支持向量機SVM - 從入門到放棄

01-25

支持向量機全稱Support Vector Machine，簡稱SVM，其公式推導是廣大機器學習面試中經典的問題之一。用紙筆推算SVM的對偶性(Duality)更是面試官們喜聞樂見的測試，已近成為了機器學習八股文。而很多機器學習的實踐者也非常喜歡SVM，更是以擅長推公式而感到「自豪」。那今天就讓我們來談談SVM，分享一些我的看法。

首先，SVM在二十世紀初的確很火，曾經佔據過機器學習的大半壁江山。仔細想來，漂亮的數學公式，核函數的應用，以及在那個時代有限的數據和硬體下良好的表現，都使得SVM一度成為了主流的模型。

但隨著後來硬體的發展和數據量增大，神經網路慢慢有了一席之地並最終站穩了腳跟。一向穩紮穩打的決策樹為基底的模型，配合著集成學習，也逐步取代了SVM的位置。現在當我們試圖解決一個機器學習問題的時候，一般率先想到是集成學習，如隨機森林(Random Forests)和這兩年大火的XGBoost，而不再是SVM。那麼到底是什麼讓SVM慢慢走下了神壇呢?我有幾點不成熟的看法。

1. 模型穩定性低，輸入的微小變化會使得模型難以收斂。以Python為例，Sklearn中的Support Vector Classifier是基於C++版本的Libsvm。可調的參數包括C，取值範圍為0-1(在sklearn中)，決定了分類器對於誤分類的容忍度，C的取值越大，容忍度越低。當C=1時，分類器不允許誤分類的存在。如果SVM當下配合的核函數是非線性函數，如RBF，那麼在高維空間的確可以找到完全沒有誤分的方法。但如果用線性核搭配C=1或者較大的C，那麼有很大的概率分類器不會收斂，會一直運行下去。如下圖所示，C的大小代表了對誤分類的容忍度，從左至右C越來越小，容忍度越來大。當然，圖中的C的取值並不是0-1，這個和具體的代碼有關。

按照道理來說較大的C也可能收斂，但這個優化演算法有關，如果你的數據恰好各個維度間差別很大，那麼會因為各種原因在優化中陷入死循環無法跳脫，此處暫時不表。而對於新手來說，很多時候對於參數其實理解有限，很容易用網格搜索(GridSearch)扔進去一堆參數，那麼如果碰到上面這個情況，是否能收斂就看命了。而因為越來越多的工具包封裝程度很高，大部分人不會設置最大運行次數，所以會陷入死循環。如果你的數據集不大且長時間SVM無法收斂，可以嘗試：

檢查是否同時使用了線性核以及 C=1 (或其他較大的值)
嘗試將訓練數據進行歸一化或者標準化 (是否是因為優化過程出了問題)
嘗試設置最大訓練次數，默認的max_iter = -1會導致訓練器無限運行下去

2. 在數據量大的情況下運算複雜度高，不適合處理過大的數據。

在這個時代，多大的數據才算大？1TB還是10TB，可惜都不是。根據Sklearn文檔介紹：

The implementation is based on libsvm. The fit time complexity is more than quadratic with the number of samples which makes it hard to scale to dataset with more than a couple of 10000 samples.

10000條以上的數據對於SVM來說就不好處理了，這在2017年還是顯得很不合理。究其根本，核化的SVM本身的時間複雜度 $O(mn^2)$ 就是二次時間，n是樣本數，m是特徵數。當數據量較大的時候，還面臨空間複雜度的問題，cache的儲存可能不夠，因此在數據量大特徵多的情況下SVM的時間複雜度可能遠超二次時間。在這種情況下，除了調大cache的尺寸，還需要盡量的壓縮數據降低維度。然而最好的方法還是棄用SVM而選擇更好的模型。

3. 「乏善可陳」的分類能力。刨去前面提到的低穩定性不談，SVM當年最為自豪的分類能力似乎在各種新模型的對比下也顯得黯然失色。此處有經驗主義之談，我在很多數據上進行過對比，SVM雖然不是最差的，但很少有機會超過更受大家青睞的新的集成模型。

4. 總結

寫這篇文章是有感而發，最近在運行實驗的時候約定俗成的把SVM當作了一個參照組，結果負責跑試驗的朋友一晚上都在運行而無法收斂。等我再查看代碼時才發現了存在線性SVM和C=1的組合，這讓我再一次陷入到了曾被SVM推導折磨的恐懼當中。不過如果沒深刻了解過SVM，也不會這麼快想到為什麼模型無法收斂。

然而，在有這麼多優秀模型的前提下，跟SVM死磕似乎已經不再是最划算的做法。我也建議各位面試官們不要在沉迷於教科書上優美的SVM對偶性公式了。把面試時間花在考察應聘者解決問題的能力上來。而各位每天都在和機器學習打交道的朋友們，人生苦短，為什麼不用XGBoost呢？不僅效果好，收斂快，對數據缺失魯棒性強，還能自動對特徵重要性排序。

當然，這篇文章只是實驗之餘的調侃而已。不過從這裡說開去，機器學習的實踐者最重要的是選擇適合的模型解決問題，而不是理論漂亮的模型。而我們也要警惕機器學習面試越來越像八股文，就像現在的非常套路的程序員面試。我認為時間應該花在解決問題，而不是解決面試上去。

每當想到以後可能也有機器學習版的LeetCode，我就感到不寒而慄。?????

註：此文的目的只是為了說明SVM不再是最好的out of box演算法，在非常少數的情況下可能SVM會有不錯的表現。