雷鋒網［AI科技評論］按：本文根據王立威教授在中國人工智慧學會AIDL第二期人工智慧前沿講習班＊機器學習前沿所作報告《機器學習理論：回顧與展望》編輯整理而來， 雷鋒網在未改變原意的基礎上略作了刪減。
王立威
王立威， 在北京大學教授主要研究領域為機器學習。 在包括COLT, NIPS， JMLR, PAMI等權威會議期刊發表論文60餘篇。 2010年入選 AI’s 10 to Watch， 是首位獲得該獎項的亞洲學者。 2012年獲得首屆國家自然科學基金優秀青年基金， 新世紀優秀人才。 任 NIPS 等權威會議 Area Chair， 和多家學術期刊編委。 以下為王立威教授所做的現場演講的第四部分， 主要覆蓋Algorithmic Stability的介紹。
| 演算法穩定性
我們接下來談談第三個比較重要的學習理論， 叫Algorithmic Stability（演算法穩定性）。
演算法穩定性是什麼？
剛剛我們談到了機器學習理論的發展， 從最開始幾乎不關心演算法， 只考慮模型的複雜度， 慢慢到Margin， 實際上已經和演算法有關， 而Algorithmic Stability其實完全就是探討演算法性質， 我這個演算法究竟具備了一個什麼樣的特點， 從而導致我們能夠有一個好的泛化能力。
什麼叫做Algorithmic Stability呢？我們還是從比較宏觀的角度來考慮， 細節大家回去以後自己去看。 簡而言之， 怎樣的演算法是stable的？它的核心是說， 當演算法用一個訓練資料集可以訓練出一個結果，
Algorithmic Stability， 就是從定量的角度上來刻畫以下的關係：當換掉其中一個訓練資料時， 演算法學出來的結果會有多大的改變。
穩定的演算法會有更好的泛化能力
大家覺得， 是比較stable的演算法會有更好的泛化能力呢， 還是說一個不stable的演算法有比較好的泛化能力呢？從直覺上思考一下， 顯然是stable的演算法有很好的泛化能力。
我還拿最開始的“胡克定律”來說明。 如果是一個線性的模型， 訓練資料更換一個， 其實這條直線不會有顯著的變化；如果我有100個資料， 用99階多項式來匹配這100個資料， 假如把這100個資料換掉一個， 我相信新的99階多項式可能就會發生重大的改變。 所以大家要從新的角度，
演算法穩定性理論是一個很定量的描述：如果我的演算法具有一個什麼樣的程度的穩定性， 那麼演算法的生成範圍就能有什麼樣的表徵， 我們就能給出一個數學領域的嚴謹描述， 一個定量的刻畫。 具體的內容我就跳過去了。
SVM與SGD， 演算法穩定性如何？
我在講這個演算法穩定性比較新的內容之前， 先說一說一些很傳統的演算法， 有一些是穩定性很好的。
舉個例子， SVM的穩定性很好。 SVM可以從數學上證明， 如果換掉其中的一個訓練資料， 其實你得到的結果通常發生的改變是比較小的， 是1/√n的級別， n是數據的量。 如果改變一個資料只是1/√n級別的變化， 那麼它的演算法穩定性很好。 什麼樣的演算法穩定性很不好呢？比如說以前有一個演算法叫決策樹（decision tree），假如換掉其中一個資料，有可能決策樹就完全變掉了。
所以從這個演算法說回今天我們最常用的方法上。今天大家很多人都在用深度學習（Deep Learning），訓練深度學習，大家是用什麼樣的演算法在訓練Deep Learning呢？最常用的演算法就是SGD（隨機梯度下降）。我們來問問大家，SGD這個演算法究竟是一個stable的演算法還是一個不stable的演算法？你從直覺上先想一下，梯度下降（GD）是在當前求它的梯度，沿梯度下降的方向走一小步。由於我求GD很費勁，所以我們從隨機角度入手，對某一個數據點求一個梯度，這就是一個SGD。
SGD這個演算法有沒有穩定性呢？這是2016年去年的一個結果（上圖），SGD這個演算法具有一定的穩定性，如果你在一個convex function上用SGD它的穩定性相當好。通常大家都知道，深度學習的損失函數是非凸的,而仍然可以證明SGD是具有一定的穩定性的，雖然在理論上可能暫時還證明不出來它具有非常高的穩定性，但是它能有一個還不錯的穩定性，在實際中它是不是有穩定性？我認為如果是做研究的老師、同學們其實可以去思考這個問題，這個如果做深度學習是一個比較重要的成果。
深度學習演算法
接下來我們可以簡單地總結一下深度學習演算法。很多深度學習做應用的人會覺得，傳統的機器學習理論無法解釋今天深度學習的成功，因為今天的深度學習在很多方法跟傳統的機器學習理論看上去是矛盾的。
我舉個例子，今天大家用的這個深度學習的網路，它的VC Dimension是多少？數學上可以證明，如果用全連接的網路，它的VC Dimension基本上就是它的編的數目，可是今天我們用的網路，通常編的數目是我們訓練資料要高一個數量級，編的數目就是我們參數的個數，所以實際上我們是在一個什麼樣的模型中間去學習呢？是在一個VC Dimension大概是10倍於訓練資料的空間在做，這跟我們之前提到，你的訓練資料 10倍於VC Dimension的空間做，是不一樣的。在VC Dimension是訓練資料10倍的情況下，如果你用training error最小化這樣的簡單的演算法，是不能指望得到任何好的成果的。所以從我個人的角度來看，深度學習之所以能在VC Dimension是資料量的10倍的複雜度的模型裡學習，並且能夠取得成功，極大地依賴於SGD的演算法。
如果大家設計了一個優化演算法，我給你一個資料，給你一個參數個數為訓練資料量10倍的網路，而且你找到了全域最優解，我可以負責任地告訴大家，你最後的效果一定是很差的。所以我們今天的深度學習我認為之所以能做好，正是由於它沒有找到全域最優解，如果真的能找到，這個性能就壞掉了，或者說必須換成小的網路才有可能。所以SGD這個演算法啟發大家的一點是，如果從做研究的角度講，還有沒有更好地滿足前面講的方法？
我再談一點可能跟應用結合更緊密的方面。如果有做深度學習這種實驗經驗的老師、同學們，不知道大家是怎麼做的，反正我的一些學生的經驗是這樣的：毫無疑問，深度學習的訓練是最困難的，經常會發生以下幾個現象中的一個或者多個。
第一，過擬合。我一訓練，training error很快下降了，但是一測試發現，測試資料集和訓練資料集的差別巨大，什麼原因呢？由於深度學習通常用的網路或者模型是非常複雜的，所以你一旦要在整個模型中找到一個training loss非常低的點，或者說你SGD在走的這條路徑當中，實際上演算法穩定性是有一定概率意義的，可能你這次走壞了，沒走好，實際上stability就不存在了，這是第一種現象。在今天的深度學習中，過擬合還是一個非常常見的現象。
第二種，training loss的問題。你訓練很長時間就是不降下來，這是什麼原因呢？我個人認為，這個原因就是，SGD由於是隨機的，實在是沒有找到一個loss，能夠下降到可接受的點，比如說在很平坦的區域就卡在那兒了，大家看到有很多做深度學習應用的研究者，比如Bengio，給了很多這樣的報告，經常出現訓練不下降了，是因為你可能陷在一個很平坦的區域，在很大的一個領域裡面你的training loss幾乎沒有什麼變化，這個結論是不是真的對？我認為還不一定完全正確，還需要有更多的研究。
還有其他一些現象，比如不同的超參數得到的訓練結果差異非常大，大家知道深度學習裡面有很多超參數要去調，你的這個數不一樣，訓練的結果完全不一樣，所以這些都可以從理論學習的層面去研究，不僅研究，而且希望能夠對大家未來能夠有一切指導性，就是我如何能夠設計這個演算法，使其達到最終比較好的目的。如果從學術的角度來講，這應該也是一個很值得探討的問題，從應用的角度來講，對於提高我們訓練的效率是很有價值的。
大家可能都知道，如果你是一個做深度學習經驗豐富的研究者，和一個剛入門的人，對於同樣的問題，即使你拿到同樣的代碼，其實你想調出同樣的結果，需要花的時間差異是巨大的，所以這些方面是很值得深入探討的一些問題。
關於演算法穩定性和SGD具體的演算法，為什麼它具有穩定性，我想數學上就不用太多講了，大家可以再思考一下。現在SGD有很多不同優化的演算法，你能不能從演算法穩定性的角度去想一想，這幾種不同的方法誰的stability更好，誰的更差？
其實我認為還是有點區別的，你如果對這些有一個認識，可能不是說直接幫助你解決問題，但它會説明你加快在訓練速度，變成一個很有經驗的研究者。還有前面談到的drop out，從stability的角度探討一下，它能否對泛化起作用？實際上也是有可能的，我們完全有可能從很多種不同的角度去看待這個問題。
| 關於深度學習演算法的一些討論
最後談一個學術界很多人都在討論，特別是深度學習的學術界，大概大家都知道深度學習有三位最有影響的研究者，Hinton、LeCun和Bengio，現在也在研究所謂的深度學習 loss surface。也就是說，我們的目標是想優化學習一個網路，那學習網路過程其實就是在試圖將損失最小化，那麼我們能不能把loss這個函數，當然是非常非常高維的函數，（你有多少個參數，函數就是多少），我能不能分析一下在這個高維空間中我這個loss function到底長什麼樣？
有很多人寫論文證明loss surface對於深度網路是沒有壞的local minima，比如去年的一篇NIPS的oral paper。但是大家特別是做研究的想一想，其實你稍微思考一下應該能明白，這是根本不可能的，顯然結論是不正確的。
很簡單的例子：你這個網路的最優點，在整個空間裡面的數目是非常之大的，因為網路它有很高的對稱性。比如說我這樣一個網路，我的參數設置是最優，我把這些參數隨便做一個置換(permutation)，也是最優，具有這樣性質的非凸函數，存在局部極小值。所以loss surface這裡面可研究的內容很多，沒有現在大家想像的這麼簡單。
那麼，如果大家想做研究開發新的方法，前面我們講了，一個是現在遇到問題是防止過擬合，還有一種情況是走到一個地方很平坦不下降了，你遇到這種地方怎麼讓它儘快的跑出來，能夠讓它下降。
這是從演算法穩定性的角度介紹一下我個人認為可以去研究的一些點，對深度學習和泛化、機器學習理論，覺得有趣的點可以研究。
最後總結一下，我覺得我們必須得坦率地承認，我們的學習理論目前為止對深度學習有一個很好的解釋，過去的VC理論、Margin Theory，還有演算法穩定性等等都不能很完美地解釋，雖然演算法穩定性我認為有一部分解釋了，但是我們應該採取的態度，至少從我的角度來看，不是說就認為學習理論就沒有意義了，我覺得還是有意義的，它一定在經過進過更深入研究以後能夠幫助我們更好地產生insight,設計出更好的學習演算法，也許有一天,深度學習可能不是最好的方法，甚至被淘汰了，我認為這完全是有可能的，但是還會有新的更好的方法。
我的報告就到這裡。謝謝大家！
關於王教授及其他教授的主題報告，敬請期待雷鋒網的後續報導。
什麼樣的演算法穩定性很不好呢？比如說以前有一個演算法叫決策樹（decision tree），假如換掉其中一個資料，有可能決策樹就完全變掉了。所以從這個演算法說回今天我們最常用的方法上。今天大家很多人都在用深度學習（Deep Learning），訓練深度學習，大家是用什麼樣的演算法在訓練Deep Learning呢？最常用的演算法就是SGD（隨機梯度下降）。我們來問問大家，SGD這個演算法究竟是一個stable的演算法還是一個不stable的演算法？你從直覺上先想一下，梯度下降（GD）是在當前求它的梯度，沿梯度下降的方向走一小步。由於我求GD很費勁，所以我們從隨機角度入手，對某一個數據點求一個梯度，這就是一個SGD。
SGD這個演算法有沒有穩定性呢？這是2016年去年的一個結果（上圖），SGD這個演算法具有一定的穩定性，如果你在一個convex function上用SGD它的穩定性相當好。通常大家都知道，深度學習的損失函數是非凸的,而仍然可以證明SGD是具有一定的穩定性的，雖然在理論上可能暫時還證明不出來它具有非常高的穩定性，但是它能有一個還不錯的穩定性，在實際中它是不是有穩定性？我認為如果是做研究的老師、同學們其實可以去思考這個問題，這個如果做深度學習是一個比較重要的成果。
深度學習演算法
接下來我們可以簡單地總結一下深度學習演算法。很多深度學習做應用的人會覺得，傳統的機器學習理論無法解釋今天深度學習的成功，因為今天的深度學習在很多方法跟傳統的機器學習理論看上去是矛盾的。
我舉個例子，今天大家用的這個深度學習的網路，它的VC Dimension是多少？數學上可以證明，如果用全連接的網路，它的VC Dimension基本上就是它的編的數目，可是今天我們用的網路，通常編的數目是我們訓練資料要高一個數量級，編的數目就是我們參數的個數，所以實際上我們是在一個什麼樣的模型中間去學習呢？是在一個VC Dimension大概是10倍於訓練資料的空間在做，這跟我們之前提到，你的訓練資料 10倍於VC Dimension的空間做，是不一樣的。在VC Dimension是訓練資料10倍的情況下，如果你用training error最小化這樣的簡單的演算法，是不能指望得到任何好的成果的。所以從我個人的角度來看，深度學習之所以能在VC Dimension是資料量的10倍的複雜度的模型裡學習，並且能夠取得成功，極大地依賴於SGD的演算法。
如果大家設計了一個優化演算法，我給你一個資料，給你一個參數個數為訓練資料量10倍的網路，而且你找到了全域最優解，我可以負責任地告訴大家，你最後的效果一定是很差的。所以我們今天的深度學習我認為之所以能做好，正是由於它沒有找到全域最優解，如果真的能找到，這個性能就壞掉了，或者說必須換成小的網路才有可能。所以SGD這個演算法啟發大家的一點是，如果從做研究的角度講，還有沒有更好地滿足前面講的方法？
我再談一點可能跟應用結合更緊密的方面。如果有做深度學習這種實驗經驗的老師、同學們，不知道大家是怎麼做的，反正我的一些學生的經驗是這樣的：毫無疑問，深度學習的訓練是最困難的，經常會發生以下幾個現象中的一個或者多個。
第一，過擬合。我一訓練，training error很快下降了，但是一測試發現，測試資料集和訓練資料集的差別巨大，什麼原因呢？由於深度學習通常用的網路或者模型是非常複雜的，所以你一旦要在整個模型中找到一個training loss非常低的點，或者說你SGD在走的這條路徑當中，實際上演算法穩定性是有一定概率意義的，可能你這次走壞了，沒走好，實際上stability就不存在了，這是第一種現象。在今天的深度學習中，過擬合還是一個非常常見的現象。
第二種，training loss的問題。你訓練很長時間就是不降下來，這是什麼原因呢？我個人認為，這個原因就是，SGD由於是隨機的，實在是沒有找到一個loss，能夠下降到可接受的點，比如說在很平坦的區域就卡在那兒了，大家看到有很多做深度學習應用的研究者，比如Bengio，給了很多這樣的報告，經常出現訓練不下降了，是因為你可能陷在一個很平坦的區域，在很大的一個領域裡面你的training loss幾乎沒有什麼變化，這個結論是不是真的對？我認為還不一定完全正確，還需要有更多的研究。
還有其他一些現象，比如不同的超參數得到的訓練結果差異非常大，大家知道深度學習裡面有很多超參數要去調，你的這個數不一樣，訓練的結果完全不一樣，所以這些都可以從理論學習的層面去研究，不僅研究，而且希望能夠對大家未來能夠有一切指導性，就是我如何能夠設計這個演算法，使其達到最終比較好的目的。如果從學術的角度來講，這應該也是一個很值得探討的問題，從應用的角度來講，對於提高我們訓練的效率是很有價值的。
大家可能都知道，如果你是一個做深度學習經驗豐富的研究者，和一個剛入門的人，對於同樣的問題，即使你拿到同樣的代碼，其實你想調出同樣的結果，需要花的時間差異是巨大的，所以這些方面是很值得深入探討的一些問題。
關於演算法穩定性和SGD具體的演算法，為什麼它具有穩定性，我想數學上就不用太多講了，大家可以再思考一下。現在SGD有很多不同優化的演算法，你能不能從演算法穩定性的角度去想一想，這幾種不同的方法誰的stability更好，誰的更差？
其實我認為還是有點區別的，你如果對這些有一個認識，可能不是說直接幫助你解決問題，但它會説明你加快在訓練速度，變成一個很有經驗的研究者。還有前面談到的drop out，從stability的角度探討一下，它能否對泛化起作用？實際上也是有可能的，我們完全有可能從很多種不同的角度去看待這個問題。
| 關於深度學習演算法的一些討論
最後談一個學術界很多人都在討論，特別是深度學習的學術界，大概大家都知道深度學習有三位最有影響的研究者，Hinton、LeCun和Bengio，現在也在研究所謂的深度學習 loss surface。也就是說，我們的目標是想優化學習一個網路，那學習網路過程其實就是在試圖將損失最小化，那麼我們能不能把loss這個函數，當然是非常非常高維的函數，（你有多少個參數，函數就是多少），我能不能分析一下在這個高維空間中我這個loss function到底長什麼樣？
有很多人寫論文證明loss surface對於深度網路是沒有壞的local minima，比如去年的一篇NIPS的oral paper。但是大家特別是做研究的想一想，其實你稍微思考一下應該能明白，這是根本不可能的，顯然結論是不正確的。
很簡單的例子：你這個網路的最優點，在整個空間裡面的數目是非常之大的，因為網路它有很高的對稱性。比如說我這樣一個網路，我的參數設置是最優，我把這些參數隨便做一個置換(permutation)，也是最優，具有這樣性質的非凸函數，存在局部極小值。所以loss surface這裡面可研究的內容很多，沒有現在大家想像的這麼簡單。
那麼，如果大家想做研究開發新的方法，前面我們講了，一個是現在遇到問題是防止過擬合，還有一種情況是走到一個地方很平坦不下降了，你遇到這種地方怎麼讓它儘快的跑出來，能夠讓它下降。
這是從演算法穩定性的角度介紹一下我個人認為可以去研究的一些點，對深度學習和泛化、機器學習理論，覺得有趣的點可以研究。
最後總結一下，我覺得我們必須得坦率地承認，我們的學習理論目前為止對深度學習有一個很好的解釋，過去的VC理論、Margin Theory，還有演算法穩定性等等都不能很完美地解釋，雖然演算法穩定性我認為有一部分解釋了，但是我們應該採取的態度，至少從我的角度來看，不是說就認為學習理論就沒有意義了，我覺得還是有意義的，它一定在經過進過更深入研究以後能夠幫助我們更好地產生insight,設計出更好的學習演算法，也許有一天,深度學習可能不是最好的方法，甚至被淘汰了，我認為這完全是有可能的，但是還會有新的更好的方法。
我的報告就到這裡。謝謝大家！
關於王教授及其他教授的主題報告，敬請期待雷鋒網的後續報導。