xbox IP-2-Euclidean转换介绍

Reading time ~1 minute

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通过的低维向量表示。用户u通过向量表示,item i通过表示,它们间的匹配质量(match quaity)通过两个向量间的内积来表示。内积越高表示该用户越愿意消费该item。

检索问题:理想的,给定一个用户u,它由向量表示,所有item vectors 都会被检索。对于每个这样的item vector ,会计算它的匹配质量,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。给定一个向量表示在维度i上的measure,具有:。norm通过来表示;欧氏空间中,。我们通过来表示x和y间的内积dot product (inner product)。最终,我们使用来表示一个标量a与一个向量x进行拼接。

3.简化搜索问题(REDUCIBLE SEARCH PROBLEMS)

该paper的一个关键贡献是,在search problem间进行有效的简化。在该部分,我们对search problem的概念进行公式化,并展示了在已知变种间的有效简化。

我们将search problem定义为:

定义1:

一个search problem 包含了一个关于n个items的实例集合,一个query ,以及一个search function:

函数s用于:对于一个给定query q,检索在I中的某一item的索引。我们的目标是,对items使用 进行预处理,以便每个query都能有效得到结果。预处理函数g可以涉及到一个从某一domain到另一domain的转换,以便转换后的search problem可以在一个不同的domain上执行。以下的定义对search problems间的概念的简化做了公式化:

定义二

一个search problem 被简化成一个search problem ,其中,如果存在函数,那么:

该简化不会对g和h的运行时长做任何限制。注意,g只当成一个预处理step运行,而h会被应用到query时。这提出了一个要求:h必须有的运行时间。我们将该问题公式化为:

定义三

我们会说:,g和h的运行时间分别为

对于在中的一个query vector,我们会在该paper中考虑三个search problem:

  • MIP:在中的n个vectors上的最大内积(maximum inner product)。为
  • NN:在中n个vectors的最近邻(nearest neighbor),为()
  • MCS:在中n个向量的最大cosine相似度。()

它们的正式定义如下:

实例(Instance):一个包含n个item向量的矩阵 ,其中; 因此

查询(Query):一个vector ;

目标(objective):根据以下公式进行检索index:

其中i表示Y的第i列。

下一节展示了这三个问题间是如何进行转换的,可以使用:

来达成上述目标。

3.1 保序转换(Order Preserving Transformations)

当对三个向量进行一个内积比较时,vectors x、间不支持三角不等式(triangle inequality),因为这是在MIP中的情况。许多高效的搜索数据结构依赖于三角不等式,如果MIP可以被转换成使用欧氏距离的NN,这些数据结构立马变得可用。我们的第一个定理论声明是,通过使用比原始问题多一维Euclidian metric,MIP可以被简化到NN。

定理1

证明

假设:

对输入(input)预处理:

在query时:。因为:

我们有:

最终,和x是与index i相互独立的:

定理1是基础。在余下章节,我们会表述它的特性以及相关转换。

如果知道转化后的在一个mainifold上,如上,我们期望通过使用反向化简来恢复Y。然而,在常见case中,该transformation只可能通过再增加一维:

定理2

证明

输入的预处理:

在查询时:

我们有:

最终:

MIP搜索可以被嵌入到一个MCS search中,通过增加1维来实现:

定理3

证明

预处理(preprocessing)和查询转换(query transformation)与定理1相同。输入的预处理为:

,假设:

在query时:

最终:

然而,MCS可以通过归一化向量来简化MIP查询:

定理4

证明

输入预处理:

在query时:

最终:

我们的最终结果表明,一个NN search可以被转换成一个MCS search,通过增加1维来实现:

定理5

证明

与定理1中的简化相同。输入的预处理为:,以及

在query时:

加上定理1:

接下来,我们利用定理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定义了第一个简化函数。假设:,以及:

…(2)

其中,当应用到Y上时,给定元素。这会将MIP化简到NN。由于NN在输入空间中(input space)对于平移(shift)和旋转(rotations)是不变的,我们可以使用PCA rotation来构成(compose)该转换(transformations),并且可保证一个等价的search problem。

我们对数据进行mean-center并进行rotate:假设是在第一次化简后的均值,并且是一个使用沿着它的列进行复制的矩阵。该中心数据矩阵的SVD为:

其中,数据项(data items)出现在的列中。矩阵W是一个的矩阵。的每一列定义了一个正交单位长度的特征向量(eigenvector),因此,每个定义了一个超平面,每个被投影到它上面。矩阵W是一个旋转矩阵,它会将这些vectors对齐到它的主成分(principal components)上。我们定义了中心旋转(centered rotation)作为我们的第二个转换:

…(3)

其成分(composition)为:

…(4)

仍定义了一个从MIP到NN的简化(reduction)。使用,为我们给出了一个关于输入向量的转换后集合,可以在其上执行一个Euclidian search。另外,在该转换后,该点会被旋转,因而它们的成分(compoments)会减小方差的阶数(order of variance)。接着,我们会使用一个PCA-Tree数据结构来索引在中的转换后的item vectors。我们将上述逻辑表述在算法1中。

算法1

4.2

参考

BERT4Rec介绍

# 介绍从历史行为中建模用户的动态偏好,对于推荐系统来说是个挑战。之前的方法采用序列神经网络以从左到右的方式将用户历史交互编码成隐表示,来生成推荐。尽管它们是有效的,这种从左到右的单向模型是次优的,我们对此仍有争论,因为有以下的限制:- a) 单向结构限制了在用户行为序列中...… Continue reading

youtube推荐强化学习介绍

Published on June 20, 2019

DSIN介绍

Published on May 27, 2019