SVM(2) 之线性可分支持向量机学习方法

2018-09-14 本文已影响20人 mmmwhy

上一篇大概讲了一下拉格朗日对偶法以及KKT条件，这一篇推导一下SVM的公式。下一篇举个例子，差不多就结束了。

线性可分支持向量机

首先，考虑一下原始问题

我们其实是想找出一个分割面来，把两个空间的元素一一分开。
假设，这个分割面为：

接下来的很多地方会看到这个式子的影子。

函数间隔

前提
一般来说，一个点距离分离超平面的远近可以表示分类预测的确定成都，即距离越远，越确定，距离越近，越不确定。
距离
给定分割平面： $w·x+b = 0$ ，那么把点 $x$ 代入 $|w·x+b|$ 其实就是点x距离超平面的距离。(回忆一下预备知识上边那个式子)
概念
$w·x+b$ 与标记 $y$ 的符号是否一致，表示分类是否正确。所以可以使用 $y(w·x+b)$ 表示分类正确性及确信度。

对于一个训练样本 $(x^{(i)}, y^{(i)})$ , 我们定义它到超平面 $(w,b)$ 的函数间隔为:
$\hat{\gamma}_i=y_{i}(w^Tx_{i}+b)$
超平面的定义，其实只需要最核心部分的向量，就是被称作支持向量的点。
$\hat{\gamma}_i=\min_i\hat{\gamma}_{i}.$

几何间隔

$\gamma_{i}=y_{i}(\frac{w^T}{\Vert w\Vert}x_{i}+\frac{b}{\Vert w\Vert})$
同样的
$\gamma=\min_i\gamma_{i}$

那么几何间隔与函数间隔是什么关系呢?
$\gamma^{(i)}=\frac{\hat{\gamma}^{(i)}}{\Vert w\Vert}$ 增加了一个 $||w||$ 保证函数间隔不会乱跑

间隔最大化

原始约束最优化问题

最大间隔超平面
我们的目标是求得一个几何间隔最大的超平面，即最大间隔超平面。

$\begin{align} \max_{w,b} &\quad \gamma \\ \\ s.t. &\quad y_{i}(\frac{w}{\Vert w\Vert}\cdot x_i+ \frac{b}{\Vert w\Vert})\ge\gamma, \quad i=1,2,…,N \\ \end{align}$

几何间隔换成函数间隔

因为几何间隔太复杂 ( 其实就是为了一会推公式方便
$\begin{align} \max_{w,b} &\quad \frac{\hat{\gamma}}{\Vert w\Vert} \\ \\ s.t. &\quad y_{i}({w}\cdot x_i+ {b})\ge\hat{\gamma}, \quad i=1,2,…,N \\ \end{align}$

令 $\hat{\gamma}＝1$
因为函数间隔取多少，并不影响该 最优化问题，又由于最大化 $\frac{1}{\Vert w\Vert}$ 与最小化 $\frac{1}{2}\Vert w\Vert^2$ 是等价的，于是可获得
$\begin{align} \min_{w,b} &\quad {\frac12}||w||^2 \\ \\ s.t. &\quad y_{i}(w\cdot x_{i}+b)-1\ge 0 \end{align}$

为什么要搞这么多次变换，因为拉格朗日乘子法的结构限制，详情见SVM(1) 之拉格朗日乘子法和KKT条件

需要注意的一点是这里是 $\ge$ ，使用拉格朗日算子法的时候留意。

对偶算法

拉格朗日函数

首先构造拉格朗日函数

$\mathcal{L}(w, b, \alpha)=\frac12||w||^2-\sum_{i=1}^m\alpha_i[y^{(i)}(w^Tx^{(i)}+b)-1].$

这里负号和注意有关

$\min_{w,b}\mathcal{L}(w,b,\alpha)$

$\frac{\partial\mathcal{L}}{\partial w}=w-\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}=0, \\ \frac{\partial\mathcal{L}}{\partial b}=0-\sum_{i=1}^m\alpha_iy^{(i)}=0$
得
$w=\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}, \\ \sum_{i=1}^m\alpha_iy^{(i)}=0$

再将求得的 $w$ 带回 $\mathcal{L}(w,b,\alpha)$ 可得到 $\mathop\min_{w,b}\mathcal{L}(w,b,\alpha)$
$\begin{align} & \mathop\min_{w,b}\mathcal{L}(w,b,\alpha) \\ & =\frac12(\sum_i^m\alpha_iy_ix_i)(\sum_j^m\alpha_jy_jx_j) - (\sum_i^m\alpha_iy_ix_i)(\sum_j^m\alpha_jy_jx_j)+(\sum_i^m\alpha_iy_ib) + \sum_i^m\alpha_i \\ & = -\frac12(\sum_i^m\alpha_iy_ix_i)(\sum_j^m\alpha_jy_jx_j) + b\sum_i^m\alpha_iy_i + \sum_i^m\alpha_i \\ & = \sum_i^m\alpha_i - \frac12\sum_i^m\sum_j^m\alpha_i\alpha_jy_iy_jx_i^Tx_j \\ & = \sum_i^m\alpha_i - \frac12\sum_i^m\sum_j^m\alpha_i\alpha_jy_iy_j\langle x_i,x_j\rangle \end{align}$

$\max_{\alpha}\min_{w,b}\mathcal{L}(w,b,\alpha)$

$\left \{ \begin{split} \max \limits_{\alpha} & -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i \cdot x_j) + \sum_{i=1}^N \alpha_i \\ s.t. & \sum_{i=1}^N \alpha_i y_i = 0 \\ & \alpha_i \ge 0, i = 1,2,\cdots,N \end{split} \right.$
将极大转换成极小，得到下面与之等价的对偶最优化问题：
$\begin{equation} \left \{ \begin{split} \min \limits_{\alpha} & \frac{1}{2}\sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i \cdot x_j) - \sum_{i=1}^N \alpha_i \\ s.t. & \sum_{i=1}^N \alpha_i y_i = 0 \\ & \alpha_i \ge 0, i = 1,2,\cdots,N \end{split} \right. \end{equation}$

原始问题对 $w$ 求导的时候得到了第一个式子，把第一个式子带回 $wx+b=y$ 得到第二个式子
$\begin{equation} \left \{ \begin{split} w^{*} &= \sum_{i=1}^N \alpha_i^{*} y_i x_i \\ b^{*} &= y_j - \sum_{i=1}^N \alpha_i^{*} y_i (x_i \cdot x_j) \end{split} \right. \end{equation}$

综上所述，对于给定的线性可分训练数据集，可以首先求对偶问题(2)的解 $\alpha^{*}$ ；再利用上式求得原始问题的解 $w^{*},b^{*}$ ；从而得到分离超平面及分类决策函数。这种算法称为线性可分支持向量机的对偶学习算法，是线性可分支持向量机学习的基本算法。

小结：线性可分支持向量机对偶学习算法

输入：线性可分训练数据集
$T = \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N) \}$
其中， $x_i \in R^n, y_i \in \{+1,-1\}, i = 1,2,\cdots, N$ 。

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

(1) 构造并求解约束最优化问题：
$\left \{ \begin{split} \min \limits_{\alpha} & \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j(x_i \cdot x_j) - \sum_{i=1}^N \alpha_i \\ s.t. & \sum_{i=1}^N \alpha_i y_i = 0 \\ & \alpha_i \ge 0, i = 1,2,\cdots,N \end{split} \right.$
用SMO算法求 $\alpha^{*}=(\alpha_1^{*},\alpha_2^{*},\cdots,\alpha_N^{*})^T$