排序学习方法总结.docx

《排序学习方法总结.docx》由会员分享，可在线阅读，更多相关《排序学习方法总结.docx（9页珍藏版）》请在一课资料网上搜索。

1、排序学习方法引子Learning to Rank在淘宝中的应用怎样把用户想要的、好的商品排到网页的前面；怎样调节不同卖家的流量：给质量好的并且价格不便宜的商品更多流量，来引导市场更加规范是淘宝运营要考虑的问题。需要解决的问题其实是很复杂的，比如对商品如何排序、按什么标准排序、排序结果如何判断这一系列问题。淘宝将商品分为五个等级：bad/fair/good/excellent/prefect。但判断商品的好坏要用到很多特征，比如：商品人气分、卖家分、图像质量、客户反馈分等等，随着时间的变化，新的特征在不断的加入，每个特征是站在不同的角度来描述商品的好坏，这些分数也根据不同的规则形成，而如何对这些

2、分数通过线性加权的方式获得最终的排序也非常的重要。排序学习方法可以用来解决这个问题。淘宝通过Learning to Rank的方法，通过机器学习模型来自动调整模型参数，但不产生新特征，之后新加入的特征会通过模型来确定它的最优参数。1. 排序学习方法简述（1） 什么是排序学习方法？排序学习方法用来做什么的？排序学习是当前文本检索领域的研究热点，它使用机器学习的方法训练出对数据排序特征的一个排序函数。排序学习方法将机器学习方法引入到信息检索的文档相关性排序问题中，充分考虑各种排序方法对最终排序结果的影响，通过训练学习排序模型，将各种排序方法视为特征，对文档的相关性做综合的评估。排序学习是一个信息检

3、索与机器学习相结合的研究领域。它的目标是应用机器学习算法学习排序函数，利用排序函数计算文档和查询的相关性分数，并以此为依据对文档集合进行排序。排序学习研究的核心问题是如何构造一个函数或模型反映文档对于查询的相关度。/排序学习研究的核心问题是如何利用训练数据设计合适的排序算法，在此基础上构造更为“精确”的排序模型。（所谓的精确通常需要一个定量的度量，在排序学习领域，主要是通过对测试集上排序结果的评价来实现，常用的标准有MAP和NDCG等）。本实验的排序学习算法采用线性模型，将各特征赋予权重，以此预测社会网络中结构洞节点新的排序结果。（2） 排序学习方法分类按照所使用的机器学习工具不同，可以分为：

4、a) 基于SVM的排序算法b) 基于神经网络的排序算法c) 基于Boosting的排序算法d) 基于其他机器学习工具（如遗传算法等）的排序算法按照学习到的排序模型是否为线性分为：a) 线性排序算法b) 非线性排序算法根据训练数据的不同划分为：a) 基于单个样本的Pointwise算法b) 基于样本对的Pairwise算法c) 基于样本队列的Listwise算法2. 排序学习方法对比（1） 基于单个样本的Pointwise算法其基本思想是将训练集中的每个查询-文档对作为一个训练数据，采用某种合适的分类或回归的方法来学习一个排序模型。因为每个文档都被看做一个单独的训练数据，故被称为Pointwis

5、e法。训练数据少，算法简单明了。比较有代表性的算法有：RankProp/Prank/OAP-BPM/EXC/IMC基于神经网络的排序算法：RankProp基于感知机的在线排序算法：Prank(Perception Rank)/OAP-BPM基于SVM的排序算法Pointwise算法的不足之处：这种排序学习方法与普通的分类或者回归方法没有本质的不同个，它没有融入排序特性，也没有发挥排序学习方法的最大功效，所以研究者提出了排序学习的另外两类方法。（2） 基于样本对的Pairwise算法每个输入数据为一对具有偏序关系（preference relation）的文档，通过对这些数据对的有监督学习来学习

6、一个排序模型，其学习目标是使得结果列表中的错误的偏序对越少越好。目前公认最为经典的三个Pairwise算法是：基于SVM的Ranking SVM算法基于神经网络的RankNet算法基于Boosting的RankBoost算法基于Pairwise的排序算法的不足之处：a) 排序是对某个查询在所有候选文档的排序结果，而不是每对文档之间的偏序关系b) Pairwise法假设所有的文档对是独立同分布的，这点与实际并不完全相符c) 从训练数据本身的构成来说，不同的查询拥有的文档对数目不同，这样不加均一化地在一起学习，其结果不可避免的向拥有文档对较多的查询偏移（3） 基于样本队列的Listwise算法该方

7、法将每个查询的“结果列表”（list）看成一个训练数据，该算法设计关键在于定义一个基于Listwise的损失函数（Loss function）以及选用合适的工具进行学习。大体可以分为两大类：a) 基于概率模型的列表级排序算法以Listnet算法为代表，其基本思想是将排序问题看成一个排列概率问题，使用神经网络为学习工具，并使用梯度下降法为优化方法进行求解。相比起Pairwise法的RankingSVM、RankNet、RankBoost算法，Listnet算法所获得的排序模型不仅是查询级的，而且更关注排名靠前的文档，因此也更满足实际信息检索用户的实际需求。同样基于概率模型的Listwise算法还

8、有RankCosine、ListMLE，它们与Listnet的不同之处在于它们定义的目标函数不同。RankCosine的优化目标函数是基于余弦相似度的，它用两个向量分别代表真实结果列表和预测结果列表，并用两个向量之间的余弦角度来度量他们之间的距离；ListMLE说定义的目标函数则是基于极大似然估计的。ListMLE算法是一种基于Luce模型的排序算法，虽然ListMLE算法后于ListNet算法出现，但从性能上看并不优于ListNet。b) 基于直接优化评估标准的排序算法针对Pairwise算法“优化目标和评价目标的不一致性”，即算法的学习目标为“最小化错误对“而学习后的评价标准却为MAP、N

9、DCG等，但是结果通常是错误对越少MAP值却变得不好，因此提出了”直接优化评估标准“的排序算法。该算法的基本思想是：首先定义一个面向某具体评估标准（MAP或NDCG等）的学习目标，然后选择合适的机器工具和优化算法进行求解，在此基础上构造更符合用户检索需要的排序模型。该方法的缺点：需要选取合适的目标来代替原有的“非光滑”的优化目标难以选取合适的优化算法进行求解3. ListNet方法（1）ListNet算法步骤：输入：训练集x1,y1，x2,y2，x3,y3xn,yn，迭代次数T，学习步长输出：for t=1 to T do:for i=1 to m do : a)输入数据，在的初始值下，代入线

10、性神经网络模型中根据排序函数计算出得分列表 b)用梯度下降神经网络算法，计算出的梯度（gradient）c)通过公式=-*更新end forend for（2）梯度下降法：输入：x1，x2，xn，真实值y1，y2，yn，学习步长输出：假设函数h()损失函数：J()=12i=1nhxi-yi2对赋初值，初值可以是随机的，也可以是一个全零的向量对损失函数中求偏导改变的值，使得J()按梯度下降的方向进行减少，=-*（J）求得 min J()（3）ListNet方法的损失函数ListNet方法最早将Luce模型引入到Listwise方法中，它所采用的机器学习方法为神经网络模型。 什么是Luce模型？

11、通过Luce模型，可以将任意一种排列方式表示成一个概率值，假设有一系列对象标识为1,2，n，为这些对象的一种排列方式，而n为所有可能的对象的排列方式。排序函数给每个对象打出排序后的得分，分数集合表示为s=s1，s2，s3，sn，则给这些对象打分的排序方式的概率可以定义为：Ps()=j=1n(sj)k=jn(sk)，()是严格递增的正函数，实际应用过程中一般用exp()函数来表示应用Luce模型，能够将一个序列的排序方式表示成一个单一的概率值，是因为它有以下优秀的性质：a) 所有可能的排序方式其概率和等于1b) 基于排序函数的任意排序列表，若交换较高得分的对象与较低得分的对象位置，将得到一个较低

12、的概率值c) 对于一个给定的排序函数，基于该函数有最高的排列概率值，而逆序的排序列表则为最低概率值对于一组排序对象，可以根据对象的评分函数应用Luce模型得到所有排列方式的概率值，从而得到每种评分函数的排列概率分布。这里的评分函数有两种，一种是相关性判断条件，另一种是排序函数，可以用Luce模型对这两种评分函数分别获得一个序列的概率分布，应用交叉熵分量这两个概率分布的相似性进而构造损失函数。该思想就是ListNet方法实现的基础，损失函数表示为：Lyq.zq=-qQ(j=1n(yj)k=jn(yk)log(j=1n(zj)k=jn(zk) Q为训练集中所有查询，为查询所对应的文档列表所有的排列

13、方式，y为相关性判断条件，z为排序函数，n表示序列中对象的个数，k/j均指序列中对象的位置。该损失函数的特点是连续可微，并且是凸函数，误差损失在0-1之间。尽管listwise损失函数有以上优点，但是计算量成为该算法的致命缺点，按照上述损失函数进行迭代算计算的整体时间复杂度则为O（n*n!），而n如果超过1000，计算量都非常大，所以要采取办法简化计算，优化算法。前k项概率（kn）就是用来解决这个问题的，其核心思想可以解释为用随机序列的前k项排列概率来近似代替原有整个序列的概率，虽然牺牲了一定的准确度，但是有效的节省了运算时间。在社会网络中挖掘结构洞节点对应着节点的排序问题，那么我们需要得到的

14、一个排序函数h，产生一个得分列表z，那么前k项概率公式可以表示为：Pz(h)=j=1kexp(h(xj)k=jnexp(h(xk)应用前k项概率估计序列概率，并使用交叉熵表示损失函数，则损失函数可以表示为：Ly,zh=-kPy*log(Pz(h)ListNet采用梯度下降神经网络算法，损失函数相对于的梯度可以进行计算：=L(y,zh)=-kPz(h)PyPz(h) 虽然通过前k项概率优化了计算时间，但仍要计算n!/(n-k)!次，为了进一步提高计算效率，将k值设为1，这样可以更大幅度的减少该算法的计算量，此时，算法的时复杂度则可以降低到O(n)。则上式可以得到：=j=1nPyh(xj)+1j=

15、1nexp(hxj)j=1nexp(hxj)*h(xj)从而可以得到：=-*线性神经网络模型最后的结果是：hxj=，x4. 排序学习方法的评估用学习得到的排序模型对文档进行排序，然后用验证方法来验证处排序结果跟原先的相关度判断之间的不同。最后用在测试样本集上所有查询的平均值来验证排序模型的性能。现今主要的评价标准主要有以下几种类型：（1） MAP（Mean Average Precision）对所有查询的AP求宏平均。AP即是平均准确率，对不同召回率点上的准确率进行平均。a) 未插值的AP：某个查询共有6个相关结果，某系统排序返回了5篇相关文档，其位置分别为第1、第2、第5、第10、第20位，

16、则AP=（1/1+2/2+3/5+4/10+5/20+0）/6b) 插值的AP：在召回率分别为0,0.1,0.2，1.0的十一个点上的正确率值求平均c) 只对返回的相关文档进行计算AP，如a)中的例子，AP=（1/1+2/2+3/5+4/10+5/20）/5，倾向那些快速返回结果的系统，没有考虑召回率而MAP是反映系统在全部相关文档上性能的单值指标，系统检索出来的相关文档越靠前，rank越高，MAP就可能越高，如果系统更没有返回相关文档，则准确率默认为0.多个查询下的准确率/查全率曲线，可以通过计算其平均查准率得到，公式如下：MAP=Pr=i=1NPi(r)NP(r)指查全率为r时的平均查准率，Pi(r)只查全率为r时的第i个查询的查准率。例：假设有两个主题，主题1有4个相关网页，主题2有5个相关网页。某系统对于主题1检索出4个相关网页，其rank分别为1, 2, 4, 7；对于主题2检索出3个相关网页，其rank分别为1,3,5。对于主题1，平均准确率为(1/1+2/2+3/4+4/7)/4=0.83。对于主题2，平均准确率为(1/1+2/3+3/5+0+0)/5=0.45。则MAP= (0.83+0.45)/2=0.64。”（2） NDCG（Normalized Discounted Cumulative Gain）