經(jīng)典的「沒有免費午餐定理」表明：如果某種學習算法在某些方面比另一種學習算法更優(yōu)，則肯定會在其它某些方面弱于另一種學習算法。

也就是說，對于任何一個學習問題，沒有最優(yōu)的算法，只有最合適的算法。

而在這項最新研究中，作者向我們揭示了這一現(xiàn)象背后的數(shù)學原理：每個神經(jīng)網(wǎng)絡(luò)，都是一個高維向量。

在高維向量空間中，不存在單調(diào)的大小比較。如果兩個向量A、B是垂直的，則內(nèi)積為零，通常也反映兩者更加不相關(guān)，比如作用在物體運動方向的垂直方向的力就不做功。

類似地，如果兩個神經(jīng)網(wǎng)絡(luò)對應(yīng)的向量內(nèi)積為零，則反映它們的相似程度更低。

在擬合第三個向量C，也就是通過數(shù)據(jù)進行訓練和學習時，如果A和C內(nèi)積更大，則表示A更容易學習C，也反映B更不容易學習C。

另一方面，當A通過訓練變得更加接近C時，與C垂直的另一個神經(jīng)網(wǎng)絡(luò)D也會因此和A更加不相關(guān)，也就是A變得更加難以學習D。

此即本文提出的「沒有免費午餐定理」加強版。

利用這個數(shù)學描述，我們就可以量化神經(jīng)網(wǎng)絡(luò)的泛化能力。

該研究主要基于寬神經(jīng)網(wǎng)絡(luò)，而表示神經(jīng)網(wǎng)絡(luò)的高維空間的每一個維度，都是由神經(jīng)正切核的特征向量構(gòu)成的。

神經(jīng)正切核與寬神經(jīng)網(wǎng)絡(luò)的聯(lián)系，在之前的文章中已有介紹，參見：

深度學習為何泛化的那么好？秘密或許隱藏在內(nèi)核機中

同時，作者也指出，該發(fā)現(xiàn)在寬度較小的網(wǎng)絡(luò)中也成立。

在高維空間中，神經(jīng)網(wǎng)絡(luò)泛化性的非單調(diào)數(shù)學關(guān)系一覽無余。

作者 | Mr Bear、杏花

編輯 | 青暮

長期以來，探尋神經(jīng)網(wǎng)絡(luò)泛化性能的量化方法一直是深度學習研究的核心目標。

盡管深度學習在許多任務(wù)上取得了巨大的成功，但是從根本上說，我們還無法很好地解釋神經(jīng)網(wǎng)絡(luò)學習的函數(shù)為什么可以很好地泛化到未曾見過的數(shù)據(jù)上。

從傳統(tǒng)的統(tǒng)計學習理論的直覺出發(fā)，過參數(shù)化的神經(jīng)網(wǎng)絡(luò)難以獲得如此好的泛化效果，我們也很難得到有用的泛化界。

因此，研究人員試圖尋找一種新的方法來解釋神經(jīng)網(wǎng)絡(luò)的泛化能力。

近日，加州大學伯克利分校的研究者于 Arxiv 上在線發(fā)表了一篇題為「NEURAL TANGENT KERNEL EIGENVALUES ACCURATELY PREDICT GENERALIZATION」的論文，指出「神經(jīng)正切核」的特征值可以準確地預(yù)測神經(jīng)網(wǎng)絡(luò)的泛化性能。

「神經(jīng)正切核」是近年來神經(jīng)網(wǎng)絡(luò)優(yōu)化理論研究的熱點概念，研究表明：通過梯度下降以無窮小的步長（也稱為梯度流）訓練的經(jīng)過適當隨機初始化的足夠?qū)挼纳窠?jīng)網(wǎng)絡(luò)，等效于使用稱為神經(jīng)正切核（NTK）的核回歸預(yù)測器。

在本文中，作者指出：通過研究神經(jīng)網(wǎng)絡(luò)的神經(jīng)正切核的特征系統(tǒng)，我們可以預(yù)測該神經(jīng)網(wǎng)絡(luò)在學習任意函數(shù)時的泛化性能。具體而言，作者提出的理論不僅可以準確地預(yù)測測試的均方誤差，還可以預(yù)測學習到的函數(shù)的所有一階和二階統(tǒng)計量。

此外，通過使用量化給定目標函數(shù)的「可學習性」的度量標準，本文作者提出了一種加強版的「沒有免費午餐定理」，該定理指出，對于寬的神經(jīng)網(wǎng)絡(luò)而言：提升其對于給定目標函數(shù)的泛化性能，必定會弱化其對于正交函數(shù)的泛化性能。

最后，作者將本文提出的理論與寬度有限（寬度僅為 20）的網(wǎng)絡(luò)進行對比，發(fā)現(xiàn)本文提出的理論在這些寬度較小的網(wǎng)絡(luò)中也成立，這表明它不僅適用于標準的 NTK，事實上也能正確預(yù)測真實神經(jīng)網(wǎng)絡(luò)的泛化性能。

論文地址：https://arxiv.org/pdf/2110.03922.pdf

1

問題定義及研究背景

作者首先將上述問題形式化定義為：從第一性原理出發(fā)，對于特定的目標函數(shù)，我們是否高效地預(yù)測給定的神經(jīng)網(wǎng)絡(luò)架構(gòu)利用有限的個訓練樣本學習到的函數(shù)的泛化性能？

該理論不僅可以解釋為什么神經(jīng)網(wǎng)絡(luò)在某些函數(shù)上可以很好地泛化，而且還可以預(yù)測出給定的網(wǎng)絡(luò)架構(gòu)適合哪些函數(shù)，讓我們可以從第一性原理出發(fā)為給定的問題挑選最合適的架構(gòu)。

為此，本文作者進行了一系列近似，他們首先將真實的網(wǎng)絡(luò)近似為理想化的寬度無限的網(wǎng)絡(luò)，這與核回歸是等價的。接著，作者針對核回歸的泛化推導出了新的近似結(jié)果。這些近似的方程能夠準確預(yù)測出原始網(wǎng)絡(luò)的泛化性能。

本文的研究建立在無限寬網(wǎng)絡(luò)理論的基礎(chǔ)之上。該理論表明，隨著網(wǎng)絡(luò)寬度趨于無窮大，根據(jù)類似于中心極限定理的結(jié)果，常用的神經(jīng)網(wǎng)絡(luò)會有非常簡單的解析形式。特別是，采用均方誤差（MSE）損失的梯度下降訓練的足夠?qū)挼木W(wǎng)絡(luò)等價于 NTK 核回歸模型。利用這一結(jié)論，研究者們研究者們通過對核回歸的泛化性能分析將相同的結(jié)論推廣至了有限寬的網(wǎng)絡(luò)。

Bordelon 等人于 2020 年發(fā)表的 ICML 論文「Spectrum dependent learning curves in kernel regression and wide neural networks」指出，當使用 NTK 作為核時，其表達式可以精準地預(yù)測學習任意函數(shù)的神經(jīng)網(wǎng)絡(luò)的 MSE。我們可以認為，當樣本被添加到訓練集中時，網(wǎng)絡(luò)會在越來越大的輸入空間中泛化得很好。這個可學習函數(shù)的子空間的自然基即為 NTK 的特征基，我們根據(jù)其特征值的降序來學習特征函數(shù)。

具體而言，本文作者首先形式化定義了目標函數(shù)的可學習性，該指標具備 MSE 所不具備的一些理想特性。接著，作者使用可學習性來證明了一個加強版的「沒有免費午餐定理」，該定理描述了核對正交基下所有函數(shù)的歸納偏置的折中。該定理表明，較高的 NTK 本征模更容易學習，且這些本征模之間在給定的訓練集大小下的學習能力存在零和競爭。作者進一步證明，對于任何的核或較寬的網(wǎng)絡(luò)，這一折中必然會使某些函數(shù)的泛化性能差于預(yù)期。

2

特征值與特征向量

令A(yù)為n階方陣，若存在數(shù)λ和非零向量x，使得Ax=λx，則λ稱為A的特征值，x為A對應(yīng)于特征值λ的特征向量。

圖 1：特征值與特征向量的定義

簡而言之，由于λ為常量，矩陣A并不改變特征向量的方向，只是對特征向量進行了尺度為λ的伸縮變換：

圖 2：特征值與特征向量的幾何意義

通過在特征向量為基構(gòu)成的向量空間中將神經(jīng)網(wǎng)絡(luò)重新表示，我們得以將不同初始化的神經(jīng)網(wǎng)絡(luò)以及學習后的神經(jīng)網(wǎng)絡(luò)進行量化對比。

3

神經(jīng)正切核

一個前饋神經(jīng)網(wǎng)絡(luò)可以代表下面的函數(shù)：

其中，θ是一個參數(shù)向量。令訓練樣本為x，目標值為y，測試數(shù)據(jù)點為x'，假設(shè)我們以較小的學習率η執(zhí)行一步梯度下降，MSE 損失為。則參數(shù)會以如下所示的方式更新：

我們希望知道對于測試點而言，參數(shù)更新的變化有多大。為此，令θ線性變化，我們得到：

其中，我們將神經(jīng)正切核 K 定義為：

值得注意的是，隨著網(wǎng)絡(luò)寬度區(qū)域無窮大，修正項可以忽略不計，且在任意的隨機初始化后，在訓練的任何時刻都是相同的，這極大簡化了對網(wǎng)絡(luò)訓練的分析?？梢宰C明，在對任意數(shù)據(jù)集上利用 MSE 損失進行無限時長的訓練后，網(wǎng)絡(luò)學習到的函數(shù)可以歸納如下：

4

近似核回歸的泛化

為了推導核回歸的泛化性，我們將問題簡化，僅僅觀察核的特征基上的學習問題。我們將核看做線性操作，其特征值/向量對滿足：

直觀地說，核是一個相似函數(shù)，我們可以將它的高特征值特征函數(shù)解釋為「相似」點到相似值的映射。在這里，我們的分析重點在于對泛化性的度量，我們將其稱之為「可學習性」，它量化了標函數(shù)和預(yù)測函數(shù)的對齊程度：

我們將初始化的神經(jīng)網(wǎng)絡(luò)f和學習目標函數(shù)f^分別用特征向量展開：

并以內(nèi)積的形式提出可學習性的表達式：

這樣就可以計算f和f^之間的接近（可學習）程度。

作者還推導出了學習到的函數(shù)的所有一階和二階統(tǒng)計量的表達式，包括恢復(fù)之前的 MSE 表達式。如圖 3 所示，這些表達式不僅對于核回歸是相當準確的，而且也可以精準預(yù)測有限寬度的網(wǎng)絡(luò)。

圖 3：為四種訓練集大小不同的布爾函數(shù)訓練神經(jīng)網(wǎng)絡(luò)的泛化性能度量。無論是對 MSE 還是可學習性而言，理論預(yù)測結(jié)果（曲線）與真實性能（點）都能夠很好地匹配。

5

核回歸的沒有免費午餐定理

除了對泛化性能的近似，本文作者還針對核回歸問題提出了一種加強版的「沒有免費午餐定理」。經(jīng)典的「沒有免費午餐定理」的結(jié)論是：由于對所有可能函數(shù)的相互補償，最優(yōu)化算法的性能是等價的。

圖 4：經(jīng)典的沒有免費午餐定理（來源：《機器學習》，周志華）

簡單地說，如果某種學習算法在某些方面比另一種學習算法更優(yōu)，則肯定會在其它某些方面弱于另一種學習算法。具體而言，沒有免費午餐定理表明：

• 1）對所有可能的的目標函數(shù)求平均，得到的所有學習算法的「非訓練集誤差」的期望值相同；

• 2）對任意固定的訓練集，對所有的目標函數(shù)求平均，得到的所有學習算法的「非訓練集誤差」的期望值也相同；

• 3）對所有的先驗知識求平均，得到的所有學習算法的「非訓練集誤差」的期望值也相同；

• 4）對任意固定的訓練集，對所有的先驗知識求平均，得到的所有學習算法的的「非訓練集誤差」的期望值也相同。

對于核回歸問題而言，所有可能的目標函數(shù)的期望滿足：

所有核特征函數(shù)的可學習性與訓練集大小正相關(guān)。

圖 5：可學習性的特征函數(shù)之和始終為訓練集的大小。

如圖 5 所示，堆疊起來的柱狀圖顯式了一個在十點域上的十個特征函數(shù)的隨機 D 可學習性。堆疊起來的數(shù)據(jù)柱顯示了十個特征函數(shù)的 D-可學習性，他們都來自相同的訓練集 D，其中數(shù)據(jù)點個數(shù)為 3，我們將它們按照特征值的降序從上到下排列。每一組數(shù)據(jù)柱都代表了一種不同的網(wǎng)絡(luò)架構(gòu)。對于每個網(wǎng)絡(luò)架構(gòu)而言，每個數(shù)據(jù)柱的高度都近似等于 n。在圖（A）中，對于每種學習情況而言，左側(cè)的 NTK 回歸的 D-可學習性之和恰好為 n，而右側(cè)代表有限寬度網(wǎng)絡(luò)的柱與左側(cè)也十分接近。

6

實驗結(jié)果

在本文中，作者通過一系列實驗證明了對有限寬度網(wǎng)絡(luò)和 NTK 回顧IDE所有理論預(yù)測。在實驗過程中，所有的實驗架構(gòu)為帶有 4 個隱藏層的全連接網(wǎng)絡(luò)，使用的激活函數(shù)為 ReLU，網(wǎng)絡(luò)寬度為 500。由于使用了全連接網(wǎng)絡(luò)，因此其核為旋轉(zhuǎn)不變性 NTK。實驗使用了三個不同的輸入空間x（離散的單位元、超立方體、超球面）。對于每個輸入空間而言，x的特征模會被劃分到k∈N的退化子集中，其中 k 越大則空間中的變化越快。在所有情況下，隨著k的增大，特征值會減小，這與人們普遍認為的神經(jīng)網(wǎng)絡(luò)傾向于緩慢變化函數(shù)的「頻譜偏置」（Spectral bias）是一致的。

神經(jīng)核的譜分析結(jié)果

圖 6：神經(jīng)核的譜分析使我們可以準確地預(yù)測學習和泛化的關(guān)鍵度量指標。

圖 6 中的圖表展示了帶有四個隱藏層、激活函數(shù)為 ReLU 的網(wǎng)絡(luò)學習函數(shù)的泛化性能，其中訓練數(shù)據(jù)點的個數(shù)為 n。理論預(yù)測結(jié)果與實驗結(jié)果完美契合。

• （A-F）經(jīng)過完整 batch 的梯度下降訓練后，模型學到的數(shù)據(jù)插值圖。隨著 n 增大，模型學到的函數(shù)越來越接近真實函數(shù)。本文提出的理論正確地預(yù)測出：k=2 時學習的速率比 k=7 時更快，這是因為 k=2 時的特征值更大。

• （G,J）為目標函數(shù)和學習函數(shù)之間的 MSE，它是關(guān)于 n 的函數(shù)。圖中的點代表均值，誤差條代表對稱的 1σ方差。曲線展示出了兩盒的一致性，它們正確地預(yù)測了 k=2 時 MSE 下降地更快。
  

• （H,K）為偽本征模的傅里葉系數(shù)，。由于 k=2 時的特征值更大，此時的傅里葉系數(shù)小于 k=7 時的情況。在這兩種模式下，當被充分學習時，傅里葉系數(shù)都會趨向于 0。實驗結(jié)果表明理論預(yù)測的 1與實驗數(shù)據(jù)完美契合。

• （I,L）可學習性：對于目標函數(shù)和學習到的函數(shù)對齊程度的度量。隨著 n 增大，在[0,1]的區(qū)間內(nèi)單調(diào)遞增。由于 k=2 時的特征值更大，其可學習性也更高。

預(yù)測可學習性

圖 7：理論預(yù)測值與任意特征函數(shù)在多種輸入空間上的真實的可學習性緊密匹配。每張圖展示了關(guān)于訓練集大小 n 的特征函數(shù)的可學習性。NTK 回歸和通過梯度下降訓練的有限寬度網(wǎng)絡(luò)的理論曲線完美匹配。誤差條反映了1由于數(shù)據(jù)集的隨機選擇造成的方差。（A）單位圓上正弦特征函數(shù)的可學習性。作者將單位圓離散化為 M=2^8 個輸入點，訓練集包含所有的輸入點，可以完美地預(yù)測所有的函數(shù)。（B）8d 超立方體頂點的子集對等函數(shù)的可學習性。k值較高的特征函數(shù)擁有較小的特征值，其學習速率較慢。當 n =2^8 時，所有函數(shù)的預(yù)測結(jié)果都很完美。虛線表示 L-n/m 時的情況，所有函數(shù)的可學習性都與一個隨機模型相關(guān)。（C）超球諧函數(shù)的可學習性。具有較高 k 的特征函數(shù)有較小的特征值，學習速率較慢，在連續(xù)的輸入空間中，可學習性沒有嚴格達到 1。

可學習性的統(tǒng)一形式

圖 8：本征模的可學習性 vs. 特征值的統(tǒng)一函數(shù)形式。

對于任意的數(shù)據(jù)集大小和輸入域而言，本征模的可學習性嚴格符合曲線的形式，其中 C 為與問題無關(guān)的參數(shù)。理論曲線（實線）在每種情況下都是類似于 Sigmoid 函數(shù)的形狀。NTK 回歸和有限寬度網(wǎng)絡(luò)的真實的本征?？蓪W習性完美地契合。垂直的虛線代表每個學習問題下的 C 值。（A-C）可學習性 vs. 單位圓本征模的特征值。（D-F）n=64 時的可學習性曲線。此時每條曲線上的本征模都高于（A-C）中的情況，這說明由于 n 的增大導致可學習性也得以提升。（G）中的點來自（A-F），經(jīng)過了放縮處理，放到了同一張圖中。

非均方誤差曲線

圖 9：本文提出的理論可以正確預(yù)測，對于特征值較小的特征函數(shù)。

MSE會隨著數(shù)據(jù)點被加入到較小的訓練集中而增大。（A-C）在給定的 n 個訓練點的 3 個不同域上分別學習 4 個不同特征模時，NTK 回歸和有限網(wǎng)絡(luò)的泛化 MSE。理論曲線與實驗數(shù)據(jù)非常吻合。

寬度有限網(wǎng)絡(luò)下的情況

圖 10：即使是對于寬度非常窄的網(wǎng)絡(luò)，本文理論上對可學習性的預(yù)測仍然十分準確。

上圖顯式了 8d 超立方體上的四個特征模式的可學習性和訓練集大小的關(guān)系，作者使用了一個包含 4 個隱藏層的網(wǎng)絡(luò)進行學習，其網(wǎng)絡(luò)寬度可變，激活函數(shù)為 ReLU。所有圖表中的理論曲線都相同，虛線表示了樸素的、泛化性能極差的模型的可學習性。（A）嚴格的 NTK 回歸下的可學習性（B-F）有限寬度網(wǎng)絡(luò)的可學習性。隨著寬度的減小，平均的可學習性微弱增大， 1σ誤差增大。盡管如此，即使在寬度僅僅為 20 時，平均學習率也與理論預(yù)測值十分契合。

7

質(zhì)疑

在reddit上，有人指出，這種量化計算的前提是要學習的函數(shù)f^是已知的，“但如何應(yīng)用于學習函數(shù)完全未知的情況呢？”

對此，一作回應(yīng)道：沒錯，我們的理論假設(shè)知道完整的目標學習函數(shù) f^，而在實踐中我們只能看到一個訓練集。

“但從折中的角度來使用該理論也是可行的。假設(shè)我們知道目標學習函數(shù)屬于少數(shù)可能函數(shù)之一。 該理論原則上包含足夠的信息來優(yōu)化內(nèi)核，因此它在所有可能函數(shù)上都具有很高的平均性能。 當然，目標學習函數(shù)永遠不會只是少數(shù)幾個離散選項中的一個。但是如果擁有一些關(guān)于目標學習函數(shù)的先驗——例如，自然圖像可能服從某些統(tǒng)計。另外，或許也可以從數(shù)據(jù)-數(shù)據(jù)內(nèi)核矩陣中獲得足夠的信息來使用該理論，我們以后可能會探索這個方向！”

8

結(jié)語

在本文中，作者提出了一種神經(jīng)網(wǎng)絡(luò)泛化的第一性原理，該理論能有效、準確地預(yù)測許多泛化性能指標。這一理論為神經(jīng)網(wǎng)絡(luò)的歸納偏置提供了新的視角，并為理解它們的學習行為提供了一個總體框架，為許多其他深度學習之謎的原理研究打開一扇嶄新的大門。

參考鏈接：

https://www.reddit.com/r/MachineLearning/comments/qfy76l/r_neural_tangent_kernel_eigenvalues_accurately/

雷鋒網(wǎng)雷鋒網(wǎng)

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