详解支持向量机（Support Vector Machine, SVM）

接触支持向量机（Support Vector Machine, SVM）有很长一段时间了，对它的原理一直懵懵懂懂。有幸在国科大听了兰艳艳老师的课，对SVM有了更加深入的认识，决定写成笔记记录下来，当作是一次回顾，也希望对读者有启发。

一、引入问题

如图1所示，有一堆邮件用点表示，其中绿色的点表示正常邮件，红色的点表示垃圾邮件，需要画出一条分类线将这两种类别的邮件分开。

图1 两种不同的邮件

假设我们找到了很多条直线，它们都能将正常邮件和垃圾邮件分开，如图2所示。那么问题来了，哪一条分类线才是适合这个问题的最好分类线呢？

图2 垃圾邮件的分类线

思考一下找到分类线后我们需要用它来做什么？我们需要用它来分类测试集上的数据，也就是分类未知的数据，那么我们当然是希望它在测试集上表现比较好，而不仅仅是能把训练集全部分对，所以我们要选择泛化误差最小的那条分类线。

这里通俗地解释一下泛化误差的意思：泛化误差就是衡量一个模型推广能力的指标，泛化误差小就是当给我们一个新的数据，模型也有很大可能将数据分为正确的一类。
根据泛化误差的准则，我们需要找到一条有足够容忍度的分类线，它能够容忍数据的轻微波动，这样的分类线推广能力才会强，泛化误差才会小。比如图2中，选择红线、黄线和紫线作为分类线，那么假如靠近分类线的红点稍微向左偏移，模型就会将它判定为绿色的那一类，这样明显是错误的，我们称模型的泛化性较差，推广能力不强，泛化误差较大。而对于图2中的黑线，我们肉眼可见，它的容忍区间很大，也就是它到旁边最近的绿点和红点的间隔较大，即使数据点稍有偏动，模型也能将其正确分类，我们称这样的模型泛化性较强，推广能力较强，泛化误差较小。

二、支持向量机（Support vector machine, SVM）

我们都知道，逻辑回归（Logistic Regression）是一个概率模型，通过计算概率大小来判断类别，概率越大，置信度（confidence）越高，更有把握将数据分到正确的一类。而同样地，在上面的垃圾邮件分类中，经过分析，黑色的线在分类上比其它颜色的线具有更高的confidence能将邮件数据分到正确的类别。那么问题来了，如果没有概率，SVM拿什么来定义confidence？
前面我们已经分析过了，黑色的线比其他线具有更大的容忍区间，因此它的泛化误差更小，confidence更高。而更大的容忍区间意味着邻近的数据点与分类线的距离更大，抗扰动能力更强，我们定义这个距离为间隔（margin），如图3所示，黑色的实线到左右两条黑色的虚线的距离就是margin，用它来衡量confidence大小，即，margin越大，confidence越高。SVM的任务就是找到这样的一条直线，这条直线能够使margin最大，所以SVM又称为最大化间隔（Max Margin）。注意：Max Margin是一种思想，而SVM属于Max Margin的一个典型代表。

图3 SVM的间隔

训练集训练好分类模型之后，将该分类模型用于测试数据上，如图4所示，A，B，C三个点为测试数据点，显然，如果将图中的黑色实线作为分类线，A，B，C三个点都将分为Spam这一类，但是它们三个点的confidence不同，原因是它们到黑色实线的距离不同，A到黑色实线的距离最小，所以将它分为Spam的confidence最小，C到黑色实线的距离最大，所以将它分为Spam的confidence最大。

图4 SVM的测试

三、SVM的数学表达

对于二分类问题，定义标签$y\in\lbrace-1, 1\rbrace$y∈{−1,1}。给定一个训练集$(x^i, y^i), i\leq n$(xi,yi),i≤n，定义函数间隔（Functional margin）:
$\hat{\gamma}^i = y^i(w^Tx^i+b) \tag{1} \\ if\quad y^i=1, \quad w^Tx^i+b > 0 \\ if\quad y^i=-1, \quad w^Tx^i+b < 0$γ^​i=yi(wTxi+b)ifyi=1,wTxi+b>0ifyi=−1,wTxi+b<0(1)

无论什么情况，$y^i(w^Tx^i+b)>0$yi(wTxi+b)>0，模型才能得到一个正确的分类，反映了$\hat{\gamma}^i$γ^​i首先是一个正的距离。
补充说明：给定一个正样本，即$y=1$y=1，我们希望$w^Tx^i+b$wTxi+b不光大于0，还应该越大越好，这样子我们将其分为正类的confidence越高；同理，对于负样本，我们希望$w^Tx^i+b$wTxi+b小于0，并且越小越好，所以，对于函数间隔$\hat{\gamma}^i = y^i(w^Tx^i+b)$γ^​i=yi(wTxi+b)，我们希望它越大越好，越大confidence越高。函数间隔虽然不是几何意义上的间隔，但是依然可以作为衡量confidence的标准。也正是因为$\hat{\gamma}^i$γ^​i是通过定义一个函数反映了margin的效果，所以称之为函数间隔。
训练集上的所有数据离分类面最近的函数间隔定义为
$\hat{\gamma} = \min_{i=1,2,...,n}\hat{\gamma}^i \tag{2}$γ^​=i=1,2,...,nmin​γ^​i(2)
称为训练集上的函数间隔。
函数间隔并非真正意义上的几何间隔，几何间隔定义如下：
$\gamma^i = y^i\frac{(w^Tx^i+b)}{||w||_2} \tag{3} \\ \gamma = \min_{i=1,2,...,n}\gamma^i \\ \implies \gamma = \frac{\hat{\gamma}}{||w||_2}$γi=yi∣∣w∣∣2​(wTxi+b)​γ=i=1,2,...,nmin​γi⟹γ=∣∣w∣∣2​γ^​​(3)
前面有提到过，margin就是距离分类线最近的点到分类面的距离，我们也称为几何margin，它能决定confidence。我们希望算法能够有一个最优的分类线，它应该有足够的容忍度，也就是意味着分类线距离最近邻的那个点都越远越好，即几何margin足够大。基于上面的标准，我们定义如下的算法：
$\max_{\gamma,w,b}\gamma \tag{4}\\ s.t.\quad y^i\frac{(w^Tx^i+b)}{||w||_2} \geq \gamma, \quad i=1,2...,n$γ,w,bmax​γs.t.yi∣∣w∣∣2​(wTxi+b)​≥γ,i=1,2...,n(4)
上面的式子是一个最大化+约束条件的线性可分问题，这是SVM最早的思想。首先最大化几何margin，然后在约束条件上，任何其他点到分界线的距离都应该大于等于几何margin，因为几何margin就是最近邻点到分界线的距离，其他点的距离必然比它大，这样可以保证在训练样本上所有的点都能分对。
将（4）中公式改写成更容易求解的形式：
（1）利用几何margin和函数margin之间的关系：
$\max_{\gamma,w,b}\frac{\hat{\gamma}}{||w||_2} \tag{5}\\ s.t.\quad y^i(w^Tx^i+b) \geq \hat{\gamma}, \quad i=1,2...,n$γ,w,bmax​∣∣w∣∣2​γ^​​s.t.yi(wTxi+b)≥γ^​,i=1,2...,n(5)
（2）函数margin是随着$w$w和$b$b不断变化的，但是$w$w和$b$b如果是同倍数的放大或缩小,并不会影响分类线的位置。我们可以根据这个特性取合适的$w$w，使得$\hat{\gamma}=1$γ^​=1，也就是函数margin等于1，然后将（5）式子进行进一步简化：
$\min_{w,b}\frac{1}{2}||w||_2^2 \tag{6}\\ s.t.\quad y^i(w^Tx^i+b) \geq 1, \quad i=1,2...,n$w,bmin​21​∣∣w∣∣22​s.t.yi(wTxi+b)≥1,i=1,2...,n(6)
这里解释一下为什么max问题变成了min问题：若$\hat{\gamma}=1$γ^​=1，则$\max_{\gamma,w,b}\frac{1}{||w||_2}$maxγ,w,b​∣∣w∣∣2​1​等价于$\min_{w,b}\frac{1}{2}||w||_2^2$minw,b​21​∣∣w∣∣22​。（6）式是SVM的基本形式，它是一个凸的二次优化的问题，它的最优解不光存在，而且唯一，因为它找的是$\frac{1}{2}||w||_2^2$21​∣∣w∣∣22​下最小的目标值。这个优化问题可用二次优化的方法来求解，但是事实上通常不会这么去做，因为这样一个二次优化问题的复杂度是非常高的。后面我们将介绍SVM的对偶形式，用它来解优化问题会更方便。

四、SVM的对偶形式

在讲对偶形式之前，我们先来回顾一下优化的概念。优化分为三种：（1）无约束优化；（2）等式约束条件；（3）不等式约束条件。无约束优化我们不必赘述，我们来看一下有约束条件的优化问题：
$\min_{w}f(w) \tag{7}\\ s.t.\quad g_i(w) \leq 0, \quad i=1,2...,k \\ \quad h_i(w) = 0, \quad i=1,2...,l$wmin​f(w)s.t.gi​(w)≤0,i=1,2...,khi​(w)=0,i=1,2...,l(7)
（7）式中含有等式和不等式的约束，而解决含有约束条件的优化问题必然要用到拉格朗日乘数法（Lagrange Multiplier Method）：
$L(w,\alpha,\beta)=f(w)+\sum_{i=1}^{k}\alpha_ig_i(w)+\sum_{i=1}^{l}\beta_ih_i(w) \tag{8}$L(w,α,β)=f(w)+i=1∑k​αi​gi​(w)+i=1∑l​βi​hi​(w)(8)
其中，$\alpha_i, \beta_i$αi​,βi​是拉格朗日乘子。令
$\theta_P(w)=\max_{\alpha,\beta:\alpha_i\geq0}L(w,\alpha,\beta) \tag{9}\\ =\max_{\alpha,\beta:\alpha_i\geq0}(f(w)+\sum_{i=1}^{k}\alpha_ig_i(w)+\sum_{i=1}^{l}\beta_ih_i(w))$θP​(w)=α,β:αi​≥0max​L(w,α,β)=α,β:αi​≥0max​(f(w)+i=1∑k​αi​gi​(w)+i=1∑l​βi​hi​(w))(9)
下面证明优化$\theta_P(w)$θP​(w)就是优化$f(w)$f(w):
（1）假如$w$w违反任何约束条件，则有$g_i(w)>0$gi​(w)>0或者$h_i(w) \ne 0$hi​(w)​=0。当$g_i(w)>0$gi​(w)>0，必然有$\alpha_i\geq0$αi​≥0使得$\alpha_ig_i(w)=\infin$αi​gi​(w)=∞，那么$\theta_P(w)=\max_{\alpha,\beta:\alpha_i\geq0}L(w,\alpha,\beta)=\infin$θP​(w)=maxα,β:αi​≥0​L(w,α,β)=∞，显然这不是我们想要的最优值。当$h_i(w) \ne 0$hi​(w)​=0，那么必然有$\beta_i$βi​使得$\beta_ih_i(w)=\infin$βi​hi​(w)=∞，那么$\theta_P(w)=\max_{\alpha,\beta:\alpha_i\geq0}L(w,\alpha,\beta)=\infin$θP​(w)=maxα,β:αi​≥0​L(w,α,β)=∞，也不是我们想要的最优值。
（2）假如$w$w不违反任何约束条件，则有$g_i(w)\le0$gi​(w)≤0且$h_i(w)=0$hi​(w)=0。当$g_i(w)\le0$gi​(w)≤0，且$\alpha_i\geq0$αi​≥0，必然有$\sum_{i=1}^{k}\alpha_ig_i(w)\le0$∑i=1k​αi​gi​(w)≤0；当$h_i(w)=0$hi​(w)=0，无论$\beta$β取任何值，必然有$\sum_{i=1}^{l}\beta_ih_i(w)=0$∑i=1l​βi​hi​(w)=0。因此，$\theta_P(w)=\max_{\alpha,\beta:\alpha_i\geq0}L(w,\alpha,\beta)=\max_{\alpha,\beta:\alpha_i\geq0}(f(w)+0+0)=\max_{\alpha,\beta:\alpha_i\geq0}f(w)=f(w)$θP​(w)=maxα,β:αi​≥0​L(w,α,β)=maxα,β:αi​≥0​(f(w)+0+0)=maxα,β:αi​≥0​f(w)=f(w)。
因此，$\theta_P(w)$θP​(w)就等价于带有约束条件的$f(w)$f(w)，而
$\min_wf(w)=\min_w\theta_P(w)=\min_w\max_{\alpha,\beta:\alpha_i\geq0}L(w,\alpha,\beta) \tag{10}$wmin​f(w)=wmin​θP​(w)=wmin​α,β:αi​≥0max​L(w,α,β)(10)
上式与原始问题的解是一样的，定义$p^*=\min_w\theta_P(w)$p∗=minw​θP​(w)是原始问题的最优值。接下来正式进入我们的重头戏——对偶问题。
令

$\theta_D(\alpha,\beta)=\min_{w}L(w,\alpha,\beta) \tag{11}\\ \max_{\alpha,\beta:\alpha_i\geq0}\theta_D(\alpha,\beta)=\max_{\alpha,\beta:\alpha_i\geq0}\min_{w}L(w,\alpha,\beta)$θD​(α,β)=wmin​L(w,α,β)α,β:αi​≥0max​θD​(α,β)=α,β:αi​≥0max​wmin​L(w,α,β)(11)
跟原来的问题相比，原来是min，max问题，现在是max，min问题，将上式的最优值定义为$d^*=\max_{\alpha,\beta:\alpha_i\geq0}\theta_D(\alpha,\beta)$d∗=maxα,β:αi​≥0​θD​(α,β)。那么$d^*$d∗和$p^*$p∗有什么关系？

$p^*=\min_w\max_{\alpha,\beta:\alpha_i\geq0}L(w,\alpha,\beta) \ge \min_w\max_{\alpha,\beta:\alpha_i\geq0}\min_wL(w,\alpha,\beta) \tag{12}\\ =\max_{\alpha,\beta:\alpha_i\geq0}\min_{w}L(w,\alpha,\beta)=d^*$p∗=wmin​α,β:αi​≥0max​L(w,α,β)≥wmin​α,β:αi​≥0max​wmin​L(w,α,β)=α,β:αi​≥0max​wmin​L(w,α,β)=d∗(12)
由上面的推导可知，$d^*\le p^*$d∗≤p∗。我们将$d^*=\max_{\alpha,\beta:\alpha_i\geq0}\theta_D(\alpha,\beta)$d∗=maxα,β:αi​≥0​θD​(α,β)称为原始问题的一个对偶问题，并且希望用对偶问题替代原问题求解，复杂度会降低，所以我们希望$d^*\le p^*$d∗≤p∗（弱对偶性）变为$d^*=p^*$d∗=p∗（强对偶性）。那么什么时候$d^*=p^*$d∗=p∗呢？
假设目标函数$f(w)$f(w)和所有不等式约束$g_i(w)$gi​(w)都是凸函数，所有等式约束$h_i(w)$hi​(w)都是仿射的（仿射的含义：存在$a_i$ai​和$b_i$bi​，使得$h_i(w)=a_i^Tw+b_i,a_i\in R^n,w\in R^n,b_i\in R$hi​(w)=aiT​w+bi​,ai​∈Rn,w∈Rn,bi​∈R，我们可以简单理解仿射类似于线性），并且对于所有的$i$i都有$g_i(w)<0$gi​(w)<0，那么一定存在$w^*,\alpha^*,\beta^*$w∗,α∗,β∗是原始问题和对偶问题的解，即，$d^*=p^*=L(w^*,\alpha^*,\beta^*)$d∗=p∗=L(w∗,α∗,β∗)。另外，$w^*,\alpha^*,\beta^*$w∗,α∗,β∗还满足KKT（Karush-Kuhn-Tucker）条件：
$\frac{\partial L(w^*,\alpha^*,\beta^*)}{\partial w_i}=0,\quad i=1,2,...,M \tag{13}\\ g_i(w^*)\le0,\quad i=1,2,...,k\\ h_i(w^*)=0,\quad i=1,2,...,l\\ a_i^*g_i(w^*)=0,\quad i=1,2,...,k\\ a_i^*\ge0,\quad i=1,2,...,k$∂wi​∂L(w∗,α∗,β∗)​=0,i=1,2,...,Mgi​(w∗)≤0,i=1,2,...,khi​(w∗)=0,i=1,2,...,lai∗​gi​(w∗)=0,i=1,2,...,kai∗​≥0,i=1,2,...,k(13)
上面的五个式子就是KKT条件的具体内容。如果$w^*,\alpha^*,\beta^*$w∗,α∗,β∗满足KKT条件，那么$d^*=p^*$d∗=p∗，即优化对偶问题等价于优化原问题；同样地，如果$d^*=p^*$d∗=p∗，那么$w^*,\alpha^*,\beta^*$w∗,α∗,β∗必然满足KKT条件。所以KKT条件是原问题和对偶问题等价的充要条件。至于由KKT条件如何推导出$d^*=p^*$d∗=p∗，我也并不是很了解，随着知识的拓展，后面可能会接触到，至少现在我们不必太纠结这一点，只需要知道，满足了KKT条件，我们就能将优化原问题转化为优化对偶问题，极大地减少计算复杂度。
OK，回顾了优化和拉格朗日乘数法的概念，了解了对偶问题和KKT条件，我们就将这些知识用在SVM的求解上面。前面我们已经讲过，SVM的基本形式：
$\min_{w,b}\frac{1}{2}||w||_2^2 \tag{14}\\ s.t.\quad y^i(w^Tx^i+b) \geq 1, \quad i=1,2...,n$w,bmin​21​∣∣w∣∣22​s.t.yi(wTxi+b)≥1,i=1,2...,n(14)
写成一般的带不等式约束优化问题：
$\min_{w,b}f(w)=\frac{1}{2}||w||_2^2 \tag{15}\\ s.t.\quad g_i(w)=-y^i(w^Tx^i+b)+1 \le0, \quad i=1,2...,n$w,bmin​f(w)=21​∣∣w∣∣22​s.t.gi​(w)=−yi(wTxi+b)+1≤0,i=1,2...,n(15)
因为$f(w)=\frac{1}{2}||w||_2^2$f(w)=21​∣∣w∣∣22​是凸的，不等式约束也是凸的（SVM的不等式约束是线性函数，线性函数一定是凸的），所以对偶问题和原始问题的解是一样的，我们可以用拉格朗日对偶形式来求解，也就是min和max可以互换。下图5是SVM的基本形式所对应的图像，两条虚线分别对应$w^Tx^i+b=1$wTxi+b=1和$w^Tx^i+b=-1$wTxi+b=−1，即，$y^i(w^Tx^i+b)=1$yi(wTxi+b)=1，而其他的$y^i(w^Tx^i+b)>1$yi(wTxi+b)>1则表示点不在边界上，在边界以外的位置。

图5 SVM的基本形式

其实SVM为什么叫Support Vector Machine，而不叫Max Margin？因为正如图5所示，最近的向量点（vector）支撑着两条虚线——$w^Tx^i+b=1$wTxi+b=1和$w^Tx^i+b=-1$wTxi+b=−1，中间那条实线是$w^Tx^i+b=0$wTxi+b=0，是后续用在测试集分类的分类线。这些最近的vector成为support vector。Support vector的特性，就是只有Support vector会对最终的结果有作用。在SVM中会发现，之前有很多算法，比如逻辑回归要做一个极大似然估计，要统计每一个类别有多少个样本，每个训练集都会用到。但是在SVM中其它的vector都没用，只有support vector才有用，极大减少了计算的代价，这是SVM非常神奇的地方。因此，为了突出SVM的这个特点，就将其取名为Support Vector Machine，仅仅需要考虑这几个支撑点就可以了，它们已经完全决定了算法的特性，决定了算法泛化能力的高低，也决定了算法的复杂度。
KKT条件中，实际起作用的只有互补松弛条件——$a_i^*g_i(w^*)=0$ai∗​gi​(w∗)=0，其中$g_i(w)=1-y^i(w^Tx^i+b) \le0$gi​(w)=1−yi(wTxi+b)≤0的几何含义是“点是否虚线边界（margin）上”。如果是在margin上，$1-y^i(w^Tx^i+b)=0$1−yi(wTxi+b)=0；如果是margin以外，$1-y^i(w^Tx^i+b)<0$1−yi(wTxi+b)<0。$g_i(w)\le0$gi​(w)≤0就是告诉我们每个点要分对。互补松弛条件的特点在于“松弛”，意思是若$a_i^*$ai∗​或者$g_i(w^*)$gi​(w∗)有一个等于0，那么另一个就不必为0，这就是松弛的含义——不需要严格出现两个变量都是0的情况，标准放的松一点，有一个为0即可。有这个标准，我们可以分析：
如果$g_i(w)<0$gi​(w)<0，即i点在margin以外，由互补松弛条件可得$\alpha_i=0$αi​=0；如果$g_i(w)=0$gi​(w)=0，即i点在margin上，由互补松弛条件可得$\alpha_i<0$αi​<0。根据以上分析，在margin外的点，$\boldsymbol{\alpha_i=0}$αi​=0；在margin上的点，$\boldsymbol{\alpha_i>0}$αi​>0。
将SVM写成拉格朗日乘数法的形式：
$L(w,b,\alpha)=\frac{1}{2}||w||_2^2+\sum_{i=1}^n\alpha_i[1-y^i(w^Tx^i+b)] \tag{16}$L(w,b,α)=21​∣∣w∣∣22​+i=1∑n​αi​[1−yi(wTxi+b)](16)
只有在margin上的点$\boldsymbol{\alpha_i}$αi​才不为0，结合（16）式可以看出，只有这些点才对结果有作用，margin外的点不对结果产生作用。因此，从KKT条件可知，SVM的support vector在数学上有什么样的作用。
将（16）进行对偶形式优化，先对$L(w,b,\alpha)$L(w,b,α)求$\min_{w,b}$minw,b​，再求$\max_{\alpha}$maxα​：
（1）先对$L(w,b,\alpha)$L(w,b,α)求$\min_{w,b}$minw,b​，有
$\nabla_wL(w,b,\alpha)=w-\sum_{i=1}^{n}\alpha_iy^ix^i=0 \tag{17}\\ \Rightarrow w=\sum_{i=1}^{n}\alpha_iy^ix^i$∇w​L(w,b,α)=w−i=1∑n​αi​yixi=0⇒w=i=1∑n​αi​yixi(17)
$\frac{\partial{L(w,b,\alpha)}}{\partial{b}}=\sum_{i=1}^{n}\alpha_iy^i=0 \tag{18}$∂b∂L(w,b,α)​=i=1∑n​αi​yi=0(18)
上面的（18）式体现了$b$b不重要，但是告诉我们一个条件。
（2）将（17）（18）代回$L(w,b,\alpha)$L(w,b,α)，得到
$\theta_D(\alpha)=\sum_{i=1}^{n}\alpha_i-\frac{1}{2}\sum_{i,j=1}^{n}y^iy^j\alpha_i\alpha_j(x^i)^Tx^j \tag{19}$θD​(α)=i=1∑n​αi​−21​i,j=1∑n​yiyjαi​αj​(xi)Txj(19)
再求$\max_{\alpha}$maxα​，得到SVM的对偶形式如下：
$\max_\alpha\sum_{i=1}^{n}\alpha_i-\frac{1}{2}\sum_{i,j=1}^{n}y^iy^j\alpha_i\alpha_j(x^i)^Tx^j \tag{20} \\ s.t.\quad \alpha_i\ge0,i=1,2,...,n \\ \sum_{i=1}^{n}\alpha_i y^i=0$αmax​i=1∑n​αi​−21​i,j=1∑n​yiyjαi​αj​(xi)Txjs.t.αi​≥0,i=1,2,...,ni=1∑n​αi​yi=0(20)
假设$\alpha^*=(\alpha^*_1,\alpha^*_2...,\alpha^*_n)$α∗=(α1∗​,α2∗​...,αn∗​)是$\max_\alpha$maxα​的最优解，有
$w^*=\sum_{i=1}^{n}\alpha_i^*y^ix^i \tag{21}$w∗=i=1∑n​αi∗​yixi(21)
存在$\alpha^*_j>0$αj∗​>0，即，j点在边界上，有
$y^j((w^*)^Tx^j+b^*)=1 \tag{22} \\ \Rightarrow (w^*)^Tx^j+b^*=\frac{1}{y^j} \\ 由于y^j=\plusmn1,故\frac{1}{y^j}=y^j \\ \Rightarrow (w^*)^Tx^j+b^*=y^j$yj((w∗)Txj+b∗)=1⇒(w∗)Txj+b∗=yj1​由于yj=±1,故yj1​=yj⇒(w∗)Txj+b∗=yj(22)
将（21）式代入（22）式中，得
$b^*=y^j-\sum_{i=1}^{n}\alpha_i^*y^i(x^i)^Tx^j \tag{23}$b∗=yj−i=1∑n​αi∗​yi(xi)Txj(23)
$w^*$w∗体现了每个样本进行了一个线性加权，每个$\alpha^*_i$αi∗​表示该样本i对结果的贡献，在边界外的点都是$\alpha_i^*=0$αi∗​=0，所以只需要计算support vector的加权值。正样本$y^i=1$yi=1对$w^*$w∗起到正向作用，负样本$y^i=-1$yi=−1对$w^*$w∗起到负向作用，作用大小由$\alpha_i^*$αi∗​决定。上面的结论都是由SVM的对偶形式分析得来的，所以再次体现了对偶形式比原始形式更加重要。如果单从原始形式看的话，没有办法分析这个算法最终是谁影响的，每个点都对其产生怎样的作用。但是如果将其转化为对偶形式，就能清楚地看到每个训练数据是怎样发挥作用的，也就是$w,b$w,b是受谁的影响？受谁的影响更大？这些信息都可以通过对偶形式获得，所以SVM的对偶形式非常重要。

五、SVM的软间隔形式

前面我们已经得到了SVM的对偶形式，并且得到了$w^*$w∗和$b^*$b∗的表达式，但是计算出$w^*$w∗和$b^*$b∗的关键在于我们如何求出$\alpha_i^*$αi∗​，这个后续将会介绍。我们先看另外一个问题。
我们前面介绍的SVM应对的问题是线性可分的情况，称为硬间隔（Hard Margin）的SVM。如果问题是线性不可分的情况，也就是无法用一个分类面完全将不同类的数据分开，总会有误差的存在，如图6所示，那应该怎么办？

图6 线性不可分

有两种方法：一种是用核的方法将数据映射到高维空间的方法；另外一种是引入一个松弛变量的方法，这种方法也称为软间隔（Soft Margin）的SVM。本节只会介绍有松弛变量的方法。

假设问题不再是线性可分了，意味着总会有误差的存在。soft margin的想法就是反正你总要有误差了，那我就给你一定的容忍度，但是我只要把误差惩罚在算法里面就可以了，因此引入一个叫做松弛变量的变量，记为$\xi$ξ，如图7所示。

图7 软间隔

本来左上方蓝色的点应该属于右下方才是正确的分类，但不幸的是，这个点没办法被黑色的直线正确分类，从而产生一个误差，这个误差我们记为$\xi_i$ξi​，它是图中橙色的直线。之前hard margin是两种情况，一种是点在margin上，一种是点在margin外。而soft margin是三种情况：（1）点在margin上；（2）点在margin外且分对；（3）点被分错。分错的点我们才会给它一个容忍度，也就是松弛变量。图7中两个分错的点松弛变量为$\xi_i$ξi​和$\xi_j$ξj​。hard margin要求算法一定要把所有点分对，soft margin就是比较好说话的人，它不要求算法一定要把所有点都分对，不要求$\xi_i$ξi​非要等于0，但是要尽可能小。 在SVM的基本格式中加入一个惩罚项$\sum_{i=1}^n\xi_i$∑i=1n​ξi​：
$\min_{w,b}\frac{1}{2}||w||_2^2+C\sum_{i=1}^n\xi_i \tag{24}\\ s.t.\quad y^i(w^Tx^i+b) \geq 1-\xi_i, \quad i=1,2...,n \\ \xi_i \ge0, i=1,2,...,n$w,bmin​21​∣∣w∣∣22​+Ci=1∑n​ξi​s.t.yi(wTxi+b)≥1−ξi​,i=1,2...,nξi​≥0,i=1,2,...,n(24)
既然有松弛变量让算法有一定容忍度，那就要交一定罚金，罚金的倍数为（24）中的$C$C。soft margin的SVM形式仍然是凸的二次优化问题，因为它仍然要求$w$w，而$w$w仍是范数平方的形式。当然，对这个形式仍然可用拉格朗日的技巧来求它的对偶形式，由于$\xi_i\ge0$ξi​≥0也是个不等式约束，拉格朗日会变成这样的一个形式：
$L(w,b,\xi,\alpha,\eta)=\frac{1}{2}||w||_2^2+C\sum_{i=1}^n\xi_i \\ -\sum_{i=1}^n\alpha_i[y^i(w^Tx^i+b)-1+\xi_i]-\sum_{i=1}^n\eta_i\xi_i \tag{25}$L(w,b,ξ,α,η)=21​∣∣w∣∣22​+Ci=1∑n​ξi​−i=1∑n​αi​[yi(wTxi+b)−1+ξi​]−i=1∑n​ηi​ξi​(25)
下面的步骤跟前面做法一样，过程如下：
$\nabla_wL(w,b,\xi,\alpha,\eta)=w-\sum_{i=1}^{n}\alpha_iy^ix^i=0 \tag{26}\\ \Rightarrow w=\sum_{i=1}^{n}\alpha_iy^ix^i$∇w​L(w,b,ξ,α,η)=w−i=1∑n​αi​yixi=0⇒w=i=1∑n​αi​yixi(26)
$\frac{\partial{L(w,b,\xi,\alpha,\eta)}}{\partial{b}}=\sum_{i=1}^{n}\alpha_iy^i=0 \tag{27}$∂b∂L(w,b,ξ,α,η)​=i=1∑n​αi​yi=0(27)
$\frac{\partial{L(w,b,\xi,\alpha,\eta)}}{\partial{\xi_i}}=C-\alpha_i-\eta_i=0 \tag{28}$∂ξi​∂L(w,b,ξ,α,η)​=C−αi​−ηi​=0(28)
代回原拉格朗日式子中，得到
$\theta_D(\alpha)=\sum_{i=1}^{n}\alpha_i-\frac{1}{2}\sum_{i,j=1}^{n}y^iy^j\alpha_i\alpha_j(x^i)^Tx^j \tag{29}$θD​(α)=i=1∑n​αi​−21​i,j=1∑n​yiyjαi​αj​(xi)Txj(29)
得到新的soft margin情况之下的一个对偶问题的形式：
$\max_\alpha\sum_{i=1}^{n}\alpha_i-\frac{1}{2}\sum_{i,j=1}^{n}y^iy^j\alpha_i\alpha_j(x^i)^Tx^j \tag{30} \\ s.t.\quad 0\le\alpha_i\le C,i=1,2,...,n \\ \sum_{i=1}^{n}\alpha_i y^i=0$αmax​i=1∑n​αi​−21​i,j=1∑n​yiyjαi​αj​(xi)Txjs.t.0≤αi​≤C,i=1,2,...,ni=1∑n​αi​yi=0(30)
我们可以对比一下它和hard margin对偶问题的差别在哪里？是不是只多了一个$\alpha_i\le C$αi​≤C。那$\alpha_i$αi​代表每个训练数据的重要性。在hard margin里，$\alpha_i$αi​是可以无限大的，代表那些support vector的权重可以无限大。而在soft margin中，$\alpha_i$αi​无法无限大，有一个$C$C限界。接着同hard margin一样的方式，得到
$w^*=\sum_{i=1}^{n}\alpha_i^*y^ix^i \tag{31}$w∗=i=1∑n​αi∗​yixi(31)
$b^*=y^j-\sum_{i=1}^{n}\alpha_i^*y^i(x^i)^Tx^j \tag{32}$b∗=yj−i=1∑n​αi∗​yi(xi)Txj(32)
分类超平面：
$\sum_{i=1}^{n}\alpha_i^*y^i(x^i)^Tx+b^*=0 \tag{33}$i=1∑n​αi∗​yi(xi)Tx+b∗=0(33)
决策函数：
$f_{w,b}(x)=sign(\sum_{i=1}^{n}\alpha_i^*y^i(x^i)^Tx+b^*) \tag{34}$fw,b​(x)=sign(i=1∑n​αi∗​yi(xi)Tx+b∗)(34)
soft margin对比hard margin的KKT条件，多了两个变化：

$\alpha_i^*g_i(w^*)=\alpha_i^*[y^i(w^Tx^i+b)-1+\xi_i]=0 \tag{35}$αi∗​gi​(w∗)=αi∗​[yi(wTxi+b)−1+ξi​]=0(35)
$\eta_i^*\xi_i=0 \tag{36}$ηi∗​ξi​=0(36)
对照图8，我们看看不同$\alpha_i^*$αi∗​的取值对应的不同情况：
如果$\alpha_i^*=0$αi∗​=0，由（28）式可知，$C=\alpha_i^*+\eta_i^*$C=αi∗​+ηi∗​，所以$\eta_i^*=C$ηi∗​=C，又由（36）式可知，$\xi_i=0$ξi​=0，故$g_i(w^*)=-[y^i((w^*)^Tx^i+b^*)-1+\xi_i]=-[y^i((w^*)^Tx^i+b^*)-1]\le0$gi​(w∗)=−[yi((w∗)Txi+b∗)−1+ξi​]=−[yi((w∗)Txi+b∗)−1]≤0，所以$y^i((w^*)^Tx^i+b^*)\ge1$yi((w∗)Txi+b∗)≥1，表示分为正确的一类。
如果$0\le\alpha_i^*\le C$0≤αi∗​≤C，由（35）式可知，$g_i(w^*)=0$gi​(w∗)=0；由（28）式可知，$C=\alpha_i^*+\eta_i^*\Rightarrow0<\eta_i<C$C=αi∗​+ηi∗​⇒0<ηi​<C；由（36）式可知，$\xi_i=0$ξi​=0，将其代入$g_i(w^*)=0$gi​(w∗)=0，得到$y^i((w^*)^Tx^i+b)=1$yi((w∗)Txi+b)=1，表示被分对且在边界上。
如果$\alpha_i^*=C$αi∗​=C，由（28）式可知，$C=\alpha_i^*+\eta_i^*\Rightarrow\eta_i=0$C=αi∗​+ηi∗​⇒ηi​=0；由（35）式可知，$g_i(w^*)=0\Rightarrow y^i((w^*)^Tx^i+b^*)=1-\xi_i$gi​(w∗)=0⇒yi((w∗)Txi+b∗)=1−ξi​；又因为$\xi_i\ge0\Rightarrow y^i((w^*)^Tx^i+b^*)\le1$ξi​≥0⇒yi((w∗)Txi+b∗)≤1，表示要么在边界上，要么被分错。

图8 软间隔的三种情况

由上面的分析可知，只有分错和在边界上的点它们的$\alpha_i^*$αi∗​才不为0，也就是只有这些点才起作用，其中分错的点作用最大，它们的$\alpha_i^*=C$αi∗​=C。
OK，接下来我们思考一个问题，$C$C到底是什么？$C$C其实就是容忍程度，就是一个点分错，给它的惩罚有多大。soft margin的目标函数为$\min_{w,b}\frac{1}{2}||w||_2^2+C\sum_{i=1}^n\xi_i$minw,b​21​∣∣w∣∣22​+C∑i=1n​ξi​，当$C$C越小，惩罚越小，那么可以容忍的犯错点越多；反之，当$C$C越大，惩罚越大，那么可以容忍的犯错点就越少。所以$C$C作为超参数，在实际应用中对它的调节很重要。
其实很多算法都有一个损失函数，我们来看一下SVM的损失函数是什么。（24）式是SVM的优化目标，下式便是它的损失函数的优化：
$\min_{w,b}\sum_{i=1}^n[1-y^i(w^Tx^i+b)]_++\lambda||w||_2^2 \tag{37}$w,bmin​i=1∑n​[1−yi(wTxi+b)]+​+λ∣∣w∣∣22​(37)
分析一下这个损失函数如何得到的：
由约束条件可知，$1-y^i(w^Tx^i+b)\le\xi_i$1−yi(wTxi+b)≤ξi​。只有当$1-y^i(w^Tx^i+b)>0$1−yi(wTxi+b)>0，结合$\xi_i\ge0$ξi​≥0，约束条件变为$\xi_i\ge1-y^i(w^Tx^i+b)$ξi​≥1−yi(wTxi+b)；当$1-y^i(w^Tx^i+b)\le0$1−yi(wTxi+b)≤0，结合$\xi_i\ge0$ξi​≥0，约束条件变为$\xi_i\ge0$ξi​≥0；所以$1-y^i(w^Tx^i+b)>0$1−yi(wTxi+b)>0时，$1-y^i(w^Tx^i+b)$1−yi(wTxi+b)这个式子才有意义，我们取这个式子的正部作为损失函数的一项（正部的含义是当式子大于0时等于它本身，当式子小于等于0时等于0），还有一项是$\lambda||w||_2^2$λ∣∣w∣∣22​，其中$\lambda=\frac{1}{C}$λ=C1​。所以带约束的优化函数就等于这个损失函数。下面是$L(f,x,y)=[1-y(w^Tx+b)]_+$L(f,x,y)=[1−y(wTx+b)]+​这个损失函数的图像：

图9 Hinge Loss Function

图9中绿色的线就是损失函数的图像，这个损失又叫hinge损失，横轴为$yf(x)$yf(x)。我们知道，回归的真实损失为平方损失，二分类的真实损失为0,1损失。当二分类为0时表示分对，等于1时表示分错。在图9中，$yf(x)<0$yf(x)<0是有错，就是红色的那条线。绿色的线是红色线的上界。对分类而言损失函数不好分析，它是个截断函数，而且有参数$w$w需要学习和估计，并且它是个非凸函数，在中间截断处没有梯度，没办法用导数方法直接求解，所以求解很困难、麻烦。人们想要给他们找到替代的损失，每找一个替代损失就会出现新的算法，找的过程就是在找一些凸的上界，不同算法可以画到函数图像来看，如图10所示。

图10 不同算法的损失函数对比

归根结底就会发现，这些算法好不好从理论上在于目标函数与真实目标函数有多接近，从这个意义上可以衡量不同算法之间性能上的差异。