向量数据库FAISS之四：向量检索和 FAISS

ops/2024/11/26 12:51:38/

来自 YouTube

1.相似度搜索的传统方法(Jaccard, w-shingling, Levenshtein)

1.Jaccard 距离

  1. 公式

    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. 使用场景

    • 文本比较：计算两个文档中词汇的相似度。
    • 聚类：用于计算文档、图像等对象的相似性。

2.w-shingling

  1. 定义

    w-shingling是一种将文本划分为重叠子字符串（或n-grams）的方法，w 代表子字符串的长度。

    例如，对于字符串 “abcde” 和 w = 3 ，可以得到 shingle 集合 {abc, bcd, cde}。

  2. 使用场景

    • 通常结合 Jaccard 相似度衡量不同的文本相似性
    • 文本相似度：通过生成w-shingles，然后计算Jaccard相似度来判断文本的相似度。
    • 近似重复文档检测。

3.Levenshtein 距离(编辑距离)

  1. 定义

    Levenshtein距离计算两个字符串之间通过插入、删除或替换操作变成相同字符串所需的最小操作次数。

  2. 使用场景

    • 拼写检查：判断两个字符串（单词）之间的编辑距离。
    • DNA序列比对：分析生物序列的相似性。

2.基于向量的相似度搜索(TF-IDF, BM25, SBERT)

在这里插入图片描述

1.TF-IDF

  1. 公式

    • 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)

  2. 解决的问题

    • 衡量某个词在单个文档中的重要性，常用于文本检索和关键词提取
    • 通过IDF，减少在大多数文档中普遍出现的词（如“the”，“and”）的权重。

  3. 不足

    • 没有考虑词的位置、词序关系以及文档长度的影响
    • 对于长文档，TF-IDF会产生偏差，因为词频可能更高，但未必意味着其重要性更大。(比如有一篇文章专门讨论狗，狗出现的很多，但是未必重要)
    • 只能衡量词和文档的静态相关性，无法考虑用户查询的动态需求。

2.BM25

  1. 公式

    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 。

  2. 解决的问题

    • 在TF-IDF 的基础上，BM25 加入了文档长度归一化的机制，避免了长文档在词频上的不公平优势。
    • BM25 是一种平衡频率和文档长度的动态模型，适用于实际的文档检索。

  3. 不足

    尽管在信息检索中表现优越，但对于词序、词义关系等更复杂的语义问题处理能力有限。

3.SBERT

  1. SBERT（Sentence-BERT） 是基于 BERT 模型的一种变体，专门用于生成句子的向量表示，以便更好地进行句子间的相似度计算和语义搜索

  2. 原理

    SBERT的主要目标是通过预训练的 BERT 模型，结合句子对比学习策略，生成高质量的句子嵌入（sentence embeddings），并在向量空间中表示这些句子的语义。

    与原始 BERT 只能处理单个句子的方式不同，SBERT 能高效计算句子相似度。

  3. 步骤

    1. 句子嵌入生成：通过双塔结构（Siamese Network），输入的句子对分别通过共享权重的BERT编码器生成句子的嵌入向量。
    2. 相似度计算：SBERT 使用余弦相似度、欧几里得距离等来衡量句子嵌入之间的相似性。
    3. 训练方式：SBERT 使用对比损失（Contrastive Loss）、**三元组损失（Triplet Loss）**或者基于自然语言推理（NLI）的数据集训练，以优化嵌入质量。

    双塔结构
    是一种神经网络结构，通常用于计算两个输入之间的相似性。它的核心思想是通过共享权重的两个子网络分别对两个输入进行编码，然后比较它们的输出向量来评估相似性。

    工作原理

    1. 输入 → 两个文本或图像等

    2. 共享权重编码器

      两个子网络(塔)是共享参数的，即 他们使用完全相同的网络权重。

      对于输入 A 和 B，得到向量表示 E A E_A EA​ 和 E B E_B EB​

    3. 相似度计算

      对 E A E_A EA​ 和 E B E_B EB​ 计算相似性，可以用余弦相似度、欧几里得距离、曼哈顿距离等度量方式来衡量两个输入在向量空间中的接近程度。

    4. 损失函数

      训练时，使用 对比损失（Contrastive Loss）或 三元组损失（Triplet Loss）来让相似输入的嵌入向量更接近，不相似输入的嵌入向量远离。

    5. 共享权重的优势

      通过共享参数，双塔结构保证了两个输入被同样处理，这避免了输入之间的不对称处理问题。

  4. 解决的问题

    • 句子相似度计算：BERT 只能处理句子对的相似度，而 SBERT 可以通过向量计算高效地处理大量句子的相似度问题，极大加速了计算过程。
    • 语义搜索：SBERT 可以将文本数据转化为语义向量，通过快速的余弦相似度计算，实现语义层面的搜索。
    • 嵌入聚类：通过生成高质量的句子向量，SBERT 可以用于句子的聚类分析。

  5. 不足

    • 计算开销：SBERT 在生成句子嵌入时仍然依赖于BERT模型，计算成本相对较高，尤其在处理长文本时。
    • 上下文依赖性不足：SBERT 生成的句子嵌入是固定的，缺乏对上下文动态变化的建模能力。
    • 无法处理词序关系：SBERT 主要关注句子级别的语义嵌入，对于词序或细粒度的信息捕捉能力有限。

  6. 代码

    在这里插入图片描述

faiss_140">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])     
'''

在这里插入图片描述

不同探针和质心下的召回率和搜索时间

在这里插入图片描述

不同质心下的索引大小


http://www.ppmy.cn/ops/136082.html

相关文章

如何在分布式环境中实现高可靠性分布式锁

如何在分布式环境中实现高可靠性分布式锁

目录 一、简单了解分布式锁 （一）分布式锁：应对分布式环境的同步挑战 （二）分布式锁的实现方式 （三）分布式锁的使用场景 （四）分布式锁需满足的特点 二、Redis 实现分…
阅读更多...
第十章作业

第十章作业

作业1 <!DOCTYPE html> <html lang"zh-CN"> <head> <meta charset"UTF-8"> <meta charset"UTF-8"> <title>数字时钟</title> <style> body { display: flex; flex-direction: colu…
阅读更多...
微信小程序登录注册页面设计（小程序项目）

微信小程序登录注册页面设计（小程序项目）

需求 在微信小程序设计并实现登录页面&#xff0c;并填写相关登录注册函数 实现效果 代码实现 html代码 <view class"top" style"border-bottom-style: none;background-color:#FF8C69;"><!-- <view class"back" bind:tap"…
阅读更多...
【Python TensorFlow】进阶指南（续篇三）

【Python TensorFlow】进阶指南（续篇三）

在前几篇文章中&#xff0c;我们探讨了TensorFlow的高级功能&#xff0c;包括模型优化、分布式训练、模型解释等多个方面。本文将进一步深入探讨一些更具体和实用的主题&#xff0c;如模型持续优化的具体方法、异步训练的实际应用、在线学习的实现细节、模型服务化的最佳实践、…
阅读更多...
transformer.js（三）：底层架构及性能优化指南

transformer.js（三）：底层架构及性能优化指南

Transformer.js 是一个轻量级、功能强大的 JavaScript 库&#xff0c;专注于在浏览器中运行 Transformer 模型&#xff0c;为前端开发者提供了高效实现自然语言处理&#xff08;NLP&#xff09;任务的能力。本文将详细解析 Transformer.js 的底层架构&#xff0c;并提供实用的性…
阅读更多...
NUXT3学习日记四（路由中间件、导航守卫）

NUXT3学习日记四（路由中间件、导航守卫）

前言 在 Nuxt 3 中&#xff0c;中间件&#xff08;Middleware&#xff09;是用于在页面渲染之前或导航发生之前执行的函数。它们允许你在路由切换时执行逻辑&#xff0c;像是身份验证、重定向、权限控制、数据预加载等任务。中间件可以被全局使用&#xff0c;也可以只在特定页…
阅读更多...
Spring Boot图书馆管理系统：疫情中的技术实现

Spring Boot图书馆管理系统：疫情中的技术实现

摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了疫情下图书馆管理系统的开发全过程。通过分析疫情下图书馆管理系统管理的不足&#xff0c;创建了一个计算机管理疫情下图书馆管理系统的方案。文章介绍了疫情下图…
阅读更多...
redis-击穿、穿透、雪崩

redis-击穿、穿透、雪崩

击穿、穿透、雪崩经常听人说吧&#xff1f; 那他到底是啥呢&#xff1f;无非就是在有缓存层的情况下&#xff0c;对各种绕过缓存层从而直接落到了DB上的情况进行的分类。 概念性的东西大概如下&#xff0c;我是记不住&#xff0c;后期具体使用与规避这些问题才是大事&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023