乘积量化(Product Quantization)

相似近邻搜索--乘积量化

论文：Product Quantization for Nearest Neighbor Search

主要思想：将高维向量分解为低维向量的笛卡尔积，并在每个低维空间中对向量进行量化。量化，即用编码(int)代替低维向量(float64). 用编码的欧氏距离估计两个向量的距离，文中指出，非对称距离（向量和编码的距离近似真实距离）能够提升模型精度。

训练：聚类

将划分好的子空间中低维向量进行聚类，找到最近中心点，索引即需要存储的编码。其中聚类的距离公式可选择欧氏距离、余弦相似度等。

搜索：

寻找与所给向量query最相似的向量，有两种方法：

1、对称：将query用聚类中心点表示，再寻找最相近的向量；

2、非对称：直接用query寻找已存储数据库中最相近的向量。

参考文献：

[1] Hervé Jégou, Matthijs Douze, Cordelia Schmid. Product Quantization for Nearest Neighbor Search. IEEE Transactions on Pattern Analysis and Machine Intelligence, Institute of Electrical and Electronics Engineers, 2011, 33 (1), pp.117-128. ff10.1109/TPAMI.2010.57ff. ffinria-00514462v2ff