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

馮 昌，廖士中

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

1 引言

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

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

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

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

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

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

2 預(yù)備知識

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

2.1 循環(huán)矩陣

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

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

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

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

2.2 隨機傅里葉特征映射

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

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

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

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

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

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

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

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

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

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

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

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

定義1（循環(huán)隨機矩陣）矩陣C為m維循環(huán)矩陣，第一列元素均獨立同分布采樣于某一連續(xù)概率分布，σ0,σ1,…,σm-1為拉德馬赫隨機變量 (?[σi=1]=?[σi=-1]=1/2,i=0,1,…,m-1）。稱矩陣P=[σ0C0·;σ1C1·;…;σm-1C(m-1)·]為循環(huán)隨機矩陣，其中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)隨機矩陣。用Π代替式（2）中的投影矩陣W，得到循環(huán)隨機特征映射（circulantrandomfeaturemapping，CRF）：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 大規(guī)模核方法

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

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

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

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

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

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

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

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

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

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

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

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

其內(nèi)積為：

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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

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

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

Table 5 Predicting time on different datasets表5 不同數(shù)據(jù)集上預(yù)測時間 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].計算機研究與發(fā)展,2014,51(10):2171-2177.

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