論文の概要: Online Algorithms with Uncertainty-Quantified Predictions

• arxiv url: http://arxiv.org/abs/2310.11558v1
• Date: Tue, 17 Oct 2023 20:09:41 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-19 12:08:35.070752
• Title: Online Algorithms with Uncertainty-Quantified Predictions
• Title（参考訳）: 不確実な予測付きオンラインアルゴリズム
• Authors: Bo Sun, Jerry Huang, Nicolas Christianson, Mohammad Hajiesmaili, Adam Wierman
• Abstract要約: 本稿では,オンラインアルゴリズムの設計における不確実性定量化予測を最適に活用する方法について考察する。 特に,基底真理が一定の範囲に落下する可能性を示す不確実な定量化を付加した予測について考察する。 いずれの場合も、確率論的予測を完全に活用するためには、アルゴリズム設計に対する非自明な修正が必要であることを実証する。
• 参考スコア（独自算出の注目度）: 12.57910560144628
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Online algorithms with predictions have become a trending topic in the field of beyond worst-case analysis of algorithms. These algorithms incorporate predictions about the future to obtain performance guarantees that are of high quality when the predictions are good, while still maintaining bounded worst-case guarantees when predictions are arbitrarily poor. In general, the algorithm is assumed to be unaware of the prediction's quality. However, recent developments in the machine learning literature have studied techniques for providing uncertainty quantification on machine-learned predictions, which describes how certain a model is about its quality. This paper examines the question of how to optimally utilize uncertainty-quantified predictions in the design of online algorithms. In particular, we consider predictions augmented with uncertainty quantification describing the likelihood of the ground truth falling in a certain range, designing online algorithms with these probabilistic predictions for two classic online problems: ski rental and online search. In each case, we demonstrate that non-trivial modifications to algorithm design are needed to fully leverage the probabilistic predictions. Moreover, we consider how to utilize more general forms of uncertainty quantification, proposing a framework based on online learning that learns to exploit uncertainty quantification to make optimal decisions in multi-instance settings.
• Abstract（参考訳）: 予測付きオンラインアルゴリズムは、アルゴリズムの最悪のケース分析以上の分野でトレンドとなっている。 これらのアルゴリズムは将来の予測を取り込んで、予測が良ければ高品質なパフォーマンス保証を得る一方で、予測が任意に貧弱な場合には境界付きの最悪の保証を維持する。 一般に、このアルゴリズムは予測の品質に気付いていないと仮定される。 しかし、機械学習文学における最近の進展は、モデルがその品質に関する確実性を示す機械学習予測に対する不確実性定量化技術の研究を行っている。 本稿では,オンラインアルゴリズムの設計における不確実性定量化予測の最適活用方法について考察する。 特に,スキーレンタルとオンライン検索という2つの古典的なオンライン問題に対して,これらの確率的予測を用いたオンラインアルゴリズムをデザインし,一定の範囲の根拠真理の可能性を記述した不確実性定量化による予測を考察する。 いずれの場合も、確率論的予測を完全に活用するためには、アルゴリズム設計に対する非自明な修正が必要である。 さらに,より一般的な不確実性定量化の活用方法を考察し,不確実性定量化を活用し,マルチインスタンス環境で最適な決定を行うオンライン学習に基づく枠組みを提案する。

関連論文リスト

• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  オンライン優先制約による非サーボ的スケジューリングについて検討する。 アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
  論文  参考訳（メタデータ） (2023-01-30T13:17:15Z)
• Online TSP with Predictions [3.8411077568039866]
  古典的オンライン旅行セールスマン問題(OLTSP)について検討する。 他の研究の予測モデルとは異なり、OLTSPの実際の要求はその到着時間と位置に関連しており、予測された要求と一致しないかもしれない。 我々の主な成果は、様々な予測モデルと設計アルゴリズムを研究し、異なる設定で最もよく知られた結果を改善することである。
  論文  参考訳（メタデータ） (2022-06-30T15:35:53Z)
• Online Algorithms with Multiple Predictions [17.803569868141647]
  本稿では,複数の機械学習予測を付加したオンラインアルゴリズムについて検討する。 我々のアルゴリズムは、オンラインアルゴリズムの古典的ポテンシャルに基づく分析に予測の利用を取り入れている。
  論文  参考訳（メタデータ） (2022-05-08T17:33:01Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。 我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。 これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-21T13:18:11Z)
• Learning Predictions for Algorithms with Predictions [49.341241064279714]
  予測器を学習するアルゴリズムに対して,一般的な設計手法を導入する。 オンライン学習の手法を応用して、敵のインスタンスに対して学習し、堅牢性と一貫性のあるトレードオフを調整し、新しい統計的保証を得る。 両部マッチング,ページマイグレーション,スキーレンタル,ジョブスケジューリングの手法を解析することにより,学習アルゴリズムの導出におけるアプローチの有効性を実証する。
  論文  参考訳（メタデータ） (2022-02-18T17:25:43Z)
• Parsimonious Learning-Augmented Caching [29.975391787684966]
  本稿では,学習補助アルゴリズムが同時に予測を利用できるような設定を導入し,研究する。 定量的に類似した結果が得られるが、予測のサブ線形数のみを用いることを示す。
  論文  参考訳（メタデータ） (2022-02-09T03:40:11Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。