?

導言

用logistic回歸解決二分類問題時，后驗概率\(P(y=1|x;\theta)\)由logistic函數\(h_\theta(x)=g(\theta^Tx)\)給出。當且僅當\(h_\theta(x)\geq 0.5\)也就是\(\theta^Tx\geq 0\)時，我們預測樣本類別標簽\(y=1\)。\(\theta^Tx\)越大，\(h_\theta(x)=g(\theta^Tx)\)越大。因此，當\(\theta^Tx\gg 0\)時，我們很確定預測結果為\(y=1\)；反之，若\(\theta^Tx\ll 0\)，我們認為預測結果為\(y=0\)是最合理的。給定訓練集，若能找到參數\(\theta\)，對所有標簽為\(y^{(i)}=1\)的樣本滿足\(\theta^Tx^{(i)}\gg 0\),且對所有標簽為\(y^{(i)}=-1\)樣本滿足\(\theta^Tx^{(i)}\ll 0\)，那么最終的分類正確率會最高。稍后，我們用函數間隔來形式化這個思想。

以下圖為例，從更直觀的角度簡述另一種思路。圖中紅色的點表示正樣本，綠色的點表示負樣本，藍色直線為\(\theta^Tx=0\)給出的的決策邊界(Decision Boundary)，也稱之為分割超平面(Hyperplane)。圖中樣本C離決策邊界很遠，我們可以很確定樣本C的預測結果為\(y=1\)；樣本A離決策邊界很久，如果決策邊界發生輕微的偏轉，樣本A很可能被劃分到另外一類。對于給定的訓練集，如果我們能找到一條決策邊界，使得所有樣本都盡可能離決策邊界很遠，那么我們的預測結果可信度也會更高。在這里，樣本點與決策面之間的距離衡量標準為幾何間隔。

我們從解決二分類問題的線性分類器著手，逐步深入地介紹SVM。為了便于表述，樣本類別標簽定義為\(y\in\{-1,1\}\)。分類器的參數為\(w\)和\(b\)，形式如下 \begin{equation} h_{w,b}(x)=g(w^Tx+b)= \left\lbrace\begin{array}{cc} +1 & ,w^Tx+b\geq 0\\ -1 & ,w^Tx+b<0 \end{array}\right. \end{equation}由函數定義可知，分類器\(h_{w,b}\)會直接輸出樣本的預測值，而不會經歷logistic回歸中估算\(P(y=1|x)\)的中間步驟。

函數間隔和幾何間隔

給定\(m\)個訓練樣本組成的訓練集\(\mathcal{S}=\{(x^{(i)},y^{(i)});i=1,\cdots,m\}\)。 針對樣本\((x^{(i)},y^{(i)})\)的函數間隔(Functional Margin)為: \begin{equation} \hat{\gamma}^{(i)}=y^{(i)}(W^Tx^{(i)}+b) \end{equation}函數間隔越大意味著我們對預測結果的正確性越有信心。整個訓練集上的函數間隔定義為: \begin{equation} \hat{\gamma}=\min_{i=1,\cdots,m}\hat{\gamma}^{(i)} \end{equation}\(\hat{\gamma}\)也就是支持向量對應函數間隔。 針對樣本\((x^{(i)},y^{(i)})\)的幾何間隔(Geometric Margin)為: \begin{equation} \gamma^{(i)}=\frac{y^{(i)}(W^Tx^{(i)}+b)}{\|w\|}=\frac{\hat{\gamma}^{(i)}}{\|w\|} \end{equation}整個訓練集上的幾何間隔定義為: \begin{equation} \gamma=\min_{i=1,\cdots,m}\gamma^{(i)} \end{equation}\(\gamma\)也就是支持向量對應幾何間隔。

最優間隔分類器

最優間隔分類器(Optimal Margin Classifier)的意圖在于把樣本點和超平面之間最壞情況下的距離最大化，也就是尋找一個最優超平面，使得支持向量離超平面最遠，實現不同類樣本最大限度線性可分。函數間隔只能通過正負號反映分類正確與否，正號表示分類正確，負號表示分類錯誤；而樣本間線性可分程度實際上是由幾何間隔決定的。

1. 最優間隔分類器最直觀的目標函數如下： \begin{equation} \begin{array}{l} \underset{\hat{\gamma},w,b}{\max}\quad \gamma \\ s.t. \quad y^{(i)}(W^Tx^{(i)}+b)\geq\gamma,i=1,\cdots,m \\ \large\qquad \|w\|=1 \end{array} \end{equation}約束條件\(\|w\|=1\)是為了保證函數間隔等于幾何間隔，但該約束把參數空間限定在超球面上，沒有較好的優化方法來求解這類問題。
2. 函數間隔是幾何間隔的\(\|w\|\)倍，利用這層關系將目標函數轉化為如下形式： \begin{equation} \begin{array}{l} \underset{\hat{\gamma},w,b}{\max}\quad \frac{\hat{\gamma}}{\|w\|} \\ s.t. \quad y^{(i)}(W^Tx^{(i)}+b)\geq\hat{\gamma},i=1,\cdots,m \end{array} \end{equation}目標仍然是求訓練集上幾何間隔的最大值，但上一個目標函數的兩個約束條件簡化成了對函數間隔的約束。
3. 幾何間隔對\(\|w\|\)和\(\hat{\gamma}\)具有伸縮不變性。以相同倍數縮放\(\|w\|\)和\(\hat{\gamma}\)，直到\(\hat{\gamma}=1\)，此時幾何間隔保持不變。目標函數進一步簡化為： \begin{equation} \begin{array}{l} \underset{w,b}{\max}\quad \frac{1}{\|w\|} \\ s.t. \quad y^{(i)}(W^Tx^{(i)}+b)\geq 1,i=1,\cdots,m \end{array} \end{equation}
4. 由于\(\max\frac{1}{\|w\|}\rightleftharpoons\min\frac{1}{2}\|w\|^2\)，我們最終得到如下的目標函數： \begin{equation} \begin{array}{l} \underset{w,b}{\min}\quad \frac{1}{2}\|w\|^2 \\ s.t. \quad y^{(i)}(W^Tx^{(i)}+b)\geq 1,i=1,\cdots,m \end{array} \end{equation}

核函數

對于線性不可分的問題，我們也可以通過將數據映射到維度更高的特征空間，部分甚至完全將其解決。如下左圖所示，紅色和綠色所示的正負樣本分別集中在兩個同心圓上，在二維的輸入空間中不可能實現線性可分。但是我們可以很容易找到藍色圓環環所示的超平面，將兩類樣本完美劃分開。二元二次曲線的通式為\(a_1x_1^2+a_2x_2^2+a_3x_1x_2+a_4x_1+a_5x_2+a_6=0\)，也就是說，我們將二維空間中的樣本映射到五維空間，其對應的特征表示由\((x_1,x_2)\)變為\((x_1^2,x_2^2,x_1x_2,x_1,x_2)\)，這樣我們就可以在五維空間中構造相應的超平面將所有樣本劃分開。如下右圖的線性不可分情況較左圖復雜很多，但我還是可以找到紅色曲線所示的分割面，顯然這條紅色曲線需要更高階的多項式來表示。沿用左圖的思想，我們仍然可以將樣本映射到高維空間后實現線性可分。

下圖更為直觀得顯示出了Kernel的神奇之處

?

特征映射(Feature Mapping)函數\(\phi\)將數據\(x\)從輸入空間映射到高維甚至無限維的特征空間中，對應的核函數\(K\)定義如下： \begin{equation} K(x_1,x_2)=<\phi(x_1),\phi(x_2)>=\phi(x_1)^T\phi(x_2) \end{equation}其中，輸入空間的兩個樣本點\(x_1\)和\(x_2\)經過函數\(\phi\)分別被映射到特征空間中的\(\phi(x_1)\)和\(\phi(x_2)\)，\(<\cdot,\cdot>\)表示內積運算。 假設\(x_1=(\eta_1,\eta_2)^T,x_2=(\epsilon_1,\epsilon_2)^T\)，核函數形式為: \begin{equation} \begin{array}{ll} K(x_1,x_2)&=\left(<x_1,x_2>+1\right)^2\\ &=\left((\eta_1\epsilon_1+\eta_2\epsilon_2)+1\right)^2\\ &=(\eta_1\epsilon_1+\eta_2\epsilon_2)^2+2(\eta_1\epsilon_1+\eta_2\epsilon_2)+1\\ &=\eta_1^2\epsilon_1^2+\eta_2^2\epsilon_2^2+2\eta_1\epsilon_1\eta_2\epsilon_2+2\eta_1\epsilon_1+2\eta_2\epsilon_2+1\\ &=<\phi(x_1),\phi(x_2)> \end{array} \end{equation}滿足條件的映射函數\(\phi\)：\(\phi(x_1)=(\eta_1^2,\eta_2^2,\sqrt{2}\eta_1\eta_2,\sqrt{2}\eta_1,\sqrt{2}\eta_2,1)^T\)，\(\phi(x_2)=(\epsilon_1^2,\epsilon_2^2,\sqrt{2}\epsilon_1\epsilon_2,\sqrt{2}\epsilon_1,\sqrt{2}\epsilon_2,1)^T\)。每個核函數必然對應一種映射關系，但并非所有的特征映射函數\(\phi\)都可以很容易求解出來。\(<\phi(x_1),\phi(x_2)>=K(x_1,x_2)\)告訴我們特征空間的內積運算可以在輸入空間通過核函數計算出來，因此根本沒必要知道核函數對應的\(\phi\)。 常見的核函數有如下幾種形式： \begin{equation} \text{線性核函數：}K(x,y)=x^Ty+c \end{equation} \begin{equation} \text{多項式核函數：}K(x,y)=(\alpha x^Ty+c)^d \end{equation} \begin{equation} \text{高斯核函數：}K(x,y)=\exp\left(-\frac{\|x-y\|^2}{2\sigma^2}\right) \end{equation} \begin{equation} \text{Sigmoid核函數：}K(x,y)=\tanh(\alpha x^Ty+c) \end{equation} 有的核函數還可以反應樣本間的相似程度， 比如我們可以選擇高斯核函數： \begin{equation} K(x,y)=\exp\left(-\frac{\|x-y\|^2}{2\sigma^2}\right) \end{equation}若\(x\)與\(z\)極為相似，\(K(x,z)\approx 1\)；反之，若兩者差異很大，\(K(x,z)\approx 0\)。 一個有效的核函數到底有哪些性質呢？給定數據集\(\{x^{(1)},x^{(2)},\cdots,x^{(m)}\}\)，定義在該數據集上\(m\times m\)的核矩陣(Kernel Matrix)為\(K_{ij}=K(x^{(i)},x^{(j)})\)。核矩陣有如下兩條性質：

• 對稱性(Symmetric)。 \begin{equation} K(x_i,x_j)=\langle\phi(x_i),\phi(x_j)\rangle=\langle\phi(x_j),\phi(x_i)\rangle=K(x_j,x_i) \end{equation}
• 半正定(Positive semi-definite)。對任意\(z\in\mathcal{R}^m\)， \begin{align} z^TKz&=\sum_i\sum_jz_iK_{ij}z_j\\ &=\sum_i\sum_jz_i\left(\sum_k \phi_k(x_i)\phi_k(x_j)\right)z_j\\ &=\sum_k\left(\sum_iz_i\phi_k(x_i)\right)\left(\sum_jz_j\phi_k(x_j)\right)\\ &=\sum_k\left(\sum_iz_i\phi_k(x_i)\right)^2\geq 0 \end{align}

核函數有效的充要條件：對于給定的任意數據集\(\{x^{(1)},x^{(2)},\cdots,x^{(m)}\}\)，核矩陣對稱半正定。 核函數的巧妙之處在于樣本在特征空間中的內積運算可以由核函數在維度較低的輸入空間中完成。一方面，我們無需顯示計算出映射函數\(\phi\)；另一方面，可以規避高維空間的內積操作帶來的諸多問題。 那么，什么樣的核函數才是最好的？目前沒有選擇合適核函數的指導性原則。我們只能通過經驗知識針對特定問題選擇性能較優的核函數；或者對多個核函數進行交叉驗證，最終選擇實驗效果最好的核函數。目前，將多個核函數融合形成混合核函數也是一大研究熱點。 實際上，核函數的應用范圍非常廣。只要算法能用內積形式表述，就可以將其替換為核函數，使得算法能在核函數對應的高維空間發揮作用。

軟間隔

我們用下圖所示的例子討論軟間隔問題。在下圖中，如果沒有標號為1和2的兩個樣本點，我們可以找到紅色直線所示間隔最大的分割超平面?，F實不可能那么完美，標號為1的樣本點迫使最優間隔超平面變成藍色直線所在位置，樣本間的間隔變得很??；標號為2的樣本點直接使整個數據集在輸入空間變成線性不可分了。我們注意到，這兩個樣本點離各自所屬的群體都很遠，我們稱這些偏離群體的個別樣本點為離群點(Outliers)。

離群點的存在主要有兩個因素：1)數據集中存在噪聲；2)給定的數據集規模太小，不具有代表性。在實際問題中，噪聲總是存在的。將噪聲點當作正常樣本對待顯然不明智；完全忽略噪聲點也不可取。因為在數據集有限的情況下，這些看似噪聲的數據既可能真的是由于各種差錯而出現的噪聲，也有可能反應了問題的屬性，只是我們碰巧只收集到這類數據中的幾個樣本。我們唯一能確定的就是噪聲點具有諸多不確定性。為了保證模型對噪聲具有較好的魯棒性，就要有容忍噪聲的博大胸懷，部分考慮它們的建議(這其中似乎又蘊藏了深刻的哲理，細細體會)。

為了讓模型在一定程度上考慮離群點的影響，引入松弛變量和懲罰因子，目標函數如下： \begin{equation} \begin{array}{l} \underset{w,b}{\min}\quad \frac{1}{2}\|w\|^2+C\sum_{i=1}^m\epsilon_i\\ s.t. \quad y^{(i)}(W^Tx^{(i)}+b)\geq 1-\epsilon_{i},i=1,\cdots,m\\ \large\qquad \epsilon_i\geq 0,i=1,\cdots,m \end{array} \end{equation}其中\(\epsilon_i\)為松弛變量(slack variable)，表示誤分類的樣本與分割超平面之間的距離，正確分類的樣本對應的松弛變量為0。\(C\)為懲罰因子，表示對離群點的重視程度。

從目標函數可以看出，當\(C\)為\(+\infty\)時，\(\epsilon_i\)必然為0才能使目標函數最小，這意味著那些離群點要被正確劃分到所屬的類別；當\(C=0\)時，離群點對應的\(\epsilon_i\)不會影響目標函數，相當于離群點完全被忽略（如下圖所示）。\(y^{(i)}(w^Tx^{(i)}+b)>0\)說明樣本被正確分類；被誤分類的樣本對應的\(\epsilon_i>1\),但我們不鼓勵誤分類情況的出現，因此在原有的目標函數后加上懲罰項。

    %上圖的Matlab代碼如下：
figure;
load fisheriris
X = [meas(:,1), meas(:,2)];
% Extract the Setosa class
Y = nominal(ismember(species,'setosa'));
% Randomly partitions observations into a training set and a test
% set using stratified holdout
P = cvpartition(Y,'Holdout',0.20);
% Use a linear support vector machine classifier
subplot(1,2,1);
svmStruct = svmtrain(X(P.training,:),Y(P.training),'showplot',true,'boxconstraint',0.01);
C = svmclassify(svmStruct,X(P.test,:),'showplot',true);
errRate = sum(Y(P.test)~= C)/P.TestSize  %mis-classification rate
conMat = confusionmat(Y(P.test),C) % the confusion matrix
title(['C=0.01']);
subplot(1,2,2);
svmStruct = svmtrain(X(P.training,:),Y(P.training),'showplot',true,'boxconstraint',100);
C = svmclassify(svmStruct,X(P.test,:),'showplot',true);
errRate = sum(Y(P.test)~= C)/P.TestSize  %mis-classification rate
conMat = confusionmat(Y(P.test),C) % the confusion matrix
title('C=100')
  

對偶

在前面的章節中，我們一步步導出了SVM的目標函數，那么怎樣求解呢？整個求解的思路基本分為三步：1)定義原優化問題；2)根據原問題導出對偶問題；3)通過求解對偶問題間接求解原問題。 根據目標函數定義拉格朗日函數： \begin{equation} \begin{array}{ll} L(w,b,\epsilon,\alpha,\beta)&=\frac{1}{2}\|w\|^2+C\sum_{i=1}^m\epsilon_i\\ &\quad-\sum_{i=1}^m\alpha_i\left(y^{(i)}(w^Tx^{(i)}+b)+\epsilon_i-1\right)-\sum_{i=1}^m\beta_i\epsilon_i \end{array} \end{equation} \begin{equation} Q_P(w,b,\epsilon)=\underset{\alpha_1\geq 0,\beta_i\geq 0}{\max}L(w,b,\epsilon,\alpha,\beta) \end{equation} \begin{equation} Q_D(\alpha,\beta)=\underset{w,b,\epsilon_i\geq 0}{\min}L(w,b,\epsilon,\alpha,\beta) \end{equation} 原問題(Primal Problem)定義如下： \begin{equation} p^*=\underset{w,b,\epsilon_i\geq 0}{\min}Q_P(w,b,\epsilon) \end{equation} 對偶問題(Dual Problem)定義如下： \begin{equation} d^*=\underset{\alpha_i\geq 0,\beta_i\geq 0}{\max}Q_D(\alpha,\beta) \end{equation} 原問題與對偶問題之間的關系為： \begin{equation} p^*\geq d^* \end{equation} 當且僅當參數滿足KKT條件時，\(p^*=d^*\)。KKT條件如下： \begin{align} \left\lbrace \begin{array}{l} \nabla_w L(W,b,\epsilon,\alpha,\beta)=0\\ \nabla_b L(W,b,\epsilon,\alpha,\beta)=0\\ \nabla_\epsilon L(W,b,\epsilon,\alpha,\beta)=0\\ \alpha_i\geq 0\\ y^{(i)}(w^Tx^{(i)}+b)+\epsilon_i-1\geq 0\\ \alpha_i\left(y^{(i)}(w^Tx^{(i)}+b)+\epsilon_i-1\right)=0\\ \beta_i\geq 0\\ \epsilon_i\geq 0\\ \beta_i\epsilon_i=0 \end{array} \right. \end{align} 將拉格朗日函數對參數\(w,b,\epsilon\)的偏導設置為0： \begin{equation} \nabla_w L(w,b,\epsilon,\alpha,\beta)=w-\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}=0\Rightarrow w=\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)} \end{equation} \begin{equation} \nabla_b L(w,b,\epsilon,\alpha,\beta)=-\sum_{i=1}^m\alpha_iy^{(i)}=0\Rightarrow \sum_{i=1}^m\alpha_iy^{(i)}=0 \end{equation} \begin{equation} \nabla_{\epsilon_i}L(w,b,\epsilon,\alpha,\beta)=C-\alpha_i-\beta_i=0\Rightarrow \alpha_i+\beta_i=C \end{equation} 將上述三個結論帶入拉格朗日函數： \begin{equation} \begin{array}{cl} &L(w,b,\epsilon,\alpha,\beta)\\ &=\frac{1}{2}\left(\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}\right)^T\left(\sum_{j=1}^m\alpha_jy^{(j)}x^{(j)}\right) +C\sum_{i=1}^m\epsilon_i\\ &\quad-\sum_{i=1}^m\alpha_iy^{(i)}\left(\sum_{j=1}^m\alpha_jy^{(j)}x^{(j)}\right)^Tx^{(i)}-b\sum_{i=1}^m\alpha_iy^{(i)}\\ &\quad-\sum_{i=1}^m\alpha_i\epsilon_i+\sum_{i=1}^m\alpha_i-\sum_{i=1}^m\beta_i\epsilon_i\\ &=\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy^{(i)}y^{(j)}\langle x^{(i)},x^{(j)}\rangle+C\sum_{i=1}^m\epsilon_i\\ &\quad-\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy^{(i)}y^{(j)}\langle x^{(i)},x^{(j)}\rangle-b\sum_{i=1}^m\alpha_iy^{(i)}\\ &\quad-\sum_{i=1}^m(\alpha_i+\beta_i)\epsilon_i+\sum_{i=1}^m\alpha_i\\ &=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy^{(i)}y^{(j)}\langle x^{(i)},x^{(j)}\rangle\\ &=W(\alpha) \end{array} \end{equation} 我們可以根據\(h_{w,b}(x)\)預測樣本的類別： \begin{equation} h_{w,b}(x)=g(w^Tx+b)=g(\sum_{i=1}^m\alpha_iy^{(i)}\langle x^{(i)},x\rangle+b) \end{equation} 由\(w=\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}\)知，真正對\(w\)具有決定權的樣本對應的拉格朗日乘子\(\alpha_i\)不為0；又根據KKT條件中的\(\alpha_i\left(y^{(i)}(w^Tx^{(i)}+b)+\epsilon_i-1\right)=0\)，必然有\(\left(y^{(i)}(w^Tx^{(i)}+b)+\epsilon_i-1\right)=0\),而滿足該條件的僅包括支持向量和被誤分類的樣本。根據函數\(h_{w,b}(x)\)，真正參與后期分類任務的樣本同樣只涉及到支持向量和被誤分類的樣本。支持向量和誤分類的樣本在整個數據集中的所占的比例往往非常小，一旦支持向量機在特定數據集上訓練好后，我們只需要保留支持向量和被誤分類的樣本即可。如此以來，即使訓練集有上百萬個訓練樣本，我們最終需要保留下來的可能只有幾百個樣本，SVM的效率之高由此可見一斑！ 在\(W(\alpha)\)和\(h_{w,b}(x)\)中，都涉及到內積運算，我們在后面的討論中會直接引入核函數，用\(K_{ij}\)替換\(\langle x^{(i)},x^{(j)}\rangle\)。 此外，結合KKT條件和\(\alpha_i+\beta_i=C\)，我們還可以推導出在后面的順序最小優化中會用到的三個結論：

1. 當\(\alpha_i=0\)時，\(y^{(i)}(w^Tx^{(i)}+b)\geq 1\)，證明如下： \begin{align*} \begin{array}{l} \text{因為}?\alpha_i=0,\alpha_i+\beta_i=C\\ \text{所以}??\beta_i=C\\ \text{因為}?\beta_i\epsilon_i=0\\ \text{所以}??\epsilon_i=0\\ \text{因為}?y^{(i)}(w^Tx^{(i)}+b)+\epsilon_i-1\geq 0\\ \text{所以}??y^{(i)}(w^Tx^{(i)}+b)\geq 1 \end{array} \end{align*}
2. 當\(\alpha_i=C\)時，\(y^{(i)}(w^Tx^{(i)}+b)\leq 1\)，證明如下： \begin{align*} \begin{array}{l} \text{因為}?\alpha_i=C,\alpha_i+\beta_i=C\\ \text{所以}??\beta_i=0\\ \text{因為}?\beta_i\epsilon_i=0,\epsilon_i\geq 0\\ \text{所以}??\epsilon_i\geq 0\\ \text{因為}?\alpha_i\left(y^{(i)}(w^Tx^{(i)}+b)+\epsilon_i-1\right)=0\\ \text{所以}??y^{(i)}(w^Tx^{(i)}+b)+\epsilon_i-1=0\\ \text{所以}??y^{(i)}(w^Tx^{(i)}+b)=1-\epsilon_i\leq 1 \end{array} \end{align*}
3. 當\(0< \alpha_i < C\)時，\(y^{(i)}(w^Tx^{(i)}+b)=1\)，證明如下： \begin{align*} \begin{array}{l} \text{因為} 0< \alpha_i < C,\alpha_i+\beta_i=C\\ \text{所以} 0< \beta_i < C\\ \text{因為}?\beta_i\epsilon_i=0\\ \text{所以}??\epsilon_i=0\\ \text{因為}?\alpha_i\left(y^{(i)}(w^Tx^{(i)}+b)+\epsilon_i-1\right)=0\\ \text{所以}??y^{(i)}(w^Tx^{(i)}+b)+\epsilon_i-1=0\\ \text{所以}??y^{(i)}(w^Tx^{(i)}+b)=1 \end{array} \end{align*}

順序最小優化

我們先引入坐標上升(Coordinate Ascent)算法，然后由此引出順序最小優化(Sequential Minimal Optimization,SMO)算法。坐標上升要解決的優化問題形式如下： \begin{equation} \underset{\alpha}{\max} W(\alpha_1,\alpha_2,\cdots,\alpha_m) \end{equation}優化規則概括為:1)固定除了\(\alpha_i\)之外的所有其他參數；2)搜尋使\(W\)最優的參數\(\alpha_i\)；3)按照\(\alpha_1,\alpha_2,\cdots,\alpha_m\)的順序不斷重復前兩步直到收斂。下圖是該算法的優化示意圖，其中藍色的折線為向前移動的軌跡，每次移動的軌跡都與坐標軸平行，因為每次只更新了一個參數。

對有多個參數的優化問題，我們不必每次都按照固定的順序逐個優化參數，可以嘗試優先選擇對問題的優化貢獻最大的參數。

回到順序最小優化算法上來，這里的最小指的是每次用最少的參數進行優化。我們面臨的對偶問題如下： \begin{equation} \begin{array}{l} \underset{\alpha}{\max} W(\alpha)=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy^{(i)}y^{(j)}\langle x^{(i)},x^{(j)}\rangle \\ s.t. \quad \sum_{i=1}^m\alpha_iy^{(i)}=0 \\ \large\qquad 0\leq\alpha_i\leq C,i=1,\cdots,m \end{array} \end{equation} 這里的等式約束\(\sum_{i=1}^m\alpha_iy^{(i)}=0\)使得坐標上升算法不能直接用于優化對偶問題。如果我們固定除\(\alpha_i\)外的所有參數，由于等式關系的存在，\(\alpha_i\)也就成為被固定的常數而不是可以優化的變量。如果要利用坐標上升的思想解決這個優化問題，必須選擇至少兩個參數作為變量，并固定其他所有參數，然后同時優化選出的參數。SMO算法的思想與坐標上升基本一致：1)用啟發式方法選擇一對參數\(\alpha_i,\alpha_j\)，這對參數使目標函數以最快的速度靠近全局最優值；2)針對參數\(\alpha_i,\alpha_j\)優化目標函數\(W(\alpha)\)，并固定其他所有參數；3)不斷重復前兩步直至收斂。 不失一般性，任意選擇一對參數\(\alpha_1,\alpha_2\)作為變量，并固定其他所有參數。由等式約束得到下式： \begin{equation} \alpha_1y^{(1)}+\alpha_2y^{(2)}=-\sum_{i=3}^m\alpha_ky^{(k)}=\zeta\Rightarrow \alpha_1+y^{(1)}y^{(2)}\alpha_2=y^{(1)}\zeta \end{equation}\(\alpha_1,\alpha_2\)需要滿足的約束條件為\(0\leq\alpha_1\leq C,0\leq\alpha_2\leq C\),也就是\(\alpha_1,\alpha_2\)的參數空間被固定在一個矩形框中，稱這種約束為"Box Constraint"。 前面已經說過，\(y^{(i)}\in\{-1,1\}\)，當\(y^{(1)},y^{(2)}\)取不同值時會影響參數的范圍。下面分兩種情況討論參數的上下界。

• 若\(y^{(1)}\cdot y^{(2)}=-1\)，有\(\alpha_1-\alpha_2=t\)，那么可能有下圖所示的兩種情況：

　　\(\alpha_2\)的上下界形式如下： \begin{equation} \begin{array}{l} H=\min(C,C+\alpha_2-\alpha_1)\\ L=\max(0,\alpha_2-\alpha_1) \end{array} \end{equation}

• 若\(y^{(1)}\cdot y^{(2)}=1\)，有\(\alpha_1+\alpha_2=t\)，那么也可能有下圖所示的兩種情況：

　　\(\alpha_2\)的上下界形式如下： \begin{equation} \begin{array}{l} H=\min(C,\alpha_1+\alpha_2)\\ L=\max(0,\alpha_1+\alpha_2-C) \end{array} \end{equation}

若將除\(\alpha_1,\alpha_2\)之外的所有參數固定，則\(W(\alpha)\)可視為關于\(\alpha_1,\alpha_2\)的函數： \begin{equation} \begin{array}{ll} &\quad W(\alpha_1,\alpha_2)\\ &=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy^{(i)}y^{(j)}K_{ij}\\ &=\alpha_1+\alpha_2+\sum_{i=3}^m\alpha_i\\ &\quad -\frac{1}{2}\sum_{i=1}^m\left(\sum_{j=1}^2y^{(i)}y^{(j)}\alpha_i\alpha_jK_{ij}+\sum_{j=3}^my^{(i)}y^{(j)}\alpha_i\alpha_jK_{ij}\right)\\ &=\alpha_1+\alpha_2+\sum_{i=3}^m\alpha_i\\ &\quad -\frac{1}{2}\sum_{i=1}^2\left(\sum_{j=1}^2y^{(i)}y^{(j)}\alpha_i\alpha_jK_{ij}+\sum_{j=3}^my^{(i)}y^{(j)}\alpha_i\alpha_jK_{ij}\right)\\ &\quad-\frac{1}{2}\sum_{i=3}^m\left(\sum_{j=1}^2y^{(i)}y^{(j)}\alpha_i\alpha_jK_{ij}+\sum_{j=3}^my^{(i)}y^{(j)}\alpha_i\alpha_jK_{ij}\right)\\ &=\alpha_1+\alpha_2+\sum_{i=3}^m\alpha_i-\frac{1}{2}\sum_{i=1}^2\sum_{j=1}^2y^{(i)}y^{(j)}\alpha_i\alpha_jK_{ij}\\ &\quad -\sum_{i=1}^2\sum_{j=3}^my^{(i)}y^{(j)}\alpha_i\alpha_jK_{ij}-\frac{1}{2}\sum_{i=3}^m\sum_{j=3}^my^{(i)}y^{(j)}\alpha_i\alpha_jK_{ij} \end{array} \end{equation} 令\(V_i=\sum_{j=3}^my{(j)}\alpha_jK_{ij}\)，則上式簡化為： \begin{equation} \begin{array}{ll} W(\alpha_1,\alpha_2)&=\alpha_1+\alpha_2-\frac{1}{2}\alpha_1^2K_{11}-y^{(1)}y^{(2)}\alpha_1\alpha_2K_{12}\\ &\quad-\frac{1}{2}\alpha_2^2K_{22}-y^{(1)}\alpha_1V_1-y^{(2)}\alpha_2V_2+const \end{array} \end{equation} 將\(\alpha_1=y^{(1)}\eta-y^{(1)}y^{(2)}\alpha_2\)帶入上式，\(W(\alpha_1,\alpha_2)\)簡化為關于\(\alpha_2\)的函數： \begin{equation} \begin{array}{ll} &\quad W(\alpha_2)\\ &=y^{(1)}\zeta-y^{(1)}y^{(2)}\alpha_2+\alpha_2-\frac{1}{2}(y^{(1)}\zeta-y^{(1)}y^{(2)}\alpha_2)^2K_{11}\\ &\quad-y^{(1)}y^{(2)}(y^{(1)}\zeta-y^{(1)}y^{(2)}\alpha_2)\alpha_2K_{12}-\frac{1}{2}\alpha_2^2K_{22}\\ &\quad-y^{(1)}(y^{(1)}\eta-y^{(1)}y^{(2)}\alpha_2)V_1-y^{(2)}\alpha_2V_2+const\\ &=y^{(1)}\zeta-y^{(1)}y^{(2)}\alpha_2+\alpha_2-\frac{1}{2}(\zeta^2-2y^{(2)}\zeta\alpha_2+\alpha_2^2)K_{11}\\ &\quad-(y^{(2)}\zeta-\alpha_2)\alpha_2K_{12}-\frac{1}{2}\alpha_2^2K_{22}-(\eta-y^{(2)}\alpha_2)V_1\\ &\quad-y^{(2)}\alpha_2V_2+const\\ &=-\frac{1}{2}(K_{11}-2K_{12}+K_{22})\alpha_2^2\\ &\quad +y^{(2)}(y^{(2)}-y^{(1)}+\zeta K_{11}-\zeta K_{12}+V_1-V_2)\alpha_2+const\\ &=A\alpha_2^2+B\alpha_2+C \end{array} \end{equation} \(W(\alpha_2)\)形式上為一元二次函數，現在分析一下\(A\)的情況，以便確定\(W(\alpha_2)\)在何處取得最大值。假設\(\phi(x_1)=(a_1,a_2,\cdots,a_n),\phi(x_2)=(b_1,b_2,\cdots,b_n)\)，則有 \begin{align} &K_{11}=\langle \phi(x_1),\phi(x_1)\rangle=\sum_{i=1}^na_i^2\\ &K_{12}=\langle\phi(x_1),\phi(x_2)\rangle=\sum_{i=1}^na_ib_i\\ &K_{22}=\langle\phi(x_2),\phi(x_2)\rangle=\sum_{i=1}^nb_i^2\\ \end{align} \begin{equation} \begin{array}{l} a_i^2+b_i^2-2a_ib_i=(a_i-b_i)^2\geq 0\\ \Rightarrow K_{11}-2K_{12}+K_{22}\geq 0\\ \Rightarrow A\leq 0 \end{array} \end{equation} 在用啟發式方法選擇\(\alpha_1\)和\(\alpha_2\)時，我們會選擇使\(A\neq 0\)的一對參數，所以\(W(\alpha_2)\)的曲線圖為開口向下的拋物線，最大值在極值點處取得。 \begin{equation} \begin{array}{ll} \frac{\partial W(\alpha_2)}{\partial\alpha_2}&=-(K_{11}-2K_{12}+K_{22})\alpha_2\\ &\quad +y^{(2)}(y^{(2)}-y^{(1)}+\zeta K_{11}-\zeta K_{12}+V_1-V_2) \end{array} \end{equation} 引入以下三個變量： \begin{align} &f_i=\sum_{i=1}^my^{(j)}\alpha_jK_{ij}+b\\ &E_i=f_i-y^{(i)}\\ &V_i=f_i-\sum_{j=1}^2y^{(j)}\alpha_jK_{ij}-b \end{align} 又有\(\alpha_1=y^{(1)}\eta-y^{(1)}y^{(2)}\alpha_2\)，令\(W(\alpha_2)\)針對\(\alpha_2\)的偏導為0： \begin{equation} \begin{array}{ll} &\quad (K_{11}-2K_{12}+K_{22})\alpha_2^{new}\\ &=y^{(2)}[y^{(2)}-y^{(1)}+\zeta(K_{11}-K_{12})\\ &\quad +(f_1-y^{(1)}\alpha_1^{old}K_{11}-y^{(2)}\alpha_2^{old}K_{12}-b)\\ &\quad-(f_2-y^{(1)}\alpha_1^{old}K_{21}-y^{(2)}\alpha_2^{old}K_{22}-b)]\\ &=y^{(2)}[(f_1-y^{(1)})-(f_2-y^{(2)})+\zeta(K_{11}-K_{12})\\ &\quad -(\zeta-y^{(2)}\alpha_2^{old})K_{11}-y^{(2)}\alpha_2^{old}K_{12}\\ &\quad +(\zeta-y^{(2)}\alpha_2^{old})K_{12}+y^{(2)}\alpha_2^{old}K_{22}]\\ &=y^{(2)}[(f_1-y^{(1)})-(f_2-y^{(2)})\\ &\quad +y^{(2)}\alpha_2^{old}(K_{11}-2K_{12}+K_{22})]\\ &=(K_{11}-2K_{12}+K_{22})\alpha_2^{old}+y^{(2)}(E_1-E_2) \end{array} \end{equation} 最后，我們得到如下的更新規則： \begin{equation} \alpha_2^{new}=\alpha_2^{old}+\frac{y^{(2)}(E_1-E_2)}{K_{11}-2K_{12}+K_{22}} \end{equation} 注意\(\alpha_2\)存在上下界，而上面根據極值點求出的\(\alpha_2^{new}\)很可能不在上下界確定的區間內： \begin{equation} \alpha_2^{new}\left\lbrace \begin{array}{ll} L, & \alpha_2^{new}\leq L\\ \alpha_2^{new}, & L<\alpha_2^{new}<H\\ H, & \alpha_2^{new}\geq H \end{array}\right. \end{equation} 根據\(\alpha_1\)和\(\alpha_2\)在更新前后都必須要滿足的線性約束條件，很容易求出\(\alpha_1^{new}\)： \begin{equation} \begin{array}{ll} &\alpha_1^{new}+y^{(1)}y^{(2)}\alpha_2^{new}=y^{(1)}\zeta=\alpha_1^{old}+y^{(1)}y^{(2)}\alpha_2^{old}\\ &\Rightarrow \alpha_1^{new}=\alpha_1^{old}+y^{(1)}y^{(2)}(\alpha_2^{old}-\alpha_2^{new}) \end{array} \end{equation} 有了\(\alpha_i\)的更新規則，我們可以確定分割超平面的方向向量\(w\)，那么我們又如何確定\(b\)的值呢？前面推導出了一個結論： \begin{equation} \left\lbrace \begin{array}{l} \alpha_i=0\Rightarrow y^{(i)}(w^Tx^{(i)}+b)\geq 1\\ \alpha_i=C\Rightarrow y^{(i)}(w^Tx^{(i)}+b)\leq 1\\ 0<\alpha_i<C\Rightarrow y^{(i)}(w^Tx^{(i)}+b)=1 \end{array}\right. \end{equation} 下面根據\(\alpha_1\)和\(\alpha_2\)的情況，分四種情況討論：

1. \(\alpha_1\in (0,C)\)時 \begin{equation} \begin{array}{l} y^{(1)}(w^Tx^{(1)}+b)=1\\ \Rightarrow\alpha_1^{new}y^{(1)}K_{11}+\alpha_2^{new}y^{(2)}K_{12}+\sum_{j=3}^m\alpha_jK_{1j}+b_{new}=y^{(1)} \end{array} \end{equation}又\(f_1=\sum_{j=1}^2\alpha_j^{old}y^{(1)}K_{1j}+\sum_{j=3}^m\alpha_jK_{1j}+b_{old}\)，\(E_1=f_1-y^{(1)}\)，得： \begin{equation} \begin{array}{ll} b_{new}&=(\alpha_1^{old}-\alpha_1^{new})y^{(1)}K_{11}\\ &\quad+(\alpha_2^{old}-\alpha_2^{new})K_{12}-E_1+b_{old}=b_1 \end{array} \end{equation}
2. ?\(\alpha_2\in (0,C)\)時 \begin{equation} \begin{array}{l} y^{(2)}(w^Tx^{(2)}+b)=1\\ \Rightarrow\alpha_1^{new}y^{(1)}K_{12}+\alpha_2^{new}y^{(2)}K_{22}+\sum_{j=3}^m\alpha_jK_{2j}+b_{new}=y^{(2)} \end{array} \end{equation}又\(f_2=\sum_{j=1}^2\alpha_j^{old}y^{(1)}K_{2j}+\sum_{j=3}^m\alpha_jK_{2j}+b_{old}\)，\(E_2=f_2-y^{(2)}\)，得： \begin{equation} \begin{array}{ll} b_{new}&=(\alpha_1^{old}-\alpha_1^{new})y^{(1)}K_{12}\\ &\quad+(\alpha_2^{old}-\alpha_2^{new})K_{22}-E_2+b_{old}=b_2 \end{array} \end{equation}
3. ?\(\alpha_1,\alpha_2\in (0,C)\)時，\(b_{new}=b_1=b_2\)
4. \(\alpha_1,\alpha_2\in \{0,C\}\)時，\(b_{new}\)可以為\(b_1\)和\(b_2\)間的任意值，一般取\(b_{new}=(b_1+b_2)/2\)

現在討論最后一個問題，如何用啟發式的方法選擇兩個乘子\(\alpha_1,\alpha_2\)?歸結為如下幾點：

• 外層循環選擇第一個乘子\(\alpha_1\)，內層循環選擇第二個最大化\(|E_1-E_2|\)的乘子\(\alpha_2\)。
• 外層循環先在整個訓練集上遍歷一次，然后盡可能多的在非邊界樣本( \(0< \alpha_{i} < {C} \))組成的集合上反復遍歷，從中選擇違反KKT調節的乘子，如此不斷重復，直到所有乘子都滿足KKT條件。
• 給定第一個乘子\(\alpha_1\)，內層循環先在非邊界乘子組成的集合上最大化\(|E_1-E_2|\)的乘子；如果參數基本沒變化，則從隨機位置開始遍歷非邊界樣本；如果參數仍然基本沒變化，則從隨機位置開始遍歷整個訓練集；如果沒有樣本能使參數發生變化，則第一個樣本會被忽略，重新選擇第一個乘子。

KKT條件是在精度\(eps\)內檢查的，一般\(eps=10^{-3}\)。\(|E_1-E_2|\)只是更新\(\alpha_2\)的步長的粗略估計，使\(|E_1-E_2|\)最大的樣本不一定能使參數得到更新。 在用程序實現SVM的過程中有三個小技巧可以加速程序的運行：1)每次更新參數后，更新分割超平面的方向向量\(w^{new}=w^{old}+(\alpha_1^{new}-\alpha_1^{old})y^{(1)}x^{(1)}+(\alpha_2^{new}-\alpha_2^{old})y^{(2)}x^{(2)}\)；2)核矩陣在整個過程中都不需要改動，因此計算好后可以存儲下來；3)每次更新參數后，同樣要更新樣本對應的誤差\(E_i^{new}=E_i^{old}+(\alpha_1^{new}-\alpha_1^{old})y^{(1)}K_{i1}+(\alpha_2^{new}-\alpha_2^{old})y^{(2)}K_{i2}+b_{new}-b_{old}\)。 具體內容及偽代碼請參加John C. Platt在1998年發表的論文《Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector Machines》。 John C. Platt的個人主頁 。 上述討論的SVM只能解決二分類問題，那么對于有\(K\)個類別的多分類問題我們怎么辦呢？有兩種策略：One-vs-One和One-vs-All。One-vs-One的思路如下：每次取出兩類樣本訓練一個SVM，最終得到\(K(K-1)/2\)個分類器；預測新樣本時，依次用\(K(K-1)/2\)個分類器進行預測，采取投票機制決定最后的分類結果。One-vs-All的思路如下：每次以一類樣本作為正樣本，其他樣本作為負樣本，最終訓練出\(K\)個分類器；預測新樣本時，依次用\(K\)個分類器進行預測，選擇能使\(|w^Tx+b|\)最大對應的類別作為輸出結果。 本篇博文對應的PDF文檔請在 這里下載 。

Support Vector Machine