SVM(2) 之 线性可分支持向量机学习方法
in 统计学习原理 with 0 comment

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

in 统计学习原理 with 0 comment

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


线性可分支持向量机

首先,考虑一下原始问题

我们其实是想找出一个分割面来,把两个空间的元素一一分开。
假设,这个分割面为:
$$w^*·x+b^* = 0$$

间隔

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

预备知识

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

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

函数间隔

对于一个训练样本$(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}$$

$$\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^{*})$$

Responses

From now on, bravely dream and run toward that dream.
陕ICP备17001447号