劃到雙變量解析更新的全程推導)
提起 SMO很多人的第一印象是“SVM 庫內部那個優(yōu)化器”——調包調久了接口后面發(fā)生了什么很少有人細看。但序列最小最優(yōu)化算法SMO值得每一個做機器學習的人認真拆一遍它把一個大到近乎無解的二次規(guī)劃問題拆成無數(shù)個只包含兩個變量的子問題而且每個子問題都能用解析公式直接算出不需要任何數(shù)值優(yōu)化庫。這個設計在今天看來依然非常聰明理解它之后你會對 SVM 的訓練過程、支持向量的含義、甚至調參時那些“說不清但確實有效”的經驗有完全不一樣的感覺。這篇文章不準備從零堆數(shù)學公式而是順著 SMO 的求解思路走一遍先從 SVM 訓練為什么難解講起再拆 SMO 的核心機制、兩個乘子的解析求解、啟發(fā)式選擇策略、收斂判定細節(jié)最后給一份可以照著改的 Python 簡化實現(xiàn)以及我在實際調試中踩過的坑。適合想搞懂 SMO 內部邏輯的學生、面試被問到 SMO 細節(jié)的求職者以及想手動實現(xiàn)一遍而不是只調庫的工程師。1. 為什么SVM訓練必須拆成小問題一個被核矩陣卡死的優(yōu)化困境1.1 從分類超平面到凸二次規(guī)劃SVM 的分類思路是找一個間隔最大的超平面。線性可分情況下這個超平面要滿足所有點都被正確分開同時離它最近的點要盡可能遠。數(shù)學上這個問題等價于最小化 $\frac{1}{2}||w||^2$約束是 $y_i(w^T x_i b) \ge 1$。但現(xiàn)實數(shù)據(jù)幾乎都不是線性可分的于是引入松弛變量 $\xi_i$ 和懲罰系數(shù) $C$把目標改成$$ \min_{w,b,\xi} \frac{1}{2}||w||^2 C\sum_{i1}^{N}\xi_i $$加上約束 $y_i(w^T x_i b) \ge 1 - \xi_i$、$\xi_i \ge 0$ 之后用拉格朗日乘子法轉成對偶問題就會得到下面這個形式$$ \max_{\alpha} W(\alpha) \sum_{i1}^{N}\alpha_i - \frac{1}{2}\sum_{i1}^{N}\sum_{j1}^{N}\alpha_i \alpha_j y_i y_j K(x_i, x_j) $$約束條件有三個$\alpha_i \ge 0$、$\alpha_i \le C$、$\sum_{i1}^{N}\alpha_i y_i 0$。這里的 $K(x_i, x_j)$ 是核函數(shù)也就是把原始特征映射到高維空間后的內積。SMO 就是在解這個對偶問題——準確說是在解這個帶約束的凸二次規(guī)劃QP問題。1.2 標準QP方法的內存噩夢如果從來沒親手解過 SVM 的對偶問題你可能會說這很簡單啊找個現(xiàn)成的 QP 求解器丟進去不就好了理論上確實如此但一算復雜度就發(fā)現(xiàn)問題了。對偶目標函數(shù)中有一個 $\alpha_i \alpha_j K(x_i, x_j)$ 的求和項這意味著我們需要一個 $N \times N$ 的核矩陣 $K$。當訓練樣本有 1000 個時核矩陣是 1000×1000存下來大約 8MB當樣本數(shù)到 1 萬就是 800MB到 10 萬80GB直接內存爆炸。即便你把矩陣稀疏化處理或分塊迭代標準的數(shù)值優(yōu)化方法每一次迭代都要做矩陣運算代價依然高得離譜。這就是 SVM 在早期很難大規(guī)模落地的原因。我記得以前在某高校實驗室跑一個模擬項目數(shù)據(jù)量只有小幾萬直接用內點法求解對偶問題內存就吃到了好幾個 G而且收斂非常慢。后來換了基于分解思想的優(yōu)化器訓練時間從幾十分鐘直接降到了幾分鐘這就是 SMO 這類算法存在的意義。1.3 SMO的做法把大問題切成“一口能吃下去”的小塊SMO 的想法很直接既然一次性解 $N$ 個 $\alpha$ 代價太大那就一次只解其中的一小部分。它每次選擇一個工作集只對這些 $\alpha$ 做優(yōu)化固定其他所有 $\alpha$然后在子問題上求出解析解。關鍵點在于SMO 選的工作集大小是 2。為什么不能是 1因為約束 $\sum_i \alpha_i y_i 0$ 把整個 $\alpha$ 向量綁在了一個超平面上如果只動一個 $\alpha_i$約束瞬間就破壞了必須同時動另一個 $\alpha_j$ 來“補償”它。所以 2 是保持等式約束可行的最小單位。每優(yōu)化兩個 $\alpha$SMO 只需要計算對應的核函數(shù)值不需要存儲整個核矩陣。那些核函數(shù)值可以實時算也可以緩存一部分?？臻g復雜度從 $O(N^2)$ 降到了 $O(N)$這是 SMO 能處理大規(guī)模數(shù)據(jù)的最根本原因。2. 為什么每次只動兩個拉格朗日乘子約束下的最小自由度2.1 單變量更新為何走不通很多第一次接觸坐標下降法的人會想那我挨個 $\alpha_i$ 更新不就行了每次固定其他變量只優(yōu)化一個這就是經典的坐標下降法。但 SVM 對偶問題里的等式約束 $\sum_i \alpha_i y_i 0$ 是一道硬墻。假設你固定除 $\alpha_1$ 外的所有 $\alpha$那么 $\alpha_1$ 的值就已經被唯一確定沒有任何可調整空間。同理如果你固定 $\alpha_1, \alpha_3, \alpha_4, \dots$只動 $\alpha_2$$\alpha_2$ 同樣被鎖死。所以單變量子問題在數(shù)學上不可行必須同時更新兩個變量才能有真正的自由度。這也是為什么 SMO 叫“序列最小優(yōu)化”——每次優(yōu)化的子問題規(guī)模是所有滿足約束的最小子問題也就是兩個變量。2.2 兩個變量的組合方式等式約束下的一條線段當只看兩個變量 $\alpha_1$ 和 $\alpha_2$ 的時候等式約束變成$$ y_1 \alpha_1 y_2 \alpha_2 y_1 \alpha_1^{old} y_2 \alpha_2^{old} \text{常數(shù)} $$這條直線在 $(\alpha_1, \alpha_2)$ 平面上是一條斜線再加上 $0 \le \alpha_i \le C$ 的盒子約束可行域就是這條直線穿過盒子后剩下的線段。換句話說無論我們怎么調整$\alpha_1$ 和 $\alpha_2$ 都必須落在這條線段上。一旦確定 $\alpha_2$ 的新值$\alpha_1$ 的新值就被這條直線唯一確定這就是 SMO 解析更新公式的幾何基礎。2.3 SMO與坐標下降法的關系嚴格來說SMO 可以看作坐標下降法在帶等式約束條件下的變體它每次在一個二維坐標平面上做精確的一維搜索但因為約束的存在坐標軸要沿著約束方向“旋轉”一下。我當初學的時候有個直觀的感受坐標下降法就像你在一個有圍欄的山坡上每次都只沿著東西或南北方向走一小步而 SMO 則像是沿著圍欄的方向走每次保證不越界而且每步都能直接走到這個方向的局部最低點。所以 SMO 的收斂速度在多數(shù)情況下是比普通坐標下降快的。2.4 子問題的幾何直覺再往深一層如果 $y_1 y_2$那么等式約束變成 $\alpha_1 \alpha_2 \text{常數(shù)}$可行域是一條斜率為 -1 的線段如果 $y_1 \ne y_2$等式約束變成 $\alpha_1 - \alpha_2 \text{常數(shù)}$可行域是一條斜率為 1 的線段。上下界 $L$ 和 $H$ 就是這條線段兩端被盒子邊界截斷的位置。理解這個幾何關系對后面推導 $L$、$H$ 的公式非常有用。很多教程直接甩兩個 case 的公式讓人背背完就忘理解了截斷原理任何時候都能自己推出來。3. 兩個乘子的解析求解從二次函數(shù)求導到上下界裁剪3.1 拆出與α1、α2相關的目標函數(shù)現(xiàn)在進入 SMO 最核心的數(shù)學部分。我們把對偶目標函數(shù) $W(\alpha)$ 中所有含 $\alpha_1$、$\alpha_2$ 的項單獨拆出來其余項因為在本次迭代中不變可以直接消去。展開后目標函數(shù)是$$ W \alpha_1 \alpha_2 - \frac{1}{2} \alpha_1^2 K_{11} - \frac{1}{2} \alpha_2^2 K_{22} - \alpha_1 \alpha_2 y_1 y_2 K_{12} $$ $$y_1 \alpha_1 \sum_{i\ne 1}\alpha_i y_i K_{i1} - y_2 \alpha_2 \sum_{i\ne 2}\alpha_i y_i K_{i2} \text{常數(shù)項} $$其中 $K_{ij} K(x_i, x_j)$常數(shù)項包含所有與 $\alpha_1$、$\alpha_2$ 無關的部分。由于 $\alpha_1$ 和 $\alpha_2$ 由等式約束綁定我們只需優(yōu)化 $\alpha_2$ 一個變量$\alpha_1$ 是它的函數(shù)。3.2 用等式約束消掉α1令 $s y_1 y_2$等式約束可以寫成$$ \alpha_1 s \alpha_2 \alpha_1^{old} s \alpha_2^{old} \gamma $$于是$$ \alpha_1 \gamma - s \alpha_2 $$把 $\alpha_1$ 代入 $W$目標函數(shù)就變成只關于 $\alpha_2$ 的一元二次函數(shù)。到這里問題已經轉化成了高中生的求拋物線極值問題只是別忘了后面還有 $[0, C]$ 的邊界約束。3.3 解析更新公式的推導對一元二次函數(shù)求導并令導數(shù)為 0可以得到未裁剪的 $\alpha_2$ 新值公式$$ \alpha_2^{new, unc} \alpha_2^{old} \frac{y_2(E_1 - E_2)}{\eta} $$其中 $E_i u_i - y_i$ 是第 $i$ 個樣本的預測誤差$u_i \sum_j \alpha_j y_j K(x_j, x_i) b$ 是當前模型對第 $i$ 個樣本的預測輸出$\eta K_{11} K_{22} - 2K_{12}$。很多資料里符號跟我這里不太一樣原因在于 $E_i$ 的定義究竟是“預測減真值”還是“真值減預測”。我建議統(tǒng)一用“預測減真值”來記憶推導過程會更順。如果你看到別處的公式符號相反不要慌檢查一下它的 $E$ 定義。$\eta$ 的物理含義是兩個樣本在核函數(shù)映射后的距離平方的一半嚴謹?shù)卣f$\eta ||\phi(x_1) - \phi(x_2)||^2$它衡量了兩個樣本在特征空間中的距離。$\eta$ 越小說明兩個樣本在特征空間里越接近更新的步長就越大$\eta$ 接近 0 時解析解的分母趨近 0這種情況需要單獨處理。3.4 可行域裁剪L和H的計算未裁剪的解不一定落在可行域內必須把它裁剪到線段 $[L, H]$ 上。$L$ 和 $H$ 的計算邏輯如下當 $y_1 y_2$ 時$$ L \max(0, \alpha_1^{old} \alpha_2^{old} - C), \quad H \min(C, \alpha_1^{old} \alpha_2^{old}) $$當 $y_1 \ne y_2$ 時$$ L \max(0, \alpha_2^{old} - \alpha_1^{old}), \quad H \min(C, C \alpha_2^{old} - \alpha_1^{old}) $$裁剪得到$$ \alpha_2^{new} \begin{cases} H, \alpha_2^{new, unc} H \ \alpha_2^{new, unc}, L \le \alpha_2^{new, unc} \le H \ L, \alpha_2^{new, unc} L \end{cases} $$然后由 $\alpha_1 \gamma - s \alpha_2$ 反解出$$ \alpha_1^{new} \alpha_1^{old} s(\alpha_2^{old} - \alpha_2^{new}) $$3.5 更新b和誤差的時機$\alpha$ 更新完之后$b$ 也必須同步更新否則模型輸出 $u_i$ 仍然是舊的后續(xù)迭代誤差全都會錯。$b$ 的更新依賴當前 $\alpha$ 的變化量和新舊核值$$ b_1 b - E_1 - y_1(\alpha_1^{new} - \alpha_1^{old})K_{11} - y_2(\alpha_2^{new} - \alpha_2^{old})K_{12} $$$$ b_2 b - E_2 - y_1(\alpha_1^{new} - \alpha_1^{old})K_{12} - y_2(\alpha_2^{new} - \alpha_2^{old})K_{22} $$選擇規(guī)則是若 $0 \alpha_1^{new} C$取 $b b_1$否則若 $0 \alpha_2^{new} C$取 $b b_2$若兩者都在邊界上取 $b (b_1 b_2) / 2$。這個選擇規(guī)則并不是拍腦袋定的。當某個 $\alpha$ 嚴格落在 $(0, C)$ 內部意味著該樣本恰好落在間隔邊界上它對應的 KKT 條件要求 $y_i u_i 1$因此 $b$ 有唯一確定值如果兩個 $\alpha$ 都在邊界上說明當前迭代沒有提供足夠的約束信息$b$ 可能落在一個區(qū)間內這時取平均是最穩(wěn)妥的近似。4. 啟發(fā)式選擇策略決定SMO收斂速度的分水嶺4.1 盲目選擇第一個乘子的代價理論上只要每輪都找一個違反 KKT 條件的乘子對并做一次解析更新SMO 就一定會收斂。但如果每次隨機選收斂速度會慢到讓人崩潰。原因在于隨機選擇的兩點可能已經在最優(yōu)值附近更新幅度極小甚至在邊界上連動都不能動白白浪費大量計算。實際工程中選的好不好對迭代次數(shù)的影響是數(shù)量級的差異——同一個數(shù)據(jù)集上好的選擇策略可能 200 次迭代收斂隨機選擇可能 5000 次都不一定停。4.2 外循環(huán)優(yōu)先尋找違反KKT條件的樣本SMO 的外循環(huán)負責選第一個乘子 $\alpha_i$。它的策略是優(yōu)先遍歷那些違反 KKT 條件最嚴重的樣本。具體做法通常分兩遍走第一遍遍歷所有非邊界樣本也就是 $0 \alpha_i C$ 的那部分。為什么優(yōu)先它們因為這些樣本恰好落在間隔邊界上它們對模型的影響最直接也最容易被 KKT 條件判定為“不合格”。第二遍才遍歷全部樣本。如果第一遍把所有非邊界樣本都檢查完沒有發(fā)現(xiàn)需要更新的乘子再對全部樣本做一次掃描看有沒有漏網之魚。這種“先邊界后全局”的策略可以理解為熟悉的地方先仔細查查不到問題再去整個空間掃一遍。很多實現(xiàn)還會記錄一輪迭代中是否有 $\alpha$ 發(fā)生變化如果有下一輪繼續(xù)優(yōu)先掃描非邊界樣本直到連續(xù)多輪都沒有變化才切換到全局掃描。這個細節(jié)對收斂速度影響非常大。4.3 內循環(huán)基于最大步長原則選擇配對乘子外循環(huán)選好 $\alpha_i$ 之后內循環(huán)負責選第二個乘子 $\alpha_j$。SMO 的目標是找一個和 $\alpha_i$ 配對后能產生最大“步長”的 $\alpha_j$。步長可以近似用 $|E_i - E_j|$ 來度量。直覺上如果兩個乘子對應的誤差相差很大說明它們對模型當前位置的“不滿意程度”差異很大配對更新往往能帶來更大的修正。反之如果兩個誤差幾乎一樣更新可能非常平緩。實現(xiàn)時需要維護一個誤差緩存數(shù)組 $E$每次更新后同步刷新涉及到的誤差這樣內循環(huán)可以在 $O(N)$ 時間內掃一遍找到 $|E_i - E_j|$ 最大的 $j$。如果最大步長候選的更新幅度太小SMO 會退而求其次從所有非邊界樣本中隨機挑一個實在找不到能有效更新的配對就結束當前外層循環(huán)。4.4 誤差緩存和邊界樣本的偏好誤差緩存是 SMO 實現(xiàn)中一個容易被忽略但極其重要的工程細節(jié)。因為內循環(huán)要用到 $E_i$ 和 $E_j$ 的差如果每次現(xiàn)算 $u_i$復雜度是多了一層 $N$ 次核函數(shù)求和內循環(huán)整體代價會變成 $O(N^2)$ 量級得不償失。所以成熟實現(xiàn)一般維護一個 $E$ 數(shù)組只有當某個樣本的 $\alpha$ 被更新過才重新計算它的誤差。上文提到的“先邊界后全局”策略在誤差緩存層面也有意義非邊界樣本的 $\alpha$ 頻繁變動緩存更新有實際價值邊界樣本的 $\alpha$ 基本是 0 或 $C$誤差不太會變可以少花心思。4.5 迭代之間的收斂加速技巧我見過一個很實用的加速技巧在外循環(huán)掃描時記錄當前所有非邊界樣本中“剛剛發(fā)生更新”的樣本集合下一輪優(yōu)先處理它們。因為在 SMO 迭代的中后期大部分樣本已經滿足 KKT 條件反復全量掃描會浪費大量算力只有那些剛被調整過的樣本周圍才最可能還有不滿足條件的鄰居。另一個技巧是給內循環(huán)設置“最大嘗試次數(shù)”。如果連續(xù)多次挑選出的 $j$ 都無法讓 $\alpha_2$ 變化超過閾值就讓內循環(huán)跳出換一個外層變量。這個上限可以避免死循環(huán)也可以理解為一個控制計算預算的開關。5. 容差、C值、收斂判定SMO調參中容易被忽略的細節(jié)5.1 KKT條件的數(shù)值松弛tol的本質嚴格來說SMO 的收斂條件是所有樣本都滿足 KKT 條件。但浮點數(shù)計算有誤差加上 SVM 的 KKT 條件本身是“硬性”的等式不等式直接零容忍判定會永遠無法收斂。所以實現(xiàn)中都會引入一個容差參數(shù) $\text{tol}$。對于一個樣本 $i$KKT 條件的數(shù)值化判定是$$ y_i u_i 1 - \text{tol} \quad \text{且} \quad \alpha_i C \Rightarrow \text{違反} $$$$ y_i u_i 1 \text{tol} \quad \text{且} \quad \alpha_i 0 \Rightarrow \text{違反} $$$\text{tol}$ 的大小直接影響訓練何時停止。太大會導致模型還沒解好就停預測性能下降太小會讓訓練時間暴漲因為最后幾個不符合條件的樣本往往非常頑固。我在實際項目中常用的值是 0.001有時數(shù)據(jù)噪聲比較大時會放寬到 0.01收斂速度會明顯改善分類性能幾乎不掉。5.2 C值對α邊界分布的影響$C$ 是軟間隔中控制“容錯程度”的懲罰系數(shù)。從 SMO 視角看$C$ 直接決定了 $\alpha$ 的取值邊界$\alpha_i$ 被限制在 $[0, C]$ 內。$C$ 越大模型越傾向于讓訓練樣本都滿足間隔條件$\alpha$ 更容易頂?shù)缴辖?$C$出現(xiàn)更多的邊界樣本$C$ 越小模型越寬容$\alpha$ 更容易落在內部或者保持為 0。這也解釋了為什么調參時 $C$ 對模型復雜度影響這么大——它實際上在調節(jié)“有多少樣本成為支持向量”以及“這些支持向量的影響力上限”。5.3 b的選擇策略與多解問題第 3 節(jié)提到了 $b$ 的更新規(guī)則但它背后還有一個更隱蔽的問題當對偶問題存在多個最優(yōu)解時$b$ 的取值不是唯一的。具體來說如果所有 $\alpha$ 都等于 $C$ 或都等于 0沒有任何一個 $\alpha$ 落在 $(0, C)$ 區(qū)間內那么支撐間隔的“自由支持向量”就不存在$b$ 可以在一個范圍內浮動。SMO 里用 $(b_1 b_2)/2$ 作為一種折中但嚴格的數(shù)學做法還需要從全部支持向量對應的 KKT 條件反解 $b$取所有解的中間值。在實踐里如果發(fā)現(xiàn)訓練后的模型在驗證集上表現(xiàn)不穩(wěn)定尤其是界附近的樣本都差不多時可以先檢查一下是不是 $b$ 的選擇不夠合理。5.4 停止條件的判定策略SMO 的標準停止條件是連續(xù)若干輪外循環(huán)都沒有發(fā)生任何 $\alpha$ 更新也就是沒有發(fā)現(xiàn)違反 KKT 條件的樣本就終止迭代。不同實現(xiàn)中也會用“總迭代次數(shù)超過上限”作為保險絲。我個人的經驗是不要把停止條件完全托付給“全部滿足 KKT”。數(shù)據(jù)規(guī)模很大時最后 0.1% 的樣本可能反復出現(xiàn)“輕微違反—更新—又輕微違反”的振蕩如果堅持零違反會白白多跑很多輪。一個實用的做法是記錄上一輪更新的 $\alpha$ 數(shù)量和單次更新的最大變化量當最大變化量低于某個閾值比如 $10^{-5}$時就提前停止效果幾乎不受影響。5.5 超參數(shù)組合在真實數(shù)據(jù)上的表現(xiàn)下面這張表是我在幾個不同類型的模擬數(shù)據(jù)集上跑簡化版 SMO 的粗略感受供參考場景Ctol迭代輪數(shù)收斂卡點線性可分數(shù)據(jù)10.001少無明顯卡點高噪聲數(shù)據(jù)0.10.01中噪聲樣本反復違反 KKT高維稀疏數(shù)據(jù)100.001中邊界樣本數(shù)量大掃描耗時長近似線性相關數(shù)據(jù)1000.0001多$\eta$ 接近 0更新幅度小而頻繁這些數(shù)字不是絕對標準但能說明一個問題SMO 的收斂行為和數(shù)據(jù)本身的幾何結構強相關調整超參數(shù)時必須結合數(shù)據(jù)特點來做而不是機械套固定值。6. 一個簡化版SMO的實現(xiàn)從偽代碼到Python核心邏輯6.1 數(shù)據(jù)結構與核矩陣計算的取舍寫簡化版 SMO 時第一個要決定的是要不要緩存核矩陣。全緩存空間大但每次迭代訪問快完全不緩存每次現(xiàn)算內循環(huán)掃描 $j$ 的時候復雜度會飆到 $O(N^2)$。折中方案是只緩存當前外層變量和其他樣本的核函數(shù)值內循環(huán)掃描時反復用這一列這樣時間可控內存占用也只有 $O(N)$。我下面的示例為了可讀性每次直接用核函數(shù)現(xiàn)算數(shù)據(jù)量大時你需要自己加緩存原理是相通的。6.2 主循環(huán)的邏輯主循環(huán)就是一個“外循環(huán) 內循環(huán)”的嵌套結構外循環(huán)遍歷樣本挑選違反 KKT 條件的 $\alpha_i$。內循環(huán)選擇配對 $\alpha_j$計算解析更新。如果發(fā)生更新同步更新 $b$ 和誤差緩存。連續(xù)多輪無更新則停止。下面是核心邏輯的 Python 風格示意重點看結構不要直接拿來跑大規(guī)模數(shù)據(jù)import numpy as np def smo_simple(X, y, C, tol, max_passes, kernel): m X.shape[0] alpha np.zeros(m) b 0.0 passes 0 # 簡化版每輪都全量重算誤差不額外緩存 E np.array([predict(X, y, alpha, b, kernel, X[i]) - y[i] for i in range(m)]) # 實際建議用增量更新誤差緩存 def g(i): return np.sum(alpha * y * kernel(X, X[i])) b # 需要矩陣化加速 while passes max_passes: num_changed 0 for i in range(m): Ei E[i] # 檢查第 i 個樣本是否違反 KKT if (y[i] * Ei -tol and alpha[i] C) or (y[i] * Ei tol and alpha[i] 0): # 內循環(huán)選 |Ei - Ej| 最大的 j diff np.abs(E - Ei) diff[i] -1 j int(np.argmax(diff)) Ej E[j] alpha_i_old, alpha_j_old alpha[i], alpha[j] # 計算 L 和 H if y[i] y[j]: L max(0, alpha[i] alpha[j] - C) H min(C, alpha[i] alpha[j]) else: L max(0, alpha[j] - alpha[i]) H min(C, C alpha[j] - alpha[i]) if L H: continue eta kernel(X[i], X[i]) kernel(X[j], X[j]) - 2 * kernel(X[i], X[j]) if eta 0: continue alpha_j_new alpha[j] y[j] * (Ei - Ej) / eta alpha_j_new min(H, max(L, alpha_j_new)) if abs(alpha_j_new - alpha[j]) 1e-5: continue alpha[i] y[i] * y[j] * (alpha[j] - alpha_j_new) alpha[j] alpha_j_new # 更新 b b1 b - Ei - y[i] * (alpha[i] - alpha_i_old) * kernel(X[i], X[i]) \ - y[j] * (alpha[j] - alpha_j_old) * kernel(X[i], X[j]) b2 b - Ej - y[i] * (alpha[i] - alpha_i_old) * kernel(X[i], X[j]) \ - y[j] * (alpha[j] - alpha_j_old) * kernel(X[j], X[j]) if 0 alpha[i] C: b b1 elif 0 alpha[j] C: b b2 else: b (b1 b2) / 2 # 全量重算誤差簡化版才這么干 for k in range(m): E[k] g(k) - y[k] num_changed 1 if num_changed 0: passes 1 else: passes 0 return alpha, b這個簡化版忽略了核矩陣緩存、內循環(huán)最大嘗試次數(shù)、非邊界樣本優(yōu)先掃描等加速手段但邏輯是完整可跑的。6.3 解析解、裁剪與b更新代碼里 $\alpha_j^{new}$ 的更新公式、$L$ 和 $H$ 的裁剪、$b_1$、$b_2$ 的更新和前面推導的公式完全對應。寫代碼時最容易出錯的地方是更新 $\alpha_i$ 的公式里符號搞反。這里有一個驗證技巧更新完之后檢查 $\sum \alpha_i y_i$ 是否保持不變。我在調試時曾經加了一行斷言立刻抓到了符號錯誤。如果你自己寫建議保留類似的檢查直到代碼穩(wěn)定。6.4 玩具數(shù)據(jù)上的跑通與驗證在二維平面生成兩類線性可分的數(shù)據(jù)用高斯核跑一遍簡化版 SMO可以直觀看到支持向量浮現(xiàn)出來。收斂后$\alpha$ 中大部分是 0只有少量樣本的 $\alpha$ 不為 0這些正好是離分類邊界最近的點。用這個結果畫分類邊界和間隔線你會發(fā)現(xiàn)這類可視化往往能幫助理解 SVM 模型的實際行為。很多初學者只看到分類邊界忽略間隔線上的支持向量真正畫出散點圖后才能直觀明白“為什么少數(shù)樣本就決定了整個模型”。7. 我在實際訓練SMO時踩過的坑與調試心得7.1 誤差緩存不同步導致收斂慢得離譜我第一次按教程寫 SMO 時最讓人困惑的現(xiàn)象是目標函數(shù)明明在下降但收斂輪數(shù)比預期多了幾十倍。排查了很久才發(fā)現(xiàn)問題出在誤差緩存沒有即時更新。當時我在更新 $\alpha_i$ 和 $\alpha_j$ 后只重算了這兩個樣本的誤差其他樣本的誤差還留在舊值。SMO 的內循環(huán)用 $|E_i - E_j|$ 選配對樣本如果其他樣本的誤差停留在舊狀態(tài)選擇就會被誤導老是選中一些已經不需要更新的樣本。這類問題比較隱蔽因為代碼不會報錯只是性能異常。教訓是涉及誤差緩存時寧可多算一點也要保證一致性。7.2 eta很小的時候如何處理高斯核下如果兩個樣本完全一樣或者高度相似$\eta K_{11} K_{22} - 2K_{12}$ 會趨近于 0此時 $\alpha_2^{new}$ 的更新公式分母接近 0一除就得到極大的值裁剪之后可能變成邊界值但這不代表真實最優(yōu)。我見過直接用 $\eta 0$ 跳過更新的實現(xiàn)這其實不太夠。更穩(wěn)的做法是當 $\eta$ 小于某個閾值比如 $10^{-12}$時直接比較目標函數(shù)在 $L$ 和 $H$ 兩個端點處的值選一個目標值更大的方向走而不是粗暴跳過。這樣既不崩潰也不會丟掉真正有效的更新機會。7.3 停止條件設置過嚴導致過擬合有一段時間我在一個比較小的模擬數(shù)據(jù)集上調 SMO把 tol 設成了 $10^{-5}$結果模型在訓練集上表現(xiàn)很好驗證集上反而變差。原因很簡單SMO 在解對偶問題tol 越小解越逼近數(shù)學意義上的最優(yōu)但在數(shù)據(jù)本身有噪聲的情況下這個“最優(yōu)”反而過度擬合了訓練數(shù)據(jù)。后來我調整了思路把 tol 看作一個正則化尺度的一部分而不是單純的控制收斂精度。項目里處理噪聲較多的數(shù)據(jù)時用較大的 tol 配合合適的 $C$模型泛化性能通常更穩(wěn)。7.4 核函數(shù)數(shù)值范圍導致的梯度消失問題這個坑跟 SMO 本身無關但會讓一切調試無從下手。如果使用多項式核或者 sigmoid 核特征數(shù)值范圍差異很大時核矩陣的元素可能膨脹到 $10^{20}$ 或者縮小到 $10^{-20}$隨之 $\eta$ 和誤差更新都發(fā)生數(shù)值溢出。處理方式是先對特征做標準化再選核函數(shù)。我習慣在進入 SMO 之前先做一次 min-max 標準化核函數(shù)里再根據(jù)數(shù)據(jù)規(guī)模調一下參數(shù)。很多人在這上面花過大量時間結果最后發(fā)現(xiàn)是數(shù)據(jù)預處理的問題。7.5 工程實現(xiàn)上的其他實用建議最后整理一些偏工程向的建議雖然不復雜但每個都能幫你省不少時間核函數(shù)計算寫成矩陣形式至少在選內循環(huán)配對樣本時用向量化不然純 Python 循環(huán)會慢到懷疑人生。內循環(huán)選擇 $j$ 時把當前 $i$ 的誤差排除在外否則可能出現(xiàn)自己配自己的情況。記錄每次迭代中有多少個 $\alpha$ 發(fā)生了更新連續(xù)幾輪更新數(shù)量遞減是收斂的正常信號如果某輪突然暴漲常見原因是誤差緩存不一致。早停并不是越晚越好。大規(guī)模數(shù)據(jù)上不必等到嚴格 KKT 全滿足用“單次最大變化量低于閾值”來停藥訓練時間和模型質量都很均衡。我自己的使用習慣是先在一個小的子集上把 SMO 跑通再上全量數(shù)據(jù)避免把調試時間浪費在等待上。SMO 雖然看起來只是 SVM 的內部組件但它把“大問題拆小”這個思想體現(xiàn)得淋漓盡致很多人看完它之后再去看其他分解類優(yōu)化方法都會有一種觸類旁通的感覺。如果你正準備深入學習支持向量機或者優(yōu)化算法親手實現(xiàn)一遍 SMO 絕對是最值回票價的一件事。 拆解SMO算法：從凸二次規(guī)劃到雙變量解析更新的全程推導
提起 SMO很多人的第一印象是“SVM 庫內部那個優(yōu)化器”——調包調久了接口后面發(fā)生了什么很少有人細看。但序列最小最優(yōu)化算法SMO值得每一個做機器學習的人認真拆一遍它把一個大到近乎無解的二次規(guī)劃問題拆成無數(shù)個只包含兩個變量的子問題而且每個子問題都能用解析公式直接算出不需要任何數(shù)值優(yōu)化庫。這個設計在今天看來依然非常聰明理解它之后你會對 SVM 的訓練過程、支持向量的含義、甚至調參時那些“說不清但確實有效”的經驗有完全不一樣的感覺。這篇文章不準備從零堆數(shù)學公式而是順著 SMO 的求解思路走一遍先從 SVM 訓練為什么難解講起再拆 SMO 的核心機制、兩個乘子的解析求解、啟發(fā)式選擇策略、收斂判定細節(jié)最后給一份可以照著改的 Python 簡化實現(xiàn)以及我在實際調試中踩過的坑。適合想搞懂 SMO 內部邏輯的學生、面試被問到 SMO 細節(jié)的求職者以及想手動實現(xiàn)一遍而不是只調庫的工程師。1. 為什么SVM訓練必須拆成小問題一個被核矩陣卡死的優(yōu)化困境1.1 從分類超平面到凸二次規(guī)劃SVM 的分類思路是找一個間隔最大的超平面。線性可分情況下這個超平面要滿足所有點都被正確分開同時離它最近的點要盡可能遠。數(shù)學上這個問題等價于最小化 $\frac{1}{2}||w||^2$約束是 $y_i(w^T x_i b) \ge 1$。但現(xiàn)實數(shù)據(jù)幾乎都不是線性可分的于是引入松弛變量 $\xi_i$ 和懲罰系數(shù) $C$把目標改成$$ \min_{w,b,\xi} \frac{1}{2}||w||^2 C\sum_{i1}^{N}\xi_i $$加上約束 $y_i(w^T x_i b) \ge 1 - \xi_i$、$\xi_i \ge 0$ 之后用拉格朗日乘子法轉成對偶問題就會得到下面這個形式$$ \max_{\alpha} W(\alpha) \sum_{i1}^{N}\alpha_i - \frac{1}{2}\sum_{i1}^{N}\sum_{j1}^{N}\alpha_i \alpha_j y_i y_j K(x_i, x_j) $$約束條件有三個$\alpha_i \ge 0$、$\alpha_i \le C$、$\sum_{i1}^{N}\alpha_i y_i 0$。這里的 $K(x_i, x_j)$ 是核函數(shù)也就是把原始特征映射到高維空間后的內積。SMO 就是在解這個對偶問題——準確說是在解這個帶約束的凸二次規(guī)劃QP問題。1.2 標準QP方法的內存噩夢如果從來沒親手解過 SVM 的對偶問題你可能會說這很簡單啊找個現(xiàn)成的 QP 求解器丟進去不就好了理論上確實如此但一算復雜度就發(fā)現(xiàn)問題了。對偶目標函數(shù)中有一個 $\alpha_i \alpha_j K(x_i, x_j)$ 的求和項這意味著我們需要一個 $N \times N$ 的核矩陣 $K$。當訓練樣本有 1000 個時核矩陣是 1000×1000存下來大約 8MB當樣本數(shù)到 1 萬就是 800MB到 10 萬80GB直接內存爆炸。即便你把矩陣稀疏化處理或分塊迭代標準的數(shù)值優(yōu)化方法每一次迭代都要做矩陣運算代價依然高得離譜。這就是 SVM 在早期很難大規(guī)模落地的原因。我記得以前在某高校實驗室跑一個模擬項目數(shù)據(jù)量只有小幾萬直接用內點法求解對偶問題內存就吃到了好幾個 G而且收斂非常慢。后來換了基于分解思想的優(yōu)化器訓練時間從幾十分鐘直接降到了幾分鐘這就是 SMO 這類算法存在的意義。1.3 SMO的做法把大問題切成“一口能吃下去”的小塊SMO 的想法很直接既然一次性解 $N$ 個 $\alpha$ 代價太大那就一次只解其中的一小部分。它每次選擇一個工作集只對這些 $\alpha$ 做優(yōu)化固定其他所有 $\alpha$然后在子問題上求出解析解。關鍵點在于SMO 選的工作集大小是 2。為什么不能是 1因為約束 $\sum_i \alpha_i y_i 0$ 把整個 $\alpha$ 向量綁在了一個超平面上如果只動一個 $\alpha_i$約束瞬間就破壞了必須同時動另一個 $\alpha_j$ 來“補償”它。所以 2 是保持等式約束可行的最小單位。每優(yōu)化兩個 $\alpha$SMO 只需要計算對應的核函數(shù)值不需要存儲整個核矩陣。那些核函數(shù)值可以實時算也可以緩存一部分?？臻g復雜度從 $O(N^2)$ 降到了 $O(N)$這是 SMO 能處理大規(guī)模數(shù)據(jù)的最根本原因。2. 為什么每次只動兩個拉格朗日乘子約束下的最小自由度2.1 單變量更新為何走不通很多第一次接觸坐標下降法的人會想那我挨個 $\alpha_i$ 更新不就行了每次固定其他變量只優(yōu)化一個這就是經典的坐標下降法。但 SVM 對偶問題里的等式約束 $\sum_i \alpha_i y_i 0$ 是一道硬墻。假設你固定除 $\alpha_1$ 外的所有 $\alpha$那么 $\alpha_1$ 的值就已經被唯一確定沒有任何可調整空間。同理如果你固定 $\alpha_1, \alpha_3, \alpha_4, \dots$只動 $\alpha_2$$\alpha_2$ 同樣被鎖死。所以單變量子問題在數(shù)學上不可行必須同時更新兩個變量才能有真正的自由度。這也是為什么 SMO 叫“序列最小優(yōu)化”——每次優(yōu)化的子問題規(guī)模是所有滿足約束的最小子問題也就是兩個變量。2.2 兩個變量的組合方式等式約束下的一條線段當只看兩個變量 $\alpha_1$ 和 $\alpha_2$ 的時候等式約束變成$$ y_1 \alpha_1 y_2 \alpha_2 y_1 \alpha_1^{old} y_2 \alpha_2^{old} \text{常數(shù)} $$這條直線在 $(\alpha_1, \alpha_2)$ 平面上是一條斜線再加上 $0 \le \alpha_i \le C$ 的盒子約束可行域就是這條直線穿過盒子后剩下的線段。換句話說無論我們怎么調整$\alpha_1$ 和 $\alpha_2$ 都必須落在這條線段上。一旦確定 $\alpha_2$ 的新值$\alpha_1$ 的新值就被這條直線唯一確定這就是 SMO 解析更新公式的幾何基礎。2.3 SMO與坐標下降法的關系嚴格來說SMO 可以看作坐標下降法在帶等式約束條件下的變體它每次在一個二維坐標平面上做精確的一維搜索但因為約束的存在坐標軸要沿著約束方向“旋轉”一下。我當初學的時候有個直觀的感受坐標下降法就像你在一個有圍欄的山坡上每次都只沿著東西或南北方向走一小步而 SMO 則像是沿著圍欄的方向走每次保證不越界而且每步都能直接走到這個方向的局部最低點。所以 SMO 的收斂速度在多數(shù)情況下是比普通坐標下降快的。2.4 子問題的幾何直覺再往深一層如果 $y_1 y_2$那么等式約束變成 $\alpha_1 \alpha_2 \text{常數(shù)}$可行域是一條斜率為 -1 的線段如果 $y_1 \ne y_2$等式約束變成 $\alpha_1 - \alpha_2 \text{常數(shù)}$可行域是一條斜率為 1 的線段。上下界 $L$ 和 $H$ 就是這條線段兩端被盒子邊界截斷的位置。理解這個幾何關系對后面推導 $L$、$H$ 的公式非常有用。很多教程直接甩兩個 case 的公式讓人背背完就忘理解了截斷原理任何時候都能自己推出來。3. 兩個乘子的解析求解從二次函數(shù)求導到上下界裁剪3.1 拆出與α1、α2相關的目標函數(shù)現(xiàn)在進入 SMO 最核心的數(shù)學部分。我們把對偶目標函數(shù) $W(\alpha)$ 中所有含 $\alpha_1$、$\alpha_2$ 的項單獨拆出來其余項因為在本次迭代中不變可以直接消去。展開后目標函數(shù)是$$ W \alpha_1 \alpha_2 - \frac{1}{2} \alpha_1^2 K_{11} - \frac{1}{2} \alpha_2^2 K_{22} - \alpha_1 \alpha_2 y_1 y_2 K_{12} $$ $$y_1 \alpha_1 \sum_{i\ne 1}\alpha_i y_i K_{i1} - y_2 \alpha_2 \sum_{i\ne 2}\alpha_i y_i K_{i2} \text{常數(shù)項} $$其中 $K_{ij} K(x_i, x_j)$常數(shù)項包含所有與 $\alpha_1$、$\alpha_2$ 無關的部分。由于 $\alpha_1$ 和 $\alpha_2$ 由等式約束綁定我們只需優(yōu)化 $\alpha_2$ 一個變量$\alpha_1$ 是它的函數(shù)。3.2 用等式約束消掉α1令 $s y_1 y_2$等式約束可以寫成$$ \alpha_1 s \alpha_2 \alpha_1^{old} s \alpha_2^{old} \gamma $$于是$$ \alpha_1 \gamma - s \alpha_2 $$把 $\alpha_1$ 代入 $W$目標函數(shù)就變成只關于 $\alpha_2$ 的一元二次函數(shù)。到這里問題已經轉化成了高中生的求拋物線極值問題只是別忘了后面還有 $[0, C]$ 的邊界約束。3.3 解析更新公式的推導對一元二次函數(shù)求導并令導數(shù)為 0可以得到未裁剪的 $\alpha_2$ 新值公式$$ \alpha_2^{new, unc} \alpha_2^{old} \frac{y_2(E_1 - E_2)}{\eta} $$其中 $E_i u_i - y_i$ 是第 $i$ 個樣本的預測誤差$u_i \sum_j \alpha_j y_j K(x_j, x_i) b$ 是當前模型對第 $i$ 個樣本的預測輸出$\eta K_{11} K_{22} - 2K_{12}$。很多資料里符號跟我這里不太一樣原因在于 $E_i$ 的定義究竟是“預測減真值”還是“真值減預測”。我建議統(tǒng)一用“預測減真值”來記憶推導過程會更順。如果你看到別處的公式符號相反不要慌檢查一下它的 $E$ 定義。$\eta$ 的物理含義是兩個樣本在核函數(shù)映射后的距離平方的一半嚴謹?shù)卣f$\eta ||\phi(x_1) - \phi(x_2)||^2$它衡量了兩個樣本在特征空間中的距離。$\eta$ 越小說明兩個樣本在特征空間里越接近更新的步長就越大$\eta$ 接近 0 時解析解的分母趨近 0這種情況需要單獨處理。3.4 可行域裁剪L和H的計算未裁剪的解不一定落在可行域內必須把它裁剪到線段 $[L, H]$ 上。$L$ 和 $H$ 的計算邏輯如下當 $y_1 y_2$ 時$$ L \max(0, \alpha_1^{old} \alpha_2^{old} - C), \quad H \min(C, \alpha_1^{old} \alpha_2^{old}) $$當 $y_1 \ne y_2$ 時$$ L \max(0, \alpha_2^{old} - \alpha_1^{old}), \quad H \min(C, C \alpha_2^{old} - \alpha_1^{old}) $$裁剪得到$$ \alpha_2^{new} \begin{cases} H, \alpha_2^{new, unc} H \ \alpha_2^{new, unc}, L \le \alpha_2^{new, unc} \le H \ L, \alpha_2^{new, unc} L \end{cases} $$然后由 $\alpha_1 \gamma - s \alpha_2$ 反解出$$ \alpha_1^{new} \alpha_1^{old} s(\alpha_2^{old} - \alpha_2^{new}) $$3.5 更新b和誤差的時機$\alpha$ 更新完之后$b$ 也必須同步更新否則模型輸出 $u_i$ 仍然是舊的后續(xù)迭代誤差全都會錯。$b$ 的更新依賴當前 $\alpha$ 的變化量和新舊核值$$ b_1 b - E_1 - y_1(\alpha_1^{new} - \alpha_1^{old})K_{11} - y_2(\alpha_2^{new} - \alpha_2^{old})K_{12} $$$$ b_2 b - E_2 - y_1(\alpha_1^{new} - \alpha_1^{old})K_{12} - y_2(\alpha_2^{new} - \alpha_2^{old})K_{22} $$選擇規(guī)則是若 $0 \alpha_1^{new} C$取 $b b_1$否則若 $0 \alpha_2^{new} C$取 $b b_2$若兩者都在邊界上取 $b (b_1 b_2) / 2$。這個選擇規(guī)則并不是拍腦袋定的。當某個 $\alpha$ 嚴格落在 $(0, C)$ 內部意味著該樣本恰好落在間隔邊界上它對應的 KKT 條件要求 $y_i u_i 1$因此 $b$ 有唯一確定值如果兩個 $\alpha$ 都在邊界上說明當前迭代沒有提供足夠的約束信息$b$ 可能落在一個區(qū)間內這時取平均是最穩(wěn)妥的近似。4. 啟發(fā)式選擇策略決定SMO收斂速度的分水嶺4.1 盲目選擇第一個乘子的代價理論上只要每輪都找一個違反 KKT 條件的乘子對并做一次解析更新SMO 就一定會收斂。但如果每次隨機選收斂速度會慢到讓人崩潰。原因在于隨機選擇的兩點可能已經在最優(yōu)值附近更新幅度極小甚至在邊界上連動都不能動白白浪費大量計算。實際工程中選的好不好對迭代次數(shù)的影響是數(shù)量級的差異——同一個數(shù)據(jù)集上好的選擇策略可能 200 次迭代收斂隨機選擇可能 5000 次都不一定停。4.2 外循環(huán)優(yōu)先尋找違反KKT條件的樣本SMO 的外循環(huán)負責選第一個乘子 $\alpha_i$。它的策略是優(yōu)先遍歷那些違反 KKT 條件最嚴重的樣本。具體做法通常分兩遍走第一遍遍歷所有非邊界樣本也就是 $0 \alpha_i C$ 的那部分。為什么優(yōu)先它們因為這些樣本恰好落在間隔邊界上它們對模型的影響最直接也最容易被 KKT 條件判定為“不合格”。第二遍才遍歷全部樣本。如果第一遍把所有非邊界樣本都檢查完沒有發(fā)現(xiàn)需要更新的乘子再對全部樣本做一次掃描看有沒有漏網之魚。這種“先邊界后全局”的策略可以理解為熟悉的地方先仔細查查不到問題再去整個空間掃一遍。很多實現(xiàn)還會記錄一輪迭代中是否有 $\alpha$ 發(fā)生變化如果有下一輪繼續(xù)優(yōu)先掃描非邊界樣本直到連續(xù)多輪都沒有變化才切換到全局掃描。這個細節(jié)對收斂速度影響非常大。4.3 內循環(huán)基于最大步長原則選擇配對乘子外循環(huán)選好 $\alpha_i$ 之后內循環(huán)負責選第二個乘子 $\alpha_j$。SMO 的目標是找一個和 $\alpha_i$ 配對后能產生最大“步長”的 $\alpha_j$。步長可以近似用 $|E_i - E_j|$ 來度量。直覺上如果兩個乘子對應的誤差相差很大說明它們對模型當前位置的“不滿意程度”差異很大配對更新往往能帶來更大的修正。反之如果兩個誤差幾乎一樣更新可能非常平緩。實現(xiàn)時需要維護一個誤差緩存數(shù)組 $E$每次更新后同步刷新涉及到的誤差這樣內循環(huán)可以在 $O(N)$ 時間內掃一遍找到 $|E_i - E_j|$ 最大的 $j$。如果最大步長候選的更新幅度太小SMO 會退而求其次從所有非邊界樣本中隨機挑一個實在找不到能有效更新的配對就結束當前外層循環(huán)。4.4 誤差緩存和邊界樣本的偏好誤差緩存是 SMO 實現(xiàn)中一個容易被忽略但極其重要的工程細節(jié)。因為內循環(huán)要用到 $E_i$ 和 $E_j$ 的差如果每次現(xiàn)算 $u_i$復雜度是多了一層 $N$ 次核函數(shù)求和內循環(huán)整體代價會變成 $O(N^2)$ 量級得不償失。所以成熟實現(xiàn)一般維護一個 $E$ 數(shù)組只有當某個樣本的 $\alpha$ 被更新過才重新計算它的誤差。上文提到的“先邊界后全局”策略在誤差緩存層面也有意義非邊界樣本的 $\alpha$ 頻繁變動緩存更新有實際價值邊界樣本的 $\alpha$ 基本是 0 或 $C$誤差不太會變可以少花心思。4.5 迭代之間的收斂加速技巧我見過一個很實用的加速技巧在外循環(huán)掃描時記錄當前所有非邊界樣本中“剛剛發(fā)生更新”的樣本集合下一輪優(yōu)先處理它們。因為在 SMO 迭代的中后期大部分樣本已經滿足 KKT 條件反復全量掃描會浪費大量算力只有那些剛被調整過的樣本周圍才最可能還有不滿足條件的鄰居。另一個技巧是給內循環(huán)設置“最大嘗試次數(shù)”。如果連續(xù)多次挑選出的 $j$ 都無法讓 $\alpha_2$ 變化超過閾值就讓內循環(huán)跳出換一個外層變量。這個上限可以避免死循環(huán)也可以理解為一個控制計算預算的開關。5. 容差、C值、收斂判定SMO調參中容易被忽略的細節(jié)5.1 KKT條件的數(shù)值松弛tol的本質嚴格來說SMO 的收斂條件是所有樣本都滿足 KKT 條件。但浮點數(shù)計算有誤差加上 SVM 的 KKT 條件本身是“硬性”的等式不等式直接零容忍判定會永遠無法收斂。所以實現(xiàn)中都會引入一個容差參數(shù) $\text{tol}$。對于一個樣本 $i$KKT 條件的數(shù)值化判定是$$ y_i u_i 1 - \text{tol} \quad \text{且} \quad \alpha_i C \Rightarrow \text{違反} $$$$ y_i u_i 1 \text{tol} \quad \text{且} \quad \alpha_i 0 \Rightarrow \text{違反} $$$\text{tol}$ 的大小直接影響訓練何時停止。太大會導致模型還沒解好就停預測性能下降太小會讓訓練時間暴漲因為最后幾個不符合條件的樣本往往非常頑固。我在實際項目中常用的值是 0.001有時數(shù)據(jù)噪聲比較大時會放寬到 0.01收斂速度會明顯改善分類性能幾乎不掉。5.2 C值對α邊界分布的影響$C$ 是軟間隔中控制“容錯程度”的懲罰系數(shù)。從 SMO 視角看$C$ 直接決定了 $\alpha$ 的取值邊界$\alpha_i$ 被限制在 $[0, C]$ 內。$C$ 越大模型越傾向于讓訓練樣本都滿足間隔條件$\alpha$ 更容易頂?shù)缴辖?$C$出現(xiàn)更多的邊界樣本$C$ 越小模型越寬容$\alpha$ 更容易落在內部或者保持為 0。這也解釋了為什么調參時 $C$ 對模型復雜度影響這么大——它實際上在調節(jié)“有多少樣本成為支持向量”以及“這些支持向量的影響力上限”。5.3 b的選擇策略與多解問題第 3 節(jié)提到了 $b$ 的更新規(guī)則但它背后還有一個更隱蔽的問題當對偶問題存在多個最優(yōu)解時$b$ 的取值不是唯一的。具體來說如果所有 $\alpha$ 都等于 $C$ 或都等于 0沒有任何一個 $\alpha$ 落在 $(0, C)$ 區(qū)間內那么支撐間隔的“自由支持向量”就不存在$b$ 可以在一個范圍內浮動。SMO 里用 $(b_1 b_2)/2$ 作為一種折中但嚴格的數(shù)學做法還需要從全部支持向量對應的 KKT 條件反解 $b$取所有解的中間值。在實踐里如果發(fā)現(xiàn)訓練后的模型在驗證集上表現(xiàn)不穩(wěn)定尤其是界附近的樣本都差不多時可以先檢查一下是不是 $b$ 的選擇不夠合理。5.4 停止條件的判定策略SMO 的標準停止條件是連續(xù)若干輪外循環(huán)都沒有發(fā)生任何 $\alpha$ 更新也就是沒有發(fā)現(xiàn)違反 KKT 條件的樣本就終止迭代。不同實現(xiàn)中也會用“總迭代次數(shù)超過上限”作為保險絲。我個人的經驗是不要把停止條件完全托付給“全部滿足 KKT”。數(shù)據(jù)規(guī)模很大時最后 0.1% 的樣本可能反復出現(xiàn)“輕微違反—更新—又輕微違反”的振蕩如果堅持零違反會白白多跑很多輪。一個實用的做法是記錄上一輪更新的 $\alpha$ 數(shù)量和單次更新的最大變化量當最大變化量低于某個閾值比如 $10^{-5}$時就提前停止效果幾乎不受影響。5.5 超參數(shù)組合在真實數(shù)據(jù)上的表現(xiàn)下面這張表是我在幾個不同類型的模擬數(shù)據(jù)集上跑簡化版 SMO 的粗略感受供參考場景Ctol迭代輪數(shù)收斂卡點線性可分數(shù)據(jù)10.001少無明顯卡點高噪聲數(shù)據(jù)0.10.01中噪聲樣本反復違反 KKT高維稀疏數(shù)據(jù)100.001中邊界樣本數(shù)量大掃描耗時長近似線性相關數(shù)據(jù)1000.0001多$\eta$ 接近 0更新幅度小而頻繁這些數(shù)字不是絕對標準但能說明一個問題SMO 的收斂行為和數(shù)據(jù)本身的幾何結構強相關調整超參數(shù)時必須結合數(shù)據(jù)特點來做而不是機械套固定值。6. 一個簡化版SMO的實現(xiàn)從偽代碼到Python核心邏輯6.1 數(shù)據(jù)結構與核矩陣計算的取舍寫簡化版 SMO 時第一個要決定的是要不要緩存核矩陣。全緩存空間大但每次迭代訪問快完全不緩存每次現(xiàn)算內循環(huán)掃描 $j$ 的時候復雜度會飆到 $O(N^2)$。折中方案是只緩存當前外層變量和其他樣本的核函數(shù)值內循環(huán)掃描時反復用這一列這樣時間可控內存占用也只有 $O(N)$。我下面的示例為了可讀性每次直接用核函數(shù)現(xiàn)算數(shù)據(jù)量大時你需要自己加緩存原理是相通的。6.2 主循環(huán)的邏輯主循環(huán)就是一個“外循環(huán) 內循環(huán)”的嵌套結構外循環(huán)遍歷樣本挑選違反 KKT 條件的 $\alpha_i$。內循環(huán)選擇配對 $\alpha_j$計算解析更新。如果發(fā)生更新同步更新 $b$ 和誤差緩存。連續(xù)多輪無更新則停止。下面是核心邏輯的 Python 風格示意重點看結構不要直接拿來跑大規(guī)模數(shù)據(jù)import numpy as np def smo_simple(X, y, C, tol, max_passes, kernel): m X.shape[0] alpha np.zeros(m) b 0.0 passes 0 # 簡化版每輪都全量重算誤差不額外緩存 E np.array([predict(X, y, alpha, b, kernel, X[i]) - y[i] for i in range(m)]) # 實際建議用增量更新誤差緩存 def g(i): return np.sum(alpha * y * kernel(X, X[i])) b # 需要矩陣化加速 while passes max_passes: num_changed 0 for i in range(m): Ei E[i] # 檢查第 i 個樣本是否違反 KKT if (y[i] * Ei -tol and alpha[i] C) or (y[i] * Ei tol and alpha[i] 0): # 內循環(huán)選 |Ei - Ej| 最大的 j diff np.abs(E - Ei) diff[i] -1 j int(np.argmax(diff)) Ej E[j] alpha_i_old, alpha_j_old alpha[i], alpha[j] # 計算 L 和 H if y[i] y[j]: L max(0, alpha[i] alpha[j] - C) H min(C, alpha[i] alpha[j]) else: L max(0, alpha[j] - alpha[i]) H min(C, C alpha[j] - alpha[i]) if L H: continue eta kernel(X[i], X[i]) kernel(X[j], X[j]) - 2 * kernel(X[i], X[j]) if eta 0: continue alpha_j_new alpha[j] y[j] * (Ei - Ej) / eta alpha_j_new min(H, max(L, alpha_j_new)) if abs(alpha_j_new - alpha[j]) 1e-5: continue alpha[i] y[i] * y[j] * (alpha[j] - alpha_j_new) alpha[j] alpha_j_new # 更新 b b1 b - Ei - y[i] * (alpha[i] - alpha_i_old) * kernel(X[i], X[i]) \ - y[j] * (alpha[j] - alpha_j_old) * kernel(X[i], X[j]) b2 b - Ej - y[i] * (alpha[i] - alpha_i_old) * kernel(X[i], X[j]) \ - y[j] * (alpha[j] - alpha_j_old) * kernel(X[j], X[j]) if 0 alpha[i] C: b b1 elif 0 alpha[j] C: b b2 else: b (b1 b2) / 2 # 全量重算誤差簡化版才這么干 for k in range(m): E[k] g(k) - y[k] num_changed 1 if num_changed 0: passes 1 else: passes 0 return alpha, b這個簡化版忽略了核矩陣緩存、內循環(huán)最大嘗試次數(shù)、非邊界樣本優(yōu)先掃描等加速手段但邏輯是完整可跑的。6.3 解析解、裁剪與b更新代碼里 $\alpha_j^{new}$ 的更新公式、$L$ 和 $H$ 的裁剪、$b_1$、$b_2$ 的更新和前面推導的公式完全對應。寫代碼時最容易出錯的地方是更新 $\alpha_i$ 的公式里符號搞反。這里有一個驗證技巧更新完之后檢查 $\sum \alpha_i y_i$ 是否保持不變。我在調試時曾經加了一行斷言立刻抓到了符號錯誤。如果你自己寫建議保留類似的檢查直到代碼穩(wěn)定。6.4 玩具數(shù)據(jù)上的跑通與驗證在二維平面生成兩類線性可分的數(shù)據(jù)用高斯核跑一遍簡化版 SMO可以直觀看到支持向量浮現(xiàn)出來。收斂后$\alpha$ 中大部分是 0只有少量樣本的 $\alpha$ 不為 0這些正好是離分類邊界最近的點。用這個結果畫分類邊界和間隔線你會發(fā)現(xiàn)這類可視化往往能幫助理解 SVM 模型的實際行為。很多初學者只看到分類邊界忽略間隔線上的支持向量真正畫出散點圖后才能直觀明白“為什么少數(shù)樣本就決定了整個模型”。7. 我在實際訓練SMO時踩過的坑與調試心得7.1 誤差緩存不同步導致收斂慢得離譜我第一次按教程寫 SMO 時最讓人困惑的現(xiàn)象是目標函數(shù)明明在下降但收斂輪數(shù)比預期多了幾十倍。排查了很久才發(fā)現(xiàn)問題出在誤差緩存沒有即時更新。當時我在更新 $\alpha_i$ 和 $\alpha_j$ 后只重算了這兩個樣本的誤差其他樣本的誤差還留在舊值。SMO 的內循環(huán)用 $|E_i - E_j|$ 選配對樣本如果其他樣本的誤差停留在舊狀態(tài)選擇就會被誤導老是選中一些已經不需要更新的樣本。這類問題比較隱蔽因為代碼不會報錯只是性能異常。教訓是涉及誤差緩存時寧可多算一點也要保證一致性。7.2 eta很小的時候如何處理高斯核下如果兩個樣本完全一樣或者高度相似$\eta K_{11} K_{22} - 2K_{12}$ 會趨近于 0此時 $\alpha_2^{new}$ 的更新公式分母接近 0一除就得到極大的值裁剪之后可能變成邊界值但這不代表真實最優(yōu)。我見過直接用 $\eta 0$ 跳過更新的實現(xiàn)這其實不太夠。更穩(wěn)的做法是當 $\eta$ 小于某個閾值比如 $10^{-12}$時直接比較目標函數(shù)在 $L$ 和 $H$ 兩個端點處的值選一個目標值更大的方向走而不是粗暴跳過。這樣既不崩潰也不會丟掉真正有效的更新機會。7.3 停止條件設置過嚴導致過擬合有一段時間我在一個比較小的模擬數(shù)據(jù)集上調 SMO把 tol 設成了 $10^{-5}$結果模型在訓練集上表現(xiàn)很好驗證集上反而變差。原因很簡單SMO 在解對偶問題tol 越小解越逼近數(shù)學意義上的最優(yōu)但在數(shù)據(jù)本身有噪聲的情況下這個“最優(yōu)”反而過度擬合了訓練數(shù)據(jù)。后來我調整了思路把 tol 看作一個正則化尺度的一部分而不是單純的控制收斂精度。項目里處理噪聲較多的數(shù)據(jù)時用較大的 tol 配合合適的 $C$模型泛化性能通常更穩(wěn)。7.4 核函數(shù)數(shù)值范圍導致的梯度消失問題這個坑跟 SMO 本身無關但會讓一切調試無從下手。如果使用多項式核或者 sigmoid 核特征數(shù)值范圍差異很大時核矩陣的元素可能膨脹到 $10^{20}$ 或者縮小到 $10^{-20}$隨之 $\eta$ 和誤差更新都發(fā)生數(shù)值溢出。處理方式是先對特征做標準化再選核函數(shù)。我習慣在進入 SMO 之前先做一次 min-max 標準化核函數(shù)里再根據(jù)數(shù)據(jù)規(guī)模調一下參數(shù)。很多人在這上面花過大量時間結果最后發(fā)現(xiàn)是數(shù)據(jù)預處理的問題。7.5 工程實現(xiàn)上的其他實用建議最后整理一些偏工程向的建議雖然不復雜但每個都能幫你省不少時間核函數(shù)計算寫成矩陣形式至少在選內循環(huán)配對樣本時用向量化不然純 Python 循環(huán)會慢到懷疑人生。內循環(huán)選擇 $j$ 時把當前 $i$ 的誤差排除在外否則可能出現(xiàn)自己配自己的情況。記錄每次迭代中有多少個 $\alpha$ 發(fā)生了更新連續(xù)幾輪更新數(shù)量遞減是收斂的正常信號如果某輪突然暴漲常見原因是誤差緩存不一致。早停并不是越晚越好。大規(guī)模數(shù)據(jù)上不必等到嚴格 KKT 全滿足用“單次最大變化量低于閾值”來停藥訓練時間和模型質量都很均衡。我自己的使用習慣是先在一個小的子集上把 SMO 跑通再上全量數(shù)據(jù)避免把調試時間浪費在等待上。SMO 雖然看起來只是 SVM 的內部組件但它把“大問題拆小”這個思想體現(xiàn)得淋漓盡致很多人看完它之后再去看其他分解類優(yōu)化方法都會有一種觸類旁通的感覺。如果你正準備深入學習支持向量機或者優(yōu)化算法親手實現(xiàn)一遍 SMO 絕對是最值回票價的一件事。