隨機特征上一致中心調節的支持向量機

廖士中，盧瑋

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

隨機特征上一致中心調節的支持向量機

廖士中，盧瑋

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

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

并行支持向量機；大規模數據集；有限資源；隨機傅里葉特征；一致中心調節

1 引言

支持向量機（SVM）[1]是在統計學習理論基礎上發展起來的一類重要的學習方法，是目前最為流行的數據挖掘方法。

SVM的本質是求解一個二次凸優化問題。當樣本數據規模l較大時，訓練SVM的空間復雜性為O(l2)，時間復雜性為O(l3)。在傳統PC機上已經無法求解大規模SVM學習問題，因而基于計算機集群、超級計算機并行環境下的并行SVM方法應運而生。

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

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

2 隨機傅里葉特征

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

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

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

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

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

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

按照上述構造傅里葉特征的方法，結合定理2得到以下定理。

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

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

3 一致中心調節框架

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

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

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

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

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

圖1 并行框架流程圖

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

4 并行算法：RF-CCASVM

本章給出基于傅里葉特征應用一致中心調節的詳細算法RF-CCASVM，并對算法進行理論分析。

4.1 算法描述

最常使用的核函數為高斯核，因此給出構造高斯核的傅里葉特征的詳細算法。訓練線性SVM使用簡單高效的對偶坐標下降算法[14]。給出在一致中心調節框架下的對偶坐標下降算法。

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

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

4.1.2 并行框架下的對偶坐標下降

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

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

并行一致調節SVM算法將經傅里葉映射后的數據均勻的劃分到各個進程上，根據并行框架，使用該對偶坐標下降算法求解。具體的算法描述如下：

4.2 算法分析

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

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

5 實驗與分析

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

表1 實驗用標準數據集

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

表2 算法參數設置

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

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

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

圖3 RF-CCASVM與LIBSVM預測準確率比較

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

圖4 RF-CCASVM算法加速比

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

6 結束語

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

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

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

[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

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

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

2013-08-13

2013-10-08

1002-8331（2014）17-0044-05

CNKI網絡優先出版：2013-11-25,http://www.cnki.net/kcm s/detail/11.2127.TP.20131125.1535.015.htm l