摘要：但在年春季關(guān)于理論機(jī)器學(xué)習(xí)的課程上，泛化理論專家表達(dá)了對這篇論文的不滿，尤其是其標(biāo)題。在一個相關(guān)的說明中，及其聯(lián)合作者的幾篇更早期的論文已經(jīng)提出了與張弛原等人對深度網(wǎng)絡(luò)的看法相當(dāng)相似的觀點。

深度學(xué)習(xí)的理論還存在諸多神秘之處。近來很多機(jī)器學(xué)習(xí)理論研究者都在關(guān)注神秘的泛化（generalization）：為什么訓(xùn)練后的深度網(wǎng)絡(luò)能在之前并未見過的數(shù)據(jù)上取得良好的表現(xiàn)，即便它們的自由參數(shù)的數(shù)量遠(yuǎn)遠(yuǎn)超過了數(shù)據(jù)點的數(shù)量（經(jīng)典的「過擬合」情況）？張馳原等人的論文《理解深度學(xué)習(xí)需要重新思考泛化（Understanding Deep Learning requires Rethinking Generalization）》為這一難題帶來了一些關(guān)注。

論文地址：https://arxiv.org/abs/1611.03530。

他們的主要實驗發(fā)現(xiàn)是：如果你在帶有隨機(jī)標(biāo)簽的圖像上訓(xùn)練一個經(jīng)典的卷積網(wǎng)絡(luò)架構(gòu)（比如 Alexnet），那么你仍然可以在這些訓(xùn)練數(shù)據(jù)上實現(xiàn)非常高的準(zhǔn)確度。（此外，人們認(rèn)為有助于實現(xiàn)更好的泛化的常見正則化策略其實幫助不大。）不用說，這個訓(xùn)練后的網(wǎng)絡(luò)之后并不能預(yù)測仍未見過的圖像的（隨機(jī)）標(biāo)簽，這就意味著它不能泛化。這篇論文指出將分類器與帶有隨機(jī)標(biāo)簽的數(shù)據(jù)進(jìn)行擬合的能力也是機(jī)器學(xué)習(xí)領(lǐng)域內(nèi)的一種傳統(tǒng)方法，該方法被稱為 Rademacher 復(fù)雜度（后面我們會討論），因此 Rademacher 復(fù)雜度在樣本復(fù)雜度上并沒有有意義的邊界。我覺得這篇論文寫得很有意思，推薦閱讀。該論文獲得了 ICLR 2017 較佳論文獎，恭喜作者。

但在 2017 年春季關(guān)于理論機(jī)器學(xué)習(xí)的 Simons Institute 課程上，泛化理論專家表達(dá)了對這篇論文的不滿，尤其是其標(biāo)題。他們認(rèn)為相似的問題已經(jīng)在更簡單的模型上得到過廣泛的研究了，比如 kernel SVM（核支持向量機(jī)）（老實說，這篇論文里也明確提到過）。設(shè)計具有很高 Rademacher 復(fù)雜度同時又能在真實數(shù)據(jù)上很好地訓(xùn)練和泛化的支持向量機(jī)架構(gòu)是很簡單的。此外，用于解釋這種泛化行為的理論也已經(jīng)得到了發(fā)展（而且還適用于 boosting 等相關(guān)模型）。在一個相關(guān)的說明中，Behnam Neyshabur 及其聯(lián)合作者的幾篇更早期的論文已經(jīng)提出了與張弛原等人對深度網(wǎng)絡(luò)的看法相當(dāng)相似的觀點。

但不管這些吐槽抱怨，張弛原等人的論文讓人們關(guān)注起這個核心的理論難題了，我們應(yīng)該感到高興。實際上，在 Simons Institute 課程上的熱情討論者自己也組成了小組來解決這個難題，這帶來了多篇論文（其中后兩篇出現(xiàn)在了 NIPS" 17 上）：

Dzigaite 和 Roy 的論文《Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data》：https://arxiv.org/abs/1703.11008

Bartlett、Foster 和 Telgarsky 的論文《Spectrally-normalized margin bounds for neural networks》https://arxiv.org/abs/1706.08498

Neyshabur、Bhojapalli、MacAallester 和 Srebro 的論文《A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks》：https://arxiv.org/abs/1707.09564

在解讀這些研究結(jié)果之前，我先說明一下對張弛原等人論文的標(biāo)題的部分爭議源自一些基本的困惑，即當(dāng)前的泛化理論是規(guī)范性的還是僅僅是描述性的。這些困惑由源自課程和教科書對泛化理論的標(biāo)準(zhǔn)對待方式，我在我的研究生課程上教授最近的進(jìn)展時也發(fā)現(xiàn)了這一點。

規(guī)范性理論還是描述性理論

為了闡釋兩者的差異，假設(shè)有一位病人對其醫(yī)生說：「醫(yī)生，我晚上常常醒來而且一天都很累?！?/p>

醫(yī)生 1（沒有進(jìn)行任何身體檢查）：「哦，你患了失眠癥?！?/p>

我將這種診斷稱為描述性的（descriptive），因為這只是給該病人的問題分配一個標(biāo)簽，而沒有給出如何解決該問題的任何見解。與之相反：

醫(yī)生 2（經(jīng)過仔細(xì)的身體檢查后）：「你的鼻竇增生導(dǎo)致睡眠呼吸暫停。移除它可以解決你的問題?！?/p>

這樣的診斷是規(guī)范性的（prescriptive）。

泛化理論：描述性還是規(guī)范性？

比如 VC 維、Rademacher 復(fù)雜度和 PAC-Bayes 邊界等泛化理論概念是為缺乏泛化的基本現(xiàn)象賦予一個描述性標(biāo)簽。對于今天復(fù)雜的機(jī)器學(xué)習(xí)模型來說，它們很難計算，更不要說用來指導(dǎo)學(xué)習(xí)系統(tǒng)的設(shè)計了。

泛化理論：描述性部分

我們現(xiàn)在討論 Rademacher 復(fù)雜度，本文中的討論會有所簡化。詳情可參閱我的課程筆記：https://www.cs.princeton.edu/courses/archive/fall17/cos597A/lecnotes/generalize.pdf。在這里的討論中，為了方便起見，假設(shè)標(biāo)簽和損失是 0 和 1，并且假設(shè)泛化能力糟糕的 h 在訓(xùn)練樣本 S 上的表現(xiàn)完美但在留存集 S2 上的完全錯誤，也就是說：

Rademacher 復(fù)雜度涉及到下面的思想實驗。從 D 中取大小為 2m 的單個樣本集，然后將其分成兩半，其中一半是 S，另一半是 S2。翻轉(zhuǎn) S2 中點的標(biāo)簽。現(xiàn)在嘗試尋找能較好地描述這些新樣本的分類器 C，也就是說最小化

為什么呢？因為翻轉(zhuǎn)點的標(biāo)簽可以將好的分類變成糟糕的分類，或反過來，因此 S2 的損失函數(shù)是 1 減去翻轉(zhuǎn)前的損失。如果這個量有很高的概率很小（比如接近于 0），那么我們就說這個分類器的類別的 Rademacher 復(fù)雜度高。

但 (3) 式表明 Rademacher 復(fù)雜度高的情況是：S、S2 是來自 D 的大小為 m 的隨機(jī)樣本，所以它們的總大小是 2m；當(dāng)泛化失敗時，我們就成功找到了使

非常小的假設(shè) h。

換句話說，繼續(xù)用醫(yī)療的例子類比，醫(yī)生只需聽到「泛化沒有發(fā)生」就得到結(jié)論「Rademacher 復(fù)雜度高」。所以我說這個結(jié)果是描述性的。

類似地，VC 維邊界也是描述性的。如果存在一個大小為 k 的集合使得下面的結(jié)果成立，那么 VC 維至少是 k+1。如果我們檢查類別中的所有可能的分類器，并且該標(biāo)簽序列中每一個標(biāo)簽都給了樣本中的 k 個數(shù)據(jù)點，那么我們可以找到 0 和 1 構(gòu)成的所有可能的 2^k 個序列。

因此，再次類比一下，醫(yī)生只需聽到「泛化沒有在樣本大小為 m 的情況下實現(xiàn)」就得到結(jié)論「VC 維高于Ω(m/logm)」。

我們也可以類似地證明 PAC-Bayes 邊界也是描述性的，你可以在我的課程筆記中看到：http://www.cs.princeton.edu/courses/archive/fall17/cos597A/lecnotes/generalize.pdf

為什么學(xué)生搞不清楚，認(rèn)為這樣的泛化理論工具能為機(jī)器學(xué)習(xí)算法的設(shè)計提供一些強(qiáng)有力的技術(shù)呢？

答案：也許是因為教學(xué)筆記和教科書中的標(biāo)準(zhǔn)演示就像是在假設(shè)我們在計算上是萬能的——好像我們可以計算 VC 維和 Rademacher 復(fù)雜度并因此能在可實現(xiàn)泛化的訓(xùn)練所需的樣本規(guī)模上達(dá)到有意義的邊界。盡管之前在使用簡單的分類器的時候也許能辦到，但現(xiàn)在我們的復(fù)雜分類器具有數(shù)以百萬計的變量，而且這些變量還是反向傳播等非凸優(yōu)化技術(shù)的產(chǎn)物。為了降低這種復(fù)雜學(xué)習(xí)架構(gòu)的 Rademacher 復(fù)雜度的邊界，實際上的方法是在訓(xùn)練分類器后通過留存集檢測泛化的缺乏。這一領(lǐng)域的每個實踐者都在這樣做（卻沒有意識到），張弛原等人強(qiáng)調(diào)了現(xiàn)在的理論毫無助益，這一點值得稱贊。

尋找規(guī)范性泛化理論：新論文

在我們的醫(yī)學(xué)類比中，我們看到醫(yī)生至少需要做一次身體檢查才能得到規(guī)范性的診斷。這些新論文的作者也直觀地把握住了這一點并且試圖確定可能實現(xiàn)更好泛化的真實神經(jīng)網(wǎng)絡(luò)的性質(zhì)。幾十年前有人在簡單的 2 層網(wǎng)絡(luò)上進(jìn)行過這樣的分析（與「邊際（margin）」相關(guān)），其中的難點是尋找與多層網(wǎng)絡(luò)的類比。Bartlett 等人和 Neyshabur 等人都深入研究了深度網(wǎng)絡(luò)的層的權(quán)重舉證的穩(wěn)定秩（stable rank）。這些可被看作是「flat minimum」的一個實例，多年來神經(jīng)網(wǎng)絡(luò)方面的文獻(xiàn)一直在討論這個問題。我將在未來的文章中給出我對這些結(jié)果的理解和一些改進(jìn)。注意，這些方法目前還未給出任何有關(guān)訓(xùn)練網(wǎng)絡(luò)所需數(shù)據(jù)點數(shù)量的不尋常的邊界。

Dziugaite 和 Roy 選擇了稍有不同的方向。他們的工作始于 McAllester 的 1999 PAC-Bayes 邊界，也即：如果該算法在假設(shè)上的先驗分布是 P，那么對于在該假設(shè)上的每個后驗分布 Q（可能取決于數(shù)據(jù)），根據(jù) Q 所選擇的平均分類器的泛化誤差的上界如下，其中 D() 表示 KL 散度：

這使得可以通過 Langford 和 Caruana 之前的論文（(Not) Bounding the True Error）中類似的過程為泛化誤差設(shè)置上界，其中 P 是均勻高斯，Q 是訓(xùn)練后的深度網(wǎng)絡(luò)的有噪聲版本（我們想要解釋它的泛化）。具體來說，如果 w_ij 是該訓(xùn)練后網(wǎng)絡(luò)中邊 i,j 的權(quán)重，那么為權(quán)重 w_ij 增加高斯噪聲 η_ij 就構(gòu)成了 Q。因此根據(jù) Q 所得到的隨機(jī)分類器不過是該訓(xùn)練后網(wǎng)絡(luò)的一個有噪聲版本而已?，F(xiàn)在我們看到關(guān)鍵了：使用非凸優(yōu)化來尋找 η_ij 的方差的一個選擇，使之能在兩個不相容的指標(biāo)上找到平衡：（a）源自 Q 的平均分類器的訓(xùn)練誤差不比原來的訓(xùn)練后的網(wǎng)絡(luò)多很多（同樣，這是通過優(yōu)化找到的極小值的「平坦度」的量化）；（b）上面表達(dá)式的右邊盡可能小。假設(shè)（a）和（b）都可以適當(dāng)?shù)卮_定邊界，那么源自 Q 的平均分類器可以在未曾見過的數(shù)據(jù)上表現(xiàn)得相當(dāng)好。（注意這種方法只是證明了訓(xùn)練后的分類器的有噪聲版本的泛化能力。）

將這種方法應(yīng)用到在 MNIST 數(shù)據(jù)集上訓(xùn)練的簡單全連接神經(jīng)網(wǎng)絡(luò)上，他們可以證明這種方法可在 MNIST 上實現(xiàn) 17% 的誤差（實際誤差要低得多，在 2% 到 3% 之間）。他們的論文也由此得名，承諾有非空虛（nonvacuous）的泛化邊界。對于這個結(jié)果，我覺得最有意思的是它使用了非凸優(yōu)化的能力（在上面被用來尋找一個合適的噪聲分布 Q）來闡釋有關(guān)非凸優(yōu)化的一個元問題，即深度學(xué)習(xí)不過擬合的原因是什么。

原文鏈接：http://www.offconvex.org/2017/12/08/generalization1/

商業(yè)智能與數(shù)據(jù)分析群

興趣范圍包括各種讓數(shù)據(jù)產(chǎn)生價值的辦法，實際應(yīng)用案例分享與討論，分析工具，ETL工具，數(shù)據(jù)倉庫，數(shù)據(jù)挖掘工具，報表系統(tǒng)等全方位知識

QQ群：81035754