雷鋒網［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中怎麼用大家都比較熟悉了， 想像一下：
比如空間中有正負兩類點， 現在要找一條線把這兩類點分開。 需要找一種個分法使得這兩類點分完了以後，
而對於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就是一個很典型的例子。但是不要著急，我們慢慢的深入研究它、理解它，我相信對深度學習是一樣的，應該在不久的將來，我們從理論上會對深度學習有一個更深刻的認識。
關於王教授及其他教授的主題報告，敬請期待雷鋒網的後續報導。
要麼是全部分成正類，要麼全部分成負類。用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就是一個很典型的例子。但是不要著急，我們慢慢的深入研究它、理解它，我相信對深度學習是一樣的，應該在不久的將來，我們從理論上會對深度學習有一個更深刻的認識。
關於王教授及其他教授的主題報告，敬請期待雷鋒網的後續報導。