論文の概要: High-Dimensional Prediction for Sequential Decision Making
- arxiv url: http://arxiv.org/abs/2310.17651v2
- Date: Fri, 27 Oct 2023 17:59:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-30 10:42:29.433567
- Title: High-Dimensional Prediction for Sequential Decision Making
- Title(参考訳): シークエンシャル意思決定の高次元予測
- Authors: Georgy Noarov, Ramya Ramalingam, Aaron Roth, Stephan Xie
- Abstract要約: 本研究では,任意の条件付けイベントの収集対象である逆選択された高次元状態の予測を行う問題について検討する。
この問題を解決するための効率的なアルゴリズムと、適切な条件付けイベントを選択することに起因する多くのアプリケーションを提供します。
- 参考スコア(独自算出の注目度): 9.684829814477526
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of making predictions of an adversarially chosen
high-dimensional state that are unbiased subject to an arbitrary collection of
conditioning events, with the goal of tailoring these events to downstream
decision makers. We give efficient algorithms for solving this problem, as well
as a number of applications that stem from choosing an appropriate set of
conditioning events.
For example, we can efficiently make predictions targeted at polynomially
many decision makers, giving each of them optimal swap regret if they
best-respond to our predictions. We generalize this to online combinatorial
optimization, where the decision makers have a very large action space, to give
the first algorithms offering polynomially many decision makers no regret on
polynomially many subsequences that may depend on their actions and the
context. We apply these results to get efficient no-subsequence-regret
algorithms in extensive-form games (EFGs), yielding a new family of regret
guarantees for EFGs that generalizes some existing EFG regret notions, e.g.
regret to informed causal deviations, and is generally incomparable to other
known such notions.
Next, we develop a novel transparent alternative to conformal prediction for
building valid online adversarial multiclass prediction sets. We produce class
scores that downstream algorithms can use for producing valid-coverage
prediction sets, as if these scores were the true conditional class
probabilities. We show this implies strong conditional validity guarantees
including set-size-conditional and multigroup-fair coverage for polynomially
many downstream prediction sets. Moreover, our class scores can be guaranteed
to have improved $L_2$ loss, cross-entropy loss, and generally any Bregman
loss, compared to any collection of benchmark models, yielding a
high-dimensional real-valued version of omniprediction.
- Abstract(参考訳): 本研究では,任意のコンディショニングイベントの収集対象とならない,敵対的に選択された高次元状態の予測を,下流の意思決定者に合わせることを目的として行う。
この問題を解決するための効率的なアルゴリズムと、適切なコンディショニングイベントを選択することに起因する多くのアプリケーションを提供します。
例えば、多項式的に多くの意思決定者をターゲットにした予測を効率的に行うことができ、予測に最もよく対応すれば、それぞれが最適なスワップ後悔を与えます。
我々は、意思決定者が非常に大きなアクション空間を持つオンライン組合せ最適化にこれを一般化し、多項式的に多くの意思決定者に提供する最初のアルゴリズムに、そのアクションとコンテキストに依存する可能性のある多項式的部分列を後悔しないようにする。
これらの結果を適用して、広範形式ゲーム(EFG)における効率のよい非逐次回帰アルゴリズム(non-subsequence-regret algorithm)を得るとともに、既存のEFGの後悔概念(例えば、因果偏差に対する後悔)を一般化するEFGに対する新しい遺族を与える。
次に,オンラインで有効な対向的多クラス予測セットを構築するための,コンフォメーション予測の新たな透明な代替手法を開発する。
下流アルゴリズムが有効な被覆予測セットを作成するのに使用できるクラススコアを,そのスコアが真の条件付きクラス確率であるかのように作成する。
これは、多項式に多数存在する下流予測集合に対して、セットサイズ条件付きおよびマルチグループフェアカバレッジを含む強い条件付き妥当性保証を示す。
さらに、我々のクラススコアは、任意のベンチマークモデルと比較すると、$L_2$損失、クロスエントロピー損失、および一般的なブレグマン損失の改善が保証され、高次元の実測値バージョンが得られる。
関連論文リスト
- Optimal Transport-based Conformal Prediction [8.302146576157497]
コンフォーマル予測(CP)は、ブラックボックス学習モデルにおける不確実性のための原則化されたフレームワークである。
レンズを通して予測スコア関数を処理する新しいCPプロシージャを提案する。
次に,マルチ出力回帰とマルチクラス分類の定量化に本手法を適用した。
論文 参考訳(メタデータ) (2025-01-31T09:48:28Z) - Conformal Generative Modeling with Improved Sample Efficiency through Sequential Greedy Filtering [55.15192437680943]
生成モデルは出力に対する厳密な統計的保証を欠いている。
厳密な統計的保証を満たす予測セットを生成する逐次共形予測法を提案する。
このことは、高い確率で予測セットが少なくとも1つの許容可能な(または有効な)例を含むことを保証している。
論文 参考訳(メタデータ) (2024-10-02T15:26:52Z) - Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
確率に基づく推論の原理を再検討し、確率比を用いて妥当な信頼シーケンスを構築することを提案する。
本手法は, 精度の高い問題に特に適している。
提案手法は,オンライン凸最適化への接続に光を当てることにより,推定器の最適シーケンスを確実に選択する方法を示す。
論文 参考訳(メタデータ) (2023-11-08T00:10:21Z) - When Does Confidence-Based Cascade Deferral Suffice? [69.28314307469381]
カスケードは、推論コストをサンプル毎に適応的に変化させる古典的な戦略である。
deferralルールは、シーケンス内の次の分類子を呼び出すか、または予測を終了するかを決定する。
カスケードの構造に執着しているにもかかわらず、信頼に基づく推論は実際は極めてうまく機能することが多い。
論文 参考訳(メタデータ) (2023-07-06T04:13:57Z) - Bayesian Optimization with Conformal Prediction Sets [44.565812181545645]
コンフォーマル予測(Conformal prediction)は、不確実な定量化手法であり、不特定モデルに対してもカバレッジを保証する。
本稿では,モデルの妥当性が保証された検索空間の領域にクエリを誘導する共形ベイズ最適化を提案する。
多くの場合、クエリのカバレッジはサンプル効率を損なうことなく大幅に改善できる。
論文 参考訳(メタデータ) (2022-10-22T17:01:05Z) - Generalizing Bayesian Optimization with Decision-theoretic Entropies [102.82152945324381]
統計的決定論の研究からシャノンエントロピーの一般化を考える。
まず,このエントロピーの特殊なケースがBO手順でよく用いられる獲得関数に繋がることを示す。
次に、損失に対する選択肢の選択が、どのようにして柔軟な獲得関数の族をもたらすかを示す。
論文 参考訳(メタデータ) (2022-10-04T04:43:58Z) - Efficient and Differentiable Conformal Prediction with General Function
Classes [96.74055810115456]
本稿では,複数の学習可能なパラメータに対する共形予測の一般化を提案する。
本研究は, クラス内において, ほぼ有効な人口被覆率, ほぼ最適効率を実現していることを示す。
実験の結果,提案アルゴリズムは有効な予測セットを学習し,効率を著しく向上できることがわかった。
論文 参考訳(メタデータ) (2022-02-22T18:37:23Z) - Bayesian decision-making under misspecified priors with applications to
meta-learning [64.38020203019013]
トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。
性能は不特定な事前条件で優雅に低下することを示す。
論文 参考訳(メタデータ) (2021-07-03T23:17:26Z) - The Perils of Learning Before Optimizing [16.97597806975415]
本稿では,最適化タスクを通じて予測モデルを識別することで,エンドツーエンドで予測モデルを学習する方法を示す。
2段階のアプローチとエンドツーエンドのアプローチのパフォーマンスギャップは、最適化における相関の概念の強調と密接に関係していることが示される。
論文 参考訳(メタデータ) (2021-06-18T20:43:47Z) - Efficient Conformal Prediction via Cascaded Inference with Expanded
Admission [43.596058175459746]
共形予測(CP)のための新しい手法を提案する。
我々は、単一の予測の代わりに、予測候補のセットを特定することを目指している。
この集合は、高い確率で正しい答えを含むことが保証される。
論文 参考訳(メタデータ) (2020-07-06T23:13:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。