論文の概要: Online List Labeling with Predictions

• arxiv url: http://arxiv.org/abs/2305.10536v2
• Date: Tue, 20 Jun 2023 13:45:49 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-22 02:11:36.397003
• Title: Online List Labeling with Predictions
• Title（参考訳）: 予測付きオンラインリストラベリング
• Authors: Samuel McCauley, Benjamin Moseley, Aidin Niaparast, Shikha Singh
• Abstract要約: オンラインリストラベリングの基本的な問題において,予測が活用可能であることを示す。 問題では、n個のアイテムが時間とともに到着し、サイズ Theta(n) の配列でソートされた順序で格納されなければならない。 データ構造をラベル付けした新しいリストを設計し、その性能を2つのモデルでバインドする。
• 参考スコア（独自算出の注目度）: 13.126494821223755
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A growing line of work shows how learned predictions can be used to break through worst-case barriers to improve the running time of an algorithm. However, incorporating predictions into data structures with strong theoretical guarantees remains underdeveloped. This paper takes a step in this direction by showing that predictions can be leveraged in the fundamental online list labeling problem. In the problem, n items arrive over time and must be stored in sorted order in an array of size Theta(n). The array slot of an element is its label and the goal is to maintain sorted order while minimizing the total number of elements moved (i.e., relabeled). We design a new list labeling data structure and bound its performance in two models. In the worst-case learning-augmented model, we give guarantees in terms of the error in the predictions. Our data structure provides strong guarantees: it is optimal for any prediction error and guarantees the best-known worst-case bound even when the predictions are entirely erroneous. We also consider a stochastic error model and bound the performance in terms of the expectation and variance of the error. Finally, the theoretical results are demonstrated empirically. In particular, we show that our data structure has strong performance on real temporal data sets where predictions are constructed from elements that arrived in the past, as is typically done in a practical use case.
• Abstract（参考訳）: アルゴリズムの実行時間を改善するために、学習した予測を使って最悪のケースバリアを突破する方法が示されています。 しかし、強い理論的保証を持つデータ構造に予測を組み込むことは未開発である。 本稿では,この方向を一歩進めて,基本的なオンラインリストラベリング問題において予測を活用できることを示す。 問題では、n個のアイテムが時間とともに到着し、サイズ Theta(n) の配列でソート順序で格納されなければならない。 要素の配列スロットはそのラベルであり、移動された要素の総数(すなわちrelabeled)を最小化しながらソートされた順序を維持することを目的としている。 データ構造をラベル付けした新しいリストを設計し、その性能を2つのモデルでバインドする。 最悪の場合の学習強化モデルでは、予測における誤差の観点から保証を与える。 我々のデータ構造は、予測エラーに対して最適であり、予測が完全に誤っている場合でも、最もよく知られた最悪のケース境界を保証する。 また,確率的誤差モデルを検討し,誤差の期待と分散の観点から性能を限定する。 最後に、理論結果は実証的に示される。 特に,我々のデータ構造は,過去に到達した要素から予測が構築される実時間データセットにおいて,現実のユースケースのように強いパフォーマンスを示す。

関連論文リスト

• Stochastic Online Conformal Prediction with Semi-Bandit Feedback [29.334511328067777]
  実例が時間とともに現れるオンライン学習環境について検討し、その目標は予測セットを動的に構築することである。 本稿では,この設定を対象とする新しい共形予測アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-22T00:42:49Z)
• PAC Prediction Sets Under Label Shift [52.30074177997787]
  予測セットは、個々のラベルではなくラベルのセットを予測することによって不確実性を捉える。 ラベルシフト設定においてPAC保証付き予測セットを構築するための新しいアルゴリズムを提案する。 提案手法を5つのデータセットで評価する。
  論文  参考訳（メタデータ） (2023-10-19T17:57:57Z)
• Cross-Prediction-Powered Inference [15.745692520785074]
  クロスプレディクション(Cross-prediction)は、機械学習を利用した推論の検証方法である。 予測による推論の適応よりもクロス予測の方が一貫して強力であることを示す。
  論文  参考訳（メタデータ） (2023-09-28T17:01:58Z)
• Efficient and Differentiable Conformal Prediction with General Function Classes [96.74055810115456]
  本稿では,複数の学習可能なパラメータに対する共形予測の一般化を提案する。 本研究は, クラス内において, ほぼ有効な人口被覆率, ほぼ最適効率を実現していることを示す。 実験の結果,提案アルゴリズムは有効な予測セットを学習し,効率を著しく向上できることがわかった。
  論文  参考訳（メタデータ） (2022-02-22T18:37:23Z)
• Conformal prediction for the design problem [72.14982816083297]
  機械学習の現実的な展開では、次にテストすべきデータを選択するために予測アルゴリズムを使用します。 このような設定では、トレーニングデータとテストデータの間には、異なるタイプの分散シフトがある。 このような環境で予測の不確実性を定量化する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-08T02:59:12Z)
• Generalized Adversarial Distances to Efficiently Discover Classifier Errors [0.0]
  高信頼エラーは、モデルがその予測に非常に自信を持っているが間違っている稀な出来事である。 本稿では,機械学習の概念を活用し,逆距離探索の一般化を提案する。 実験結果から, 一般化された手法では, 予測値の信頼度から, 予測値よりも誤差が大きいことがわかった。
  論文  参考訳（メタデータ） (2021-02-25T13:31:21Z)
• Distribution-Free, Risk-Controlling Prediction Sets [112.9186453405701]
  ユーザ特定レベルにおける将来のテストポイントにおける期待損失を制御するブラックボックス予測器から設定値予測を生成する方法を示す。 提案手法は,予測セットのサイズをキャリブレーションするホールドアウトセットを用いて,任意のデータセットに対して明確な有限サンプル保証を提供する。
  論文  参考訳（メタデータ） (2021-01-07T18:59:33Z)
• Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing [12.961453245099044]
  本稿では,アルゴリズムが形式的に学習可能で,例えば頑健であることを要求して,予測を伴うアルゴリズムの拡張モデルを提案する。 ネットワークフロー割当問題と制限された割当ミスパン最小化の予測を含むオンラインアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-11-23T21:38:57Z)
• Learning Output Embeddings in Structured Prediction [73.99064151691597]
  構造化予測に対する強力で柔軟なアプローチは、予測される構造化対象を潜在的に無限次元の特徴空間に埋め込むことである。 原空間における予測は、前像問題の解法により計算される。 本研究では,新しい特徴空間に出力埋め込みと回帰関数の有限近似を共同で学習することを提案する。
  論文  参考訳（メタデータ） (2020-07-29T09:32:53Z)
• Ambiguity in Sequential Data: Predicting Uncertain Futures with Recurrent Models [110.82452096672182]
  逐次データによる曖昧な予測を扱うために,Multiple hypothesis Prediction(MHP)モデルの拡張を提案する。 また、不確実性を考慮するのに適した曖昧な問題に対する新しい尺度も導入する。
  論文  参考訳（メタデータ） (2020-03-10T09:15:42Z)

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

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