当前位置：网站首页>Chapter8 支持向量机

Chapter8 支持向量机

2022-07-30 04:16:00 【桑之未落0208】

1 理解支持向量机SVM的原理和目标（what）

1.1 原理

SVM的基本原理时在特征空间中寻找间隔最大化的分离超平面的线性分类器。

当训练样本线性可分，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机。
当训练数据近似线性可分，可引入松弛变量，通过软间隔最大化，学习一个线性分类器，即线性支持向量机。
当训练数据线性不可分，通过核函数以及软间隔最大化，学习分线性支持向量机。

1.2 目标

找出所有样本距离无数条线性函数f(x,w,b)最小的距离，再中这些距离中找出最大距离所在的那条直线，即求取w,b的值

如图所示： $f(x,w,b)=sign(w\cdot x-b)$ ，其中 w,x 代表向量。

样本距离该函数之间的距离为： $\frac{(w_{j}x^{(i)}+b_{j})y^{i}}{||w||}$

所以目标为： $w^{*},b^{*}=arg max(\underset{i=1,2...n}{min}\frac{(w_{j}x^{(i)}+b_{j})y^{i}}{||w||})$

2 掌握支持向量机的计算过程和算法步骤（how）

2.1 计算过程

假设给定一个特征空间上的训练数据集 $T={(x_{1},y_{1}),(x_{2},y_{2})...(x_{N},y_{N})}$ ，其中 $x_{i}\epsilon R^{n},y_{i}\epsilon (+1,-1),i=1,2...N$ ；

$x_{i}$ 表示为第i个实例（若n大于1，则 $x_{i}$ 为向量）；

$y_{i}$ 为 $x_{i}$ 的类标记，即当 $y_{i}=+1$ 时， $x_{i}$ 为正例，当 $y_{i}=-1$ 时 $x_{i}$ 为负例。

$(x_{i},y_{i})$ 称为样本点。

给定线性可分训练数据集，通过间隔最大化得到的分离超平面为 $y(x)=w^{T}\Phi (x)+b$ ，相应的分类决策函数 $f(x)=sign(w^{T}\Phi (x)+b)$ ，该决策函数称为线性可分支持向量机。

$\varphi (x)$ 是某个确定的特征空间转换函数，它的作用是将x映射到（最高的）维度。

求解分离超平面问题=求解相应的凸二次规划问题。

（1）根据题设 $y(x)=w^{T}\Phi (x)+b$ ，有当 $y(x_{i})>0\Leftrightarrow y_{i}=+1$ ， $y(x_{i})<0\Leftrightarrow y_{i}=-1$

从而 $y_{i}\cdot y(x_{i})> 0$ 。【 $y(x_{i})$ 为预测值 $y_{i}$ 为真实值】

按一定的比例改变w,b（此时超平面的位置不会改变，但可以使得函数间隔改变），则t*y的值同样改变，从而：

$\frac{y_{i}\cdot y(x_{i})}{||w||}=\frac{y_{i}(w^{T}\cdot \Phi (x_{i})+b)}{||w||}$ ，其中 ||w|| 为的 $L_{2}$ 范数。

目标函数： $\underset{w,b}{argmax}\left \{ \frac{1}{||w||}\underset{i}{min} [y_{i}\cdot (w^{T}\cdot \Phi (x_{i})+b)]\right \}$

(2)(假如几何距离为B，即 $\frac{y_{i}(w^{T}\cdot \Phi (x_{i})+b)}{||w||}=B$ （B为常数）

等式两边除以B：

$\frac{1}{B}\cdot \frac{y_{i}(w^{T}\cdot \Phi (x_{i})+b)}{||w||}=1$ ，此时几何距离变成了1。

通过等比例缩放w的方法，使得这两类点的函数值都满足 $|y| \geq 1$ ，即约束条件。

(3)因此原问题可以转化为以下问题:

约束条件—— $y_{i}\cdot (w^{T}\cdot \Phi (x_{i})+b)\geq 1,i=1,2,...,n$

原目标函数—— $\underset{w,b}{argmax}\left \{ \frac{1}{||w||}\underset{i}{min} [y_{i}\cdot (w^{T}\cdot \Phi (x_{i})+b)]\right \}$

新目标函数—— $\underset{w,b}{argmax}\frac{1}{||w||}$ ，即 $\underset{w,b}{max}\frac{1}{||w||}$ ，即 $\underset{w,b}{min}\frac{1}{2}||w||^{2}$

（4）所用方法：拉格朗日乘子法

设函数 $L(w,b,\alpha )=\frac{1}{2}||w||^{2}-\sum_{i=1}^{n}\alpha _{i}(y_{i}(w^{T}\cdot \Phi (x_{i})+b)-1)$

原问题是极小极大问题： $\underset{w,b}{min}\underset{\alpha }{max}L(w,b,\alpha )$

原问题的对偶问题是极大极小问题： $\underset{\alpha }{max}\underset{w,b}{min}L(w,b,\alpha )$

然后分别对 w,b 求偏导，令其为0：

$\frac{\partial L}{\partial w}=0 \Rightarrow w=\sum_{i=1}^{n}\alpha _{i}y_{i}\Phi (x_{n})$

$\frac{\partial L}{\partial b }=0\Rightarrow 0=\sum_{i=1}^{n}\alpha _{i}y_{i}$

即在 $0=\sum_{i=1}^{n}\alpha _{i}y_{i}$ 约束条件下求解：

添加负号变为求解：

2.2 举例说明

我们可以看到 $\alpha _{2}=0$ ，则 $x_{2}$ 为非支持向量。

2.3 拉格朗日乘子法

约束条件： $f_{i}(x)\leq 0,i=1,2,...,n$ ， $h_{j}(x)=0,j=1,2,...,m$

目标： min f(x)

构造函数： $G(x,\mu ,\lambda )=f(x)+\sum_{i=1}^{n}\mu _{i}f_{i}(x)+\sum_{i=1}^{m}\lambda _{j}h_{j}(x)$ ,其中 $\mu _{i}\geq 0,\lambda _{j}$ 任意值。

所以

$minf(x)=\underset{x}{min}(\underset{\mu _{i}\geq 0,\lambda \epsilon R}{max}G(x,\mu ,\lambda ))$ (原始问题)

对偶函数为 $\underset{\mu _{i}\geq 0,\lambda \epsilon R}{max}\underset{x}{min}G(x,\mu ,\lambda )$

所以接下来对 $\lambda$ 求导，使其为0。

3 理解软间隔最大化的含义

当训练数据近似线性可分，可增加松弛变量 $\xi _{i}\geq 0$ ，通过软间隔最大化，使得汉化间隔加上松弛变量大于等于1，这样约束条件就变成了 $y_{i}\cdot (w^{T}\cdot x_{i}+b)\geq 1-\xi _{i}$ ，而目标函数就变为 $\underset{w,b}{min}\frac{1}{2}||w||^{2} + C\sum_{i=1}^{N}\xi _{i}$