ざっくり理解するベクトル検索

Transcript

1. ざっくり理解する ベクトル検索 めぐろLT #14 「データ分析よろず会」 Apr. 18 2024 - Chiaki Ichimura © 2024 Wantedly, Inc.
2. © 2024 Wantedly, Inc. 自己紹介 市村千晃 @chimuichimu1 • 経歴 ◦ SE, DS @SIer（2017/4 ~ 2024/2） ◦ DS @ウォンテッドリー株式会社（2024/3~） • 興味 ◦ 推薦システム ◦ データ分析コンペ
3. © 2024 Wantedly, Inc. ベクトル検索とは？ • あるベクトルに似ているベクトルを見つけるための技術 • 「似ている」の定義 ◦ コサイン類似度 ◦ ユークリッド距離 ◦ etc.
4. © 2024 Wantedly, Inc. 何に使われる？ • ベクトルで表現された ◦◦◦ に似た ◦◦◦ を探す ◦ ◦◦◦ … 文書、画像、音声、、、 • RAG を支える要素技術の一つ
5. © 2024 Wantedly, Inc. • 最近傍探索 ◦ ベクトル同士を一つ一つ比較する線形探索 ◦ 厳密な最近傍を求められるが、遅い • 近似最近傍探索 ◦ 厳密ではなく近似的な解を高速に探索 ベクトル検索の分類
6. © 2024 Wantedly, Inc. • 最近傍探索 ◦ ベクトル同士を一つ一つ比較する線形探索 ◦ 厳密な最近傍を求められるが、遅い • 近似最近傍探索 ◦ 厳密ではなく近似的な解を高速に探索 ベクトル検索の分類 どう実現している？🤔
7. © 2024 Wantedly, Inc. 近似最近傍探索のアルゴリズム • ツリーを使う手法 • グラフを使う手法 • ハッシュを使う手法 ※ 上記以外にもクラスタリングやベクトルの量子化による方法など、様々な手法がある
8. © 2024 Wantedly, Inc. ツリーを使う手法 A B C D A B D • 概要 ◦ ベクトル集合を空間的に分割 ◦ 分割のルールを基に探索範囲を決定 ◦ 範囲内のベクトルを探索 • アルゴリズムの例 ◦ k-d Tree, Randomized Trees • ライブラリの例 ◦ Annoy, scikit-learn クエリ C Bruch, S. (2024). Foundations of Vector Retrieval. arXiv preprint arXiv:2401.09350.を基に図を作成
9. © 2024 Wantedly, Inc. グラフを使う手法 • 概要 ◦ ノードがベクトルのグラフを作成 ◦ あるノードから出発し、クエリによ り似ている近傍がなくなるまで探索 • アルゴリズムの例 ◦ NSW, HNSW • ライブラリの例 ◦ NMSLIB, Voyager Bruch, S. (2024). Foundations of Vector Retrieval. arXiv preprint arXiv:2401.09350.を基に図を作成 クエリ 探索の開始点
10. © 2024 Wantedly, Inc. ハッシュを使う手法 クエリ • 概要 ◦ 似たベクトルを同じバケットに写像 するハッシュを定義し集合に適用 ◦ ハッシュの写像先のバケットを探索 • アルゴリズムの例 ◦ Locality Sensitive Hashing • ライブラリの例 ◦ Datasketch Bruch, S. (2024). Foundations of Vector Retrieval. arXiv preprint arXiv:2401.09350.を基に図を作成 ハッシュ関数 上記の例は
11. © 2024 Wantedly, Inc. まとめ • ベクトル検索は似たベクトルを探す技術で、RAGをはじめ様々な場 面で使われる • ベクトル検索の中でも、近似的な解を高速に求めるアプローチを近 似最近傍探索という • 近似最近傍探索の代表的なアルゴリズムとして、ツリーを使う手 法、グラフを使う手法、ハッシュを使う手法、がある
12. © 2024 Wantedly, Inc. もっと知りたい人へ • 近似最近傍探索の最前線 • Foundations of Vector Retrieval