机器学习算法_支持向量机SVM(1)

2019-09-27 本文已影响0人皮皮大

SVM支持向量机

简介

SVM(support vector machine)是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使其区别于感知机，感知机只是找到一个分离超平面。

SVM是非线性分类器
学习策略：间隔最大化，等价于求解凸二次规划问题或者说正则化的合页损失函数的最小化问题
学习算法：求解凸二次规划的最优化算法

线性可分支持向量机

思想

学习目标：在特征空间中找到一个分离超平面S，由 $w \bullet x+b=0$ 决定，将实例分成不同的正类和负类
$w$ 是法向量， $b$ 是截距。法向量指向的那侧是正类，另一侧是负类
通过间隔最大化求出的分离超平面具有唯一性

定义线性可分支持向量机

分离超平面 $w^* \bullet x+b^* =0$
分类决策函数
- 到决策函数的距离大于1，表示正类
- 到决策函数的距离小于1，表示负类

函数间隔和几何间隔

一个点到分离超平面的距离可以表示分类预测的确信程度。通常使用 $|w \bullet x+b|$ 来表示点x到超平面的远近

$w \bullet x+b > 0，y = +1$ 或者 $w \bullet x+b < 0，y = -1$ 都表示将将数据正确分类：即 $w \bullet x+b$ 和类标记 $y$ 的符号是一致的
在给定数据集T，超平面 $(w,b)$ 关于样本点 $(x_i,y_i)$ 的函数间隔： $\hat \gamma_i=y_i(w \bullet x_i+b)$ 定义：超平面 $(w,b)$ 关于训练数据集T的函数间隔，为所有T中样本点的函数间隔的最小值： $\hat \gamma=\mathop {\min}\limits_{i=1,2,...,N} \hat \gamma_i$

函数间隔表示分类预测的准确性和确信度。当 $w,b$ 成比例的变化时，超平面并没有变化，因此需要规范化，加上 $||w||$ ，此时变成了几何间隔。

$几何间隔=\frac {函数间隔} {||w||}$

点到超平面的距离

设样本点A到超平面 $(w,b)$ 的距离为 $\gamma_i$

如果点在超平面正的一侧，即： $y_i = +1$ ，距离为： $\gamma_i=\frac {w \bullet x_i+b} {||w||}$
如果点在超平面负的一侧，即： $y_i = -1$ ，距离为： $\gamma_i=-(\frac {w \bullet x_i+b} {||w||})$

统一地：当样本点被超平面正确分类时，点到超平面的距离为 $\gamma_i=y_i(\frac {w \bullet x_i+b} {||w||})$ 那么，当 $||w||=1$ 时候，函数间隔和几何间隔是相等的。

如果 $w,b$ 等比例的变化，函数间隔相应的变化，但是几何间隔是不变的

间隔最大化

支持向量机学习的基本思想是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。几何间隔最大的分离超平面是唯一的。这里的间隔最大化称之为硬间隔最大化。

硬间隔最大化不仅能够将正负实例点分开，还能将最难分的实例点（距离超平面最近的点）也能分开，对应的模型为 $\mathop {\max} \limits_{w,b}\gamma$
$s.t. \qquad y_i({w \bullet x_i+b}{||w||}) \geq {\gamma}$ 意思：

最大化几何间隔
约束条件表示的是超平面关于每个训练样本点的距离至少是 $\gamma$

根据函数间隔和几何间隔的关系 ${\gamma}=\frac {\hat \gamma}{||w||}$ ，模型还可以表示为： $\mathop {\max} \limits_{w,b}\frac {\hat \gamma}{||w||}$
$s.t. \qquad y_i(w \bullet x_i+b) \geq {\hat \gamma}$

函数间隔不影响模型，就取 $\hat \gamma=1$ ，那么最小化 $\frac {1}{||w||}$ 和最小化 $\frac{1}{2}||w||^2$ 等价（ $\frac{1}{2}$ 方便求导）

线性可分支持向量机的最优化问题可以表示为凸二次优化问题：

最小化法向量： $\mathop \min \limits_{w,b}\frac{1}{2} ||w||^2$

约束条件： $s.t. \qquad y_i(w \bullet x_i+b) \geq 0,i=1,2,...,N$ 求解出上述两个的式子的解 $w^*,b^*$ 就可以求出分离超平面 $w^* \bullet x+b^*$ 和决策函数 $f(x)=sign(w^* \bullet x+b^*)$

对偶问题

将线性可分支持向量机的最优化问题，通过拉格朗日对偶性，转换成求解对偶问题，得到对偶问题的最优解

对偶问题更好求解
自然引入核函数，推广到非线性支持向量机

如何构建对偶形式：

引入拉格朗日乘子 $alpha_i \geq 0, i=1,2,3...,N$ ，构建拉格朗日函数： $L(w,b,\alpha)=\frac{1}{2}||w||^2 - \sum^N_{i=1}\alpha_iy_i(w \bullet x_i+b)+\sum ^N_{i=1}\alpha_i$ 其中 $\alpha=(\alpha_1,\alpha_2,...,\alpha_N)^T$ 为拉格朗日乘子向量
原始问题的对偶问题是极大极小问题 $\mathop \max \limits_a \mathop \min \limits_{b,\alpha} L(w,b,\alpha)$
$L$ 先对 $w,b$ 求解极小，再对 $\alpha$ 求解极大值
具体过程见 $P_{120}-P_{123}$