SVM 處理大規模數據有什麼好處？

11-24

SVM處理大規模數據是一個很熱的研究話題。如果我們分類效果不好，加入海量訓練樣本，能有顯著提升么？會不會加入海量訓練樣本只能有少量提升？還是應該用更多的精力提取更多有用特徵

感謝王清翔邀請來回答這個問題，另外也很抱歉，早就答應來討論，過了一個月才來。

其實相關的問題在Quora上早就有比較詳盡的討論了[1]。下面主要針對問題中不同的部分談一點看法：

1）在實際的工程項目中，分類演算法相對變化較少，可以採用一些相對穩定和成熟的工具包，而特徵提取則和應用領域緊密相關，變化較多，需要利用領域知識進行設計。這種情況下，模型的性能更大程度上依賴於特徵提取而不是分類演算法設計，把更多的精力投入到特徵提取上是一種常態。

2）並不是說我們擁有大量可用樣本，就需要大規模的分類演算法，如果面對的分類問題本質上並不需要大量樣本，可以對可用樣本集進行抽樣。之所以需要大規模分類演算法，是因為有些問題本質上就需要有大量樣本才能解決。設想特徵空間里幾乎所有的區域都是負類的區域，只有n個無規則地分布的正類區域，則解決該問題至少需要n個正樣本，直觀地說，每少一個正樣本，性能就會下降1/n。如果n很大，就必須使用大規模的分類演算法。

當然，一個分類問題所需的樣本數並不是和特徵提取方法無關的。使用特徵A，也許特徵空間里有n個正類區域，但使用特徵B，可能特徵空間里正類區域就變成了m個。所以好的特徵提取方法的確也至關重要，但不能因此認為分類方法無關緊要。最理想狀態下，可以設計一種一維特徵，使得正類負類分別佔據坐標軸的正半段和負半段，這樣就完全不用分類演算法了。可惜這只是一種理想，並不總能成為現實。

3）如果只考慮普通的二分分類問題，大規模分類演算法的必要性也許並不明顯，目前推動這一領域研究的最主要的是一些更複雜的應用。比如垃圾郵件過濾，雖然是個二分分類問題，但考慮到不同的人對同一郵件是不是垃圾的判斷標準不同，需要解決個性化的問題。Yahoo!或Google這樣的郵件服務提供者，理論上需要訓練幾億個關聯的二分分類器，所需的樣本量自然巨大。與此相關的問題是個性化搜索，理論上也要為每個用戶訓練一個ranker。

另外，對於搜索引擎的上下文廣告，給定一個查詢以及其他一些上下文信息，需要決定展示什麼廣告給用戶。如果過濾掉一些枝節部分，不妨把這個問題看成一個多類分類問題(或者多標記的分類問題)，每個廣告就是一個類，特徵則要從查詢及其上下文中去提取。像Google這樣的服務商所考慮的廣告數目應該在百萬這個數量級上，而且每天廣告種類都會變化，對樣本數量的要求當然會非常大。與此相關的問題是對象標註，例如為flickr上的照片或者電子商務網站上的商品自動打上tag。

[1] http://www.quora.com/Why-the-current-obsession-with-big-data

關於訓練樣本數目、特徵和分類效果，往往有tradeoff的意味。對不同的實際問題，不能簡單地採用同一策略。

戰略上：
1. 訓練樣本增加當然「有可能」提升分類效果，更具區分性的特徵「更可能」提升分類效果。
2. 增加訓練樣本的數量（且不說樣本的分布選擇之類）更多的是一個勞動力問題（當然，如答案里知友提到的，當數據量需要構造並行方法時，這在技術層面也需要相應提升），但是構造更具區分性的特徵是一個創造力問題。手頭的資源很重要。另外，特徵的構造也和對樣本集的分析和把握有一定關係，所以，構造特徵離不開一定數量的樣本的吧。
3. 分散式很偉大啊。

戰術上：
1. 海量樣本，但提升有限，那也是很有可能的，關鍵是投入產出能否被接受。
2. 對於一個實際問題，到底是增加樣本還是構造特徵，更多可能是齊頭並進，真的不好定論，往往取決於實際問題的需要和資源的限制。
3. 寫paper，還是做proj，差別真的很大耶。

我感覺，數據集和對應演算法的選擇要綜合多個因素看。

首先：數據集內在的特徵。每個數據集就像一個鮮活的生命，有其內在的DNA，反映了某種本質上的規律和真相。當我們將一個數據集分成訓練集和測試集，用訓練集訓練模型，然後用測試集進行測試和評估是。其背後的邏輯，則是認為部分的數據集也具備整體的特徵，因此可用於訓練模型。如果我們承認數據集內在的特徵。那麼就會存在某個演算法和模型，相對能更好地描述這個特徵，或者反映深層的規律和真相。所以，觀察和探索數據集，找到合適的演算法，這是首要的。樣本的大小也要考慮，但是第二位的。對於一個分類問題的數據集，當用Logistic回歸、貝葉斯分類或SVM等方法來嘗試時，會發現不同的方法處於不同的準確度區間。合適的演算法，已經決定了大致的準確度。這好比是統計學上的系統誤差。剩下的，就是對演算法進行具備調優，進一步提高精度了。

第二：樣本大小。不同的演算法對樣本的需求是不同的。基於統計(或者基於內存)的學習演算法，相對需要的樣本會比較多，因為只有大樣本才能形成統計意義的規律。而基於模型的演算法，需要的樣本相對就少。SVM需要的樣本比較少，因為它的關鍵是找到支持向量，支持向量之外的遠端的樣本點，其價值並不大。如果一個很小的樣本但是能很好地從中提取支持向量，演算法就運行地很棒。相反，貝葉斯分類則需要比較大的樣本。從理論來看，Logistic回歸對樣本大小的需求介於前二者之間。結合前面講的第一點，如果我們認為一個數據集適合某種模型，但樣本卻不夠，那就要調整演算法，或設法收集更大樣本（不過在大數據時代，樣本似乎不是問題）。

第三：演算法的性能。這包括演算法的時間複雜度和空間複雜度，以及模型訓練出來後對新樣本進行預測的響應時間，還有演算法並行化的可能性。

第四：模型的增量學習。如果有新樣本的加入，模型可以增量地學習，將新的經驗加入，還是必須重新計算？如果發現原先的樣本有錯誤（超出雜訊的錯誤），模型是要重新計算，還是能快速地修正？這方面，基於內存或統計的方法，會有優勢。

還是沒人回答……拋磚引玉，請各位大牛批判

我覺得大多數分類效果不好是小樣本特徵提的有問題，沒提到有意義特徵，而不是數據量少。所以我對這麼多大公司都在做分散式SVM不太理解。

不過，對於商業應用而言，0.1%的提升可能都是非常有意義的，也對應很多白花花的銀子：）所以可能即使不是非常大的提升，有一定提升，也是值得做的

關於這個問題，各位老大都回答得很好了。
我補充幾點，第一，需要的樣本數目和特徵緯度是相關的(具體可以參考VC維),如果特徵緯度較高的情況下,增加樣本數目,一般是能夠提高演算法性能的。但是注意,樣本除了數目,還包含一個更加重要的內容,就是標定數據的質量,也就是說樣本是否包含雜訊以及一些標定錯誤的樣本,錯誤樣本增加,帶來的一定是分類器性能的下降.
第二,在實際中,還有一個十分重要的考慮因素就是性價比,因為增加樣本數目表示需要增加很多人工標定工作量;
第三,要重視特徵提取的重要性,特徵提取如果做得不夠,無論如何提高樣本數量,也無濟於事,如果特徵提取已經做得不錯,提高樣本數量和質量是一個比較明確能提高性能的方式;

SVM演算法算是統計學習里比較年青的一個演算法了，上世紀90年代才開始研究，但是它的數學理論是基於結構風險最小化來做的，因此從理論上要強於傳統的經驗風險最小化的統計學習演算法。而且目前可以證明SVM演算法在處理文本分類的時候是最優的（文本分類可以算是大規模數據了吧，起碼特徵上跟結構化數據比是海量的）。只是它的運算複雜度太高，特別是多分類問題，由於SVM是線性分類器，所以要為每個類別分別去生成一個分類模型。個人觀點：SVM更適合在做實時性要求不高的統計分析時去使用，而不適合去做線上系統，比如跟搜索引擎的爬蟲對接。當然現在很多公司都在做SVM的分散式處理。從另外一方面看，即使在優秀的演算法，也需要好的標註數據來完成訓練，盡量讓訓練數據去模擬真實的數據分布，防止分類器的過度擬合。有時我們與其絞盡腦汁去改進分類演算法，不如把訓練數據好好的標註好。

SVM 處理大規模數據，應該對高維數據的支持比較好，但訓練樣本太多反而不好。

其實我覺得問題的邏輯應該是這樣的：因為很多業界大佬如GYM擁有極大的數據量，而且又有分類的需求，而SVM是分類模型中最經典的一個，所以就這麼去做。當然SVM的複雜度比較高，所以問題就是如何降低他的計算要求，或是如何並行化。（方案見另一問：http://www.zhihu.com/question/19591450）

不是說有了massive data後SVM會怎麼怎麼樣，而是SVM如何能應用到massive data上去