論文の概要: Active clustering with bandit feedback
- arxiv url: http://arxiv.org/abs/2406.11485v1
- Date: Mon, 17 Jun 2024 12:52:19 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-18 14:51:50.296605
- Title: Active clustering with bandit feedback
- Title（参考訳）: 帯域フィードバックによるアクティブクラスタリング
- Authors: Victor Thuot, Alexandra Carpentier, Christophe Giraud, Nicolas Verzelen,
- Abstract要約: アクティブクラスタリング問題(ACP)について検討する。
学習者は$N$の武器付きバンディットと$d$次元のサブガウスフィードバックで対話する。
同じ群内の腕が同じ平均ベクトルを共有するように、腕をK$グループに隠した分割が存在する。
- 参考スコア（独自算出の注目度）: 47.131735525178144
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the Active Clustering Problem (ACP). A learner interacts with an $N$-armed stochastic bandit with $d$-dimensional subGaussian feedback. There exists a hidden partition of the arms into $K$ groups, such that arms within the same group, share the same mean vector. The learner's task is to uncover this hidden partition with the smallest budget - i.e., the least number of observation - and with a probability of error smaller than a prescribed constant $\delta$. In this paper, (i) we derive a non-asymptotic lower bound for the budget, and (ii) we introduce the computationally efficient ACB algorithm, whose budget matches the lower bound in most regimes. We improve on the performance of a uniform sampling strategy. Importantly, contrary to the batch setting, we establish that there is no computation-information gap in the active setting.
- Abstract（参考訳）: アクティブクラスタリング問題(ACP)について検討する。
学習者は、$N$の武器を持つ確率的バンディットと、$d$のサブガウスフィードバックと相互作用する。
同じグループ内の腕が同じ平均ベクトルを共有するように、腕をK$グループに隠した分割が存在する。
学習者のタスクは、最小の予算、すなわち観測回数の最小で、所定の定数$\delta$よりも小さなエラーの確率で、この隠れたパーティションを明らかにすることである。
本項で述べる。
一 予算の漸近的でない下限を導出し、
(II) 計算効率のよいACBアルゴリズムを導入する。
我々は一様サンプリング戦略の性能を改善した。
重要なことは、バッチ設定とは対照的に、アクティブ設定に計算情報ギャップがないことを保証する。
関連論文リスト
- Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - ProtoBandit: Efficient Prototype Selection via Multi-Armed Bandits [9.333087475006003]
ProtoBanditは、ソースデータセットから情報的データインスタンスのコンパクトなセットを特定するための、マルチアームのBanditベースのフレームワークである。
提案アルゴリズムは,数桁の類似性計算コール数(100～1000倍)を削減し,最先端手法と同等の解を求める。
論文 参考訳（メタデータ） (2022-10-04T19:03:47Z) - Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。
まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。
次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-31T13:09:39Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - Contextual Combinatorial Volatile Bandits via Gaussian Processes [10.312968200748116]
利用可能なベースアームのセットとそのコンテキストによるコンテキスト的バンディット問題を考える。
我々は,カーネル上信頼境界(O'CLOK-UCB)を用いた最適組合せ学習と最適化というアルゴリズムを提案する。
両アルゴリズムが従来のUTBベースのアルゴリズムを現実的な設定で大幅に上回っていることを実験的に示す。
論文 参考訳（メタデータ） (2021-10-05T18:02:10Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。