逐次モンテカルロによるスケーラブルなモデルベースクラスタリング

Abstract

オンラインクラスタリング問題では、クラスタ割り当ての候補に関して観測されるまでは解決できない不確実性がしばしば大量に存在します。この難しさは、テキストデータのようにクラスタが複雑な分布に従う場合にはさらに増幅されます。逐次モンテカルロ（SMC）手法は、この不確実性を時間とともに表現し更新する自然な方法を与えますが、大規模問題に対しては記憶容量の要求が過大で実行が困難です。本研究では、クラスタリング問題を概ね独立した部分問題へ分解する新しいSMCアルゴリズムを提案し、アルゴリズム状態のよりコンパクトな表現を可能にします。提案手法は、知識ベース構築問題の知見に動機づけられており、従来のSMCが苦手とする他の設定を含むこの状況において、我々の方法がクラスタリング問題を正確かつ効率的に解くことができることを示します。