雷鋒網(wǎng)［AI科技評論］按：本文根據(jù)王立威教授在中國人工智能學會AIDL第二期人工智能前沿講習班＊機器學習前沿所作報告《機器學習理論：回顧與展望》編輯整理而來，雷鋒網(wǎng)在未改變原意的基礎上略作了刪減。

王立威

王立威，在北京大學教授主要研究領域為機器學習。在包括COLT, NIPS，JMLR, PAMI等權(quán)威會議期刊發(fā)表論文60余篇。2010年入選 AI’s 10 to Watch，是首位獲得該獎項的亞洲學者。2012年獲得首屆國家自然科學基金優(yōu)秀青年基金，新世紀優(yōu)秀人才。任 NIPS 等權(quán)威會議 Area Chair，和多家學術(shù)期刊編委。以下為王立威教授所做的現(xiàn)場演講的第四部分，主要覆蓋Algorithmic Stability的介紹。

| 算法穩(wěn)定性

我們接下來談談第三個比較重要的學習理論，叫Algorithmic Stability（算法穩(wěn)定性）。

算法穩(wěn)定性是什么？

剛剛我們談到了機器學習理論的發(fā)展，從最開始幾乎不關心算法，只考慮模型的復雜度，慢慢到Margin，實際上已經(jīng)和算法有關，而Algorithmic Stability其實完全就是探討算法性質(zhì)，我這個算法究竟具備了一個什么樣的特點，從而導致我們能夠有一個好的泛化能力。

什么叫做Algorithmic Stability呢？我們還是從比較宏觀的角度來考慮，細節(jié)大家回去以后自己去看。簡而言之，怎樣的算法是stable的？它的核心是說，當算法用一個訓練數(shù)據(jù)集可以訓練出一個結(jié)果，假如我的訓練數(shù)據(jù)集有1萬個數(shù)據(jù)，我把其中9999個都保持不變，就把其中的1個數(shù)據(jù)換成一個新的，那么這個時候你的學習算法學出來的分類器會不會有一個顯著的變化？如果沒有顯著的變化，那么這個學習算法是stable的。如果有顯著變化，我們說這個算法是不stable的。

Algorithmic Stability，就是從定量的角度上來刻畫以下的關系：當換掉其中一個訓練數(shù)據(jù)時，算法學出來的結(jié)果會有多大的改變。

穩(wěn)定的算法會有更好的泛化能力

大家覺得，是比較stable的算法會有更好的泛化能力呢，還是說一個不stable的算法有比較好的泛化能力呢？從直覺上思考一下，顯然是stable的算法有很好的泛化能力。

我還拿最開始的“胡克定律”來說明。如果是一個線性的模型，訓練數(shù)據(jù)更換一個，其實這條直線不會有顯著的變化；如果我有100個數(shù)據(jù)，用99階多項式來匹配這100個數(shù)據(jù)，假如把這100個數(shù)據(jù)換掉一個，我相信新的99階多項式可能就會發(fā)生重大的改變。所以大家要從新的角度，也就是算法的穩(wěn)定性來刻畫。

算法穩(wěn)定性理論是一個很定量的描述：如果我的算法具有一個什么樣的程度的穩(wěn)定性，那么算法的生成范圍就能有什么樣的表征，我們就能給出一個數(shù)學領域的嚴謹描述，一個定量的刻畫。具體的內(nèi)容我就跳過去了。

SVM與SGD，算法穩(wěn)定性如何？

我在講這個算法穩(wěn)定性比較新的內(nèi)容之前，先說一說一些很傳統(tǒng)的算法，有一些是穩(wěn)定性很好的。

舉個例子，SVM的穩(wěn)定性很好。SVM可以從數(shù)學上證明，如果換掉其中的一個訓練數(shù)據(jù)，其實你得到的結(jié)果通常發(fā)生的改變是比較小的，是1/√n的級別，n是數(shù)據(jù)的量。如果改變一個數(shù)據(jù)只是1/√n級別的變化，那么它的算法穩(wěn)定性很好。什么樣的算法穩(wěn)定性很不好呢？比如說以前有一個算法叫決策樹（decision tree），假如換掉其中一個數(shù)據(jù)，有可能決策樹就完全變掉了。

所以從這個算法說回今天我們最常用的方法上。今天大家很多人都在用深度學習（Deep Learning），訓練深度學習，大家是用什么樣的算法在訓練Deep Learning呢？最常用的算法就是SGD（隨機梯度下降）。我們來問問大家，SGD這個算法究竟是一個stable的算法還是一個不stable的算法？你從直覺上先想一下，梯度下降（GD）是在當前求它的梯度，沿梯度下降的方向走一小步。由于我求GD很費勁，所以我們從隨機角度入手，對某一個數(shù)據(jù)點求一個梯度，這就是一個SGD。

SGD這個算法有沒有穩(wěn)定性呢？這是2016年去年的一個結(jié)果（上圖），SGD這個算法具有一定的穩(wěn)定性，如果你在一個convex function上用SGD它的穩(wěn)定性相當好。通常大家都知道，深度學習的損失函數(shù)是非凸的,而仍然可以證明SGD是具有一定的穩(wěn)定性的，雖然在理論上可能暫時還證明不出來它具有非常高的穩(wěn)定性，但是它能有一個還不錯的穩(wěn)定性，在實際中它是不是有穩(wěn)定性？我認為如果是做研究的老師、同學們其實可以去思考這個問題，這個如果做深度學習是一個比較重要的成果。

深度學習算法

接下來我們可以簡單地總結(jié)一下深度學習算法。很多深度學習做應用的人會覺得，傳統(tǒng)的機器學習理論無法解釋今天深度學習的成功，因為今天的深度學習在很多方法跟傳統(tǒng)的機器學習理論看上去是矛盾的。

我舉個例子，今天大家用的這個深度學習的網(wǎng)絡，它的VC Dimension是多少？數(shù)學上可以證明，如果用全連接的網(wǎng)絡，它的VC Dimension基本上就是它的編的數(shù)目，可是今天我們用的網(wǎng)絡，通常編的數(shù)目是我們訓練數(shù)據(jù)要高一個數(shù)量級，編的數(shù)目就是我們參數(shù)的個數(shù)，所以實際上我們是在一個什么樣的模型中間去學習呢？是在一個VC Dimension大概是10倍于訓練數(shù)據(jù)的空間在做，這跟我們之前提到，你的訓練數(shù)據(jù) 10倍于VC Dimension的空間做，是不一樣的。在VC Dimension是訓練數(shù)據(jù)10倍的情況下，如果你用training error最小化這樣的簡單的算法，是不能指望得到任何好的成果的。所以從我個人的角度來看，深度學習之所以能在VC Dimension是數(shù)據(jù)量的10倍的復雜度的模型里學習，并且能夠取得成功，極大地依賴于SGD的算法。

如果大家設計了一個優(yōu)化算法，我給你一個數(shù)據(jù)，給你一個參數(shù)個數(shù)為訓練數(shù)據(jù)量10倍的網(wǎng)絡，而且你找到了全局最優(yōu)解，我可以負責任地告訴大家，你最后的效果一定是很差的。所以我們今天的深度學習我認為之所以能做好，正是由于它沒有找到全局最優(yōu)解，如果真的能找到，這個性能就壞掉了，或者說必須換成小的網(wǎng)絡才有可能。所以SGD這個算法啟發(fā)大家的一點是，如果從做研究的角度講，還有沒有更好地滿足前面講的方法？

我再談一點可能跟應用結(jié)合更緊密的方面。如果有做深度學習這種實驗經(jīng)驗的老師、同學們，不知道大家是怎么做的，反正我的一些學生的經(jīng)驗是這樣的：毫無疑問，深度學習的訓練是最困難的，經(jīng)常會發(fā)生以下幾個現(xiàn)象中的一個或者多個。

• 第一，過擬合。我一訓練，training error很快下降了，但是一測試發(fā)現(xiàn)，測試數(shù)據(jù)集和訓練數(shù)據(jù)集的差別巨大，什么原因呢？由于深度學習通常用的網(wǎng)絡或者模型是非常復雜的，所以你一旦要在整個模型中找到一個training loss非常低的點，或者說你SGD在走的這條路徑當中，實際上算法穩(wěn)定性是有一定概率意義的，可能你這次走壞了，沒走好，實際上stability就不存在了，這是第一種現(xiàn)象。在今天的深度學習中，過擬合還是一個非常常見的現(xiàn)象。

• 第二種，training loss的問題。你訓練很長時間就是不降下來，這是什么原因呢？我個人認為，這個原因就是，SGD由于是隨機的，實在是沒有找到一個loss，能夠下降到可接受的點，比如說在很平坦的區(qū)域就卡在那兒了，大家看到有很多做深度學習應用的研究者，比如Bengio，給了很多這樣的報告，經(jīng)常出現(xiàn)訓練不下降了，是因為你可能陷在一個很平坦的區(qū)域，在很大的一個領域里面你的training loss幾乎沒有什么變化，這個結(jié)論是不是真的對？我認為還不一定完全正確，還需要有更多的研究。

• 還有其他一些現(xiàn)象，比如不同的超參數(shù)得到的訓練結(jié)果差異非常大，大家知道深度學習里面有很多超參數(shù)要去調(diào)，你的這個數(shù)不一樣，訓練的結(jié)果完全不一樣，所以這些都可以從理論學習的層面去研究，不僅研究，而且希望能夠?qū)Υ蠹椅磥砟軌蛴幸磺兄笇裕褪俏胰绾文軌蛟O計這個算法，使其達到最終比較好的目的。如果從學術(shù)的角度來講，這應該也是一個很值得探討的問題，從應用的角度來講，對于提高我們訓練的效率是很有價值的。

大家可能都知道，如果你是一個做深度學習經(jīng)驗豐富的研究者，和一個剛?cè)腴T的人，對于同樣的問題，即使你拿到同樣的代碼，其實你想調(diào)出同樣的結(jié)果，需要花的時間差異是巨大的，所以這些方面是很值得深入探討的一些問題。

關于算法穩(wěn)定性和SGD具體的算法，為什么它具有穩(wěn)定性，我想數(shù)學上就不用太多講了，大家可以再思考一下?，F(xiàn)在SGD有很多不同優(yōu)化的算法，你能不能從算法穩(wěn)定性的角度去想一想，這幾種不同的方法誰的stability更好，誰的更差？

其實我認為還是有點區(qū)別的，你如果對這些有一個認識，可能不是說直接幫助你解決問題，但它會幫助你加快在訓練速度，變成一個很有經(jīng)驗的研究者。還有前面談到的drop out，從stability的角度探討一下，它能否對泛化起作用？實際上也是有可能的，我們完全有可能從很多種不同的角度去看待這個問題。

| 關于深度學習算法的一些討論

最后談一個學術(shù)界很多人都在討論，特別是深度學習的學術(shù)界，大概大家都知道深度學習有三位最有影響的研究者，Hinton、LeCun和Bengio，現(xiàn)在也在研究所謂的深度學習 loss surface。也就是說，我們的目標是想優(yōu)化學習一個網(wǎng)絡，那學習網(wǎng)絡過程其實就是在試圖將損失最小化，那么我們能不能把loss這個函數(shù)，當然是非常非常高維的函數(shù)，（你有多少個參數(shù)，函數(shù)就是多少），我能不能分析一下在這個高維空間中我這個loss function到底長什么樣？

有很多人寫論文證明loss surface對于深度網(wǎng)絡是沒有壞的local minima，比如去年的一篇NIPS的oral paper。但是大家特別是做研究的想一想，其實你稍微思考一下應該能明白，這是根本不可能的，顯然結(jié)論是不正確的。

很簡單的例子：你這個網(wǎng)絡的最優(yōu)點，在整個空間里面的數(shù)目是非常之大的，因為網(wǎng)絡它有很高的對稱性。比如說我這樣一個網(wǎng)絡，我的參數(shù)設置是最優(yōu)，我把這些參數(shù)隨便做一個置換(permutation)，也是最優(yōu)，具有這樣性質(zhì)的非凸函數(shù)，存在局部極小值。所以loss surface這里面可研究的內(nèi)容很多，沒有現(xiàn)在大家想象的這么簡單。

那么，如果大家想做研究開發(fā)新的方法，前面我們講了，一個是現(xiàn)在遇到問題是防止過擬合，還有一種情況是走到一個地方很平坦不下降了，你遇到這種地方怎么讓它盡快的跑出來，能夠讓它下降。

這是從算法穩(wěn)定性的角度介紹一下我個人認為可以去研究的一些點，對深度學習和泛化、機器學習理論，覺得有趣的點可以研究。

最后總結(jié)一下，我覺得我們必須得坦率地承認，我們的學習理論目前為止對深度學習有一個很好的解釋，過去的VC理論、Margin Theory，還有算法穩(wěn)定性等等都不能很完美地解釋，雖然算法穩(wěn)定性我認為有一部分解釋了，但是我們應該采取的態(tài)度，至少從我的角度來看，不是說就認為學習理論就沒有意義了，我覺得還是有意義的，它一定在經(jīng)過進過更深入研究以后能夠幫助我們更好地產(chǎn)生insight,設計出更好的學習算法，也許有一天,深度學習可能不是最好的方法，甚至被淘汰了，我認為這完全是有可能的，但是還會有新的更好的方法。

我的報告就到這里。謝謝大家！

關于王教授及其他教授的主題報告，敬請期待雷鋒網(wǎng)的后續(xù)報道。

雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。