馮　昌　　　廖士中

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

?

隨機(jī)傅里葉特征空間中高斯核支持向量機(jī)模型選擇

馮昌廖士中

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

(changfeng@tju.edu.cn)

模型選擇是支持向量機(jī)(support vector machines, SVMs)學(xué)習(xí)的關(guān)鍵問(wèn)題.標(biāo)準(zhǔn)支持向量機(jī)學(xué)習(xí)本質(zhì)上是求解一個(gè)凸二次優(yōu)化問(wèn)題，求解的時(shí)間復(fù)雜度為數(shù)據(jù)規(guī)模的立方級(jí)，而經(jīng)典的模型選擇方法往往需要多次訓(xùn)練支持向量機(jī)，這種模型選擇方法對(duì)于中等規(guī)模的支持向量機(jī)學(xué)習(xí)計(jì)算代價(jià)已較高，更難以擴(kuò)展到大規(guī)模支持向量機(jī)學(xué)習(xí).基于高斯核函數(shù)的隨機(jī)傅里葉特征近似，提出一種新的、高效的核支持向量機(jī)模型選擇方法.首先，利用隨機(jī)傅里葉特征映射，將無(wú)限維隱式特征空間嵌入到一個(gè)相對(duì)低維的顯式隨機(jī)特征空間，并推導(dǎo)在2個(gè)不同的特征空間中分別訓(xùn)練支持向量機(jī)所得到的模型的誤差上界；然后，以模型誤差上界為理論保證，提出隨機(jī)特征空間中核支持向量機(jī)的模型選擇方法，應(yīng)用隨機(jī)特征空間中的線性支持向量機(jī)來(lái)逼近核支持向量機(jī)，計(jì)算模型選擇準(zhǔn)則的近似值，從而評(píng)價(jià)所對(duì)應(yīng)的核支持向量機(jī)的相對(duì)優(yōu)劣；最后，在標(biāo)桿數(shù)據(jù)集上驗(yàn)證所提出方法的可行性和高效性.實(shí)驗(yàn)結(jié)果表明，所提出的模型選擇方法與標(biāo)準(zhǔn)交叉驗(yàn)證方法的測(cè)試精度基本相當(dāng)，但可顯著地提高核支持向量機(jī)模型選擇效率.

模型選擇；支持向量機(jī)；隨機(jī)傅里葉特征；高斯核；交叉驗(yàn)證

支持向量機(jī)(support vector machines, SVMs)是在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上發(fā)展起來(lái)的一類(lèi)重要的學(xué)習(xí)方法，是目前流行的數(shù)據(jù)挖掘方法之一[1-2].該方法在核誘導(dǎo)的特征空間中訓(xùn)練線性學(xué)習(xí)器，并應(yīng)用泛化性理論來(lái)避免過(guò)擬合現(xiàn)象.

SVM的泛化性能主要依賴(lài)于核函數(shù)及模型參數(shù)的選擇，不合適的選擇將會(huì)導(dǎo)致過(guò)擬合(over-fitting)或欠擬合(under-fitting)，因此模型選擇是SVM學(xué)習(xí)的重要問(wèn)題.本文主要考慮高斯核SVM的模型選擇問(wèn)題，即核參數(shù)γ和特征空間中線性學(xué)習(xí)器正則化系數(shù)C的選擇，其中(γ,C)合稱(chēng)為超參數(shù)[3].

已有的模型選擇方法可概括為一個(gè)內(nèi)外雙層的優(yōu)化框架[4]：內(nèi)層在超參數(shù)固定的情況下在隱式特征空間中訓(xùn)練學(xué)習(xí)器，本質(zhì)上是求解一個(gè)標(biāo)準(zhǔn)的凸二次優(yōu)化問(wèn)題；基于內(nèi)層的學(xué)習(xí)結(jié)果，外層通過(guò)最小化泛化誤差來(lái)調(diào)節(jié)超參數(shù).k-折交叉驗(yàn)證(k-fold cross validation,k-CV)是泛化誤差的有效估計(jì)[5]，被廣泛應(yīng)用在不同問(wèn)題的學(xué)習(xí)過(guò)程中.對(duì)于參數(shù)空間中的每一組參數(shù)(γ,C)，k-CV需要訓(xùn)練學(xué)習(xí)器k次，因此計(jì)算代價(jià)較高.最小化泛化誤差的理論上界是另外一類(lèi)模型選擇方法[6-7]，通?？梢詰?yīng)用梯度下降算法實(shí)現(xiàn).常見(jiàn)理論上界有半徑間隔界(radius margin bound)[6]、span界[7]等.一般來(lái)說(shuō)，在優(yōu)化框架外層，基于理論上界的模型選擇方法僅僅只需在梯度下降方向評(píng)估模型，不再需要搜索整個(gè)參數(shù)空間，從而提高模型選擇效率，但是該類(lèi)方法仍需多次訓(xùn)練SVM.

在核誘導(dǎo)的特征空間中訓(xùn)練線性學(xué)習(xí)器本質(zhì)上是求解一個(gè)凸二次優(yōu)化問(wèn)題，求解時(shí)間復(fù)雜度為O(l3)，其中l(wèi)為訓(xùn)練樣本的個(gè)數(shù).基于分解法實(shí)現(xiàn)的高效SVM求解器，最小序貫優(yōu)化算法(sequential minimal optimization, SMO)，求解時(shí)間復(fù)雜度為O(l2)[8].若利用10折交叉驗(yàn)證模型選擇，在10×10=100個(gè)(γ,C)參數(shù)組合上進(jìn)行SVM學(xué)習(xí)，需要訓(xùn)練1 000個(gè)SVM；若應(yīng)用理論上界方法進(jìn)行模型選擇，仍需要訓(xùn)練多個(gè)SVM.對(duì)于一般規(guī)模的數(shù)據(jù)，模型選擇過(guò)程已十分耗時(shí)，更難擴(kuò)展到大規(guī)模問(wèn)題.

線性SVM研究引起了廣泛關(guān)注.大量計(jì)算高效的線性SVM算法被提出，包括隨機(jī)梯度下降算法[9]、割平面方法[10]、對(duì)偶坐標(biāo)下降算法[11]等.利用具有線性時(shí)間復(fù)雜度的線性SVM算法，日常PC機(jī)就可以有效地處理大規(guī)模問(wèn)題[12].但是對(duì)于非線性問(wèn)題，線性SVM的預(yù)測(cè)準(zhǔn)確率遠(yuǎn)不及核SVM.Rahimi和Recht[13]提出利用隨機(jī)傅里葉特征近似高斯核函數(shù)，將核誘導(dǎo)的特征空間嵌入到一個(gè)顯式的隨機(jī)特征空間，從而可以應(yīng)用高效的線性SVM一致逼近核SVM.該方法不但具有線性SVM的求解效率，而且能保持核SVM的預(yù)測(cè)精度.劉勇等人[14]基于高斯核的顯式描述給出了另外一種顯式特征映射方法,從而也能夠應(yīng)用線性算法求解非線性問(wèn)題.該類(lèi)方法將核SVM線性化，可很大程度地提升核SVM模型選擇優(yōu)化框架的內(nèi)層效率.

對(duì)于模型選擇而言，沒(méi)有必要對(duì)每個(gè)模型都計(jì)算其精確結(jié)果，所需的僅是一個(gè)能夠評(píng)估模型相對(duì)優(yōu)劣且可快速計(jì)算的近似解.基于這一思想，核矩陣近似已經(jīng)成功應(yīng)用在支持向量機(jī)和最小二乘支持向量機(jī)的高效模型選擇過(guò)程[15-17].本文基于高斯核函數(shù)的隨機(jī)傅里葉特征近似，應(yīng)用線性SVM近似核SVM，提出一種新的高斯核支持向量機(jī)模型選擇方法.首先，證明隨機(jī)特征空間中近似模型與其對(duì)應(yīng)精確模型的誤差上界.然后，在該誤差上界的保證下，提出一種隨機(jī)特征空間中核SVM模型選擇的新方法.在模型選擇優(yōu)化框架內(nèi)層，不再求解凸二次優(yōu)化問(wèn)題，而是將核誘導(dǎo)的特征空間嵌入到一個(gè)相對(duì)低維的顯式隨機(jī)特征空間，訓(xùn)練線性SVM，計(jì)算模型選擇準(zhǔn)則的近似值，評(píng)價(jià)對(duì)應(yīng)核SVM的相對(duì)優(yōu)劣.以k-折交叉驗(yàn)證模型選擇實(shí)驗(yàn)為例，驗(yàn)證所提出的方法的有效性及高效性.實(shí)驗(yàn)結(jié)果表明，在模型選擇標(biāo)準(zhǔn)數(shù)據(jù)集上，所提出的模型選擇方法與標(biāo)準(zhǔn)交叉驗(yàn)證方法測(cè)試精度相當(dāng)，但可顯著地提高核SVM模型選擇效率.

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

首先簡(jiǎn)要回顧支持向量機(jī)，然后介紹高斯核函數(shù)的隨機(jī)傅里葉特征近似.

1.1支持向量機(jī)

令S={(x1,y1),(x2,y2),…,(xl,yl)}∈(X ×Y)l表示樣本集合，其中X為輸入空間，Y為輸出域.考慮二分類(lèi)問(wèn)題，即Y={-1,+1}，輸入空間X ∈d.

軟間隔SVM原優(yōu)化問(wèn)題描述如下：

(1)

其中，常量C>0，稱(chēng)為正則化參數(shù).SVM的對(duì)偶問(wèn)題為一個(gè)標(biāo)準(zhǔn)的凸二次優(yōu)化問(wèn)題：

(2)

(3)

通過(guò)上述優(yōu)化過(guò)程可知，支持向量機(jī)的性能主要依賴(lài)于拉格朗日乘子、核函數(shù)、超參數(shù)的選擇.然而，當(dāng)核函數(shù)與超參數(shù)給定時(shí)，拉格朗日乘子可以通過(guò)優(yōu)化過(guò)程求得.因此核函數(shù)與超參數(shù)的選擇對(duì)SVM的性能起著決定性作用.不同的核函數(shù)表現(xiàn)能力不盡相同，其中高斯核是一種通用核，是使用最為廣泛的支持向量機(jī)核函數(shù)，定義形式為

(4)

1.2隨機(jī)傅里葉特征

定義1. 傅里葉變換與傅里葉逆變換.f(t)表示變量t的函數(shù)，如果f(t)滿(mǎn)足Dirichlet條件：具有有限個(gè)間斷點(diǎn)、有限個(gè)極值點(diǎn)，f(t)絕對(duì)可積，則

(5)

稱(chēng)為f(t)的傅里葉變換，且有

(6)

定理1. Bochner定理[19].連續(xù)函數(shù)f:d|→正定，當(dāng)且僅當(dāng)f為某一有限非負(fù)Borel測(cè)度μ的傅里葉變換，

(7)

只要核函數(shù)κ(·)選擇合適，Bochner定理保證存在一個(gè)概率分布p(·)的傅里葉變換與κ(·)對(duì)應(yīng)，即有如下推論.

推論1. 任一正定平移不變核k(x,y)=κ(x-y)均滿(mǎn)足式(8):

(8)

其中，p(w)為w的概率密度函數(shù).

對(duì)于高斯核函數(shù)，通過(guò)k(x,y)的傅里葉逆變換計(jì)算p(w),可得w～N (0,2γI)，其中I表示單位矩陣.易知

k(x,y)=Ew[e-iwT(x-y)]=Ew[cos(wT(x-y))]=

(9)

k(x,y)=E[〈Zw,b(x),Zw,b(y)〉],

(10)

則〈Zw,b(x),Zw,b(y)〉是高斯核函數(shù)的一個(gè)無(wú)偏估計(jì).利用標(biāo)準(zhǔn)蒙特卡洛近似積分方法逼近高斯核，構(gòu)造如下隨機(jī)特征映射

(11)

其中wi∈d是一個(gè)高斯隨機(jī)向量，服從正態(tài)分布N (0,2γI);隨機(jī)變量bi服從均勻分布U(-π,π)，i=1,2,…,D.同樣有k(x,y)=E[〈ψ(x),ψ(y)〉].

2　隨機(jī)特征空間中模型近似誤差

算法1. 隨機(jī)特征空間中線性SVM.

輸出：隨機(jī)特征空間中決策函數(shù)f.

① fori=1,2,…,Ddo

② 采樣wi∈d：wi～N (0,2γI)；

③ 采樣bi∈U [-π,π]；

④ endfor

⑤ for each (x,y)∈S do

⑥ 根據(jù)式(1)計(jì)算ψ(x)；

⑦ endfor

隨機(jī)傅里葉特征方法通過(guò)近似高斯核函數(shù)，將原始數(shù)據(jù)映射到一個(gè)相對(duì)低維的有限維特征空間，并在新的特征空間中訓(xùn)練線性學(xué)習(xí)器，算法描述見(jiàn)算法1.本節(jié)將分析在隨機(jī)特征空間中訓(xùn)練線性SVM得到模型與在原始數(shù)據(jù)空間上直接訓(xùn)練核SVM得到模型的誤差上界.

(12)

其中H=[ψ(x1)T,ψ(x2)T,…,ψ(xl)T].

命題1表明在Frobenius范數(shù)定義下，隨機(jī)特征空間中潛在的近似核矩陣Q以O(shè)(1D)的收斂速度逼近K[20].

命題1. 對(duì)于任意δ∈(0,1)，下面的式(13)以1-δ的概率成立，

(13)

假設(shè)在訓(xùn)練數(shù)據(jù)S上利用核矩陣訓(xùn)練核SVM得到的假設(shè)記為f，在隨機(jī)特征中訓(xùn)練線性SVM得到的假設(shè)記為f′，潛在的近似核矩陣為Q(注：訓(xùn)練線性SVM不需要計(jì)算核矩陣).對(duì)于任意x∈X，比較f(x)和f′(x)之間的差異.

命題2度量了SVM應(yīng)用核矩陣得到的假設(shè)與應(yīng)用近似核矩陣得到的假設(shè)之間的誤差界[21].

命題2. 記h為利用核矩陣K∈l×l訓(xùn)練核支持向量機(jī)得到的假設(shè)，h′為利用近似核矩陣K′訓(xùn)練支持向量機(jī)得到的假設(shè).進(jìn)一步，對(duì)于所有x∈X，定義τ>0,使得k(x,x)≤τ及k′(x,x)≤τ.那么，對(duì)于所有x∈X如下不等式成立：

|h′(x)-h(x)|≤

(14)

其中C0為某一常量.

定理2. 模型近似誤差界.對(duì)于任意δ∈(0,1)，所有x∈X，下列不等式以1-δ概率成立，

|f′(x)-f(x)|≤

(15)

證畢.

定理2給出了分別訓(xùn)練基于隨機(jī)特征的線性SVM及對(duì)應(yīng)高斯核SVM得到?jīng)Q策函數(shù)之間的誤差上界.隨著隨機(jī)特征空間維度D的增加，該誤差界將變得更小.該定理保證了,在隨機(jī)特征空間中訓(xùn)練線性SVM得到的近似模型能夠被用來(lái)評(píng)價(jià)在核誘導(dǎo)的特征空間中對(duì)應(yīng)精確模型的相對(duì)優(yōu)劣.

3　高斯核SVM模型選擇

模型選擇優(yōu)化框架外層通過(guò)使得泛化誤差最小化搜索參數(shù)空間，內(nèi)層則訓(xùn)練多個(gè)核SVM.本節(jié)通過(guò)應(yīng)用隨機(jī)特征方法提升模型選擇優(yōu)化框架內(nèi)層效率，即在優(yōu)化框架內(nèi)層利用基于隨機(jī)特征的線性SVM近似核SVM.

對(duì)于模型選擇而言，選擇準(zhǔn)則沒(méi)有必要是泛化誤差的無(wú)偏估計(jì)，近似準(zhǔn)則值只要能夠區(qū)分不同模型的相對(duì)優(yōu)劣選擇出最優(yōu)的模型即可.由定理2可知，在隨機(jī)特征空間中利用基于隨機(jī)特征的線性SVM近似核SVM，得到的近似模型相對(duì)于精確模型有界.因此，能夠利用此近似方法計(jì)算模型選擇準(zhǔn)則的近似值，從而高效地評(píng)價(jià)原核誘導(dǎo)的特征空間中對(duì)應(yīng)模型的相對(duì)優(yōu)劣.具體描述見(jiàn)算法2.

算法2. 基于隨機(jī)傅里葉特征的近似模型選擇算法AMS-RFF.

輸出：(γ,C)opt.

① 初始化：(γ,C)=(γ0,C0);

② repeat

③ 利用算法1在訓(xùn)練集S上訓(xùn)練學(xué)習(xí)器，得到線性決策函數(shù)f；

④ 利用f計(jì)算模型選擇準(zhǔn)則T的值；

⑤ 若T的值減小則更新(γ,C)opt；

⑥ 在P中更新(γ,C);

⑦ until 準(zhǔn)則T的值最小化；

⑧ 輸出(γ,C)opt.

記l為訓(xùn)練樣本規(guī)模，d為訓(xùn)練樣本維度，D為隨機(jī)傅里葉特征空間維度.訓(xùn)練高斯核SVM應(yīng)用高效的SMO算法實(shí)現(xiàn)[8,22]，其計(jì)算時(shí)間復(fù)雜度為O(l2).線性支持向量機(jī)求解的時(shí)間復(fù)雜度為O(lD)[12].隨機(jī)傅里葉特征映射的時(shí)間復(fù)雜度為O(lDd).

對(duì)于半徑間隔界和Span界方法，需要在模型選擇內(nèi)層的每一次迭代完整地求解核SVM.記S為模型選擇需要迭代的次數(shù).標(biāo)準(zhǔn)核SVM模型選擇時(shí)間復(fù)雜度為O(Sl2)，而算法2的時(shí)間復(fù)雜度為O(SdlD).

對(duì)于k-折交叉驗(yàn)證方法，記Sγ,SC分別表示參數(shù)γ,C格搜索的長(zhǎng)度.標(biāo)準(zhǔn)核SVM模型選擇時(shí)間復(fù)雜度為O(kSγSCl2).算法1中，隨機(jī)特征映射時(shí)間復(fù)雜度為O(SγldD)，訓(xùn)練線性SVM的時(shí)間復(fù)雜度為O(kSγSClD)，因此算法2總的時(shí)間復(fù)雜度為O((d+kSC)SγlD).

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

交叉驗(yàn)證是一種廣泛應(yīng)用且有效的模型選擇方法.以k-折交叉驗(yàn)證(k=5,10)為例，驗(yàn)證提出算法AMS-RFF的可行性及計(jì)算效率.實(shí)驗(yàn)中數(shù)據(jù)集為標(biāo)準(zhǔn)模型選擇數(shù)據(jù)集[23]，如表1所示：

Table 1　Specification of Benchmark Datasets

為了消除數(shù)據(jù)劃分帶來(lái)的影響，每一個(gè)數(shù)據(jù)集根據(jù)訓(xùn)練集與測(cè)試集大小隨機(jī)劃分100次(對(duì)于Image和Splice各進(jìn)行20次)，得到100組訓(xùn)練集和測(cè)試集.實(shí)驗(yàn)中，首先在訓(xùn)練集上進(jìn)行模型選擇得到最優(yōu)參數(shù)組合，然后利用最優(yōu)參數(shù)組合訓(xùn)練核SVM，最后在測(cè)試集上評(píng)價(jià)最優(yōu)參數(shù)下的核SVM模型.應(yīng)用統(tǒng)計(jì)分析方法評(píng)價(jià)模型選擇算法.

使用LIBSVM[22]作為高斯核SVM的SMO算法實(shí)現(xiàn)，使用LIBLINEAR[12]訓(xùn)練線性SVM.實(shí)驗(yàn)環(huán)境為Core i5個(gè)人PC機(jī)，主頻3.2 GHz，內(nèi)存4 GB，算法實(shí)現(xiàn)采用C++語(yǔ)言.

核SVMk-折交叉驗(yàn)證模型選擇過(guò)程記為k-CV，與之對(duì)應(yīng)，在模型選擇優(yōu)化框架內(nèi)層訓(xùn)練基于隨機(jī)特征的線性SVM，進(jìn)行k-折交叉驗(yàn)證過(guò)程記為Approximatek-CV(簡(jiǎn)寫(xiě)為Ak-CV),其中k=5,10.交叉驗(yàn)證在13×11大小的格搜索空間上進(jìn)行，γ∈{2-15,2-13,…,29}，C∈{2-5,2-3,…,215}.算法1中隨機(jī)特征空間維度統(tǒng)一設(shè)置為D=30.

再看模型選擇效率，對(duì)于所有13個(gè)數(shù)據(jù)集，僅僅在3個(gè)數(shù)據(jù)集上Ak-CV (k=5,10)沒(méi)有帶來(lái)效率上的提升，這3個(gè)數(shù)據(jù)集(Thyroid,Titanic,Heart)的數(shù)據(jù)量均小于200.對(duì)于數(shù)據(jù)規(guī)模較大的數(shù)據(jù)集，Ak-CV能帶來(lái)效率上10倍甚至20倍的提升.隨著數(shù)據(jù)量的增加，效率提升更加明顯.這是因?yàn)樗岢龅姆椒ㄅc標(biāo)準(zhǔn)交叉驗(yàn)證方法在小規(guī)模數(shù)據(jù)上效率差異不大，隨著數(shù)據(jù)規(guī)模的增加，所提出的方法效率提高越明顯.

在數(shù)據(jù)集Splice和Image上進(jìn)行另外一組實(shí)驗(yàn)，驗(yàn)證標(biāo)準(zhǔn)5-折交叉驗(yàn)證(5-CV)與所提出的方法(A5-CV)性能隨著訓(xùn)練樣本規(guī)模的變化情況，實(shí)驗(yàn)結(jié)果如圖1和圖2所示.隨著訓(xùn)練樣本規(guī)模的變化，2種模型選擇方法選擇的模型測(cè)試準(zhǔn)確率相差不大(如圖1所示).在模型選擇的效率上，A5-CV的時(shí)間幾乎與訓(xùn)練樣本規(guī)模呈線性關(guān)系，而5-CV的時(shí)間與樣本規(guī)模呈平方關(guān)系，這正好與第3節(jié)模型選擇時(shí)間復(fù)雜度分析結(jié)果一致.因而，所提出的方法更加適用于大規(guī)模核方法模型選擇問(wèn)題.

Table 2　Comparison of Computation Time and Test Accuracy (Acc) of Model Selection among k-CV and Approximate

Fig. 1　The test accuracy varies with respect to the number of training samples.圖1　測(cè)試準(zhǔn)確率隨著訓(xùn)練樣本數(shù)的變化情況

Fig. 2　The time of model selection varies with respect to the number of training samples.圖2　模型選擇時(shí)間隨著訓(xùn)練樣本數(shù)的變化情況

5　結(jié)束語(yǔ)

核SVM優(yōu)化問(wèn)題求解的復(fù)雜度為O(l3)，基于分解策略的高效SMO算法求解的復(fù)雜度為O(l2)，其中l(wèi)為訓(xùn)練樣本的個(gè)數(shù).模型選擇過(guò)程往往需要多次訓(xùn)練核SVM，并且精確評(píng)估每一個(gè)模型，計(jì)算代價(jià)過(guò)高.針對(duì)這一問(wèn)題，提出基于隨機(jī)傅里葉特征的高斯核模型選擇方法.通過(guò)隨機(jī)傅里葉特征映射將數(shù)據(jù)映射到顯式的隨機(jī)特征空間，訓(xùn)練具有O(l)復(fù)雜度的線性SVM，進(jìn)而可高效計(jì)算模型選擇準(zhǔn)則的近似值，大幅度提升模型選擇效率.推導(dǎo)了隨機(jī)特征空間中模型與對(duì)應(yīng)核誘導(dǎo)的特征空間中模型的誤差上界，從理論上保證了可利用隨機(jī)特征方法評(píng)價(jià)原特征空間中模型的相對(duì)優(yōu)劣.所提出的方法適用于大規(guī)模核SVM的模型選擇.

進(jìn)一步工作考慮隨機(jī)特征空間維度D的選擇問(wèn)題.

[1]Vapnik V N. Statistical Learning Theory[M]. New York: John Wiley & Sons, 1998[2]Sch?lkopf B, Smola A J. Learning with Kernels: Support Vector Machines, Regularization, Optimization,and Beyond[M]. Cambridge, MA: MIT Press, 2002[3]Chapelle O, Vapnik V. Model selection for support vector machines[C]Advances in Neural Information Processing Systems 12. Cambridge, MA: MIT Press, 2000: 230-236[4]Guyon I, Saffari A, Dror G, et al. Model selection: Beyond the Bayesianfrequentist divide[J]. Journal of Machine Learning Research, 2010, 11: 61-87[5]Duan K, Keerthi S S, Poo A N. Evaluation of simple performance measures for tuning SVM hyperparameters[J]. Neurocomputing, 2003, 51: 41-59[6]Chapelle O, Vapnik V N, Bousquet O, et al. Choosing multiple parameters for support vector machines[J]. Machine Learning, 2002, 46(123): 131-159[7]Vapnik V N, Chapelle O. Bounds on error expectation for support vector machines[J]. Neural Computation, 2000, 12(9): 2013-2036[8]Platt J C. Fast Training of support vector machines using sequential minimal optimization[C]Advances in Kernel Methods: Support Vector Learning. Cambridge, MA: MIT Press, 1999: 185-208[9]Zhang T. Solving large scale linear prediction problems using stochastic gradient descent algorithms[C]Proc of the 21st Int Conf on Machine Learning. New York: ACM, 2004: 919-926[10]Joachims T. Training linear SVMs in linear time[C]Proc of the 12th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2006: 217-226[11]Hsieh C J, Chang K W, Lin C J, et al. A dual coordinate descent method for large-scale linear SVM[C]Proc of the 25th Int Conf on Machine Learning. New York: ACM, 2008: 408-415[12]Fan R E, Chang K W, Hsieh C J, et al. LIBLINEAR: A library for large linear classification[J]. Journal of Machine Learning Research, 2008, 9: 1871-1874[13]Rahimi A, Recht B. Random features for large-scale kernel machines[C]Advances in Neural Information Processing Systems 20. Cambridge, MA: MIT Press, 2007: 1177-1184[14]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 (in Chinese)(劉勇, 江沙里, 廖士中. 基于近似高斯核顯式描述的大規(guī)模SVM求解[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(10): 2171-2177)[15]Ding L, Liao S. Approximate model selection for large scale LSSVM[C]Proc of the 3rd Asian Conf on Machine Learning. Brookline, MA: Microtome Publishing, 2011: 165-180[16]Ding L, Liao S. Nystr?m approximate model selection for LSSVM[C]Proc of the 16th Pacific Asia Conf on Knowledge Discovery and Data Mining. Berlin: Springer, 2012: 282-293[17]Ding Lizhong, Liao Shizhong. Approximate model selection on regularization path for support vector machines[J]. Journal of Computer Research and Development, 2012, 49(6): 1248-1255 (in Chinese)(丁立中, 廖士中. 基于正則化路徑的支持向量機(jī)近似模型選擇[J]. 計(jì)算機(jī)研究與發(fā)展, 2012, 49(6): 1248-1255)[18]Kimeldorf G S, Wahba G. A correspondence between Bayesian estimation on stochastic processes and smoothing by splines[J]. The Annals of Mathematical Statistics, 1970, 41(2): 495-502[19]Rudin W. Fourier Analysis on Groups[M]. New York: John Wiley & Sons, 1962[20]Chitta R, Jin R, Jain A K. Efficient kernel clustering using random Fourier features[C]Proc of the 12th IEEE Int Conf on Data Mining. Piscataway, NJ: IEEE, 2012: 161-170[21]Cortes C, Mohri M, Talwalkar A. On the impact of kernel approximation on learning accuracy[C]Proc of the 13th Int Conf on Artificial Intelligence and Statistics. Brookline, MA: Microtome Publishing, 2010: 113-120[22]Chang C C, Lin C J. LIBSVM: A library for support vector machines[J]. ACM Trans on Intelligent Systems and Technology, 2011, 2: 27:1-27:27[23]Ratsch G, Onoda T, Müller K R. Soft margins for AdaBoost[J]. Machine Learning, 2001, 42(3): 287-320[24]Cawley G C, Talbot N L. Preventing over-fitting during model selection via Bayesian regularisation of the hyper-parameters[J]. Journal of Machine Learning Research, 2007, 8: 841-861[25]Dem?ar J. Statistical comparisons of classifiers over multiple data sets[J]. Journal of Machine Learning Research, 2006, 7: 1-30

Feng Chang, born in 1989, PhD candidate. Student member of China Computer Federation. His main research interests include kernel methods, model selection and randomized computation.

Liao Shizhong, born in 1964. PhD, professor, and PhD supervisor. Member of China Computer Federation. His main research interests include artificial intelligent and theoretical computer science.

Model Selection for Gaussian Kernel Support Vector Machines in Random Fourier Feature Space

Feng Chang and Liao Shizhong

(SchoolofComputerScienceandTechnology,TianjinUniversity,Tianjin300350)

Model selection is very critical to support vector machines (SVMs). Standard SVMs typically suffer from cubic time complexity in data size since they solve the convex quadratic programming problems. However, it usually needs to train hundredsthousands of SVMs for model selection, which is prohibitively time-consuming for medium-scale datasets and very difficult to scale up to large-scale problems. In this paper, by using random Fourier features to approximate Gaussian kernel, a novel and efficient approach to model selection of kernel SVMs is proposed. Firstly, the random Fourier feature mapping is used to embed the infinite-dimensional implicit feature space into an explicit random feature space. An error bound between the accurate model obtained by training kernel SVM and the approximate one returned by the linear SVM in the random feature space is derived. Then, in the random feature space, a model selection approach to kernel SVM is presented. Under the guarantee of the model error upper bound, by applying the linear SVMs in the random feature space to approximate the corresponding kernel SVMs, the approximate model selection criterion can be efficiently calculated and used to assess the relative goodness of the corresponding kernel SVMs. Finally, comparison experiments on benchmark datasets for cross validation model selection show the proposed approach can significantly improve the efficiency of model selection for kernel SVMs while guaranteeing test accuracy.

model selection; support vector machines (SVMs); random Fourier features; Gaussian kernel; cross validation

2015-06-12；

2015-10-30

國(guó)家自然科學(xué)基金項(xiàng)目(61170019)

廖士中(szliao@tju.edu.cn)

TP181; TP301

This work was supported by the National Natural Science Foundation of China (61170019).