AI内参_25_024_CVPR_2018论文精读如何解决排序学习计算复杂度高这个问题

你好，我是洪亮杰。

今天我和你分享的主题是CVPR二零一八论文精读。

如何解决排序学习计算复杂度高这个问题。

今天我们来看这次大会的一篇最佳论文提名标题是基于排序的损失函数的有效优化，还是先简单介绍一下论文的作者群？这篇论文的作者来自好几个不同的学术机构。

第一作者普里迪什莫哈帕德拉是印度海德拉巴的国际信息科技大学的计算机科学博士生，他已经在NIPSCVPRICCVAI space等国际机器学习权威会议上发表了多篇论文。

第二作者，米卡尔罗莱内克来自德国的马克思普兰克智能系统大学是博士后研究员。

在这篇论文中，第一作者和第二作者的贡献相当。

第四作者贾瓦哈是来自印度国际信息科技学院的教授，他是第一作者莫哈帕德拉的博士生导师。

第四，作者，弗拉迪米尔克摩格洛夫是奥地利科技大学的机器学习教授。

最后一个作者，帕万库玛来自牛津大学。

这篇论文提出了一个针对排序学习中，基于整个排序的损失函数的快速优化算法，这是一个重要的贡献。

在计算机视觉中有很多机器学习的任务，都需要针对两个图像进行一个偏好的偏序。

而在信息检索或者搜索中，排序是一个核心问题。

这个算何对于排序、学习算法的重大改进，都会有广泛的应用。

先来回顾一下我们学过的三种形态的排序。

学习算法。

第一种是单点法排序。

这个算法针对每一个查询关键词和相对应的某个文档，我们仅仅判断每一个文档是不是相关的。

大多数的单点法排序算法都是把整个问题都转化成为分类或者回归问题。

这样就可以利用大规模机器学习的便利来快速的学习排序函数。

第二种是配对法排序，这个算法是以单点法为基础，因为配对法完全忽略两个文档之间的相对关系。

所以配对法是对两个文档与同一个查询关键词的相对相关度，或者说是相关度的差值进行建模。

第三种是列表法，排序列表法是直接针对排序的目标函数或者指标进行优化。

这种方法虽然在理论上有优势，但是计算复杂度一般都比较高。

在现实中，对排序效果的提升比较有限。

因此，在实际场景中，依然有大量的应用采用单点法或者配对法排序。

这篇论文就是针对列表法排序学习的计算复杂度高。

这个问题，作者们发明了一套叫做基于快速排序机制的优化框架。

在这个优化框架下，排序学习计算复杂度高，这个问题得到了大幅度优化。

作者们然后证明了流行的针对NDCG和MAP进行排序学习都满足所发明的优化框架。

这样也就在理论上提供了快速优化的可能性。

要理解这篇论文的核心方法。

我们先要从配对法排序学习。

想起针对每一个查询关键词，我们可以构建一个文档和文档的矩阵。

这个矩阵的每一个元素代表两个文档在当前查询关键词下的关系。

如果这个矩阵关系是正一，那么就表明这一行所代表的文档排位要优先于这一列所代表的文档当果。

这个矩阵元素是负一，那么就表明这一行所代表的文档要比这一列所代表的文档排位低。

当然还有矩阵元素是零的情况，那就是这两个文档的排位可以是一样的。

在这个数据基础上，我们可以从所有的这些二元关系中推导出一个整体的排序。

下面来看配对法排序的核心思路。

对于同一个查询关键词而言，我们从和这个查询关键词相关的文档中随机抽取一个文档。

然后从和这个查询关键词不相关的文档中也抽取一个文档。

这两个抽取出来的文档就组成一个配对。

我们希望建立一个模型或者函数。

对于这样任意的配对，总能够让相关文档的函数值大于不相关文档的函数值。

如果我们对这两个配对法稍微做一些更改，得到的就是列表法排序。

首先，我们依然针对每一个正相关的文档进行函数值预测。

也针对每一个负相关的文档进行函数值预测。

我们把这两个函数值的差值当做是预测的配对矩阵中这两个文档相对应的那一个元素。

只不过在这个时候，我们关注的不是这两个文档的关系，而是配对矩阵所代表的排序和真实排序之间的差别。

这个差别越小，我们就认为最终的基于列表的损失函数就小。

如果差别大，那损失函数的差别就会变得很大。

如何针对这个基于列表的损失函数进行优化，从而能让我们针对单一文档的函数打分最优呢？这就是列表法排序学习的一个核心困难。

有一个优化办法，就是找到这当前函数打分的情况下，有哪个文档配对违反了排序原则。

什么是违反排序原则呢？我们刚才说了，模型是希望把正相关的文档排在负相关的文档前面。

但是如果函数并没有完全被学习好，那么负相关的文档也会排到正相关的文档之前，这就叫违反排序原则。

如果我们找到这样的配对，那么就可以通过调整函数的参数，让这样的违反配对不出现。

很显然，当我们有很多这样配对的时候，找到违反排序原则，最严重的那个配对，也就是负相关的函数值要远远大于正相关函数值的这个配对。

对于我们改进函数的参数就会很有帮助。

所以这里的关键就变成了如何找到违反排序原则最严重的配对。

作者们针对这个任务发明的一个框架，叫做基于快速排序机制。

具体来说，作者们发现，违反排序原则最严重的配对需要满足一些原则。

我们需要对当前的数据序列进行快速排序，从而能够找到这个违反排序原则的配对。

这里有很多的细节，有兴趣的话，建议大家读读原论文。

你只需要记住这个快速排序机制，利用了快速排序的时间复杂度，来实现寻找违反排序原则最严重配对的这个目的。

那么是不是大多数排序指标都符合这个机制呢？作者们提供的答案是，普遍的，MAP和NDCG都符合这个机制，论文给出了证明，因此我们就可以直接使用论文的结论。

作者们在passcwork二零一一数据集上进行了实验，主要是比较了直接进行单点法排序，以及直接进行列表法优化和这篇论文提出的优化算法之间的性能差距。

在这个比较下，本文提出的方法优势非常明显，基本上是以单点法的时间复杂度达到了列表法的性能。

今天我为你讲了CVP二零一八的最佳论文提名，我们一起来回顾一下要点。

第一，这篇文章的主要贡献是提出了一个基于整个排序的损失函数的快速优化算法。

第二，文章提出方法的核心内容是发明了一个框架，叫做基于快速排序机制。

第三，我们简单介绍了一下论文的实验结果，最后给你留一个思考题。

回忆一下我们曾经讲过的lambda mart算法，那里其实也有这么一个寻找违反排序原则配对的步骤。

你能想起来这是什么步骤吗？欢迎你给我留言，和我一起讨论。