ベクトル検索

意味の近さで検索する。 RAG の基盤。

原理#

文書と質問を同じ空間のベクトルにし、 距離が近いものを返す。

$$\text{類似度}=\cos \theta =\frac{𝐪\cdot 𝐝}{\Vert 𝐪\Vert \Vert 𝐝\Vert }$$

コサイン類似度が最もよく使われる。 ベクトルを正規化すれば内積と一致する。

キーワード検索との違い#

	キーワード (BM25)	ベクトル
一致	語の完全一致	意味の近さ
「車」で「自動車」	引っかからない	引っかかる
固有名詞、型番	強い	弱いことがある
計算コスト	軽い	埋め込みの計算が要る

両者は補完的なので、実務ではハイブリッド検索 （両方の結果を統合する）が標準になりつつある。

近似最近傍探索 (ANN)#

100 万件のベクトルと全部比較するのは重い。 厳密解を諦めて高速化する。

手法	原理
HNSW	多層のグラフを辿る。精度と速度のバランスが良い
IVF	クラスタに分けて、近いクラスタだけ探す
PQ (直積量子化)	ベクトルを圧縮してメモリを削減

HNSW は $𝒪(\log n)$ 程度で探索でき、 現在最も広く使われている。 二分探索の考え方を 高次元・近似に拡張したものと見ることもできる。

次元の呪い#

高次元では、すべての点の距離が近づいてしまう。 「最も近い点」と「平均的な点」の差が小さくなり、 最近傍探索の意味が薄れる。

埋め込みが 1000 次元でも実用になるのは、 データが実際には低次元の多様体に乗っているため。

参考文献#

• Yu. A. Malkov, D. A. Yashunin. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. IEEE TPAMI 42(4), 2020. https://doi.org/10.1109/TPAMI.2018.2889473
• Hervé Jégou, Matthijs Douze, Cordelia Schmid. Product Quantization for Nearest Neighbor Search. IEEE TPAMI 33(1), 2011. https://doi.org/10.1109/TPAMI.2010.57
• Stephen Robertson, Hugo Zaragoza. The Probabilistic Relevance Framework: BM25 and Beyond. Foundations and Trends in Information Retrieval 3(4), 2009. https://doi.org/10.1561/1500000019