大規模核方法的隨機假設空間方法*

馮 昌，廖士中

天津大學 計算機科學與技術學院，天津 300350

1 引言

大規模核方法是大規模數據分析與挖掘的基本機器學習方法之一。已有工作表明，大規模核方法不僅可給出與深度神經網絡相當的學習精度[1]，而且模型簡單，理論堅實。

核方法是在核誘導的再生核希爾伯特空間（reproducing kernel Hilbert space，RKHS）中訓練線性學習器以求解原始學習問題，例如支持向量機（support vector machine，SVM)與核嶺回歸（kernel ridge regression，KRR)。在高維再生核希爾伯特空間中，核方法訓練線性學習器得到的假設具有較好預測性能。但是基于核矩陣的存儲與計算使得核方法的計算復雜度至少為O(l2)，其中l表示樣本規模[2-3]。當訓練數據規模較大時，核方法的訓練時間過長，存儲空間需求過高，從而難以應用于大規模學習問題。

提高核方法可擴展性是核方法學習方法研究一直致力的目標，例如通過分解方法求解對偶二次優化問題的序貫最小優化方法[4]、基于低秩核矩陣近似的算法[5]、并行內點求解法[6]等。在再生核希爾伯特空間中，以上方法雖能在一定程度上緩解核方法對時間和空間的極大需求，但隨著噪聲樣本的增加，支持向量的個數也會線性增加[7]。這將導致核方法不僅在訓練階段，在預測階段計算開銷也將急劇增加。

大規模線性學習算法已有系統研究[8]，提出了隨機梯度下降法[9]、對偶坐標下降法[10]等。已有結果表明，線性支持向量機雖然在超高維文本和基因分類問題上能取得較好的學習效果，但是對于一般問題，預測精度很難超越核支持向量機[8]。然而，線性或亞線性時間復雜度的求解算法，計算開銷小，易于擴展到大規模問題[11]，這促進了應用線性學習算法求解非線性問題的研究工作[12-16]。核顯式特征表示方法通過顯式構造特征映射預處理數據，然后利用預處理后的數據訓練線性支持向量機[12]。相比于原始核方法，該方法計算效率高，但只局限于低維的多項式核與串核。

隨機傅里葉特征映射方法通過近似平移不變核顯式構造特征映射，保證任意兩點對應隨機特征映射的內積近似其對應的核函數值，為顯式構造假設空間求解大規模核方法提供了一種有效途徑[14-15]。循環隨機特征映射給出一種關于樣本維度對數線性時間復雜度的核函數近似方法[16]。本文應用循環隨機特征映射構造D維隨機假設空間：

其中，α∈?D；Π為循環隨機矩陣；b為隨機向量；C為某一常量；FD為循環隨機假設空間?；诶埋R赫復雜性（Rademacher complexity），推導了循環隨機假設空間的一致泛化誤差界，并給出了其相對于再生核希爾伯特空間中最優假設泛化誤差的偏差上界。實驗驗證了本文方法不僅能夠顯著地提高非線性核方法的計算效率，而且能夠保證預測精度。大規模核方法的隨機假設空間方法理論堅實，計算高效，實現簡單，是一種大規模核方法的高效實現方法。

2 預備知識

下面簡要介紹與循環矩陣有關的基本知識及隨機傅里葉特征映射。

2.1 循環矩陣

循環矩陣是一種Toeplitz矩陣，有如下形式：

可以看到循環矩陣C的每一列都可由它前一列元素循環向下平移一個元素得到。由此可知，循環矩陣可由它的第一列確定。因此，儲存m維循環矩陣的空間復雜度為Θ(m)。循環矩陣有如下離散傅里葉矩陣表示形式[17]。

定理1矩陣C的第一列元素組成的列向量記為c=[c0,c1,…,cm-1]T∈?m。C為循環矩陣的充要條件為C有如下離散傅里葉矩陣表示形式：

由定理1可知，對于任意m維向量x，基于快速傅里葉變換（fast Fourier transform，FFT）和快速傅里葉逆變換，循環矩陣投影Cx可在O(mlbm)時間復雜度內計算。

2.2 隨機傅里葉特征映射

基于Bochner定理，近似平移不變核可顯式構造隨機特征映射[14]。

定理2（Bochner定理[18]）連續函數f:?d?? 正定，當且僅當f為某一有限非負Borel測度μ的傅里葉變換：

由定理2可知，只要核函數k(?)選擇合適（歸一化），存在一個概率分布p(·)的傅里葉變換與之對應，從而有如下推論。

推論1正定平移不變核K(x,y)=k(x-y)可改寫為：

其中，w∈?d；p(w)為多維變量概率密度函數。

因此Zw,b(x),Zw,b(y)是高斯核函數的一個無偏估計。通過蒙特卡洛采樣方法逼近高斯核，構造如下隨機特征映射：

其中，wi∈d是一個高斯隨機向量，每一個元素均獨立同分布采樣于 N(0,1/σ2)；bi均勻采樣于 [-π,π]，i=1,2,…,D。以矩陣形式改寫ΦRKS：

其中，W∈D×d為高斯隨機矩陣，該矩陣每一個元素均獨立采樣于N(0,1/σ2)；b為均勻隨機向量，每一維均獨立采樣于U[-π,π]；cos(·)為逐點映射函數。由此可以看出，RKS由隨機投影與余弦變換組成。可證明ΦRKS(x),ΦRKS(y)為高斯核的一個無偏估計，近似的方差為[19-20]：

3 循環隨機假設空間

首先介紹循環隨機特征映射，然后應用循環隨機特征映射顯式構造循環隨機假設空間。

3.1 循環隨機特征映射

由定理1可知，若能用具有循環矩陣結構的隨機矩陣替代式（2）中的無特殊結構的隨機矩陣W，能夠顯著地提高隨機特征映射的計算效率，減少對存儲空間的需求。為消除循環矩陣行/列相關性，引入拉德馬赫隨機變量，定義如下循環隨機矩陣。

定義1（循環隨機矩陣）矩陣C為m維循環矩陣，第一列元素均獨立同分布采樣于某一連續概率分布，σ0,σ1,…,σm-1為拉德馬赫隨機變量 (?[σi=1]=?[σi=-1]=1/2,i=0,1,…,m-1）。稱矩陣P=[σ0C0·;σ1C1·;…;σm-1C(m-1)·]為循環隨機矩陣，其中Ci·表示循環矩陣C的第i行。

不失一般性，假設d能夠整除D，令t=D/d。構造投影矩陣Π=[P(1);P(2);…;P(t)]∈?D×d，其中P(i)為循環隨機矩陣。用Π代替式（2）中的投影矩陣W，得到循環隨機特征映射（circulantrandomfeaturemapping，CRF）：

可證明K(x,y)=[ΦCRF(x),ΦCRF(y)]，近似方差與RKS近似核函數的方差相同[16]。

3.2 循環隨機假設空間

定義2（循環隨機假設空間（circulant random hypothesis space，CRHS））基于循環隨機特征映射（3）定義如下D維假設空間：

其中α∈?D，稱之為循環隨機假設空間。

定義3（拉德馬赫復雜性[21]）函數類F的拉德馬赫復雜性定義為：

其中σ1,σ2,…,σm為獨立同分布拉德馬赫隨機變量。

引理1循環隨機假設空間FD的拉德馬赫復雜性：

證明定義集合 S={α∈?D:||α||∞≤C/D}，集合

機器學習算法的預測性能一般通過輸出假設的泛化誤差（generalization error）進行度量。假設的泛化誤差定義如下：

其中，?(f(x),y)表示損失函數；P表示X×Y上某個固定但未知的概率分布。正因P未知，所以泛化誤差R(f)不可計算，往往通過經驗風險（empirical risk）進行估計。經驗風險定義：

其中，l表示訓練樣本的規模。循環隨機假設空間中任意假設的泛化誤差界可由經驗風險來界定。

定理3（一致泛化誤差）假設間隔損失函數?(y,y′)=?(yy′) 是L-Lipschitz 連續的。對于任意δ∈(0,1)，下列不等式至少以1-δ概率成立：

證明基于拉德馬赫復雜性，文獻[21]給出了期望風險與經驗風險之間的關系：

根據引理1可知Rl(FD)的上界為，帶入上式即可證明該定理。

令Ω表示循環隨機假設空間的參數空間，p(ω)為參數空間上的概率分布。與隨機循環假設空間FD對應，定義如下假設類：

Fp由參數空間Ω上加權余弦函數組成，其權重α(ω)衰減速度高于p(ω)?？勺C明Fp在再生核希爾伯特空間中是稠密的[22]。因此，再生核希爾伯特空間中假設均可由Fp中假設任意逼近。進一步，可假定目標函數在Fp中，令fp=argminf∈FpR(f)，循環隨機假設空間中學習算法輸出假設記為?。

定理4假定學習算法的間隔損失函數?(y,y′)=?(yy′)L-Lipschitz連續。訓練樣本根據某一固定但未知的概率分布獨立生成，記為{(xi,yi)l i=1}。循環隨機假設空間 FD的隨機參數ω1,ω2,…,ωD根據p(ω)獨立生成。循環隨機假設空間中正則化經驗風險最小化算法輸出的假設?滿足，對于任意δ∈(0,1/2)，下列不等式至少以1-2δ概率成立：

證明類似于文獻[23]，可證明循環隨機假設空間相對于Fp的近似誤差界：

進一步結合循環隨機假設空間的一致泛化誤差界（定理3）即可證明該定理。

該定理表明在循環隨機假設空間中，學習算法輸出假設的泛化誤差以速度收斂到最優假設fp的泛化誤差。因此，循環隨機假設空間是一種有理論保證且計算高效的顯式假設空間。

類似地，應用RKS[14]與Fastfood[24]構造隨機假設空間，分別記為RRHS（RKS random hypothesis space）和 FRHS（fastfood random hypothesis space），其計算復雜度與循環隨機假設空間構造的計算復雜度對比如表1所示。

Table 1 Computational complexities of RRHS,FRHS and CRHS表1 RRHS、FRHS與CRHS構造的計算復雜度

4 大規模核方法

下面主要針對分類與回歸問題，給出大規模核方法的循環隨機假設空間算法。

記樣本空間中的數據集合為S={(xi,yi)l i=1}，其中xi∈?d，對于二分類問題yi={-1,+1}，對于多分類問題yi={1,2,…,M1}，M1∈?+，對于回歸問題yi∈[-M2,M2]，M2∈?+，其中i=1,2,…,l。循環隨機假設空間是一種顯式假設空間，可應用已有的線性/亞線性學習算法求解分類/回歸問題。本文提出大規模核方法的循環隨機假設空間算法框架，具體描述見算法1。

算法1大規模核方法的循環隨機假設空間算法

輸入：訓練數據S={(xi,yi)li=1}，隨機假設空間維度D，高斯核參數σ，正則化參數λ。

輸出：循環隨機假設空間及假設f。

（1）隨機生成ω1,ω2,…,ωD～N(0,I/σ2)；

（2）隨機生成b1,b2,…,bD～U[-π,π]；

（3）隨機生成σ1,σ2,…,σD～{-1,+1}；

（4）構造循環隨機矩陣Π及假設空間CRHS；

（5）在CRHS中，利用訓練數據S與正則化參數λ，訓練正則化線性學習器。

如果一個二元函數K(x,y):X×X→?能夠表示成兩個一元函數?:X→F內積的形式，即

那么稱K(x,y)為核。?(·)往往是超高維甚至是無窮維的，根據優化算法的對偶表示，核方法可以在不知道?(·)具體形式的情形下，僅僅依靠K(·,·)表示學習假設，從而避免了維數災難，此方法稱為核技巧。核K對應的RKHS為：

其內積為：

由表示定理可知，目標假設可表示為：

KSVM與KRR可統一地表示為正則化學習問題：

其中，?(·,·)為損失函數；λ為正則化系數。對于支持向量機 ?(f(x),y)=max(0,1-yf(x))，對于核嶺回歸?(f(x),y)=(f(x)-y)2。

算法時間復雜度：在隱式特征空間中，基于核技巧求解式（4）的時間復雜度至少為O(l2)，只能適用于中等以下規模學習問題。算法1時間復雜度為O(l)，可適用于大規模學習問題。

5 實驗結果與分析

針對分類與回歸問題，驗證大規模核方法的循環隨機假設空間算法（CRHS）的有效性與高效性。實驗中數據為標桿數據集，包括二分類、多分類、回歸數據，如表2所示。

Table 2 Characteristics of datasets表2 數據集說明

對比算法包括大規模核方法的RKS假設空間算法（RRHS）、大規模核方法的Fastfood假設空間算法（FRHS）與精確核方法（Kernel）。高斯核參數γ=1/(2σ2)與正則化參數λ均從備選參數集{2-9,2-7,…,27,29}中選擇。對于每一種算法，參數(γ,λ)通過5-折交叉驗證確定。假設空間維度D經驗地設置為幾百到幾千。所有隨機算法在每個數據集上重復10次，記錄平均值及均方誤差。實驗代碼用R語言實現，實驗平臺為Ubuntu Linux server 16.04，實驗環境為2.60 GHz Intel?Xeon?CPU和64 GB內存。

在數據集dna和ijcnn1上，比較RRHS、FRHS和CRHS方法預測準確率隨著假設空間維度D變化的情況，實驗結果見圖1。隨著假設空間維度的增加，3種方法的預測準確率快速增加然后趨于平穩。RRHS與CRHS方法的預測準確率基本趨于一致，正好與隨機特征映射近似核函數的理論結果相符合。驗證了應用循環隨機矩陣取代無結構的隨機矩陣構造隨機特征映射和隨機假設空間的有效性。當假設空間維度較低時，在同樣的假設空間維度設置下FRHS預測準確率不如其他兩種隨機假設空間方法。這是因為Fastfood近似核函數的方差比其他兩種方法近似核函數方差大。當假設空間維度較低時，其對學習精度的影響不能忽略，FRHS的預測準確率不如其他兩種方法。當假設空間維度足夠高時，3種方法的預測準確率相當。

在每個數據集上，統一將RRHS、FRHS和CRHS方法的假設空間維度D設置足夠高，并與精確核方法相比較，預測精度如表3所示。幾乎在所有分類與回歸數據集上，3種隨機方法都能取得與精確核方法相當或者更高的預測精度。這3種隨機方法的預測精度之間并沒有顯著差別。表4與表5分別給出了不同學習算法對應的訓練與預測時間?？梢钥闯?，幾乎在所有的數據集上，RRHS、FRHS和CRHS的訓練與預測效率明顯高于精確核方法。除了mnist和CT slices這兩個相對高維的數據集，在其他數據集上，FRHS的訓練和預測效率明顯不如RRHS和CRHS。這是因為FRHS需要通過補0的方式預處理數據以適應快速Hadamard變換。當數據維度較低時，快速Hadamard變換帶來的效率提升被數據預處理時間所抵消。因此，只有當數據維度較高時，例如mnist，FRHS的訓練與預測效率才顯著高于RRHS。然而，所提出的CRHS能夠一定程度解決FRHS所面臨的問題。一般情況下，當原始數據維度d＞100時，CRHS能夠在保持預測精度的同時顯著地提高訓練與預測效率。綜上，CRHS是一種高效的大規模核方法學習算法，適用于大規模機器學習。

Fig.1 Testing accuracies of RRHS,FRHS and CRHS with hypothesis space dimension D圖1RRHS、FRHS和CRHS的預測準確率隨假設空間維度的變化

Table 3 Testing accuracies and MSEs on different datasets表3 不同數據集上的測試準確率和均方誤差

6 結束語

核方法在高維再生核希爾伯特空間中通過核技巧與二次優化技術尋找一個最優假設以求解樣本空間中的非線性學習問題?；诤司仃嚨拇鎯εc計算使得核方法的計算時空復雜度至少為樣本規模的平方級。當數據規模較大時，核方法的訓練、預測時間過長，存儲空間需求過高，難以應用于大規模學習問題。為此提出大規模核方法的循環隨機假設空間方法，一方面能夠在關于數據維度對數線性時間復雜度內構造顯式假設空間，另一方面在顯式假設空間中可應用大量已有的線性或亞線性時間復雜度的線性學習算法來求解非線性問題。循環隨機假設空間不僅有一致泛化誤差界保證，而且其泛化誤差能夠以的速率高概率地收斂到最優假設的泛化誤差。幾乎在所有數據集上，本文方法能夠在保證預測精度的情況下，大幅度地提高模型訓練與預測效率。

進一步工作考慮循環隨機假設空間維度D的設置與概率分布N(0,I/σ2)的選擇問題。

Table 4 Training time on different datasets表4 不同數據集上訓練時間 s

Table 5 Predicting time on different datasets表5 不同數據集上預測時間 s

[1]Huang P S,Avron H,Sainath T N,et al.Kernel methods match deep neural networks on TIMIT[C]//Proceedings of the 2014 IEEE International Conference on Acoustics,Speech and Signal Processing,Florence,May 4-9,2014.Piscataway:IEEE,2014:205-209.

[2]Vapnik V N.Statistical learning theory[M].New York:Wiley-Interscience,1998.

[3]Sch?lkopf B,Smola A J.Learning with kernels:support vector machines,regularization,optimization,and beyond[M].Cambridge:MIT Press,2002.

[4]Chang C C,Lin C J.LIBSVM:a library for support vector machines[J].ACM Transactions on Intelligent Systems and Technology,2011,2(3):27.

[5]Drineas P,Mahoney M W.On the Nystr?m method for approximating a Gram matrix for improved kernel-based learning[J].Journal of Machine Learning Research,2005,6:2153-2175.

[6]Chang E Y,Zhu Kaihua,Wang Hao,et al.PSVM:parallelizing support vector machines on distributed computers[C]//Proceedings of the 21st Annual Conference on Neural Information Processing Systems,Vancouver,Dec 3-6,2007.Red Hook:CurranAssociates,2008:257-264.

[7]Steinwart I.Sparseness of support vector machines[J].Journal of Machine Learning Research,2003,4(6):1071-1105.

[8]Yuan Guoxun,Ho C H,Lin C J.Recent advances of largescale linear classif i cation[J].Proceedings of the IEEE,2012,100(9):2584-2603.

[9]Zhang Tong.Solving large sale linear prediction problems using stochastic gradient descent algorithms[C]//Proceedings of the 21st International Conference on Machine Learning,Banff,Jul 4-8,2004.New York:ACM,2004:919-926.

[10]Fan Rongen,Chang Kaiwei,Hsieh C J,et al.LIBLINEAR:a library for large linear classif i cation[J].Journal of Machine Learning Research,2008,9:1871-1874.

[11]Shalev-Shwartz S,Singer Y,Srebro N,et al.Pegasos:primal estimated sub-gradient solver for SVM[J].Mathematical Programming,2011,127(1):3-30.

[12]Chang Yinwen,Hsieh C J,Chang Kaiwei,et al.Training and testing low-degree polynomial data mappings via linear SVM[J].Journal of Machine Learning Research,2010,11:1471-1490.

[13]Liu Yong,Jiang Shali,Liao Shizhong.Approximate Gaussian kernel for large-scale SVM[J].Journal of Computer Research and Development,2014,51(10):2171-2177.

[14]Rahimi A,Recht B.Random features for large-scale kernel machines[C]//Proceedings of the 21st Annual Conference on Neural Information Processing Systems,Vancouver,Dec 3-6,2007.Red Hook:CurranAssociates,2008:1177-1184.

[15]Feng Chang,Liao Shizhong.Model selection for Gaussian kernel support vector machines in random Fourier feature space[J].Journal of Computer Research and Development,2016,53(9):1971-1978.

[16]Feng Chang,Hu Qinghua,Liao Shizhong.Random feature mapping with signed circulant matrix projection[C]//Proceedings of the 24th International Joint Conference on Artif icial Intelligence,Buenos Aires,Jul 25-31,2015.Menlo Park:AAAI,2015:3490-3496.

[17]Davis P J.Circulant matrices[M].San Francisco:John Wiley&Sons,1979:1-250.

[18]Rudin W.Fourier analysis on groups[M].San Francisco:John Wiley&Sons,2011:1-285.

[19]Sutherland D J,Schneider J G.On the error of random Fourier features[C]//Proceedings of the 31st Conference on Uncertainty in Artif i cial Intelligence,Amsterdam,Jul 12-16,2015.Corvallis:AUAI Press,2015:862-871.

[20]Yu F X,Suresh A T,Choromanski K,et al.Orthogonal random features[C]//Proceedings of the Annual Conference on Neural Information Processing Systems,Barcelona,Dec 5-10,2016.Red Hook:CurranAssociates,2016:1975-1983.

[21]Bartlett P L,Mendelson S.Rademacher and Gaussian complexities:risk bounds and structural results[J].Journal of Machine Learning Research,2002,3:463-482.

[22]Rahimi A,Recht B.Uniform approximation of functions with random bases[C]//Proceedings of the 46th Annual Allerton Conference on Communication,Control,and Computing,Monticello,Sep 23-26,2008.Piscataway:IEEE,2008:555-561.

[23]Rahimi A,Recht B.Weighted sums of random kitchen sinks:replacing minimization with randomization in learning[C]//Proceedings of the 22nd Annual Conference on Neural Information Processing Systems,Vancouver,Dec 8-11,2008.Red Hook:CurranAssociates,2009:1313-1320.

[24]Le Q,Sarlós T,Smola A J.Fastfood—approximating kernel expansions in loglinear time[C]//Proceedings of the 30th International Conference on Machine Learning,Atlanta,Jun 16-21,2013.Brookline:Microtome Publishing,2013:244-252.

附中文參考文獻：

[13]劉勇,江沙里,廖士中.基于近似高斯核顯式描述的大規模SVM求解[J].計算機研究與發展,2014,51(10):2171-2177.

[15]馮昌,廖士中.隨機傅里葉特征空間中高斯核支持向量機模型選擇[J].計算機研究與發展,2016,53(9):1971-1978.