039 | 机器学习排序算法经典模型：RankSVM

到目前为止，我们在专栏里已经讨论了关于搜索引擎方方面面的很多话题，包括经典的信息检索技术、查询关键字理解、文档理解以及现代搜索引擎的架构等等 。同时，我们也从机器学习角度出发对搜索引擎的最核心部分，也就是排序算法进行了最基本的分享，囊括了单点法排序学习（Pointwise Learning to Rank）、配对法排序学习（Pairwise Learning to Rank）以及列表法排序学习（Listwise Learning to Rank），相信你应该对这类算法的大概内容有所掌握。

那么，这周我们就来看看机器学习排序算法中几个经典的模型，希望能够通过这几个经典的算法为你深入学习和研究排序算法指明方向。

今天，我就来分享配对法排序中最有价值一个算法，排序支持向量机（RankSVM）。这个算法的核心思想是应用支持向量机到序列数据中，试图对数据间的顺序直接进行建模。

排序支持向量机的历史

20 世纪 90 年代中后期，受统计学习理论（Statistical Learning Theory ）思想和风险最小化框架（Risk Minimization Framework）趋于成熟的影响，支持向量机逐渐成为当时机器学习界的主流模型。一时间，各个应用领域的学者和工程师都在思考如何把支持向量机利用到自己的问题领域上，从而获得更好的效果。

拉夫⋅赫博里奇（Ralf Herbrich）发表于 1999 年 [1] 和 2000 年 [2] 的论文中讨论了如何把支持向量机和有序回归（Ordinal Regression）结合起来。赫博里奇当时在柏林科技大学（Technical University of Berlin）攻读博士学位。2000 年到 2011 年，他在微软研究院和 Bing 任职，从事机器学习，特别是贝叶斯方法（Bayesian method）的研究。2011 年到 2012 年，他在 Facebook 短暂任职后，于 2012 年加入了亚马逊负责机器学习的研发工作，并且担任在柏林的研发中心主管经理（Managing Director）。尽管赫博里奇很早提出了把有序回归和支持向量机结合的思路，但是当时的论文并没有真正地把这个新模型用于大规模搜索系统的验证。

更加完整地对排序支持向量机在搜索中的应用进行论述来自于康奈尔大学教授索斯腾⋅乔基姆斯（Thorsten Joachims）以及他和合作者们发表的一系列论文（见参考文献 [3]、[4]、[5] 和 [6]）。索斯滕我们前面介绍过，他是机器学习界享有盛誉的学者，是 ACM 和 AAAI 的双料院士；他所有论文的引用数超过 4 万次；他获得过一系列奖项，包括我们前面讲的 2017 年 ACM KDD 的时间检验奖等等。

排序支持向量机模型

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

在二分分类问题中（Binary Classification），线性支持向量机的核心思想是找到一个“超平面”（Hyperplane）把正例和负例完美分割开。在诸多可能的超平面中，支持向量机尝试找到距离两部分数据点边界距离最远的那一个。这也就是为什么有时候支持向量机又被称作是“边界最大化”（Large Margin）分类器。

如果问题并不是线性可分的情况，支持向量机还可以借助“核技巧”（Kernel Trick）来把输入特性通过非线性变换转化到一个线性可分的情况。关于支持向量机的具体内容你可以参考各类机器学习教科书的论述。

要把支持向量机运用到排序场景下，必须改变一下原来的问题设置。我们假设每个数据点由特性 X 和标签 Y 组成。这里的 X 代表当前文档的信息、文档与查询关键字的相关度、查询关键字的信息等方方面面关于文档以及查询关键字的属性。Y 是一个代表相关度的整数，通常情况下大于 1。

那么，在这样的设置下，我们针对不同的 X，需要学习到一个模型能够准确地预测出 Y 的顺序。意思是说，如果有两个数据点 X1X1 和