近傍検索 （NNS: Nearest Neighbor Search）

目的

推薦システムに使用される技術である近傍検索について簡単に概要を掴む。

近傍検索とは

すべての候補アイテムの埋め込みとクエリの埋め込みの類似度（通常はない席または距離）を計算し、その中で最も近い（類似した）アイテムを見つける手法。

今回は、その中でもよく使用されるアルゴリズムである、Brute Force と ScaNN （Scalable Nearest Neighbors）についてまとめる。

Brute Force（総当たり検索）

概要

Brute Force（総当たり検索）は、すべての候補アイテムの埋め込みとクエリの埋め込みの類似度（通常は内積または距離）を計算し、その中で最も近い（類似した）アイテムを見つける方法。

メリットとデメリット

• メリット：
  • 最も単純で理解しやすい。
  • 正確性が高く、必ず最適化を見つける。
• デメリット：
  • 計算量が多いため、候補アイテムが多い場合には非常に遅くなる。

猿にでもわかる例

例えば、図書館で特定の本を探していたとする。Brute Force検索は、図書館のすべての本を1冊ずつ手にとり、それが探している本かどうかを確認するようなもの。

確実に本を見つけることができるが、図書館の蔵書が多いと非常に時間がかかる。

ScaNN (Scalable Nearest Neighbors)

概要

ScaNNは、大規模データセットに対して効率的に近傍検索を行うためのアルゴリズム。ScaNNは、データを適切に構造化し、検索空間を分割することで、検索速度を大幅に向上させる。

メリットとデメリット

• メリット：
  • 高速で、大規模データセットに対してスケーラブル
  • 計算量を削減しながら高い精度を維持
• デメリット：
  • 設定とチューニングが複雑
  • 厳密な最適解ではなく、近似解を提供することがある

猿にでもわかる例

図書館の例でいうと、ScaNNは図書館の本をジャンルや著者別に整理し、探している本がある可能性が高い棚だけ探すようなもの。これによって、探す時間が大幅に短縮されるが、稀に見逃すこともある。

ScaNNの内部構造

ScaNNは以下のようなステップを踏む：

1. データ分割： データセットを小さなクラスタに分割する。これにより、検索空間が減少する。
2. クラスタ内検索： クエリに最も近いクラスタを特定し、そのクラスタ内で検索を行う。
3. 近似解と精緻化： 近似解を早く見つけた後、それを更に精緻化して、精度の高い結果を提供する。

まとめ

• Brute Forceは正確であるが、計算コストが高い。
• ScaNNは高速でスケーラブルであるが、近似解となる場合がある。