海量文本求topk相似：faiss库初探

近似最近邻搜索一般可以实现两个目标：一是加快查询速度，二是降低内存压力。
那它是怎么实现的呢？
近似最近邻搜索中蕴含了降维和聚类的思想，以下是两种常用的实现方法：
一是基于哈希函数的局部敏感哈希，二是基于向量量化的乘积量化。

基于哈希的方法，是通过哈希函数把向量变换成二值码(如0101110101)，然后将向量距离近似成二值码距离（如海明距离），从而减少计算距离的时间。
局部敏感哈希就是一种基于哈希的方法，通过选择合适的哈希函数，将高维空间的数据映射到低维空间。
这起到降维的作用。
同时以非常大的概率，将在高维空间中相邻的点，映射到同一个桶（Bucket）中，而不相邻的点，映射到同一个桶的概率很小。
这起到聚类的作用。
在高维空间中相邻的数据，映射到低维空间后，依然保持相邻关系，这与传统的HashTable不同。

对数据库中的所有数据都进行哈希映射，把所有数据分到不同的桶里面。
过来一条查询数据，将其映射到某个桶内，然后和这个桶内的所有数据计算距离，从而得出topk相似的数据。
这就将在一个超大集合内查找相邻元素的问题，转化为了在一个很小的子集合内查找相邻元素的问题，计算量自然减少了。

这是什么意思？
向量用对应的类中心来近似，那这个类里面的所有向量不就是一样的吗？
错！
乘积量化（PQ，Product Quantization）是向量量化的代表方法，我们来看乘积量化是怎么做的，就能理解上面的话了。
上面说的聚类，可不是把所有的向量进行聚类，而是先把向量切分成若干个区域（类似BERT的Multi-Head的切分），再对每个区域的所有数据进行聚类。
比如数据有1万条，每条数据表示为100维的向量。
把100维向量切分为4个25维的子向量，第1个子向量集合仍然有1万个数据，第2、3、4个子向量集合也有1万个数据。
对于每个子向量集合（1万个数据）聚成K类，得到K个类中心。
每个子向量集合作为一个量化器，可以得到4个量化器（Quantizer）。
那么聚类中心一共是4×K个吗？
错！

聚类中心一共是 K^4
个。

因为这是乘积量化，而乘积指的是笛卡尔积。
假设集合A={a,b}，集合B={1,2,3,4}，也就是K=2，则两个集合的笛卡尔积为：
8个聚类中心，正是K的4次方。

那么向量用对应的聚类中心来近似，又是啥子？

比如一个向量被切分了4个子向量，4个子向量分别属于 a、b、a、b类。
那么该向量就表示为（a_1, b_2, a_3, b_4），也就是用聚类中心的id来表示。
从100维变成了4维，维度降低25倍。
如果这100维数据是float32类型的（32bits），压缩成8bits，那么压缩比为：
(100*32/4)/8=100
为啥你解释得这么细？
因为faiss这个库的乘积量化就是这么干的啊！
以上是前期的准备工作，可以看做是在训练一个模型，构建所有聚类中心的索引（Index）。
模型训练好了，来了一个查询向量，怎么搜索topk相似呢？
这就需要计算查询向量和数据库中某个向量的距离。
论文中有两种计算距离的近似方法：
对称方法（Symmetric distance computation ，SDC）。
非对称方法（Asymmetric distance computation ，ADC）。
对称方法就是指，将查询向量和被查询向量都用聚类中心的id来编码。
查询向量：（a_1, b_2, a_3, b_4）
被查向量：（a_1, a_2, b_3, a_4）
聚类中心两两之间的距离提前计算好了，假如为：
查询向量：（a_1, b_2, a_3, b_4）
被查向量：（a_1, a_2, b_3, b_4）
中心距离：（0,     1,     3,     0）
那么 sum(0,1,3,0)=4，就是查询向量和被查向量的距离。
对应的公式为：

非对称方法就是指，不需要将查询向量用聚类中心的id来编码，只对被查询向量编码。
将查询向量分为4个子向量后，直接求子向量和被查向量的聚类中心的距离，再加总求和。
查询向量：（1,     2,     3,     4）
被查向量：（a_1, b_2, a_3, b_4）
中心距离：（0,     1,     3,     0）
对应的公式为：

论文中选择的方法是非对称的方法。
用一句话来总结乘积量化：
乘积量化的本质是将高维向量空间分解为子空间的笛卡尔积，然后分别量化这些子空间。
四：faiss库的使用