論文の概要: Solving the Online Assignment Problem with Machine Learned Advice
- arxiv url: http://arxiv.org/abs/2208.04016v1
- Date: Mon, 8 Aug 2022 09:54:22 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-09 14:25:05.500200
- Title: Solving the Online Assignment Problem with Machine Learned Advice
- Title（参考訳）: 機械学習によるオンラインアサインメント問題の解決
- Authors: Clarence Gabriel R. Kasilag, Pollux M. Rey, Jhoirene B. Clemente
- Abstract要約: オンライン代入問題に対するオンラインアルゴリズムは、事前に入力全体を予測する機械学習アルゴリズムをシミュレートして提供する。
機械学習予測誤差が増加するにつれて、解の質が低下することを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The online assignment problem plays an important role in operational research
and computer science which is why immense attention has been given to improving
its solution quality. Due to the incomplete information about the input, it is
difficult for online algorithms to produce the optimal solution. The quality of
the solution of an online algorithm is measured using a competitive ratio. No
online deterministic algorithm can achieve a competitive ratio better than
(2n-1). It has been shown that advice in online computation improves the lower
bound of the competitive ratio of online problems. Advice in online computation
can be interpreted as additional information for the online algorithm to
compensate for the lack of information about the whole input sequence. In this
study, we investigate how introducing machine-learned advice could improve the
competitive ratio for this problem. We provide an online algorithm for the
online assignment problem by simulating a machine learning algorithm that
predicts the whole input in advance. We utilize an optimal offline algorithm to
provide a matching solution from the predicted input. Furthermore, we
investigate how the prediction error of machine learning affects the
competitive ratio of the online algorithm. We utilize a benchmark data set to
perform our empirical analysis. We show that as the Machine Learning prediction
error increases, the solution quality decreases. Moreover, the magnitude of
error is directly proportional to the size of the input. This result is
analogous to the competitive ratio of the best deterministic algorithm for the
online assignment problem which is dependent also on the parameter n.
- Abstract（参考訳）: オンライン割り当て問題は、運用研究やコンピュータ科学において重要な役割を果たすため、ソリューションの品質向上に多大な注意が払われている。
入力に関する不完全な情報のため、オンラインアルゴリズムが最適解を生成することは困難である。
オンラインアルゴリズムの解の質は、競合比を用いて測定される。
オンライン決定論的アルゴリズムは (2n-1) よりも競争率を向上できない。
オンライン計算におけるアドバイスは、オンライン問題の競争比率の低さを改善できることが示されている。
オンライン計算のアドバイスは、入力シーケンス全体の情報不足を補うオンラインアルゴリズムのための追加情報として解釈することができる。
本研究では,機械学習によるアドバイスの導入が,この問題に対する競争率をいかに向上させるかを検討する。
オンライン代入問題に対するオンラインアルゴリズムは、事前に入力全体を予測する機械学習アルゴリズムをシミュレートして提供する。
最適なオフラインアルゴリズムを用いて,予測入力からのマッチングソリューションを提供する。
さらに,機械学習の予測誤差がオンラインアルゴリズムの競争比に与える影響について検討した。
ベンチマークデータセットを使用して経験的分析を行います。
機械学習予測誤差が増加するにつれて、解の質が低下することを示す。
さらに、誤差の大きさは入力のサイズに直接比例する。
この結果は、パラメータ n にも依存するオンライン代入問題に対する最良の決定論的アルゴリズムの競合比に類似している。
関連論文リスト
- Understanding the performance gap between online and offline alignment algorithms [63.137832242488926]
オフラインのアルゴリズムは、ペアの分類が得意になるようにポリシーを訓練し、オンラインのアルゴリズムは世代ごとに良いことを示しています。
このことは、識別能力と生成能力の間のユニークな相互作用を示唆しており、これはサンプリングプロセスに大きく影響している。
我々の研究は、AIアライメントにおけるオンラインサンプリングの重要な役割に光を当て、オフラインアライメントアルゴリズムのある種の根本的な課題を示唆している。
論文 参考訳（メタデータ） (2024-05-14T09:12:30Z) - Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。
この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。
本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
論文 参考訳（メタデータ） (2024-03-12T08:40:21Z) - Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms [11.029788598491077]
エネルギーとサステナビリティの交差点で発生した問題を捉えるオンライン問題の一群である,スイッチングコストによるオンライン変換について検討する。
本稿では,この問題の決定論的および決定論的変異に対して,競合的(ロバストな)しきい値に基づくアルゴリズムを導入する。
そこで我々は,ブラックボックスのアドバイスを活かした学習強化アルゴリズムを提案し,平均ケース性能を著しく向上させた。
論文 参考訳（メタデータ） (2023-10-31T16:34:49Z) - Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental
Problem via Best-Possible Competitive Analysis [0.1529342790344802]
マルチオプションスキーレンタル問題に対する学習向上アルゴリズムを提案する。
提案アルゴリズムは,この問題に対して最も有効なランダム化競合アルゴリズムに基づいている。
論文 参考訳（メタデータ） (2023-02-14T05:05:03Z) - Robustification of Online Graph Exploration Methods [59.50307752165016]
我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。
本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-10T10:02:31Z) - Adversarial Deep Learning for Online Resource Allocation [12.118811903399951]
私たちはディープニューラルネットワークを使って、リソース割り当てと価格の問題に対するオンラインアルゴリズムをゼロから学習しています。
私たちの研究は、最悪のパフォーマンス保証の観点から、ディープニューラルネットワークを使用してオンラインアルゴリズムを設計した初めてのものです。
論文 参考訳（メタデータ） (2021-11-19T15:48:43Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳（メタデータ） (2021-09-13T18:10:52Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳（メタデータ） (2021-03-02T11:04:33Z) - Metrical Task Systems with Online Machine Learned Advice [0.0]
機械学習予測器によるオンラインアルゴリズムの強化は,予測器の精度が適切であれば,競争比を確実に低下させることができることを示す。
我々は、$n$タスク上の一様タスクシステムの特定のクラスに焦点を当て、最良の決定論的アルゴリズムは$O(n)$競争であり、最良のランダム化アルゴリズムは$O(log n)$競争である。
論文 参考訳（メタデータ） (2020-12-17T04:56:51Z) - Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online
Algorithms [85.97516436641533]
機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。
目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。
機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
論文 参考訳（メタデータ） (2020-10-22T04:51:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。