向量数据库
向量与向量数据库
向量（vectors）也称为嵌入（embeddings），可以来自于结构化数据，也可以是对非结构化数据的抽象，例如文本、图像、语言等。一般地，利用一些模型手段，将非结构化数据转换为长度相同的向量形式，通过向量相似度比较，进而完成语义搜索或推荐，常见的任务包括推荐系统、人脸识别、文档问答、图文检索等。
一般地，向量可以分为浮点数向量（floating-point embeddings）和二值向量（binary embeddings）。浮点数向量中每个位置的值均为 FP32 浮点数。以一个 128 维的向量来说，其将至少占用 $128 * 4 = 512$ 字节存储。二值向量是指向量各个位置的值均为 0 或 1 的向量。以一个 128 维的二值向量来说，其将至少占用 $ 128 / 8 = 16 $ 字节存储。
为了方便且高效地存储和查询向量，向量数据库（vector database）应运而生。大部分向量数据库都支持在 CPU 上对稠密向量进行检索，也有一些对稀疏向量和 GPU 有额外的加速效果。
向量索引
向量索引（vector index）是为了加速向量的查询而建立的索引机制，不同的向量数据库中实现了多种向量索引机制，以应对不同的数据和任务。由于向量本身的特性，无法将传统的索引机制应用到向量检索中。在实际应用中，由于集合中向量数目多、向量维度高，将查询向量与集合中的向量进行全量的 K 近邻搜索往往是不现实的。
为了均衡查询速度和准确性，一般会使用近似近邻搜索（approximate nearest neighbor search，ANNS）。根据 ANNS 的向量索引方式，一般可以将其分为四类：
- 基于树的索引
- 基于图的索引
- 基于哈希的索引
- 基于量化的索引
向量索引的选择应该考虑多个因素：查询速度、结果质量和索引占用的存储大小，查询速度和结果质量往往不可兼得。对于向量索引来说，包括索引的建立和查询两个阶段，更快、更准确的查询方法，往往其索引的建立也更加复杂、耗时。
FLAT 索引
使用 FLAT 索引时，不对向量做任何形式的压缩和近似，直接采用暴力搜索的方式，将查询向量与集合中的向量逐一比对，返回 $k$ 近邻结果。
使用 FLAT 索引能够保证返回最精确的结果，结果质量高。但因为 FLAT 索引查询速度慢，一般只适用于十万以下的数据量，因此产生了一些近似近邻搜索的方法，实现查询速度与结果质量的平衡。
IVF 索引
Inverted File（IVF）索引的主要思想是将集合中的向量分为若干簇（clusters），将查询向量与最接近的簇中的向量进行比对，大大降低了对比范围。在 Faiss 中，其基本过程为：
- 将集合中的向量分为
nlist个簇 - 将查询向量与簇中心进行对比，得到
nprobe个簇 - 将查询向量与这些簇中的向量进行对比（暴力全量）
其中，nlist 为簇的总数，在创建索引时指定；nprobe 为查询的簇的总数，在查询时指定，增大 nprobe 可以使结果更准确（解决边界问题）。
LSH 索引
局部敏感哈希（locality sensitive hashing，LSH）索引利用哈希冲突，使用哈希函数将向量分配到桶中，以使得同一个桶中的向量具有更高的相似性。在 Faiss 中，其基本实现为：
- 将向量分为多个子向量
- 对子向量应用哈希函数（Murmurhash），将子向量映射到（二值）桶中
- 组合子向量的哈希值，得到向量的哈希签名
- 对查询向量做同样操作
- 使用 Hamming 距离等计算哈希签名距离，以获取近邻节点
LSH 索引容易受到维度爆炸（dimension curse）影响，难以用于向量维度较高的情况。
HNSW 索引
Hierarchical Navigable Small World（HNSW）索引构建具有导航能力的分层图结构，越上层的图节点越少，距离也越远。在搜索过程中，从上向下在每层的图中找到最相近的节点，作为入口进入下一层，不断重复直到最终得到结果。通过不断向图中插入节点，实现索引的建立。其建立的过程为（粗略）：
- 针对节点 $q$，获取其所在层 $l$（采样，分配到上层的概率按指数递减）
- 从入口节点所在的层 $L$ 开始，查询层中距离 $q$ 最近的节点，作为入口，进入下一层，重复直至达到 $l$ 层
- 从 $l$ 层开始，查询层中距离 $q$ 最近的若干节点，并添加双向连接，重复直至达到 $0$ 层
- 如果 $l > L$，则将 $q$ 设置为入口节点
节点的搜索过程为：
- 从顶层的入口节点开始，寻找当前层距离节点 $q$ 最近的节点
- 将上一步的节点作为入口，进入下一层
- 重复 1-2 步，直到达到 $0$ 层
- 将 $0$ 层中最近的若干节点返回
关于 HNSW 的构建和搜索，参考论文 Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs。
PQ 索引
Product quantization（PQ）索引通过压缩向量的个数，以大幅降低内存使用并加速大向量的搜索。具体而言：
- 将较长的向量分成多个子向量
- 对于各个子向量进行聚类，得到 $N$ 个中心点
- 使用这些中心点与查询向量进行对比
索引的选择
在索引使用中，一些技术是可以组合的，往往可以加速搜索或使结果更加准确，例如 PQ 和 IVF。在对样本量、精确性、速度、内存有要求的情况下，应该选择不同的索引策略，其他情况可以默认选择 HNSW。
标量索引
一些向量数据库除了支持向量存储外，一般还可以为向量增加元数据描述字段，用于对向量进行过滤。元数据字段可以是整数、浮点数、布尔、字符串等类型，这些字段也被称为标量字段。
标量索引
标量索引（scalar index）是即为标量字段上建立的索引机制，与传统数据库类似，用于加速查询。
向量检索
向量检索（vector query）与向量搜索不同，用来对标量字段进行过滤，并返回这些结果对应的向量。
混合搜索
混合搜索（hybrid search）是指在一次搜索中，同时使用向量索引和标量索引对数据进行过滤，并得到相关条目。
相似性度量
相似性度量（similarity metrics）用于度量向量之间的相似性，选择适当的度量方式，可以提升结果的准确性。
浮点向量相似度
欧氏距离
向量 $\mathbf{a} = (a_1, a_2, \dots, a_n)$ 和 $\mathbf{b} = (b_1, b_2, \dots, b_n)$ 之间的欧氏距离定义为：
\[L(\mathbf{a}, \mathbf{b}) = \sqrt {\sum_{i=1}^{n}(a_i - b_i)^2}\]欧氏距离的取值范围为 $[0, +\infty)$，值越小相似度越高。
余弦相似度
余弦相似度（cosine similarity）是向量内积（inner product）的一种特殊形式，当向量 $\mathbf{a} = (a_1, a_2, \dots, a_n)$ 和 $\mathbf{b} = (b_1, b_2, \dots, b_n)$ 均为单位向量时，内积就变成了余弦相似度，其定义为：
\[P(\mathbf{a}, \mathbf{b}) = \sum_{i = 1}^{n}(a_i * b_i)\]内积的取值范围为 $(-\infty, \infty)$，而余弦相似度的取值范围为 $[-1, 1]$，值越大相似度越高。在计算余弦相似度时，要求对向量进行标准化。
二值向量相似度
Jaccard 距离
Jaccard 相似性系数（Jaccard similarity coefficient）是用来衡量两个样本集之间的相似度，其被定义为：
\[J(A,B) = \cfrac{|A \cap B|}{|A \cup B|}\]Jaccard 距离基于 Jaccard 相似性系数，用于衡量样本集之间的不相似性：
\[J'(A, B) = 1 - J(A, B) = \cfrac{|A \cup B| - |A \cap B|}{|A \cup B|}\]对于二值向量来说，用 $M_{ij}, i, j\in{0, 1}$ 表示向量 $\mathbf{a}$、$\mathbf{b}$ 中对应位置为 $(i, j)$ 的计数，则 Jaccard 距离为：
\[\begin{split} J'(\mathbf{a}, \mathbf{b}) & = \cfrac{M_{01} + M_{10}}{M_{01} + M{10} + M_{11}} \\ &= \cfrac{\mathbf{a} \cdot \mathbf{b}}{|\mathbf{a}|^2 + |\mathbf{b}|^2 - \mathbf{a} \cdot \mathbf{b}} \end{split}\]Jaccard 距离的取值范围为 $[0, 1]$，值越小相似度越高。
Hamming 距离
Hamming 距离一般用于度量长度相同的两个字符串，对于二值向量，其距离定义为向量各个位置上不相同的值的个数。
以字符串 1101 1001 和 1001 1101 为例，从其按位异或结果 $ 11011001 \oplus 10011101 =01000100 $ 中可知 Hamming 距离为 $2$。
Hamming 距离的取值范围为 $[0, n]$，值越小相似度越高。
向量模型与产品
向量模型
开源模型：
- sentence-transformers/all-MiniLM-L6-v2：基于 BERT，在超过十亿的英文文本对上训练，适合于各种语义相似度任务，对于不同任务也有单独的模型，适合长度为 128 以下的文本，输出向量长度为 384，在长文本上效果逊于大模型
- moka-ai/m3e-base：基于 Roberta，在超过两千万的中文句对上训练，支持中英双语的同质文本相似度计算，输出向量长度为 768，中文表现超 OpenAI ada-002
- openai/clip-vit-base-patch32：OpenAI 发布的开源多模态模型（仅参数），在超过一亿的图文对上进行训练，可以生成文本、图像的嵌入向量，输出向量长度为 1024
闭源模型：
- OpenAI：使用 OpenAI 提供的闭源 API，模型为 ada-002，可以获得长度为 1536 的嵌入向量
- Google：使用 Google PaLM 提供的闭源 API，模型为 gecko-001，可以获得长度为 768 的嵌入向量
数据库产品
开源产品：
- Faiss：Facebook 开源的向量检索工具，绝对的老大哥，支持 GPU
- Milvus：国产开源向量检索工具，提供收费云服务，支持 GPU，不支持 LSH 索引
- Qdrant：开源，提供收费云服务，不支持 GPU
- Chroma：开源，简单易用，与 LangChain、OpenAI 等集成方便
闭源：
- Pinecone：闭源收费，对用户屏蔽了索引的相关细节