論文の概要: Selection of the Most Probable Best
- arxiv url: http://arxiv.org/abs/2207.07533v1
- Date: Fri, 15 Jul 2022 15:27:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-18 16:31:36.063314
- Title: Selection of the Most Probable Best
- Title(参考訳): 最も可能性の高いベストの選択
- Authors: Taeho Kim, Kyoung-kuk Kim, Eunhye Song
- Abstract要約: 我々は、すべてのk解のシミュレーション出力が共通の不確実な入力モデルに依存する期待値ランキングと選択問題を考える。
入力モデルの不確実性が有限なサポート上の確率単純性によって捉えられることを考慮し、最適である確率が最大となる解として最も確率の高いベスト(MPB)を定義する。
まず,MPBを見つけるための効率的なサンプリングアルゴリズムを考案するために,まず,MPBを誤って選択する確率の大きな偏差率に対する低い境界を導出する。
- 参考スコア(独自算出の注目度): 2.4314805796379217
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider an expected-value ranking and selection problem where all k
solutions' simulation outputs depend on a common uncertain input model. Given
that the uncertainty of the input model is captured by a probability simplex on
a finite support, we define the most probable best (MPB) to be the solution
whose probability of being optimal is the largest. To devise an efficient
sampling algorithm to find the MPB, we first derive a lower bound to the large
deviation rate of the probability of falsely selecting the MPB, then formulate
an optimal computing budget allocation (OCBA) problem to find the optimal
static sampling ratios for all solution-input model pairs that maximize the
lower bound. We devise a series of sequential algorithms that apply
interpretable and computationally efficient sampling rules and prove their
sampling ratios achieve the optimality conditions for the OCBA problem as the
simulation budget increases. The algorithms are benchmarked against a
state-of-the-art sequential sampling algorithm designed for contextual ranking
and selection problems and demonstrated to have superior empirical performances
at finding the MPB.
- Abstract(参考訳): 我々は、すべてのk解のシミュレーション出力が共通の不確実な入力モデルに依存する期待値ランキングと選択問題を考える。
入力モデルの不確実性が有限なサポート上の確率単純性によって捉えられることを考慮し、最適である確率が最大となる解として最も確率の高いベスト(MPB)を定義する。
効率的なサンプリングアルゴリズムを考案するために、まず、MPBを誤って選択する確率の大きな偏差率に下限を導出し、次に最適計算予算割当(OCBA)問題を定式化し、下限を最大化する解-入出力モデルペアに対して最適な静的サンプリング比を求める。
本研究では, 解釈可能かつ計算効率の良いサンプリング規則を適用した逐次アルゴリズムを考案し, シミュレーション予算の増大に伴い, ocba問題の最適条件が達成されることを示す。
アルゴリズムは,コンテキストのランク付けと選択問題用に設計された最先端の逐次サンプリングアルゴリズムに対してベンチマークを行い,mpbの探索において優れた経験的性能を示すことを示した。
関連論文リスト
- Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential
Number of Optima [12.009357100208353]
本稿では,最適化アルゴリズムが大規模最適集合を処理する方法の研究を支援するために,テスト関数EqualBlocksOneMax(EBOM)を提案する。
EBOM は EBOM の理論的に理想的なモデルと非常によく似ており、このモデルは同じ最大確率で指数的に多くの最適値のそれぞれをサンプリングする。
論文 参考訳(メタデータ) (2023-10-06T06:32:07Z) - Convergence Rate Analysis for Optimal Computing Budget Allocation
Algorithms [1.713291434132985]
オーディナル最適化(Ordinal Optimization, OO)は、離散イベント動的システムを最適化するための広く研究されている手法である。
OOのよく知られた方法は、最適計算予算配分(OCBA)である。
本稿では,2つのOCBAアルゴリズムについて検討する。
論文 参考訳(メタデータ) (2022-11-27T04:55:40Z) - Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。
これらの問題に対する新規で簡単な最適化法を開発した。
結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
論文 参考訳(メタデータ) (2021-09-23T17:38:24Z) - Towards Feature-Based Performance Regression Using Trajectory Data [0.9281671380673306]
ブラックボックス最適化は非常に活発な研究領域であり、毎年多くの新しいアルゴリズムが開発されている。
アルゴリズムの多様性はメタプロブレム(メタプロブレム):どのアルゴリズムが与えられた問題を選択するか?
過去の研究では、探索ランドスケープ分析に基づくインスタンスごとのアルゴリズム選択が、このメタプロブレムに取り組むための効率的な手段であることが示されている。
論文 参考訳(メタデータ) (2021-02-10T10:19:13Z) - Efficient semidefinite-programming-based inference for binary and
multi-class MRFs [83.09715052229782]
分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。
一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
論文 参考訳(メタデータ) (2020-12-04T15:36:29Z) - Amortized Conditional Normalized Maximum Likelihood: Reliable Out of
Distribution Uncertainty Estimation [99.92568326314667]
本研究では,不確実性推定のための拡張性のある汎用的アプローチとして,償却条件正規化最大値(ACNML)法を提案する。
提案アルゴリズムは条件付き正規化最大度(CNML)符号化方式に基づいており、最小記述長の原理に従って最小値の最適特性を持つ。
我々は、ACNMLが、分布外入力のキャリブレーションの観点から、不確実性推定のための多くの手法と好意的に比較することを示した。
論文 参考訳(メタデータ) (2020-11-05T08:04:34Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - A PAC algorithm in relative precision for bandit problem with costly
sampling [0.0]
本稿ではまず,この離散最適化問題に対して,相対的精度でほぼ正解(PAC)を得るための単純帯域幅アルゴリズムを提案する。
また、同一の保証付きPACソリューションを提供する適応的帯域幅アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-07-30T09:22:25Z) - Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。
我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文 参考訳(メタデータ) (2020-04-23T05:00:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。