論文の概要: Sample-Optimal Large-Scale Optimal Subset Selection
- arxiv url: http://arxiv.org/abs/2408.09537v1
- Date: Sun, 18 Aug 2024 16:44:41 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-20 18:24:47.955626
- Title: Sample-Optimal Large-Scale Optimal Subset Selection
- Title（参考訳）: サンプル最適大規模最適サブセット選択
- Authors: Zaile Li, Weiwei Fan, L. Jeff Hong,
- Abstract要約: 私たちは、現在のトップ$m$の代替品をサンプリングし続けるトップ$m$greedy選択メカニズムを設計し、トップ$m$のサンプル手段を実行します。
EFG-$m$プロシージャはサンプル最適であり、良い選択の確率の観点から一貫したものであることを示す。
驚いたことに、EFG-$m$プロシージャは、選択した代替案のサブセット内で、余分なコストで、差分ベースのランキングを達成できることを示した。
- 参考スコア（独自算出の注目度）: 0.9558392439655016
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Ranking and selection (R&S) conventionally aims to select the unique best alternative with the largest mean performance from a finite set of alternatives. However, for better supporting decision making, it may be more informative to deliver a small menu of alternatives whose mean performances are among the top $m$. Such problem, called optimal subset selection (OSS), is generally more challenging to address than the conventional R&S. This challenge becomes even more significant when the number of alternatives is considerably large. Thus, the focus of this paper is on addressing the large-scale OSS problem. To achieve this goal, we design a top-$m$ greedy selection mechanism that keeps sampling the current top $m$ alternatives with top $m$ running sample means and propose the explore-first top-$m$ greedy (EFG-$m$) procedure. Through an extended boundary-crossing framework, we prove that the EFG-$m$ procedure is both sample optimal and consistent in terms of the probability of good selection, confirming its effectiveness in solving large-scale OSS problem. Surprisingly, we also demonstrate that the EFG-$m$ procedure enables to achieve an indifference-based ranking within the selected subset of alternatives at no extra cost. This is highly beneficial as it delivers deeper insights to decision-makers, enabling more informed decision-makings. Lastly, numerical experiments validate our results and demonstrate the efficiency of our procedures.
- Abstract（参考訳）: ランキング・アンド・セレクション(R&S)は、伝統的に、有限個の選択肢から最大の平均性能を持つ唯一の選択肢を選択することを目的としている。
しかし、より良い意思決定をサポートするために、平均的なパフォーマンスが$m$の上位にある選択肢の小さなメニューを提供する方がより有益かもしれない。
このような問題、すなわち最適部分集合選択(OSS)は、従来のR&Sよりも対処が難しい。
この課題は、選択肢の数がかなり多い場合にさらに重要になる。
そこで本論文は,大規模なOSS問題に対処することに焦点を当てている。
この目的を達成するために、トップ$m$greedy選択機構を設計し、トップ$m$実行中のサンプル手段で現在のトップ$m$代替品をサンプリングし続け、探索ファーストのトップ$m$greedy(EFG-$m$)手順を提案する。
拡張された境界交差フレームワークにより、EFG-$m$プロシージャがサンプル最適であり、良好な選択の確率の観点から一貫したものであることを証明し、大規模なOSS問題の解法の有効性を確認した。
驚いたことに、EFG-$m$プロシージャは、選択した代替案のサブセット内で、余分なコストで、差分ベースのランキングを達成できることを示した。
これは、意思決定者に深い洞察を提供し、より深い意思決定を可能にするため、非常に有益である。
最後に,提案手法の有効性を検証し,その有効性を実証する数値実験を行った。
関連論文リスト
- Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - Query Routing for Homogeneous Tools: An Instantiation in the RAG Scenario [62.615210194004106]
ツール学習に関する現在の研究は、主に様々な選択肢から最も効果的なツールを選択することに焦点を当てており、しばしば費用対効果を見落としている。
本稿では,タスクの達成に必要な性能と関連するコストの両方を予測し,同種ツールの選択に対処する。
論文 参考訳（メタデータ） (2024-06-18T09:24:09Z) - Efficient Prompt Optimization Through the Lens of Best Arm Identification [50.56113809171805]
この作業は、明示的な予算制約の下でプロンプト選択を効率的に行うための、原則化されたフレームワークであるTRIPLEを提供する。
マルチアームバンディット(MAB)における即時最適化と固定予算ベストアーム識別(BAI-FB)の間に確立された新しい接続上に構築されている。
論文 参考訳（メタデータ） (2024-02-15T05:31:13Z) - qPOTS: Efficient batch multiobjective Bayesian optimization via Pareto optimal Thompson sampling [0.0]
多目的最適化を解くためのサンプル効率のアプローチは、プロセス・オラクル・サロゲート(GP)とMOBOOTS$である。
我々はトンプソンサンプリング(TS)に基づくアプローチ(qtextttPOTS$)を提案する。
$qtextttPOTS$は、GP後部の安価な多目的最適化を進化的アプローチで解決する。
論文 参考訳（メタデータ） (2023-10-24T12:35:15Z) - Best Arm Identification for Stochastic Rising Bandits [84.55453174601826]
SRB(Rising Bandits)は、選択される度に選択肢の期待される報酬が増加する、シーケンシャルな意思決定の問題をモデル化する。
本稿では,SRBの固定予算ベストアーム識別(BAI)問題に焦点をあてる。
R-UCBE と R-SR の2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-15T08:01:37Z) - Discovering Many Diverse Solutions with Bayesian Optimization [7.136022698519586]
信頼領域を用いたランク順ベイズ最適化(ROBOT)を提案する。
ROBOTは、ユーザが特定した多様性基準に従って、多様なハイパフォーマンスソリューションのポートフォリオを見つけることを目的としている。
そこで本研究では,機能評価をほとんど必要とせず,高い性能の多様な解を多数発見できることを示す。
論文 参考訳（メタデータ） (2022-10-20T01:56:38Z) - Generalizing Bayesian Optimization with Decision-theoretic Entropies [102.82152945324381]
統計的決定論の研究からシャノンエントロピーの一般化を考える。
まず,このエントロピーの特殊なケースがBO手順でよく用いられる獲得関数に繋がることを示す。
次に、損失に対する選択肢の選択が、どのようにして柔軟な獲得関数の族をもたらすかを示す。
論文 参考訳（メタデータ） (2022-10-04T04:43:58Z) - Uncertainty-Aware Search Framework for Multi-Objective Bayesian
Optimization [40.40632890861706]
高価な関数評価を用いたマルチオブジェクト(MO)ブラックボックス最適化の問題点を考察する。
UeMOと呼ばれる新しい不確実性対応検索フレームワークを提案し、評価のための入力シーケンスを効率的に選択する。
論文 参考訳（メタデータ） (2022-04-12T16:50:48Z) - SelectAugment: Hierarchical Deterministic Sample Selection for Data
Augmentation [72.58308581812149]
そこで我々は,SelectAugmentと呼ばれる効果的な手法を提案し,決定論的かつオンラインに拡張するサンプルを選択する。
具体的には、各バッチにおいて、まず増分比率を決定し、次にこの比で各トレーニングサンプルを増分するかを決定する。
これにより、サンプルを増量する際のランダム性による負の効果を効果的に軽減し、DAの有効性を向上させることができる。
論文 参考訳（メタデータ） (2021-12-06T08:38:38Z) - Lookahead and Hybrid Sample Allocation Procedures for Multiple Attribute
Selection Decisions [0.9137554315375922]
本稿では、各測定値が1つの属性の1つのサンプルを1つの代替として生成する設定について考察する。
収集するサンプルが一定数与えられた場合、決定者は、どのサンプルを取得するかを決定し、測定を行い、属性の規模に関する事前の信念を更新し、代替案を選択する必要がある。
論文 参考訳（メタデータ） (2020-07-31T15:04:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。