|
|
# 024 | CVPR 2018论文精读：如何解决排序学习计算复杂度高这个问题？
|
|
|
|
|
|
今天，我们来看这次大会的一篇最佳论文提名，标题是《基于排序的损失函数的有效优化》（Efficient Optimization for Rank-based Loss Functions）。
|
|
|
|
|
|
还是先简单介绍下论文的作者群。这篇论文的作者来自好几个不同的学术机构。
|
|
|
|
|
|
第一作者普里迪什·莫哈帕德拉（Pritish Mohapatra）是印度海得拉巴的国际信息科技大学（International Institute of Information Technology，Hyderabad）的计算机科学博士生。他已经在NIPS、CVPR、ICCV、AISTATS等国际机器学习权威会议上发表了多篇论文。
|
|
|
|
|
|
第二作者米卡尔·罗莱内克（Michal Rolinek）来自德国的马克思普朗克智能系统大学（Max Planck Institute for Intelligent Systems），博士后研究员。在这篇论文中，第一作者和第二作者的贡献相当。
|
|
|
|
|
|
第三作者贾瓦哈（C.V. Jawahar）是来自印度国际信息科技学院的教授。他是第一作者莫哈帕德拉的博士生导师。
|
|
|
|
|
|
第四作者弗拉迪米尔·科莫格罗夫（Vladimir Kolmogorov）是奥地利科技大学（Institute of Science and Technology Austria）的机器学习教授。
|
|
|
|
|
|
最后一个作者帕万·库玛（M. Pawan Kumar）来自牛津大学。
|
|
|
|
|
|
## 论文的主要贡献
|
|
|
|
|
|
这篇论文提出了一个针对排序学习中**基于整个排序的损失函数**的快速优化算法，这是一个重要贡献。
|
|
|
|
|
|
在计算机视觉中，有很多机器学习的任务都需要针对两个图像进行一个偏好的排序。而在信息检索或者搜索中，排序是一个核心问题。因此，任何对于排序学习算法的重大改进都会有广泛的应用。
|
|
|
|
|
|
先来回顾下我们学过的三种形态的排序学习算法。
|
|
|
|
|
|
第一种是**单点法排序**。这个算法针对每一个查询关键词和相对应的某个文档，我们仅仅判断每一个文档是不是相关的。大多数的单点法排序算法都把整个问题转换成为分类或者回归问题。这样就可以利用大规模机器学习的便利来快速地学习排序函数。
|
|
|
|
|
|
第二种是**配对法排序**。这个算法是以单点法为基础。因为单点法完全忽略两个文档之间的相对关系。所以配对法是对两个文档与同一个查询关键词的相对相关度，或者说是相关度的差值进行建模。
|
|
|
|
|
|
第三种是**列表法排序**。列表法是直接针对排序的目标函数或者指标进行优化。这种方法虽然在理论上有优势，但是计算复杂度一般都比较高，在现实中对排序效果的提升比较有限，因此在实际场景中，依然有大量的应用采用单点法或者配对法排序。
|
|
|
|
|
|
这篇论文就是针对列表法排序学习的“**计算复杂度高**”这个问题，作者们发明了一套叫作“**基于快速排序机制**”（Quicksort flavoured algorithm）的优化框架。在这个优化框架下，排序学习计算复杂度高的这个问题得到了大幅度优化。作者们然后证明了流行的针对NDCG和MAP进行排序学习都满足所发明的优化框架，这样也就在理论上提供了快速优化的可能性。
|
|
|
|
|
|
## 论文的核心方法
|
|
|
|
|
|
要理解这篇论文的核心方法，我们先从配对法排序学习讲起。
|
|
|
|
|
|
针对每一个查询关键词，我们可以构建一个**文档和文档的矩阵**。这个矩阵的每一个元素代表两个文档在当前查询关键词下的关系。如果这个矩阵元素是+1，那么就表明这一行所代表的文档排位要优先于这一列所代表的文档。如果这个矩阵元素是-1，那么就表明这一行所代表的文档要比这一列所代表的文档排位低。当然，还有矩阵元素是0的情况，那就是这两个文档的排位可以是一样的。在这个数据基础上，我们可以从所有这些二元关系中推导出一个整体的排序。
|
|
|
|
|
|
下面来看配对法排序的核心思路。对于同一个查询关键词而言，我们从和这个查询关键词相关的文档中，随机抽取一个文档，然后从和这个查询关键词不相关的文档中也抽取一个文档，这两个抽取出来的文档就组成一个配对。我们希望**建立一个模型或者函数**，对于这样任意的配对，总能够让**相关文档的函数值大于不相关文档的函数值**。
|
|
|
|
|
|
如果我们对这个配对法稍微做一些更改，得到的就是列表法排序。首先，我们依然针对每一个正相关的文档进行函数值预测，也针对每一个负相关的文档进行函数值预测。我们把这两个函数值的差值，当做是预测的配对矩阵中这两个文档相对应的那一个元素。只不过在这个时候，我们关注的不是这两个文档的关系，而是配对矩阵所代表的排序和真实排序之间的**差别**。这个差别越小，我们就认为最终的基于列表的损失函数就小；如果差别大，那损失函数的差别就大。
|
|
|
|
|
|
如何针对这个基于列表的损失函数进行优化，从而能让我们针对单一文档的函数打分最优呢？这就是列表法排序学习的一个核心困难。
|
|
|
|
|
|
有一个优化办法，就是找到在当前函数打分的情况下，有哪个文档配对违反了排序原则。什么是**违反排序原则**呢？我们刚才说了，模型是希望把正相关的文档排在负相关的文档前面。但是，如果函数并没有完全被学习好，那么负相关的文档也会排到正相关的文档之前，这就叫违反排序原则。
|
|
|
|
|
|
如果我们找到这样的配对，那么就可以通过调整函数的参数，让这样的违反配对不出现。很显然，当我们有很多这样的配对时，找到违反排序原则最严重的那个配对，也就是负相关的函数值要远远大于正相关函数值的这个配对，对于我们改进函数的参数就会很有帮助。所以，这里的关键就变成了**如何找到违反排序原则最严重的配对**（Most-violating ranking）。
|
|
|
|
|
|
作者们针对这个任务发明了一个框架，叫作“**基于快速排序机制**”。具体来说，作者们发现，违反排序原则最严重的配对需要满足一些原则。我们需要对当前的数据序列进行快速排序，从而能够找到这个违反排序原则的配对。这里有很多的细节，有兴趣的话建议去读读原论文。你只需要记住，这个快速排序机制利用了**快速排序的时间复杂度**，来实现寻找违反排序原则最严重配对的这个目的。
|
|
|
|
|
|
那么，是不是大多数排序指标都符合这个机制呢？作者们提供的答案是普遍的MAP和NDCG都符合这个机制。论文给出了证明，因此我们就可以直接使用论文的结论。
|
|
|
|
|
|
## 实验结果
|
|
|
|
|
|
作者们在PASCAL VOC 2011数据集上进行了实验，主要是比较了直接进行单点法排序以及直接进行列表法优化，和这篇论文提出的优化算法之间的性能差距。在这个比较下，本文提出的方法优势非常明显，基本上是以单点法的时间复杂度达到了列表法的性能。
|
|
|
|
|
|
## 小结
|
|
|
|
|
|
今天我为你讲了CVPR 2018的最佳论文提名。
|
|
|
|
|
|
一起来回顾下要点：第一，这篇文章的主要贡献是提出了一个基于整个排序的损失函数的快速优化算法；第二，文章提出方法的核心内容是发明了一个框架，叫作“基于快速排序机制”；第三，我们简单介绍了一下论文的实验结果。
|
|
|
|
|
|
最后，给你留一个思考题，回忆一下我们曾经讲过的LambdaMART算法，那里其实也有这么一个寻找违反排序原则配对的步骤，你能想起来是什么步骤吗？
|
|
|
|
|
|
欢迎你给我留言，和我一起讨论。
|
|
|
|