基于神經正切核的多核學習方法

王 梅，許傳海，劉 勇

（1.東北石油大學計算機與信息技術學院，黑龍江大慶 163318；2.黑龍江省石油大數據與智能分析重點實驗室（東北石油大學），黑龍江大慶 163318；3.中國人民大學高瓴人工智能學院，北京 100872；4.大數據管理與分析方法研究北京市重點實驗室（中國人民大學），北京 100872）

（?通信作者電子郵箱liuyonggsai@ruc.edu.cn）

0 引言

核方法，如支持向量機（Support Vector Machine，SVM）［1］、最小二乘支持向量機［2］等，是一類重要的機器學習方法。這些方法隱式地將數據點從輸入空間映射到一些特征空間，并在特征空間中學習線性學習器。隱式特征映射是由核函數誘導生成，因此核函數選擇的好壞決定核方法的性能。然而，傳統的核函數如線性核函數、多項式核函數和高斯核函數等只具有淺層結構，表示能力較弱。

雖然核方法能使線性方法這樣簡單的算法表現出令人印象深刻的性能，但是它們都是基于單個核函數的單核方法，它們在處理樣本中包含異構信息［3-7］、樣本規模較大［8-9］、數據不規則或者數據分布不平坦［10］時存在很多的不足。為此，人們提出了多核學習方法代替單核方法，不僅能增強決策函數的可解釋性，還能獲得比單核模型更優的性能［11］。

為了提高多核學習方法的精度，一些人開始在規定的一組連續參數化的基本核函數的凸集中學習核問題［12］，但大多數的多核學習算法所使用的度量通常是基于半徑邊緣或其他相關的正則化泛函，通常具有較慢的收斂速度。

為解決上述問題，本文提出了一種基于神經正切核（Neural Tangent Kernel，NTK）的多核學習方法。首先，用NTK 替代傳統的核函數如線性核、高斯核和多項式核等作為多核學習方法的基核函數；接著，采用主特征值比例的度量方法證明了一種收斂速度較快的泛化誤差界，相比現有的度量方法，該度量定義在核矩陣上，可以很容易通過訓練數據進行估計；然后將主特征值度量求出的特征值比例與核目標對齊方法相結合，求出每個基核函數的最優權重系數，采用線性合成的方法求出多核決策函數進行問題的求解；最后，在標準數據集上進行實驗，結果表明本文提出的方法有著較好的效果。

1 相關工作

1.1 多核學習

與單核只學習單個核函數不同的是，多核學習遵循不同的方式學習一組基本核函數的組合系數［13］。但是，如何通過學習獲得最優的組合系數是一個需要解決的難題。針對這一問題，近年來學者們通過理論研究和經驗證明提出了多種多核學習方法。如基于Boosting［14］的多核組合方法，基于半無限線性規劃［15］的學習方法，以及簡單多核學習［16］方法和基于無限核［17］的學習方法等。在這些多核學習框架內，最終的內核函數通常是有限個基本核函數的凸組合，且基核函數需要進行提前設置。

在過去的幾年中，人們針對多核學習方法展開了大量的研究，提出了許多有效的算法來提高學習效率和預測（分類）的精度。如Alioscha-Perez 等［18］采用隨機方差縮減梯度方法，避免了大量的矩陣運算和內存分配，解決了多核學習方法無法擴展到大規模樣本的問題；Wang等［19］基于類內散布矩陣的跡，提出了一種名為跡約束多核學習的方法，該方法可以在學習基核權重的過程中同時調整正則化參數C，節省訓練時間；Liu等［20］根據每個樣本的觀測通道對樣本進行分類，提出了一種無需進行任何插補的缺失多核學習方法，提高了算法的分類性能。針對基核函數的組合策略，王梅等［21］通過求解秩空間差異性對核函數進行組合；賈涵等［22］采用模糊約束理論求解各核函數的權重得到組合核函數；He等［23］通過使用核目標對齊的方法計算單核的權重，進而構造最終的合成核。

1.2 泛化理論

基核選擇對于多核學習具有重要影響，它與泛化誤差算法密切相關，一般泛化誤差最小的核被認為是最優核。近年來，人們利用局部拉德馬赫復雜度推導出了更緊的泛化界。Koltchinskii 等［24］首次提出局部拉德馬赫復雜度的概念，利用迭代的方法獲得數據相關的上界。Bartlett等［25］基于局部拉德馬赫復雜度導出了泛化界，并進一步提出了凸函數在分類和預測問題中的一些應用。基于局部拉德馬赫復雜度和積分算子尾部特征值的關系，Kloft 等［26］導出了多核學習的泛化界。然而核函數積分算子的特征值很難計算，為此Cortes等［27］利用核矩陣的尾特征值設計了新的核學習算法。但對于不同類型的核函數，核特征值的差異可能很大，因此核函數的尾特征值不能很好地反映不同核函數的優度。對此，Liu等［28］首先考慮了核函數的特征值的相對值，并在文獻［29］中將特征值相對值的另一度量——主特征值比例應用到多核學習方法中。

1.3 神經網絡與核方法

神經網絡和核方法之間的聯系在二十幾年前就已經開始研究。Williams［30］的早期工作已經注意到具有無限寬度的單隱層的神經網絡和高斯過程之間具有等價性。Lee 等［31］又將該結果擴展到深度完全連接的神經網絡上，只對最后一層進行訓練，其余層都保留初始值。最近Jacot等［32］研究表明過參數化深層神經網絡的訓練可以用一種名為神經切線核的核回歸訓練動力學來進行表征。NTK在無限寬極限下趨于一個確定的核，而且在梯度下降的訓練過程中保持不變。雖然上述理論結果僅在無限寬度限制下是精確的，但Lee 等［33］通過實驗發現，即使對于有限寬度的實際網絡，原始網絡的預測與線性化版本的預測之間也具有很好的一致性。除了在全連接網絡上，NTK 還被應用于卷積神經網絡［34］、殘差網絡［35］和圖神經網絡［36］等多種神經網絡結構中。此外，Li 等［37］從經驗上表明，使用NTK 進行分類可以獲得具有相應結構的深層神經網絡的性能。最近的工作還比較了NTK 與普通核函數的性能，Arora等［38］通過實驗表明NTK優于高斯核和低次多項式核。

2 本文方法

下面將簡要介紹NTK、主特征值比例和核對齊等概念，然后對本文提出的基于NTK 的多核學習方法（Neural Tangent Kernel-Multi-Kernel Learning，NTK-MKL）進行闡述。

2.1 符號定義

令k：X×X→R 表示d維輸入空間X∈Rd中的核函數，它對應于再生核希爾伯特空間H中輸入向量的點積。也就是，存在映射函數φ將輸入數據從輸入空間X映射到核空間H中，使得k(xi，xj)=φ(xi)?φ(xj)，其中xi，xj∈X。

泛化誤差（風險）R(f)是度量算法性能的常用評價準則：

其中?(f(x)，y)：Y×Y→[0，B]為損失函數，B為常數。在本文中，對于分類? 是鉸鏈損失：?(t，y)=max(0，1-yt)。由于概率分布P是未知的，那么R(f)就不能被明確地計算出來，因此使用它的經驗分布：

2.2 核方法與多核學習

支持向量機（SVM）是一種比較常用的核方法。假設在二分類問題中，SVM 的目的是在特征空間中找到一個能以最小錯誤率將數據分開的分類超平面vTφ(x) +b=0，其中v是超平面的法向量，b為偏置。超平面的獲得可通過求解以下優化問題解決：

其中：ξ=(ξ1，ξ2，…，ξn)T是松弛變量的向量形式；C是權衡訓練誤差和泛化之間的正則化參數。假設αi是式（3）中第i個不等式對應的拉格朗日乘子，那么式（3）的對偶問題可以寫成：

對式（4）進行求解后，SVM的決策函數可以寫成：

其中樣本xi是具有拉格朗日乘子ai＞0的支持向量。

與用一個固定的核進行學習不同的是，多核學習通常組合不同的基核函數來獲得更好的映射性能，其采用φ(?)=的形式進行映射，且這些基核可以由不同類型的核函數或具有不同核參數的核構建。本文采用線性組合合成方法對多個基核函數進行凸組合，則最終的組合核函數Kd可表示為：

2.3 神經正切核

首先定義一個含L個隱層的全連接神經網絡，其中第0層為輸入層，第L層為輸出層。讓x∈Rd表示為輸入數據，則，那么L隱層的全連接神經網絡可以被遞歸定義為：

其中：h=1，2，…，L；表示為第h層的權重矩陣，dh為隱層的寬度；σ：R →R 是激活函數；cσ是縮放因子。本文中，對于全連接神經網絡，將σ設置為ReLU激活函數，對于NTK 考慮其為具有ReLU 激活函數的全連接神經網絡所誘導出的核函數。神經網絡的最后一層被表示為：

給定n個數據點，y′=，則神經網絡的輸出函數可以表示為：

在神經網絡的訓練過程中，使用無窮小學習速率的梯度下降最小化目標的平方損失來學習網絡參數w。對于時間t≥0 時，可以將網絡參數w視為在優化過程中出現的隨時間變化的連續變量wt。

當隱層寬度趨于無限寬限制時，即d1，d2，…，dL→∞，文獻［32］證明了wt在優化過程中保持恒定等于w0，即NTK 核在無限寬限制下不隨時間變化。此外，該文獻中還證明了在一定的隨機初始化和無限寬限制下，NTK 核概率收斂到一個確定的極限核，這意味著在某些初始化下對神經網絡的預測與使用NTK 核進行的核回歸之間是等價的。NTK 核的極限梯度核形式可以寫為：

由式（11）可知NTK 核相當于一個具有多層結構的神經網絡，相對于一般多核學習方法使用淺層結構的基核函數，NTK 對于復雜數據有著更好的表示能力，且最近的實驗工作表明，使用NTK 核的核方法的性能與具有相似網絡結構的神經網絡性能相似，某些情況下甚至更好，所以本文采用NTK核作為多核學習方法的基核函數。

2.4 核對齊

核對齊是由Cristianini等［39］引入的一種核度量標準，它定義了理想核函數，主要度量目標核函數與理想核函數之間的相似性，兩者的對齊值越大，分類器在特征空間中泛化能力越強。

定義1核對齊。設K1和K2是兩個來自數據集S={(x1，y1)，(x2，y2)，…，(xm，ym)}上的核k1和k2所導出的核矩陣，那么這兩個核之間的核對齊定義為：

當K2為從標簽y(x)中導出時，式（12）轉換為：

其中：K為核函數k對應的Gram 矩陣；y=(y1，y2，…，ym)T，yyT為理想核矩陣。

從式（13）可知，其值越大，目標核矩陣與理想核矩陣之間的距離越小，目標核函數對樣本數據的特征選擇和表示能力就越好，可以很好地度量核函數k的性能，所以本文采用核對齊方法對基核函數進行度量，計算對應基核函數的權重參數。

2.5 主特征值比例

定義2主特征值比例。設K是一個核函數，K=是它的核矩陣。那么K的主特征值比例被定義為：

其中：t∈{1，2，…，n-1}；λi(K)是矩陣K降序排列的第i個特征值；tr(K)是矩陣K的跡。

定理1假設?是一個L-Lipschitz損失函數，?K∈КNTK有：

其中：ΦK(x)是關于NTK 核的特征映射函數，КNTK是一組有限的NTK 核函數，概率為1-δ，那么當?k≥1 且時，下面的不等式成立，

其中：c3=40Δ2L2k，c4=。

證明 該定理是基于前期工作導出的，首先基于局部拉德馬赫復雜度證明了NTK 核再生希爾伯特空間關于主特征值的界。然后根據文獻［40］定理4.1的不等式

導出了關于泛化誤差R(f)和經驗誤差的不等式。上式中f為一類范圍在[-1，1]中的函數，B為常數為子根函數（sub-root function）的定點。最后，估計了，并給出了的范圍，完成了定理的證明。具體的證明過程可以參考文獻［29］的定理2。與之不同的是，本文把以前的傳統核換成了NTK核，當令k=log(n)時，的收斂速率為：

當n較大時，可以知道，所以R(f) -。可以看到，對于任意的t，的值越大，其泛化界就越緊，導出的界也就越好。

2.6 基于NTK的多核學習算法

其中：λ為正則化參數，分別表示為第i個基核函數的主特征值比例和核對齊值。將上式進行歸一化得到：

式（16）即為最終的基核函數的權重系數。那么式（6）可以改寫為：

參考式（7），最終基于SVM 的多核學習方法求解優化問題后，得到的決策函數可表示為：

綜上所述，本文基于NTK 核提出了一種名為NTK-MKL的多核學習算法，將傳統的單層次的基核函數改為具有深層結構的NTK 核，將核對齊方法和主特征值比例結合來求取基核函數的權重參數，最后以線性加權組合的方式來構造多核函數進行問題的求解，算法的具體流程如算法1所示。

算法1 NTK-MKL。

3）基于步驟1）、2）根據式（16）求得基核函數權重參數αi；

4）將αi根據式（16）進行歸一化得到最終的權重參數；

6）將Kd代入多核SVM 中求解優化問題，求出決策函數f(x)。

2.7 時間復雜度分析

假設數據集的規模為n，基核函數個數為m，特征值個數為t，輸入數據的維度為d，則計算基核函數的主特征值比例的時間復雜度為O(tn2)，計算基核函數的相似性度量的時間復雜度為O(n2)，計算具有L個隱層全連接神經網絡的NTK 的時間復雜度為O(n2(d+L))，應用梯度下降法求解優化問題的時間復雜度為O(n2)。由此可知，本文提出的NTK-MKL 算法的時間復雜度為O(tmn2)+O(mn2)+O(n2)+O(mn2(d+L))。

3 實驗結果與分析

3.1 數據集

本文采用6 個UCI 數據集來驗證所提算法的性能，其中包括汽車評估數據集（car）、避孕方法選擇數據集（cmc）、紅酒質量數據集（red-wine）、苗圃數據集（nursery）、網上購物者購買意圖數據集（shoppers）和阿維拉（avila）數據集，數據集的詳細信息如表1所示。

表1 UCI數據集信息Tab.1 UCI dataset information

雖然UCI 數據集是標準數據集，但其官網提供的原始數據中還是會出現一些格式的問題，不能直接用于程序的計算，需要對其進行相應的處理。如avila 數據集標簽屬性的值為A-I和W-Y 共計12類，為方便進行分類任務，需將連續數值離散化，本文根據不同類別所占的數據規模，將數據分為三類，其中A 和B-F各為一類，G-I與W-Y 合成為一類，分別用0、1、2表示。還有一些數據集中存在一些字符型離散型數據，需要將其根據某種規則轉換為數值型數據。如car 數據集中的low、med、high和vhigh等屬性值，本文在[-1，1]區間內平均取n個實數進行替換，n為字符型屬性個數，那么low、med、high和vhigh根據規則被轉換為-1、-0.5、0.5和1。

3.2 實驗方法與結果分析

本節將通過2 類實驗來驗證本文提出的多核學習方法的有效性和可行性。實驗1 為NTK 與傳統的核函數的對比實驗，實驗2 為在本文提出的多核學習方法上分別使用傳統核和NTK 與其他分類算法的對比實驗。實驗采用準確率（accuracy）、召回率（recall）和精確率（precision）三個指標來對多核學習算法的性能進行評價，其中召回率和精確率為宏召回率和宏精確率。所有實驗均隨機選取70%數據作為訓練數據，30%作為測試數據。

3.2.1 單核對比實驗及結果

首先利用Google 開發的NEURAL TANGENTS 軟件包來隨機初始化3 個NTK 函數，分別用ntk1、ntk2和ntk3表示，隨機數的范圍為｛0，1，2｝。每個ntk的網絡結構均為3層，第0層為輸入層，第3 層為輸出層，激活函數為ReLU，第一層的神經元數均為2 048；第二層的神經元數均為2。然后將3 個NTK 函數與高斯核函數和多項式核函數應用到支持向量模型，在car數據集和shoppers 數據集上進行對比實驗，其中高斯核函數的參數為0.1，多項式核函數的參數為3，car 數據集和shoppers 數據集的實驗結果如表2。由表2 可以看出，NTK 的準確率在兩個數據集上均高于傳統的核函數，說明NTK 相較于傳統的核函數有著更好的效果。除此之外，在表2 中傳統核雖然有著不錯的準確率，但精確率和召回率相對較低，也就是說傳統核在進行多分類時對數據規模較大的類別識別效果較好，但對于規模較小的類識別效果較差。由此，也可看出NTK 相較于傳統的核函數，在數據集較大且數據分布不均衡時有著更好的表示能力。

表2 car數據集和shoppers數據集上的實驗結果 單位：%Tab.2 Experimental results on car dataset and shoppers dataset unit：%

3.2.2 分類算法對比實驗及結果

首先采用與上一節相同的方法來完成NTK 的初始化，然后對傳統核和NTK 采用2.6 節所描述的算法，在cmc、redwine、nursery、shoppers 和avila 數據集上與Adaboost 算法和K近鄰（K-Nearest Neighbor，KNN）算法進行對比。其中Adaboost 算法的最大迭代次數（n_estimators）設置為50，學習率（learning_rate）設置為1；KNN 算法的k值設置為5，近鄰樣本的權重（weights）設置為uniform。分類算法在數據集上的準確率結果如表3 所示，其中：MKL（r+p）表示使用高斯核和多項式核采用本文所提算法進行組合計算，NTK-MKL 表示使用ntk2和ntk3使用本文算法組合計算。由表3 可以看出，MKL（r+p）和NTK-MKL 的效果在所有數據集上都比Adaboost和KNN 算法要好，說明本文的NTK-MKL 算法是有效且可行的。除此之外，在nursery、shoppers 和avila 等規模較大的數據集上NTK-MKL 效果要好于MKL（r+p），說明NTK 核相較于傳統的核函數在處理較大規模的數據時具有更好的表示能力。

表3 分類算法對比實驗結果 單位：%Tab.3 Experimental results comparison of classification algorithms unit：%

4 結語

本文基于主特征值比例和目標核對齊度量，提出了一種新的多核學習算法NTK-MKL。該算法首先使用NTK 作為多核學習的基核函數，然后將主特征值比例和核對齊相結合作為基核函數的度量準則，求出每個基核函數的權值比例，根據權值比例將基核函數進行線性加權組合，基于SVM 形成多核學習分類器，完成分類任務。相較于傳統的多核學習方法，NTK-MKL 擁有更好的表示能力和更快收斂速率的泛化誤差界。實驗結果表明，本文提出的多核學習方法在多個數據集上的學習結果較佳。由于NTK 核具有多層結構，在對其進行計算時需要消耗較多的時間，如何減少計算時間將是下一步需要解決的問題。