廖士中，盧瑋

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

隨機特征上一致中心調(diào)節(jié)的支持向量機

廖士中，盧瑋

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

支持向量機（SVM）是最為流行的分類工具，但處理大規(guī)模的數(shù)據(jù)集時，需要大量的內(nèi)存資源和訓(xùn)練時間，通常在大集群并行環(huán)境下才能實現(xiàn)。提出一種新的并行SVM算法，RF-CCASVM，可在有限計算資源上求解大規(guī)模SVM。通過隨機傅里葉映射，應(yīng)用低維顯示特征映射一致近似高斯核對應(yīng)的無限維隱式特征映射，從而用線性SVM一致近似高斯核SVM。提出一致中心調(diào)節(jié)的并行化方法。具體地，將數(shù)據(jù)集劃分成若干子數(shù)據(jù)集，多個進程并行地在各自的子數(shù)據(jù)集上獨立訓(xùn)練SVM。當(dāng)各個子數(shù)據(jù)集上的最優(yōu)超平面即將求出時，用由各個子集上獲得的一致中心解取代當(dāng)前解，繼續(xù)在各子集上訓(xùn)練直到一致中心解在各個子集上達到最優(yōu)。標(biāo)準(zhǔn)數(shù)據(jù)集的對比實驗驗證了RF-CCASVM的正確性和有效性。

并行支持向量機；大規(guī)模數(shù)據(jù)集；有限資源；隨機傅里葉特征；一致中心調(diào)節(jié)

1 引言

支持向量機（SVM）[1]是在統(tǒng)計學(xué)習(xí)理論基礎(chǔ)上發(fā)展起來的一類重要的學(xué)習(xí)方法，是目前最為流行的數(shù)據(jù)挖掘方法。

SVM的本質(zhì)是求解一個二次凸優(yōu)化問題。當(dāng)樣本數(shù)據(jù)規(guī)模l較大時，訓(xùn)練SVM的空間復(fù)雜性為O(l2)，時間復(fù)雜性為O(l3)。在傳統(tǒng)PC機上已經(jīng)無法求解大規(guī)模SVM學(xué)習(xí)問題，因而基于計算機集群、超級計算機并行環(huán)境下的并行SVM方法應(yīng)運而生。

現(xiàn)有并行SVM可分為兩類。一類是對已有的串行SVM算法進行并行化。包括對SMO算法的并行化實現(xiàn)[2-3]，對內(nèi)點法的并行化實現(xiàn)[4]以及對梯度下降算法的并行化[5]。對已有的流行SVM串行算法進行并行化，雖然能緩解串行算法對內(nèi)存的極大需求以及極長的訓(xùn)練時間，但同時也增加了大量通信和同步開銷。另一類是設(shè)計新的算法，使其算法框架易于并行。Collobert等提出在各個子集上并行訓(xùn)練出多個SVM，再通過神經(jīng)網(wǎng)絡(luò)求出最終的SVM[6]。Graf等提出級聯(lián)SVM的思想[7]。在樹狀結(jié)構(gòu)中，將下層SVM的支持向量組合作為新的支持向量訓(xùn)練SVM。這兩種并行方法減少了訓(xùn)練過程中頻繁的數(shù)據(jù)通信。進程間的通信僅發(fā)生在各個SVM之間，但是這些方法需要訓(xùn)練多個SVM。Hazan等提出一種適于分布式并行的SVM算法[8]。使用一個全局校正量對各個子集上迭代求出的解進行校正，使其接近全局解。Forero等采用ADMM框架獲得全局校正量[9]?；谌中Ｕ枷氲牟⑿蠸VM在整個算法中只需求解一次SVM。在解優(yōu)化問題的過程中，每輪迭代之后，各個進程間進行通信，獲得全局校正量。

這些并行SVM方法都依賴于大型的計算平臺，通過擴大集群規(guī)模，增加計算資源來緩解計算復(fù)雜性，并未從根本上解決處理大規(guī)模問題面臨的瓶頸。本文提出資源有限的大規(guī)模SVM求解的并行方法。首先，應(yīng)用隨機傅里葉特征[10-12]一致近似核函數(shù)。核矩陣的計算是訓(xùn)練核SVM的主要開銷。隨機傅里葉映射能根據(jù)核函數(shù)確定出顯示特征映射，從而將只能核化處理的非線性問題轉(zhuǎn)化為映射后特征空間上的線性問題。這一方法可根據(jù)現(xiàn)有資源來確定隨機采樣規(guī)模，避免求解并存儲核矩陣，從而合理地降低了計算復(fù)雜性和對計算資源的需求。然后，提出一致中心調(diào)節(jié)的策略來設(shè)計高效的并行算法，進一步縮短訓(xùn)練時間?；谌中Ｕ牟⑿蠸VM思想[9]，但考慮到在求解優(yōu)化算法的早期，每次優(yōu)化求出的臨時解具有很強的隨機性，此時進行校正沒有意義，因而在每個子集上解優(yōu)化問題的迭代早期，不進行全局校正。只有當(dāng)子數(shù)據(jù)集上的臨時解趨于最優(yōu)解時，才應(yīng)用一致中心量對子集上的迭代解進行校正，各個進程間才進行通信。該并行化設(shè)計相比在全過程中采用一致量進行校正的方法，減少了數(shù)據(jù)通信量，降低了進程間的通信開銷。在各個子集上求解優(yōu)化問題可采用通用的SVM求解器。通過傅里葉特征映射將核SVM轉(zhuǎn)化為線性SVM，再應(yīng)用并行一致中心調(diào)節(jié)的策略訓(xùn)練線性SVM，可使過去只能在超級計算機或計算集群上處理的任務(wù)，也能在計算資源有限的環(huán)境下快速地訓(xùn)練并保持原有的預(yù)測能力。在標(biāo)準(zhǔn)數(shù)據(jù)集上進行對比實驗充分表明，該算法在大規(guī)模的數(shù)據(jù)集上取得非常好的實驗結(jié)果。

2 隨機傅里葉特征

首先介紹機傅里葉特征的相關(guān)知識。隨機傅里葉特征的概念是由Rahim i等[10]首先提出的。其理論基礎(chǔ)來源于調(diào)和分析中的博赫納定理。

定理1（博赫納定理[13]）Rd上的連續(xù)函數(shù)F(x)是正定的當(dāng)且僅當(dāng)F(x)為某一有限非負(fù)Borel測度μ的傅里葉變換，F(xiàn)(x)=∫Rde-ix'tdμ(t)。

對任一正定平移不變核函數(shù)k(x，y)=κ(x-y)，都有k(x，y)=∫Rdp(γ)e-iγ'(x-y)dγ，其中，p(γ)為γ的概率密度函數(shù)。

令ζγ(x)=e-iγ'x，則k(x，y)=E[ζγ(x)ζγ(y)*]，*表示共軛。ζγ(x)ζγ(y)*為k(x，y)的無偏估計。當(dāng)k(x，y)和 p(γ)均為實數(shù)時，用ψγ(x)=[cos(γ'x+2πθ)]代替ζγ(x)， γ服從密度函數(shù)為p(γ)的分布，θ服從[0，1]分布。為減小樣本方差，采用蒙特卡羅方法隨機采樣得到E[ζγ(x)ζγ(y)*]。對γ和θ采樣D次，構(gòu)造映射Ψ:x→則有k(x，y)≈Ψγ(x)'Ψγ(y)。

對于有界的隨機變量，存在Hoffeding不等式：

定理2（Hoffeding不等式）設(shè)相互獨立的隨機變量ξ1，ξ2，…，ξN，滿足ξi∈[a，b]，i=1，2，…，N，記=1/則對任意ε＞0，有：

按照上述構(gòu)造傅里葉特征的方法，結(jié)合定理2得到以下定理。

定理3[10]在一給定的數(shù)據(jù)集S={(x1，y1)，(x2，y2)，…，(xl，yl)}，有：

該定理保證了在給定數(shù)據(jù)集上，用隨機特征近似核函數(shù)的誤差界。

3 一致中心調(diào)節(jié)框架

給定訓(xùn)練數(shù)據(jù)集S={(x1，y1)，(x2，y2)，…，(xl，yl)}，xi∈Rd為輸入向量，yi=±1對應(yīng)兩類輸出。SVM求解優(yōu)化問題：

其中，ξ(w;xi，yi)為損失函數(shù)，C＞0為懲罰項系數(shù)。對于L1-SVM，ξ(w;xi，yi)=max(1-yiw'φ(xi)，0)；對于L2-SVM，ξ(w;xi，yi)=max(1-yiw'φ(xi)，0)2。將訓(xùn)練實例{1，2，…，l}劃分為m塊{B1，B2，…，Bm}，式（3）可寫為：

將式（4）分解成m個子問題，在每個子數(shù)據(jù)塊上求解以下問題：

在各個子數(shù)據(jù)塊上訓(xùn)練得到的w不能保證一致。通過對各個子數(shù)據(jù)塊上的w進行校正，讓各個子數(shù)據(jù)塊上的w最終收斂到相同的值，獲得在整個數(shù)據(jù)集上的解w。對各個子數(shù)據(jù)塊上訓(xùn)練過程中的得到的w按照如下方法進行校正：各個處理器并行的在子數(shù)據(jù)集上采用標(biāo)準(zhǔn)SVM求解器求解w，在求解原優(yōu)化問題或?qū)ε純?yōu)化問題的過程中生成序列{wk}或{αk}。當(dāng)各個處理器上分別求出的wk或αk均滿足松弛的最優(yōu)性條件時，主處理器收集各個處理器上得到的w或α，并將其平均值作為對各個子數(shù)據(jù)集上訓(xùn)練出的w或α進行校正，發(fā)送給各個子數(shù)據(jù)集上，作為下一輪迭代的輸入，各進程在子數(shù)據(jù)集上繼續(xù)求優(yōu)化解。重復(fù)以上過程，直到所有進程上的優(yōu)化問題求解完畢。此時，各個進程上的w均收斂到相同的值。

并行算法框架設(shè)計如下：將數(shù)據(jù)集分割成m塊，分別存儲到m個進程中。m個進程并行的的在子數(shù)據(jù)上訓(xùn)練SVM。子進程算法的基本流程圖如圖1所示。

圖1 并行框架流程圖

該并行過程相比于其他的并行SVM算法，極大地減少了數(shù)據(jù)通信和同步操作。在訓(xùn)練過程的早期，各個進程間不需要通信。直到在各個子進程上求出的解接近最優(yōu)解時，進程間才開始通信。

4 并行算法：RF-CCASVM

本章給出基于傅里葉特征應(yīng)用一致中心調(diào)節(jié)的詳細算法RF-CCASVM，并對算法進行理論分析。

4.1 算法描述

最常使用的核函數(shù)為高斯核，因此給出構(gòu)造高斯核的傅里葉特征的詳細算法。訓(xùn)練線性SVM使用簡單高效的對偶坐標(biāo)下降算法[14]。給出在一致中心調(diào)節(jié)框架下的對偶坐標(biāo)下降算法。

4.1.1 高斯核的隨機傅里葉特征

對于高斯核k(x，y)=exp(-‖x-y‖2/2σ2)，根據(jù)傅里葉逆變換求得對應(yīng)的分布函數(shù)為N(0，Id/σ2)。求高斯核的隨機傅里葉特征的算法描述如下：

4.1.2 并行框架下的對偶坐標(biāo)下降

對偶坐標(biāo)下降算法求解SVM的對偶問題。問題（3）的對偶問題為：

當(dāng)PGi(α)=0，α在第i維上的值已是最優(yōu)，不需要更新。否則按以下規(guī)則更新αi：

并行一致調(diào)節(jié)SVM算法將經(jīng)傅里葉映射后的數(shù)據(jù)均勻的劃分到各個進程上，根據(jù)并行框架，使用該對偶坐標(biāo)下降算法求解。具體的算法描述如下：

4.2 算法分析

度量并行算法性能的兩個常用指標(biāo)為：加速比和并行效率。

理想情況下，加速比應(yīng)為m，并行效率達到1。但由于并行算法中存在通信開銷，加速比＜m，并行效率＜1。

5 實驗與分析

實驗在配置為2.3 GHz（雙核）CPU，4 GB內(nèi)存的PC機上完成。MPI并行環(huán)境使用MPICH。首先在數(shù)據(jù)集Web，IJCNN和CovType上進行實驗，比較RF-CCASVM與LIBSVM的運行性能。CovType為多分類數(shù)據(jù)集，僅考慮將第2類其他類相區(qū)分的2分類問題。CovType數(shù)據(jù)集沒有測試數(shù)據(jù)。將CovType數(shù)據(jù)集的9/10作為訓(xùn)練集，余下的1/10作為測試集。數(shù)據(jù)集信息見表1。

表1 實驗用標(biāo)準(zhǔn)數(shù)據(jù)集

LIBSVM采用高斯核。兩個算法的最優(yōu)參數(shù)(C，g)均通過5折交叉驗證得到。使用選出的最優(yōu)(C，g)訓(xùn)練SVM。算法的參數(shù)設(shè)置見表2。NA表示LIBSVM在CovType數(shù)據(jù)集上無法運行。

表2 算法參數(shù)設(shè)置

首先比較RF-CCASVM與LIBSVM的運行時間。實驗結(jié)果如圖2所示。RF-CCASVM算法極大地縮短了在數(shù)據(jù)集上的訓(xùn)練時間。數(shù)據(jù)集越大，該算法的高效性越明顯。在CovType數(shù)據(jù)集上，LIBSVM在PC機上無法實驗，在有限的內(nèi)存上，RF-CCASVM仍可快速地進行訓(xùn)練。

圖2 RF-CCASVM與LIBSVM運行時間比較

接下來比較RF-CCASVM與LIBSVM在標(biāo)準(zhǔn)數(shù)據(jù)集上的預(yù)測精度。實驗結(jié)果如圖3所示。RF-CCASVM為近似算法，有一致近似界的保證。算法的預(yù)測結(jié)果非常接近LIBSVM的精確解。盡管該算法是近似求解，但仍有非常高的預(yù)測準(zhǔn)確率。

圖3 RF-CCASVM與LIBSVM預(yù)測準(zhǔn)確率比較

另外還進行RF-CCASVM算法的可擴展性實驗。使用不同的進程數(shù)進行實驗，統(tǒng)計訓(xùn)練時間，計算加速比。實驗結(jié)果如圖4所示。線性訓(xùn)練過程非常快，因而通信和同步代價對并行算法的執(zhí)行時間有較大影響。在該并行算法中，進程間通信D維向量。因此，高維的傅里葉特征會增加通信開銷。該算法在數(shù)據(jù)集上較小時會有一定的不穩(wěn)定性。在較小的數(shù)據(jù)集上，加速比會出現(xiàn)異常。

圖4 RF-CCASVM算法加速比

最后，還將RF-CCASVM算法與目前已有的其他并行算法進行比較。實驗對比P-packSVM[5]，PSVM[4]，PSSVM[15]算法在Adult和Web數(shù)據(jù)集上的預(yù)測準(zhǔn)確率。這三種并行算法均是在計算機集群或大型服務(wù)器上完成的，實驗結(jié)果由算法的作者在文章中提供。RF-CCASVM在兩個數(shù)據(jù)集上的實驗結(jié)果分別是在采樣特征D=3 000和D=200時得到的。實驗結(jié)果表明，RF-CCASVM算法能在有限資源上解決大規(guī)模的學(xué)習(xí)問題，并能獲得與運行在大集群并行環(huán)境下的并行學(xué)習(xí)算法相當(dāng)?shù)念A(yù)測能力。

6 結(jié)束語

圖5 RF-CCASVM與其他并行算法預(yù)測能力比較

提出了一種資源有限的大規(guī)模并行SVM算法。應(yīng)用隨機傅里葉特征來一致近似核函數(shù)，進而在隨機傅里葉特征空間上訓(xùn)練線性SVM。該并行算法的時間復(fù)雜性為O(lD lb(1/?)/m)。理論分析與實驗結(jié)果表明，該并行算法可在有限的計算資源條件下，高效求解大規(guī)模SVM，并保證較高的預(yù)測精度，是正確的、有效的。

進一步工作將研究隨機特征采樣維度D的選取方法，給出理論界、計算開銷和可保證的預(yù)測精度。

[1]Vapnik V.The nature of statistical learning theory[M].New York：Springer-Verlag，2000.

[2]Cao L J，Keerthi S S，Ong C J，et al.Developing parallel sequential minimal optimization for fast training support vector machine[J].Neurocomputing，2006，70（1）：93-104.

[3]Zanghirati G，Zanni L.A parallel solver for large quadratic programs in training support vector machines[J].Parallel Computing，2003，29（4）：535-551.

[4]Chang E Y，Zhu Kaihua，Wang Hao，et al.Parallelizing support vector machines on distributed computers[C]//Advances in Neural Information Processing Systems.Cambridge：MIT Press，2008：257-264.

[5]Zhu Z A，Chen Weizhu，Wang Gang，et al.P-packsvm：parallel primal gradient descent kernel SVM[C]//Proceedings of the 9th IEEE International Conference on Data Mining.Piscataway：IEEE Press，2009：677-686.

[6]Collobert R，Bengio S，Bengio Y.A parallel mixture of SVMs for very large scale problems[J].Neural Computation，2002，14（5）：1105-1114.

[7]Graf H P，Cosatto E，Bottou L，et al.Parallel support vector machines：the cascade SVM[C]//Advances in Neural Information Processing Systems.Cambridge：MIT Press，2005：521-528.

[8]Hazan T，Man A，Shashua A.A parallel decomposition solver for SVM：distributed dual ascend using fenchel duality[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Piscataway：IEEE Press，2008：1-8.

[9]Forero P A，Cano A，Giannakis G B.Consensus-based distributed support vector machines[J].Journal of Machine Learning Research，2010，11：1663-1707. [10]Rahimi A，Recht B.Random features for large-scale kernel machines[C]//Advances in Neural Information Processing Systems.Cambridge：MIT Press，2008：1177-1184.

[11]Bǎzǎ E G，Li Fuxin，Sminchisescu C.Fourier kernel learning[C]//Proceedings of the 12th European Conference on Computer Vision.Berlin：Springer，2012：459-473.

[12]Li Fuxin，Ionescu C，Sminchisescu C.Random Fourier approximations for skewed multiplicative histogram kernels[C]//Proceedings of the 32nd DAGM Conference on Pattern Recognition.New York：Springer-Verlag，2010：262-271.

[13]Rudin W.Fourier analysis on groups[M].New York：JohnWiley & Sons，1990.

[14]Hsieh Cho-Jui，Chang Kai-Wei，Lin Chih-Jen，et al.A dual coordinate descent method for large-scale linear SVM[C]//Proceedings of the 25th International Conference on Machine Learning.New York：ACM，2008：408-415.

[15]Roberto D M，Harold Y M B，ángel N V.Parallel semiparametric support vector machines[C]//Proceedings of the 2011 International Joint Conference on Neural Networks. Piscataway：IEEE Press，2011：475-481.

LIAO Shizhong, LU Wei

School of Computer Science and Technology, Tianjin University, Tianjin 300072, China

Support Vector Machines（SVMs）have become popular classification tools, but when dealing with very large datasets, SVMs need large memory requirement and computation time. Therefore, large-scale SVMs are performed on computer clusters or supercomputers. A novel parallel algorithm for large-scale SVM is presented. The algorithm is performed on a resource-limited computing environment and guarantees a uniform convergence. The infinite-dimensional implicit feature mapping of the Gaussian kernel function is sufficiently approximated by a low-dimensional feature mapping. The kernel SVM is approximated with a linear SVM by explicitly mapping data to low-dimensional features using random the Fourier map. The parallelization of the algorithm is implemented with a consensus centre adjustment strategy.Concretely, the dataset is partitioned into several subsets, and separate SVMs are trained on processors parallel with the subsets. When the optimal hyperplanes on subsets are nearly found, solutions achieved by separate SVMs are replaced by the consensus centre and are retrained on the subsets until the consensus centre is optimal on all subsets. Comparative experiments on benchmark databases are performed. The results show that the proposed resource-limited parallel algorithm is effective and efficient.

parallel Support Vector Machines（SVM）; large-scale datasets; limited resource; random Fourier features;consensus centre adjustment

LIAO Shizhong, LU Wei. Support vector machine via consensus centre adjustment on random features. Computer Engineering and Applications, 2014, 50（17）：44-48.

A

TP181

10.3778/j.issn.1002-8331.1308-0145

國家自然科學(xué)基金（No.61170019）；天津市自然科學(xué)基金（No.11JCYBJC00700）。

廖士中（1964—），男，博士，教授，研究領(lǐng)域為人工智能應(yīng)用基礎(chǔ)、理論計算機科學(xué)；盧瑋（1989—），女，在讀碩士研究生，研究方向為核方法、并行算法。E-mail：szliao@tju.edu.cn

2013-08-13

2013-10-08

1002-8331（2014）17-0044-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-11-25,http://www.cnki.net/kcm s/detail/11.2127.TP.20131125.1535.015.htm l