向量搜索的简明数学基础

虽然 Milvus 开源向量搜索引擎（GitHub）可以为用户隔离下面这些头疼的细节，不过多学一点向量数据的知识总是没坏处的。

L2 正则化（归一化）

n 维原始向量空间： $\mathbb{R}^n, n \in \mathbb{N}$ （ $\mathbb{R}$ 为实数， $\mathbb{N}$ 为非零自然数）

原始向量： $X = (x_1, x_2, ..., x_n$ ,&space;X&space;\in&space;\mathbb{R}^n>)

向量 X 的 L2 范数（模长）： $| X | = \sqrt{\displaystyle\sum_{i=1}^n x_i ^2}$

归一化后的向量： $X' = (x_1', x_2', ..., x_n'$ ,X%27&space;\in&space;\mathbb{R}}^n>)

其中每一维的 L2 正则化算法： $x_i' = \frac{x_i}{| X |} = \frac{x_i}{\sqrt{\displaystyle\sum_{i=1}^n x_i ^2}}$

归一化后，向量模长等于 1： $| X' | = 1$

计算向量相似度

近似最近邻搜索（approximate nearest neighbor searching, ANNS）是目前针对向量搜索的主流思路。其核心理念是只在原始向量空间的子集中进行计算和搜索，从而加快整体搜索速度。

假设搜索空间（即原始向量空间的子集）： $\gamma, \gamma \subset \mathbb{R}^n$

内积（点积）

向量 A，B 的内积： $p(A,B$ &space;=&space;A&space;\cdot&space;B&space;=&space;\displaystyle\sum_{i=1}^n&space;a_i&space;\times&space;b_i>)

余弦相似度

向量 A，B 的余弦相似度： $\cos (A,B$ &space;=&space;\frac{A&space;\cdot&space;B}{|A&space;|&space;|B|}>)

通过余弦判断相似度：数值越大，相似度越高。即

$TopK(A$ &space;=&space;\underset{B&space;\in&space;\gamma}{\operatorname{argmax}}(cos(A,B))>)

假设向量 A，B 归一化后的向量分别是 A’，B’ ，则

$cos(A,B$ &space;=&space;\frac{A&space;\cdot&space;B}{|A&space;|&space;|B|}&space;=&space;\frac{&space;\displaystyle\sum{i=1}^n&space;a_i&space;\times&space;b_i}{|A|&space;|B|}&space;=&space;\displaystyle\sum{i=1}^n&space;\bigg(\frac{a_i}{|A|}&space;\times&space;\frac{b_i}{|B|}\bigg)=cos(A%27,B%27)>)

因此，归一化后，两个向量之间的余弦相似度不变。特别的，

$cos(A',B'$ &space;=&space;\displaystyle\sum_{i=1}^n&space;\bigg(\frac{a_i}{|A|}&space;\times&space;\frac{b_i}{|B|}\bigg)=p(A%27,B%27)>)

因此，归一化后，内积与余弦相似度计算公式等价。

欧氏距离

向量 A，B 的欧式距离： $d(A,B$ &space;=&space;\sqrt{\displaystyle\sum_{i=1}^n&space;(a_i-b_i)&space;^2}>)

通过欧氏距离判断相似度：欧式距离越小，相似度越高。即

$TopK(A$ &space;=&space;\underset{B&space;\in&space;\gamma}{\operatorname{argmin}}(d(A,B))>)

假设向量 A，B 经过归一化，那么进一步展开上面的公式：

$\begin{gathered} d(A,B$ &space;=&space;\sqrt{\displaystyle\sum{i=1}^n&space;(a_i-b_i)&space;^2}&space;=\sqrt{\displaystyle\sum{i=1}^n&space;(ai^2-2a_i&space;\times&space;b_i+b_i^2)}&space;=\sqrt{\displaystyle\sum{i=1}^n&space;ai^2+\displaystyle\sum{i=1}^n&space;bi^2-2\displaystyle\sum{i=1}^n&space;a_i&space;\times&space;b_i}&space;=\sqrt{2-2&space;\times&space;p(A,B)}&space;&space;\therefore&space;d(A,B)^2&space;=&space;-2&space;\times&space;p(A,B)&space;+&space;2&space;\end{gathered}>)