线形可分支持向量机

Posted on

支持向量机

定义在特征空间上的间隔最大的线形分类器，核技巧使得它称为事实上的非线性分类器。核函数表示将输入从输入空间映射到特征空间，得到的特征向量的内积。

线形可分支持向量机

给定线形可分训练机，通过间隔最大化或等价求解凸二次规划，得到分离超平面：
$$
w^0 \cdot x + b^0 = 0
$$

以及相应的分类决策函数：
$$
f(x)=sign(w^0\cdot x+b^0)
$$
称为线形SVM。

函数间隔

定义超平面关于样本点的函数间隔为：
$$
\hat{\gamma}_i = y_i(w\cdot x_i+b)
$$

超平面$(w,b)$关于训练集$T$的函数间隔：
$$
\hat{\gamma}=\min\limits_{i=1,\dots,N} \hat{\gamma}_i
$$

点$x_i$与超平面$(w,b)$之间的距离（几何间隔）：
$$
\gamma_i=y_i(\frac{w}{||w||}\cdot x_i + \frac{b}{||w||})
$$

其中$||w||$为$w$的$L_2$范数。

$(w,b)$关于$T$的几何间隔：
$$
\gamma=\min\limits_{i=1,\dots,N}\gamma_i
$$

易知$\gamma_i=\frac{\hat\gamma_i}{||w||}$，$\gamma=\frac{\hat\gamma}{||w||}$

间隔最大化

$$
\max\limits_{w, b} \gamma
$$

$$
s.t. y_i(\frac{w}{||w||}x_i+\frac{b}{||w||}) \ge \gamma, i=1,\dots,N
$$

或：
$$
\max\limits_{w,b} \frac{\hat\gamma}{||w||}
$$
$$
s.t. y_i(w\cdot x_i+b)\ge \hat\gamma, i=1,\dots,N
$$

或：
$$
\min\limits_{w,b} \frac{1}{2}||w||^2
$$
$$
s.t. y_i(w\cdot x_i+b) -1 \ge 0, i=1,\dots,N
$$

线形可分支持向量机——最大间隔法

输入：训练集$t={(x_1,y_1),\dots,(x_N,y_N)}$（二分类）

输出：最大间隔分离超平面和决策函数

  1. 构造并求解最优化问题
    $$
    \min\limits_{w,b} \frac{1}{2}||w||^2
    $$
    $$
    s.t. y_i(w\cdot x_i+b) -1 \ge 0, i=1,\dots,N
    $$
    求得最优解$w^0,b^0$

  2. 由此得到分离超平面：
    $$
    w^0\cdot x+b^0 =0
    $$
    分类决策函数：
    $$
    f(x)=sign(w^0x+b^0)
    $$

线形可分数据集的最大间隔分离超平面是存在且唯一的。

支持向量

在线形可分的情况下，训练数据集的样本点中与分离超平面最近的样本点的实例称为支持向量。

支持向量：$y_i(w\cdot x_i+b)-1=0$

对于$y_i=+1$的点，支持向量在超平面$H_1:w\cdot x+b=1$上。

对于$y_i=-1$的点，支持向量在超平面$H_2:w\cdot x+b=-1$上。

线形可分支持向量机的对偶算法

应用拉格朗日对偶性，求解对偶问题，得到原始问题的最优解。

定义拉格朗日函数：
$$
L(w,b, \alpha) = \frac{1}{2} ||w||^2 - \sum\limits_{i=1}^{N} \alpha_i y_i (w\cdot x_i + b) + \sum\limits_{i=1}^{N} \alpha_i
$$
其中$\vec\alpha=(\alpha_1,\dots,\alpha_N)^T$为拉格朗日乘子向量。

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：
$$
\max\limits_{\alpha} \min\limits_{w,b} L(w, b, \alpha)
$$

首先对$(w, b)$求最小：
$$
\min\limits_{w,b} L(w, b, \alpha) = - \frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + \sum\limits_{i=1}^{N}\alpha_i
$$

对上式求对$\alpha$的极大：
$$
\min\limits_{\alpha} \frac{1}{2}\sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_i\alpha_i y_iy_j (x_i \cdot x_j) - \sum\limits_{i=1}^{N}\alpha_i
$$

$$
s.t. \sum\limits_{i=1}^{N}\alpha_iy_i=0, \alpha_i\ge 0, i=1, \dots, N
$$

如果$\alpha^0=(\alpha^0_1, \dots, \alpha^0_l)^T$是上述对偶最优化问题的解，则存在下标$j$，使得$\alpha^0_j \ge 0$，并可按下式求得原始最优化问题的解$w^0,b^0$：
$$
w^0 = \sum\limits_{i=1}^{N} \alpha^0_iy_ix_i
$$
$$
b^0=y_j - \sum\limits_{i=1}^{N} \alpha^0_iy_i(x_i \cdot x_j)
$$

于是有分离超平面：
$$
\sum\limits_{=1}^{N} \alpha^0_i y_i (x \cdot x_i) + b^0 = 0
$$

分类决策函数：
$$
f(x)=sign(\sum\limits_{i=1}^{N} \alpha^0_i y_i (x \cdot x_i) + b^{*})
$$