曲径通幽：向量数据库

引言

向量数据库，顾名思义，它是用来存储向量的数据库。它是一种专门用于存储和管理高维向量数据的数据库，能够高效地进行相似性检索。与传统数据库不同，它侧重于处理复杂、非结构化的数据，如文本、图像、音频等。

事实上向量数据库并不是崭新的领域，在过去，它与近似最近邻搜索（ANNS）算法被广泛应用于推荐系统上，在人脸识别、图像搜寻等领域已经存在有比较长的时间，只是近年来随着LLM的普及，向量数据库也开始走红。

向量数据库对于GPT的作用

在guangzhengli大佬在他的博客向量数据库一文中提到了GPT的缺陷：

过去几个月的时间，我们正处于人工智能的革命中，其中最耀眼的莫过于 GPT-3.5/4 的横空出世，而 GPT-3.5/4 带给我们无限震撼的同时，其天然的缺陷和诸多的限制也让开发者头痛不已，例如其输入端上下文（tokens）大小的限制困扰着很多的开发者和消费者，像 gpt-3.5-turbo 模型它的限制是 4K tokens(～3000字)，这意味着使用者最多只能输入 3000 字给 GPT 来理解和推理答案。

有人可能会疑惑，我使用的 ChatGPT 是有对话记忆功能的，既然它可以做到聊天记忆，那么它的输入端 token 有限制也没什么关系，只要我将给 ChatGPT 的文字内容拆分成多次输入，它自然就可以记住我之前的对话，从而做到解除 token 限制。

这个想法是不太正确的，GPT 作为 LLM 模型是没有记忆功能的，所谓的记忆功能只是开发者将对话记录存储在内存或者数据库中，当你发送消息给 gpt 模型时，程序会自动将最近的几次对话记录（基于对话的字数限制在 4096 tokens 内）通过 prompt 组合成最终的问题，并发送给 ChatGPT。简而言之，如果你的对话记忆超过了 4096 tokens，那么它就会忘记之前的对话，这就是目前 GPT 在需求比较复杂的任务中无法克服的缺陷。

目前，不同模型对于 token 的限制也不同，gpt-4 是 32K tokens 的限制，而目前最大的 token 限制是 Claude 模型的 100K，这意味可以输入大约 75000 字的上下文给 GPT，这也意味着 GPT 直接理解一部《哈利波特》的所有内容并回答相关问题。

但这样就能解决我们所有的问题了吗？答案是否定的，首先 Claude 给出的例子是 GPT 处理 72K tokens 上下文的响应速度是 22 秒。如果我们拥有 GB 级别或更大的文档需要进行 GPT 理解和问答，目前的算力很难带来良好体验，更关键的是目前 GPT API 的价格是按照 tokens 来收费的，所以输入的上下文越多，其价格越按昂贵。

这种情况有点类似于早期开发者面对内存只有几 MB 甚至几 KB 时期开发应用的窘境，一是‘内存’昂贵，二是‘内存’太小，所以在 GPT 模型在性能、成本、注意力机制等方面有重大革命性进展前，开发者不得不面对的绕过 GPT tokens 限制的难题。

而向量数据库正是LLM模型对于这种窘境的解决方案：

在 GPT 模型的限制下，开发者们不得不寻找其他的解决方案，而向量数据库就是其中之一。向量数据库的核心思想是将文本转换成向量，然后将向量存储在数据库中，当用户输入问题时，将问题转换成向量，然后在数据库中搜索最相似的向量和上下文，最后将文本返回给用户。

当我们有一份文档需要 GPT 处理时，例如这份文档是客服培训资料或者操作手册，我们可以先将这份文档的所有内容转化成向量（这个过程称之为 Vector Embedding），然后当用户提出相关问题时，我们将用户的搜索内容转换成向量，然后在数据库中搜索最相似的向量，匹配最相似的几个上下文，最后将上下文返回给 GPT。这样不仅可以大大减少 GPT 的计算量，从而提高响应速度，更重要的是降低成本，并绕过 GPT 的 tokens 限制。

再比如我们和 ChatGPT 之间有一份很长的对话，我们可以将所有对话以向量的方式保存起来，当我们提问给 ChatGPT 时，我们可以将问题转化为向量对过去所有的聊天记录进行语义搜索，找到与当前问题最相关的‘记忆’，一起发送给 ChatGPT，极大的提高 GPT 的输出质量。

向量嵌入

向量数据库中的 Vector Embedding（向量嵌入）是将非结构化数据（如文本、图像、音频等）转换为高维向量的过程，这些向量能够捕捉数据的语义或特征信息，从而支持高效的相似性搜索和分析。

1. 什么是向量嵌入？

• 定义：Vector Embedding 是通过机器学习模型（如神经网络）将数据对象（单词、图片、用户行为等）映射到一个连续的向量空间中的过程。每个向量是高维空间中的一个点，它们之间的几何关系（如距离、方向）反映原始数据之间的语义或特征关联。

  • 例如：单词 "猫" 和 "狗" 可能被映射到向量空间中相近的位置，而 "汽车" 的向量则相对较远。
• 核心目标：将非结构化数据转化为计算机可计算的数学形式，同时保留其语义或特征信息，以便进行高效的相似性匹配。

2. 为什么需要向量嵌入？

回到开头，因为传统数据库难以直接处理非结构化数据（如搜索相似图片或理解文本语义），通过向量嵌入，我们可以实现：

1. 语义保留：相似对象在向量空间中距离更近（如余弦相似度高）。
2. 高效计算：向量化后可通过数学运算（如内积、欧氏距离）快速比较相似性。
3. 兼容机器学习：向量是深度学习模型的天然输出形式，便于后续处理。

3. 如何生成向量嵌入？

不同数据类型使用不同的模型生成嵌入向量：

• 文本：

  • Word2Vec：将单词映射为向量（"国王 - 男人 + 女人 ≈ 女王"）。
  • BERT/Transformer：生成上下文相关的句子或段落嵌入。

• 图像：

  • CNN（如ResNet）：提取图像特征生成向量。
  • CLIP：将图像和文本映射到同一向量空间。

• 其他数据：

  • 用户行为（推荐系统）、音频（如MFCC特征）、图数据（Graph Embedding）等。

关键特性

向量数据库利用向量嵌入

向量数据库专为存储和查询高维向量优化，核心功能包括：

1. 索引结构：

   • 使用近似最近邻（ANN）算法（如HNSW、IVF-PQ）加速搜索，避免暴力计算的性能瓶颈。

2. 相似性搜索：

   • 输入一个向量，快速找到数据库中与其最相似的向量（如查找与这张图片最相似的10张图片）。

3. 混合查询：

   • 结合传统属性过滤（如价格<100）与向量相似性搜索。

从文本到向量的一个例子

假设用 Word2Vec 生成词向量：

• 单词 "猫" → [0.25, -0.1, 0.7, ...]（300维）
• 单词 "狗" → [0.27, -0.12, 0.68, ...]
• 单词 "汽车" → [-0.3, 0.9, 0.15, ...]

计算余弦相似度：

• sim(猫, 狗) ≈ 0.92（高相似度）
• sim(猫, 汽车) ≈ 0.15（低相似度）

在向量数据库中搜索“猫”的最近邻时，“狗”会被优先返回。

最近邻搜索

最近邻检索（Nearest Neighbor Search）就是根据数据的相似性，从数据库中寻找与目标数据最相似的项目。更精确地，对于一个包含 $N$ 个元素的集合 $\mathcal{X} = \left\{\mathbf{x}_1, \mathbf{x}_2, \cdots, \mathbf{x}_n\right\}$，给定查询项$\mathbf{q}$的最近邻 $NN \left(\mathbf{q}\right) = \arg\min_{\mathbf{x} \in \mathcal{X}} dist \left(\mathbf{q}, \mathbf{x}\right)$，其中$dist \left(\mathbf{q}, \mathbf{x}\right)$为$\mathbf{q}$和$\mathbf{x}$之间的距离。

这种相似性通常会被量化到空间上数据之间的距离，可以认为数据在空间中的距离越近，则数据之间的相似性越高。

当需要查找离目标数据最近的前k个数据项时，此时我们称其为k-NN（K-Nearest Neighbor）检索。

由于维数灾难或者叫作维度诅咒，我们通常难以在高维欧几里得空间中以较小的代价找到精确的最近邻。
而且一般地，使用单次朴素算法最近邻搜索的复杂度为O $\left(DN\right)$，即线性复杂度，因为待搜索集合大小为 $N$，需要遍历每个元素计算距离，所以复杂度是O $\left(N\right)$，每个元素维度为 $D$，单次计算距离复杂度为 O $\left(D\right)$，总体就是O $\left(DN\right)$，因此通常来说，不能满足对于大规模数据检索的时间性能要求。

而近似最近邻搜索（Approximate Nearest Neighbor Search）则是一种通过牺牲精度来换取时间和空间的方式从大量样本中获取最近邻的方法。

近似最近邻检索

原理

近似最近邻检索利用数据量增大后数据之间会形成簇状聚集分布的特性，通过对数据分析聚类的方法对数据库中的数据进行分类或编码，对于目标数据根据其数据特征预测其所属的数据类别，返回类别中的部分或全部作为检索结果。

核心思想

搜索可能是近邻的数据项而不再只局限于返回最可能的项目，在牺牲可接受范围内的精度的情况下提高检索效率。

总的来说，这里有两种算法思想：基于哈希的算法和矢量量化算法

基于哈希的算法

这里着重介绍局部敏感哈希（Local Sensitive Hash），即LSH方法。

核心思想

在高维空间相邻的数据经过哈希函数的映射投影转化到低维空间后，他们落入同一个哈希桶的概率很大而不相邻的数据映射到同一个哈希桶的概率则很小。在检索时将欧氏空间的距离计算转化到汉明（Hamming）空间，并将全局检索转化为对映射到同一个桶中的数据进行检索，从而提高了检索速度。

局部敏感哈希采用的是与数据无关的哈希函数，也就是说，在整个学习处理过程中不会依赖任何的数据内容信息。因为局部敏感哈希通过一个局部敏感哈希函数把相似的数据点以更高的概率映射到相同的哈希编码上去。这样我们在进行查询时就可以先找到查询样本落入那个哈希桶，然后再在这个哈希桶内进行遍历比较就可以找到最近邻了。

SimHash（汉明距离）

SimHash 作为局部敏感哈希算法的一种其主要思想是将高维特征映射到低维特征，再通过两个向量的汉明距离来确定是否存在重复或相似。

算法流程如下：

在生成 SimHash 值之后，我们可以通过比较不同文档之间的汉明距离来评估其相似性。为了提升在海量数据环境中去除重复内容的效率，以 64 位指纹为例，可以将其划分为 4 个 16 位的数据块。依据鸽巢原理，若两篇文档的汉明距离为 3，则它们至少有一个数据块是完全相同的。通过将这 4 个数据块利用 KV 数据库和倒排索引进行存储，其中 Key 为 16 位的截断指纹，Value 为对应的剩余指纹集合，从而显著提高查询效率。此外，还可以选择 16 位、8 位和 4 位进行索引，一般来说，索引的位数越小，匹配的精度越高，但相应的存储空间需求也会增加。

p-stable 分布（欧氏距离）

当一个在 $\Re$ 上的分布 $\mathcal{D}$ 为 $p\text{-stable}$ 时，存在 $p \geq 0$ 使得对于任意 $n$ 个实数 $v_1, \cdots, v_n$ 和独立同分布 $\mathcal{D}$ 下的变量 $X_1, \cdots, X_n$ ，有随机变量 $\sum_{i}{v_i X_i}$ 和 $\left(\sum_{i}{\left|v_i\right|^p}\right)^{1/p} X$ 具有相同的分布，其中 $X$ 为分布 $\mathcal{D}$ 下的随机变量。

常见的 p-stable 分布有：

1. 柯西分布：密度函数为 $c \left(x\right) = \dfrac{1}{\pi} \dfrac{1}{1 + x^2}$ ，为 $1\text{-stable}$。
2. 正态分布：密度函数为 $g \left(x\right) = \dfrac{1}{\sqrt{2 \pi}} e^{-x^2 / 2}$ ，为 $2\text{-stable}$。

p-stable 分布主要可以用于估计$\left\|v\right\|_p$，对于两个相似的$v_1, v_2$，它们应该具有更小的$\left\|v_1 - v_2\right\|_p$，也就是对应的哈希值有更大的概率发生碰撞。对于$v_1, v_2$，距离的映射$a \cdot v_1 - a \cdot v_2$和$\left\|v_1 - v_2\right\|_p \cdot X$具有相同的分布。$a \cdot v$将向量$v$映射到实数集，如果将实轴以宽度$w$进行等分，$a \cdot v$落在哪个区间中就将其编号赋予它，这样构造的哈希函数具有局部保持特性。构造的哈希函数族的形式为：
$$h_{a, b} \left(v\right) = \left\lfloor \dfrac{a \cdot v + b}{w} \right\rfloor$$

其中，向量$a$的元素 $a_i \sim N \left(0, 1\right)$，$b \sim U \left(0, w\right)$。令 $c = \left\|u - v \right\|_p$，则两个向量在被分配到一个桶中的概率为：
$$Pr \left[h_{a, b} \left(u\right) = h_{a, b} \left(v\right)\right] = \int_{0}^{w} \dfrac{1}{c} \cdot f_p \left(\dfrac{t}{u}\right) \left(1 - \dfrac{t}{w}\right) dt$$

局部敏感哈希可以在次线性时间内完成搜索，但缺点在于需要比较长的比特哈希码和比较多的哈希表才能达到预期的性能。

矢量量化算法

矢量量化（Vector Quantization）是信息论中一种用于数据压缩的方法，其目的是减少表示空间的维度，其代表是乘积量化（Product Quantization）。

核心思想

它的主要思想是将特征向量进行正交分解，在分解后的低维正交子空间上进行量化，由于低维空间可以采用较小的码本进行编码，因此可以降低数据存储空间。

乘积量化有两种计算距离的方式：对称距离和非对称距离。

对于$x$和$y$的距离$d \left(x, y\right)$，对称距离利用$d \left(q \left(x\right), q \left(y\right)\right)$进行估计，非对称距离利用$d \left(x, q \left(y\right)\right)$进行估计。对称距离和非对称距离在不同阶段的时间复杂度如下表所示：

其中，$k^*$为 centroids 个数，$D$为向量维度，$n$为样本个数，$m$为分割个数。通常情况下我们采用非对称距离，其更接近真实距离。

PQ方法采用基于查找表的非对称距离计算（Asymmetric Distance Computation）快速求取特征向量之间的距离，在压缩比相同的情况下，与采用汉明距离的二值编码方法，采用ADC的PQ方法的检索精度更高。

然而，PQ方法假设各子空间的数据分布相互独立，当子空间数据的相互依赖较强时检索精度下降严重。

针对这点就有通过旋转矩阵来调整数据空间的OPQ（Optimized Product Quantization）算法。Optimized Product Quantization 是乘积量化的一个优化方法。通常用于检索的原始特征维度较高，实践中利用乘积量化之前会对高维特征利用 PCA 等方法进行降维处理。这样在降低维度的时候还能够使得对向量进行子段切分的时候各个维度不相关。

如下列矩阵表达，原本按照1234维排列的数据空间通过与正交矩阵R相乘，其维度排列变成了3214，那么我们就可以寻找一个合适的正交矩阵重新排列向量的维度，使得其划分的各子空间之间的依赖性达到最小。

$$ \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \otimes \begin{pmatrix} a^1 & b^1 & c^1 & d^1 \\ a^2 & b^2 & c^2 & d^2 \\ a^3 & b^3 & c^3 & d^3 \\ a^4 & b^4 & c^4 & d^4 \end{pmatrix} = \begin{pmatrix} a^3 & b^3 & c^3 & d^3 \\ a^2 & b^2 & c^2 & d^2 \\ a^1 & b^1 & c^1 & d^1 \\ a^4 & b^4 & c^4 & d^4 \end{pmatrix} $$

计算相似性的方法

欧几里德距离

欧几里得距离是指两个向量之间的距离，欧几里得距离算法的优点是可以反映向量的绝对距离，特别是针对那些需要考虑包含向量长度的相似性计算，计算公式如下：
$$d(\mathbf{A},\mathbf{B})=\sqrt{\sum_{i=1}^n(A_i-B_i)^2}$$

余弦相似度

余弦相似度是指两个向量之间的夹角余弦值，余弦相似度的计算不会关注向量模长，它只关注向量的方向，适用于高维向量的相似性计算，计算公式如下：
$$\cos(\theta)=\frac{\mathbf{A}\cdot\mathbf{B}}{|\mathbf{A}||\mathbf{B}|}$$

点积相似度

向量的点积相似度是指两个向量之间的点积值，点积相似度算法的优点在于它计算方法较为简单，计算速度也很快，同时考虑到了向量的模长和方向，但点积相似度算法会受到向量的长度的影响，在计算高维向量的相似性时可能会受其影响，其计算公式为：
$$\mathbf{A}\cdot\mathbf{B}=\sum_{i=1}^nA_iB_i$$

向量数据库种类