Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
ざっくり理解するベクトル検索
Search
chimuichimu
April 18, 2024
3
1k
ざっくり理解するベクトル検索
chimuichimu
April 18, 2024
Tweet
Share
More Decks by chimuichimu
See All by chimuichimu
朝 Kaggle のすすめ
chimuichimu
3
450
atmaCup#19 2nd Place Solution
chimuichimu
2
230
Wantedly Visit における相互推薦システムの活用事例
chimuichimu
1
250
データ駆動で実現する、人と企業のマッチング
chimuichimu
0
96
PydanticAI × Logfire ではじめる LLM エージェントのモニタリング
chimuichimu
3
980
ウォンテッドリーの推薦システム開発を支える評価とデプロイの仕組み
chimuichimu
1
700
進化計算ライブラリ DEAP の紹介
chimuichimu
2
140
Spotify Web API を使った分析で新しいお気に入りアーティストを発見する
chimuichimu
3
200
非競プロ勢によるUSPTOコンペ参加記
chimuichimu
2
1.6k
Featured
See All Featured
A Modern Web Designer's Workflow
chriscoyier
693
190k
Docker and Python
trallard
44
3.3k
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
233
17k
Imperfection Machines: The Place of Print at Facebook
scottboms
267
13k
Fantastic passwords and where to find them - at NoRuKo
philnash
51
3.2k
Why Our Code Smells
bkeepers
PRO
336
57k
Unsuck your backbone
ammeep
670
57k
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
8
680
Thoughts on Productivity
jonyablonski
69
4.6k
Gamification - CAS2011
davidbonilla
81
5.2k
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
656
60k
Understanding Cognitive Biases in Performance Measurement
bluesmoon
29
1.6k
Transcript
ざっくり理解する ベクトル検索 めぐろLT #14 「データ分析よろず会」 Apr. 18 2024 - Chiaki
Ichimura © 2024 Wantedly, Inc.
© 2024 Wantedly, Inc. 自己紹介 市村千晃 @chimuichimu1 • 経歴 ◦
SE, DS @SIer(2017/4 ~ 2024/2) ◦ DS @ウォンテッドリー株式会社(2024/3~) • 興味 ◦ 推薦システム ◦ データ分析コンペ
© 2024 Wantedly, Inc. ベクトル検索とは? • あるベクトルに似ているベクトルを見つけるための技術 • 「似ている」の定義 ◦
コサイン類似度 ◦ ユークリッド距離 ◦ etc.
© 2024 Wantedly, Inc. 何に使われる? • ベクトルで表現された ◦◦◦ に似た ◦◦◦
を探す ◦ ◦◦◦ … 文書、画像、音声、、、 • RAG を支える要素技術の一つ
© 2024 Wantedly, Inc. • 最近傍探索 ◦ ベクトル同士を一つ一つ比較する線形探索 ◦ 厳密な最近傍を求められるが、遅い
• 近似最近傍探索 ◦ 厳密ではなく近似的な解を高速に探索 ベクトル検索の分類
© 2024 Wantedly, Inc. • 最近傍探索 ◦ ベクトル同士を一つ一つ比較する線形探索 ◦ 厳密な最近傍を求められるが、遅い
• 近似最近傍探索 ◦ 厳密ではなく近似的な解を高速に探索 ベクトル検索の分類 どう実現している?🤔
© 2024 Wantedly, Inc. 近似最近傍探索のアルゴリズム • ツリーを使う手法 • グラフを使う手法 •
ハッシュを使う手法 ※ 上記以外にもクラスタリングやベクトルの量子化による方法など、様々な手法がある
© 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.を基に図を作成
© 2024 Wantedly, Inc. グラフを使う手法 • 概要 ◦ ノードがベクトルのグラフを作成 ◦
あるノードから出発し、クエリによ り似ている近傍がなくなるまで探索 • アルゴリズムの例 ◦ NSW, HNSW • ライブラリの例 ◦ NMSLIB, Voyager Bruch, S. (2024). Foundations of Vector Retrieval. arXiv preprint arXiv:2401.09350.を基に図を作成 クエリ 探索の開始点
© 2024 Wantedly, Inc. ハッシュを使う手法 クエリ • 概要 ◦ 似たベクトルを同じバケットに写像
するハッシュを定義し集合に適用 ◦ ハッシュの写像先のバケットを探索 • アルゴリズムの例 ◦ Locality Sensitive Hashing • ライブラリの例 ◦ Datasketch Bruch, S. (2024). Foundations of Vector Retrieval. arXiv preprint arXiv:2401.09350.を基に図を作成 ハッシュ関数 上記の例は
© 2024 Wantedly, Inc. まとめ • ベクトル検索は似たベクトルを探す技術で、RAGをはじめ様々な場 面で使われる • ベクトル検索の中でも、近似的な解を高速に求めるアプローチを近
似最近傍探索という • 近似最近傍探索の代表的なアルゴリズムとして、ツリーを使う手 法、グラフを使う手法、ハッシュを使う手法、がある
© 2024 Wantedly, Inc. もっと知りたい人へ • 近似最近傍探索の最前線 • Foundations of
Vector Retrieval