Learning to Rank简介

　　Rank一直是信息检索的核心问题，在文档检索，协同过滤，情感分析等领域都有着广泛的应用。传统的排序模型靠人工拟合排序公式，参数少，简单易调，但是能利用的特征较少，随着数据量的剧增，无法得到理想的排序性能，如果参数较多，会使得经验方法调参特别困难，也无法得到理想的排序模型。近些年，由于数据量的增加，排序需要考虑的因素也越来越多，而机器学习更适合采用很多特征来进行公式模拟，所以，利用机器学习技术来进行排序就应运而生，这就是LTR(Lerning to Rank)。

1：传统排序模型

　　传统的排序模型考虑的因素不多，主要是查询和文档的相关性，或者是网页的权威程度，利用词频，逆文档频率，文档长度等几个因子来人工模拟排序公式，主要模型大致分为两类：相关度排序模型和重要性排序模型。

　　1.1：RRM(Relevance Ranking Model<相关度排序模型>)

　　　　相关度排序模型通过不断的实验为排序公式确定最佳的参数组合，来为查询和文档的相关性进行进行打分，以此来为文档进行排序，常见模型包括：布尔模型(Boolean Model 简称BM)，向量空间模型(Vector Space Model 简称VSM)，隐语义分析(Latent Semantic Analysis 简称LSA)，BM25。

　　1.2：IRM(Importance Ranking Model<重要性排序模型>)

　　　　重要性排序模型不考虑查询，主要是基于文档之间的图模型来判断文档的重要性，以此来为文档进行排序，常见模型包括：PageRank，HITS，HillTop，TrustRank。

2：LTR

　　对于传统的排序模型，单个模型往往只能考虑某一个方面(相关度或者重要性)，所以只用当个模型达不到要求，搜索引擎通常会组合多种排序模型来进行排序，但是，如何组合多个排序模型来形成一个新的排序模型，以及如何调节这些参数，将会是一个巨大的挑战，使用机器学习的方法，我们可以把各个现有排序模型的输出作为特征，然后训练一个新的模型，并自动学得这个新模型的参数，从而很方便的可以组合多个现有模型来生成新的排序模型，Learning to rank是采用机器学习的方法，通过训练模型来解决排序问题。

　　需要注意的是，排序问题最关注的的是各个documents之间的相对顺序问题，而不是各个documents的预测分最准确。

　　2.1：Feature exetraction

　　检索结果的排序取决于一系列特征，与文本分类不同，LTR考虑的是给定query的document集合的排序，所以，LTR用到的特征不仅仅包含document本身的一些特征，也包括document和query之间的相关度，以及document在整个网络中的重要性，大致可以分为两类：

　　1：document本身的一些特征：PageRank，内容丰富度，是否是spam等。

　　2：query-document的特征：相关性，query term在文档中出现的次数等。

　　2.2：Training data

　　LTR的训练数据可以有三种形式：

　　　　1：对于每个query，各个document的绝对相关值。

　　　　2：对于每个query，两两document之间的相对相关值。

　　　　3：对于每个query，所有document的按相关度排序的list。

　　训练数据的获取有三种主要的方法：

　　1，人工标注：首先从搜索引擎的搜索记录中随机抽取一些查询，讲这些查询提交给多个不同的搜索引擎，然后选取各个搜索引擎返回结果的前K个，最后由专业人员来对这些文档按照和query的相关度进行标注。

　　2，从日志中挖掘：搜索引擎都有大量的日志记录用户的行为，我们可以从中提取出LTR的训练数据。Joachims提出了一种很有意思的方法，给定一个query，搜索引擎返回的结果列表为L，用户点击的文档的集合为C，如果一个文档di被点击过，另一个文档dj没有被点击过，并且dj在结果列表中排在di之前，则di>dj就是一条训练记录，亦即训练数据为：{di>dj|di属于C，dj属于L-C，p(dj)<p(di)}，其中p(d)表示文档d在查询结果列表中的位置，越小表示越靠前。

　　3，公共数据集：

　　　　LETOR, http://research.microsoft.com/en-us/um/beijing/projects/letor/

　　　　Microsoft Learning to Rank Dataset, http://research.microsoft.com/en-us/projects/mslr/

　　　　Yahoo Learning to Rank Challenge, http://webscope.sandbox.yahoo.com/

　　2.3：Model training

　　对于每个给定的query-document pair，抽取相应的特征(既包括query和document之间的各种相关度，也包括document本身的特征以及重要性等)，另外通过人工标注或者从日志中挖掘的方法来得到给定查询下文档集合的真是序列，然后我们使用LTR的各种算法来学到一个排序模型，使其输出的文档虚了和真是序列尽可能相似。Learning to Rank是监督学习方法，所以会分为training阶段和testing阶段，如下图所示：

　　2.4：Formulation

　　用通用的公式来表示Learning to Rank算法，loss function为L(F(x)，y)，从而risk function（loss function在X，Y联合分布下的期望值）为：

　　有了training data后，进一步得到empirical risk function：

　　于是，学习问题变成了如何最小化这个empirical risk function。而这个优化问题很难解决，因为loss function不连续。于是可以使用一个方便求解的surrogate function来替换原始loss function，转而优化这个替换函数：

　　替换函数的选择有很多种，根据Learning to Rank的类型不同而有不同的选择：

　　　　1)pointwise loss：例如squared loss等

　　　　2)pairwise loss：例如hinge loss，exponential loss，logistic loss等

　　　　3)listwise loss：

　　2.5：LTR算法分类

　　　　2.5.1：PointWise

　　　　　　PointWise只考虑单个document与给定查询query之间的相关度，常见算法有：PRanking，OAP-BPM，Ranking with Large Margin Principles，McRank，Constraint Ordinal Regression。

　　　　2.5.2：PairWise

　　　　　　PairWise考虑给定查询query下，两个documents的相对相关度，优化的目标是正例与反例之间的序，常见算法有：Learning to Retrieve Information，Learning to Order Things，Ranking SVM，RankBoost，LDM，RankNet，FRank，MHR，Round Robin Ranking，GBRank，QBRank，MPRank，IR-SVM，RankRLS，Ranking Refinement，SSRankBoost，SortNet，MPBoost，GBlend，CRR。

　　　　2.5.3：ListWise

　　　　　　ListWise考虑给定查询query下的文档集合的整体序列，优化的是序的好坏，常见算法有：LambdaRank，LambdaMART，AdaRank，SVM-MAP，SoftRank，GPRank，CCA，RankCosine，ListNet，ListMLE，PermuRank，BoltzRank，BayesRank，NDGG Boost，IntervalRank，ES-Rank。

　　2.6：Evaluation

　　LTR是用机器学习的方法来进行排序，所以评价LTR效果的指标就是评价排序的指标：

　　　　1：WTA(Winners take all)：对于给定的查询q，如果模型返回的结果列表中，第一个文档是相关的，则WTA(q)=1，否则为0.

　　　　2：MRR(Mean Reciprocal Rank)：对于给定查询q，如果第一个相关的文档的位置是R(q)，则MRR(q)=1/R(q).

　　　　3：MAP(Mean Average Precision)：对于每个真实相关的文档d，考虑其在模型排序结果中的位置R(d)，统计该位置之前的文档集合的分类准确率，取所有这些准确率的平均值，在MAP中，对query-doc pair的相关性判断只有两档：1和0，对于一个query，其AP值为：