?

導(dǎo)言

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

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

我們從解決二分類問題的線性分類器著手，逐步深入地介紹SVM。為了便于表述，樣本類別標(biāo)簽定義為\(y\in\{-1,1\}\)。分類器的參數(shù)為\(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}由函數(shù)定義可知，分類器\(h_{w,b}\)會直接輸出樣本的預(yù)測值，而不會經(jīng)歷logistic回歸中估算\(P(y=1|x)\)的中間步驟。

函數(shù)間隔和幾何間隔

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

最優(yōu)間隔分類器

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

1. 最優(yōu)間隔分類器最直觀的目標(biāo)函數(shù)如下： \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\)是為了保證函數(shù)間隔等于幾何間隔，但該約束把參數(shù)空間限定在超球面上，沒有較好的優(yōu)化方法來求解這類問題。
2. 函數(shù)間隔是幾何間隔的\(\|w\|\)倍，利用這層關(guān)系將目標(biāo)函數(shù)轉(zhuǎn)化為如下形式： \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}目標(biāo)仍然是求訓(xùn)練集上幾何間隔的最大值，但上一個目標(biāo)函數(shù)的兩個約束條件簡化成了對函數(shù)間隔的約束。
3. 幾何間隔對\(\|w\|\)和\(\hat{\gamma}\)具有伸縮不變性。以相同倍數(shù)縮放\(\|w\|\)和\(\hat{\gamma}\)，直到\(\hat{\gamma}=1\)，此時幾何間隔保持不變。目標(biāo)函數(shù)進一步簡化為： \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\)，我們最終得到如下的目標(biāo)函數(shù)： \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}

核函數(shù)

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

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

?

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

• 對稱性(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}

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

軟間隔

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

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

為了讓模型在一定程度上考慮離群點的影響，引入松弛變量和懲罰因子，目標(biāo)函數(shù)如下： \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}其中\(zhòng)(\epsilon_i\)為松弛變量(slack variable)，表示誤分類的樣本與分割超平面之間的距離，正確分類的樣本對應(yīng)的松弛變量為0。\(C\)為懲罰因子，表示對離群點的重視程度。

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

    %上圖的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')
  

對偶

在前面的章節(jié)中，我們一步步導(dǎo)出了SVM的目標(biāo)函數(shù)，那么怎樣求解呢？整個求解的思路基本分為三步：1)定義原優(yōu)化問題；2)根據(jù)原問題導(dǎo)出對偶問題；3)通過求解對偶問題間接求解原問題。 根據(jù)目標(biāo)函數(shù)定義拉格朗日函數(shù)： \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} 原問題與對偶問題之間的關(guān)系為： \begin{equation} p^*\geq d^* \end{equation} 當(dāng)且僅當(dāng)參數(shù)滿足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} 將拉格朗日函數(shù)對參數(shù)\(w,b,\epsilon\)的偏導(dǎo)設(shè)置為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} 將上述三個結(jié)論帶入拉格朗日函數(shù)： \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} 我們可以根據(jù)\(h_{w,b}(x)\)預(yù)測樣本的類別： \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\)具有決定權(quán)的樣本對應(yīng)的拉格朗日乘子\(\alpha_i\)不為0；又根據(jù)KKT條件中的\(\alpha_i\left(y^{(i)}(w^Tx^{(i)}+b)+\epsilon_i-1\right)=0\)，必然有\(zhòng)(\left(y^{(i)}(w^Tx^{(i)}+b)+\epsilon_i-1\right)=0\),而滿足該條件的僅包括支持向量和被誤分類的樣本。根據(jù)函數(shù)\(h_{w,b}(x)\)，真正參與后期分類任務(wù)的樣本同樣只涉及到支持向量和被誤分類的樣本。支持向量和誤分類的樣本在整個數(shù)據(jù)集中的所占的比例往往非常小，一旦支持向量機在特定數(shù)據(jù)集上訓(xùn)練好后，我們只需要保留支持向量和被誤分類的樣本即可。如此以來，即使訓(xùn)練集有上百萬個訓(xùn)練樣本，我們最終需要保留下來的可能只有幾百個樣本，SVM的效率之高由此可見一斑！ 在\(W(\alpha)\)和\(h_{w,b}(x)\)中，都涉及到內(nèi)積運算，我們在后面的討論中會直接引入核函數(shù)，用\(K_{ij}\)替換\(\langle x^{(i)},x^{(j)}\rangle\)。 此外，結(jié)合KKT條件和\(\alpha_i+\beta_i=C\)，我們還可以推導(dǎo)出在后面的順序最小優(yōu)化中會用到的三個結(jié)論：

1. 當(dāng)\(\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. 當(dāng)\(\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. 當(dāng)\(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*}

順序最小優(yōu)化

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

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

回到順序最小優(yōu)化算法上來，這里的最小指的是每次用最少的參數(shù)進行優(yōu)化。我們面臨的對偶問題如下： \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\)使得坐標(biāo)上升算法不能直接用于優(yōu)化對偶問題。如果我們固定除\(\alpha_i\)外的所有參數(shù)，由于等式關(guān)系的存在，\(\alpha_i\)也就成為被固定的常數(shù)而不是可以優(yōu)化的變量。如果要利用坐標(biāo)上升的思想解決這個優(yōu)化問題，必須選擇至少兩個參數(shù)作為變量，并固定其他所有參數(shù)，然后同時優(yōu)化選出的參數(shù)。SMO算法的思想與坐標(biāo)上升基本一致：1)用啟發(fā)式方法選擇一對參數(shù)\(\alpha_i,\alpha_j\)，這對參數(shù)使目標(biāo)函數(shù)以最快的速度靠近全局最優(yōu)值；2)針對參數(shù)\(\alpha_i,\alpha_j\)優(yōu)化目標(biāo)函數(shù)\(W(\alpha)\)，并固定其他所有參數(shù)；3)不斷重復(fù)前兩步直至收斂。 不失一般性，任意選擇一對參數(shù)\(\alpha_1,\alpha_2\)作為變量，并固定其他所有參數(shù)。由等式約束得到下式： \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\)的參數(shù)空間被固定在一個矩形框中，稱這種約束為"Box Constraint"。 前面已經(jīng)說過，\(y^{(i)}\in\{-1,1\}\)，當(dāng)\(y^{(1)},y^{(2)}\)取不同值時會影響參數(shù)的范圍。下面分兩種情況討論參數(shù)的上下界。

• 若\(y^{(1)}\cdot y^{(2)}=-1\)，有\(zhòng)(\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\)，有\(zhòng)(\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\)之外的所有參數(shù)固定，則\(W(\alpha)\)可視為關(guān)于\(\alpha_1,\alpha_2\)的函數(shù)： \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)\)簡化為關(guān)于\(\alpha_2\)的函數(shù)： \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)\)形式上為一元二次函數(shù)，現(xiàn)在分析一下\(A\)的情況，以便確定\(W(\alpha_2)\)在何處取得最大值。假設(shè)\(\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} 在用啟發(fā)式方法選擇\(\alpha_1\)和\(\alpha_2\)時，我們會選擇使\(A\neq 0\)的一對參數(shù)，所以\(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} 又有\(zhòng)(\alpha_1=y^{(1)}\eta-y^{(1)}y^{(2)}\alpha_2\)，令\(W(\alpha_2)\)針對\(\alpha_2\)的偏導(dǎo)為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} 最后，我們得到如下的更新規(guī)則： \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\)存在上下界，而上面根據(jù)極值點求出的\(\alpha_2^{new}\)很可能不在上下界確定的區(qū)間內(nèi)： \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} 根據(jù)\(\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\)的更新規(guī)則，我們可以確定分割超平面的方向向量\(w\)，那么我們又如何確定\(b\)的值呢？前面推導(dǎo)出了一個結(jié)論： \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} 下面根據(jù)\(\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\)

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

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

KKT條件是在精度\(eps\)內(nèi)檢查的，一般\(eps=10^{-3}\)。\(|E_1-E_2|\)只是更新\(\alpha_2\)的步長的粗略估計，使\(|E_1-E_2|\)最大的樣本不一定能使參數(shù)得到更新。 在用程序?qū)崿F(xiàn)SVM的過程中有三個小技巧可以加速程序的運行：1)每次更新參數(shù)后，更新分割超平面的方向向量\(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)每次更新參數(shù)后，同樣要更新樣本對應(yīng)的誤差\(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}\)。 具體內(nèi)容及偽代碼請參加John C. Platt在1998年發(fā)表的論文《Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector Machines》。 John C. Platt的個人主頁 。 上述討論的SVM只能解決二分類問題，那么對于有\(zhòng)(K\)個類別的多分類問題我們怎么辦呢？有兩種策略：One-vs-One和One-vs-All。One-vs-One的思路如下：每次取出兩類樣本訓(xùn)練一個SVM，最終得到\(K(K-1)/2\)個分類器；預(yù)測新樣本時，依次用\(K(K-1)/2\)個分類器進行預(yù)測，采取投票機制決定最后的分類結(jié)果。One-vs-All的思路如下：每次以一類樣本作為正樣本，其他樣本作為負樣本，最終訓(xùn)練出\(K\)個分類器；預(yù)測新樣本時，依次用\(K\)個分類器進行預(yù)測，選擇能使\(|w^Tx+b|\)最大對應(yīng)的類別作為輸出結(jié)果。 本篇博文對應(yīng)的PDF文檔請在 這里下載 。

Support Vector Machine