💘无处不在的匹配检索
人脸识别、语音识别、智能客服等人工智能应用在我们日常生活中无处不在。
无论是语音、文字还是图像，一种较为通用的做法是，将其转化为低维度的向量，和已有知识库进行检索匹配，返回识别结果。
例如1家拥有10,000名员工的公司，为了方便员工进出办公场地开启了人脸验证。公司需要先采集每位员工1张近期照片，存储为员工人脸知识库（一般是特征向量的形式）。当某员工扫脸后，后端的AI模型会将图片实时编码为向量，从知识库中检索出最接近的照片。如果二者相似度大于某个阈值，证明是本公司员工，开门大吉。
之前我曾经介绍过几种KNN的高效实现方法，结合有效的特征编码器这些方法完全可以在实际中应用。本文将重点关注另一种向量检索方法——乘积量化，运用了非常巧妙的数据压缩思想。
💘暴力搜索不香吗？
提起向量检索，最直观的方式就是逐一比对的暴力搜索法。但是线性时/空复杂度严重限制了它在实际中的用武之地。
当视频/文本数据规模n达到千万/上亿级别，假设特征维度是D，将会带来灾难性的O(n*D)计算复杂度。所以有了ANN、HNSW、乘积量化等向量检索优化方法。
其中ANN、HNSW代表的KNN算法主要从时间复杂度出发，通过高效的数据存储结构降低搜索时间。乘积量化主要从空间复杂度出发，通过压缩量化显著降低向量大小，进而提升搜索效率。
💘什么是乘积量化？
下面从实例出发，通俗易懂地带大家了解乘积量化方法。乘积量化一般包含两个步骤：首先是向量压缩，其次对压缩后的向量做近邻搜索。
向量压缩
假设有5W张图片，通过CNN/Transformer等网络提取特征后，每张图片包含1024维度的特征向量。那么整体数据集可以由 的向量来表示。
接着，我们将1024维度的向量均分成 组子向量，每组子向量 维：
对于每一组子向量，都包含了50K个样本，使用KMeans方法聚成 类。即每一个子向量都有256个中心点：
有了中心点，我们可以用中心点的ID来表示各组子向量中的每一个向量。中心点ID只需要8比特位来保存（ ），所以原始由32位浮点数精度组成的1024维向量，可以转化为8个8比特整数。单个向量大小从4096字节（ ）降为8字节。如下图所示：
最近邻搜索
向量压缩后，还需要完成最近邻相似搜索。一般有SDC、ADC两种搜索算法，两种方法的区别在于是否要对查询向量 做向量化。
SDC算法：先用PQ量化器将 和 映射为对应的中心点 和 ，然后用公式(1)来求解相似度：
(1)
ADC算法：只对 表示为对应的中心点 ，然后用公式(2)求解：
(2)
其中， 表示向量的第 组子向量。
💘乘积量化食用方法
笔者帮大家调研了一下，使用乘积量化的方式非常简单。一种是通过Facebook开源的相似检索工具包Faiss直接调用，不仅实现了常规PQ，还提供加入倒排索引的量化搜索“IndexIVFPQ”进一步加快搜索效率，关于Faiss可以戳笔者的这篇文章了解。
另一种方式，是调用nanopq库[2]。nanopq是原生的、为实现乘积量化极其优化版本而开发的Python工具包，没有借助任何第三方依赖，感兴趣的读者可以阅读源码从coding角度进一步认识PQ算法。调用的方式也非常简洁。
避免了重复造轮子的工作，学习新的算法想必会更加得心应手，快来一起试试吧！
