大規(guī)模相似性搜索：原理、技術與 Faiss 實踐

發(fā)布于 2025-1-10 12:36

瀏覽

0收藏

相似性搜索為何重要？

人工智能和機器學習的興起，催生了大量高維數(shù)據(jù)表示形式，即嵌入（embeddings），它們捕捉數(shù)據(jù)點之間的復雜關系，助力強大的分析與理解。然而，在大型數(shù)據(jù)集中查找相似嵌入是一項計算密集型任務。相似性搜索在檢索增強生成（Retrieval-Augmented Generation，RAG）領域引發(fā)了變革。RAG 將傳統(tǒng)信息檢索與語言模型相結(jié)合，通過利用相似性搜索查找相關文檔，使模型能訪問更廣泛的知識庫，生成更具信息量和上下文豐富的輸出，從而提高生成文本的準確性和相關性。

大規(guī)模相似性搜索的挑戰(zhàn)

傳統(tǒng)數(shù)據(jù)庫和搜索引擎難以滿足大規(guī)模相似性搜索的需求。它們依賴結(jié)構化查詢和索引方法，無法應對高維數(shù)據(jù)的動態(tài)特性。因此，需要專門的技術來解決這一問題。

大規(guī)模相似性搜索：原理、技術與 Faiss 實踐-AI.x社區(qū)

Faiss 框架

Faiss 由 Facebook AI Research 開發(fā)，是一個專為高效相似性搜索設計的強大庫。它提供多種索引方法，在性能、準確性和內(nèi)存使用之間進行了不同的權衡優(yōu)化。Faiss 還支持 GPU 加速，非常適合處理大規(guī)模數(shù)據(jù)集。

大規(guī)模相似性搜索：原理、技術與 Faiss 實踐-AI.x社區(qū)

基礎準備

首先安裝和導入必要的依賴項：

pip install faiss-cpu
import time
import faiss
import numpy as np

接著定義一些常量：d? 表示向量維度（128），nb? 表示基礎向量數(shù)量（10000），nq 表示查詢向量數(shù)量（100）。

d = 128
nb = 10000
nq = 100

為保證結(jié)果可復現(xiàn)，初始化隨機種子：

np.random.seed(1234)

生成兩組隨機向量，xb? 代表基礎向量（10000 x 128），xq 代表查詢向量（100 x 128）：

xb = np.random.random((nb, d)).astype('float32')
xq = np.random.random((nq, d)).astype('float32')

這些向量本質(zhì)上就是我們的數(shù)據(jù)點。

分層可導航小世界（Hierarchical Navigable Small World，HNSW）

大規(guī)模相似性搜索：原理、技術與 Faiss 實踐-AI.x社區(qū)

工作原理：HNSW 是一種基于圖的索引方法，向量被組織在小世界圖的層次結(jié)構中。圖中的每個節(jié)點（向量）都與其最近鄰節(jié)點相連。搜索時，算法在圖中導航，快速收斂到最近的向量。
優(yōu)勢：HNSW 準確性高且搜索速度快，尤其適用于高維數(shù)據(jù)集。
關鍵參數(shù)：

M（每個節(jié)點的連接數(shù)）：控制圖中每個節(jié)點連接的鄰居數(shù)量。數(shù)值越高，準確性越高，但內(nèi)存消耗也越大。

efConstruction? 和efSearch：分別控制索引構建和搜索過程中的探索深度。數(shù)值越高，搜索準確性越好，但計算量也更大。

創(chuàng)建兩個 HNSW 索引 —— HNSWFlat? 和 HNSWSQ（標量量化）來對比性能：

# HNSWFlat 是基本的 HNSW 實現(xiàn)
index_hnswflat = faiss.IndexHNSWFlat(d, 32)
start = time.time()
index_hnswflat.add(xb)
indexing_time_hnswflat = time.time() - start
start = time.time()
D, I = index_hnswflat.search(xq, 5)
search_time_hnswflat = time.time() - start

# HNSWSQ 結(jié)合了標量量化（SQ）以加快索引速度
quantizer_sq = faiss.IndexScalarQuantizer(d, faiss.ScalarQuantizer.QT_8bit)
index_hnswsq = faiss.IndexHNSWFlat(d, 32)
start = time.time()
index_hnswsq.add(xb)
indexing_time_hnswsq = time.time() - start
start = time.time()
D, I = index_hnswsq.search(xq, 5)
search_time_hnswsq = time.time() - start

兩個索引都使用“扁平”存儲方法，即不壓縮原始向量。

輸出結(jié)果：

print(f"HNSWFlat Indexing Time: {indexing_time_hnswflat:.4f} seconds")
print(f"HNSWFlat Search Time: {search_time_hnswflat:.4f} seconds")
print(f"HNSWSQ Indexing Time: {indexing_time_hnswsq:.4f} seconds")
print(f"HNSWSQ Search Time: {search_time_hnswsq:.4f} seconds")

與基于 IVF 的方法相比，HNSW 方法的索引速度明顯較慢，因為 HNSW 需要構建鄰居圖，計算成本較高。由于標量量化（SQ）在索引過程中更緊湊地表示向量，降低了向量維度，所以 HNSWSQ? 比 HNSWFlat? 稍快。HNSWFlat? 和 HNSWSQ 的搜索時間比基于 IVF 的方法略長，這是因為需要遍歷圖來找到最近鄰居。HNSW 以高精度著稱，尤其在高維空間中，但代價是索引和搜索時間較長。

倒排文件索引（Inverted File Index，IVF）

大規(guī)模相似性搜索：原理、技術與 Faiss 實踐-AI.x社區(qū)

工作原理：IVF 是大規(guī)模數(shù)據(jù)集相似性搜索中另一種常用方法。它將數(shù)據(jù)集劃分為多個桶（buckets）或“列表”，每次查詢僅搜索其中一部分桶。
優(yōu)勢：與 HNSW 相比，IVF 的主要優(yōu)勢是內(nèi)存需求較低。
關鍵參數(shù)：

nlist：聚類（或桶）的數(shù)量。數(shù)值越高，精度越高，但索引時間也會增加。

nprobe：查詢時搜索的聚類數(shù)量。增加此參數(shù)可提高召回率，但會降低搜索速度。

對比 IndexIVFFlat?（無乘積量化）和 IndexIVFPQ（有乘積量化）：

# IVFFlat 使用無量化的扁平索引
nlist = 100
quantizer = faiss.IndexFlatL2(d)
index_ivfflat = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_L2)
start = time.time()
index_ivfflat.train(xb)
index_ivfflat.add(xb)
indexing_time_ivfflat = time.time() - start
index_ivfflat.nprobe = 10
start = time.time()
D, I = index_ivfflat.search(xq, 5)
search_time_ivfflat = time.time() - start

# IVFPQ 結(jié)合乘積量化（PQ）以提高內(nèi)存效率
m = 8
nbits = 8
index_ivfpq = faiss.IndexIVFPQ(quantizer, d, nlist, m, nbits)
start = time.time()
index_ivfpq.train(xb)
index_ivfpq.add(xb)
indexing_time_ivfpq = time.time() - start
index_ivfpq.nprobe = 10
start = time.time()
D, I = index_ivfpq.search(xq, 5)
search_time_ivfpq = time.time() - start

IVF 的關鍵思想是將數(shù)據(jù)集劃分為聚類（桶），每次查詢僅搜索其中一部分桶。這里設置 nlist 為 100，即有 100 個聚類。

輸出結(jié)果：

print(f"IVFFlat Indexing Time: {indexing_time_ivfflat:.4f} seconds")
print(f"IVFFlat Search Time: {search_time_ivfflat:.4f} seconds")
print(f"IVFPQ Indexing Time: {indexing_time_ivfpq:.4f} seconds")
print(f"IVFPQ Search Time: {search_time_ivfpq:.4f} seconds")

IVFPQ? 的索引時間比 IVFFlat? 長得多，因為 IVFPQ? 在初始聚類后還涉及額外的量化步驟。它應用乘積量化（PQ），需要學習一個碼本，將每個向量壓縮為多個量化子向量。IVFPQ 的搜索時間略長，這是由于在搜索過程中需要從量化表示中解壓縮和重構向量，但差異很小，其內(nèi)存效率的提升通常值得這額外的搜索時間。

局部敏感哈希（Locality Sensitive Hashing，LSH）

大規(guī)模相似性搜索：原理、技術與 Faiss 實踐-AI.x社區(qū)

工作原理：LSH 將高維向量轉(zhuǎn)換為低維“哈希”值。相似向量更有可能具有相同的哈希值，通過關注包含相關哈希的桶來實現(xiàn)高效搜索。
優(yōu)勢：LSH 為相似性搜索提供了一種快速且可擴展的方法，尤其適用于大型數(shù)據(jù)集和高維空間。
關鍵參數(shù)：

哈希表數(shù)量：控制準確性和速度之間的權衡。哈希表越多，準確性越高，但搜索時間也會增加。

每個表的哈希函數(shù)數(shù)量：用于生成每個哈希值的哈希函數(shù)數(shù)量。

使用 IndexLSH（基于哈希的方法，利用隨機投影為每個向量創(chuàng)建哈希值）：

nbits = 16
index_lsh = faiss.IndexLSH(d, nbits)
start = time.time()
index_lsh.add(xb)
indexing_time_lsh = time.time() - start
start = time.time()
D, I = index_lsh.search(xq, 5)
search_time_lsh = time.time() - start

相似向量更有可能具有相同的哈希值，我們使用 16 位哈希。

輸出結(jié)果：

print(f"LSH Indexing Time: {indexing_time_lsh:.4f} seconds")
print(f"LSH Search Time: {search_time_lsh:.4f} seconds")

LSH 的索引速度極快，因為它只是基于隨機投影將數(shù)據(jù)點哈希到哈希桶中，無需像 IVF 或 HNSW 那樣的訓練過程，所以索引幾乎是即時的。與 IVFFlat? 和 HNSW? 相比，LSH 的搜索相對較慢，這是因為 LSH 的隨機性，可能需要搜索多個哈希桶才能找到最近鄰居。LSH 通常索引速度快，但與 HNSW 或 IVFPQ 等更復雜的方法相比，可能會犧牲準確性和搜索速度。

本文只是對大規(guī)模相似性搜索領域的簡要介紹，僅觸及了基礎知識，還有更多內(nèi)容有待探索。未來我們將深入研究實際應用，探索更高級的索引方法，甚至使用 Faiss 構建一些有趣的項目。

本文轉(zhuǎn)載自 ??柏企閱文??，作者：柏企

標簽

技術

Faiss

IVFPQ

贊

回復