排序学习方法
引子——Learning to Rank在淘宝中的应用
怎样把用户想要的、好的商品排到网页的前面;怎样调节不同卖家的流量:给质量好的并且价格不便宜的商品更多流量,来引导市场更加规范是淘宝运营要考虑的问题。需要解决的问题其实是很复杂的,比如对商品如何排序、按什么标准排序、排序结果如何判断这一系列问题。
淘宝将商品分为五个等级:bad/fair/good/excellent/prefect。但判断商品的好坏要用到很多特征,比如:商品人气分、卖家分、图像质量、客户反馈分等等,随着时间的变化,新的特征在不断的加入,每个特征是站在不同的角度来描述商品的好坏,这些分数也根据不同的规则形成,而如何对这些分数通过线性加权的方式获得最终的排序也非常的重要。排序学习方法可以用来解决这个问题。
淘宝通过Learning to Rank的方法,通过机器学习模型来自动调整模型参数,但不产生新特征,之后新加入的特征会通过模型来确定它的最优参数。
1. 排序学习方法简述
(1) 什么是排序学习方法?排序学习方法用来做什么的?
排序学习是当前文本检索领域的研究热点,它使用机器学习的方法训练出对数据排序特征的一个排序函数。
排序学习方法将机器学习方法引入到信息检索的文档相关性排序问题中,充分考虑各种排序方法对最终排序结果的影响,通过训练学习排序模型,将各种排序方法视为特征,对文档的相关性做综合的评估。
排序学习是一个信息检索与机器学习相结合的研究领域。它的目标是应用机器学习算法学习排序函数,利用排序函数计算文档和查询的相关性分数,并以此为依据对文档集合进行
排序。
排序学习研究的核心问题是如何构造一个函数或模型反映文档对于查询的相关度。/排序学习研究的核心问题是如何利用训练数据设计合适的排序算法,在此基础上构造更为“精确”的排序模型。(所谓的精确通常需要一个定量的度量,在排序学习领域,主要是通过对测试集上排序结果的评价来实现,常用的标准有MAP和NDCG等)。
本实验的排序学习算法采用线性模型,将各特征赋予权重,以此预测社会网络中结构洞节点新的排序结果。
(2) 排序学习方法分类
按照所使用的机器学习工具不同,可以分为:
a) 基于SVM的排序算法
b) 基于神经网络的排序算法
c) 基于Boosting的排序算法
d) 基于其他机器学习工具(如遗传算法等)的排序算法
按照学习到的排序模型是否为线性分为:
a) 线性排序算法
b) 非线性排序算法
根据训练数据的不同划分为:
a) 基于单个样本的Pointwise算法
b) 基于样本对的Pairwise算法
c) 基于样本队列的Listwise算法
2. 排序学习方法对比
(1) 基于单个样本的Pointwise算法
其基本思想是将训练集中的每个查询-文档对作为一个训练数据,采用某种合适的分类或回归的方法来学习一个排序模型。因为每个文档都被看做一个单独的训练数据,故被称为Pointwise法。训练数据少,算法简单明了。
比较有代表性的算法有:RankProp/Prank/OAP-BPM/EXC/IMC
基于神经网络的排序算法:RankProp
基于感知机的在线排序算法:Prank(Perception Rank)/OAP-BPM
基于SVM的排序算法
Pointwise算法的不足之处:
这种排序学习方法与普通的分类或者回归方法没有本质的不同个,它没有融入排序特性,也没有发挥排序学习方法的最大功效,所以研究者提出了排序学习的另外两类方法。
(2) 基于样本对的Pairwise算法
每个输入数据为一对具有偏序关系(preference relation)的文档,通过对这些数据对的有监督学习来学习一个排序模型,其学习目标是使得结果列表中的错误的偏序对越少越好。
目前公认最为经典的三个Pairwise算法是:
基于SVM的Ranking SVM算法
基于神经网络的RankNet算法
基于Boosting的RankBoost算法
基于Pairwise的排序算法的不足之处:
a) 排序是对某个查询在所有候选文档的排序结果,而不是每对文档之间的偏序关
系
b) Pairwise法假设所有的文档对是独立同分布的,这点与实际并不完全相符
c) 从训练数据本身的构成来说,不同的查询拥有的文档对数目不同,这样不加均
一化地在一起学习,其结果不可避免的向拥有文档对较多的查询偏移
(3) 基于样本队列的Listwise算法
该方法将每个查询的“结果列表”(list)看成一个训练数据,该算法设计关键在于定义一个基于Listwise的损失函数(Loss function)以及选用合适的工具进行学习。大体可以分为两大类:
a) 基于概率模型的列表级排序算法
以Listnet算法为代表,其基本思想是将排序问题看成一个排列概率问题,使用神经网络为学习工具,并使用梯度下降法为优化方法进行求解。
相比起Pairwise法的RankingSVM、RankNet、RankBoost算法,Listnet算法所获得的排序模型不仅是查询级的,而且更关注排名靠前的文档,因此也更满足实际信息检索用户的实际需求。
同样基于概率模型的Listwise算法还有RankCosine、ListMLE,它们与Listnet的不同之处在于它们定义的目标函数不同。
RankCosine的优化目标函数是基于余弦相似度的,它用两个向量分别代表真实结果列表和预测结果列表,并用两个向量之间的余弦角度来度量他们之间的距离;ListMLE说定义的目标函数则是基于极大似然估计的。
ListMLE算法是一种基于Luce模型的排序算法,虽然ListMLE算法后于ListNet算法出现,但从性能上看并不优于ListNet。
b) 基于直接优化评估标准的排序算法
针对Pairwise算法“优化目标和评价目标的不一致性”,即算法的学习目标为“最小化错误对“而学习后的评价标准却为MAP、NDCG等,但是结果通常是错误对越少MAP值却变得不好,因此提出了”直接优化评估标准“的排序算法。
该算法的基本思想是:首先定义一个面向某具体评估标准(MAP或NDCG等)的学习目标,然后选择合适的机器工具和优化算法进行求解,在此基础上构造更符合用户检索需要的排序模型。
该方法的缺点:
需要选取合适的目标来代替原有的“非光滑”的优化目标
难以选取合适的优化算法进行求解
3. ListNet方法
(1)ListNet算法步骤:
输入:训练集 ? ? ? ? 迭代次数T,学习步长? ?,?? , ?,?? , ?,?? …… ?,?? ,
输出: ?
for t=1 to T do:
for i=1 to m do :
的初始值下,代入线性神经网络模型中根据排序函数计算 a)输入数据,在 ?
出得分列表
的梯度(gradient)?? b)用梯度下降神经网络算法,计算出 ?
= ????? 更新 c)通过公式 ?′??
end for
end for
(2)梯度下降法:
输入: ??,??,……?? ,真实值 ??,??,……?? ,学习步长?
输出:假设函数h(?)
?损失函数:J(?)=? ??=?[?? ?? ???] ?对?赋初值,初值可以是随机的,也可以是一个全零的向量
对损失函数中?求偏导
改变?的值,使得J(?)按梯度下降的方向进行减少,?′=?-?*(??? ? )
求得 min J(?)
(3)ListNet方法的损失函数
ListNet方法最早将Luce模型引入到Listwise方法中,它所采用的机器学习方法为神经网络模型。
什么是Luce模型? 通过Luce模型,可以将任意一种排列方式表示成一个概率值,假设有一系列对象标识为1,2,……,n,π为这些对象的一种排列方式,而Ωn为所有可能的对象的排列方式。排序函数给每个对象打出排序后的得分,分数集合表示为s={s1,s2,s3,……,sn},则给这些对象打分的排序方式π的概率可以定义为: ?Ps(π)= nj=1 Φ(sπ j )k=jΦ(sπ k ),
Φ()是严格递增的正函数,实际应用过程中一般用exp()函数来表示
应用Luce模型,能够将一个序列的排序方式表示成一个单一的概率值,是因为它有以下优秀的性质:
a) 所有可能的排序方式其概率和等于1
b) 基于排序函数的任意排序列表,若交换较高得分的对象与较低得分的对象位置,将
得到一个较低的概率值
c) 对于一个给定的排序函数,基于该函数有最高的排列概率值,而逆序的排序列表则
为最低概率值
对于一组排序对象,可以根据对象的评分函数应用Luce模型得到所有排列方式的概率值,从而得到每种评分函数的排列概率分布。这里的评分函数有两种,一种是相关性判断条件,另一种是排序函数,可以用Luce模型对这两种评分函数分别获得一个序列的概率分布,应用交叉熵分量这两个概率分布的相似性进而构造损失函数。该思想就是ListNet方法实现的基础,损失函数表示为:
L y.zqq =Φ(yπ j )Φ(zπ j )nn? q∈Q π∈Ω( j=1 )log( j=1 ) Φ(y)Φ(z) πkπkk=jk=j
Q为训练集中所有查询,Ω为查询所对应的文档列表所有的排列方式,y为相关性判断条件,z为排序函数,n表示序列中对象的个数,k/j均指序列中对象的位置。
该损失函数的特点是连续可微,并且是凸函数,误差损失在0-1之间。尽管listwise损失函数有以上优点,但是计算量成为该算法的致命缺点,按照上述损失函数进行迭代算计算的整体时间复杂度则为O(n*n!),而n如果超过1000,计算量都非常大,所以要采取办法简化计算,优化算法。
前k项概率(k<<n)就是用来解决这个问题的,其核心思想可以解释为用随机序列的前k项排列概率来近似代替原有整个序列的概率,虽然牺牲了一定的准确度,但是有效的节省了运算时间。
在社会网络中挖掘结构洞节点对应着节点的排序问题,那么我们需要得到的一个排序函数h,产生一个得分列表z,那么前k项概率公式可以表示为: θ
kexp(hθ(xj))
Pz(h)= θ k=jhkθj=1
应用前k项概率估计序列概率,并使用交叉熵表示损失函数,则损失函数可以表示为:
L y,z h =? Py?log(Pz(h)) θkθ
ListNet采用梯度下降神经网络算法,损失函数相对于θ的梯度可以进行计算:
?L(y,z h )?Pz(h)
?θ=θ
?θ=? kθPy
Pz(h)θ?θ
虽然通过前k项概率优化了计算时间,但仍要计算n!/(n-k)!次,为了进一步提高计算效率,将k值设为1,这样可以更大幅度的减少该算法的计算量,此时,算法的时复杂度则可以降低到O(n)。则上式可以得到:
n
?θ= Py
j=1?h(xj)θ?θ+1
(h xj )j=1exp?θn(h xj )? [exp?j=1θ?h(xj)θ?θ]
从而可以得到:θ′=θ?η??θ
线性神经网络模型最后的结果是:h xj = θ,x θ
4. 排序学习方法的评估
用学习得到的排序模型对文档进行排序,然后用验证方法来验证处排序结果跟原先的相关度判断之间的不同。最后用在测试样本集上所有查询的平均值来验证排序模型的性能。 现今主要的评价标准主要有以下几种类型:
(1) MAP(Mean Average Precision)
对所有查询的AP求宏平均。AP即是平均准确率,对不同召回率点上的准确率进行平均。
a) 未插值的AP:某个查询共有6个相关结果,某系统排序返回了5篇相关文档,
其位置分别为第1、第2、第5、第10、第20位,则AP=
(1/1+2/2+3/5+4/10+5/20+0)/6
b) 插值的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. 多个查询下的准确率/查全率曲线,可以通过计算其平均查准率得到,公式如下:
?
? = ???=?
?=???(?) P(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)
第二篇:软件技术学习方法总结
软件技术专业学习方法总结
我们想要学好软件技术的话,一定要培养自己学习软件的兴趣。兴趣是激发我们学习积极性的动力,也是激发创造力的必要条件。因此,在计算机教学过程中,我们学生一定要让自己对软件开发产生的学习兴趣,只有对自己所学的知识真正热爱,我们才能学好这一科目。这就要求我们学会生动活泼的学习各种软件知识,这是激发我们学习兴趣的关键因素。我们可以从我们平时感兴趣的话题入手,如游戏、网页等,通过对其编程思想的分析提高自己的学习兴趣。
我们很多学生都带了笔记本电脑到学校。这就给我们课外的学习和锻炼自己的编程能力给予了极大的方便。我们在下课后和睡觉前,完全可以自己多根据书上的内容在自己的电脑上多多练习、多多锻炼。只有这样,我们才能让自己实现学有所值,才能让自己获得必需的操作知识,让自己在各个方面各个层次都能够得到发展并且不断提高自己、充实自己。在课堂上我们要主动参与老师的互动、乐于探究问题、勤于动手编写代码,培养自己搜集和处理信息的能力、获取新知识的能力、分析和解决问题的能
力以及交流与合作的能力。这是非常重要的。 我们在上机过程中会产生各种各样的学习问题,有的有些深度,有的非常容易。我们学生很容易失去兴趣和信心。打个比方来说,我们如果对学习内容感到明显懂了或者学通了,并且有了学习成果,就对自己有了自信心,对学习的兴趣也就随之萌发、
高涨起来。所以我们如果遇到有困难的地方,一定要向老师提问,只有搞懂自己不懂的地方,才会对自己产生自信,这样有利于我们学好自己专业的知识。
当然,在上课时如果老师师先提出一些与教学内容有关的实际问题,让我们想想如何来解决,而我们有感觉有点困难的话,不要急着向老师问,可以自己先试着解决。如在教数据库时,老师问我们“如何将全班同学的学号、姓名、性别、家庭地址、家庭电话等信息以数据库形式存放起来,供查询等使用?”,然后引出建立数据库的方法,我们可以在上机时建立这个数据库,并在以后学习中经常引用这个数据库。又如在学习数据库的命令文件时,针对老师事先设计好的一个界面良好、简单实用的程序并上课时运行给我们看后,让自己想想,如何才能来编程实现,并告诉自己这个程序设计一点也不难,只要学习老师教的几个命令后就可以自己完成,这样可以激发自己的求知欲望,让自己更好的学习这节课所教的内容。
老师教我们的教学方法一般是启发式教学,这是指老师在教学工作中依据教材的内在联系和学生的认识规律,由浅入深、由近及远、由表及里、由易到难的逐步提出问题,解决问题,引导学生主动、积极、自觉地掌握知识的教学方法。所以我们可以根据老师所讲的内容让自己思考问题的答案及解决问题的方法。这种教学方法,强调老师是主导,教学过程要由教师来组织,我们学生是学习的主体,所以我们要积极思维,调动自己在学习上的积极
性,正确的理解、系统的掌握所学的知识。我们可以通过老师这种教学方法突出重点、分散难点、抓住关键,好好学习。对于学习比较吃力的同学,可以一点一点逐步慢慢来学,跟上老师节奏,不要想着一步登天。有助于增强自己的逻辑思维能力,提高自己对问题的分析和解决能力。我们一定要善于抓住问题的本质。 还有些问题,需要相互比较才行,不然不容易注意到它们之间的差别,通过比较,才进一步认识,从而建立正确的概念,真正的攻克相似的难题。
以上就是我对软件技术专业学习方法的总结,希望能对大家有一点点的帮助,谢谢老师同学的阅读。