熟悉算法 --Learning to Rank & KL 距离

KL 距离

先简单介绍下：KL 距离--Kullback-Leibler Divergence

KL 距离，是 Kullback-Leibler 差异（Kullback-Leibler Divergence）的简称，也叫做相对熵（Relative Entropy）。它衡量的是 相同事件空间里的两个概率分布的差异情况。其物理意义是：在相同事件空间里，概率分布 P(x)的事件空间，若用概率分布 Q（x）编码时，平均每个基本事件（符号）编码长度增加了多少比特。我们用 D（P||Q）表示 KL 距离，计算公式如下：

当两个概率分布完全相同时，即 P(x)=Q(X)，其相对熵为 0 。我们知道，概率分布 P(X)的信息熵为：

其表示，概率分布 P(x)编码时，平均每个基本事件（符号）至少需要多少比特编码。通过信息熵的学习，我们知道不存在其他比按照本身概率分布更好的编码方式了，所以 D(P||Q）始终大于等于 0 的。虽然 KL 被称为距离，但是其不满足距离定义的三个条件：**1）非负性；**2）对称性（不满足）；3）三角不等式（不满足）。

Learning to Rank

机器学习排序方法分为以下 3 种：单文档方法（Pointwise）、文档对方法(Pairwise)和文档列表方法(Listwise)。
注：

总体来说
Pointwise：用单个文档去训练，判断单个文档是否是跟输入的搜索是相关的
Pairwise：用 <doc1,doc2> 文档对去训练，doc1 和 doc2 都是与输入相关的，判断 doc1 是否比 doc2 更相关
Listwise：给定一个根据搜索得到的文档 list，训练一个打分函数，给 list 中的各个文档分别打分，然后根据得分进行排序

下面的似乎不太重要，想了解可以看一下

具体如下：

• 单文档方法（PointWise Approach）

单文档方法的处理对象是单独的一篇文档，将文档转换为特征向量后，机器学习系统根据从训练数据中学习到的分类或者回归函数对文档打分，打分结果即是搜索结果。下面我们用一个简单的例子说明这种方法。
图 2 是人工标注的训练集合，在这个例子中，我们对于每个文档采用了 3 个特征： 査询与文档的 Cosme 相似性分值、査询词的 Proximity 值及页面的 PageRank 数值，而相关性判断是二元的，即要么相关要么不相关，当然，这里的相关性判断完全可以按照相关程度扩展为多元的，本例为了方便说明做了简化。

** 图 2 训练数据**

例子中提供了 5 个训练实例，每个训练实例分别标出来其对应的查询，3 个特征的得分情况及相关性判断。对于机器学习系统来说，根据训练数据，需要如下的线性打分函数：
Score(Q, D)=a x CS+b x PM+cx PR+d
这个公式中，cs 代表 Cosine 相似度变徽，PM 代表 Proximity 值变量，PR 代表 pageRank， 而 a、b、c、d 则是变量对应的参数。

如果得分大于设定阀值，则叫以认为是相关的， 如果小于设定闽值则可以认为不相关。通过训练实例，可以获得最优的 a、b、c、d 参数组合，当这些参数确定后，机器学习系统就算学习完毕，之后即可利用这个打分函数进行相关性判断。对于某个新的查询 Q 和文档 D，系统首先获得其文档 D 对应的 3 个特 I 特征值，之后利用学习到的参数组合计算两者得分，当得分大于设定的闽值，即可判断文档是相关文档，否则判断为不相关文档。

PS：而微软给定的数据如下

    0 qid:1 1:3 2:0 3:2 4:2 ... 135:0 136:0 
    2 qid:1 1:3 2:3 3:0 4:0 ... 135:0 136:0 

其数据格式： label qid:id feaid:feavalue feaid:feavalue ...
每行表示一个样本，相同的查询请求的样本 qid 相同，上面就是两个对 qid 为“1”的查询；label 表示该样本和该查询请求的相关程度，该 label 等级划分方式为 {Perfect, Excellent,Good, Fair, Bad} 共五个类别。

• 文档对方法（PairWise Approach)

对于搜索系统来说，系统接收到用户査询后，返回相关文档列表，所以问题的关键是确定文档之间的先后顺序关系。单文档方法完全从单个文档的分类得分角度计算，没有考虑文档之间的顺序关系。文档对方法则将重点转向量对文档顺序关系是否合理进行判断。

之所以被称为文档对方法，是因为这种机器学习方法的训练过程和训练目标，是判断任意两个文档组成的文档对是否满足顺序关系，即判断是否 D0C1 应该排在 DOC2 的前面。图 3 展示了一个训练实例：査询 Q1 对应的搜索结果列表如何转换为文档对的形式，因为从人工标注的相关性得分可以看出，D0C2 得分最高，D0C3 次之，D0C1 得分最低，于是我们可以按照得分大小顺序关系得到 3 个如图 3 所示的文档对，将每个文档对的文档转换为特征向量后，就形成了一个具体的训练实例。

图 3 文档对的方法训练实例

根据转换后的训练实例，就可以利用机器学习方法进行分类函数的学习，具体的学习方法有很多，比如 SVM. Boosts、神经网络等都可以作为具体的学习方法，但是不论具体方法是什么，其学习目标都是一致的，即输入- 个査询和文档对, 机器学习排序能够判断这种顺序关系是否成立，如果成立，那么在搜索结果中 D0C1 应该排在 D0C2 前面，否则 Doe2 应该摔在 Docl 前面，通过这种方式，就完成搜索结果的排序任务。
尽管文档对方法相对单文档方法做出了改进，但是这种方法也存在两个明显的问题：

一个问题是：文档对方法只考虑了两个文档对的相对先后顺序，却没有考虑文档出现在搜索列表中的位置，排在搜索站果前列的文档更为重要，如果前列文档出现判断错误，代价明显高于排在后面的文档。针对这个问题的改进思路是引入代价敏感因素，即每个文档对根据其在列表中的顺序具有不同的权重，越是排在前列的权重越大，即在搜索列表前列如 果排错顺序的话其付出的代价更高?
另外一个问题是：不同的査询，其相关文档数量差异很大，所以转换为文档对之后， 有的查询对能有几百个对应的文档对，而有的查询只有十几个对应的文档对，这对机器学习系统的效果评价造成困难 ?我们设想有两个查询，査询 Q1 对应 500 个文文档对，查询 Q2 对应 10 个文档对，假设学习系统对于査询 Ql 的文档对能够判断正确 480 个，对于査询 Q2 的义格对能够判新正确 2 个，如果从总的文档对数量来看，这个学习系统的准确率是 (480+2)/（500+10）=0.95.即 95% 的准确率，但是从査询的角度，两个査询对应的准确率 分别为：96% 和 20%,两者平均为 58%,与纯粹从文档对判断的准确率相差甚远，这对如何继续调优机器学习系统会带来困扰。

PS：Pairwise 方法有很多的实现，比如 SVM Rank（开源）, 还有 RankNet(C. Burges, et al. ICML 2005)， FRank(M.Tsai, T.Liu, et al. SIGIR 2007)，RankBoost(Y. Freund, et al. JMLR 2003)等等。
你通常会看到微软数据集每个 Fold 文件夹下有 train.txt test.txt vail.text 三个文件，它们分别的作用是什么呢？
训练集--用于学习参数，比如可以训练 10 个不同阶的线性模型，这里得到每个特征值的权值；验证集--用来选择模型，主要考虑的准则是在新的数据上的泛化能力，比如根据各个模型在验证集上的权值，选择了 3 阶的模型；测试集--测试模型，测试这个被选中的 3 阶模型的表现。

• 文档列表方法（ListWise Approach)

单文档方法将训练集里每一个文档当做一个训练实例，文档对方法将同一个査询的搜索结果里任意两个文档对作为一个训练实例，文档列表方法与上述两种表示方式不同，是将每一个查询对应的所有搜索结果列表整体作为一个训练实例，这也是为何称之为文档列表方法的原因。
文档列表方法根据 K 个训练实例（一个査询及其对应的所有搜索结果评分作为一个实 例）训练得到最优评分函数 F， 对于一个新的用户査询，函数 F 对每一个文档打分，之后按照得分顺序由高到低排序，就是对应的搜索结果。 所以关键问题是：拿到训练数据，如何才能训练得到最优的打分函数？

这里介绍一种训练方法，它是基于搜索结果排列组合的概率分布情况来训练的，图 4 是这种方式训练过程的图解示意。

图 4 不同评分函数的 KL 距离

首先解释下什么是搜索结果排列组合的概率分布，我们知道，对于搜索 引擎来说，用户输入査询 Q， 搜索引擎返回搜索结果，我们假设搜索结果集合包含 A. B 和 C 3 个文档，搜索引擎要对搜索结果排序，而这 3 个文档的顺序共有 6 种排列组合方式:

ABC, ACB, BAG, BCA, CAB 和 CBA,

而每种排列组合都是一种可能的搜索结果排序方法。

对于某个评分函数 F 来说，对 3 个搜索结果文档的相关性打分，得到 3 个不同的相关度得分 F(A)、 F(B)和 F(C)， 根据这 3 个得分就可以计算 6 种排列组合情况各自的概率值。 不同的评分函数，其 6 种搜索结果排列组合的概率分布是不一样的。
了解了什么是搜索结果排列组合的概率分布，我们介绍如何根据训练实例找到最优的 评分函数。图 4 展示了一个具体的训练实例，即査询 Q1 及其对应的 3 个文档的得分情况，这个得分是由人工打上去的，所以可以看做是标准答案。可以设想存在一个最优的评分函数 g，对查询 Q1 来说，其打分结果是：A 文档得 6 分，B 文档得 4 分，C 文档得 3 分， 因为得分是人工打的，所以具体这个函数 g 是怎样的我们不清楚，我们的任务就是找到一 个函数，使得函数对 Ql 的搜索结果打分顺序和人工打分顺序尽可能相同。既然人工打分 (虚拟的函数 g) 已知，那么我们可以计算函数 g 对应的搜索结果排列组合概率分布，其具体分布情况如图 4 中间的概率分布所示。假设存在两个其他函数 h 和 f，它们的计算方法已知，对应的对 3 个搜索结果的打分在图上可以看到，由打分结果也可以推出每个函数对应的搜索结果排列组合概率分布，那么 h 与 f 哪个与虚拟的最优评分函数 g 更接近呢？一般可以用两个分布概率之间的距离远近来度量相似性，KL 距离就是一种衡量概率分布差异大小的计算工具，通过分别计算 h 与 g 的差异大小及 f 与 g 的差异大小，可以看出 f 比 h 更接近的最优函数 g，那么在这个函数中，我们应该优先选 f 作为将来搜索可用的评分函数，训练过程就是在可能的函数中寻找最接近虚拟最优函数 g 的那个函数作为训练结果，将来作为在搜索时的评分函数。