[2Win5] Poster session 2

[2Win5-11] Bandit Online Clustering using Tracking Algorithm

〇Soshi Takikawa¹, Koji Tabata¹, Tamiki Komatsuzaki¹ (1.Hokkaido University)

Keywords:multi-armed bandit problem, clustering

バンディットフィードバック下でのクラスタリングは、未知のクラスタ構造を持つ複数のarmからノイズを含む報酬データを逐次受け取り、できるだけ少ない試行回数で各armの期待報酬ベクトルが既知のときと同じグループ分けを正確に行うことを目的とする。応用例として、マーケティングにおける顧客層のグループ化やウイルスの変異株の分類などが挙げられる。従来の研究では、クラスタ数が既知であり、同一クラスタ内の期待報酬ベクトルが均一という制約があった。そこで本研究では、固定信頼度設定の多腕バンディット問題の枠組みで、より緩和された条件でのクラスタリング問題を考える。具体的には、標本複雑度の下界から各armを選ぶ最適な割合を導出し、その確率に従ってarmを選択するC-tracking, D-trackingアルゴリズムを提案手法に適用する。これにより、どのクラスタに属するか判断しづらいarmを適切な割合で選択し、効率的なクラスタリングを可能とする。本発表では、停止時間の観点からその有効性を示す。