SVM：线性可分支持向量机与硬间隔最大化

2018-12-05 本文已影响0人 HilaryQiao

SVM（support vector machine）：是一种二分类模型，将训练数据映射到特征空间中，通过超平面将样本一分为二的有监督学习方法。
数学定义：假定特征空间中的训练集
$T=\left \{\left ( x_{1},y_{1} \right ),...,(x_{i},y_{i}),...,(x_{n},y_{n}) \right \}$ ，其中， $x_{i}$ 是第i个样本的属性在特征空间的映射称为特征向量； $y_{i}\in \left \{-1,+1\right \}$ ，-1称为负类，+1称为正类； $(x_{i},y_{i})$ 称为样本点。假定此训练集是线性可分的，SVM的学习目标就是找到特征空间中的一个超平面，将训练集一分为二。如图所示：

图1：超平面将训练集一分为二

SVM的学习模型分为三种（由简至繁）：

图2：三种SVM模型从上到下有简至繁

一、线性可分支持向量机

定义：通过给定的线性可分训练集T，学习得到分类的超平面：
$y = w * x + b$ ，
从而得到决策函数：
$y = sign(w * x + b)$ ，称决策函数为线性可分支持向量机。

从定义可知，学习目标是确定参数w, b，如何确定w, b就是本文所要解决的问题。
分割训练集的超平面可以有很多，我们是选择 $H_{1} 还是 H_{2}、H_{3}？$

图3：如何确定分割训练集的超平面
我们通过求间隔最大的超平面来确定参数w, b。

问题：为什么要求间隔最大的超平面？
解答：在图1中有A、B、C三个样本点，均为正实例。其中，A距离超平面最远，那么A被划分为正例的确信度高。C距离超平面距离最近，那么C被划分为正例的确信度低。B介于AC之间，确信度也处于AC之间。因此，想要更好的划分训练集，应该寻求训练集到超平面的间隔最大化。

1.函数间隔、几何间隔、间隔最大化

上面说到一个实例距离超平面的远近可以用于度量分类预测的确信度，即
在超平面确定的情况下，可用 $| w * x + b|$ （点到直线的距离）表示分类的准确度。同时， $w*x_{i} + b$ 与 $y_{i}$ 的符号是否一致判断分类的正确性。因此可以用 $y(wx + b)$ 度量分类预测的正确性与确信度，这就是函数间隔。

函数间隔：对于给定超平面 $y = wx + b$ 与训练集T，

超平面（w, b）关于样本点 $(x_{i},y_{i})$ 的函数间隔：
$\widehat{\gamma_{i} } = y_{i}(w*x_{i} + b)$

超平面（w, b）关于训练集T的函数间隔：
$\widehat{\gamma }=min_{1...N} \ \ \widehat{\gamma_{i} }$
即找到所有样本点中距离超平面最近的那个点的函数间隔作为整个训练集的函数间隔

但是要想找到最好的超平面，仅仅知道函数间隔是不够，因为w , b 可以成比例改变比如（kw, kb）, 那么函数间隔就变为 $k\widehat{\gamma }$ 。为了找到确定的超平面，考虑规范化，即
$\widehat{\gamma_{i} } = y_{i}(\frac{w}{\left \| w \right \|}*x_{i} + \frac{b}{\left \| w \right \|})$

图4：几何间隔

几何间隔：对于给定超平面 $y = wx + b$ 与训练集T，

超平面（w, b）关于样本点 $(x_{i},y_{i})$ 的几何间隔：
$\gamma_{i} = y_{i}(\frac{w}{\left \| w \right \|}*x_{i} + \frac{b}{\left \| w \right \|})$

超平面（w, b）关于训练集T的几何间隔：
$\gamma =min_{1...N} \ \gamma_{i} =min_{1...N} \ \ \widehat{\frac{\gamma_{i}}{\left \| w \right \|} }$
即找到所有样本点中距离超平面最近的那个点的几何间隔作为整个训练集的几何间隔。

上面几何间隔也给出了几何间隔与函数间隔关系。w, b 成比例变化 $\widehat{\gamma}$ 成比例变化，但是几何间隔并不变化。

支持向量机学习的基本思想：求解能够正确划分训练集并且能够最大化几何间隔的超平面。
直观来说就是不仅要能够正确分类而且还要把最难分的点也能分清楚。比如图3中 $H_{2}，H_{3}$ 都能正确划分训练集，但是有部分样本点距离 $H_{2}$ 非常近容易划分错误，所以 $H_{3}$ 是最好的选择。

学习目标：最大化间隔
$\max_{(w,b)} \quad \gamma\quad;\\ \gamma_{i} = y_{i}(\frac{w}{\left \| w \right \|}*x_{i} + \frac{b}{\left \| w \right \|})>=\gamma$

目标是最大化几何间隔，同时该间隔要作为训练集的几何间隔，这也是这个最优化问题的约束条件。
有了学习目标，考虑构建 $\gamma与w，b$ 之间的关系，找到能够最大化γ的w, b值，就可以确定超平面了。因此，学习目标可以转化为

学习目标：最大化间隔
$\max_{(w,b)} \quad \widehat{\frac{\gamma}{\left \| w \right \|} }\quad;\\ y_{i}(w*x_{i} + b)>=\widehat\gamma$

之前说过函数间隔 $\widehat{\gamma}$ 变化并不影响几何间隔，即不影响最优化的结果。因此，这里可以设置 $\widehat{\gamma} = 1$ 。至此，得到了最终的学习目标：

学习目标：最大化间隔
$\max_{(w,b)} \quad {\frac{1}{\left \| w \right \|} }\quad;\\ y_{i}(w*x_{i} + b)>=1$

求解最优化问题的方法，这里通过构建拉格朗日函数求解最优解。不使用梯度下降法的原因是此时解空间是受约束的。接下来介绍最优解的求解过程。

SVM：线性可分支持向量机与硬间隔最大化

一、线性可分支持向量机

1.函数间隔、几何间隔、间隔最大化

猜你喜欢

热点阅读