王 梅，許傳海，劉 勇

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

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

0 引言

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

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

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

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

1 相關(guān)工作

1.1 多核學習

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

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

1.2 泛化理論

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

1.3 神經(jīng)網(wǎng)絡(luò)與核方法

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

2 本文方法

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

2.1 符號定義

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

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

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

2.2 核方法與多核學習

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

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

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

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

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

2.3 神經(jīng)正切核

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

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

給定n個數(shù)據(jù)點，y′=，則神經(jīng)網(wǎng)絡(luò)的輸出函數(shù)可以表示為：

在神經(jīng)網(wǎng)絡(luò)的訓練過程中，使用無窮小學習速率的梯度下降最小化目標的平方損失來學習網(wǎng)絡(luò)參數(shù)w。對于時間t≥0 時，可以將網(wǎng)絡(luò)參數(shù)w視為在優(yōu)化過程中出現(xiàn)的隨時間變化的連續(xù)變量wt。

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

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

2.4 核對齊

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

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

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

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

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

2.5 主特征值比例

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

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

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

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

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

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

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

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

2.6 基于NTK的多核學習算法

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

式（16）即為最終的基核函數(shù)的權(quán)重系數(shù)。那么式（6）可以改寫為：

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

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

算法1 NTK-MKL。

3）基于步驟1）、2）根據(jù)式（16）求得基核函數(shù)權(quán)重參數(shù)αi；

4）將αi根據(jù)式（16）進行歸一化得到最終的權(quán)重參數(shù)；

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

2.7 時間復雜度分析

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

3 實驗結(jié)果與分析

3.1 數(shù)據(jù)集

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

表1 UCI數(shù)據(jù)集信息Tab.1 UCI dataset information

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

3.2 實驗方法與結(jié)果分析

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

3.2.1 單核對比實驗及結(jié)果

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

表2 car數(shù)據(jù)集和shoppers數(shù)據(jù)集上的實驗結(jié)果 單位：%Tab.2 Experimental results on car dataset and shoppers dataset unit：%

3.2.2 分類算法對比實驗及結(jié)果

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

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

4 結(jié)語

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