Learning to ranking简介
目录
5.1.3 基于Ordinal Regressioin 的排序学习...
10
1前言
在传统的搜索引擎的ranking策略中，一般会包含若干子策略，子策略通过若干种方式组合成更大的策略一起发挥作用。策略的组合方式以及参数一般采取人工或者半人工的方式确定。然而随着策略的逐步细化，传统的组合方式变得越来越困难。于是Learning to Rank（LTR）就被引入了进来。LTR的核心思想是用机器学习来解决排序的问题。目前被广泛运用在信息检索（IR）、自然语言处理（NLP）和 数据挖掘（DM） 中。 LTR是监督学习，建好模型之后，需要用训练数据集的人工标注标签或其他相关性定义来训练。
2 LTR基本流程
图1 文档检索系统的基本流程
首先，介绍下信息检索系统（如搜索引擎）的一个基本流程。如图1 所示，对于一个查询任务q，搜索引擎要从海量的数据库中检索出，与当前查询q相关的所有文档D，并且按照相关性对这些文档进行排序。文档显示的位置对于用户的点击率是有很大影响的，文档越靠前，用户点击概率越高。所以要求搜索引擎尽可能的把最相关的文档排在前面，不相关的排在后面。
图2 学习排序基本架构
图2，是学习排序在信息检索系统中的基本架构。首先，通过人工标注或者搜索日记获取一批训练数据1。训练集D中q表示查询，x表示查询q与文档d构成的特征向量，y表示当前查询q文档d对的相关性（可以是1-5，也可以是：0-1）。然后通过选取合适的learning to ranking 算法在训练集上进行训练，得到训练好的模型 h。最后对于一个新的查询q-文档d对，输入其相应的特征向量x，模型h给出其相应的预测值h(x)。
其中，特征向量的元素可以分为3大类：
1、 Doc 本身的特征：pageRank, 点击次数，浏览排名，内容丰富度等等。
2、 Query-Doc的特征：文本相似性，query中的词在Doc中出现的次数等。
3、 Query的特征：如query所包含的词条数量。
公共的数据集：
1． LETOR, http://research.microsoft.com/en-us/um/beijing/projects/letor/
2． Microsoft Learningto Rank Dataset, http://research.microsoft.com/en-us/projects/mslr/
3． Yahoo Learning toRank Challenge, http://webscope.sandbox.yahoo.com/
3 模型训练
3.1排序类型
LTR的学习方法分为Pointwise、Pairwise和Listwise三类。Pointwise和pairwise把排序问题转换成回归、分类或者有序分类问题。Lisewise把查询q下整个搜索结果作为一个训练的实例。3种方法的区别主要体现在损失函数（Loss function）上。
3.1.1 Pointwise
Pointwise 模型把排序问题转化为单结果的回归、分类或者有序分类的问题。
loss function 形式为：
基本特征:
图3 Pointwise学习方式的基本特征（来自 (Li, 2011)）
现有的算法：
Pranking (NIPS 2002), OAP-BPM (EMCL2003), Ranking with Large Margin Principles (NIPS 2002), Constraint OrdinalRegression (ICML 2005)。
基本特点：
Pointwise方法仅仅使用传统的分类，回归或者Ordinal Regression方法来对给定查询下单个文档的相关度进行建模。这种方法没有考虑到排序的一些特征，比如文档之间的排序结果针对的是给定查询下的文档集合，而Pointwise方法仅仅考虑单个文档的绝对相关度；另外，在排序中，排在最前的几个文档对排序效果的影响非常重要，Pointwise没有考虑这方面的影响。
3.1.2 Pairwise
Pairwise模型把排序问题转化为结果对的回归、分类或者有序分类的问题。
其loss function 形式为：
其基本特征：
图4 Pairwise学习方式的基本特征（来自 (Li, 2011)）
现有的算法：
Learning to Retrieve Information(SCC 1995), Learning to Order Things (NIPS 1998), Ranking SVM (ICANN 1999),RankBoost (JMLR 2003), LDM (SIGIR 2005), RankNet (ICML 2005), Frank (SIGIR2007), MHR(SIGIR 2007), Round Robin Ranking (ECML 2003), GBRank
(SIGIR 2007),QBRank (NIPS 2007), MPRank (ICML 2007), IRSVM (SIGIR 2006)
基本特点：
相比于Pointwise方法，Pairwise方法通过考虑两两文档之间的相对相关度来进行排序，有一定的进步。但是，Pairwise使用的这种基于两两文档之间相对相关度的损失函数，和真正衡量排序效果的一些指标之间，可能存在很大的不同，有时甚至是负相关。
另外，有的Pairwise方法没有考虑到排序结果前几名对整个排序的重要性，也没有考虑不同查询对应的文档集合的大小对查询结果的影响(但是有的Pairwise方法对这些进行了改进，比如IR SVM就是对Ranking SVM针对以上缺点进行改进得到的算法)。
3.1.3 Listwise
Listwise模型与Pointwise和Pairwise方法不同，直接考虑给定查询下的集合的整体序列，直接优化模型输出的文档序列，使得其尽可能的接近真实文档序列。
其Loss Function：
其基本特征：
图5 Listwise学习方式的基本特征（来自 (Li, 2011)）
现有的算法：
LambdaRank (NIPS 2006), AdaRank(SIGIR 2007), SVM-MAP (SIGIR 2007), SoftRank (LR4IR 2007), GPRank (LR4IR 2007),CCA (SIGIR 2007), RankCosine (IP&M 2007), ListNet (ICML 2007), ListMLE(ICML 2008)
基本特点：
相比于Pointwise和Pairwise方法，Listwise方法直接优化给定查询下，整个文档集合的序列，所以比较好的解决了克服了以上算法的缺陷。Listwise方法中的LambdaMART(是对RankNet和LambdaRank的改进)在Yahoo Learning to Rank Challenge表现出最好的性能。
3.2 排序算法分类
|
现有排序算法分类 |
||||
|
Learning Method |
SVM |
Boosting |
Neural Net |
Others |
|
Pointwise |
OC SVM |
McRank |
|
Prank Subset Ranking |
|
Pairwise |
Ranking SVM IR SVM |
RankBoost GBRank LambdaMART |
RankNet Frank LambdaRank |
|
|
Listwise |
SVM PermuRank |
AdaRank |
ListNet ListMLE |
SoftRank AppRank |
4评价指标
对于查询qi和相应的文档集合Di,假设 为文档集合Di的排序序列，yi为文档集合Di的相关度（或者分数）。
4.1 NDCG
NDCG:全称NormalizedDiscounted Cumulative Gain.
首先介绍下DCG，其定义如下：
其中G(j)为增益（Gain）函数，表示第j个文档在被给予评分yij之后所贡献的分数增益。
定义为：
而为位置折算函数（Discounted function），因为在不同位置的增益应该是不同的，函数给结果按照位置赋予一个权重，定义如下：
其中为所有排序中最好的排序序列（最好的不唯一），及所有文档按照相关性从高到低排列时值最高。
样例：
图6 NDCG计算样例
4.2 MAP
MAP是另外一种在IR中经常用到的指标。它假设query-Doc对的相关度只有两种情况，一种是相关，用1表示；另外一种是不相关，用0表示。对于查询qi，其平均准确率定义为：
其中,的定义如下：
其中p(j)表示对于查询qi而言，直到文档qi,j的准确率。
MAP就是对所有的查询q求平均值。
样例：
图7 MAP计算样例
4.3 MRR
MRR：Mean Reciprocal Rank:是把标准答案在被评价系统给出结果中的排序取倒数作为它的准确度，再对所有的问题取平均。相对简单。
如下表中，对于查询q放回一个results列表：
(黑体字为返回结果中最匹配的一项)
可计算这个系统的MRR值为（1/3+1/2+1）/3=11/18=0.61
5 Pointwise方式
首先介绍Pointwise学习排序的经典算法，然后介绍局限性。
Pointwise的基本思想是以最直接的方式应用已有的学习方法到排序学习上面。它们直接预测文档的相关性上具体的值，而这个值并不是真正需要的，排序中只需要知道每个文档的具体位置就行。
5.1 Pointwise学习排序
5.1.1基于回归的排序学习
Cossock and Zhang[1] 把学习排序问题看作基本的回归问题。如下图所示：
其目标为学习得到一个函数f(x)，定义的loss function：
5.1.2 基于分类的排序学习
与把排序问题简化为回归问题类似，一些研究者把排序问题转化为二元分类或多元分类问题。
Nallapati [2]把SVM分类器应用于二元排序问题，它使用hinge Loss作为损失函数。
而 Gey [3]
应用logistic regression
到排序问题。
Li etal.[4] 使用提升树算法进行多元分类。其loss function
为：
其中I是一个指示函数。而P为预测文档j属于k类的概率值。F为要学习的目标函数
5.1.3 基于OrdinalRegressioin 的排序学习
基于ordinal regression的排序学习考虑到了各个文档的有序关系。假设有K种序列，那么算法的目标就是去找到一个scoring
函数 f ,
使用k-1个阈值来划分k个区间。在这类算法中比较经典的两个算法，Prank[6]
和OC SVM [5]。其中Prank [6]算法示意图如下：
其使用感知器寻找能把k个类别划分的k-1个超平面。这k-1个超平面就是我们要学习的模型f。而OC
SVM[5]类似，只是它使用的是SVM技术去学习这K-1个最大间隔的超平面，其示意图如下：
5.2 Pointwise方式的缺点
首先，在Pointwise排序模型的学习中，没出输入的是一个文档，而文档之间的相对顺序不能自然的在其学习过程中考虑进来。而排序问题更加关注与其排序位置，而不是其准确的相关度值Liu el at[7]。
再者，在排序的评价指标有两个本质属性没有在Pointwise方式中的得以考虑：
1、 每个文档在排序中的位置在所有的Pointwise损失函数中都没有考虑进去。所以在其学习过程中会无意识的提高不相关的文档的作用。
2、 它假设相关度是查询无关的。只要查询q和文档d对的相关度相同，那么他们就被划分到同一个级别中，属于同一类。然而实际上，相关度的相对性是和查询相关的，比如一个常见的查询它会有很多相关的文档，该查询和它相关性相对靠后的文档的label标注级别时可能会比一个稀有的查询和它为数不多的高度相关文档的label标准级别更高。这样就导致训练样本的不一致，并且对于预测为同一label级别的文档之间也无法相对排序。
References
[1] Cossock D, Zhang T. Subset ranking usingregression[M]//Learning theory. Springer Berlin Heidelberg, 2006: 605-619.
[2] Nallapati R. Discriminative models forinformation retrieval[C]//Proceedings of the 27th annual international ACMSIGIR conference on Research and development in information retrieval. ACM,2004: 64-71.
[3] Gey F C. Inferring probability of relevanceusing the method of logistic regression[C]//SIGIR’94. Springer London, 1994:222-231.
[4] Li P, Wu Q, Burges C J. Mcrank: Learning torank using multiple classification and gradient boosting[C]//Advances in neuralinformation processing systems. 2007: 897-904.
[5] Shashua A, Levin A. Ranking with largemargin principle: Two approaches[C]//Advances in neural information processingsystems. 2002: 937-944.
[6] Crammer K, Singer Y. Pranking withranking[C]//NIPS. 2001, 14: 641-647.
[7] Liu T Y. Learning to rank for informationretrieval[J]. Foundations and Trends in Information Retrieval, 2009, 3(3):225-331.
6 Pairwise方式
Pairwise学习排序方式是目前比较流行的方法，它们不再注重准确预测每个文档的真实相关度了，而注重两个文档的在排序中的相对顺序。这样，比起Pointwise方式更加接近排序了。
在Pairwise方式中，将排序问题转化为两个文档对之间的二元分类问题，如判断那个文档更相关。举一个比较极端的例子，如果任意两个文档对之间的相对位置都正确，那么所有的文档之间的位置都是正确的。其loss function的目标为最小化误分类文档对的位置。注意这里的分类和Pointwise方法有很多不同，其对象为文档对，而不是单个文档。
在Pairwise方式中有很多算法，他们分别基于神经网络[1]，感知器[2,3]，Boosting[4]，SVM[5,6]等等, 我们这里只介绍几种有代表性的算法。
6.1典型算法
6.1.1 Ranking SVM
Ranking svm 是由Herbrich et al.[5] 提出来的。其基本思想是把ranking问题转化为文档对的分类问题，并且使用SVM技术进行学习。
使用X表示特征空间，x表示某一个具体查询-文档对的特征, f为一个scoringfunction（打分函数）： 。给点两个查询-文档对xi和xj，如果f(xi)>f(xj)则xi要排在xj的前面。用符号表示为： 。
打分函数f可以为任意函数。简单起见，首先看下线性函数:
这时有：
接下来，对于任意两个文档xi和xj,可以
References
[1] Burges C, Shaked T, Renshaw E, et al. Learning to rank usinggradient descent[C]//Proceedings of the 22nd international conference onMachine learning. ACM, 2005: 89-96.
[2] Gao J, Qi H, Xia X, et al. Lineardiscriminant model for information retrieval[C]//Proceedings of the 28th annualinternational ACM SIGIR conference on Research and development in informationretrieval. ACM, 2005: 290-297.
[3] Shen L, Joshi A K. Ranking and rerankingwith perceptron[J]. Machine Learning, 2005, 60(1-3): 73-96.
[4] Freund Y, Iyer R, Schapire R E, et al. Anefficient boosting algorithm for combining preferences[J]. The Journal ofmachine learning research, 2003, 4: 933-969.
[5] Herbrich R, Graepel T, Obermayer K.
Largemargin rank boundaries for ordinal regression[J]. Advances in neuralinformation processing systems, 1999: 115-132.
[6]Joachims T. Optimizing search engines usingclickthrough data[C]//Proceedings of the eighth ACM SIGKDD international conferenceon Knowledge discovery and data mining. ACM, 2002: 133-142.
7 Listwise方式
8 CTR中常见的Loss function
本人小网站链接：http://www.cytzchina.com/