論文の概要: Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing

• arxiv url: http://arxiv.org/abs/2011.11743v2
• Date: Fri, 2 Jul 2021 01:59:10 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-22 03:24:12.747991
• Title: Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing
• Title（参考訳）: オンラインマッチング,フロー,ロードバランシングのための学習可能な,インスタンス・ロバスト予測
• Authors: Thomas Lavastida, Benjamin Moseley, R. Ravi and Chenyang Xu
• Abstract要約: 本稿では,アルゴリズムが形式的に学習可能で,例えば頑健であることを要求して,予測を伴うアルゴリズムの拡張モデルを提案する。 ネットワークフロー割当問題と制限された割当ミスパン最小化の予測を含むオンラインアルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 12.961453245099044
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a new model for augmenting algorithms with predictions by requiring that they are formally learnable and instance robust. Learnability ensures that predictions can be efficiently constructed from a reasonable amount of past data. Instance robustness ensures that the prediction is robust to modest changes in the problem input, where the measure of the change may be problem specific. Instance robustness insists on a smooth degradation in performance as a function of the change. Ideally, the performance is never worse than worst-case bounds. This also allows predictions to be objectively compared. We design online algorithms with predictions for a network flow allocation problem and restricted assignment makespan minimization. For both problems, two key properties are established: high quality predictions can be learned from a small sample of prior instances and these predictions are robust to errors that smoothly degrade as the underlying problem instance changes.
• Abstract（参考訳）: 本稿では,形式的に学習可能かつインスタンスロバストなアルゴリズムを,予測によって拡張するための新しいモデルを提案する。 学習可能性により、予測は妥当な過去のデータから効率的に構築できる。 インスタンスの堅牢性は、予測が問題入力の適度な変更に対して堅牢であることを保証する。 インスタンスの堅牢性は、変更の関数としてのパフォーマンスのスムーズな低下を主張する。 理想的には、パフォーマンスは最悪のケース境界よりも悪くはない。 また、予測を客観的に比較することもできる。 我々は,ネットワークフロー割当問題と制限割当メースパン最小化の予測を伴うオンラインアルゴリズムを設計する。 両方の問題に対して、2つの重要な特性が確立されている: 以前のインスタンスの小さなサンプルから高品質の予測を学習することができ、これらの予測は、基礎となる問題インスタンスが変化したときにスムーズに劣化するエラーに頑健である。

関連論文リスト

• Learning Sample Difficulty from Pre-trained Models for Reliable Prediction [55.77136037458667]
  本稿では,大規模事前学習モデルを用いて,サンプル難易度を考慮したエントロピー正規化による下流モデルトレーニングを指導する。 我々は、挑戦的なベンチマークで精度と不確実性の校正を同時に改善する。
  論文  参考訳（メタデータ） (2023-04-20T07:29:23Z)
• A Universal Error Measure for Input Predictions Applied to Online Graph Problems [57.58926849872494]
  本稿では,入力予測における誤差の定量化のための新しい尺度を提案する。 この尺度は、予測されていない要求と予測されていない実際の要求によるエラーをキャプチャする。
  論文  参考訳（メタデータ） (2022-05-25T15:24:03Z)
• Efficient and Differentiable Conformal Prediction with General Function Classes [96.74055810115456]
  本稿では,複数の学習可能なパラメータに対する共形予測の一般化を提案する。 本研究は, クラス内において, ほぼ有効な人口被覆率, ほぼ最適効率を実現していることを示す。 実験の結果,提案アルゴリズムは有効な予測セットを学習し,効率を著しく向上できることがわかった。
  論文  参考訳（メタデータ） (2022-02-22T18:37:23Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Learning to Predict Trustworthiness with Steep Slope Loss [69.40817968905495]
  本研究では,現実の大規模データセットにおける信頼性の予測問題について検討する。 我々は、先行技術損失関数で訓練された信頼性予測器が、正しい予測と誤った予測の両方を信頼に値するものとみなす傾向があることを観察する。 そこで我々は,2つのスライド状の曲線による不正確な予測から,特徴w.r.t.正しい予測を分離する,新たな急勾配損失を提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:19:09Z)
• Backward-Compatible Prediction Updates: A Probabilistic Approach [12.049279991559091]
  本稿では,予測更新問題を定式化し,上記の質問に対する効率的な確率的アプローチを提案する。 標準分類ベンチマークデータセットの広範な実験において,提案手法は後方互換性のある予測更新のための代替戦略よりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-07-02T13:05:31Z)
• Improving Uncertainty Calibration via Prior Augmented Data [56.88185136509654]
  ニューラルネットワークは、普遍関数近似器として機能することで、複雑なデータ分布から学習することに成功した。 彼らはしばしば予測に自信過剰であり、不正確で誤った確率的予測に繋がる。 本稿では,モデルが不当に過信である特徴空間の領域を探索し,それらの予測のエントロピーをラベルの以前の分布に対して条件的に高める手法を提案する。
  論文  参考訳（メタデータ） (2021-02-22T07:02:37Z)
• Bayes DistNet -- A Robust Neural Network for Algorithm Runtime Distribution Predictions [1.8275108630751844]
  ランダム化アルゴリズムは制約満足度問題 (CSP) やブール満足度問題 (SAT) の多くの最先端の解法で用いられている。 従来の最先端の手法は、入力インスタンスが従う固定パラメトリック分布を直接予測しようとする。 この新モデルは,低観測環境下での堅牢な予測性能と,検閲された観測処理を実現する。
  論文  参考訳（メタデータ） (2020-12-14T01:15:39Z)
• Predictive Business Process Monitoring via Generative Adversarial Nets: The Case of Next Event Prediction [0.026249027950824504]
  本稿では,次の事象予測の問題に対処するための,新たな逆トレーニングフレームワークを提案する。 これは、2人のプレイヤーのゲームで1つのニューラルネットワークをもう1つのニューラルネットワークと対戦させることで機能し、それは地上の真実と区別できない予測につながる。 単純なネットワークアーキテクチャとナイーブな特徴符号化を使用しても、正確さと予測のイヤーラインの両方において、体系的にすべてのベースラインを上回ります。
  論文  参考訳（メタデータ） (2020-03-25T08:31:28Z)

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

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