AI内参_54_052_机器学习排序算法经典模型RankSVM

你好，我是洪亮杰。

今天我和你分享的主题是机器学习排序算法经典模型rank SVM.到目前为止呢，我们在专栏里已经讨论了关于搜索引擎方方面面的很多话题，包括经典的信息检索、技术查询、关键字理解、文档理解以及现代搜索引擎的架构等等。

同时，我们也从机器学习角度出发，对搜索引擎的最核心部分，也就是排序算法进行了最基本的分享，囊括了单点法排序学习、配对法排序学习以及列表法排序学习，相信你应该对这类算法的大概内容有所掌握。

那么这周我们就来看看机器学习排序算法中几个经典的模型。

希望能够通过这几个经典的算法，为你深入学习和研究排序算法指明方向。

今天我就来分享配对法排序中最有价值的一个算法。

Rank SVM,也就是排序支持向量机这个算法的核心思想是应用支持向量机到序列数据中试图对数据间的顺序直接进行建模。

我先来简要说说排序支持向量机的历史。

二十世纪九十年代中后期，受统计学习理论思想和风险最小化框架趋于成熟的影响，支持向量机逐渐成为当时机器学习界的主流模型。

一时间，各个应用领域的学者和工程师都在思考，如何把支持向量机利用到自己的问题领域上，从而获得更好的效果。

拉夫赫伯里奇发表于一九九九年和二零零零年的论文中，讨论了如何把支持向量机和有序回归结合起来。

赫伯里奇当时在柏林科技大学攻读博士学位。

二零零零年到二零一一年，他在微软研究院和并任职从事机器学习，特别是贝叶斯方法的研究。

二零一一年到二零一二年，他在facebook短暂任职后于二零一二年加入了亚马逊负责机器学习的研发工作，并且担任在柏林的研发中心主管经理。

尽管赫伯里奇很早提出了把有序回归和支持向量机结合的思路，但是当时的论文并没有真正的把这个新模型用于大规模搜索系统的验证，更加完整的对排序。

支持向量机在搜索中的应用进行论述，来自于康奈尔大学教授、索斯滕乔吉姆斯以及他和合作者们发表的一系列论文。

索斯藤，我们前面介绍过，他是机器学习界享有盛誉的学者，是ACM和AAAI的双料院士，他所有论文的引用数超过四万次，他获得过一系列奖项，包括我们前面讲的二零一七年ACMKDD的时间检验奖等等。

在说明排序支持向量机之前，我们先来简要的回顾一下支持向量机的基本思想。

在二分分类问题中，线性支持向量机的核心思想是找到一个超平面，把正例和负例完美分割开。

在诸多可能的超平面中，支持向量机尝试找到距离两部分数据点边界距离最远的那一个。

这也就是为什么有时候支持向量机又被称作是边界最大化的属性。

如果问题并不是线性可分的情况，支持向量机还可以借助核技巧来把输入特性，通过非线性变换转化到一个线性可分的情况。

关于支持向量机的具体内容，你可以参考各类机器学习教科书的论述，要把支持向量机运用到排序场景。

下关须改变一下原来的问题设置。

我们假设每个数据点由特性x和标签y组成。

这里的x代表当前文档的信息、文档与查询关键字的相关度、查询关键字的信息等方方面面。

关于文档以及查询关键字的属性，y是一个代表相关度的整数，通常情况下大于一。

那么在这样的设置下，我们针对不同的x需要学习到一个模型，能够准确的预测出y的顺序。

意思是说，如果有两个数据点x一和x二，它们对应的y一是三，y二是五，因为y二大于y一。

因此，一个合理的排序模型需要把x一通过某种转换也得到的结果小于同样的转换作用于x二上。

这里的转换就是排序知识向量机需要学习到的模型。

具体说来，在线性假设下，排序知识向量机就是要学习到一组线性系数w使得在上面这个例子中，x二点击w之后的结果要大于x一点击w的结果。

当然，对于整个数据集而言，我们不仅仅需要对x一和x二这两个数据点进行合理预测。

还需要对所有的点以及它们之间所有的顺序关系进行建模。

也就是说，模型的参数w需要使得数据集上所有数据点的顺序关系的预测都准确。

很明显，上述模型是非常严格的，而实际中很可能并不存在这样的w可以完全使得所有的x都满足这样的条件。

这也就是我们之前说的线性不可分在排序中的情况。

那么更加现实的一个定义是在允许有一定误差的情况下，如何使得w可以准确预测所有数据之间的顺序关系。

并且w所确定的超平面到达两边数据的边界最大化，这就是线性排序向量积的定义。

实际上，在线性分类器的情境下，线性排序向量机实际上是针对数据配对的差值进行建模的。

回到刚才我们所说的例子，线性排序向量机是把x二减去x一的差值当做新的特性向量。

然后学习w也就是说原理上说整个知识向量机的所有理论和方法都可以不加改变的应用到这个新的特征向量空间中。

当然这个情况仅仅针对线性分类器，因为是针对两个数据点之间的关系进行建模排序，知识向量机也就成为配对法排序学习的一个经典模型。

我们刚刚提到的排序，支持向量机的定义方法虽然很直观，但是有一个非常大的问题，那就是复杂度是n的平方级。

这里的n是数据点的数目，原因是我们需要对数据点与点之间所有配对进行建模。

当我们要对上万甚至上百万的文档建模的时候，直接利用排序支持向量机的定义来求解模型参数，显然是不可行的。

于是，针对排序，支持向量机的研究和应用就集中在了如何能够降低计算复杂度这一难点上，使得算法可以在大规模数据上得以使用。

比较实用的算法是索斯滕在二零零六年发表的论文中提出的这篇论文。

就是我们在前面讲的二零一七年KDD时间检验讲。

建议你回去复习一下这里，我再简要的梳理一下要点。

这个算法的核心是重新思考了对排序支持向量机整个问题的设置。

把解决结构化向量机的一种算法，CP算法使用到了排序支持向量机上。

简单来说，这个算法就是保持一个工作集合来存放，当前循环时依然被违反的约束条件，然后在下一轮中集中优化这部分工作集合的约束条件。

整个流程开始于一个空的工作集合，每一轮优化的是一个基于当前工作集合的支持向量机子问题算法，直到所有约束条件的误差小于一个全局的参数误差为止。

索斯藤在文章中详细证明了该算法的有效性和时间复杂度相同的方法，也使得排序知识下量级的算法能够转换成为更加计算有效的优化过程。

在线性计算复杂度的情况下完成。

今天我为你讲了利用机器学习技术来学习排序算法的一个基础的算法排序。

支持向量机的基本原理作为配对法排序学习的一个经典算法排序。

支持向量机有着广泛的应用，我们一起来回顾一下要点。

第一，我们简要介绍了排序，支持向量机提出的历史背景。

第二，我们详细介绍了排序支持向量机的问题设置。

第三，我们简要提及了排序支持向量机的难点和一个实用的算法。

最后给你留一个思考题排序，支持向量机是否给了你一些启发，让你可以把更加简单的对数几率分类器应用到排序问题上呢？欢迎你给我留言，和我一起讨论。