microsoft在开放了inner product快速计算的方法:《Speeding Up the Xbox Recommender System Using a
Euclidean Transformation for Inner-Product Spaces》。主要解决inner product top-k search问题，我们来看下：
介绍
在线服务数据的大量增长，对于更好的信息过滤信息提出了新的风险与挑战。在推荐系统中，包括：
- (1) item目录(catalog)
- (2) users
- (3) 用户反馈(ratings)
推荐系统的目标是：为每个用户找到一个关于items的限定集合，使得它们具有最大可能的机会被该用户消费。现代推荐系统有两个主要部分：
- 第一部分：学习阶段，基于user feedback的离线模型学习
- 第二部分：检索阶段，对每个用户(在线)推荐items
该paper主要在第二阶段，推荐系统基于MF。特别的，对一个用户的推荐，我们引入了一个新方法来在运行时长（running time）和结果质量间做权衡。
MF是CF中最流行的方法。该方法要比其它近邻方法要好。在MF模型中，users和items通过latent feature vectors表示。Bayesian MF模型是Xbox推荐系统的核心，它每天会为数百万的用户提供游戏、电影、音乐推荐服务。在该系统中，users和items通过\(R^{50}\)的低维向量表示。用户u通过向量\(x_u\)表示，item i通过\(y_i\)表示，它们间的匹配质量(match quaity)通过两个向量间的内积\(x_u \cdot y_i\)来表示。内积越高表示该用户越愿意消费该item。
检索问题：理想情况下，给定一个用户u（它由向量\(v_u\)表示），所有item vectors \((y_1, \cdots, y_n)\)都会被检索。对于每个这样的item vector \(y_i\)，我们会计算它的匹配度\((x_u \cdot y_i)\)，items根据它们的匹配度进行排序。在该列表中具有最高匹配度的该items会被选中来形成最终的推荐列表。然而，在有限搜索时间内，items的catalog通常因为太大而不能对所有内积进行穷举计算。
Xbox的catalog包含了上百万的items。如果使用线性扫描，每个推荐都需要数百万内积计算。user vectors会吸收上下文信息，这些信息只在用户有行为时（engagement）提供。因而，user vector的计算是实时(online)的。结果是，推荐的items列表的检索只能在线(online)执行，不能离线预计算。该任务构成了在online servers引入的单个最大密集计算任务。因此，该过程需要有个快速的替代方案。
我们的贡献：该paper展示了如何来极大地加速推荐检索过程。该最优化item-user match检索与一个近似搜索相关：对与user vector检索高内积(high inner product)的items，但没必要检索最高的。该方法会由多个构建块组成。首先，我们定义了一个新的转换（transformation），它将内积问题转换成一个Euclidean最近邻问题（第3节）。作为一个预处理过程，该转换会被应用到item vectors上。在item检索期间，另一个转换会被应用到user vector上。在转换后空间中的具有最小欧氏距离（Euclidean distance）的item会被检索到。为了加快最近邻搜索，会使用PCA-Tree数据结构与一个新的邻近增强法（neighborhood boosting scheme）(第4节)。
为了演示提出方法的效果，它被应用到一个Xbox推荐数据集上，以及公开的Yahoo Music dataset上。实验表明，在推荐质量推化以及检索时间提升的trade-off曲线（第5节）。另外，time-accuracy trade-offs由两个baseline方法组成，基于LSH和对于在MF近似推荐上的当前state-of-art方法。我们展示了我们的方法具有更高的加速。
概念：我们使用：
- 小写字母表示scalars
- 粗体小写字母表示vector
- 粗体大写字母表示matrix
例如，x是scalar，x是vector，X是matrix。
给定一个向量\(x \in R^d\)，有：
- \(x_i\)表示在维度i上的measure，具有：\((x_1, x_2, \cdots, x_d)^T \in R^d\)
- norm通过\(\| \cdot \|\)来表示；欧氏空间中，\(\|x\|=\sqrt{\sum\limits_{i=1}^d x_i^2}\)。
- 我们通过\(x \cdot y\)来表示x和y间的内积dot product (inner product)。
- 最终，我们使用\((a, x^T)^T\)来表示一个标量a与一个向量x进行拼接。
3.简化搜索问题（REDUCIBLE SEARCH PROBLEMS）
该paper的一个关键贡献是，在search problem间进行有效的简化。在该部分，我们对search problem的概念进行公式化，并展示了在已知变种间的有效简化。
我们将search problem定义为：
定义1:
一个search problem \(S(I, Q, s)\)包含了一个关于n个items的实例集合\(I = \lbrace i_1, i_2, \cdots, i_n \rbrace \in I\)，一个query \(q \in Q\)，以及一个search function：
\[s : I \times Q \rightarrow \lbrace 1,2, \cdots, n \rbrace\]
函数s用于：对于一个给定query q，检索在I中的某一item的索引。我们的目标是，对items使用\(g: I \rightarrow I'\) 进行预处理，以便每个query都能有效得到结果。预处理函数g可以涉及到一个从某一domain到另一domain的转换，以便转换后的search problem可以在一个不同的domain上执行。以下的定义对search problems间的概念的简化做了公式化：
定义二：
一个search problem \(S_1(I, Q, s_1)\)被简化成一个search problem \(S_2(I', Q', s_2)\)，其中\(S_1 \leq S_2\)，如果存在函数\(g: I \rightarrow I'\)和\(h: Q \rightarrow Q'\)，那么：
\[j = s_1(I,q) \ 当且仅当 j=s_2(g(I), h(q))\]
该简化不会对g和h的运行时长做任何限制。注意，g只当成一个预处理step运行，而h会被应用到query时。这提出了一个要求：h必须有\(O(1)\)的运行时间。我们将该问题公式化为：
定义三：
我们会说：\(S_1 \leq_{O(f(n))} S_2, \ if \ S_1 \leq S_2\)，g和h的运行时间分别为\(O(f(n))\)和\(O(1)\)。
对于在\(R^d\)中的一个query vector，我们会在该paper中考虑三个search problem：
- MIP：在\(R^d\)中的n个vectors上的最大内积(maximum inner product)。为\(MIP_{n,d}\)
- NN：在\(R^d\)中n个vectors的最近邻(nearest neighbor)，为(\(NN_{n,d}\))
- MCS：在\(R^d\)中n个向量的最大cosine相似度。(\(MCS_{n,d}\))
它们的正式定义如下：
实例(Instance)：一个包含n个item向量的矩阵 \(Y=[y_1, y_2, \cdots, y_n]\)，其中\(y_i \in R^d\); 因此 \(I = R^{d \times n}\)
查询(Query)：一个vector \(x \in R^d\); \(Q = R^d\)
目标(objective)：根据以下公式进行检索index：
\[\begin{align}
s(Y,x) &= argmax_i (x \cdot y_i) && MIP_{n,d} \\
s(Y,x) &= argmin_i \| x - y_i \| && NN_{n,d} \\
s(Y,x) &= argmax_i \frac{x \cdot y_i}{\| x\| \| y_i \|} && MCS_{n,d}
\end{align}\]
其中i表示Y的第i列。
下一节展示了这三个问题间是如何进行转换的，可以使用：
-
\[MCS_{n,d} \leq_{O(n)} MIP_{n,d} \leq_{O(n)} NN_{n,d+1}\]
-
\[NN_{n,d} \leq_{O(n)} MCS_{n,d+1} \leq_{O(n)} MIP_{n,d+1}\]
来达成上述目标。
当对三个向量进行一个内积比较时，vectors x、\(y_i\)和\(y_j\)间不支持三角不等式(triangle inequality)，因为这是在MIP中的情况。许多高效的搜索数据结构依赖于三角不等式，如果MIP可以被转换成使用欧氏距离的NN，这些数据结构立马变得可用。我们的第一个定理论声明是，通过使用比原始问题多一维Euclidian metric，MIP可以被简化到NN。
定理1
\[MIP_{n,d} \leq_{O(n)} NN_{n,d+1}\]
证明：
假设：\(\phi \triangleq max_i \| y_i \|\)，
对输入(input)预处理：\(\hat{y}_i = g(y_i) = (\sqrt{\phi^2 - \|y_i\|^2}, y_i^T)^T\)
在query时：\(\hat{x} = h(x)=(0, x^T)^T\)。因为：
\[\begin{align}
& \| \hat{x} \|^2 = \| x \|^2 \\
& \|\hat{y}_i \|^2 = \phi^2 - \| y_i ||^2 + \|y_i\|^2 = \phi^2 \\
& \hat{x} \cdot \hat{y}_i = \sqrt{\phi^2 - \| x_i \|^2} \cdot 0 + x \cdot y_i = x \cdot y_i
\end{align}\]
我们有：
\[\| \hat{x} - \hat{y} \|^2 = \|\hat{x} \|^2 + \|\hat{y} \|^2 - 2 \hat{x} \cdot \hat{y}_i = \|x\|^2 + \phi^2 - 2x \cdot y_i\]
最终，\(\phi\)和x是与index i相互独立的：
\[j = argmin_i || \hat{x} - \hat{y}_i ||^2 = argmax_i (x \cdot y_i)\]
定理1是基础。在余下章节，我们会表述它的特性以及相关转换。
如果知道转化后的\(\hat{Y} = [\hat{y}_1, \hat{y}_2, \cdots, \hat{y}_n]\)在一个mainifold上，如上，我们期望通过使用\(NN_{n,d} \leq_{O(n)} MIP_{n,d-1}\)反向化简来恢复Y。然而，在常见case中，该transformation只可能通过再增加一维：
定理2
\[NN_{n,d} \leq_{O(n)} MIP_{n,d+1}\]
证明：
输入的预处理：\(\hat{y}_i = g(y_i) = (\| y_i \|^2, y_i^T)^T\)
在查询时：\(\hat{x} = h(x) = (1, -2 x^T)^T\)。
我们有：\(\hat{x} \cdot \hat{y}_i = \| y_i \|^2 - 2 x \cdot y_i\)。
最终：
\[j = \underset{i}{argmax} \ \hat{x} \cdot \hat{y}_i = \underset{i}{argmin} (\|x\|^2 + \|y_i \|^2 - 2x \cdot y_i) \\
= \underset{i}{argmin} \ \|x - y_i \|^2\]
MIP搜索可以被嵌入到一个MCS search中，通过增加1维来实现：
定理3
\[MIP_{n,d} \leq_{O(n)} MCS_{n,d+1}\]
证明：
预处理(preprocessing)和查询转换(query transformation)与定理1相同。输入的预处理为：
\(\phi \triangleq max_i \|y_i \|\)，假设：\(\hat{y}_i = g(y_i) = (\sqrt{\phi^2 - \|y_i\|^2}, y_i^T)^T\)。
在query时：
\[\hat{x} = h(x)= (0, x^T)^T\]
最终:
\[j = \underset{i}{argmax} \frac{\hat{x} \cdot \hat{y}_i}{\| \hat{x} \| \|\hat{y}_i \|} = \underset{i}{argmax} \frac{x \cdot y_i}{\| x \| \phi} = \underset{i}{argmax} x \cdot y_i\]
然而，MCS可以通过归一化向量来简化MIP查询：
定理4
\[MCS_{n,d} \leq_{O(n)} MIP_{n,d}\]
证明：
输入预处理：\(\hat{y}_i = g(y) = \frac{y_i}{\|y_i\|}\)。
在query时：\(\hat{x} = h(x) = x\)。
最终：
\[j = argmax_i \hat{x} \cdot \hat{y}_i = argmax_i \frac{x \cdot y_i}{\|x \| \|y_i \|}\]
我们的最终结果表明，一个NN search可以被转换成一个MCS search，通过增加1维来实现：
定理5
\[NN_{n,d} \leq_{O(n)} MCS_{n,d+1}\]
证明：
与定理1中的简化相同。输入的预处理为：\(\phi \triangleq max_i \| y_i \|\)，以及 \(\hat{y}_i = g(y_i) = (\sqrt{\phi^2 - \|y_i\|^2}, y_i^T)^T\)。
在query时：\(\hat{x} = h(x)=(0, x^T)^T\)。
加上定理1:
\[j = argmax_i \frac{\hat{x} \cdot \hat{y}_i}{ \|\hat{x}\| \|\hat{y}_i \|} = argmax_i \frac{x \cdot y_i}{\|x\| \phi} = argmax_i x \cdot y_i = argmin_i \|\hat{x} - \hat{y}_i \|^2\]
接下来，我们利用定理1来加速在Xbox中和其它基于MF的推荐系统的检索。
4.我们的方法
我们的解决方案基于两个部分：
- 1.将问题简化到一个Euclidian search problem
- 2.使用一个PCA-Tree来求解它。
简化过程（reduction）与定理1的定义非常相似，但会使用一个额外的平移（shift）和旋转（rotation），因此，MIP search problem会被简化到NN search，所有的vectors与它们的主成分（pricipal components）相对齐。
4.1 简化
我们首先根据定理1定义了第一个简化函数。假设：\(\phi \triangleq max_i \| y_i \|\)，以及：
\[\begin{align}
y_i^* &= g_1(y_i) = ( \sqrt{\phi^2 - \|y_i \|^2}, y_i^T)^T \\
x^* &= h_1(x)=(0, x^T)^T
\end{align}\]
…(2)
其中，当应用到Y上时，给定元素\(y_i^* \in R^{d+1}\)。这会将MIP化简到NN。由于NN在输入空间中（input space）对于平移(shift)和旋转(rotations)是不变的，我们可以使用PCA rotation来构成(compose)该转换（transformations），并且可保证一个等价的search problem。
我们对数据进行mean-center并进行rotate：假设\(\mu = \frac{1}{n} \sum\limits_i y_i^*\)是在第一次化简后的均值，并且\(M \in R^{(d+1) \times n}\)是一个使用\(\mu\)沿着它的列进行复制的矩阵。该中心数据矩阵的SVD为：
\[(Y^* - M) = W \Sigma U^T\]
其中，数据项(data items)出现在\(Y^*\)的列中。矩阵W是一个\((d+1) \times (d+1)\)的矩阵。\(W=[w_1, \cdots, w_{d+1}]\)的每一列定义了一个正交单位长度的特征向量（eigenvector），因此，每个\(w_j\)定义了一个超平面，每个\(y_i^* - \mu\)被投影到它上面。矩阵W是一个旋转矩阵，它会将这些vectors对齐到它的主成分(principal components)上。我们定义了中心旋转（centered rotation）作为我们的第二个转换：
\[\begin{align}
\hat{y}_i = g_2(y_i^*) = W^T (y_i^* - \mu) \\
\hat{x} = h_2(x^*) = W^T (x^* - \mu)
\end{align}\]
…(3)
其成分（composition）为：
\[g(y_i) = g_2(g_1(y_i)), h(x) = h_2(h_1(x))\]
…(4)
仍定义了一个从MIP到NN的简化(reduction)。使用\(\hat{y}_i = g(y_i)\)，为我们给出了一个关于输入向量\(\hat{Y}\)的转换后集合，可以在其上执行一个Euclidian search。另外，在该转换后，该点会被旋转，因而它们的成分（compoments）会减小方差的阶数（order of variance）。接着，我们会使用一个PCA-Tree数据结构来索引在\(\hat{Y}\)中的转换后的item vectors。我们将上述逻辑表述在算法1中。
算法1
4.2
略
参考
