另一篇終結深度學習理論的論文

昨天，我寫了關於 2016 年左右深度學習理論的現狀，^([1]) 以及 Zhang 等人那篇可以說標誌著其終結的 2016 年重磅論文。今天，我將介紹其後續影響，以及那篇在 2019 年再次重創深度學習理論的論文。

簡而言之，我曾主張深度學習的興起對統計學習理論這一主導理論範式構成了生存挑戰，因為神經網路具有極高的複雜性。該領域的反應是嘗試使用替代的複雜度指標，來量化神經網路在實踐中的假設類別（hypothesis class）在其他方面是如何簡單的。Zhang 等人（2016）展示了使用標準訓練方法訓練的標準神經網路架構可以記憶大量的隨機標籤數據，這表明任何此類論點都無法解釋神經網路的泛化特性。

今天我們來看看後續：深度學習理論領域對這篇論文有何反應？有哪些嘗試利用數據相關（data-dependent）的泛化界限（generalization bounds）來繞過這一結果？以及為什麼 Nagarajan 和 Kolter 那篇標題謙遜的《一致收斂可能無法解釋深度學習中的泛化》（Uniform convergence may be unable to explain generalization in deep learning）會成為這一研究路線的最後一根棺材釘？

---

讓我們簡要回顧一下 Zhang 等人的論文究竟展示了什麼。昨天我寫道：

作者的結果顯示，同一類神經網路，使用相同的學習算法訓練，在給定真實標籤時可以泛化，而在給定隨機標籤時則會死記硬背。這表明，使用標準技術可學習的神經網路假設類別，在任何有意義的層面上都不可能是簡單的，至少對於那些僅依賴於假設類別屬性和（與數據無關的）學習算法屬性的複雜度度量而言是如此。

（強調為後加）

值得注意的是，這些結果中存在一個重要的限制條件：Zhang 等人展示的是存在某些數據集，神經網路在其中會發生過擬合。這為尋找數據相關的泛化界限留下了可能性，即基於在特定數據集上訓練的特定神經網路的屬性。例如，當時仍存在一種可能性，即泛化界限可以表述為：「如果一個訓練好的神經網路具有較小的權重範數/是可壓縮的/具有較大的邊際（margin），且它是在足夠多的數據點上訓練的，那麼其測試誤差將不會比訓練誤差高出超過 epsilon。」

而這正是該領域一些研究人員所做的。Bartlett、Foster 和 Telgarsky 的《神經網路的光譜歸一化邊際界限》（2017） 引入了一種基於光譜範數（spectral norm）和參考矩陣的複雜度概念（「光譜複雜度」）；然後他們利用光譜複雜度和學習到的神經網路分類器的邊際來限制其泛化誤差。與此同時，Neyshabur、Bhojanapalli 和 Srebro 的 《神經網路光譜歸一化邊際界限的 PAC-Bayesian 方法》（2018） 也結合使用了光譜範數和與初始化的距離來論證泛化，儘管是在貝葉斯框架下。甚至 Nagarajan 和 Kolter 在他們 2017 年的工作坊論文《深度網絡中的泛化：與初始化距離的作用》 中也提出了一種數據相關的泛化界限，其中神經網路的複雜度與其權重相對於初始化的變化程度有關。

Bartlett、Foster 和 Telgarsky 基於光譜複雜度和邊際的界限。這對本文並不重要，我加入它只是為了展示其中涉及嚴謹的數學！敏銳的讀者可能會注意到，假設數據集 X 中的每個條目都是有界的，誤差相對於數據的縮放因子仍然是經典的 1/sqrt(n)*

這些界限的共同形式是，它們根據訓練權重的某種光譜範數衍生複雜度度量，除以訓練數據與決策邊界之間的邊際以及數據點數量的（平方根），來限制泛化差距。在真實標籤上訓練的神經網路往往具有較低的光譜範數，且其決策邊界與訓練數據點之間的邊際較大。因此，當給定足夠的數據點時，泛化誤差將會很低，它們應該能夠泛化！

所有這些界限的一個隱含假設是（就像統計學習理論中的大多數界限一樣），它們證明了一致收斂（uniform convergence）——無論假設是什麼，它們都適用。更準確地說，在所有可能的訓練集上以高機率保證，對於假設類別中的每一個假設 h，測試誤差和訓練誤差同時接近。具體而言，此類界限的形式為：

在可能的訓練集 S 上以高機率保證，對於假設類別中的所有 h，我們有 |假設 h 的預期測試誤差 - h 在 S 上的經驗誤差| < (某種涉及訓練數據大小和 h 的高階屬性的界限)。^([2])

這種類型的界限既非常自然也非常有用：訓練好的神經網路是某個 h ∈ H，而一致收斂保證了無論最終得到的 h 是什麼，只要我們知道 h 的一些高階屬性，該界限就成立。

Nagarajan 和 Kolter 在他們 2019 年的論文中針對的正是這整類界限。

---

那麼，Nagarajan 和 Kolter 2019 年的論文展示了什麼？

首先，他們通過實驗證明，文獻中的界限不僅是無效的（vacuous），而且縮放方向也是錯誤的。Nagarajan 和 Kolter 能夠輕鬆地在 MNIST 上訓練小型 5 層神經網路，使得 99% 的訓練數據在 Logit 空間中至少有 10 的邊際。正如你所預料的，在這種情況下，訓練網絡的測試誤差隨著數據點數量 n 的增加而降低，遵循測試誤差縮放的冪律，大約為 $n^{-0.35}$。

問題在於，在這種情況下，文獻中提出的複雜度度量也具有冪律關係。值得注意的是，學習到的權重矩陣的光譜範數隨 n 線性縮放，而與初始化的距離則隨 $n^{0.5}$ 縮放。結果是，儘管實際的泛化誤差在下降，文獻中的泛化界限反而上升，按 $n^{0.5}$ 縮放。

雖然標題沒說，但 Nagarajan 和 Kolter 的圖 1 是對 Zhang 等人之後學習理論主要研究方法的一個毀滅性反擊。而且這一次，我敢肯定製作這張圖所花費的算力比在 LessWrong 編輯器中按一下整合的 Claude 按鈕還要少。*

值得再次強調這個結果是多麼具有打擊性。傳統上，在學習理論中，預期泛化誤差的縮放比例大約為 $1/\sqrt{n}$；而在現代縮放定律中，實驗也觀察到了類似的結果。Zhang 等人之後文獻中提供的光譜範數界限不僅寬鬆到毫無意義，而且還以 $n^{0.5}$ 的比例縮放，方向完全錯誤！

其次，他們構建了一個超參數化的線性場景，在該場景下可以證明（雙邊）一致收斂界限必然失效。完整的構建超出了本部落格文章的範圍，但我認為其核心思想非常優雅。對數學細節感興趣的讀者建議閱讀論文原文。

考慮在 n 個訓練樣本上擬合一個線性分類器 w。該分類器的輸入是 K + D 維的，其中前 K 維包含確定性信號，其餘 D >> n 維是高斯噪聲，均值為零，方差縮放為 1/D。在一次梯度步驟後，線性分類器在前 K 維將與信號對齊，而其餘 D 維將是 n 個獨立高斯噪聲向量 $\sum y_i z_i$ 的總和，其中 $y_i$ 是第 $i$ 個數據點的標籤。

很容易理解為什麼 w 會泛化：對於每個新數據點，前 K 維中的信號將保持很大（因為它是確定性的）。相比之下，對於每個新數據點，D 個噪聲方向是獨立採樣的，而這個噪聲向量與我們線性分類器的最後 D 維的點積將集中在零附近。^([3])

為了證明一致收斂失效，作者構建了一個自然的「壞」數據集 S'，在該數據集上 w 的經驗誤差與預期測試誤差相去甚遠。具體來說，S' 是通過反轉訓練數據集 S 中的 D 維噪聲來構建的。這裡利用的技巧是，在 S 上訓練的線性分類器已經「記憶」了訓練噪聲。翻轉噪聲會使這種記憶反過來對抗分類器，導致它在 S' 上失敗，儘管它能很好地泛化到新數據點。

用更數學的術語來說，我們在 S 上訓練的線性分類器具有噪聲塊權重 $w_{noise} \approx \sum y_i z_i$。當你在 $x'_i = (signal, -z_i)$ 上評估 w 時，噪聲塊的貢獻變成了 $-y_i z_i \cdot z_i$。^([4]) 因為每個維度的方差是 1/D，且有 D 個噪聲方向，我們有 $z_i \cdot z_i \approx 1$。這意味著，在噪聲的高機率下，w 會誤分類 S' 中的每個點，因為噪聲成分既在錯誤的方向上，而且（通過對噪聲/信號強度的仔細微調）大到足以壓倒信號。因此，w 在 S' 上的經驗誤差為 1，而測試誤差與經驗誤差之間的差距為 $\approx 1$。由於一致收斂界限根據定義適用於該類別中的每個分類器在任何^([5])樣本上（包括 S' 上的 w），該界限必須不小於這一項，這迫使它變得無效：|測試誤差 - 訓練誤差| $\approx 1$。^([6])

對於感興趣的讀者，這是來自 Nagarajan 和 Kolter 的實際數學構建，以及正式定理的陳述，證明梯度下降表現良好，而任何一致收斂界限都證明是無效的。*

**

第三，他們將理論上的超參數化線性例子轉化為淺層 ReLU 網絡上的實驗結果。** Nagarajan 和 Kolter 構建了一個數據集，其中每個數據點位於兩個 1000 維超球體之一，半徑分別為 1 或 1.1。^([7]) 然後，他們在該數據集上訓練了一個具有 10 萬個隱藏單元的 2 層 ReLU 網絡，直到 99% 的訓練數據以 10 的邊際被正確分類。他們發現了標準結果，即測試誤差隨數據集大小大約按 $1/\sqrt{n}$ 縮放。

然後，他們通過獲取原始訓練數據集 S，並將數據點投影到相對的超球體上並交換其標籤，構建了一個壞數據集 S'。他們的 ReLU 分類器在這個投影數據集 S' 上始終獲得 0% 的準確率。這給出了與超參數化線性案例相同的結果，儘管這是一個既非線性也非超參數化輸入的案例。

作者檢查了學習到的決策邊界的 2D 切片，以理解為什麼分類器能同時獲得高測試準確率和在投影數據集上的 0% 準確率。請注意，根據構建，真實的分類邊界位於兩個超球體之間。

在訓練數據點附近，決策邊界會向遠離樣本的方向凸起，足以使邊界在數據點附近實際上包圍了兩個超球體。這意味著將數據點投影到另一個超球體上不會改變網絡對它的分類方式。由於真實標籤因這種投影而翻轉，網絡會對投影後的數據點分類錯誤。由於 S' 將所有訓練數據點投影到相對的超球體，網絡在 S' 上獲得 0% 的準確率是合理的。

相比之下，當你查看隨機的 2D 切片時，決策邊界往往位於兩個超球體之間。測試樣本引起的凸起已經「平均抵消」了。因此，對於任何新的、隨機生成的測試數據點，網絡很可能會正確分類該樣本。

Nagarajan 和 Kolter 2019 年的圖 2 顯示了兩件事。在最左邊的圖中，他們顯示隨著訓練數據點數量的增加，測試誤差降低，但在壞訓練數據集 S' 上的誤差保持在 1 不變。在中間的兩張圖中，他們顯示在訓練數據點附近，決策邊界向遠離訓練樣本的方向凸起，導致該區域出現誤分類。然而，在最右邊的圖中，他們顯示在新的隨機數據點附近，決策邊界很可能會平均抵消並位於兩個超球體之間。*

這引發了作者的推測，認為這是一個普遍現象：神經網路上的 SGD 學習到的分類器在宏觀尺度上是簡單的，但在微觀尺度上是複雜的。微觀複雜性是阻止一致收斂界限發揮作用的原因，而宏觀簡單性則解釋了泛化。在他們的 ReLU 例子中，精確的決策邊界會在採樣的訓練數據點周圍凸起（微觀複雜性），導致一致收斂界限失效；在新的測試數據點附近，這種複雜性會平均抵消（宏觀簡單性），從而帶來良好的測試性能。

---

Nagarajan 和 Kolter 的結果是對 Zhang 等人之後深度學習理論的沉重打擊：它不僅證明了該領域創建的數據相關界限縮放方向錯誤，還提供了一個超參數化場景，證明統計學習理論採取的整個方法——一致收斂界限——在證明上是行不通的。

思考 Nagarajan 和 Kolter 工作的一種更具建設性的方式是，它為解釋神經網路泛化的可能結果增加了進一步的限制。也就是說，它表明任何此類結果都需要在比光譜範數界限更強的意義上依賴於算法和數據。它需要放棄對一類假設中所有假設的最壞情況經驗誤差進行限制。並且它需要找到某種方法來處理 SGD 在神經網路上誘導的複雜微觀結構，同時又不忽視真正解釋泛化的宏觀規律性。

但將近十年過去了，我們仍然沒有得到這些結果。也許正在閱讀這篇文章的你們中有人會寫出解釋泛化的論文。與此同時，我將採取學術界的做法，將提出更好的深度學習理論這一任務留作讀者的練習。

• ^(^)澄清一下，我所說的「深度學習理論」是指「將統計學習理論擴展到使用 SGD 訓練的深度神經網路，以推導出能解釋其實踐行為的泛化界限」的工作——也就是說，不是任何關於深度學習的理論方法，而是特指嘗試為深度學習構建經典學習理論的努力。

• ^(^)「h 的高階屬性」部分是他們如何將數據依賴性引入其界限，以逃避 Zhang 等人（2016）的結果。

• ^(^)每個 $z_{i,j}$（和 $x_{new,j}$）都是獨立同分布的零均值高斯分佈，因此點積的方差隨其方差 $\sigma^2 = 1/D$ 縮放。累加 $n$ 個獨立的訓練噪聲向量，來自噪聲維度的貢獻大小大約按 $\sqrt{n/D}$ 縮放，由於 $D >> n$，這趨近於 0。

• ^(^)這裡的數學運算與前一個腳註相同，只是將 $x_{new}$ 替換為 $-z_i$。

• ^(^)敏銳的讀者可能會注意到，一致收斂界限只需要在分佈中 $1-\delta$ 的樣本上成立。這就是 $S'$ 的自然性發揮作用的地方：事實證明，不可能在 $1-\delta$ 中排除所有可能的 $S'$。

• ^(^)敏銳的讀者可能會注意到，這與機器學習中考慮的方向相反：我們通常看到的是測試誤差大而訓練誤差小，而這裡則是訓練誤差大而測試誤差小。這個例子清楚地表明，統計學習理論中標準的雙邊一致收斂泛化界限——即對訓練和測試誤差之間絕對差值的界限——可能是無效的。一個自然的問題是，我們能否通過求助於單邊界限（即僅使用訓練誤差來上限定測試誤差）來逃避這一點？在附錄中，Nagarajan 和 Kolter 展示了文獻中許多所謂的「單邊」PAC-Bayes 泛化界限是如何被雙邊一致收斂界限下限定的。後來的研究試圖推導出能逃避其論點的單邊泛化界限，儘管在實踐上並未取得太大成功。

• ^(^)這個設置最初由 Gilmer 等人（2018）的《對抗球體》（Adversarial Spheres）引入，用於研究對抗樣本。

討論