[TU-C-1] 高次元空間の最近傍探索 (Approximate Nearest Neighbor Search in High-dimensional Space)

[TU-C-1] 高次元空間の最近傍探索 (Approximate Nearest Neighbor Search in High-dimensional Space)

Kejing Lu (名古屋大学)

対象：大学院1年レベル

ビッグデータの時代では多くのアプリケーションで大規模なデータセットを扱う必要があるが，その際に必ず直面する問題が最近傍探索問題（NNS）である．この問題は非常に基本的であり，データマイニング，画像検索，推薦システムなど，ほとんど全てのアプリケーションに現れる．特に近年，人工知能・機械学習の分野で注目されている「ベクトル検索」もNNSに深く関連する．この問題を解くことは，特に高次元空間においては非常に困難である．そのため，近似最近傍探索問題（ANNS）が注目されている．このチュートリアルでは，ANNS問題の包括的な紹介を行う．チュートリアルは以下の3つの部分からなる．

第1部では，ANNSの背景と，高次元空間におけるその難しさについて述べる．この問題の目的は極めて理解しやすいが，以下の2つの理由により，この問題を実際に解くことは容易ではない．(1)大規模なデータセットに対する線形スキャン（総当り）は、その複雑さゆえに常に受け入れがたい． (2) 次元の呪いと呼ばれる現象が存在する．実際のところ，高次元空間では，低次元空間ではうまく機能していた木構造が，線形スキャンに劣る可能性がある．すなわち，高次元でこの難問を解くには，本質的に異なるアイデアが必要になる．

第2部では，高次元ユークリッド空間において有効な3種類のANNS手法である，木構造，Locality Sensitive Hashing (LSH)，類似性グラフについて紹介する．これらは一般に，高次元空間では線形スキャンよりもはるかに良く機能する．これらの基本的な考え方を紹介した後，これらに関連するANNS手法について紹介する．

第3部では，ANNSの今後の動向について紹介する．例えば，一般的にグラフベース検索が最も有効であることは知られているが，その問合せ品質の理論的保証など，その動作メカニズムについてはまだほとんど分かっていない．グラフベースの検索をより理論的に説明できる研究者や，グラフベースの性能を継続的に向上させる産業界の研究者が必要である．将来アカデミアに進む者も，また，企業に就職する者も，このテーマには面白い仕事が見つかるかもしれない．学生や若手研究者がANNSのコミュニティに参加する動機付けになれば幸いである．