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

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

线性可分支持向量机

首先，考虑一下原始问题

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

$$w^*·x+b^* = 0$$

间隔

间隔分为两种，函数间隔和几何间隔。

预备知识

设直线 L 的方程为 $Ax+By+C=0$，点 P 的坐标为$（X_0,Y_0）$，则点 P 到直线 L 的距离为

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

函数间隔

• 前提
  一般来说，一个点距离分离超平面的远近可以表示分类预测的确定成都，即距离越远，越确定，距离越近，越不确定。
• 距离
  给定分割平面： $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$

(2 )计算

$$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)$$

(3) 求得分离超平面

$$w^{*} \cdot x + b^{*} = 0$$

分类决策函数：

$$f(x) = sign(w^{*} \cdot x + b^{*})$$