1.前言

Web Search的历史经历了传统的"Text retrieval"到"基于link analysis的搜索引擎"，目前，由于机器学习和数据挖掘的技术不断成熟，利用统计模型来解决rank问题已经成为一个hot topic: Learing to Rank\(LTR\)。

  1. LTR的流程

  2. Collect Training Data(Queries and their labeled documents)

  3. Feature Extraction for Query-document Pairs

  4. Learning the Ranking Model by Minimizing a Loss Function on the Training Data

  5. Use the Model to Answer Online Queries

学习排序系统框架如图2.1所示：

 ![](http://img.blog.csdn.net/20130526121745414)

    对于标注训练集，选定LTR方法，确定损失函数，以最小化损失函数为目标进行优化即可得到排序模型的相关参数，这就是学习过程。预测过程将待预测结果输入学习得到的排序模型中，即可得到结果的相关得分，利用该得分进行排序即可得到待预测结果的最终顺序。

LTR一般说来有三类方法：单文档方法（Pointwise），文档对方法（Pairwise），文档列表方法（Listwise）。

5.训练数据的获取

有2中获取训练数据的来源：1>人工标注；2>搜索日志

3.1 人工标注

从搜索日志中随机选取一部分Query，让受过专业训练的数据评估员对"Query-Url对"给出相关性判断。常见的是5档的评分：差、一般、好、优秀、完美。以此作为训练数据。人工标注是标注者的主观判断，会受标注者背景知识等因素的影响。

 3.2搜索日志

  使用点日志的偏多。比如，如果ABC分表位于123位，B比A位置低，但却得到了更多的点击，那么B的相关性可能好于A。点击数据隐式反映了同Query下搜索结果之间相关性的相对好坏。在搜索结果中，高位置的结果被点击的概率会大于低位置的结果，这叫做“点击偏见"\(Click Bias\)。但采取以上的方式，就绕过了这个问题。因为我们只记录发生了：”点击倒置“的高低位结果，使用这样的”偏好对“作为训练数据。关于点击数据的使用，后续再讨论。在实际使用中，除了点击数据，往往还会使用更多的数据。比如通过session日志，挖掘诸如页面停留时间等维度。在实际场景中，搜索日志往往含有很多噪音。且只有Top Query\(被搜索次数较多的Query\)才能产生足够数量能说明问题的搜索日志。

 3.3公共数据集

现存一批公开的数据集可以使用

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

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

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

    4.特征抽取

    搜索引擎会使用一系列特征来决定结果的排序。一个特征称之为一个"feature"。

    feature可以分为3大类：

  4. Doc本身的特征：Pagerank、内容丰富度、是否是spam等

  5. Query-Doc的特征：文本相关性、Query term在文档中出现的次数等

此阶段就是要抽取出所有的特征，供后续训练使用。

5.模型训练

5.1训练方法

LTR的学习方法分为Pointwise、Pairwise和Listwise三类。Pointwise和Pairwise把排序问题转换成回归、分类或有序分类问题。Listwise把Query下整个搜索结果作为一个训练的实证。3种方法的区别主要体现在损失函数上：

  • Regression: treat relevance degree as real values
  • Classification: treat relevance degree as categories
  • Pairwise classification: reduce ranking to classifying the order between each pair of documents.

5.1.1 Pointwise 

Pointwis方法的主要思想是将排序问题转化为多类分类问题或者回归问题。以多类分类为例

进行说明：假设对于查询query，与其相关的文档集合为：{d1, d2, …, dn}。那么首先对这n个pair：

(query, di)抽取特征并表示成特征向量。

  • Regression-based：

将query与di之间的相关度作为value，利用regression model来得到一个query与document之间相关

度的预测。

  • Classification-based：

将query与di之间的相关度的程度作为label，一般的label等级划分方式为：｛Perfect, Excellent,

Good, Fair, Bad｝，一共五个类别。于是，对于一个查询及其文档集，可以形成n个训练实例。有了

训练实例，我们可以使用任一种多类分类器进行学习，比如最大熵，SVM。下面是一个例子：

5.1.2 Pairwise

Pairwise方法是目前比较流行的方法，相对pointwise他将重点转向文档顺序关系。它主要将排序问题归结为二元分类问题，这时候机器学习的方法就比较多了，比如Boost、SVM、神经网络等。对于同一query的相关文档集中，对任何两个不同label的文档，都可以得到一个训练实例（di,dj），如果di>dj则赋值+1，反之-1，于是我们就得到了二元分类器训练所需的训练样本了，如图2.2所示。测试时，只要对所有pair进行分类就可以得到所有文档的一个偏序关系，从而实现排序。

图2.2 Pairwise排序方法示意

尽管Pairwise对Pointwise做了改进，但该方法还是存在明显的问题：

a.只考虑了两篇文档的相对顺序，没有考虑他们出现在搜索结果列表中的位置。排在前面的文档更为重要，如果出现在前面的文档判断错误，惩罚函数要明显高于排在后面判断错误。因此需要引入位置因素，每个文档对根据其在结果列表中的位置具有不同的权重，越排在前面权重越大，如果排错顺序其受到的惩罚也越大。

b.对于不同的查询相关文档集的数量差异很大，转换为文档对后，有的查询可能只有十几个文档对，而有的查询可能会有数百个对应的文档对，这对学习系统的效果评价带来了偏置。假设查询1对应500个文档对，查询2对应10个文档对，假设机器学习系统对应查询1能够判断正确480个文档对，对应查询2能够判断正确2个。对于总的文档对该系统准确率是（480+2）/（500+10）=95%，但从查询的角度，两个查询对应的准确率分别为：96%和20%，平均为58%，与总的文档对判断准确率相差巨大，这将使得模型偏向于相关文档集大的查询。

Pairwise有很多的实现，比如Ranking SVM，RankNet，Frank，RankBoost等。

3 Listwise

Listwise与上述两种方法不同，它是将每个查询对应的所有搜索结果列表作为一个训练样例。Listwise根据训练样例训练得到最优评分函数F，对应新的查询，评分F对每个文档打分，然后根据得分由高到低排序，即为最终的排序结果。

对应如何训练最优评分函数F，本文介绍一种基于搜索结果排列组合的概率分布情况来训练的方法。如图2-2所示，对应查询Q，假设搜索引擎返回结果A、B、C三个文档，这三篇文档可以产生6中排列方式，对应评分函数F，对三篇文档进行相关度打分，得到F(A)、F(B)、F(C)，根据这三个值可以计算6种排列组合情况各自的概率值。对应不同的评分函数F，六种排列的概率分布是不同的。

假设评分函数g是由人工标记得到的标准答案对应的评分函数，它是怎样的我们暂时不清楚，我们试图找到一个评分函数f，使得f产生的打分和人工的打分尽可能相同。假设存在两个其他评分函数h和f，他们的计算方法已知，对应的搜索排列组合概率分布如图所示，通过KL距离可知，f比h更接近于虚拟的最优函数g。训练过程就是在尽可能的函数中寻找最接近虚拟函数g的那个函数，预测时用该评分函数进行打分。

Listwise方法往往更加直接，它专注于自己的目标和任务，直接对文档排序结果进行优化，因此往往效果也是最好的。Listwise常用方法有AdaRank，SoftRank，LambdaMART等。

results matching ""

    No results matching ""