支持向量機(SVM)是否適合大規模數據？

01-14

之前學習支持向量機的時候老師就說支持向量機不適用於大規模數據，然後在一篇統計人寫的論文中看到說支持向量機經常被用到massive dataset上。我就糊塗了。
1 支持向量機到底適不適合大量數據？
2 這個大量數據是如何衡量的？拋開機器學習和統計學兩個研究方向對「大量」不同的定義來看。

這個問題其實有兩個層面，一個層面是，svm在分類效果上是否適合大規模數據；另外一個層面是，svm對於大規模數據訓練的運算量是否太大而無法使用。對於第二個層面，我覺得陳義的回答已經很精彩了。

我說一下我對第一個層面的理解。我理解SVM並不是不適合大規模數據，而應該說，SVM在小樣本訓練集上能夠得到比其它演算法好很多的結果。支持向量機之所以成為目前最常用，效果最好的分類器之一，在於其優秀的泛化能力，這是是因為其本身的優化目標是結構化風險最小，而不是經驗風險最小，因此，通過margin的概念，得到對數據分布的結構化描述，因此減低了對數據規模和數據分布的要求。而大規模數據上，並沒有實驗和理論證明表明svm會差於其它分類器，也許只是相對其它分類器而言，領先的幅度沒有那麼高而已。

關於什麼是大規模機器學習，可以參考[1, 2, 3]的討論。顯然，大小是個相對的概念，在機器學習的語境下也不例外，什麼是大規模，這很大程度上取決於你所面對的應用以及可用的計算資源。在互聯網應用成為機器學習主要應用領域之一的今天，能不能處理Google或者淘寶這樣重量級的網站所生成的數據，成為互聯網從業人員心目中大規模的標尺。

從技術角度看，統計學習演算法所能處理的數據規模有幾個分水嶺：

1）演算法是否依賴於對訓練集的隨機訪問。依賴於訓練集隨機訪問的演算法需要將訓練集全部載入進內存，所能處理的數據量受內存大小的限制。

2）演算法是否能有效地利用分散式（或並行的）計算資源。單台計算機（或單處理器）的處理能力畢竟是有限的。如果可用的計算資源增長100倍，演算法能處理的數據量的增長遠小於100倍，則演算法的適用範圍也會有很大的限制。

以上主要是圍繞訓練集的規模在討論，實際上還會有更多需要考慮的問題，比如數據的維數、分類類別的數目、檢測時的效率等等問題，可以參考[2]及其中提到的相關文獻。如[3]中所說，（傳統的？）統計學習的核心問題是樣本不足時如何得到泛化能力很強的模型，但對於大規模學習來說，障礙往往在於演算法的計算能力不足，不是數據不夠，所以也可以說傳統的統計學習方法都不適合大規模數據處理(不只是SVM)。

因為互聯網應用的推動，最近幾年這個領域新結果非常多。總體來說，對於基於支持向量機的大規模線性分類問題，目前已經能比較好地解決。[4]對現有結果做了比較好的總結，[2]則對需要進一步解決的問題有很好的概述。

對於非線性分類問題，基於Dual Decomposition（或者SMO）方法的SVM-Light和LibSVM目前仍被廣泛使用，他們最壞情況下複雜度是O(訓練樣本數的平方)，並不適合在大規模數據集上做訓練。Pegasos[5]的複雜度同訓練樣本數呈線性關係，但實驗中效率並不高於SMO方法。盛佳提到的PSVM[6]利用分散式計算資源降低訓練耗時。不過在我接觸過的應用場景里（比如對象檢測），非線性SVM的最大問題不是訓練時代價問題，而是檢測時代價太高，在實際應用中基本上已經退出競爭。當然，相關的研究並沒有終止——畢竟不同的應用場景會有不同的需求。

對於未來的發展，還是多看看[2]吧。

[1] http://hunch.net/?p=330

[2] http://hunch.net/?p=1729

[3] http://yann.lecun.com/exdb/publis/pdf/bottou-lecun-04b.pdf

[4] http://cseweb.ucsd.edu/~akmenon/ResearchExam.pdf

[5] http://portal.acm.org/citation.cfm?id=1273598

[6] http://code.google.com/p/psvm/

SVM本質上是非線性方法，那麼就決定了：

(1)在樣本量比較少的時候，容易抓住數據和特徵之間的非線性關係（相比線性分類方法如logistic regression，或者linear SVM）。但是，在樣本量比較多的時候，線性分類方法的劣勢就要小了很多，例如可以通過手工拆分/離散化特徵來模擬非線性關係。這時SVM優勢就不明顯了。而且有個經驗就是，在數據量大的時候，一些看起來很粗暴無腦的方法反而有「令人驚奇的好效果」。

(2)計算複雜度高。主流的演算法是O(n^2)的，這樣對大規模數據就顯得很無力了。不僅如此，由於其存在兩個對結果影響相當大的超參數（如果用RBF核，是核函數的參數gamma以及懲罰項C），這兩個超參數無法通過概率方法進行計算，只能通過窮舉試驗來求出，計算時間要遠高於不少類似的非線性分類器。雖然說也還可以優化，但是與其優化它，不如去優化一些理論更魯棒的方法（比如GP classification），或者直接就用計算時間較低的暴力非線性方法（如random forest，這是O(nlogn)的方法）

不知道為何大多數答案都說SVM不適合大數據。

線性的SVM的就是把Linear Regression的L2 loss換成 Hinge Loss，直接用SGD就可以優化。

推薦 Pegasos: Primal Estimated sub-GrAdient SOlver for SVM 這篇經典論文。

另外LIBLINEAR用的Dual Coordinate Decent的solver，也是linear的complexity。

對於Kernel SVM，可以關注一下 ICML14 http://www.cs.utexas.edu/~cjhsieh/dcsvm_icml_final.pdf 以及Cho-Jui Hsieh的一些其他工作。

PEGASOS啊，分散式的SVM訓練方法，很早就有人提出了，《機器學習實戰》這種入門級的書都提到過

先上結論：不帶核函數的支持向量機（線性）在一定條件下是適合大量數據的，但是帶核函數的支持向量機（非線性）在處理大量數據的時候會非常慢，並不適合。

【註：以下資料來自Coursera上的Machine Learning from Stanford】

----------------------------------------搬運分割線-------------------------------------

一頁ppt截圖：

中文：

n 為特徵數，m 為訓練樣本數。

如果相較於 m 而言，n 要大許多，即訓練集數據量不夠支持我們訓練一個複雜的非線性模型（會導致high variance），我們選用邏輯回歸模型或者不帶核函數的支持向量機。

如果 n 較小，而且 m 大小中等，例如 n 在 1-1000 之間，而 m 在 10-10000 之間，使用高斯核函數的支持向量機。（效果拔群，遠勝邏輯回歸模型或者不帶核函數的支持向量機）

如果 n 較小，而 m 較大，例如 n 在 1-1000 之間，而 m 大於 50000，則使用支持向量機會非常慢，解決方案是創造、增加更多的特徵（否則會導致high bias），然後使用邏輯回歸或不帶核函數的支持向量機。

============================================

【ps】本學渣剛剛在跟學machine learning，有什麼說的不對的地方歡迎各位大神指正

liblinear可以

以前讀文獻，確實有一些提到不適合做大規模處理，有下面幾點原因：

1是在做核卷積的時候，剛開始是每個樣本兩兩做卷積，這樣就要計算n*n次，有一些文章在這裡會提到做緩存（cache）處理，是怕重複計算問題，但是明顯看到，假如樣本是10000，那麼10000*10000的矩陣大概需要400多M的空間（如果我沒算錯的話），如果是10w呢，乘以100倍，那計算機抗的住嗎，而10w對於現在動不動上億的數據確實有點小了。

2是搜索，按照platt中smo的說法是要每次搜索一對alpha，第一個是違背kkt條件最大的alpha，第二個是與第一個距離最大的alpha，計算複雜度也是O（n）最少。

但是反觀上面兩個過程，第一步對不同樣本對做核距離計算，顯然可以分開存放在不同機器，而對於第二點，啟發式搜索，有沒有必要找到更新步長最大的那一對是關鍵，但是細想無論怎麼更新，我們始終是要其滿足kkt，最大步長也是為了更快達到，那我們何不犧牲多迭代幾次而換來大規模並行呢。所以綜上，把svm做分散式並行是行得通的，所以大規模計算也是可以的。

看情況，這個的確是要結合實際業務

SVM對小樣本的尋優能力是非常好的，無可置疑

理論上可以，我覺得這種問題應該更確切的問SVM的某個實現對大量數據的支持如何，這樣可能結果更靠譜些。我在LIBSVM上測試過MNIST的分類問題，6萬的數據已經吭哧吭哧了，目前測試額matlab和python的實現，不知道在C++下速度如何

按照我的理解，SVM工作內容是去找超平面

在你的數據分布還不夠的時候，增加數據當然能夠增加模型的準確率，能夠有效調整分類面的長相，但是當你的數據分布覆蓋面足夠的時候，你的特徵向量已經基本選定，你繼續增加訓練數據，正常的數據是不會對分類面產生任何影響的，因為它們並不是特徵向量，而一些雜訊數據則會對分類面產生不好的影響，它們可能會在分類面附近甚至被當做特徵向量，導致特徵向量過多，超平面過擬合，這種不管在計算速度上還是在準確率上都會產生不太好的影響

看了一下給位的回答，還是不太明白，就去做了一下實驗，嘗試了包括SVM在內的5個模型，全部用的是默認參數。發現SVM的時間代價相比之下非常高，不能理解為啥。如下圖

綠色的是svm.SVC() ,藍色的gradient boosting 橫軸的用來訓練模型的訓練集大小，1%，10%，100%

Spark MLLib 實現了給予Hinge loss 的線性SVM，目前Spark2.0 還沒有支持核函數。

Google搞過一個parallel SVM，基本上做到了線性

傳統的支持向量機當然不適合大數據，由於其中需要涉及到不斷迭代調參。但是可以將其改進，比如做成分散式的

訓練數據太大時，如何調參是大問題。

單機的SVM不太適合但是可以用GPU 或者其他並行框架來加速

互聯網上的大規模數據噪音比較多，從而導致可能支持向量也會比較多，求得的分界面受到噪音影響也比較大。

當然適合。只要找到支撐向量就行，而且通常是稀疏的。

偷懶一點可以用knn。

因為原理差不多，所以效果也差不多。

數據量太大不大適合！數據偏移太大，分布不易正確顯示和估計數據走勢