Faiss PQ乘积量化的学习总结

好久么有写东西了，看来做一件事情，坚持真的很难。今天为什么想到写东西，是因为我刚才看到之前学过的东西又两眼摸黑了，脑子是个好东西，可惜我么有，哈哈。俗话说，好记性不如烂笔头，我今天就把他记录下来，以免我的老年痴呆复发，哈哈

首先，简单介绍下Faiss，由Facebook开发并且开源的一款针对聚类和相似性搜索的库，使用C++语言编写，并提供Python接口，内部一些算法也提供GPU实现，可做算法加速。支持十亿级别的向量搜索，是目前为止比较成熟的向量搜索库，据我所知，很多公司都是在此基础上进行二次开发与集成，来开展业务。当然，由于c++的使用局限，目前我们的使用是基于c++实现的Java封装接口，为了更好的实现业务需求。

好了，话不多说，开始干活。本文主要介绍的是Faiss中关于乘积量化的内容，包括示例（其他内容可以参考网络大神的分享），以便能清楚的理解具体的量化是如何实现的。目前业界关于相似近邻搜索算法 ANNS（Approximate Nearest Neighbor Search）主要有四类。包括基于树的算法（KD-tree，R* tree等），基于hash的算法（LSH），基于量化的算法（PQ），基于图的算法（FANNG，HNSW，NSG）。目前我在看的是NSG算法，头大……

下图想必大家都有看到过，但是是不是正真理解它的意思就不见得了，像我一样，看了忘，忘了看，哈哈。

PQ乘积量化的核心思想还是基于聚类，PQ乘积量化生成码本和量化的过程如下图：

首先，我们要进行大量的训练，针对N个训练样本，假设每个样本的维度是128维，我们需要将其切分为4个子空间，那么每个子空间的维度就是128/4=32维，假设我们的类中心分为256个，那么每一个子空间经过K-means聚类，都能得到一个码本，具体是什么意思呢？我来解释下，每一个子空间32维，那么N条样本数据，就是每个子空间就是N*32维数据，N条数据对应到256个类中，每条数据肯定能得到对应的类中心id（每条数据都会有一个聚类结果），之后，每一个子空间的单条32维数据都会对应一个类中心也就是码本，比如第一条数据的第一段子空间的32维数据，经过聚类之后，得到的类中心就是上图中右边图的第一个数字124（注意，这个数字指的是第一个子段的32维数据在256个类中的第124个类上，是一个类的编号），那么第一条128维数据对应的码本就是（124,56,132,222），具体对应的类中心也就是对应编号的类，第二条样本数据对应的类编号就是（245,156,234,232），依次类推，所以右图文字写的是N*4。每一个类中心的数据维度和你划分的子空间的数据维度是保持一致的，我们可以通过码本反找到对应的类中心。

如此，可以看到，128维的数据最终变为了四个数字，数据经过了压缩，大大的降低了计算时间以及复杂度，将高维复杂的数据经过编码后，更加利于计算，这对海量数据的检索是非常有利的。

整个的训练过程是不断修正码本的过程，这个训练最终的结果是与样本的质量密切相关的。因为会用这个结果做最终的预测，也就是真实的业务数据最终会通过这个结果将数据分布到对应的类中，与搜索效果密切相关的。用户可以考虑在特定场景下，使用特定数据进行训练，否则，需要考虑数据带来的局限性。

好了，今天就到这里，欢迎交流。