上一篇大概讲了一下拉格朗日对偶法以及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^{*})$$
本文由 mmmwhy 创作，最后编辑时间为: Sep 14, 2018 at 03:24 pm