雷鋒網(wǎng)［AI科技評(píng)論］按：本文根據(jù)王立威教授在中國(guó)人工智能學(xué)會(huì)AIDL第二期人工智能前沿講習(xí)班＊機(jī)器學(xué)習(xí)前沿所作報(bào)告《機(jī)器學(xué)習(xí)理論：回顧與展望》編輯整理而來，雷鋒網(wǎng)在未改變?cè)獾幕A(chǔ)上略作了刪減。

王立威

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

| 算法穩(wěn)定性

我們接下來談?wù)劦谌齻€(gè)比較重要的學(xué)習(xí)理論，叫Algorithmic Stability（算法穩(wěn)定性）。

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

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

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

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

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

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

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

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

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

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

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

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

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

深度學(xué)習(xí)算法

接下來我們可以簡(jiǎn)單地總結(jié)一下深度學(xué)習(xí)算法。很多深度學(xué)習(xí)做應(yīng)用的人會(huì)覺得，傳統(tǒng)的機(jī)器學(xué)習(xí)理論無法解釋今天深度學(xué)習(xí)的成功，因?yàn)榻裉斓纳疃葘W(xué)習(xí)在很多方法跟傳統(tǒng)的機(jī)器學(xué)習(xí)理論看上去是矛盾的。

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

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

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

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

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

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

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

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

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

| 關(guān)于深度學(xué)習(xí)算法的一些討論

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

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

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

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

這是從算法穩(wěn)定性的角度介紹一下我個(gè)人認(rèn)為可以去研究的一些點(diǎn)，對(duì)深度學(xué)習(xí)和泛化、機(jī)器學(xué)習(xí)理論，覺得有趣的點(diǎn)可以研究。

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

我的報(bào)告就到這里。謝謝大家！

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

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