请选择 进入手机版 | 继续访问电脑版
首页 / 快讯 / 正文
周志华:Boosting学习理论的探索 —— 一个跨越30年的故事
网站编辑004 发表于:2020-4-16 16:53:10 复制链接 看图 发表新帖
阅读数:643
呆板之心转载
泉源:CCF微信公众号 (CCFvoice)
中国盘算机学会通讯 (CCCF)
作者:周志华
这篇文章实验用平凡故事的方式陈诉一个呆板学习理论中告急题目的探索历程。读者或能从中感受到呆板学习理论探索的曲折费力,领会到理论渴望对算法计划的指引意义。
溯源
1989年,哈佛大学的莱斯利·维利昂特(Leslie Valiant,盘算学习理论奠基人、2010年ACM图灵奖得主)和他的门生迈克尔·肯斯(Michael Kearns,厥后继续贝尔实验室人工智能研究部主任)提出了一个公开题目:“弱可学习性是否等价于强可学习性?”
这个题目大抵上是说:假如一个呆板学习任务存在着比“随机推测”略好一点的“弱学习算法”,那么是否就肯定存在着精确率恣意高(与该题目的理论上限恣意靠近)的“强学习算法”?
直觉上这个题目的答案大概是“否定”的,由于我们在现实任务中通常很轻易找到比随机推测稍好一点的算法(比方说精确率到达51%)、却很难找到精确率很高的算法(比方说到达95%)。
出人意料的是,1990年,麻省理工学院的罗伯特·夏柏尔(Robert Schapire)在闻名期刊Machine Learning上发表论文,证实这个题目的答案是“YES”!更令人惊奇的是,他的证实是构造性的!
也就是说,夏柏尔给出了一个过程,直接按这个过程举行利用就能将弱学习算法提升成强学习算法。过程的要点是思量一系列“基学习器”,让“厥后者”重点关注“先行者”轻易堕落的部门,然后再将这些基学习器团结起来。
遗憾的是,这个过程仅具备理论意义,并非一个能付诸实践的实用算法,由于它要求知道一些实践中难以事先得知的信息,比方说在办理一个题目之前,先要知道这个题目的最优解有多好。
厥后夏柏尔到了新泽西的贝尔实验室工作,在这里遇见加州大学圣塔克鲁兹分校毕业的约夫·弗洛恩德(Yoav Freund)。凑巧的是,弗洛恩德曾经研究过多学习器的团结。两人开始互助。终于,他们在1995年欧洲盘算学习理论集会(注:该集会已经并入COLT)发表了一个实用算法,完备版于1997年在Journal of Computer and System Sciences发表。这就是闻名的AdaBoost。夏柏尔和弗洛恩德因这项工作获2003年“哥德尔奖”、2004年“ACM帕里斯·卡内拉基斯(Paris Kanellakis)理论与实践奖”。
周志华:Boosting学习理论的探索 —— 一个跨越30年的故事_网站编辑004于2020-04-16 16:53:10发布在理财客_互联网理财小白首选之站|http://www.licaiker.com/thread-53846-1-1.html

AdaBoost的算法流程非常简朴,用夏柏尔自己的话说,它仅需“十来行代码(just 10 lines of code)”。但这个算法非常有效,而且经修改推广能应用于诸多范例的任务。比方,在人脸辨认范畴被誉为“第一个实时人脸检测器”、得到2011年龙格-希金斯(Longuet-Higgins)奖的维奥拉-琼斯(Viola-Jones)检测器就是基于AdaBoost研制的。AdaBoost厥后衍生出一个巨大的算法眷属,统称Boosting,是呆板学习中“集成学习”的主流代表性技能。即便在当今这个“深度学习期间”,Boosting仍发挥偏告急作用,比方经常在许多数据分析比赛中打败深度神经网络而夺魁的XGBoost,就是Boosting眷属中GradientBoost算法的一种高效实现。
我们本日的故事就是关于Boosting学习理论的探索。
异象
呆板学习界早就知道,没有任何一个算法能“包打天下”(注:闻名的“没有免费的午餐”定理,拜见周志华《呆板学习》,清华大学出书社2016,1.4节)。因此不光要对算法举行实验测试,更要举行理论分析,由于有了理论上的清晰描绘,才气明确某个呆板学习算法何时能收效、为什么能收效,而不是纯粹“碰运气”。
1997年,夏柏尔和弗洛恩德给出了AdaBoost的第一个理论分析。他们证实,AdaBoost的训练毛病随训练轮数增长而指数级降落,这意味着算法收敛很快。对于各人最关心的泛化性能,即算法在处理惩罚新的、没见过的数据时的性能,他们的结论是:AdaBoost的泛化毛病
周志华:Boosting学习理论的探索 —— 一个跨越30年的故事_网站编辑004于2020-04-16 16:53:10发布在理财客_互联网理财小白首选之站|http://www.licaiker.com/thread-53846-1-1.html

训练毛病
周志华:Boosting学习理论的探索 —— 一个跨越30年的故事_网站编辑004于2020-04-16 16:53:10发布在理财客_互联网理财小白首选之站|http://www.licaiker.com/thread-53846-1-1.html


周志华:Boosting学习理论的探索 —— 一个跨越30年的故事_网站编辑004于2020-04-16 16:53:10发布在理财客_互联网理财小白首选之站|http://www.licaiker.com/thread-53846-1-1.html

隐去了相对不太告急的其他项),这里的m是训练样本数,T是训练的轮数,
周志华:Boosting学习理论的探索 —— 一个跨越30年的故事_网站编辑004于2020-04-16 16:53:10发布在理财客_互联网理财小白首选之站|http://www.licaiker.com/thread-53846-1-1.html

可以大抵明白为基学习器的复杂度。由于AdaBoost每训练一轮就增长一个基学习器,以是
周志华:Boosting学习理论的探索 —— 一个跨越30年的故事_网站编辑004于2020-04-16 16:53:10发布在理财客_互联网理财小白首选之站|http://www.licaiker.com/thread-53846-1-1.html

大抵相称于终极集成学习器的复杂度。于是,这个理论效果告诉我们:训练样本多些好,模子复杂度小些好。
渴望训练样本多,这轻易明白。为什么渴望模子复杂度小呢?这是由于呆板学习中存在“过拟合”,简朴地说,假如对训练数据学得“太好了”,反而大概会犯错误。比方图2,在学习“树叶”时,假如学习器错误地以为没有锯齿就不是树叶,这就过拟合了。一样平常以为,产生过拟合的告急缘故起因之一,就是由于模子过于复杂,导致学得“太过”了、学到了本不应学的训练样本的“特性”而非样本总体的“共性”。
周志华:Boosting学习理论的探索 —— 一个跨越30年的故事_网站编辑004于2020-04-16 16:53:10发布在理财客_互联网理财小白首选之站|http://www.licaiker.com/thread-53846-1-1.html

显然,夏柏尔和弗洛恩德在1997年的理论蕴义与呆板学习范畴的知识划一,因此很轻易得到各人认可。
然而,AdaBoost在实践中却出现出一个奇异的征象:它好像没有发生过拟合!
如图3所示,在训练毛病到达0之后继续训练,固然模子复杂度在增大,但泛化毛病却仍会继续降落。
科学发现中有一个根本方法论:如有多个理论假设符合实验观察,则选取最简便的。这就是所谓“奥卡姆剃刀(Ocama’s razor)准则”。这个准则在浩繁学科史上都发挥了告急作用。然而假如审阅AdaBoost的举动,却可以发现它是云云与众差异。
如图3中,训练到第10轮和第1000轮时形成的假设(集成学习器)都与“实验观察”(训练数据)划一,前者仅包罗10个基学习器、后者包罗1000个基学习器。显然,根据奥卡姆剃刀应该选取前者,但现实上后者却更好。
周志华:Boosting学习理论的探索 —— 一个跨越30年的故事_网站编辑004于2020-04-16 16:53:10发布在理财客_互联网理财小白首选之站|http://www.licaiker.com/thread-53846-1-1.html

也就是说,AdaBoost的举动体现不光违反了呆板学习范畴的知识,从更广大的视角看,以致违反了科学根本准则!
因此,弄清AdaBoost奇异征象背后的原理,不光能满意我们的好奇心,还大概揭开呆板学习中从前不知道的某种秘密,进而为算法计划打开一扇新门。“AdaBoost为何未发生过拟合?”作为Boosting最关键、最引人入胜的底子理论题目,吸引了诸多着名学者投入此中。
惊蛰
夏柏尔和弗洛恩德很快意识到1997理论中的题目。1998年,他们与厥后向导伯克利闻名的西蒙斯盘算理论研究所的彼得·巴特莱特(Peter Bartlett)和李伟上(Wee Sun Lee)互助发表了一个新的基于“隔断(margin)”的理论。
“隔断”是呆板学习中一个非常告急的概念。大抵来说,如图4所示,假定我们用一个分别超平面把差异种别的样天职开,那么某个样本点与超平面的“隔断”就是这个样本点相对该超平面的“隔断”。思量全部样本点相对这个超平面的“最小隔断”,就界说出了“超平面的隔断”。呆板学习中闻名的支持向量机SVM就是通过优化技能来求解出隔断最大的分别超平面,换一个角度看,就是试图使样本点相对超平面的“最小隔断”尽大概大。
在夏柏尔等人的新理论中,AdaBoost的泛化毛病界包罗一个关于隔断的阈值项θ,而且θ出现在分母上;这意味着隔断越大,泛化毛病就大概会越小。这个理论美丽地表明白AdaBoost为什么没有发生过拟合:这是由于即便训练毛病到达0,隔断仍有大概增大。如图4,超平面B已经把两类训练样本点完全分开,其训练毛病为0;继续训练大概找到超平面A,训练毛病仍为0,但是A的隔断比B更大,以是泛化毛病可以进一步减小。
周志华:Boosting学习理论的探索 —— 一个跨越30年的故事_网站编辑004于2020-04-16 16:53:10发布在理财客_互联网理财小白首选之站|http://www.licaiker.com/thread-53846-1-1.html

这项理论在1998年发表,刚幸亏那一年,多特蒙德大学的托斯腾·约阿希姆斯(Thorsten Joachims)在欧洲呆板学习大会上报道了支持向量机在文天职类任务上显现出杰出性能,呆板学习范畴正式进入“统计学习期间”,而“隔断”正是支持向量机的核心概念。从隔断的角度来表明AdaBoost的举动,无形中使呆板学习的“集成学习”与“统计学习”这两大流派走到了一起。
风趣的是,统计学习奠基人、支持向量机发明人弗拉基米尔·N.瓦普尼克(Vladimir N. Vapnik)在1990年(苏联瓦解前一年)离开苏联来到新泽西的贝尔实验室工作,夏柏尔和弗洛恩德互助时与瓦普尼克是同事,大概受到了他的影响。
冰封
夏柏尔等人在1998论文末端说,他们与李奥·布瑞曼(Leo Breiman)举行了“沉痛(poignant)”的互换。用这个词形容学术互换很少见。给他们带来沉痛感的正是被誉为“二十世纪巨大的统计学家”的加州大学伯克利分校的布瑞曼传授,他不光是统计学范畴巨擘,照旧呆板学习中闻名的集成学习方法Bagging和“随机丛林”的发明人。
1999年,布瑞曼的独立署名论文提出了一个新理论。这个理论也是基于“隔断”来对AdaBoost举行描绘,但是与夏柏尔等人1998理论差异的是,布瑞曼理论的着眼点是“最小隔断”,基于这个隔断物理量,布瑞曼得到了比夏柏尔等人“更紧”的泛化毛病界,是Boosting隔断理论体系中一个新的里程碑。
在学习理论中,“更紧的界”通常意味着“更本质的物理量”。上一节谈到过,“最小隔断”取决于最靠近分别超平面的样本点,而闻名的支持向量机就是在积极探求使得“最小隔断”最大的分别超平面。以是,布瑞曼理论显现出“最小隔断”竟然也是AdaBoost的关键,这使人们感到“醍醐灌顶”。
到此统统都很精美,只需认可:Boosting隔断理论体系的关键在于“最小隔断”就OK了。
然而,布瑞曼不光理论造诣深厚,照旧一位豪情密切的呆板学习算法发明者。既然证实白“最小隔断”是关键,而AdaBoost跟最小隔断的关联是通过复杂的理论分析才发现的,也就是说,AdaBoost并非“直接”优化最小隔断,那么何不发明一个直接优化最小隔断的新型Boosting算法呢?理论上来说这算法应该会比AdaBoost更强大。
于是,布瑞曼在1999年发明白一个新算法Arc-gv。可以从理论上证实,这个算法可以大概使最小隔断到达最优。同时,布瑞曼的大量实验也验证了该算法对应的“最小隔断”总是大于AdaBoost的“最小隔断”。然而,实验却体现出Arc-gv的泛化毛病大于AdaBoost!
这就希奇了。已经证实白Boosting隔断理论体系的关键是“最小隔断”,现在Arc-gv的“最小隔断”无论在理论上照旧在实验上都优于AdaBoost,那么Arc-gv算法的泛化性能应该更好啊,为什么反倒不如AdaBoost呢?!
证实过程无误。这就意味着,把“隔断”作为基石是错误的。因此,布瑞曼的工作不啻于宣告了Boosting隔断理论体系的“极刑”。
Boosting隔断理论体系由此进入“冰封年代”。研究者纷纷转向其他理论体系,此中最告急的是名著The Elements of Statistical Learning作者、斯坦福大学三位各人杰罗姆·弗里德曼(Jerome Friedman)、特莱沃尔·哈斯蒂(Trevor Hastie)、罗伯特·提比希阿尼(Robert Tibshirani)提出的“统计视角(Statistical View)”理论。这一派理论也有不少争议,尤其是未能清晰表明AdaBoost为何未发生过拟合。但人们以为至少它“在世”、还可以被改善,而隔断理论体系虽有精美的多少直观表明,但它已经“死了”。
周志华:Boosting学习理论的探索 —— 一个跨越30年的故事_网站编辑004于2020-04-16 16:53:10发布在理财客_互联网理财小白首选之站|http://www.licaiker.com/thread-53846-1-1.html

续命
七年后,在2006年国际呆板学习大会(ICML)上,在普林斯顿大学任教的夏柏尔与耶鲁大学的门生列夫·芮因(Lev Reyzin)互助得到了“良好论文奖”。获奖论文做了一件事:把布瑞曼 1999年的实验重新做一遍。
我们知道,Boosting隔断理论体系除了隔断,肯定还会涉及到训练样本数和模子复杂度。要讨论隔断对泛化毛病的影响,就必须把训练样本数和模子复杂度“固定”住。前者轻易:指定训练样本的个数即可;后者则必须专门处理惩罚。
一样平常以为,决定树模子复杂度由叶结点的数量决定,因此在1999年实验中布瑞曼利用了叶结点数量雷同的决定树。芮因和夏柏尔重复了布瑞曼的实验,发现AdaBoost决定树固然与Arc-gv决定树的叶结点数量雷同,但树的层数却更多。因此芮因和夏柏尔推测,这些决定树的复杂度大概差异?
这个发现并不轻易,由于这些决定树的高度差并不大。比方,在各自利用300棵决定树时,AdaBoost决定树均匀高度约为10.5,仅比Arc-gv决定树高了约1层。从大量实验数据中观察到这么小的差异,须要相称敏锐的观察力。
周志华:Boosting学习理论的探索 —— 一个跨越30年的故事_网站编辑004于2020-04-16 16:53:10发布在理财客_互联网理财小白首选之站|http://www.licaiker.com/thread-53846-1-1.html

芮因和夏柏尔用仅包罗2个叶结点的单层决定树(亦称“决定树桩”)作为基学习器重新做了实验。他们发现,固然Arc-gv的最小隔断始终大于AdaBoost,但是若思量样本总体,则AdaBoost的隔断比Arc-gv更大一些。比方从图6中可以看到AdaBoost的曲线更“靠右”,这意味着有更多的样本点取得较大的隔断值。于是芮因和夏柏尔断言,“最小隔断”并非Boosting隔断理论体系的关键,告急的是隔断的总体分布。他们推测,大概“隔断均值”或“隔断中位数”是关键物理量,但并未给出理论证实。
一样平常读者本日看这篇论文大概会感到很惊奇:它既没有提出新理论,也没有提出新算法,也没有新应用,这个“三无”论文居然得到了ICML良好论文奖?
这项工作的意义必须放到Boosting理论探索的团体图景中去观察:它体现出布瑞曼对Boosting隔断理论体系的致命打击,至少此中的实验部门并未“实锤”!
那么,芮因和夏柏尔的工作使Boosting隔断理论体系“活过来了”吗?还没有。由于布瑞曼的重要攻击来自于他的理论效果,实验起的是“验证”作用。因此,Boosting隔断理论体系想逃生,就必须有新理论,基于“最小隔断”之外的隔断物理量证实出比布瑞曼更紧的泛化毛病界。
磨砺
2008年,北京大学的王立威博士、封举富传授、杨成同砚和厥后继续日本RIKEN人工智能研究中心主任的杉山将(Masashi Sugiyama)与笔者互助,在COLT集会发表了一篇论文。这篇论文提出了“均衡隔断”的概念,而且基于它证实出一个比布瑞曼更紧的泛化毛病界。由于“均衡隔断”差异于最小隔断,因此不少学者以为Boosting理论题目办理了。
然而,笔者心有不安。一方面,在“均衡隔断”理论证实过程中用到的信息与夏柏尔和布瑞曼有所差异,相应的效果未必能直接比力;另一方面,更告急的是,“均衡隔断”是从数学上“强行”界说出来的一个概念,我们说不清它的直观物理寄义是什么。
回顾笔者研究Boosting理论题目的初心,是渴望通过弄清晰“AdaBoost为何未发生过拟合”来为新的呆板学习算法计划得到启发。假如新理论的关键概念缺乏直观物理寄义,那么就很难启发算法计划了。因此,笔者继续思索着。
2008年,南开大学组合数学中心的高尉同砚(现南京大学人工智能学院副传授)跟笔者接洽攻读博士学位,被笔者拽进了AdaBoost题目。当时估计一年应能办理。然而困难高出预期,三年下来仅基于一个走偏的小效果发表了一篇集会论文。博士生究竟有毕业文章压力,感觉“断港绝潢”了。笔者心田也很惶惑,但照旧必须斗志高昂地鼓劲。幸好笔者手上尚有另一个告急理论题目,高尉在这个题目上发表了一篇颇有影响的COLT文章,稍缓解压力,可以大概继续前行。
几经磨砺,终于在2013年我们在Artificial Intelligence发表了一个新理论,相应的泛化毛病界比夏柏尔和布瑞曼的更紧,这确证了“最小隔断”并非Boosting隔断理论体系的关键物理量。故意思的是,以往以为应该存在“某个”关键的隔断物理量,而我们的新理论显现出:应该使得“均匀隔断”最大化、同时使“隔断方差”最小化,也就是说,关键物理量并非一个,而是两个!
AdaBoost为何未发生过拟合?为安在训练毛病到达0之后继续训练仍能得到更好的泛化性能?新理论给出了答案:由于AdaBoost在训练过程中随着轮数的增长,不光使均匀隔断增大,还同时使隔断方差变小。同时,这也意味着AdaBoost终极仍有大概发生过拟合,只不外很迟——当均匀隔断已无法再增大、隔断方差也无法进一步减小时。
众所周知,以支持向量机为代表的一大类统计学习方法都在试图最大化“最小隔断”,而这个新理论显现:若能最大化“均匀隔断”同时最小化“隔断方差”,得到的学习器会更好!于是,笔者的博士生张腾同砚(现华中科技大学盘算机学院西席)等开始了这方面的探索。2014年开始的5年里,我们创建起“最优隔断分布学习机(Optimal margin Distribution Machine, ODM)”这个新的算法族,包罗二分类、多分类、聚类、半监督等学习算法,这些受新理论启发的算法工作不属于本文重点,就不赘述了。
定论
2013年的工作引起了许多反响,如在2014年国际人工智能大会(AAAI)上,国际人工智能学会主席、卡内基梅隆大学呆板学习系主任曼纽拉·维罗索(Manuela Veloso)传授的Keynote陈诉将它作为人工智能范畴的告急渴望先容,称其“使隔断理论复兴(renascence)”“为学习算法计划带来了新洞察(new insight)”。
然而,笔者仍有隐忧。固然2013理论相应的泛化毛病界在当时是最紧致的,但以后会不会有人基于其他的隔断物理量得到更紧的界,导致我们关于“AdaBoost为何未发生过拟合”的答案和“最大化均匀隔断同时最小化隔断方差”的算法引导头脑被颠覆呢?
六年后,在2019年底的NeurIPS集会上,丹麦奥胡斯大学的阿兰·格洛隆德(Allan Grnlund)、卡斯柏·拉森(Kasper G. Larsen)、莱尔·卡玛(Lior Kamma)、亚历山大·马塞厄森(Alexander Mathiasen)与加州大学伯克利分校的杰拉尼·纳尔逊(Jelani Nelson)互助发表了一篇论文(见图7)。纳尔逊是美国总统奖和斯隆研究奖得主,拉森在STOC和FOCS曾两获最佳门生论文奖,是理论盘算机科学界的新星,卡玛则毕业于以色列魏兹曼研究所这个盘算机科学重镇。理论盘算机科学家脱手呆板学习理论题目,是比年来的一个告急趋势。这篇论文终极证实白2013年我们给出的已经险些是最紧的泛化毛病上界,至多再改进一个log因子,而且这个上界已经与下界匹配,理论上不大概有更好的效果!
终于,心安了。
周志华:Boosting学习理论的探索 —— 一个跨越30年的故事_网站编辑004于2020-04-16 16:53:10发布在理财客_互联网理财小白首选之站|http://www.licaiker.com/thread-53846-1-1.html

剧终
从1998年AdaBoost隔断理论体系萌生,到几经论争跌荡得到2013年效果,颠末了15年。再经6年得到该效果的定论。假如从故事开头的1989年算起,整整履历了30年。故事中的一些重要人物如李奥·布瑞曼已经作古,而当年的研究生已成为传授。末了,本文不加表明地列出故事中最重要的三个理论效果以志吊唁(见图8)。
周志华:Boosting学习理论的探索 —— 一个跨越30年的故事_网站编辑004于2020-04-16 16:53:10发布在理财客_互联网理财小白首选之站|http://www.licaiker.com/thread-53846-1-1.html

图8 本文提到的最重要的3个理论效果
参考文献
[1]Zhou Z H. Large margin distribution learning[C]// ANNPR 2014.(keynote article)
[2]Zhang T, Zhou Z H. Optimal margin distribution machine[J]. IEEE Transactions on Knowledge and Data Engineering, DOI:10.1109/TKDE.2019.2897662.
[3]Grnlund A, Kamma L, Larsen K G, et al. Margin-based generalization lower bounds for boosted classifiers[C]// NeurIPS 2019.
注:对理论内容感爱好的读者可以从[1]中找到重要文献;对ODM算法感爱好的读者可参阅[2];[3]是“定论”一节谈到的最新工作。
作者简介
周志华:Boosting学习理论的探索 —— 一个跨越30年的故事_网站编辑004于2020-04-16 16:53:10发布在理财客_互联网理财小白首选之站|http://www.licaiker.com/thread-53846-1-1.html

周志华:CCF会士、常务理事。南京大学传授、盘算机系主任、人工智能学院院长、盘算机软件新技能国家重点实验室常务副主任。
ACM/AAAS/AAAI/IEEE/IAPR Fellow,欧洲科学院外籍院士。重要研究方向为人工智能、呆板学习、数据发掘。
接洽方式:[email protected]

文章来自理财客-www.licaiker.com 网络收集整理
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
条评论
您需要登录后才可以回帖 登录 | 立即注册
高级
相关推荐
©2001-2018 理财客_理财小白的首选之站 http://www.licaiker.com/中国互联网举报中心非经营性网站互联网理财综合门户网-理财客公安网备 地图索引 网站地图 网站地图1 网站地图2 网站地图3 网站标签
站点统计Archiver手机版小黑屋广告合作客服QQ:1259985689 理财客