文摘

学习排序算法近年来已成为重要的由于其成功应用在信息检索中,推荐系统,计算生物学,等等。排名支持向量机(RankSVM)的技术发展水平排名模型和已顺利地应用。非线性RankSVM (RankSVM非线性内核)可以给精度高于线性RankSVM (RankSVM线性内核)对于复杂非线性排名问题。然而,学习方法对非线性RankSVM仍然因为内核矩阵的计算耗时。在本文中,我们提出一个快速排名算法基于内核近似,以避免计算内核矩阵。我们探索两种内核近似方法,即Nystrom方法和随机傅里叶特征。原始的截断牛顿法用于优化成对L2-loss(平方Hinge-loss)排名模型的目标函数在非线性内核近似。实验结果表明,我们提出的方法得到一个更快的训练速度比内核RankSVM和达到类似或更好的性能先进的排名算法。

1。介绍

学习是机器学习的一个重要研究领域。它吸引了许多研究者的兴趣,因为其日益增长的应用在信息检索系统等领域1),推荐系统(2,3),机器翻译,和计算生物学4]。例如,在文档检索领域,排名模型是基于训练数据训练的一些查询。每个查询都包含一组相应的检索文件和标签由人类的相关性水平。当预测新的查询到来时,训练模型用于等级对应的文档检索查询。

许多类型的机器学习算法提出了排名的问题。其中,RankSVM [5),从基本的支持向量机(SVM) [6),是常用的方法之一。RankSVM的基本思想是将排序问题转化为两两分类问题。的早期实现RanSVM [7)是缓慢的,因为显式转换成对导致大量的训练样本。为了加快培训过程,8)提出了一个原始的牛顿法的算法来解决线性RankSVM-struct问题不需要显式转换成对。和[9)提出了RankSVM基于结构化输出学习框架。

与支持向量机、内核技巧可以用来概括非线性情况下的线性排序问题RankSVM [7,9]。内核RankSVM可以给精度高于线性RankSVM对于复杂非线性排名问题[10]。非线性内核可以原始特征映射到高维空间可以排名线性非线性问题。然而,内核RankSVM大幅增长的训练时间增加训练数据集的大小。计算复杂性的数量至少是二次培训因为内核矩阵的计算例子。内核近似是一个有效的方法来解决上面的问题。它可以避免计算内核矩阵通过显式地接近内核的数据生成一个向量表示任意两个数据点之间的相似性。

近似的方法可以分为两类:Nystrom方法(11,12)和随机傅里叶特征(13,14]。Nystrom方法接近内核矩阵的低秩矩阵。傅里叶特征的随机方法接近移不变的内核基于傅里叶变换的非负测量(15]。在本文中,我们使用内核近似方法来解决这个问题的内核RankSVM漫长的训练时间。

我们所知,这是第一个使用内核近似方法来解决学习等级问题。我们使用两种类型的近似方法,即Nystrom方法或随机傅里叶特征,将特征映射到高维空间。近似映射后,原始的截断牛顿法用于优化成对L2-loss(平方Hinge-loss) RankSVM模型的功能。实验结果表明,我们的方法可以实现高性能和比内核RankSVM训练速度快。最先进的排名算法相比,我们的方法也可以得到类似或更好的性能。Matlab代码网上对我们的算法(https://github.com/KaenChan/rank-kernel-appr)。

在本节中,我们提出的背景及相关工作学习算法和RankSVM排名。

2.1。学习排序算法

学习排序算法可以分为三类:逐点的方法,成对的方法,和list-wise方法。(我)点态:它将排序问题转换为回归或分类单一对象。然后现有回归或分类算法直接应用于模型单一对象的标签。这种方法包括McRank [16]和OC SVM [17]。(2)成对:它将排序问题转换为对回归或分类对象。它可以对模型内的偏好对象。这种方法包括RankSVM [5]和RankBoost [18]。(3)List-wise:需要排名列表实例学习和预测,可以优化List-wise直接损失函数。这种方法包括ListNet [19],AdaRank [20.],BoltzRank [21),而支持向量机地图(22]。在本文中,我们专注于基于SVM的成对的排名算法。

2.2。线性RankSVM

线性RankSVM是一种常用的成对排名算法(5]。网络搜索的问题 每个查询的查询和一组文档,功能 从query-document提取对( , )和标签 的相关性水平吗 到查询 。因此,训练数据是一组label-query-instance元组 。让 表示偏好对的集合。如果 , 和 在同一个查询( ), 是首选 ( )。线性RankSVM获得排名的目标函数 这样 , , 。

由于margin-maximization RankSVM有很好的泛化属性。根据(27),保证金被定义为最接近的两个数据点之间的距离,当数据点项目排序向量 : 最大化的利润很好,因为数据点对小利润代表非常不确定的排名决定。RankSVM能保证找到一个排序向量 与最大利润(27]。图1显示了四个数据点的margin-maximization线性RankSVM。两个线性排名的权重,即 和 ,既能对四个数据正确。但 推广了比 因为保证金 的 大于保证金吗 的 。


图1
对线性RankSVM Margin-maximization。四个数据点有偏好 并且可以线性排名。 和 边际的距离吗 和 。

L1-loss (Hinge-loss)线性RankSVM [5),目标函数是损失 在哪里 是正则化参数。方程(3)可以通过标准SVM分类解决成对差异向量 。但这种方法非常缓慢,因为大尺寸的 。

在[8),提出了一种有效的算法来解决L2-loss(平方Hinge-loss)线性RankSVM问题 他们使用了 稀疏矩阵 训练样本获取成对差异 隐式( )。如果 ,有一个数字 这样 和 剩下的是0。让 。方程(4)可以写成 在哪里 是一个 对角矩阵 如果 和0。然后,(5原始的截断牛顿法)进行了优化 。

2.3。内核RankSVM

内核方法的关键是,如果内核函数 是正定的,存在一个映射 再生核希尔伯特空间理论到再生核希尔伯特空间(),这样 在哪里 表示内积。内核方法的优势在于映射 从来没有显式计算。

对于L1-loss RankSVM,客观损失函数与内核映射 的形式(7] 的原始问题(7)可以使用拉格朗日乘数法转化为对偶问题。 每个钉弹乘数 对应于一对指数 在 和 解决内核RankSVM是一个大的二次规划问题。而不是直接计算矩阵 ,我们可以节省成本 在(5)。 的排名功能内核RankSVM形式 的计算 需要 内核评估。很难扩展到大内核RankSVM解决(8)。

几个工作提出了加快训练速度内核RankSVM,如1-slack结构方法(9),用定理再形成(27],成对问题重组(10]。然而,这些方法仍然缓慢大规模排名问题,因为计算成本的数量至少是二次培训的例子。

3所示。与内核RankSVM近似

3.1。一个统一的模型

内核RankSVM的缺点是它需要储存许多内核的价值 在优化。此外, 需要计算新的数据 在预测期间,可能对于许多向量 。这个问题可以通过近似解决内核映射明确: 在哪里 的映射内核近似。原来的功能 可以映射到近似希尔伯特空间 。与内核RankSVM近似的目标函数可以写成 在哪里 是支持向量机的损失函数,如 L1-loss支持向量机和 L2-loss支持向量机。的问题(13)可以解决使用线性近似后RankSVM映射。内核不需要在培训过程中计算。此外,权重 可以直接计算不需要存储任何训练样本。新数据 ,排名函数

我们建议的方法主要包括映射过程和排名的过程。(我)映射过程:内核近似用于原始数据映射到高维空间。我们使用两种内核近似方法,即Nystrom方法和随机傅里叶特征,将讨论部分3.2。(2)排名过程:使用线性RankSVM训练排序模型。我们使用L2-loss RankSVM由于其精度高,训练速度快。优化过程将部分中描述3.3。Nystrom方法是数据依赖和傅里叶特征的随机方法数据独立(28]。Nystrom方法通常可以得到更好的近似比随机傅里叶特征,而Nystrom方法略低于随机傅里叶特征。此外,在排名的过程,我们可以取代L2-loss RankSVM与其他线性排名算法,如ListNet [19)和弗兰克(23]。

3.2。内核近似
3.2.1之上。Nystrom方法

Nystrom得到核矩阵的低秩近似方法 通过均匀采样 的例子 ,用 。让 和 。的行和列 和 可以重新安排 在哪里 和 。然后排名- 近似矩阵 的 可以计算的11] 在哪里 的伪逆 和 是最好的 等级近似的 。的解决方案 可以通过奇异值分解)的 , ,在那里 是一个标准正交矩阵和 是一个对角矩阵 。的解决方案 可以获得的 在哪里 是第一个 列 和 。因此,Nystrom方法的非线性特性映射可以写成(28] Nystrom方法的算法描述的算法1。的总时间的近似的复杂性 样品是 。Nystrom方法的近似误差 (11]。

需要: ,
确保:
(1)均匀样本 行 ,用 ;
(2) ;
(3) ;
(4)上执行计算 得到 ;
(5)
算法1
Nystrom方法。
3.2.2。随机傅里叶特征

傅里叶特性是一种有效的随机特性转换为内核矩阵近似方法计算相对较低的内积空间的映射。

当内核 移不变的,连续的,正定,内核可以写成的傅里叶变换 在哪里 是一个概率密度函数, 。根据博赫纳定理(15),内核可以近似 在哪里 采样于 。自 和 是真实的, 在哪里 是统一来自 (13]。期望在(20.)可以近似的意思 傅里叶组件 在哪里 从分布采样 和 是均匀采样 。中描述的算法是算法2。的总时间的近似的复杂性 样品是 。Nystrom方法的近似误差 (14]。

需要: ,
确保:
(1)计算傅里叶变换 的内核;
(2)样本 从分布
(3)均匀样本 从 ;
(4)
算法2
随机傅里叶特征。
3.3。排名优化

在本节中,我们解决L2-loss(平方Hinge-loss)排名的问题(13)内核近似映射后的训练数据 类似的,(5),损失函数可以写成 在哪里 。渐变的广义海赛矩阵(23) 在哪里 是单位矩阵。海赛矩阵不需要显式地使用截断牛顿法计算(8]。牛顿的步骤 可以使用线性近似计算共轭梯度(CG)。线性CG的主要计算方法是Hessian-vector乘法 为向量 假设嵌入空间 有 维度,总该方法的复杂性 在哪里 。我们的算法的主要步骤描述的算法3。我们计算近似嵌入 使用Nystrom方法或随机线(1)傅里叶特征。 应用于所有训练样本(2)。线性RankSVM模型与原始的截断牛顿法应用在嵌入空间中一致(3)- (11)。

需要: , , ,
确保:
(1)计算近似嵌入 使用Nystrom方法或随机傅里叶特征;
(2)应用 训练样本, ;
(3)重复
(4) ;
(5) ;
(6)/ /解决 通过线性CG
(7)重复
(8)更新基于Hessian-vector乘法的计算, 为向量 ;
(9)直到收敛
(10) ;
(11)直到收敛的牛顿一步
算法3
与内核RankSVM近似。

4所示。实验

4.1。实验设置

我们使用三个数据集从LETOR (http://research.microsoft.com/en-us/um/beijing/projects/letor),即OHSUMED、MQ2007 MQ2008,来验证我们提出的排名算法。数据集的例子从信息检索中提取的数据收集。这些数据集通常用于评估新学习排名算法。表1数据集的属性列表。意思是平均精度(地图)29日)和归一化累积折扣获得(NDCG) [30.)选为评价指标排名的性能模型。

表1
使用LETOR信息数据集。Q-D双表示Query-Document双。每一对标签数据集的相关性在0 (nonrelevant), 1(可能是相关的),2(相关)。

我们比较了该方法与线性和内核RankSVM如下:(我)RankSVM-Primal(8):讨论部分2.1解决原始问题的线性L2-loss RankSVM (http://olivier.chapelle.cc/primal/)。(2)RankSVM-Struct(9]:它解决了一个等效1-slack结构线性内核(支持向量机问题http://www.cs.cornell.edu/People/tj/svm_light/svm_rank.html)。(3)RankSVM-TRON(10排名):它解决了线性或内核支持向量机问题,信赖域牛顿法(https://www.csie.ntu.edu.tw/ cjlin / libsvmtools /)。(iv)RankNystom:我们提出RankSVM Nystrom内核的近似。(v)RankRandomFourier:我们提出RankSVM傅里叶特征的随机内核近似。

hyperparameters选择算法的网格搜索。正则化参数 每个算法的选择 。对于内核RankSVM和我们的近似方法,参数 RBF核函数的选择 。MQ2007数据集,抽样数量的内核近似 设置为2000,而 对于其他数据集。所有的实验都进行高性能服务器2.0 GHz 16核CPU和64 GB的内存。

4.2。Nystrom方法的比较和随机傅里叶特征

图2显示了性能比较的RankSVM Nystrom方法和随机傅里叶特征MQ2007数据集。取线性RankSVM算法、RankSVM-Primal基线法,绘制虚线。剩下的两条线代表RankNystrom和RankRandomFourier分别。一开始,内核的性能比线性RankSVM近似方法。但随着的增加 (抽样近似的数量),两个内核可以比线性RankSVM近似方法。我们还观察到比RankRandomFourier RankNystrom得到更好的结果 很小,两种方法获得类似的结果什么时候 。

(一)
(一)
(b)
(b)
(c)
(c)
(d)
(d)
图2
性能比较的RankSVM Nystrom方法和随机傅里叶特征MQ2007数据集。(一)(电子邮件保护);(b)(电子邮件保护);(c) MeanNDCG;(d)地图。
4.3。与线性和内核RankSVM

在本部分中,我们比较建议内核其他线性近似排名算法和内核RankSVM算法。我们把 内核的近似。表2给不同的RankSVM算法的结果在第一折MQ2007数据集。线性RankSVM算法使用更少的训练时间,但他们MeanNDCG值低于的价值内核RankSVM算法。我们的内核近似方法获得更好的性能比内核RankSVM-TRON在这个数据集以更快的训练速度。我们的内核近似方法的训练时间是大约十秒,而内核的训练时间RankSVM-TRON超过13个小时。傅里叶特征随机的结果略优于RankNystrom方法。此外,L2-loss RankSVM可以获得更好的性能比L1-loss RankSVM这个数据集。的MeanNDCG RankSVM-Primal(线性)略高于RankSVM-TRON(线性)。内核近似方法获得更好的比RankSVM-TRON MeanNDCG RBF内核。

表2
结果不同的RankSVM MQ2007数据集的算法在第一折。我们把 内核的近似方法。
4.4。比较先进的

在这一部分,我们比较我们与最先进的排名算法的算法。大部分比较算法的结果来自LETOR的基线。剩下的结果来自论文的算法。的hyperparameters 和 我们提出的内核近似RankSVM网格搜索选择的部分4.1。

表3提供测试NDCG和地图的比较不同的排名算法TD2004数据集的结果。抽样的数量为内核近似 设置为500。我们可以观察到内核近似排名方法可以达到最好的表现在3方面的所有6指标。同时,RankNystrom和RankRandomFourier相似的结果。

表3
性能比较TD2004数据集。

表4提供OHSUMED数据集上的性能比较。 设置为500。我们曾经观察到3日RankRandomFourier达到最好的性能指标的6个指标。指标2日RankNystrom得到最好的结果。

表4
性能比较OHSUMED数据集。

表5MQ2007数据集提供的比较结果。 设置为2000。我们观察到RankNystrom获得最好的成绩3指标MQ2007数据集。BL-MART也达到最好的成绩3指标。然而,BL-MART火车10000年LambdaMART并创建的模型通过随机选择这些模型的一个子集,而我们提出RankNystrom算法只训练一个模型。

表5
性能比较MQ2007数据集。

5。结论

在本文中,我们提出一个快速RankSVM与内核近似算法解决内核RankSVM漫长的训练时间的问题。首先,我们提出了一个统一的内核模型近似RankSVM。近似法是用来避免计算内核矩阵显式近似内核任意两个数据点之间的相似性。然后,两种类型的方法,即Nystroem方法和随机傅里叶特征,探索近似内核矩阵。同时,原始的截断牛顿法用于优化L2-loss(平方Hinge-loss)排名模型的目标函数。实验结果表明,我们建议的方法需要更少的计算成本比内核RankSVM和达到类似或更好的性能先进的排名算法。在未来,我们打算使用更高效的内核近似和排名模型对大规模排名问题。

相互竞争的利益

作者宣称没有利益冲突有关的出版。

确认

这项工作主要是由中国自然科学基金会(61125201,61303070,U1435219)。