xbox IP-2-Euclidean转换介绍

Reading time ~3 minutes

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}\]

来达成上述目标。

3.1 保序转换(Order Preserving Transformations)

当对三个向量进行一个内积比较时,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

参考

ali COLD介绍

ali在《COLD: Towards the Next Generation of Pre-Ranking System》中讲述了他们的实现。# 摘要长期以来,pre-ranking只是ranking模块的一个简化版本,它要处理待排序的更大集合的候选。这里的努力是为了简化r...… Continue reading

dynamic embedding介绍

Published on August 02, 2020

md embedding介绍

Published on July 01, 2020