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

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

线性可分支持向量机

首先,考虑一下原始问题

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

间隔

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

预备知识

设直线 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)$的函数间隔为:

超平面的定义,其实只需要最核心部分的向量,就是被称作支持向量的点。

几何间隔

同样的

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

间隔最大化

原始约束最优化问题

  • 最大间隔超平面
    我们的目标是求得一个几何间隔最大的超平面,即最大间隔超平面。
  • 几何间隔 换成 函数间隔

    因为几何间隔太复杂 ( 其实就是为了一会推公式方便

  • 令 $\hat{\gamma}=1$
    因为函数间隔取多少,并不影响该 最优化问题,又由于最大化$\frac{1}{\Vert w\Vert}$ 与最小化 $\frac{1}{2}\Vert w\Vert^2$ 是等价的,于是可获得

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

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

对偶算法

拉格朗日函数

首先构造拉格朗日函数

这里负号和注意 有关

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

再将求得的$w$带回$\mathcal{L}(w,b,\alpha)$可得到$\mathop\min_{w,b}\mathcal{L}(w,b,\alpha)$

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

将极大转换成极小,得到下面与之等价的对偶最优化问题:

原始问题对$w$求导的时候得到了 第一个式子,把第一个式子带回$wx+b=y$得到第二个式子

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

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

输入:线性可分训练数据集

其中,$x_i \in R^n, y_i \in {+1,-1}, i = 1,2,\cdots, N $ 。

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

(1) 构造并求解约束最优化问题:

用SMO算法求 $\alpha^{}=(\alpha_1^{},\alpha_2^{},\cdots,\alpha_N^{})^T$

(2 )计算

(3) 求得分离超平面

分类决策函数:

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

https://iii.run/archives/dde355d78ff3.html

作者

mmmwhy

发布于

2018-09-14

更新于

2022-10-30

许可协议

评论