姚伟峰
[yaoweifeng0301@126.com]
http://www.cnblogs.com/Matrix_Yao/
问题
MIP (Maximum Inner Product)
-
输入
-
查询向量(query):
-
底库(database):
, 其中
-
-
输出
-
底库中与查询向量点积相似度最大的k个向量：
-
MCS (Maximum Cosine Similarity)
-
输入
-
查询向量(query):
-
底库(database):
, 其中
-
-
输出
-
底库中与查询向量点积相似度最大的k个向量：
-
转换
MIP 
L2
通过保序变换(Ordering Preserving Transformation)：
设
, 对每个查询向量
和库向量
分别作如下变换：
则，新的
维向量
和
的L2距离与, 的IP距离有如下关系： 
和
都与
无关，因此： 
即维向量、的L2距离的升序排序与、的IP距离的降序排列是一致的。
MCS L2
Cosine相似性是归一化后的IP距离：
所以，可以先对做一个归一化， 变成
。后面，就把这个问题转换成了MIP， 可以用上面的MIP->L2的变换。特殊的是：此时
。因此, 只需要做一个很简单的变换： 
则， 
即： 
从上式可得，、的L2距离的升序排列与,、的cosine相似性的降序排列是一致的。
实操适用
IVF Based Indexing, 使用方式：
-
训练阶段不使用变换，召回阶段使用变换
支持
训练阶段还是使用IP或者cosine相似性构建索引， 召回阶段使用相应的变换L2距离召回。 -
训练阶段、召回阶段都使用变换
-
MIP: 支持，但需要修改训练过程。需要注意：在训练阶段，质心是
，因此每一轮迭代算出新的质心后，需要先计算把所有质心按照上述的变换重新完整做一遍
维到。 -
MCS: 支持，但需要修改训练过程。需要注意：在训练阶段，质心是
，因此每一轮迭代算出新的质心后，需要先计算把所有质心重新做一遍归一化。
-