雷鋒網(wǎng) AI 科技評論按，本文為韋易笑在知乎問題如何學(xué)習(xí)SVM（支持向量機(jī)）以及改進(jìn)實(shí)現(xiàn)SVM算法程序下面的回復(fù)，雷鋒網(wǎng) AI 科技評論獲其授權(quán)轉(zhuǎn)載。以下為正文：

學(xué)習(xí) SVM 的最好方法是實(shí)現(xiàn)一個(gè) SVM，可講理論的很多，講實(shí)現(xiàn)的太少了。

假設(shè)你已經(jīng)讀懂了 SVM 的原理，并了解公式怎么推導(dǎo)出來的，比如到這里：

SVM 的問題就變成：求解一系列滿足約束的 alpha 值，使得上面那個(gè)函數(shù)可以取到最小值。然后記錄下這些非零的 alpha 值和對應(yīng)樣本中的 x 值和 y 值，就完成學(xué)習(xí)了，然后預(yù)測的時(shí)候用：

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

那么剩下的 SVM 實(shí)現(xiàn)問題就是如何求解這個(gè)函數(shù)的極值。方法有很多，我們先找個(gè)起點(diǎn)，比如 Platt 的 SMO 算法，它后面有偽代碼描述怎么快速求解 SVM 的各個(gè)系數(shù)。

第一步：實(shí)現(xiàn)傳統(tǒng)的 SMO 算法

現(xiàn)在大部分的 SVM 開源實(shí)現(xiàn)，源頭都是 platt 的 smo 算法，讀完他的文章和推導(dǎo)，然后照著偽代碼寫就行了，核心代碼沒幾行：

target = desired output vector

point = 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 < 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 1

endprocedure

核心代碼很緊湊，就是給定兩個(gè) ai, aj，然后迭代出新的 ai, aj 出來，還有一層循環(huán)會(huì)不停的選擇最需要被優(yōu)化的系數(shù) ai, aj，然后調(diào)用這個(gè)函數(shù)。如何更新權(quán)重和 b 變量（threshold）文章里面都有說，再多調(diào)試一下，可以用 python 先調(diào)試，再換成 C/C++，保證得到一個(gè)正確可用的 SVM 程序，這是后面的基礎(chǔ)。

第二步：實(shí)現(xiàn)核函數(shù)緩存

觀察下上面的偽代碼，開銷最大的就是計(jì)算核函數(shù) K(xi, xj)，有些計(jì)算又反復(fù)用到，一個(gè) 100 個(gè)樣本的數(shù)據(jù)集求解，假設(shè)總共要調(diào)用核函數(shù) 20 萬次，但是 xi, xj 的組和只有 100x100=1 萬種，有緩存的話你的效率可以提升 20 倍。

樣本太大時(shí)，如果你想存儲(chǔ)所有核函數(shù)的組和，需要 N*N * sizeof(double) 的空間，如果訓(xùn)練集有 10 萬個(gè)樣本，那么需要 76 GB 的內(nèi)存，顯然是不可能實(shí)現(xiàn)的，所以核函數(shù)緩存是一個(gè)有限空間的 LRU 緩存，SVM 的 SMO 求解過程中其實(shí)會(huì)反復(fù)用到特定的幾個(gè)有限的核函數(shù)求解，所以命中率不用擔(dān)心。

有了這個(gè)核函數(shù)緩存，你的 SVM 求解程序能瞬間快幾十倍。

第三步：優(yōu)化誤差值求解

注意看上面的偽代碼，里面需要計(jì)算一個(gè)估計(jì)值和真實(shí)值的誤差 Ei 和 Ej，他們的求解方法是：

E(i) = f(xi) - yi

這就是目前為止 SMO 這段為代碼里代價(jià)最高的函數(shù)，因?yàn)榛仡櫹律厦娴墓?，?jì)算一遍 f(x) 需要 for 循環(huán)做乘法加法。

platt 的文章建議是做一個(gè) E 函數(shù)的緩存，方便后面選擇 i, j 時(shí)比較，我看到很多入門版本 SVM 實(shí)現(xiàn)都是這么做。其實(shí)這是有問題的，后面我們會(huì)說到。最好的方式是定義一個(gè) g(x) 令其等于：

也就是 f(x) 公式除了 b 以外前面的最費(fèi)時(shí)的計(jì)算，那么我們隨時(shí)可以計(jì)算誤差：

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

所以最好的辦法是對 g(x) 進(jìn)行緩存，platt 的方法里因?yàn)樗?alpha 值初始化成了 0，所以 g(x) 一開始就可以全部設(shè)置成 0，稍微觀察一下 g(x) 的公式，你就會(huì)發(fā)現(xiàn)，因?yàn)槿サ袅?b 的干擾，而每次 SMO 迭代更新 ai, aj 參數(shù)時(shí)，這兩個(gè)值都是線性變化的，所以我們可以給 g(x) 求關(guān)于 a 的偏導(dǎo)，假設(shè) ai，aj 變化了步長 delta，那么所有樣本對應(yīng)的 g(x) 加上 delta 乘以針對 ai, aj 的偏導(dǎo)數(shù)就行了，具體代碼類似：

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 以后，更新所有樣本對應(yīng)的 g(x) 緩存，這樣通過每次迭代更新 g(x) 避免了大量的重復(fù)計(jì)算。

這其實(shí)是很直白的一種優(yōu)化方式，我查了一下，有人專門發(fā)論文就講了個(gè)類似的方法。

第四步：實(shí)現(xiàn)冷熱數(shù)據(jù)分離

Platt 的文章里也證明過一旦某個(gè) alpha 出于邊界（0 或者 C）的時(shí)候，就很不容易變動(dòng)，而且偽代碼也是優(yōu)先在工作集里尋找 > 0 and < C 的 alpha 值進(jìn)行優(yōu)化，找不到了，再對工作集整體的 alpha 值進(jìn)行迭代。

那么我們勢必就可以把工作集分成兩個(gè)部分，熱數(shù)據(jù)在前（大于 0 小于 C 的 alpha 值），冷數(shù)據(jù)在后（小于等于 0 或者大于等于 C 的 alpha）。

隨著迭代加深，會(huì)發(fā)現(xiàn)大部分時(shí)候只需要在熱數(shù)據(jù)里求解，并且熱數(shù)據(jù)的大小會(huì)逐步不停的收縮，所以區(qū)分了冷熱以后 SVM 大部分都在針對有限的熱數(shù)據(jù)迭代，偶爾不行了，再全部迭代一次，然后又回到冷熱迭代，性能又能提高不少。

第五步：支持 Ensemble

大家都知道，通過 Ensemble 可以讓多個(gè)不同的弱模型組和成一個(gè)強(qiáng)模型，而傳統(tǒng) SVM 實(shí)現(xiàn)并不能適應(yīng)一些類似 AdaBoost 的集成方法，所以我們需要做一些改動(dòng)?？梢宰屚饷驷槍δ骋粋€(gè)分類傳入一個(gè)“權(quán)重”過來，修正 SVM 的識別結(jié)果。

最傳統(tǒng)的修改方式就是將不等式約束 C 分為 Cp 和 Cn 兩個(gè)針對 +1 分類的 C 及針對 -1 分類的 C。修改方式是直接用原始的 C 乘以各自分類的權(quán)重，得到 Cp 和 Cn，然后迭代時(shí)，不同的樣本根據(jù)它的 y 值符號，用不同的 C 值帶入計(jì)算。

這樣 SVM 就能用各種集成方法同其他模型一起組成更為強(qiáng)大精準(zhǔn)的模型了。

實(shí)現(xiàn)到這一步你就得到了功能上和性能上同 libsvm 類似的東西，接下來我們繼續(xù)優(yōu)化。

第六步：繼續(xù)優(yōu)化核函數(shù)計(jì)算

核函數(shù)緩存非常消耗內(nèi)存，libsvm 數(shù)學(xué)上已經(jīng)沒得挑了，但是工程方面還有很大改進(jìn)余地，比如它的核緩存實(shí)現(xiàn)。

由于標(biāo)準(zhǔn) SVM 核函數(shù)用的是兩個(gè)高維矢量的內(nèi)積，根據(jù)內(nèi)積的幾個(gè)條件，SVM 的核函數(shù)又是一個(gè)正定核，即 K(xi, xj) = K(xj, xi)，那么我們同樣的內(nèi)存還能再多存一倍的核函數(shù)，性能又能有所提升。

針對核函數(shù)的計(jì)算和存儲(chǔ)有很多優(yōu)化方式，比如有人對 NxN 的核函數(shù)矩陣進(jìn)行采樣，只計(jì)算有限的幾個(gè)核函數(shù)，然后通過插值的方式求解出中間的值。還有人用 float 存儲(chǔ)核函數(shù)值，又降低了一倍空間需求。

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

對于高維樣本，比如文字這些，可能有上千維，每個(gè)樣本的非零特征可能就那么幾個(gè)，所以稀疏向量會(huì)比較高效，libsvm 也是用的稀疏向量。

但是還有很多時(shí)候樣本是密集向量，比如一共 200 個(gè)特征，大部分樣本都有 100個(gè)以上的非零特征，用稀疏向量存儲(chǔ)的話就非常低效了，openCV 的 SVM 實(shí)現(xiàn)就是非稀疏向量。

非稀疏向量直接是用數(shù)組保存樣本每個(gè)特征的值，在工程方面就有很多優(yōu)化方式了，比如用的最多的求核函數(shù)的時(shí)候，直接上 SIMD 指令或者 CUDA，就能獲得更好的計(jì)算性能。

所以最好的方式是同時(shí)支持稀疏和非稀疏，兼顧時(shí)間和空間效率，對不同的數(shù)據(jù)選擇最適合的方式。

第八步：針對線性核進(jìn)行優(yōu)化

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

K(xi, xj) = xi . xj

還有很多更高效的求解思路，比如 Pegasos 算法就用了一種類似隨機(jī)梯度下降的方法，快速求 SVM 的解權(quán)重 w，如果你的樣本適合線性核，使用一些針對性的非 SMO 算法可以極大的優(yōu)化 SVM 求解，并且能處理更加龐大的數(shù)據(jù)集，LIBLINEAR 就是做這件事情的。

同時(shí)這類算法也適合 online 訓(xùn)練和并行訓(xùn)練，可以逐步更新增量訓(xùn)練新的樣本，還可以用到多核和分布式計(jì)算來訓(xùn)練模型，這是 SMO 算法做不到的地方。

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

或許哪天出個(gè)數(shù)學(xué)家又找到一種更好的方法，可以用類似 pegasos 的方式求解非線性核，那么 SVM 就能有比較大的進(jìn)展了。

后話

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

上面就是如何實(shí)現(xiàn)一個(gè)相對成熟的 SVM 模型的思路，以及配套優(yōu)化方法，再往后還有興趣，可以接著實(shí)現(xiàn)支持向量回歸，也是一個(gè)很有用的東西。

雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。