雷鋒網 AI 科技評論按，本文為韋易笑在知乎問題如何學習SVM（支持向量機）以及改進實現SVM算法程序下面的回覆，雷鋒網 AI 科技評論獲其授權轉載。以下為正文：
學習 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 matrixprocedure 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 < L) a2 = L else if (a2 > H) a2 = H } else { Lobj = objective function at a2=L Hobj = objective function at a2=H if (Lobj < Hobj-eps) a2 = L else if (Lobj > Hobj+eps) a2 = H else a2 = alph2 } if (|a2-alph2| < eps*(a2+alph2+eps)) 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 < C 的 alpha 值進行優化，找不到了，再對工作集整體的 alpha 值進行迭代。
那麼我們勢必就可以把工作集分成兩個部分，熱數據在前（大於 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 模型的思路，以及配套優化方法，再往後還有興趣，可以接著實現支持向量回歸，也是一個很有用的東西。