如何學習SVM？怎麼改進實現SVM演算法程式？答案來了

AI1002019-09-13 09:27:22

編輯 | 憶臻

來源 | 深度學習這件小事（ID：DL_NLP）

【導讀】在 3D 動作識別領域，需要用到 SVM（支援向量機演算法），但是現在所知道的 SVM 演算法很多很亂，相關的程式包也很多，有什麼方法可以幫助我們更好地理解 SVM 演算法，以及如何利用 matlab 程式設計實現 SVM 演算法，同時在理解原有的程式包以及在原有的程式包基礎上進行改進有什麼好的方法？本文為知乎問題“如何學習 SVM（支援向量機）以及改進實現 SVM 演算法程式？”下的兩個答案。

作者：韋易笑
http://www.zhihu.com/question/31211585/answer/640501555

學習 SVM 的最好方法是實現一個 SVM，可講理論的很多，講實現的太少了。

假設你已經讀懂了 SVM 的原理，並瞭解公式怎麼推匯出來的，比如到這裡：

SVM 的問題就變成：求解一系列滿足約束的 alpha 值，使得上面那個函式可以取到最小值。然後記錄下這些非零的 alpha 值和對應樣本中的 x 值和 y 值，就完成學習了，然後預測的時候用：

上面的公式計算出 f(x) ，如果返回值 > 0 那麼是 +1 類別，否則是 -1 類別，先把這一步怎麼來的，為什麼這麼來找篇文章讀懂，不然你會做的一頭霧水。

那麼剩下的 SVM 實現問題就是如何求解這個函式的極值。方法有很多，我們先找個起點，比如 Platt 的 SMO 演算法，它後面有虛擬碼描述怎麼快速求解 SVM 的各個係數。

第一步：實現傳統的 SMO 演算法

現在大部分的 SVM 開源實現，源頭都是 platt 的 smo 演算法，讀完他的文章和推導，然後照著虛擬碼寫就行了，核心程式碼沒幾行：


target = desired output vectorpoint = training point matrix
procedure takeStep(i1,i2)   if (i1 == i2) return 0   alph1 = Lagrange multiplier for i1   y1 = target[i1]   E1 = SVM output on point[i1] – y1 (check in error cache)   s = y1*y2   Compute L, H via equations (13) and (14)   if (L == H)      return 0   k11 = kernel(point[i1],point[i1])   k12 = kernel(point[i1],point[i2])   k22 = kernel(point[i2],point[i2])   eta = k11+k22-2*k12   if (eta > 0)   {      a2 = alph2 + y2*(E1-E2)/eta      if (a2       else if (a2 > H) a2 = H   }   else   {      Lobj = objective function at a2=L      Hobj = objective function at a2=H      if (Lobj          a2 = L      else if (Lobj > Hobj+eps)         a2 = H      else         a2 = alph2   }   if (|a2-alph2|       return 0   a1 = alph1+s*(alph2-a2)   Update threshold to reflect change in Lagrange multipliers   Update weight vector to reflect change in a1 & a2, if SVM is linear   Update error cache using new Lagrange multipliers   Store a1 in the alpha array   Store a2 in the alpha array   return 1endprocedure

核心程式碼很緊湊，就是給定兩個 ai, aj 然後迭代出新的 ai, aj 出來，還有一層迴圈會不停的選擇最需要被優化的係數 ai, aj，然後呼叫這個函式。如何更新權重和 b 變數（threshold）文章裡面都有說，再多除錯一下，可以用 python 先除錯過了，再換成 C/C++，保證得到一個正確可用的 svm 程式，這是後面的基礎。

第二步：實現核函式快取

觀察下上面的虛擬碼，開銷最大的就是計算核函式 K(xi, xj)，有些計算又反覆用到，一個 100 個樣本的資料集求解，假設總共要呼叫核函式 20 萬次，但是 xi, xj 的組和只有 100x100=1萬種，有快取的話你的效率可以提升 20 倍。

樣本太大時，如果你想儲存所有核函式的組和，需要 N*N * sizeof(double) 的空間，如果訓練集有 10 萬個樣本，那麼需要 76 GB 的記憶體，顯然是不可能實現的，所以核函式快取是一個有限空間的 LRU 快取，SVM 的 SMO 求解過程中其實會反覆的用到特定的幾個有限的核函式求解，所以命中率不用擔心。

有了這個核函式快取，你的 svm 求解程式能瞬間快幾十倍。

第三步：優化誤差值求解

注意看上面的虛擬碼，裡面需要計算一個估計值和真實值的誤差 Ei 和 Ej，他們的求解方法是：


E(i) = f(xi) - yi

這就是目前為止 SMO 這段為程式碼裡代價最高的函式，因為回顧下上面的公式，計算一遍 f(x) 需要 for 迴圈做乘法加法。

platt 的文章建議是做一個 E 函式的快取，方便後面選擇 i, j 時比較，我看到很多入門版本 svm 實現都是這麼搞得。其實這是有問題的，後面我們會說到。最好的方式是定義一個 g(x) 令其等於：

也就是 f(x) 公式除了 b 以外前面那一坨最費時的計算，那麼我們隨時可以計算誤差：


E(j) = g(xj) + b - yj

所以最好的辦法是對 g(x) 進行快取，platt 的方法裡因為所有 alpha 值初始化成了 0，所以 g(x) 一開始就可以全部設定成 0，稍微觀察一下 g(x) 的公式，你就會發現，因為去掉了 b 的干擾，而每次 SMO 迭代更新 ai, aj 引數時，這兩個值都是線性變化的，所以我們可以給 g(x) 求一個關於 a 的偏導，假設 ai，aj 變化了步長 delta，那麼所有樣本對應的 g(x) 加上一個 delta 乘以針對 ai, aj 的偏導數就行了，具體程式碼類似：


double Kik = kernel(i, k);double Kjk = kernel(j, k);G[k] += delta_alpha_i * Kik * y[i] + delta_alpha_j * Kjk * y[j];

把這段程式碼放在 takeStep 後面，每次成功更新一對 ai, aj 以後，更新所有樣本對應的 g(x) 快取，這樣通過每次迭代更新 g(x) 避免了大量的重複計算。

這其實是很直白的一種優化方式，我查了一下，有人專門發論文就講了個類似的方法。

第四步：實現冷熱資料分離

Platt 的文章裡也證明過一旦某個 alpha 出於邊界（0 或者 C）的時候，就很不容易變動，而且虛擬碼裡也是優先再工作集裡尋找 > 0 and

那麼我們勢必就可以把工作集分成兩個部分，熱資料在前（大於0小於C的alpha值），冷資料在後（小於等於0 或者大於等於 C 的alpha）再後。

隨著迭代加深，會發現大部分時候只需要再熱資料裡求解，並且熱資料的大小會逐步不停的收縮，所以區分了冷熱以後你的 SVM 大部分都在針對有限的熱資料迭代，偶爾不行了，再全部迭代一次，然後又回到冷熱迭代，效能又能提高不少。

第五步：支援 Ensemble

大家都知道，通過 Ensemble 可以讓多個不同的弱模型組和成一個強模型，而傳統 SVM 實現並不能適應一些類似 AdaBoost 的整合方法，所以我們需要做一些改動。可以讓外面針對某一個分類傳入一個“權重”過來，修正 SVM 的識別結果。

最傳統的修改方式就是將不等式約束 C 分為 Cp 和 Cn 兩個針對 +1 分類的 C，和針對 -1 分類的 C。修改方式是直接用原始的 C 乘以各自分類的權重，得到 Cp 和 Cn，然後迭代時，不同的樣本根據它的 y 值符號，用不同的 C 值帶入計算。

這樣 SVM 就能用各種整合方法同其他模型一起組成更為強大精準的模型了。

實現到這一步你就得到了功能上和效能上同 libsvm 類似的東西，接下來我們繼續優化。

第六步：繼續優化核函式計算

核函式快取非常消耗記憶體，libsvm 數學上已經沒得挑了，但是工程方面還有很大改進餘地，比如它的核快取實現。

由於標準 SVM 核函式用的是兩個高維向量的內積，根據內積的幾個條件，SVM 的核函式又是一個正定核，即 K(xi, xj) = K(xj, xi)，那麼我們同樣的記憶體還能再多存一倍的核函式，效能又能有所提升。

針對核函式的計算和儲存有很多優化方式，比如有人對 NxN 的核函式矩陣進行取樣，只計算有限的幾個核函式，然後通過插值的方式求解出中間的值。還有人用 float 儲存核函式值，又降低了一倍空間需求。

第七步：支援稀疏向量和非稀疏向量

對於高維樣本，比如文字這些，可能有上千維，每個樣本的非零特徵可能就那麼幾個，所以稀疏向量會比較高效，libsvm 也是用的稀疏向量。

但是還有很多時候樣本是密集向量，比如一共 200 個特徵，大部分樣本都有 100個以上的非零特徵，用稀疏向量儲存的話就非常低效了，opencv 的 svm 實現就是非稀疏向量。

非稀疏向量直接是用陣列儲存樣本每個特診的值，在工程方面就有很多優化方式了，比如用的最多的求核函式的時候，直接上 SIMD 指令或者 CUDA，就能獲得更好的計算效能。

所以最好的方式是同時支援稀疏和非稀疏，兼顧時間和空間效率，對不同的資料選擇最適合的方式。

第八步：針對線性核進行優化

傳統的 SMO 方法，是 SVM 的通用求解方法，然而針對線性核，就是：


K(xi, xj) = xi . xj

還有很多更高效的求解思路，比如 Pegasos 演算法就用了一種類似隨機梯度下降的方法，快速求 svm 的解權重 w，如果你的樣本適合線性核，是用一些針對性的非 SMO 演算法可以極大的優化 SVM 求解，並且能處理更加龐大的資料集，LIBLINEAR 就是做這件事情的。

同時這類演算法也適合 online 訓練和並行訓練，可以逐步更新的方式增量訓練新的樣本，還可以用到多核和分散式計算來訓練模型，這是 SMO 演算法做不到的地方。

但是如果碰到非線性核，權重 w 處於高維核空間裡（有可能無限維），你沒法梯度下降迭代 w，並且 pegasos 的 pdf 裡面也沒有提到如何用到非線性核上，LIBLINEAR 也沒有辦法處理非線性核。

或許哪天出個數學家又找到一種更好的方法，可以用類似 pegasos 的方式求解非線性核，那麼 SVM 就能有比較大的進展了。

後話

上面八條，你如果實現前三條，基本就能深入理解 SVM 的原理了，如果實現一大半，就可以得到一個類似 libsvm 的東西，全部實現，你就能得到一個比 libsvm 更好用的 svm 庫了。

上面就是如何實現一個相對成熟的 svm 模型的思路，以及配套優化方法，再往後還有興趣，可以接著實現支援向量迴歸，也是一個很有用的東西。

作者：mmggqq
http://www.zhihu.com/question/31211585/answer/334551171

講道理，現在絕大部分的開源 SVM 演算法實現都比自己實現的效率高不知道多少倍（除非你是超級大牛），如果你想更好地理解原有的程式包並且在其上面改進的話，除了讀人家的實現庫文件和原始碼並沒有其他捷徑。但是我還是建議在理論學習完 SVM 後自己實現一個簡單的玩具，在實際運用中還是運用別人的庫把，你需要的功能絕大部分上面都有實現。