AI内参_37_035_机器学习排序算法配对法排序学习

你好，我是洪亮杰。

今天我和你分享的主题是配对法排序学习。

周一的文章里，我分享了最基本的单点法排序。

学习这个思路，简单实用，是把经典的信息检索问题转化为机器学习问题的第一个关键步骤。

简单回顾一下，我们介绍了在测试集里使用NDCG在某个k的位置评价精度和召回。

以这些形式来评估排序算法。

你可以看到单点法排序、学习算法的模式和我们最终需要的结果，中间还存在着明显的差距。

这个差距并不是算法好坏能够决定的，而是算法所要优化的目标，也就是单个数据点是否相关和我们的最终目的一组结果的NDCG排序，最优之间的结构化区别。

这个结构化区别激发研究者们不断思考是不是有其他的方法来优化排序算法。

今天呢我就来讲从单点法引申出来的配对法排序学习。

相对于尝试学习每一个样本是否相关，配对法的基本思路是对样本进行两两比较，从比较中学习排序。

离真正目标又近了一步。

我先来说说配对法排序学习的历史。

当人们意识到用机器学习来对排序进行学习，从文档与文档之间的相对关系入手，也就是从配对法入手，就成了一个非常火热的研究方向。

机器学习排序这个领域持续活跃了十多年。

在此期间，很多配对法排序算法被提出。

下面我就来说几个非常热门的算法。

二零零零年左右，研究人员开始利用支持向量机来训练排序算法。

来自康奈尔的索斯藤乔吉姆斯就构建了基于特征差值的rank SVM,一度成为了配对法排序学习的经典算法。

索斯藤，我们前面讲过，他获得了今年的KDD时间检验奖。

二零零五年，当时在雅虎任职的研究人员郑朝晖等人开始尝试用GBDT,也就是梯度提升决策树，尝试用这样的数模型来对文档之间的两两关系进行建模。

郑朝晖后来成为一点资讯的联合创始人。

二零零五年，微软的学者克里斯伯格斯等人开始使用神经网络训练。

Rank net文档之间两两关系的排序模型，这是最早使用深度学习模型进行工业级应用的尝试。

这篇论文在二零一五年获得了国际机器学习大会ICML二零一五的十年经典论文奖。

下面我来说说配对法排序学习的细节。

在介绍配对法排序学习的中心思路之前，我们先来重温一下测试集的测试原理。

总体来说，测试的原理和单点法一样，都是要考察测试集上。

对于某一个查询关键字来说，某一组文档所组成的排序是否是最优的？比如对于某一个查询关键字，我们针对排序产生的顶部的k格文档进行评估。

首先，查看精度，即在所有算法已经判断是相关的文档中，究竟有多少是真正相关的。

其次，看召回及所有真正相关的文档究竟有多少被提取了出来。

当然，还有f一值，也就是精度和召回和谐平均的取值。

一个平衡精度和召回的重要指标。

需要再次说明的是，精度、召回以及f一值都是在二元相关信息的标签基础上定义的。

如果需要利用五级相关信息定义，也就是通常所说的最相关相关，不能确定相关相关信息相关。

那么就需要用类似于NDCJ这样的评价指标。

Ndcj的假设是在一个排序结果里，相关信息要比不相关信息排的更高，最相关信息需要排在最上面，最不相关信息需要排在最下面。

任何排序结果，一旦偏离的这样的假设，就会受到扣分，或者惩法清楚了测试集的情况后，再回过头来看一看训练集的设置问题。

在今天文章一开篇的时候，我就提到了单点法对于排序学习的目标不明确的问题。

其实呢从NDCJ的角度来看也好，基于顶部k的精度或者召回的角度来看也好，都可以看出。

对于一个查询关键字来说，最重要的其实不是针对对某一个文档的相关性是否估计的准确，而是要能够正确估计一组文档之间的相对关系，只要相对关系估计正确了，那么从排序这个角度来说，最后的结果也就准确了。

理解这一观点。

对于深入理解排序和普通的分类之间的区别至关重要。

那么如何从单点建模再进一步呢？很显然，在排序关系中，一个关键关系就是每两个文档之间的比较，也就是我们通常所说的两两关系。

试想一下，如果针对某一个查询关键字而言，有一个完美的排序关系，然后通过这个完美的排序关系，可以推导出文档之间的两两相对关系，再从这些相对关系中进行学习，从而可以进一步对其他查询关键字进行排序。

注意在这样的架构下，训练集的样本，从每一个关键字文档对变成了关键字文档文档配对。

也就是说，每一个数据样本其实是一个比较关系。

试想有三个文档，AB和c完美的排序是b大于c大于a我们希望通过学习两两关系。

B大于CB大于a和c大于a来重构，b大于c大于a这里面呢有几个非常关键的假设。

第一啊，我们可以针对某一个关键字得到一个完美的排序关系。

在实际操作中，这个关系可以通过五级相关标签来获得，也可以通过其他信息获得，比如点击率等信息。

然而，这个完美的排序关系并不是永远都存在的。

是想在电子商务网站中对于查询关键字哈利波特，有的用户希望购买书籍，有的用户则希望购买含有哈利波特图案的t恤，显然这里面就不存在一个完美排序。

第二，我们既希望能够学习文档之间的两两配对关系，从而重构这个完美排序。

然而这也不是一个有保证的思路。

用刚才的例子希望学习两两关系，b大于CB,大于a和c大于a来重构完美排序。

B大于c大于a然而实际中这三个两两关系之间是独立的，特别是在预测的时候，即使模型能够正确判断。

B大于c和c大于a也不代表模型就一定能得到。

B大于a啊。

注意这里的关键是一定也就是模型有可能得到，也有可能得不到两两配对关系，不能一定得到完美排序。

这个结论其实就揭示了这种方法的不一致性，也就是说我们并不能真正保证可以得到最优的排序。

第三，我们能够构建样本来描述这样的两两相对的比较关系。

一个相对比较简单的情况，认为文档之间的两两关系来自于文档特征之间的差异，也就是说可以利用样本之间特征的差值当做新的特征，从而学习到差值到相关性差异。

这样的一组对应关系。

我前面提到的rank SVM就是这样的思路。

Rank SVM本质上来说，其实还是SVM,也就是支持向量机。

只不过建模的对象从单一文档变成了文档的配对更加复杂的模型。

比如GB rank,就是通过数的聚合模型，GBDT来对文档之间的关系直接建模，希望通过函数值的差值来表达文档的相关性差异。

需要注意的是，配对法排序学习，特别是在测试及预测的时候，可能会有计算复杂度的问题。

因为原则上必须要对所有的两两关系都进行预测。

现实中，如果是基于线性特征的差值来进行样本构造的话，那么测试还可以回归到线性复杂度的情况，而用其他方法就没有那么幸运了。

有很多计算提速或者是逼近算法，为两两比较排序，在实际应用中提供了可能性。

今天我为你讲了文档检索领域基于机器学习的配对法排序学习。

你可以看到，和单点法一样，整个问题的设置和传统的文字搜索技术有本质的区别。

但在文档之间关系的建模上，又比单点法前进了一大步。

一起来回顾一下要点。

第一，在火热的机器学习排序研究中，提出了很多配对法排序算法，比如rank SVMGBDT和rank net.第二，配对法排序学习测试集的测试原理和单点法一致，我们可以查看精度召回和f一值，或者利用五级相关信息。

第三，针对单点法对于排序学习的目标不明确问题，配对法排序学习有不一样的训练集设置。

在这个基础上，我介绍了三个关键假设，最后给你留一个思考题，有没有什么办法可以把单点法和配对法结合起来呢？欢迎你给我留言，和我一起讨论。