用L2 距离做MIP、MCS排序

姚伟峰
[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: 支持，但需要修改训练过程。需要注意：在训练阶段，质心是，因此每一轮迭代算出新的质心后，需要先计算把所有质心重新做一遍归一化。

参考文献

1. Speeding Up the Xbox Recommender System Using a Euclidean Transformation for Inner-Product Spaces