资讯 业界
此为临时链接,仅用于文章预览,将在时失效

北京大学王立威教授:机器学习理论的回顾与展望(三)

作者:夏睿
2017/03/09 09:29

雷锋网[AI科技评论]按:本文根据王立威教授在中国人工智能学会AIDL第二期人工智能前沿讲习班*机器学习前沿所作报告《机器学习理论:回顾与展望》编辑整理而来,雷锋网在未改变原意的基础上略作了删减。

北京大学王立威教授:机器学习理论的回顾与展望(三)

王立威

立威,在北京大学教授主要研究领域为机器学习。在包括COLT, NIPS,JMLR, PAMI等权威会议期刊发表论文60余篇。2010年入选 AI’s 10 to Watch,是首位获得该奖项的亚洲学者。2012年获得首届国家自然科学基金优秀青年基金,新世纪优秀人才。任 NIPS 等权威会议 Area Chair,和多家学术期刊编委。以下为王立威教授所做的现场演讲的第三部分,主要阐述了Margin Theory,算法稳定性等相关问题,并对深度学习算法展开了一些讨论。

北京大学王立威教授:机器学习理论的回顾与展望(三)

| Margin Theory介绍

接下来给大家介绍机器学习中第二个比较重要的理论——Margin Theory。

北京大学王立威教授:机器学习理论的回顾与展望(三)

Margin Theory和VC Theory有何区别?

VC Theory和算法关系不大,它刻画的是集合的复杂程度;

Margin Theory则不同,它牵扯到很多算法,后面我介绍的Margin Theory就是完全在刻画算法。所以大家要理解,机器学习理论的发展,是先从刻画一些结构的性质,再逐渐变化到刻画算法本身。

我认为当前,尤其对深度学习来说,最有价值的学习理论一定是在刻画深度学习算法本身的性质。当然你的模型复杂程度也有用,但那可能不是最主要的。

Margin是什么?

Margin Theory大家可能都听说过,像SVM、Boosting这样的方法都包含有Large Margin的概念。它到底是什么含义呢?

Margin Theory在SVM中怎么用大家都比较熟悉了,想象一下:

比如空间中有正负两类点,现在要找一条线把这两类点分开。需要找一种个分法使得这两类点分完了以后,离分类面的间距越大越好,而这个间距就叫Margin。

而对于Boosting来讲,也有类似的概念。我前面也讲到,Boosting就是由许多基本分类器把线性组合起来而得到的一个最终结果。

Margin有什么作用?

比如你组合了100个分类器,你要看这100个分类器里面究竟有多少是把这个数据看成正的点,有多少是看成负的。

  • 如果50%判成正的、50%判成负的,实际上这个判别结果对数据就没有Margin,Margin就是0;

  • 如果百分之百的判成正的,Margin就非常大。

所以大家可以领会一下,Boosting的Margin实际上体现了这个Boosting所用的基本分类器对数据分类结果的置信度(confidence)如果百分之百都分成正的这一类,说明这个结果的置信度非常高;如果接近50%,则说明置信度非常低。所以,这个置信度就是用Margin来表示的,它实际上对泛化能力起到了非常重要的影响。

为什么会开始研究Margin Theory?

大家最开始用VC Theory研究Boosting的时候,理论结果肯定是综合越多的基本分类器,泛化效果越差。但实际上实验结果却是,综合了几千个基本分类器之后,泛化性能不仅没有变差,还在不断变好。这看起来就很奇怪,因此也引导人们去思考,不仅要考虑模型的复杂程度,还要考虑算法本身是否也对泛化产生影响。 

从直观上理解:如何用Margin刻画泛化?

Margin既可以对SVM刻画泛化,也可以对Boosting刻画泛化。不过我们先把所有这些理论都忘掉,单纯从直观的角度来思考。

现在大家有这样两种情形大家来比较一下:

  • 第一种情形,我现在有一个分类器,它对绝大部分的数据都有一个很大的置信度,要么是全部分成正类,要么全部分成负类。用Margin语言来说,就是对于绝大部分数据Margin都很大;

  • 第二种情形,对于绝大部分数据来说Margin都很小,基本上都是只比50%稍微多一点。

这两种分类器虽然差别很大,但是我们假定这两种情况在训练数据上的训练错误率是完全相同的。

训练错误率只能表示把数据分对还是分错了,而置信度实际上则代表了具体分类值的大小。大家想想,在训练错误率完全相同的前提下,是置信度大的更可能有强泛化能力,还是说置信度小的可能性更大?即使从非常直觉的角度,不用通过任何理论你也能知道,一定是置信度大的泛化能力更大。Margin Theory就是把刚才那个很直观的想法建立在精确的数学基础上,再用严密的语言给表述出来。

北京大学王立威教授:机器学习理论的回顾与展望(三)

对数学很感兴趣的同学可以去看里面数学具体的证明;如果对这个没有兴趣的,就理解我刚才讲的。就是说对于分类结果,千万不要只看训练错误率这么一个简单的数字,你要关注Margin。Margin代表了置信度,而置信度对泛化能力有相当重大的作用。

我和周志华老师一起合作过很多工作,特别是在解释Boosting这方面。这大概是将近十年前做的工作。后来周老师和他的学生又做了很多更深入、更精致的一些工作。所以如果大家感兴趣的话可以参阅一下这方面的论文。

| 对Margin Theory的总结

VC Theory是宏观的,它是对问题的一种最简单的表述,只考虑算法对每个数据判对还是判错和模型的复杂程度,用这两点来刻画泛化。

Margin Theory告诉大家要更关注算法的信息,算法会输出很多置信度方面的信息。

其实在今天的深度学习里面,同样有这个问题: 深度学习最后输出的不光是对错,而是输出了一个实数值,这个值本身含有一定的信息量,这个值的大小在某种程度上其实也反映了置信度的大小。作为研究内容大家可以去探讨一下,这个值对于深度学习的泛化能力有什么样作用。

从Boosting发展历程中,收获了什么启发?

刚才我们讲了Margin Theory对SVM、对Boosting都是适用的,大家还可以探讨一下两者之间的关系。

下面是一个关于Boosting针对具体的Margin理论给出的数学的表达式,这个表达式比较复杂的,最初是由Boosting的提出者Freund和Schapire提出来的。这个里面其实还有很多的故事。

北京大学王立威教授:机器学习理论的回顾与展望(三)

简单说一下这里面的故事。

Boosting其实很有趣,大家如果回顾一下机器学习的发展历史,你会发现历史总是在不断重复的发生。大概在1995、1996年,人们提出了adaBoost算法。这个算法提出来之后大家觉得,怎么这么简单的一个组合就能大幅度提升性能了呢?这看起来就像魔术,像今天的深度学习一样。它的方法其实就是把基本的分类器组合起来。现在没有人能够解释为什么深度学习在实际中就是有这么好的效果,而当年adaBoost算法刚刚出来的时候也是如此。不过很快,adaBoost的提出者Freund和Schapire他们两个人就给出了理论Margin Theory,从数学上证明其原因是Boosting能够得到一个分类器,而它的Margin很大。

但是不久之后,随机森林和bagging的提出者Leo Breiman又提出一个理论,叫Minimum Margin。这个理论在定量方面做得更好,但是在实验结果上却和理论恰好相反——理论上更好的Boosting算法,反倒没有理论上不太好的Boosting算法的实验结果表现得好。所以大家能理解了,这个时候的实验结果和理论预测是完全矛盾的,那到底应该是相信实验还是相信理论呢?这时我们就必须本着实事求是的精神,百分之百的尊重实验结果:肯定是理论上出了什么问题。所以Breiman得出一个结论:Margin Theory肯定是有极大问题的,它不能解释实际的现象。

北京大学王立威教授:机器学习理论的回顾与展望(三)

很多年以后,通过学者们,包括我和周志华老师,在这方面做的一些研究,我们发现这个理论其实并没有问题,问题在于之前的理论在定量的意义上没有做到最好。你把定量做的更加深入、更加精细之后,就会发现Margin的理论和试验观测就统一了。所以Boosting发展历程的故事对我个人的一个启发是,其实有的时候算法的提出是会比理论超前的,adaBoosting就是一个很典型的例子。但是不要着急,我们慢慢的深入研究它、理解它,我相信对深度学习是一样的,应该在不久的将来,我们从理论上会对深度学习有一个更深刻的认识。

关于王教授及其他教授的主题报告,敬请期待雷锋网的后续报道。

长按图片保存图片,分享给好友或朋友圈

北京大学王立威教授:机器学习理论的回顾与展望(三)

扫码查看文章

正在生成分享图...

取消
相关文章