用L2距离做MIP、MCS排序

2020-09-11  本文已影响0人  MatrixOnEarth

问题

MIP (Maximum Inner Product)

MCS (Maximum Cosine Similarity)

转换

MIP \to L2

通过保序变换(Ordering Preserving Transformation)：
设\phi \overset{\triangle}{=}\underset{i}{max\ } ||y_i||, 对每个查询向量x和库向量y_i分别作如下变换：
\begin{align*} &\tilde{y}_{i} = (y_i^T, \sqrt{\phi^2-||y_i||^2})^T \\ &\tilde{x} = (x^T, 0)^T \end{align*}
则，新的d+1维向量\tilde{x}和\tilde{y_i}的L2距离与x, y_i的IP距离有如下关系：
\begin{align*}d^2 &= ||\tilde{x} - \tilde{y}_i||^2 \\ &= ||\tilde{x}||^2 + ||\tilde{y}_i||^2-2\tilde{x}*\tilde{y}_i \\ &= ||x||^2 + (||y_i||^2 + \phi^2 - ||y_i||^2) - 2x*y_i \\ &= ||x||^2 + \phi^2 - 2x*y_i\end{align*}
||x||^2和\phi都与i无关，因此：
j = \underset{i}{argmin\ }\sqrt{||\tilde{x} - \tilde{y}_i||^2} = \underset{i}{argmax\ }x*y_i
即d+1维向量\tilde{x}、\tilde{y_i}的L2距离的升序排序与x、y_i的IP距离的降序排列是一致的。

MCS \to L2

Cosine相似性是归一化后的IP距离：
\frac{x*y_i}{||x||* ||y_i||} \propto x * \frac{y_i}{||y_i||} 所以，可以先对y_i做一个归一化， 变成y'_i = \frac{y_i}{||y_i||}。后面，就把这个问题转换成了MIP， 可以用上面的MIP->L2的变换。特殊的是：此时\phi = 1。因此, 只需要做一个很简单的变换：
\begin{align*} &\tilde{y}_{i} = \frac{y_i}{||y_i||} \end{align*}
则，
\begin{align*}d^2 &= ||x - \tilde{y}_i||^2 \\ &= ||x||^2 + 1 - 2\frac{x*y_i}{||y_i||} \end{align*}
即：
j = \underset{i}{argmin\ }\sqrt{||x - \tilde{y}_i||^2} = \underset{i}{argmax\ }\frac{x*y_i}{||y_i||}
从上式可得，x、\tilde{y_i}的L2距离的升序排列与x,、y_i的cosine相似性的降序排列是一致的。

实操适用

IVF Based Indexing, 使用方式：

参考文献

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

猜你喜欢

热点阅读