AI内参_02_001_聊聊2017年KDD大会的时间检验奖

你好，我是侯亮杰，今天我来和你聊一聊。

二零一七年KDD大会的时间检验奖。

Acmsijkdd国际会议是由ACM的数据挖掘及知识发现专委会主办的数据挖掘研究领域的顶级会议。

Kdd最早是从一九八九年开始的KDD研讨班发展而来。

当时的研讨班依托于人工智能顶级会议、IJCI大会或者AAAI大会，而后来在一九九五年升级，为了会议的模式，到现在已经有二十多年的历史了。

今年的KDD大会于八月十三号到十七号，在加拿大的哈利法克斯成功的召开了SIJKDD每年都会奖励一篇论文。

这篇论文要在过去十年间对研究方法论以及实践产生重大影响，这就是所谓的时间检验奖、沿用次数以及对一个领域的影响力度，是评选这个奖项的重要指标。

二零一七年的SIJKDD时间检验奖授予了美国康奈尔大学信息科学系主任计算机科学系教授索斯滕乔吉姆斯。

那么这次授予是为了表彰他的论文，线性时间内训练线性支持向量机。

这篇论文也是二零零六年的KDD最佳论文，引用数超过了一千六百多次。

我先来和你说说索斯腾的学术贡献。

那么索斯腾啊，他是一位机器学习界享有盛誉的学者，也是ACM和AAAI双料的院士，他所有论文的引用数加起来超过了四万次。

二零零一年，从德国多特蒙德大学博士毕业之后，他正式加入了康奈尔大学，从事机器学习研究获得这个奖项。

之前索斯腾曾多次获得重要奖项，比如二零一七年ACMWSDM的最佳论验奖，二零一六年ACMSIJIR的时间检验奖，二零一五年ACMKDD的时间检验奖，二零零九年ICML的最佳论文奖，二零零九年ICML的十年最佳论文奖。

二零零六年ECMKDD最佳论文奖、二零零五年ICML最佳论文奖、二零零五年ICML的优秀学生论文奖和二零零五年的ACMKDD最佳学生论文奖等索斯腾的机器学习领域一直有着非常特殊的贡献。

首先，他在支持向量机的应用上做出了诸多努力。

比如说这次的时间检验奖，就是奖励他如何把支持向量机的训练达到现行复杂度，从而使支持向量机在大规模数据上的应用成为了可能。

索斯藤还致力于把支持向量机的基本算法，也就是仅仅支持分类问题和回归问题的算法，应用到更加复杂的、有结构的输出结果上，俗称结构化的支持向量机算法。

得益于这项工作，支持向量机可以对信息检索中很多复杂的、非二分的评估指标进行直接优化，如f一值平均精度均值，从而让支持向量机的应用变得更加广阔。

在让支持向量机能够顺利应用到信息检索的过程中，索思腾还发现了另外一个问题，那就是如何利用搜索引擎的间接用户反馈来训练排序算法。

具体来说，传统的搜索系统和信息检索系统主要是依靠人工标注的训练数据来进行优化和评估。

这里所说的人工标注训练数据，主要是指人为的评价目标、查询关键字和所对应的网页是否相关。

早期大家发现，虽然搜索引擎可以利用这样的数据来优化排序算法，但是搜索引擎在使用过程中会产生很多用户数据，而这些数据可以是用户点击搜索页面结果产生的信息，也可以是其他的信息。

早期这些信息并没有用于优化搜索引擎，以索思腾为主的一批学者意识到点击信息的重要性，然后开始利用这些数据来训练和评估排序算法。

这是索斯藤的第二个主要学术贡献。

索斯藤第三个主要学术贡献也是他最近几年的学术成果，那就是把因果推论和机器学习相结合，从而能够更加无偏差的训练模型。

可以说，这部分工作开创了一个新的领域，长期以来，如何有效的应用用户产生的交互数据来进行模型训练，都是大规模机器学习，特别是工业界机器学习的难点。

一方面，工业系统能够产生很多用户数据，另一方面这些用户数据又受到了当前部署系统的影响，一般都有一定的偏差。

因此，工业级机器学习系统面临一个长期挑战。

一就是如何能够在评估模型以及训练模型的时候，考虑到这样的偏差，从而去除这样的偏差。

索斯滕利用因果推论中的倾向、评分技术以及多臂赌博机思想，把这样的方法成功的引入到了机器学习中，使得无偏差的训练模型成为可能。

目前，这方面的新研究和新思想正在机器学习以及应用界产生越来越多的共鸣。

回到这篇时间检验讲的论文，它解决的是大规模优化支持向量机的问题，特别是线性支持向量机这篇文章第一次提出了简单易行的线性支持向量机，实现包括对有序回归的支持算法对于分类问题达到了大OSN,也就是实现了线性复杂度。

而对于有序回归的问题，达到了大OSN log n的复杂度，算法本身简单、高效、易于实现。

并且理论上可以扩展到核函数的情况。

在此之前，很多线性支持向量机的实现都无法达到线性复杂度。

比如当时的leab、 SVMSVM、 torch以及早期的SVM light中采用的分解算法，都只能比较有效的处理大规模的特征。

而对于大规模的数据，n则是超线性的复杂度。

另外的一些方法能够训练复杂度线性的随着训练数据的增长而增长，但是却对于特征数n呈现了二次方的复杂度。

因此之前的这些方法无法应用到大规模的数据上。

这样的情况，对于有序回归支持向量机更加麻烦。

从德国学者拉尔夫赫布里希提出有序回归支持向量机以来，一直需要通过转化为普通的支持向量机的分类问题而求解。

而这个转换过程需要产生大ON的二次方的训练数据，使得整个问题的求解也在这个量级的复杂度。

那么这篇文章里，索斯滕首先做的是对于普通的支持向量机算法的模型形式进行了变形。

他把传统的分类支持向量机写成了结构化分类支持向量机，并且提供了一个定理来证明两者之间的等价性。

粗一看这个等价的结构化分类，支持向量机并没有提供更多有价值的性稀。

然而，这个新的优化目标函数的对偶形式，由于它特殊的稀疏性，使它能够被用来进行大规模的训练。

紧接着，索斯藤又把传统的有序回归支持向量机的优化函数，写成了结构化支持向量机的形式，并且证明了两者的等价性，把两种模型表达成结构化向量机的特例。

之后索斯藤开始把解决结构化向量机的一种算法，切割平面算法，以下称为CP算法，运用到了这两种特例上。

首先，它展示了CP算法在分类问题上的应用。

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

整个流程开始于一个空的工作集合，每一轮优化的是一个基于当前工作集合的支持向量机的子问题。

算法，直到所有的约束条件的误差小于一个全局的参数误差为止。

索斯藤在文章中详细证明了这个算法的有效性和时间复杂度相同的方法，也使得有序回归支持向量机的算法能够转化成为更加计算有效的优化过程。

索斯藤在文章中做了详尽的实验，来展现新算法的有效性。

从数据的角度，它使用了五个不同的数据集，分别是路透社RCV一数据集的好几个子集。

数据的大小。

从六万多数据点到八十多万，数据点不等，特征数也从几十到四万多，特征不等。

这几种不同的数据集还是比较有代表性的。

从方法的比较上来说，索斯滕主要比较了传统的分解方法，有两个方面是重点比较的。

第一就是训练时间。

在所有的数据集上，这篇文章提出的算法都比传统算法快几个数量级提速达到近一百倍。

而有序回归的例子中，传统算法在所有数据集上都无法得到最后结果。

索斯藤进一步展示了训练时间和数据集大小的线性关系，从而验证了提出算法在真实数据上的表现。

第二个重要的比较指标是算法的准确度是否有所牺牲。

因为有时候算法的提速是在牺牲算法精度的基础上做到的。

因此，验证算法的准确度就很有意义。

在这篇文章里，索斯藤展示提出的算法精度，也就是分类准确度，并没有统计意义上的区分度，也让这个算法的有效性有了保证。

索斯腾在他的软件包SVM perf中实现了这个算法。

那么这个软件包一度成了支持向量机研究和开发的标准工具。

今天，我和你分享了索斯腾的这篇论文，堪称支持向量机文献史上的经典。

一起来回顾一下要点。

第一，索斯腾在机器学习领域有三大主要学术贡献。

第二，这篇论文理论论证非常扎实，算法清晰。

而且之后通过有效的实验，完全验证了提出算法的有效性。

文章开启了支持向量机在搜索领域的广泛应用，不愧为二零零六年的KDD最佳论文，以及今年的时间检验奖论文。

随后我给你留一个思考题，在什么应用场景下，线性大规模支持向量机可以有比较好的效果呢？欢迎在评论区留言讨论。