來源：中國計算機學會（ID：ccfvoice)
本文約2400字，建議閱讀5分鐘
這篇文章嘗試用通俗故事的方式講述一個機器學習理論中重要問題的探索歷程。讀者或能從中感受到機器學習理論探索的曲折艱辛，體會到理論進展對算法設計的指引意義。
關鍵詞：機器學習 AdaBoost間隔理論 Boosting學習理論
溯源
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)理論與實踐獎”。
AdaBoost的算法流程非常簡單，用夏柏爾自己的話說，它僅需“十來行代碼(just 10 lines of code)”。但這個算法非常有效，並且經修改推廣能應用於諸多類型的任務。例如，在人臉識別領域被譽為“第一個實時人臉檢測器”、獲得2011年龍格-希金斯(Longuet-Higgins)獎的維奧拉-瓊斯(Viola-Jones)檢測器就是基於AdaBoost研製的。AdaBoost後來衍生出一個龐大的算法家族，統稱Boosting，是機器學習中“集成學習”的主流代表性技術。即便在當今這個“深度學習時代”，Boosting仍發揮著重要作用，例如經常在許多數據分析競賽中打敗深度神經網絡而奪魁的XGBoost，就是Boosting家族中GradientBoost算法的一種高效實現。
我們今天的故事就是關於Boosting學習理論的探索。
異象
機器學習界早就知道，沒有任何一個算法能“包打天下”（注：著名的“沒有免費的午餐”定理，參見周志華《機器學習》，清華大學出版社2016，1.4節）。因此不僅要對算法進行實驗測試，更要進行理論分析，因為有了理論上的清楚刻畫，才能明白某個機器學習算法何時能奏效、為什麼能奏效，而不是純粹“碰運氣”。
希望訓練樣本多，這容易理解。為什麼希望模型複雜度小呢？這是由於機器學習中存在“過擬合”，簡單地說，如果對訓練數據學得“太好了”，反而可能會犯錯誤。例如圖2，在學習“樹葉”時，如果學習器錯誤地認為沒有鋸齒就不是樹葉，這就過擬合了。一般認為，產生過擬合的重要原因之一，就是由於模型過於複雜，導致學得“過度”了、學到了本不該學的訓練樣本的“特性”而非樣本總體的“共性”。
顯然，夏柏爾和弗洛恩德在1997年的理論蘊義與機器學習領域的常識一致，因此很容易得到大家認可。
然而，AdaBoost在實踐中卻呈現出一個奇異的現象：它似乎沒有發生過擬合！
如圖3所示，在訓練誤差到達0之後繼續訓練，雖然模型複雜度在增大，但泛化誤差卻仍會繼續下降。
科學發現中有一個基本方法論：若有多個理論假設符合實驗觀察，則選取最簡潔的。這就是所謂“奧卡姆剃刀(Ocama’s razor)準則”。這個準則在眾多學科史上都發揮了重要作用。然而如果審視AdaBoost的行為，卻可以發現它是如此與眾不同。
如圖3中，訓練到第10輪和第1000輪時形成的假設（集成學習器）都與“實驗觀察”（訓練數據）一致，前者僅包含10個基學習器、後者包含1000個基學習器。顯然，根據奧卡姆剃刀應該選取前者，但實際上後者卻更好。
也就是說，AdaBoost的行為表現不僅違背了機器學習領域的常識，從更廣大的視角看，甚至違背了科學基本準則！
因此，弄清AdaBoost奇異現象背後的道理，不僅能滿足我們的好奇心，還可能揭開機器學習中以前不知道的某種秘密，進而為算法設計打開一扇新門。“AdaBoost為何未發生過擬合？”作為Boosting最關鍵、最引人入勝的基礎理論問題，吸引了諸多知名學者投入其中。
驚蟄
夏柏爾和弗洛恩德很快意識到1997理論中的問題。1998年，他們與後來領導伯克利著名的西蒙斯計算理論研究所的彼得·巴特萊特(Peter Bartlett)和李偉上(Wee Sun Lee)合作發表了一個新的基於“間隔(margin)”的理論。
“間隔”是機器學習中一個非常重要的概念。大致來說，如圖4所示，假定我們用一個劃分超平面把不同類別的樣本分開，那麼某個樣本點與超平面的“距離”就是這個樣本點相對該超平面的“間隔”。考慮所有樣本點相對這個超平面的“最小間隔”，就定義出了“超平面的間隔”。機器學習中著名的支持向量機SVM就是通過優化技術來求解出間隔最大的劃分超平面，換一個角度看，就是試圖使樣本點相對超平面的“最小間隔”儘可能大。
在夏柏爾等人的新理論中，AdaBoost的泛化誤差界包含一個關於間隔的閾值項θ，並且θ出現在分母上；這意味著間隔越大，泛化誤差就可能會越小。這個理論漂亮地解釋了AdaBoost為什麼沒有發生過擬合：這是因為即便訓練誤差達到0，間隔仍有可能增大。如圖4，超平面B已經把兩類訓練樣本點完全分開，其訓練誤差為0；繼續訓練可能找到超平面A，訓練誤差仍為0，但是A的間隔比B更大，所以泛化誤差可以進一步減小。
這項理論在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為何未發生過擬合。但人們認為至少它“活著”、還可以被改善，而間隔理論體系雖有優美的幾何直觀解釋，但它已經“死了”。
續命
七年後，在2006年國際機器學習大會(ICML)上，在普林斯頓大學任教的夏柏爾與耶魯大學的學生列夫·芮因(Lev Reyzin)合作獲得了“傑出論文獎”。獲獎論文做了一件事：把布瑞曼 1999年的實驗重新做一遍。
我們知道，Boosting間隔理論體系除了間隔，必然還會涉及到訓練樣本數和模型複雜度。要討論間隔對泛化誤差的影響，就必須把訓練樣本數和模型複雜度“固定”住。前者容易：指定訓練樣本的個數即可；後者則必須專門處理。
一般認為，決策樹模型複雜度由葉結點的數目決定，因此在1999年實驗中布瑞曼使用了葉結點數目相同的決策樹。芮因和夏柏爾重複了布瑞曼的實驗，發現AdaBoost決策樹雖然與Arc-gv決策樹的葉結點數目相同，但樹的層數卻更多。因此芮因和夏柏爾推測，這些決策樹的複雜度或許不同？
這個發現並不容易，因為這些決策樹的高度差並不大。例如，在各自使用300棵決策樹時，AdaBoost決策樹平均高度約為10.5，僅比Arc-gv決策樹高了約1層。從大量實驗數據中觀察到這麼小的差別，需要相當敏銳的觀察力。
芮因和夏柏爾用僅包含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 Grønlund)、卡斯柏·拉森(Kasper G. Larsen)、萊爾·卡瑪(Lior Kamma)、亞歷山大·馬塞厄森(Alexander Mathiasen)與加州大學伯克利分校的傑拉尼·納爾遜(Jelani Nelson)合作發表了一篇論文（見圖7）。納爾遜是美國總統獎和斯隆研究獎得主，拉森在STOC和FOCS曾兩獲最佳學生論文獎，是理論計算機科學界的新星，卡瑪則畢業於以色列魏茲曼研究所這個計算機科學重鎮。理論計算機科學家出手機器學習理論問題，是近年來的一個重要趨勢。這篇論文最終證明了2013年我們給出的已經幾乎是最緊的泛化誤差上界，至多再改進一個log因子，並且這個上界已經與下界匹配，理論上不可能有更好的結果！
終於，心安了。
劇終
從1998年AdaBoost間隔理論體系萌生，到幾經論爭跌宕得到2013年結果，經過了15年。再經6年得到該結果的定論。如果從故事開頭的1989年算起，整整經歷了30年。故事中的一些主要人物如李奧·布瑞曼已經作古，而當年的研究生已成為教授。最後，本文不加解釋地列出故事中最主要的三個理論結果以志紀念（見圖8）。
圖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]Grønlund A, Kamma L, Larsen K G, et al. Margin-based generalization lower bounds for boosted classifiers[C]// NeurIPS 2019.
注：對理論內容感興趣的讀者可以從[1]中找到主要文獻；對ODM算法感興趣的讀者可參閱[2]；[3]是“定論”一節談到的最新工作。
周志華
CCF會士、常務理事。南京大學教授、計算機系主任、人工智能學院院長、計算機軟件新技術國家重點實驗室常務副主任。
ACM/AAAS/AAAI/IEEE/IAPR Fellow，歐洲科學院外籍院士。主要研究方向為人工智能、機器學習、數據挖掘。
校對：林亦霖
—完—
關注清華-青島數據科學研究院官方微信公眾平臺“ AI數據派 ”及姊妹號“ 數據派THU ”獲取更多講座福利及優質內容。
閱讀更多 數據派THU 的文章
