背景

回顾 感知机 处理二分类问题。先给定一个特征空间上的训练集：
$T=\{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\} \\ x_i\in \mathcal X=\mathbf R^n , y_i\in \mathcal Y\it =\{-1,+1\}, i=1,2,\dots,N; \ \ 0<\eta\leqslant 1$T={(x1​,y1​),(x2​,y2​),…,(xN​,yN​)}xi​∈X=Rn,yi​∈Y={−1,+1},i=1,2,…,N;  0<η⩽1
我们的目标是在特征空间上找到一个分离超平面，能将样本分到不同的类中，超平面对应的方程为：
$w^*\cdot x+b^* = 0$w∗⋅x+b∗=0
它由法向量$w$w和 截距$b$b 决定，记作$(w,b)$(w,b)。分离超平面将特征空间划分为两部分，一部分是正类，一部分是负类。法向量指向的一侧为正类，另一侧为负类。

一般地，当训练数据集线性可分时，存在无穷个分离超平面可将两类数据正确分开。感知机利用误分类最小的策略，求得分离超平面，不过这时的解有无穷多个。线性可分支持向量机利用间隔最大化求最优分离超平面，这时，解是唯一的。也就是说感知机和支持向量机在损失函数的选择不同，造成最终超平面的不同。

间隔最大化

在介绍间隔最大化及其相应的约束最优化问题之前，先介绍函数间隔和几何间隔。

函数间隔

对于正确分类点来说： $w\cdot x_0 + b$w⋅x0​+b 与 $y_i$yi​ 总是符号相同。即：
$y_i(w\cdot x_0 + b)>0$yi​(w⋅x0​+b)>0
所以有：$|w\cdot x_0 + b|=y_i(w\cdot x_0 + b)$∣w⋅x0​+b∣=yi​(w⋅x0​+b) 用来表示分类的正确性及确信度。这就是函数间隔。

定义超平面$(w,b)$(w,b) 关于样本点$(x_i,y_i)$(xi​,yi​) 的函数间隔为：
$\hat \gamma_i = y_i(w\cdot x_i + b)$γ^​i​=yi​(w⋅xi​+b)
超平面$(w,b)$(w,b) 关于样本点$(x_i,y_i)$(xi​,yi​) 的函数间隔的最小值为：
$\hat \gamma = \min \limits_{i=1,\ldots, N} \hat \gamma_i$γ^​=i=1,…,Nmin​γ^​i​

几何间隔

函数间隔存在一个问题：只要成比例的改变$w,b$w,b ，如：将他们变为$2w,2b$2w,2b，超平面并没有改变，但是函数间隔却变为了原来的两倍。所以我们引入$||w||$∣∣w∣∣ 对函数间隔进行约束，得到几何间隔：
$\gamma_i = \frac{y_i(w\cdot x_i + b)}{||w||}$γi​=∣∣w∣∣yi​(w⋅xi​+b)​
超平面$(w,b)$(w,b) 关于样本点$(x_i,y_i)$(xi​,yi​) 的几何间隔的最小值为：
$\gamma = \min \limits_{i=1,\ldots, N} \gamma_i$γ=i=1,…,Nmin​γi​

间隔最大化

间隔最大化的直观解释是: 最大化最小几何间距。也就是说，不仅将正负实例点分开，而且对最难分的实例点(离超平面最近的点)也有足够大的确信度将它们分开。即：
$\begin{aligned} &\max_{w,b} \gamma \\ &s.t. \quad \frac{y_i(w\cdot x_i + b)}{||w||} \geq \gamma,i=1,2,\dots,N\\ \end{aligned}$​w,bmax​γs.t.∣∣w∣∣yi​(w⋅xi​+b)​≥γ,i=1,2,…,N​
将上式的几何间隔转为函数间隔表达：
$\begin{aligned} &\max_{w,b}\frac{\hat \gamma}{\left\|w\right\|}\\ &s.t.\ \ \ y_i(w\cdot x_i+b)\geq \hat\gamma,\quad i=1,2,\dots,N\\ \end{aligned}$​w,bmax​∥w∥γ^​​s.t.   yi​(w⋅xi​+b)≥γ^​,i=1,2,…,N​

函数间隔的取值并不影响最优化问题的解，所以取$\hat \gamma = 1$γ^​=1，所以上述问题转为以下问题：
$\begin{aligned} &\min_{w,b}\frac{1}{2}||w||^2\\ &s.t.\ \ \ y_i(w\cdot x_i+b)-1\geq0, \quad i=1,2,\dots,N\\ \end{aligned}$​w,bmin​21​∣∣w∣∣2s.t.   yi​(w⋅xi​+b)−1≥0,i=1,2,…,N​
这是一个凸二次规划问题。这个问题的最优解$w^*,b^*$w∗,b∗ 即为算求的超平面。

学习的对偶算法

求解SVM的最优化问题，应用拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解。这样做的优点是：（1）对偶问题往往容易求解（2）自然引入核函数。

原始问题：
$\begin{aligned} &\min_{w,b}\frac{1}{2}||w||^2\\ &s.t.\ \ \ 1- y_i(w\cdot x_i+b)\leq 0, \quad i=1,2,\dots,N\\ \end{aligned}$​w,bmin​21​∣∣w∣∣2s.t.   1−yi​(w⋅xi​+b)≤0,i=1,2,…,N​

首先构造拉格朗日函数，对每一个不等式约束引入拉格朗日乘子$\alpha_i \geq 0, i=1,2,\ldots,N$αi​≥0,i=1,2,…,N ,定义拉格朗日函数：
$\begin{aligned} L(w,b,\alpha) &=\frac{1}{2}\left\|w\right\|^2+\left[\sum_{i=1}^N\alpha_i[1-y_i(w\cdot x_i+b)]\right]\\ &=\frac{1}{2}\left\|w\right\|^2-\sum_{i=1}^N\alpha_iy_i(w\cdot x_i+b)+\sum_{i=1}^N\alpha_i \end{aligned}\\ \alpha_i \geqslant0, i=1,2,\dots,N$L(w,b,α)​=21​∥w∥2+[i=1∑N​αi​[1−yi​(w⋅xi​+b)]]=21​∥w∥2−i=1∑N​αi​yi​(w⋅xi​+b)+i=1∑N​αi​​αi​⩾0,i=1,2,…,N
其中，$\alpha = (\alpha_1,\alpha_2,\ldots,\alpha_N)^T$α=(α1​,α2​,…,αN​)T 是拉格朗日乘子。

原始问题等价于：
$\min \limits_{w,b} \max\limits_{\alpha}L(w,b,\alpha)$w,bmin​αmax​L(w,b,α)

根据拉格朗日对偶性，所以原始问题的对偶问题是：
$\max\limits_\alpha\min\limits_{w,b}L(w,b,\alpha)$αmax​w,bmin​L(w,b,α)
原始问题与对偶问题有相同的解，所以我们通过求对偶问题的解间接得到原始问题的最优解，这样可以简小计算量，这就是SVM的对偶算法。

所以接下来我们的目标就是求解：$\max\limits_\alpha\min\limits_{w,b}L(w,b,\alpha)$αmax​w,bmin​L(w,b,α) 。分两步进行：

（1）求$\min\limits_{w,b}L(w,b,\alpha)$w,bmin​L(w,b,α)

将拉格朗日函数$L(w,b,\alpha)$L(w,b,α) 分别对$w,b$w,b 求偏导并令其等于0。
$\frac{\partial L(w,b,\alpha)}{\partial w} = w-\sum_{i=1}^N \alpha_iy_i x_i= 0 \;\Rightarrow w = \sum\limits_{i=1}^{N}\alpha_iy_ix_i$∂w∂L(w,b,α)​=w−i=1∑N​αi​yi​xi​=0⇒w=i=1∑N​αi​yi​xi​

$\frac{\partial L(w,b,\alpha)}{\partial b} = -\sum_{i=1}^N\alpha_iy_i= 0 \;\Rightarrow \sum\limits_{i=1}^{N}\alpha_iy_i = 0$∂b∂L(w,b,α)​=−i=1∑N​αi​yi​=0⇒i=1∑N​αi​yi​=0

将$w = \sum\limits_{i=1}^{N}\alpha_iy_ix_i,\sum\limits_{i=1}^{N}\alpha_iy_i = 0$w=i=1∑N​αi​yi​xi​,i=1∑N​αi​yi​=0 ，带入$L(w,b,\alpha)$L(w,b,α) 得：
$\begin{aligned} L(w,b,\alpha)& = \frac{1}{2}||w||^2 - \sum_{i=1}^N\alpha_iy_i(w\cdot x_i+b)+\sum_{i=1}^N\alpha_i \\& = \frac{1}{2}w^Tw-\sum\limits_{i=1}^{N}\alpha_iy_iw^Tx_i - \sum\limits_{i=1}^{N}\alpha_iy_ib + \sum\limits_{i=1}^{N}\alpha_i \\& = \frac{1}{2}w^T\sum\limits_{i=1}^{N}\alpha_iy_ix_i -\sum\limits_{i=1}^{N}\alpha_iy_iw^Tx_i - \sum\limits_{i=1}^{N}\alpha_iy_ib + \sum\limits_{i=1}^{N}\alpha_i \\& = \frac{1}{2}w^T\sum\limits_{i=1}^{N}\alpha_iy_ix_i - w^T\sum\limits_{i=1}^{N}\alpha_iy_ix_i - \sum\limits_{i=1}^{N}\alpha_iy_ib + \sum\limits_{i=1}^{N}\alpha_i \\& = - \frac{1}{2}w^T\sum\limits_{i=1}^{N}\alpha_iy_ix_i - \sum\limits_{i=1}^{N}\alpha_iy_ib + \sum\limits_{i=1}^{N}\alpha_i \\& = - \frac{1}{2}w^T\sum\limits_{i=1}^{N}\alpha_iy_ix_i - b\sum\limits_{i=1}^{N}\alpha_iy_i + \sum\limits_{i=1}^{N}\alpha_i \\& = -\frac{1}{2}(\sum\limits_{i=1}^{N}\alpha_iy_ix_i)^T(\sum\limits_{i=1}^{N}\alpha_iy_ix_i) - b\sum\limits_{i=1}^{N}\alpha_iy_i + \sum\limits_{i=1}^{N}\alpha_i \\& = -\frac{1}{2}\sum\limits_{i=1}^{N}\alpha_iy_ix_i^T\sum\limits_{i=1}^{N}\alpha_iy_ix_i - b\sum\limits_{i=1}^{N}\alpha_iy_i + \sum\limits_{i=1}^{N}\alpha_i \\& = -\frac{1}{2}\sum\limits_{i=1}^{N}\alpha_iy_ix_i^T\sum\limits_{i=1}^{N}\alpha_iy_ix_i + \sum\limits_{i=1}^{N}\alpha_i \\& = -\frac{1}{2}\sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N}\alpha_iy_ix_i^T\alpha_jy_jx_j + \sum\limits_{i=1}^{N} \alpha_i \\& = -\frac{1}{2}\sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N}\alpha_iy_i\alpha_jy_j x_i^T x_j + \sum\limits_{i=1}^{N} \alpha_i \end{aligned}$L(w,b,α)​=21​∣∣w∣∣2−i=1∑N​αi​yi​(w⋅xi​+b)+i=1∑N​αi​=21​wTw−i=1∑N​αi​yi​wTxi​−i=1∑N​αi​yi​b+i=1∑N​αi​=21​wTi=1∑N​αi​yi​xi​−i=1∑N​αi​yi​wTxi​−i=1∑N​αi​yi​b+i=1∑N​αi​=21​wTi=1∑N​αi​yi​xi​−wTi=1∑N​αi​yi​xi​−i=1∑N​αi​yi​b+i=1∑N​αi​=−21​wTi=1∑N​αi​yi​xi​−i=1∑N​αi​yi​b+i=1∑N​αi​=−21​wTi=1∑N​αi​yi​xi​−bi=1∑N​αi​yi​+i=1∑N​αi​=−21​(i=1∑N​αi​yi​xi​)T(i=1∑N​αi​yi​xi​)−bi=1∑N​αi​yi​+i=1∑N​αi​=−21​i=1∑N​αi​yi​xiT​i=1∑N​αi​yi​xi​−bi=1∑N​αi​yi​+i=1∑N​αi​=−21​i=1∑N​αi​yi​xiT​i=1∑N​αi​yi​xi​+i=1∑N​αi​=−21​i=1∑N​j=1∑N​αi​yi​xiT​αj​yj​xj​+i=1∑N​αi​=−21​i=1∑N​j=1∑N​αi​yi​αj​yj​xiT​xj​+i=1∑N​αi​​
即：
$\min\limits_{w,b}L(w,b,\alpha)=-\frac{1}{2}\sum\limits_{i=1,j=1}^{N}\alpha_iy_ix_i^T\alpha_jy_jx_j + \sum\limits_{i=1}^{N}\alpha_i$w,bmin​L(w,b,α)=−21​i=1,j=1∑N​αi​yi​xiT​αj​yj​xj​+i=1∑N​αi​
（2） 求$\min\limits_{w,b}L(w,b,\alpha)$w,bmin​L(w,b,α) 对$\alpha$α 的极大化
$\begin{aligned} &\max \limits_{\alpha}\sum\limits_{i=1}^{m}\alpha_i - \frac{1}{2}\sum\limits_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j \\& st.\quad \sum_{i=1}^N\alpha_iy_i = 0 \\& \alpha_i \geq 0, \quad i=1,2,\ldots N \end{aligned}$​αmax​i=1∑m​αi​−21​i=1,j=1∑m​αi​αj​yi​yj​xiT​xj​st.i=1∑N​αi​yi​=0αi​≥0,i=1,2,…N​
假设上式的最优解为$\alpha^*=(\alpha_1^*,\alpha_2^*,\ldots\alpha_N^*)$α∗=(α1∗​,α2∗​,…αN∗​) 。

所以，我们就有了对偶问题的最优解：$\alpha^*,w^*,b^*$α∗,w∗,b∗

为什么原始问题与对偶问题有相同的解？

若原始问题与对偶问题有相同的解$w^*, b^*, \alpha^*$w∗,b∗,α∗，则要满足KKT条件：
$\nabla_wL(w^*, b^*, \alpha^*) = w^*-\sum\limits_{i=1}^{m}\alpha_iy_ix_i = 0 \quad\quad (1) \\ \nabla_bL(w^*, b^*, \alpha^*) = -\sum\limits_{i=1}^{m}\alpha_iy_i = 0 \quad\quad (2) \\ \alpha^*(1-y_i(w^{*T}x_i+b^*)) = 0 \quad\quad (3) \\ 1-y_i(w^{*T}x_i+b^*) \le 0 \quad\quad\quad (4) \\ a_i^* \ge 0,\quad i=1,2,...m \quad\quad\quad (5)$∇w​L(w∗,b∗,α∗)=w∗−i=1∑m​αi​yi​xi​=0(1)∇b​L(w∗,b∗,α∗)=−i=1∑m​αi​yi​=0(2)α∗(1−yi​(w∗Txi​+b∗))=0(3)1−yi​(w∗Txi​+b∗)≤0(4)ai∗​≥0,i=1,2,...m(5)

由此得
$w = \sum\limits_{i=1}^{N}\alpha_iy_ix_i$w=i=1∑N​αi​yi​xi​
公式(3)为KKT对偶互补条件（只要一个不为0，另一个就必为0），可以知道：而当$\alpha_i =0$αi​=0 对应样本$x_i$xi​ 的约束不起作用。而当$\alpha^*>0$α∗>0，则有:
$\begin{aligned} y_i(w^{*T}x_i+b^*)-1 = 0 \\ y_i(\sum\limits_{i=1}^{N}\alpha_iy_ix_i^Tx_i+b^*)-1 = 0 \end{aligned}$yi​(w∗Txi​+b∗)−1=0yi​(i=1∑N​αi​yi​xiT​xi​+b∗)−1=0​
此时，$\alpha_i >0$αi​>0 对应样本$x_i$xi​的点为支持向量。$x_i$xi​ 一定在间隔边界上。

由此说明：当样本点$x_i$xi​ 处于可行域的内部时，这时不等式约束并不起作用，只有位于可行域边界的点才会起作用，也就是所谓的支持向量。

注意到$y_j^2=1$yj2​=1，即得：
$b^* = y_j -\sum\limits_{i=1}^{m}\alpha_i^{*}y_ix_i^Tx_j$b∗=yj​−i=1∑m​αi∗​yi​xiT​xj​
所以超平面为：
$\sum_{i=1}^N \alpha_i^* y_i(x\cdot x_i) + b^* =0$i=1∑N​αi∗​yi​(x⋅xi​)+b∗=0

支持向量和间隔边界

通过上述分析可知：支持向量是使得约束
$y_i(wx_i+b) - 1 =0$yi​(wxi​+b)−1=0
成立的点。

当$y_i=1$yi​=1 是，支持向量在超平面$H_1$H1​ 上：
$H_1:wx+b=1$H1​:wx+b=1
当$y_i=-1$yi​=−1 是，支持向量在超平面$H_2$H2​ 上：
$H_1:wx+b=-1$H1​:wx+b=−1
如下图所示：在$H_1$H1​和$H_2$H2​ 上的点就是支持向量。

$H_1$H1​和$H_2$H2​ 之间的距离称为间隔。

线性可分SVM的算法流程

输入：线性可分的m个样本${(x_1,y_1), (x_2,y_2), ..., (x_m,y_m),}$(x1​,y1​),(x2​,y2​),...,(xm​,ym​),

输出：分离超平面的参数$w^{*}$w∗和$b^{*}$b∗和分类决策函数。

(1) 构造优化问题：
$\min\limits_{\alpha} \frac{1}{2}\sum\limits_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j -\sum\limits_{i=1}^{m} \alpha_i$αmin​21​i=1,j=1∑m​αi​αj​yi​yj​xiT​xj​−i=1∑m​αi​

$s.t. \quad \sum\limits_{i=1}^{m}\alpha_iy_ix_i =0 \\ \alpha_i \geq 0, i=1,2,...,m$s.t.i=1∑m​αi​yi​xi​=0αi​≥0,i=1,2,...,m

(2) 采用SMO算法求出使得上式极小化的$\alpha^*$α∗

(3) 计算$w^{*} = \sum\limits_{i=1}^{m}\alpha_i^{*}y_ix_i$w∗=i=1∑m​αi∗​yi​xi​

(4) 找到某个满足$\alpha_j > 0$αj​>0对应的支持向量$(x_j,y_j)$(xj​,yj​)，计算：
$b^* = y_j - (w^*)^Tx_j = y_j -\sum\limits_{i=1}^{m}\alpha_i^{*}y_ix_i^Tx_j$b∗=yj​−(w∗)Txj​=yj​−i=1∑m​αi∗​yi​xiT​xj​
(5) 得到划分超平面与决策函数：
$w^{*T}x+b^* = 0 \\ f(x) = sign(w^{*T} x + b^{*})$w∗Tx+b∗=0f(x)=sign(w∗Tx+b∗)

局限性

本文介绍的是基于硬间隔最大化的样本线性可分SVM算法，对于线性不可分的数据，无法找到划分超平面，本文的算法无法使用。下一篇介绍的软间隔最大化SVM算法可以解决这个问题。