大規(guī)模核方法的隨機(jī)假設(shè)空間方法*

馮 昌，廖士中

天津大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300350

1 引言

大規(guī)模核方法是大規(guī)模數(shù)據(jù)分析與挖掘的基本機(jī)器學(xué)習(xí)方法之一。已有工作表明，大規(guī)模核方法不僅可給出與深度神經(jīng)網(wǎng)絡(luò)相當(dāng)?shù)膶W(xué)習(xí)精度[1]，而且模型簡(jiǎn)單，理論堅(jiān)實(shí)。

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

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

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

隨機(jī)傅里葉特征映射方法通過近似平移不變核顯式構(gòu)造特征映射，保證任意兩點(diǎn)對(duì)應(yīng)隨機(jī)特征映射的內(nèi)積近似其對(duì)應(yīng)的核函數(shù)值，為顯式構(gòu)造假設(shè)空間求解大規(guī)模核方法提供了一種有效途徑[14-15]。循環(huán)隨機(jī)特征映射給出一種關(guān)于樣本維度對(duì)數(shù)線性時(shí)間復(fù)雜度的核函數(shù)近似方法[16]。本文應(yīng)用循環(huán)隨機(jī)特征映射構(gòu)造D維隨機(jī)假設(shè)空間：

其中，α∈?D；Π為循環(huán)隨機(jī)矩陣；b為隨機(jī)向量；C為某一常量；FD為循環(huán)隨機(jī)假設(shè)空間。基于拉德馬赫復(fù)雜性（Rademacher complexity），推導(dǎo)了循環(huán)隨機(jī)假設(shè)空間的一致泛化誤差界，并給出了其相對(duì)于再生核希爾伯特空間中最優(yōu)假設(shè)泛化誤差的偏差上界。實(shí)驗(yàn)驗(yàn)證了本文方法不僅能夠顯著地提高非線性核方法的計(jì)算效率，而且能夠保證預(yù)測(cè)精度。大規(guī)模核方法的隨機(jī)假設(shè)空間方法理論堅(jiān)實(shí)，計(jì)算高效，實(shí)現(xiàn)簡(jiǎn)單，是一種大規(guī)模核方法的高效實(shí)現(xiàn)方法。

2 預(yù)備知識(shí)

下面簡(jiǎn)要介紹與循環(huán)矩陣有關(guān)的基本知識(shí)及隨機(jī)傅里葉特征映射。

2.1 循環(huán)矩陣

循環(huán)矩陣是一種Toeplitz矩陣，有如下形式：

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

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

由定理1可知，對(duì)于任意m維向量x，基于快速傅里葉變換（fast Fourier transform，F(xiàn)FT）和快速傅里葉逆變換，循環(huán)矩陣投影Cx可在O(mlbm)時(shí)間復(fù)雜度內(nèi)計(jì)算。

2.2 隨機(jī)傅里葉特征映射

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

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

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

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

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

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

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

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

3 循環(huán)隨機(jī)假設(shè)空間

首先介紹循環(huán)隨機(jī)特征映射，然后應(yīng)用循環(huán)隨機(jī)特征映射顯式構(gòu)造循環(huán)隨機(jī)假設(shè)空間。

3.1 循環(huán)隨機(jī)特征映射

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

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

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

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

3.2 循環(huán)隨機(jī)假設(shè)空間

定義2（循環(huán)隨機(jī)假設(shè)空間（circulant random hypothesis space，CRHS））基于循環(huán)隨機(jī)特征映射（3）定義如下D維假設(shè)空間：

其中α∈?D，稱之為循環(huán)隨機(jī)假設(shè)空間。

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

其中σ1,σ2,…,σm為獨(dú)立同分布拉德馬赫隨機(jī)變量。

引理1循環(huán)隨機(jī)假設(shè)空間FD的拉德馬赫復(fù)雜性：

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

機(jī)器學(xué)習(xí)算法的預(yù)測(cè)性能一般通過輸出假設(shè)的泛化誤差（generalization error）進(jìn)行度量。假設(shè)的泛化誤差定義如下：

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

其中，l表示訓(xùn)練樣本的規(guī)模。循環(huán)隨機(jī)假設(shè)空間中任意假設(shè)的泛化誤差界可由經(jīng)驗(yàn)風(fēng)險(xiǎn)來界定。

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

證明基于拉德馬赫復(fù)雜性，文獻(xiàn)[21]給出了期望風(fēng)險(xiǎn)與經(jīng)驗(yàn)風(fēng)險(xiǎn)之間的關(guān)系：

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

令Ω表示循環(huán)隨機(jī)假設(shè)空間的參數(shù)空間，p(ω)為參數(shù)空間上的概率分布。與隨機(jī)循環(huán)假設(shè)空間FD對(duì)應(yīng)，定義如下假設(shè)類：

Fp由參數(shù)空間Ω上加權(quán)余弦函數(shù)組成，其權(quán)重α(ω)衰減速度高于p(ω)。可證明Fp在再生核希爾伯特空間中是稠密的[22]。因此，再生核希爾伯特空間中假設(shè)均可由Fp中假設(shè)任意逼近。進(jìn)一步，可假定目標(biāo)函數(shù)在Fp中，令fp=argminf∈FpR(f)，循環(huán)隨機(jī)假設(shè)空間中學(xué)習(xí)算法輸出假設(shè)記為?。

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

證明類似于文獻(xiàn)[23]，可證明循環(huán)隨機(jī)假設(shè)空間相對(duì)于Fp的近似誤差界：

進(jìn)一步結(jié)合循環(huán)隨機(jī)假設(shè)空間的一致泛化誤差界（定理3）即可證明該定理。

該定理表明在循環(huán)隨機(jī)假設(shè)空間中，學(xué)習(xí)算法輸出假設(shè)的泛化誤差以速度收斂到最優(yōu)假設(shè)fp的泛化誤差。因此，循環(huán)隨機(jī)假設(shè)空間是一種有理論保證且計(jì)算高效的顯式假設(shè)空間。

類似地，應(yīng)用RKS[14]與Fastfood[24]構(gòu)造隨機(jī)假設(shè)空間，分別記為RRHS（RKS random hypothesis space）和 FRHS（fastfood random hypothesis space），其計(jì)算復(fù)雜度與循環(huán)隨機(jī)假設(shè)空間構(gòu)造的計(jì)算復(fù)雜度對(duì)比如表1所示。

Table 1 Computational complexities of RRHS,FRHS and CRHS表1 RRHS、FRHS與CRHS構(gòu)造的計(jì)算復(fù)雜度

4 大規(guī)模核方法

下面主要針對(duì)分類與回歸問題，給出大規(guī)模核方法的循環(huán)隨機(jī)假設(shè)空間算法。

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

算法1大規(guī)模核方法的循環(huán)隨機(jī)假設(shè)空間算法

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

輸出：循環(huán)隨機(jī)假設(shè)空間及假設(shè)f。

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

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

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

（4）構(gòu)造循環(huán)隨機(jī)矩陣Π及假設(shè)空間CRHS；

（5）在CRHS中，利用訓(xùn)練數(shù)據(jù)S與正則化參數(shù)λ，訓(xùn)練正則化線性學(xué)習(xí)器。

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

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

其內(nèi)積為：

由表示定理可知，目標(biāo)假設(shè)可表示為：

KSVM與KRR可統(tǒng)一地表示為正則化學(xué)習(xí)問題：

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

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

5 實(shí)驗(yàn)結(jié)果與分析

針對(duì)分類與回歸問題，驗(yàn)證大規(guī)模核方法的循環(huán)隨機(jī)假設(shè)空間算法（CRHS）的有效性與高效性。實(shí)驗(yàn)中數(shù)據(jù)為標(biāo)桿數(shù)據(jù)集，包括二分類、多分類、回歸數(shù)據(jù)，如表2所示。

Table 2 Characteristics of datasets表2 數(shù)據(jù)集說明

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

在數(shù)據(jù)集dna和ijcnn1上，比較RRHS、FRHS和CRHS方法預(yù)測(cè)準(zhǔn)確率隨著假設(shè)空間維度D變化的情況，實(shí)驗(yàn)結(jié)果見圖1。隨著假設(shè)空間維度的增加，3種方法的預(yù)測(cè)準(zhǔn)確率快速增加然后趨于平穩(wěn)。RRHS與CRHS方法的預(yù)測(cè)準(zhǔn)確率基本趨于一致，正好與隨機(jī)特征映射近似核函數(shù)的理論結(jié)果相符合。驗(yàn)證了應(yīng)用循環(huán)隨機(jī)矩陣取代無結(jié)構(gòu)的隨機(jī)矩陣構(gòu)造隨機(jī)特征映射和隨機(jī)假設(shè)空間的有效性。當(dāng)假設(shè)空間維度較低時(shí)，在同樣的假設(shè)空間維度設(shè)置下FRHS預(yù)測(cè)準(zhǔn)確率不如其他兩種隨機(jī)假設(shè)空間方法。這是因?yàn)镕astfood近似核函數(shù)的方差比其他兩種方法近似核函數(shù)方差大。當(dāng)假設(shè)空間維度較低時(shí)，其對(duì)學(xué)習(xí)精度的影響不能忽略，F(xiàn)RHS的預(yù)測(cè)準(zhǔn)確率不如其他兩種方法。當(dāng)假設(shè)空間維度足夠高時(shí)，3種方法的預(yù)測(cè)準(zhǔn)確率相當(dāng)。

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

Fig.1 Testing accuracies of RRHS,FRHS and CRHS with hypothesis space dimension D圖1RRHS、FRHS和CRHS的預(yù)測(cè)準(zhǔn)確率隨假設(shè)空間維度的變化

Table 3 Testing accuracies and MSEs on different datasets表3 不同數(shù)據(jù)集上的測(cè)試準(zhǔn)確率和均方誤差

6 結(jié)束語

核方法在高維再生核希爾伯特空間中通過核技巧與二次優(yōu)化技術(shù)尋找一個(gè)最優(yōu)假設(shè)以求解樣本空間中的非線性學(xué)習(xí)問題。基于核矩陣的存儲(chǔ)與計(jì)算使得核方法的計(jì)算時(shí)空復(fù)雜度至少為樣本規(guī)模的平方級(jí)。當(dāng)數(shù)據(jù)規(guī)模較大時(shí)，核方法的訓(xùn)練、預(yù)測(cè)時(shí)間過長(zhǎng)，存儲(chǔ)空間需求過高，難以應(yīng)用于大規(guī)模學(xué)習(xí)問題。為此提出大規(guī)模核方法的循環(huán)隨機(jī)假設(shè)空間方法，一方面能夠在關(guān)于數(shù)據(jù)維度對(duì)數(shù)線性時(shí)間復(fù)雜度內(nèi)構(gòu)造顯式假設(shè)空間，另一方面在顯式假設(shè)空間中可應(yīng)用大量已有的線性或亞線性時(shí)間復(fù)雜度的線性學(xué)習(xí)算法來求解非線性問題。循環(huán)隨機(jī)假設(shè)空間不僅有一致泛化誤差界保證，而且其泛化誤差能夠以的速率高概率地收斂到最優(yōu)假設(shè)的泛化誤差。幾乎在所有數(shù)據(jù)集上，本文方法能夠在保證預(yù)測(cè)精度的情況下，大幅度地提高模型訓(xùn)練與預(yù)測(cè)效率。

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

Table 4 Training time on different datasets表4 不同數(shù)據(jù)集上訓(xùn)練時(shí)間 s

Table 5 Predicting time on different datasets表5 不同數(shù)據(jù)集上預(yù)測(cè)時(shí)間 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.

附中文參考文獻(xiàn)：

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

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