[2Win5] ポスターセッション2

[2Win5-11] Trackingアルゴリズムを用いたバンディットオンラインクラスタリング

〇瀧川 颯士¹、田畑 公次¹、小松崎 民樹¹ (1.北海道大学)

キーワード：多腕バンディット問題、クラスタリング

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