检索算法小结

原创

languageX

发布于 2024-07-01 19:55:18

2760

文章被收录于专栏：大语言模型大语言模型

上一篇文章介绍了大模型应用利器--RAG。在RAG中当然少不了检索。检索算法在信息检索、搜索引擎和推荐系统等领域中扮演着至关重要的角色。它们的核心任务是根据用户查询从大量数据中找出最相关的信息。本文就对检索算法进行以下小结。

常见的检索算法确实可以理解为相似度计算的过程。在信息检索系统中，检索算法的主要目标是根据查询从大量文档中找到最相关的文档。这通常涉及计算查询和文档之间的相似度，并根据相似度对文档进行排序。

常见检索算法和相似度计算方法

布尔模型：
- 简单且直观，布尔检索基于布尔逻辑，通过简单的布尔运算符（AND, OR, NOT）来判断文档是否匹配查询。它不使用相似度计算。对用户要求较高，需要构造复杂的布尔表达式。
概率检索模型：
- BM25 等模型利用文档和词项的统计信息，提供更精确的相关性评分。

\text{BM25}(d, q) = \sum_{i=1}^{n} \text{IDF}(q_i) \cdot \frac{f(q_i, d) \cdot (k_1 + 1)}{f(q_i, d) + k_1 \cdot (1 - b + b \cdot \frac{|d|}{\text{avgdl}})}

\text{IDF}(q_i) = \log \left( \frac{N - n(q_i) + 0.5}{n(q_i) + 0.5} + 1 \right)

{N}表示语料库的文档总数
{n(q_i)}是包含词语 {q_i}的文档数
{f(q_i,d)}是词语{q_i}在文档{d}中出现的频率
{|d|}是文档{d}的长度
{avgdl}是所有文档的平均长度
{k_1}和{b}是可调参数
{IDF(q_i)}是逆文档频率
向量空间模型（VSM）：
- 向量空间模型（VSM）最早的实现通常使用词频-逆文档频率（TF-IDF）来将文档和查询向量化，然后利用向量之间的相似度计算来进行信息检索。TF-IDF是一种经典的文本特征表示方法，它通过词频（TF）和逆文档频率（IDF）的乘积来衡量一个词对于文档的重要程度。
- 在现代信息检索任务中，embedding模型的向量检索与传统的向量空间模型（Vector Space Model, VSM）有着紧密的联系，Embedding模型是现代深度学习中广泛使用的一类模型，用于将高维的稀疏文本表示转换为低维的稠密向量。这些模型可以捕捉到词语和文档的语义关系，从而提高检索效果。虽然TF-IDF在早期的VSM中非常流行，并且在某些情况下仍然有效，但随着深度学习技术的发展，使用预训练的语言模型（如BERT、GPT）来生成文档和查询的向量表示已经成为一种更为流行和有效的方法。这些预训练模型可以捕捉更丰富的语义信息，从而提高了检索的效果和准确性。

milvus库中检索度量方式以及索引类型

在相似度度量( similarity metrics ) milvus 介绍两种 embeddings 形式，1. 浮点形式 embeddings 2. 二级制 embeddings 。我们以常见的浮点形式 emebeddings 作为主力介绍内容。

度量方式 ( Metric Types )：
- L2 （欧氏距离）
  - 欧氏距离是向量空间中两点之间的直线距离，也称为 L2 距离或欧几里得距离。对于两个 {n}维向量{A}和{B}，它们之间的欧氏距离计算公式如下：
  - \text{L2 Distance} = \sqrt{\sum_{i=1}^{n}(A_i - B_i)^2}
- 内积是两个向量之间的点积运算，也称为点乘或数量积（在机器学习领域 inner-product = dot-product ）。对于两个 {n}维向量{A}和{B}，它们之间的内积计算公式如下：
  - \text{Inner Product} = \sum_{i=1}^{n} A_i \times B_i
- 余弦相似度是衡量两个向量之间夹角的余弦值，常用于衡量向量之间的相似度。两个 {n}维向量{A}和{B}，它们之间的余弦相似度计算公式如下：
  - \text{Cosine Similarity} = \frac{\vec{A} \cdot \vec{B}}{\|\vec{A}\| \|\vec{B}\|}
索引类型 ( Index Types ) 针对 floating-point embeddings :
- FLAT
  - 当使用 FLAT 索引时，不进行额外的索引结构构建。这意味着每个向量都被存储在内存中的一个位置，并且搜索时需要遍历整个向量空间以找到与查询向量最接近的向量，适用于小规模数据集，可以达到 100% 的召回率。
  - FLAT 查询时间，随着同时查询数量的增加而增大。
- IVF_FLAT
  - 通过将分割成小的倒排列表，可以减小搜索的空间范围，从而加速相似度搜索。可以在一定程度上提高搜索速度，但不牺牲准确率。
  - IVFFLAT在CPU上的查询时间与 nq、nprobe 正相关，而IVFFLAT在GPU上的查询时间对 nq 和 nprobe 的变化并不敏感。这是因为IVFFLAT的索引数据较大，将索引数据从 CPU 拷贝到 GPU 所用时间占了总查询时间的大部分。由图所示，除了nq＝1000且nprobe＝32的情况，IVFFLAT在CPU上的查询效率更高。
  - 用公开数据集sift-128-euclidean（1,000,000 条128维向量）和glove-200-angular（1,183,514 条200维向量）分别建立IVFFLAT索引（nlist=16384），并测得召回率（k=10）随 nprobe 变化曲线如上图所示。
- IVF_SQ8
  - 使用量化技术，查询速度较快，有限的内存资源，可接受一定程度的召回率折中。
  - 当磁盘或内存、显存资源有限时，IVFSQ8是一个更好的选择。它通过对向量进行标量量化（Scalar Quantization），能把原始向量中每个FLOAT（4字节）转为UINT8（1字节），从而可以把磁盘及内存、显存资源的消耗量减少为原来的1/4~1/3。同样以sift-1b数据集为例，生成的IVFSQ8索引文件只有140GB。
  - 优点：查询速度快，资源占用仅为 IVFFLAT 的 1/4~1/3
  - 缺点：查询召回率比 IVFFLAT 低
  - 用公开数据集sift-1b（10亿条128维向量）建立IVFSQ8索引，并分别只用CPU或GPU做查询，在不同nprobe参数下测得的查询时间随nq变化情况如上图所示。IVFSQ8的查询性能曲线跟IVFFLAT非常相似，但索引大小的精减带来了全面的性能提升。同样，在nq和nprobe较小时，IVFSQ8在CPU上的查询性能更高。
  - 用公开数据集sift-128-euclidean（1,000,000 条128维向量）和glove-200-angular（1,183,514 条200维向量）分别建立IVFSQ8索引（nlist=16384），并测得召回率（k=10）随nprobe变化曲线如上图，IVFSQ8对原始数据的压缩并未导致明显的查询召回率下降，对应不同的nprobe，IVFSQ8的召回率（k=10）最多只比IVFFLAT低1个百分点。
- IVF_PQ
  - 基于 IVF_FLAT 的一种向量数据有损压缩算法（ PQ乘积量化），首先，PQ 先将 D 维空间切分成 M 份：类似于将 128 维空间切分成 M 个 D/M 维的子空间，每个子向量进行 k-means 聚类。
  - 使用量化技术，查询速度较快，有限的内存资源，可接受一定程度的召回率折中。
- HNSW
  - 前身是NSW，Milvus借鉴了 SkipList 的思想，提升了其整体性能，按照一定的规则把一张的图分成多张，越接近上层的图，平均度数越低，节点之间的距离越远；越接近下层的图平均度数越高，节点之间的距离也就越近
  - 基于图索引，非常快的查询速度，保证一定的召回率，但需要更大的内存空间
- SCANN
  - 基于量化技术，非常快的查询速度，保证一定的召回率，也需要更大的内存空间。
- AUTOINDEX
  - AUTOINDEX 是Zilliz Cloud 独有的索引类型，可以帮助您获取最佳搜索性能。当您在 Zilliz Cloud 上为 Collection 中的向量字段创建索引时，会自动应用 AUTOINDEX 索引。