論文の概要: Best of Many in Both Worlds: Online Resource Allocation with Predictions under Unknown Arrival Model
- arxiv url: http://arxiv.org/abs/2402.13530v2
- Date: Sat, 22 Jun 2024 21:24:15 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-26 01:51:30.686074
- Title: Best of Many in Both Worlds: Online Resource Allocation with Predictions under Unknown Arrival Model
- Title（参考訳）: 両世界の多くの人々のベスト:未知の領域モデルに基づく予測付きオンラインリソース割り当て
- Authors: Lin An, Andrew A. Li, Benjamin Moseley, Gabriel Visotsky,
- Abstract要約: オンライン意思決定者は、到着や要求など、将来の変数に関する予測を得ることが多い。
意思決定者にとって予測精度は未知であるため、予測に盲目的に追従することは有害である。
我々は未知の予測精度に頑健な方法で予測を利用するアルゴリズムを開発した。
- 参考スコア（独自算出の注目度）: 16.466711636334587
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Online decision-makers often obtain predictions on future variables, such as arrivals, demands, inventories, and so on. These predictions can be generated from simple forecasting algorithms for univariate time-series, all the way to state-of-the-art machine learning models that leverage multiple time-series and additional feature information. However, the prediction accuracy is unknown to decision-makers a priori, hence blindly following the predictions can be harmful. In this paper, we address this problem by developing algorithms that utilize predictions in a manner that is robust to the unknown prediction accuracy. We consider the Online Resource Allocation Problem, a generic model for online decision-making, in which a limited amount of resources may be used to satisfy a sequence of arriving requests. Prior work has characterized the best achievable performances when the arrivals are either generated stochastically (i.i.d.) or completely adversarially, and shown that algorithms exist which match these bounds under both arrival models, without ``knowing'' the underlying model. To this backdrop, we introduce predictions in the form of shadow prices on each type of resource. Prediction accuracy is naturally defined to be the distance between the predictions and the actual shadow prices. We tightly characterize, via a formal lower bound, the extent to which any algorithm can optimally leverage predictions (that is, to ``follow'' the predictions when accurate, and ``ignore'' them when inaccurate) without knowing the prediction accuracy or the underlying arrival model. Our main contribution is then an algorithm which achieves this lower bound. Finally, we empirically validate our algorithm with a large-scale experiment on real data from the retailer H&M.
- Abstract（参考訳）: オンライン意思決定者は、到着、要求、在庫など、将来の変数に関する予測を得ることが多い。
これらの予測は、単変量時系列の単純な予測アルゴリズムから、複数の時系列と追加の機能情報を活用する最先端の機械学習モデルまで、すべて生成することができる。
しかし、事前判断者にとって予測精度は未知であるため、予測に盲目的に従うことは有害である可能性がある。
本稿では,未知の予測精度に頑健な予測アルゴリズムを開発することにより,この問題に対処する。
本稿では,オンライン意思決定の汎用モデルであるオンラインリソース割当問題について考察する。
先行研究は、到着が確率的に(つまり)あるいは完全に逆向きに生成されるとき、最も達成可能なパフォーマンスを特徴付けており、基礎となるモデル「知識」を使わずに、両方の到着モデルの下でこれらの境界に一致するアルゴリズムが存在することを示した。
この背景として,資源の種類ごとに影価格の形で予測を導入する。
予測精度は、予測と実際の影価格の間の距離として自然に定義される。
我々は、任意のアルゴリズムが予測を最適に活用できる範囲(正確には「follow」、不正確な場合は「ignore」、不正確な場合は「ignore」)を、予測精度や下層の到着モデルを知ることなく、形式的な下限によって強く特徴づける。
我々の主な貢献は、この下限を達成するアルゴリズムである。
最後に,小売業者のH&Mによる実データに対する大規模な実験により,我々のアルゴリズムを実証的に検証した。
関連論文リスト
- Next Best View For Point-Cloud Model Acquisition: Bayesian Approximation and Uncertainty Analysis [2.07180164747172]
この研究は、Next-Best-View(PC-NBV)にポイントネットベースのニューラルネットワークを適用する。
モデルアーキテクチャにドロップアウト層を組み込むことで、予測に関連する不確実性推定の計算を可能にする。
本研究の目的は,次の視点を正確に予測することで,ネットワークの精度を向上させることである。
論文 参考訳（メタデータ） (2024-11-04T01:32:09Z) - Towards Human-AI Complementarity with Prediction Sets [14.071862670474832]
予測セットに基づく意思決定支援システムは、人間の専門家が分類タスクを解くのに役立つことが証明されている。
共形予測を用いて構築された予測集合は、一般に平均精度の点で準最適であることを示す。
我々は,多種多様な専門家モデルと非最適スコアに対して,同等あるいはより優れた性能を提供する予測セットを見つけることが保証される,欲求的アルゴリズムを導入する。
論文 参考訳（メタデータ） (2024-05-27T18:00:00Z) - Algorithms with Prediction Portfolios [23.703372221079306]
我々は、マッチング、ロードバランシング、非クレアボイラントスケジューリングなど、多くの基本的な問題に対する複数の予測器の使用について検討する。
これらの問題のそれぞれに対して、複数の予測器を利用する新しいアルゴリズムを導入し、その結果のパフォーマンスに限界を証明します。
論文 参考訳（メタデータ） (2022-10-22T12:58:07Z) - Paging with Succinct Predictions [25.959849403994202]
予測情報を最小限に抑えるという新たな視点から学習増強型ページングについて検討する。
学習強化アルゴリズムの3つの望ましい特性をすべて満たす2つの設定のアルゴリズムを開発する。
論文 参考訳（メタデータ） (2022-10-06T09:26:34Z) - Uncertainty estimation of pedestrian future trajectory using Bayesian
approximation [137.00426219455116]
動的トラフィックシナリオでは、決定論的予測に基づく計画は信頼できない。
著者らは、決定論的アプローチが捉えられない近似を用いて予測中の不確実性を定量化する。
将来の状態の不確実性に対する降雨重量と長期予測の影響について検討した。
論文 参考訳（メタデータ） (2022-05-04T04:23:38Z) - Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。
我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。
これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
論文 参考訳（メタデータ） (2022-02-21T13:18:11Z) - Robustification of Online Graph Exploration Methods [59.50307752165016]
我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。
本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-10T10:02:31Z) - Dense Uncertainty Estimation [62.23555922631451]
本稿では,ニューラルネットワークと不確実性推定手法について検討し,正確な決定論的予測と確実性推定の両方を実現する。
本研究では,アンサンブルに基づく手法と生成モデルに基づく手法の2つの不確実性推定法について検討し,それらの長所と短所を,完全/半端/弱度に制御されたフレームワークを用いて説明する。
論文 参考訳（メタデータ） (2021-10-13T01:23:48Z) - Learning to Predict Trustworthiness with Steep Slope Loss [69.40817968905495]
本研究では,現実の大規模データセットにおける信頼性の予測問題について検討する。
我々は、先行技術損失関数で訓練された信頼性予測器が、正しい予測と誤った予測の両方を信頼に値するものとみなす傾向があることを観察する。
そこで我々は,2つのスライド状の曲線による不正確な予測から,特徴w.r.t.正しい予測を分離する,新たな急勾配損失を提案する。
論文 参考訳（メタデータ） (2021-09-30T19:19:09Z) - Private Prediction Sets [72.75711776601973]
機械学習システムは、個人のプライバシーの確実な定量化と保護を必要とする。
これら2つのデシラタを共同で扱う枠組みを提案する。
本手法を大規模コンピュータビジョンデータセット上で評価する。
論文 参考訳（メタデータ） (2021-02-11T18:59:11Z) - Bayes DistNet -- A Robust Neural Network for Algorithm Runtime
Distribution Predictions [1.8275108630751844]
ランダム化アルゴリズムは制約満足度問題 (CSP) やブール満足度問題 (SAT) の多くの最先端の解法で用いられている。
従来の最先端の手法は、入力インスタンスが従う固定パラメトリック分布を直接予測しようとする。
この新モデルは,低観測環境下での堅牢な予測性能と,検閲された観測処理を実現する。
論文 参考訳（メタデータ） (2020-12-14T01:15:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。