?

導(dǎo)言

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

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

我們從解決二分類問(wè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}\)會(huì)直接輸出樣本的預(yù)測(cè)值，而不會(huì)經(jīng)歷logistic回歸中估算\(P(y=1|x)\)的中間步驟。

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

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

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

最優(yōu)間隔分類器(Optimal Margin Classifier)的意圖在于把樣本點(diǎn)和超平面之間最壞情況下的距離最大化，也就是尋找一個(gè)最優(yōu)超平面，使得支持向量離超平面最遠(yuǎn)，實(shí)現(xiàn)不同類樣本最大限度線性可分。函數(shù)間隔只能通過(guò)正負(fù)號(hào)反映分類正確與否，正號(hào)表示分類正確，負(fù)號(hào)表示分類錯(cuò)誤；而樣本間線性可分程度實(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ù)空間限定在超球面上，沒(méi)有較好的優(yōu)化方法來(lái)求解這類問(wèn)題。
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)練集上幾何間隔的最大值，但上一個(gè)目標(biāo)函數(shù)的兩個(gè)約束條件簡(jiǎn)化成了對(duì)函數(shù)間隔的約束。
3. 幾何間隔對(duì)\(\|w\|\)和\(\hat{\gamma}\)具有伸縮不變性。以相同倍數(shù)縮放\(\|w\|\)和\(\hat{\gamma}\)，直到\(\hat{\gamma}=1\)，此時(shí)幾何間隔保持不變。目標(biāo)函數(shù)進(jìn)一步簡(jiǎn)化為： \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ù)

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

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

?

特征映射(Feature Mapping)函數(shù)\(\phi\)將數(shù)據(jù)\(x\)從輸入空間映射到高維甚至無(wú)限維的特征空間中，對(duì)應(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}其中，輸入空間的兩個(gè)樣本點(diǎn)\(x_1\)和\(x_2\)經(jīng)過(guò)函數(shù)\(\phi\)分別被映射到特征空間中的\(\phi(x_1)\)和\(\phi(x_2)\)，\(<\cdot,\cdot>\)表示內(nèi)積運(yùn)算。 假設(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\)。每個(gè)核函數(shù)必然對(duì)應(yīng)一種映射關(guān)系，但并非所有的特征映射函數(shù)\(\phi\)都可以很容易求解出來(lái)。\(<\phi(x_1),\phi(x_2)>=K(x_1,x_2)\)告訴我們特征空間的內(nèi)積運(yùn)算可以在輸入空間通過(guò)核函數(shù)計(jì)算出來(lái)，因此根本沒(méi)必要知道核函數(shù)對(duì)應(yīng)的\(\phi\)。 常見(jiàn)的核函數(shù)有如下幾種形式： \begin{equation} \text{線性核函數(shù)：}K(x,y)=x^Ty+c \end{equation} \begin{equation} \text{多項(xiàng)式核函數(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\)。 一個(gè)有效的核函數(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ì)：

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

軟間隔

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

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

為了讓模型在一定程度上考慮離群點(diǎn)的影響，引入松弛變量和懲罰因子，目標(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)，表示誤分類的樣本與分割超平面之間的距離，正確分類的樣本對(duì)應(yīng)的松弛變量為0。\(C\)為懲罰因子，表示對(duì)離群點(diǎn)的重視程度。

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

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

對(duì)偶

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

1. 當(dāng)\(\alpha_i=0\)時(shí)，\(y^{(i)}(w^Tx^{(i)}+b)\geq 1\)，證明如下： \begin{align*} \begin{array}{l} \text{因?yàn)閩?\alpha_i=0,\alpha_i+\beta_i=C\\ \text{所以}??\beta_i=C\\ \text{因?yàn)閩?\beta_i\epsilon_i=0\\ \text{所以}??\epsilon_i=0\\ \text{因?yàn)閩?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\)時(shí)，\(y^{(i)}(w^Tx^{(i)}+b)\leq 1\)，證明如下： \begin{align*} \begin{array}{l} \text{因?yàn)閩?\alpha_i=C,\alpha_i+\beta_i=C\\ \text{所以}??\beta_i=0\\ \text{因?yàn)閩?\beta_i\epsilon_i=0,\epsilon_i\geq 0\\ \text{所以}??\epsilon_i\geq 0\\ \text{因?yàn)閩?\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\)時(shí)，\(y^{(i)}(w^Tx^{(i)}+b)=1\)，證明如下： \begin{align*} \begin{array}{l} \text{因?yàn)閩 0< \alpha_i < C,\alpha_i+\beta_i=C\\ \text{所以} 0< \beta_i < C\\ \text{因?yàn)閩?\beta_i\epsilon_i=0\\ \text{所以}??\epsilon_i=0\\ \text{因?yàn)閩?\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)化問(wèn)題形式如下： \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)按照\(chéng)(\alpha_1,\alpha_2,\cdots,\alpha_m\)的順序不斷重復(fù)前兩步直到收斂。下圖是該算法的優(yōu)化示意圖，其中藍(lán)色的折線為向前移動(dòng)的軌跡，每次移動(dòng)的軌跡都與坐標(biāo)軸平行，因?yàn)槊看沃桓铝艘粋€(gè)參數(shù)。

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

回到順序最小優(yōu)化算法上來(lái)，這里的最小指的是每次用最少的參數(shù)進(jìn)行優(yōu)化。我們面臨的對(duì)偶問(wèn)題如下： \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)化對(duì)偶問(wèn)題。如果我們固定除\(\alpha_i\)外的所有參數(shù)，由于等式關(guān)系的存在，\(\alpha_i\)也就成為被固定的常數(shù)而不是可以優(yōu)化的變量。如果要利用坐標(biāo)上升的思想解決這個(gè)優(yōu)化問(wèn)題，必須選擇至少兩個(gè)參數(shù)作為變量，并固定其他所有參數(shù)，然后同時(shí)優(yōu)化選出的參數(shù)。SMO算法的思想與坐標(biāo)上升基本一致：1)用啟發(fā)式方法選擇一對(duì)參數(shù)\(\alpha_i,\alpha_j\)，這對(duì)參數(shù)使目標(biāo)函數(shù)以最快的速度靠近全局最優(yōu)值；2)針對(duì)參數(shù)\(\alpha_i,\alpha_j\)優(yōu)化目標(biāo)函數(shù)\(W(\alpha)\)，并固定其他所有參數(shù)；3)不斷重復(fù)前兩步直至收斂。 不失一般性，任意選擇一對(duì)參數(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ù)空間被固定在一個(gè)矩形框中，稱這種約束為"Box Constraint"。 前面已經(jīng)說(shuō)過(guò)，\(y^{(i)}\in\{-1,1\}\)，當(dāng)\(y^{(1)},y^{(2)}\)取不同值時(shí)會(huì)影響參數(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}\)，則上式簡(jiǎn)化為： \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)\)簡(jiǎn)化為關(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\)時(shí)，我們會(huì)選擇使\(A\neq 0\)的一對(duì)參數(shù)，所以\(W(\alpha_2)\)的曲線圖為開(kāi)口向下的拋物線，最大值在極值點(diǎn)處取得。 \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} 引入以下三個(gè)變量： \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)\)針對(duì)\(\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ù)極值點(diǎn)求出的\(\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)出了一個(gè)結(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)\)時(shí) \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)\)時(shí) \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)\)時(shí)，\(b_{new}=b_1=b_2\)
4. \(\alpha_1,\alpha_2\in \{0,C\}\)時(shí)，\(b_{new}\)可以為\(b_1\)和\(b_2\)間的任意值，一般取\(b_{new}=(b_1+b_2)/2\)

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

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

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

Support Vector Machine