論文の概要: Optimal Clustering with Bandit Feedback

• arxiv url: http://arxiv.org/abs/2202.04294v1
• Date: Wed, 9 Feb 2022 06:05:05 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-10 15:40:05.716436
• Title: Optimal Clustering with Bandit Feedback
• Title（参考訳）: バンディットフィードバックを用いた最適クラスタリング
• Authors: Junwen Yang, Zixin Zhong, Vincent Y. F. Tan
• Abstract要約: 本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
• 参考スコア（独自算出の注目度）: 84.04424523097168
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: This paper considers the problem of online clustering with bandit feedback. A set of arms (or items) can be partitioned into various groups that are unknown. Within each group, the observations associated to each of the arms follow the same distribution with the same mean vector. At each time step, the agent queries or pulls an arm and obtains an independent observation from the distribution it is associated to. Subsequent pulls depend on previous ones as well as the previously obtained samples. The agent's task is to uncover the underlying partition of the arms with the least number of arm pulls and with a probability of error not exceeding a prescribed constant $\delta$. The problem proposed finds numerous applications from clustering of variants of viruses to online market segmentation. We present an instance-dependent information-theoretic lower bound on the expected sample complexity for this task, and design a computationally efficient and asymptotically optimal algorithm, namely Bandit Online Clustering (BOC). The algorithm includes a novel stopping rule for adaptive sequential testing that circumvents the need to exactly solve any NP-hard weighted clustering problem as its subroutines. We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower bound asymptotically, and significantly outperforms a non-adaptive baseline algorithm.
• Abstract（参考訳）: 本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 一組の腕(またはアイテム)は、未知の様々なグループに分割することができる。 各グループ内では、各腕に関連付けられた観測は、同じ平均ベクトルを持つ同じ分布に従う。 それぞれの時間ステップで、エージェントは腕をクエリまたはプルし、関連する分布から独立した観察を得る。 その後のプルは、前回取得したサンプルだけでなく、前回のものにも依存する。 エージェントのタスクは、最小数のアームプルと、所定の定数$\delta$を超えないエラーの確率で、腕の基本的な分割を明らかにすることである。 提案する問題は、ウイルスの変異のクラスタリングからオンライン市場セグメンテーションまで、数多くの応用を見出した。 本稿では,本課題に期待されるサンプル複雑性について,インスタンス依存情報理論下限を示し,計算効率と漸近的最適アルゴリズム,すなわちbandit online clustering (boc) を設計する。 このアルゴリズムは適応逐次テストのための新しい停止規則を含み、npハード重み付きクラスタリング問題をサブルーチンとして正確に解決する必要性を回避している。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は漸近的に下界と一致し、非適応ベースラインアルゴリズムを著しく上回ることを示す。

関連論文リスト

• Representative Arm Identification: A fixed confidence approach to identify cluster representatives [7.459521930846415]
  マルチアームバンディット(MAB)フレームワークにおける代表腕識別問題について検討する。 RAI問題は、最高の腕や、上位の$K$から$M$を識別するなど、いくつかのよく研究されたMAB問題としてカバーされている。 本稿では,信頼区間の概念に基づく2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-26T11:47:52Z)
• An SDP-based Branch-and-Cut Algorithm for Biclustering [0.0]
  本稿では,二クラスタリング問題に対する分枝切断アルゴリズムを提案する。 提案アルゴリズムは汎用的な解法よりも20倍大きな解法を解くことができることを示す。
  論文  参考訳（メタデータ） (2024-03-17T21:43:19Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。 本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Certifying clusters from sum-of-norms clustering [13.747619681451875]
  本稿では,近似解から正しいクラスタ割り当てを同定し,証明するクラスタリングテストを提案する。 提案手法では, クラスタ割り当てが, 十分に多くの繰り返しを経て, 原始二重経路追従アルゴリズムによって保証されることが保証されていることを示す。
  論文  参考訳（メタデータ） (2020-06-19T20:26:26Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)

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

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