精通推荐算法9：向量检索技术

向量检索在CV、NLP、搜索引擎、推荐系统和在线广告中应用十分广泛。利用距离计算和向量检索技术，可以为目标用户推荐与其最匹配的Top-K物品，这就是典型的u2i。还可以基于目标用户最近点击或购买过的物品，推荐与之最相似的Top-K物品，这就是典型的i2i。目前向量检索已经广泛应用在推荐系统的召回等模块中。

本文会先介绍向量距离计算方法，它是向量检索的基础。然后再介绍四种主流的向量检索技术。最后介绍工业界应用较多的几种向量检索工具。

1 向量距离计算方法

通过向量距离计算，可以衡量两个向量间相似度，从而检索出Top-K近邻。常见的距离计算方法有：

（1） 余弦相似度（Cosine Similarity）。计算两向量夹角的余弦，夹角越小，则向量距离越近。其数学表达如下所示。

需要注意的是，余弦相似度只考虑了两向量的方向，而没有考虑其大小。

（2） 杰卡尔德系数（Jaccard Coefficient）。用来衡量两个集合差异性，二者交集大小与并集大小的比值。其数学表达如下所示。

杰卡尔德系数对数据集大小敏感，且只考虑元素是否存在，而不考虑元素顺序，故可能存在一定的误判。

（3） 曼哈顿距离（Manhattan Distance）。沿着网格线，从一个点到另一个点之间的距离之和。它也被称为L1距离或城市街区距离。在二维平面上，其数学表达如下所示。

其中，（x1,y1）和 (x2,y2) 是两个点的坐标。曼哈顿距离计算简单，对于路径规划等问题有较好的可解释性。其缺点主要有，处理连续数据时可能有一定误差，且只考虑了沿坐标轴的距离，而没有考虑方向的影响。

（4） 欧几里得距离（Euclidean Distance）。N维空间中两个点之间的距离。最常见的向量距离方法，又称欧式距离或L2距离等。在二维平面上，其数学表达如下所示。

其中，（x1,y1）和 (x2,y2) 是两个点的坐标。欧几里得距离可解释性强，计算简单，可用于分类、聚类和回归等各种机器学习算法。但它对异常值和离群点非常敏感，不适用于离散型数据，且高维空间中计算复杂度特别大。

（5） 切比雪夫距离（Chebyshev Distance）。两向量在各坐标维度上的最大差值。它等于国际象棋的国王从一个方格到另一个方格的最小步数，故又称棋盘距离。在二维平面上，其数学表达如下所示。

其中，（x1,y1）和 (x2,y2) 是两个点的坐标。切比雪夫距离对异常值和离群点不敏感，可以有效处理高维数据。但它没有考虑各维度之间关系，可能导致计算不准确。且只考虑了两样本点的最大差值，可能会忽略一些重要信息。

（6） 闵可夫斯基距离（Minkowski Distance）。它是曼哈顿距离、欧式距离和切比雪夫距离的推广，又称闵式距离。在二维平面上，其数学表达如下所示。

其中，（x1,y1）和 (x2,y2) 是两个点的坐标。参数 p 可用来控制距离度量方法。当 p=1 ,闵式距离退化为曼哈顿距离。当 p=2 退化为欧式距离。当 p=∞ ,退化为切比雪夫距离。

（7） 编辑距离（Edit Distance）。将一个字符串转换为另一个字符串需要的最少编辑操作次数。一次编辑操作包括插入、删除和替换一个字符。编辑距离常用在文本相似度比对、拼写检查等领域，又称莱文斯坦距离（Levenshtein Distance）。例如将字符串“distenc”转换成“distance”,需要先将“e”替换为“a”,然后在末尾插入“e”，故其编辑距离为2。编辑距离可以利用动态规划来求解。

（8） 海明距离（Hamming Distance）。两个等长字符串之间对应位置不同字符的个数。常用在信息编码中，可以表示两个编码之间的最小距离。海明距离越大，两编码之间的差异越大。例如10010和11001，从左到右依次有第二位、第四位和第五位不同，故其海明距离为3。海明距离可以利用异或操作实现，计算速度十分快。ETA长序列建模模型，便采用了这一方法。

2 向量检索方法

推荐系统的候选物品池一般很大，可以达到千万量级。如何从海量数据中实时检索最相似的物品，一直以来都是业界一大难题。为了平衡检索精度和算力资源，一般基于近似最近邻搜索（Approximate Nearest Neighbor Search，简称ANNS），不会追求绝对最近邻。向量检索主要有哈希法、基于树的方法、向量量化法和近邻图方法等。

2.1 哈希法

哈希法（Hash）通过哈希函数（也叫散列函数），将输入数据压缩为固定大小的输出（哈希值）。对于相同的输入，始终会生成相同的输出。常见的哈希方法有MD5、SHA-256、PCA、LSH等。下面重点讲解应用极广的局部敏感哈希。

局部敏感哈希（Local Sensitive Hashing, 简称LSH）的基本思想是，高维空间中的点向低维空间投影时，其距离关系基本不变。原本距离近的两点，投影后距离依然相近。不过距离远的点投影后，有一定的几率变得相近。基于这一点，LSH对高维向量进行投影，将距离相近的向量映射到同一个桶内。检索时只需要从相邻的几个桶内查找即可，大大缩短了向量检索复杂度。

距离较远的点也有一定的概率被Hash到同一个桶内，为了提高近邻搜索准确率，可以使用多桶Hash。同时落入多个桶内的两个点，其距离相近的概率大大增加。这一方法一般称为“多表哈希”。5.8节介绍的ETA长序列建模中的SimHash，便是一种多表LSH的具体实现，如下图所示。

2.2 基于树的方法

KD树（k-dimensional tree）是一种常见的基于树的向量检索方法。它利用二叉树，对k维空间的点进行存储，以便实现快速检索。其非叶子结点可以看做一个超平面，将空间分割成左右两部分。左子树代表超平面左边的点，右子树代表超平面右边的点。

构建KD树时，需要先选择一个维度和分割点。假如维度为x轴，则所有x值小于分割点的节点都会归入左子树，x值大于分割点的则归入右子树，从而将数据集划分为两个子集。然后在子集内递归这一过程。最后完成KD树的构建。通常选择方差最大的那个维度作为分割维度，选取中位数作为分割点，从而让左右子树尽量均匀分布，减少KD树的深度。二维空间KD树构建的例子，如下图所示。

检索KD树时，从根节点开始，判断数据与分割点的大小关系，找到包含目标数据的子树。然后在子树中继续递归查找，直到找到与之最近的那个点。KD树可以快速处理大量数据，其时间复杂度为 O(logn) 。但构建过程比较耗时，数据分布不均匀时，其检索效率会降低。

2.3 向量量化法

向量量化（Vector Quantization）可实现向量降维和压缩。其核心思想是，将向量划分成若干子向量，然后利用子向量的索引来编码原始向量。其具体实现很多，有残差向量量化（Residual Vector Quantization，简称RVQ）、乘积量化（Product Quantization，简称PQ）、倒排乘积量化（Inverted Product Quantization，简称IVFPQ）和最优乘积量化（Optimal Product Quantization, 简称OPQ）等。下面重点介绍乘积量化PQ，它是IVFPQ和OPQ的基础。

PQ索引构建主要分为切分、聚类和编码三步。首先将N个原始向量，各自切分为多个子向量。比如256维向量，切分为8个32维子向量。然后在每个子向量空间内进行聚类，可以采用KMeans等聚类算法。假设每个子空间有1024个聚类，对每个聚类中心编码，得到1024个ID。最后将目标样本切分为多个子向量，并利用距离最近的聚类中心ID进行编码，将所有子向量的编码拼接起来得到最终结果。PQ索引构建过程如下图所示。

PQ乘积向量索引构建过程示例

检索阶段，首先对检索向量进行切分，计算其在每个子空间内，与每个聚类中心的距离。假如有8个子空间，每个子空间1024个聚类，则可以形成大小为8 * 1024的距离表。然后利用距离表计算检索向量与每个候选样本的距离，此时直接从距离表中查找二者在每个子空间内的距离，并累加起来即可。最后再取出Top-K最近邻候选样本。

利用IVFPQ、OPQ等乘积量化优化方法，可以进一步提升向量检索速度。乘积量化具有压缩率高、查询速度快和易于实现等优点，因此得到了广泛使用。但也存在精度有损失、计算复杂度高和需要预先训练等不足。

2.4 近邻图方法

图是一种高效的数据结构，利用图结构构建向量索引，可以提升向量检索的召回率。近几年基于近邻图的向量检索使用越来越广泛，特别是HNSW算法提出后，近邻图已经成为向量检索工具的必备算法。

HNSW于2016年被提出，它在NSW（Navigable small world）算法的基础上，加入了层级结构，从而使检索速度更快。二者是同一作者，建议先熟悉NSW算法。

构建NSW索引图时，为了减少检索跳转次数，可以规定每个节点必须和m个节点有边。构建阶段，向图中逐个插入新节点，找到与它最近的m个节点，将它们连接起来。所有节点插入完毕后，即完成了构图。那怎么寻找最近的节点呢？从已插入节点中选择任一点作为起始，计算起始点与新节点之间的距离，以及起始点的所有邻居节点与新节点距离，选取其中最近的节点作为新的起始点，直到最近的点就是起始点本身为止。然后再查找第二近和第三近的节点，直到全部m个节点找到为止。

如下图所示，设定每个节点必须有3个邻居节点。第一步向图中插入A点，由于只有一个节点，故不需要连接边。第二步插入B点，并连接BA。第三步插入C点，并连接CA和CB。第四步插入D点，由于正好有3个已有节点，故与它们连接起来，即DA、DB和DC。第五步插入E点，此时有4个已插入节点，要从中选出3个最近的，这一步是比较关键的一步。

NSW索引图构建示例

其步骤如下：

（1）从A、B、C、D四个点任选一个作为起始点，比如A点。

（2）计算A点，以及它的所有邻居节点与E点距离，即EA、EB、EC和ED。

（3）从中选择最近的点，发现EC距离最短，故选择C点作为新的起始点。

（4）重复（2）和（3）两步，发现C点和它的邻居节点相比，距离E点最近。故可认为所有已插入节点中，C点与E点最近。

（5）依此类推，得到第二近的D点和第三近的B点。

（6）连接EC、ED和EB，即完成了E点的插入。

按照相同方法，继续插入F、G、H和I等其他节点，直到所有节点插入完毕。

由于规定了每个节点的最少邻居数，故NSW可以形成一些距离较远的边，如图6-20中的红色连线所示。这些边有利于减少检索阶段的节点跳转次数，被称为“高速公路”。如上图所示，当需要检索与绿色点最近的节点时，如果选择从M点出发，借助“高速公路”，只需要三次跳转就可以找到最近的E点。否则需要跳转很多步，大大降低了检索速度。

HNSW（Hierarchical Navigable Small World Graphs）在NSW基础上，加入了分层检索能力，从而进一步提升检索速度。如下图所示，当需要检索绿色点的最近邻时，先从最上层中随机选取一个起始点，并在该层中寻找最近邻。然后以它作为下一层的起始点，并同样在该层中寻找最近邻。依此类推直到最后一层。这种先粗筛再精选的做法，跟推荐算法的“先召回再排序”异曲同工。

HNSW分层检索示意图

HNSW算法比较复杂，可以设置的参数也较多。增大最少邻居节点数，可以提升检索召回率和检索速度，但构图速度会变慢。增加分层层数，可以提升检索速度，但会导致构图速度变慢，内存消耗也变多。实际应用时，可以通过实验来逐步调整。

HNSW算法召回率很高，几乎可以与暴力搜索相比。同时检索速度很快，1亿级别数据只需要几百毫秒。但其索引构建很慢，占用内存也很高。目前已经广泛应用在推荐系统中，Faiss等大部分向量检索工具，也有其具体实现。

3 向量检索常用工具：Faiss

向量检索在推荐系统中十分重要，特别是召回模块。其准确性、召回率和检索速度要求都很高，直接关乎召回算法的成败。向量检索同时也是复杂度较高的一个技术方向，其算法和工程难度均很大。好在业界有一些优秀的向量检索工具，包括Spotify公司的Annoy、Facebook的Faiss、谷歌的ScaNN、Zilliz公司的Milvus、阿里达摩院的Proxima、蚂蚁金服的ZSearch、京东的Vearch等。下面重点介绍下Faiss向量检索库。

Faiss（Facebook AI Similarity Search）[17]是一种高效的向量检索库，可以在大规模数据中快速寻找相似向量。它支持多种距离计算方法，如欧式距离、余弦距离和曼哈顿距离等。实现了暴力检索、LSH局部敏感哈希、PQ乘积量化、IVFPQ倒排乘积量化和HNSW近邻图算法等多种向量检索方法。并提供了Python和C++接口，以及GPU加速功能。目前已经被很多公司广泛使用了。其使用十分简单，如下面例子所示。

import faiss


def search(query_embedding, doc_embeddings):
    """
    构建索引，并检索topK近邻向量
    @param query_embedding: 需要查找的向量
    @param doc_embeddings: 候选向量库
    @return: 返回与query相似的topK向量
    """
    # 1 确定要采取的向量检索算法，以及距离度量方法。
    # HNSW64：采用HNSW算法，每个节点的最大邻居数为64。邻居数越大检索越精准，但构图耗时也越大
    param = 'HNSW64'

	# measure表示距离度量方法，METRIC_L2为欧式距离。
    measure = faiss.METRIC_L2

    # 2 开始构建索引
    dimension = doc_embeddings.shape[1]
    index = faiss.index_factory(dimension, param, measure)
    index.add(doc_embeddings)

    # 3 topK检索，查找query_embedding向量的topK近邻。返回与每个邻居的距离，以及它们的id
    top_k = 500
    distances, ids = index.search(query_embedding, top_k)

    return ids

Faiss使用步骤基本大同小异，需要配置的是使用哪种检索算法，以及距离度量方法。检索算法主要有：Flat（暴力检索）、LSH（局部敏感哈希）、PQx（乘积量化，x表示向量分段数，如PQ8）、HNSWx（HNSW近邻图，x表示最大邻居节点数，如HNSW64）等。距离度量方法主要有：METRIC_INNER_PRODUCT（余弦相似度）、METRIC_L1（曼哈顿距离）、METRIC_L2（欧式距离）、METRIC_Linf（切比雪夫距离）、METRIC_Lp（闵可夫斯基距离）等。