来自 YouTube
1.相似度搜索的传统方法(Jaccard, w-shingling, Levenshtein)
1.Jaccard 距离
-
公式
Jaccard ( A , B ) = 1 − ∣ A ∩ B ∣ ∣ A ∪ B ∣ \text{Jaccard}(A, B) = 1 - \frac{|A \cap B|}{|A \cup B|} Jaccard(A,B)=1−∣A∪B∣∣A∩B∣
其中， A 和 B 是两个集合。Jaccard 距离用于衡量两个集合的相似性，值在 0 到 1 之间，0 表示完全相同，1 表示完全不同。
-
使用场景
- 文本比较：计算两个文档中词汇的相似度。
- 聚类：用于计算文档、图像等对象的相似性。
2.w-shingling
-
定义
w-shingling是一种将文本划分为重叠子字符串（或n-grams）的方法，w 代表子字符串的长度。
例如，对于字符串 “abcde” 和 w = 3 ，可以得到 shingle 集合 {abc, bcd, cde}。
-
使用场景
- 通常结合 Jaccard 相似度衡量不同的文本相似性
- 文本相似度：通过生成w-shingles，然后计算Jaccard相似度来判断文本的相似度。
- 近似重复文档检测。
3.Levenshtein 距离(编辑距离)
-
定义
Levenshtein距离计算两个字符串之间通过插入、删除或替换操作变成相同字符串所需的最小操作次数。
-
使用场景
- 拼写检查：判断两个字符串（单词）之间的编辑距离。
- DNA序列比对：分析生物序列的相似性。
2.基于向量的相似度搜索(TF-IDF, BM25, SBERT)
1.TF-IDF
-
公式
-
TF（词频）：某词 t 在文档 d 中出现的次数除以文档总词数：
TF ( t , d ) = 词 t 在文档 d 中出现的次数 文档 d 的总词数 \text{TF}(t, d) = \frac{\text{词 } t \text{ 在文档 } d \text{ 中出现的次数}}{\text{文档 } d \text{ 的总词数}} TF(t,d)=文档 d 的总词数词 t 在文档 d 中出现的次数
-
IDF（逆文档频率）：词 t 在文档集合 D 中出现的频率的倒数：
IDF ( t , D ) = log ( ∣ D ∣ ∣ { d ∈ D : t ∈ d } ∣ ) \text{IDF}(t, D) = \log \left( \frac{|D|}{|\{d \in D : t \in d\}|} \right) IDF(t,D)=log(∣{d∈D:t∈d}∣∣D∣)
-
TF-IDF
TF-IDF ( t , d , D ) = TF ( t , d ) × IDF ( t , D ) \text{TF-IDF}(t, d, D) = \text{TF}(t, d) \times \text{IDF}(t, D) TF-IDF(t,d,D)=TF(t,d)×IDF(t,D)
-
-
解决的问题
- 衡量某个词在单个文档中的重要性，常用于文本检索和关键词提取
- 通过IDF，减少在大多数文档中普遍出现的词（如“the”，“and”）的权重。
-
不足
- 没有考虑词的位置、词序关系以及文档长度的影响
- 对于长文档，TF-IDF会产生偏差，因为词频可能更高，但未必意味着其重要性更大。(比如有一篇文章专门讨论狗，狗出现的很多，但是未必重要)
- 只能衡量词和文档的静态相关性，无法考虑用户查询的动态需求。
2.BM25
-
公式
BM25 是 TF-IDF 的改进
BM25 ( t , d ) = IDF ( t ) × TF ( t , d ) ⋅ ( k 1 + 1 ) TF ( t , d ) + k 1 ⋅ ( 1 − b + b ⋅ ∣ d ∣ avgdl ) \text{BM25}(t, d) = \text{IDF}(t) \times \frac{\text{TF}(t, d) \cdot (k_1 + 1)}{\text{TF}(t, d) + k_1 \cdot \left(1 - b + b \cdot \frac{|d|}{\text{avgdl}}\right)} BM25(t,d)=IDF(t)×TF(t,d)+k1⋅(1−b+b⋅avgdl∣d∣)TF(t,d)⋅(k1+1)
- TF ( t , d ) \text{TF}(t, d) TF(t,d) 是词 t t t 在文档 d d d 中的词频。
- IDF ( t ) = log ( N − n ( t ) + 0.5 n ( t ) + 0.5 ) \text{IDF}(t) = \log \left( \frac{N - n(t) + 0.5}{n(t) + 0.5} \right) IDF(t)=log(n(t)+0.5N−n(t)+0.5) 是词 t t t 的逆文档频率，其中 N N N 是总文档数， n ( t ) n(t) n(t) 是包含词 t t t 的文档数。
- ∣ d ∣ |d| ∣d∣ 是文档 d d d 的长度， avgdl \text{avgdl} avgdl 是所有文档的平均长度。
- k 1 k_1 k1 和 b b b 是调节参数，通常 k 1 ∈ [ 1.2 , 2.0 ] k_1 \in [1.2, 2.0] k1∈[1.2,2.0] ， b ≈ 0.75 b \approx 0.75 b≈0.75 。
-
解决的问题
- 在TF-IDF 的基础上，BM25 加入了文档长度归一化的机制，避免了长文档在词频上的不公平优势。
- BM25 是一种平衡频率和文档长度的动态模型，适用于实际的文档检索。
-
不足
尽管在信息检索中表现优越，但对于词序、词义关系等更复杂的语义问题处理能力有限。
3.SBERT
-
SBERT（Sentence-BERT） 是基于 BERT 模型的一种变体，专门用于生成句子的向量表示，以便更好地进行句子间的相似度计算和语义搜索
-
原理
SBERT的主要目标是通过预训练的 BERT 模型，结合句子对比学习策略，生成高质量的句子嵌入（sentence embeddings），并在向量空间中表示这些句子的语义。
与原始 BERT 只能处理单个句子的方式不同，SBERT 能高效计算句子相似度。
-
步骤
- 句子嵌入生成：通过双塔结构（Siamese Network），输入的句子对分别通过共享权重的BERT编码器生成句子的嵌入向量。
- 相似度计算：SBERT 使用余弦相似度、欧几里得距离等来衡量句子嵌入之间的相似性。
- 训练方式：SBERT 使用对比损失（Contrastive Loss）、**三元组损失（Triplet Loss）**或者基于自然语言推理（NLI）的数据集训练，以优化嵌入质量。
双塔结构
是一种神经网络结构，通常用于计算两个输入之间的相似性。它的核心思想是通过共享权重的两个子网络分别对两个输入进行编码，然后比较它们的输出向量来评估相似性。工作原理
-
输入 → 两个文本或图像等
-
共享权重编码器
两个子网络(塔)是共享参数的，即 他们使用完全相同的网络权重。
对于输入 A 和 B，得到向量表示 E A E_A EA 和 E B E_B EB
-
相似度计算
对 E A E_A EA 和 E B E_B EB 计算相似性，可以用余弦相似度、欧几里得距离、曼哈顿距离等度量方式来衡量两个输入在向量空间中的接近程度。
-
损失函数
训练时，使用 对比损失（Contrastive Loss）或 三元组损失（Triplet Loss）来让相似输入的嵌入向量更接近，不相似输入的嵌入向量远离。
-
共享权重的优势
通过共享参数，双塔结构保证了两个输入被同样处理，这避免了输入之间的不对称处理问题。
-
解决的问题
- 句子相似度计算：BERT 只能处理句子对的相似度，而 SBERT 可以通过向量计算高效地处理大量句子的相似度问题，极大加速了计算过程。
- 语义搜索：SBERT 可以将文本数据转化为语义向量，通过快速的余弦相似度计算，实现语义层面的搜索。
- 嵌入聚类：通过生成高质量的句子向量，SBERT 可以用于句子的聚类分析。
-
不足
- 计算开销：SBERT 在生成句子嵌入时仍然依赖于BERT模型，计算成本相对较高，尤其在处理长文本时。
- 上下文依赖性不足：SBERT 生成的句子嵌入是固定的，缺乏对上下文动态变化的建模能力。
- 无法处理词序关系：SBERT 主要关注句子级别的语义嵌入，对于词序或细粒度的信息捕捉能力有限。
-
代码
3.faiss-相似度搜索介绍与如何选择索引
不同的索引在不同向量数量的查询时间对比。注意，纵轴是对数时间
-
数据集
import shutil import urllib.request as request from contextlib import closing# first we download the Sift1M dataset with closing(request.urlopen('ftp://ftp.irisa.fr/local/texmex/corpus/sift.tar.gz')) as r:with open('sift.tar.gz', 'wb') as f:shutil.copyfileobj(r, f)import tarfile# the download leaves us with a tar.gz file, we unzip it tar = tarfile.open('sift.tar.gz', "r:gz") tar.extractall()import numpy as np# now define a function to read the fvecs file format of Sift1M dataset def read_fvecs(fp):a = np.fromfile(fp, dtype='int32')d = a[0]return a.reshape(-1, d + 1)[:, 1:].copy().view('float32')# data we will search through xb = read_fvecs('./sift/sift_base.fvecs') # 1M samples # also get some query vectors to search with xq = read_fvecs('./sift/sift_query.fvecs') # take just one query (there are many in sift_learn.fvecs) xq = xq[0].reshape(1, xq.shape[1])
1.Flat Indexes
除此之外，也有 IndexFlatIP（**IP, Inner Product，**内积）
质量很高，但是速度很慢
d = 128
k = 10import faissindex = faiss.IndexFlatIP(d)
index.add(xb)%%time
D, I = index.search(xq, k)'''
CPU times: user 16.2 ms, sys: 2.14 ms, total: 18.4 ms
Wall time: 21.8 ms
'''
baseline = I[0].tolist()
2.LSH（局部敏感哈希）
与字典(尽量最小化碰撞)不同，LSH 尝试最大化碰撞。然后将搜索范围限制在一个桶内
nbits = d*4index = faiss.IndexLSH(d, nbits)
index.add(xb)%%time
D, I = index.search(xq, k)
'''
CPU times: user 3.3 ms, sys: 2.47 ms, total: 5.76 ms
Wall time: 5.37 ms
'''
np.in1d(baseline, I)
'''
array([ True, True, True, True, False, False, True, False, False,True])
'''
可以用 nbits 在速度与准确率直接找平衡
nibts 越高，召回率越高
但是，nbits 越高，速度越慢
3.HNSW
这是一个NSW图，图中两个顶点的距离为 4 跳。
以此类推，下面是 HNSW
同样需要四跳
M = 16 # 每个顶点的连接数
ef_search = 8 # 搜索的深度
ef_construction = 64 # 构建时的扩展因子，决定了在构建图时为每个点找到最近邻的搜索深度index = faiss.IndexHNSWFlat(d, M)index.hnsw.efSearch = ef_search
index.hnsw.efConstruction = ef_constructionindex.add(xb)%%time
D, I = index.search(xq, k)
'''
CPU times: user 366 μs, sys: 261 μs, total: 627 μs
Wall time: 1.27 ms
'''
np.in1d(baseline, I)
'''
array([ True, True, False, False, False, True, False, False, True,True])
'''
# 以上不太准，调整 M 和 ef_search
M = 32 # 每个顶点的连接数
ef_search = 32 # 搜索的深度
ef_construction = 64 # 构建时的扩展因子，决定了在构建图时为每个点找到最近邻的搜索深度......
%%time
D, I = index.search(xq, k)
'''
CPU times: user 345 μs, sys: 133 μs, total: 478 μs
Wall time: 375 μs
'''
np.in1d(baseline, I)
'''
array([ True, True, False, True, True, True, True, False, True,True])
''
对比不同的 M、efConstruction 和 efSearch 组合的召回率
可以发现，
- M 的大小对效果提升最明显
- 其次是 efSearch
- 最后是 efConstruction
- 总结，efConstruction 最后大一些，M在 32-64 以上就可以了，efSearch = 32 是中位数，最好和 M 一起调节
不同的 M、efSearch 对查找时间的对比
- 可以发现，efSearch = 32, M=32 就不错
4.IVF
其实这个算法就像聚类，通过调整 探针 nprobe 来权衡准确率是查找时间
nlist = 128 # 质心数量quantizer = faiss.IndexFlatIP(d)
index = faiss.IndexIVFFlat(quantizer, d, nlist)index.train(xb) # 需要训练！index.add(xb)index.nprobe = 1%%time
D, I = index.search(xq, k)
'''
CPU times: user 928 μs, sys: 305 μs, total: 1.23 ms
Wall time: 576 μs
'''
np.in1d(baseline, I)
'''
array([ True, False, False, True, True, False, False, True, False,True])
'''
# 把探针改成 2
index.nprobe = 2
%%time
D, I = index.search(xq, k)
'''
CPU times: user 2.78 ms, sys: 2.16 ms, total: 4.93 ms
Wall time: 5.13 ms
'''
np.in1d(baseline, I)
'''
array([ True, True, True, True, True, False, True, True, True,True])
'''
不同探针和质心下的召回率和搜索时间
不同质心下的索引大小
