【机器学习】SVM初级解析

训练样本集

样本点：$D=\{(x_1, y_1), (x_2, y_2), \cdots, (x_m, y_m)\}$
样本标记：$y_i=\{-1, +1\}$

划分超平面

$w^Tx+b=0$

其中$\color{red}{w}$为垂直于超平面的法向量；

支持向量

假设超平面$(w, b)$可以将样本正确分类，存在$(x_i, y_i)\in D$，使得：

$\begin{cases}y_i=+1, &w^Tx_i+b>0\\y_i=-1, &w^Tx_i+b<0\end{cases}$

若超平面能将样本正确分类，则存在w和b的缩放变换

$\begin{cases}w^Tx_i+b\ge+1, &y_i=+1\\w^Tx_i+b\le-1, &y_i=-1\end{cases}\tag1$

距离超平面最近的几个样本点，使(1)式成立，这些样本点被称为“支持向量”，其符合条件：

$y_i(w^Tx_i+b)=1$

最大间隔

根据点到直线的距离公式，任意样本点到超平面的距离为：

$r=\frac{|w^Tx+b|}{\Vert w\Vert}$

正负样本支持向量到超平面距离之和：

$\begin{aligned} \gamma&=r_++r_-\\&=\frac{|+1|}{\Vert w\Vert}+\frac{|-1|}{\Vert w\Vert}\\ &=\frac2{\Vert w\Vert} \end{aligned}$

使$\gamma$最大化，寻找到具有“最大间隔”的划分超平面

$\begin{aligned} &\underset{w, b}{max}\frac2{\Vert w\Vert}\\ &s.t.\ y_i(w^Tx_i+b)\ge1, i=1, 2, \cdots, m \end{aligned}$

SVM基本模型

最大化$\Vert w\Vert^{-1}$等价于最小化$\Vert w\Vert^2$，所以整理公式得：

$\begin{aligned} &\underset{w, b}{min}\frac12\Vert w\Vert^2\\ &s.t.\ y_i(w^Tx_i+b)\ge1, i=1, 2, \cdots, m \end{aligned}\tag2$

该式的意义：在保障超平面正确分类的前提条件下，支持向量离超平面越远越好。
该式的表述状态满足拉尔朗日乘子法的优化要求，但因为约束条件是不等式，该式需满足KKT条件

对偶问题：拉格朗日乘子法

使用拉格朗日乘子法，可使(2)式中对$w, b$最小化问题转化为对偶问题，即：

$\underset{w, b}{min}\ \underset{\alpha}{max}L(w, b, \alpha)=\underset{\alpha}{max}\ \underset{w, b}{min}L(w, b, \alpha)$

对(2)式中的条件约束添加拉格朗日乘子$\alpha_i\ge0$，因为是约束条件，所以构造的条件函数必须是小于0的形式：

$L(w, b, \alpha)=\frac12\Vert w\Vert^2+\sum_{i=1}^m\alpha_i[1-y_i(w^Tx_i+b)]\tag3$

因为是不等值约束，(3)式需满足KKT条件：

$\begin{cases}\alpha_i\ge0 &\text{乘子基本条件}\\ y_i(w^Tx_i+b)-1\ge0 &\text{约束基本条件}\\ \alpha_i[y_i(w^Tx_i+b)-1]=0 &\text{原函数与约束函数正交边界} \end{cases}$

因为是求最小化的问题，那么令$L(w, b, \alpha)$对$w$和$b$的偏导为0，得：

$\tag{4} \frac{\partial L(w, b, \alpha)}{\partial w}=w-\sum_{i=1}^m\alpha x_iy_i=0$

$\tag{5} \frac{\partial L(w, b, \alpha)}{\partial b}=\alpha_iy_i=0$

将(5)式带入(3)式中化简，得：

$\begin{aligned} L(w, b, \alpha) &=\frac12\sum_{i=1}^m\alpha_i x_iy_i\sum_{j=1}^m\alpha_j x_jy_j-\sum_{i=1}^m\alpha_i x_iy_i\sum_{j=1}^m\alpha_j x_jy_j+\sum_{i=1}^m\alpha_i-\sum_{i=1}^m\alpha_iy_ib \\ &=\sum_{i=1}^m\alpha_i-\frac12\sum_{i=1}^m\alpha_i x_iy_i\sum_{j=1}^m\alpha_j x_jy_j \qquad \text{将(4)式带入}\\ &=\sum_{i=1}^m\alpha_i-\frac12\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_j y_iy_jx_i^Tx_j\ \qquad \textcolor{blue}{s.t.\sum_{i=1}^m\alpha_iy_i=0, \alpha_i\ge0, i=1, 2, \cdots, m} \end{aligned}$

从KKT条件可以看出，对于任意训练样本集$(x_i, y_i)$，总有两情况：

• 当$\alpha_i=0$时，样本点满足 $y_i(w^Tx_i+b)>1$，即样本点在支持向量所构成的超平面以外。
• 当$y_i(w^Tx_i+b)=0$时，样本点就是支持向量。