支持向量机-算法概述

2020-02-20  本文已影响0人  shenny_

​ 我的微信公众号: s406205391; 欢迎大家一起学习,一起进步!!!

​ 有些人认为,支持向量机(SVM)是最好的现成的分类器,这里说的“现成”指的是分类器不加修改即可直接使用。同时,这就意味着在数据上应用基本形式的SVM分类器就可以得到低错误率的结果。SVM能够对训练集之外的数据点做出很好的分类决策。

距离的定义:基于最大间隔分隔数据

​ 假设在一个平面上有如下两组数据,我们可以用如下一条直线将两组数据分隔开(我们将上述可以把数据集分隔开的直线称为分隔超平面)。图左和图右两条直线均可有效的将数据分隔开。那么,哪一条直线的分隔效果更好呢?很明显图右的直线分隔效果更好,因为它距离两组数据的距离相对于图左直线更远。支持向量就是离分隔超平面最近的那些点

image

​ 那么,我们在设计分类器之前,就先得学会如何计算支持向量到分隔超平面之间的距离。假设由图点x是分隔超平面的支持向量,w是超平面上的法向量,w'和w''是超平面上的两个点。我们定义超平面方程为wTx+b=0。那么我们可以得到两个等式:

image

优化目标: 找到一条线(w和b),是的离该线最近的点能够最远

​ 有了距离公式,那么也有了我们机器学习的优化方向:让支持向量与超平面的距离最远。在做SVM机器学习的时候,我们首先需要定义标签,即将我们的训练数据进行分类。在这里,为了后期计算方便,我们将数据分类两类,分别用1和-1表示。那么就有了如下的决策方程:

y(x)=w^{T}\phi(x)+b \Rightarrow \begin{aligned}y(x_{i})>0 &\Leftrightarrow y_{i}=+1\\ y(x_{i})<0&\Leftrightarrow y_{i}=-1\end{aligned} \Rightarrow y(i) \cdot y(x_{i})>0 这里的φ(x)我们可以先暂时理解为x

将距离公式带入到决策方程,可得:\frac{y_{i} \cdot (w^{T} \cdot \phi(x_{i}) + b)}{||w||} (由于y_{i} \cdot y(x_{i})>0, 所有将绝对值展开,公式依旧成立。)

对于该决策方程,我们设计优化目标,找到一条离支持向量的点最远的直线,优化目标如下:

目标函数: argmax_{w,b}\left\{ \frac{1}{||w||} min[y_{i} \cdot (w^{T} \cdot \phi(x_{i} + b))] \right \}

求解目标函数

​ 上述的目标函数看起来很复杂,通俗的将,大括号内的意思即为,找到在整个样本中,距离决策边界距离最小的样本。大括号外面即,找到与这些这些样本距离最大的线。

放缩变换

​ 对于决策方程,不太好求解,我们这里可以做一下变换。我们通过放缩变换使得:对于决策方程(w,b),其结果|y|>=1 \Rightarrow y_{i} \cdot (w^{T} \cdot \phi(x_{i}) + b) >= 1 (之前我们认为恒大于0,现在更严格了一些)

由于y_{i} \cdot (w^{T} \cdot \phi(x_{i}) + b) >= 1 , 那么,其最小值就为1,那么,我们只需要考虑argmax_{w,b} \frac{1}{||w||}

当前目标max_{w,b} \frac{1}{||w||},约束条件:y_{i} \cdot (w^{T} \cdot \phi(x_{i}) + b) >= 1

函数变换

​ 对于上述目标函数,我们适当转换一下,方便求解。我们可以将上述函数的求最大值问题,改为求极小值问题:

转换函数 \Rightarrow min_{w,b} \frac{1}{2}w^{2}

​ 转换思路为:先将\frac{1}{||w||}转换成其倒数,再取其平方,再添加一个常规项1/2。虽然做了如下操作之后,最后得到的点的值会发生变换,但是,取到的点是不变的

对于这个函数,我们可以用拉格朗日乘子法求解

求解拉格朗日乘子法

拉格朗日乘子法是专门用来求解带约束条件的问题的。他的基本公式为:

min L(x, \lambda,w)=f_{0}(x) + \Sigma{\lambda_{i}f_{i}(x)} + \Sigma{v_{i}h_{i}(x)}

​ 把我们的方程代入,即得:

L(w,b,\alpha)= \frac{1}{2}||w||^{2} - \Sigma{\alpha_{i}(y_{i}(w^{T} \cdot \phi(x_i) +b)-1)} 约束条件:{y_i(w^T \cdot \Phi(x_i) + b)>=1}

​ 上式有三个未知量,w, α,b。如果我们能求得这三个变量之间的关系,即可得到方程的解。我们分别对w和b求偏导,得:

对w求偏导:\frac{\partial L}{\partial w}=0 \Rightarrow w=\sum\limits_{1-n} {\alpha_{i}y_{i}\Phi(x_n)}

对b求偏导:\frac{\partial L}{\partial b}=0 \Rightarrow 0=\sum\limits_{1-n}{\alpha_{i}y_{i}}

我们带入原式即得:

L(w,b,\alpha)= \frac{1}{2}||w||^{2} - \Sigma{\alpha_{i}(y_{i}(w^{T} \cdot \phi(x_i) +b)-1)}

​ 其中:w=\sum\limits_{1-n} {\alpha_{i}y_{i}\Phi(x_n)}; 0=\sum\limits_{1-n}{\alpha_{i}y_{i}}

=\frac{1}{2}w^{T}w-w^{T}\sum\limits_{i=1}\limits^{n}\alpha_{i}y_{i}\Phi(x_{i}) - b\sum\limits_{i=1}\limits^{n}\alpha_{i}y_{i} + \sum\limits_{i=1}\limits^{n}\alpha_{i}

=\sum\limits_{i=1}\limits^{n}\alpha_{i} - \frac{1}{2}(\sum\limits_{i=1}\limits^{n}\alpha_{i}y_{i}\Phi(x_{i})^T\sum\limits_{i=1}\limits^{n}\alpha_{i}y_{i}\Phi(x_{i}) 完成了第一步求解minL(w,b,α)

=\sum\limits_{i=1}\limits^{n}\alpha_{i} - \frac{1}{2}\sum\limits_{i=1,j=1}\limits^{n}\alpha_{i}\alpha_{j}y_i y_j \Phi^T(x_i)\Phi^T(x_j) 求解该式的极值

继续求解

​ 我们需要求解上式的极大值,添加一个符号,我们转换为求解该式的极小值。

即: \frac{1}{2}\sum\limits_{i=1,j=1}\limits^{n}\alpha_{i}\alpha_{j}y_i y_j \Phi^T(x_i)\Phi^T(x_j) - \sum\limits_{i=1}\limits^{n}\alpha_{i}; 条件:\sum\limits_{i=1}\limits^n \alpha_i yi = 0; \alpha_i >= 0

实例求解

我们现在以一个实例,求解上述方程。

image

​ 我们将上面数据代入即可得:


image

对α1和α2求偏导即可得: \alpha_1 = 1.5; \alpha_2 = -1

这里,α2小于0,不满足约束条件,所以应该在边界上。此时α1=0或者α2=0.

image

将α结果代入求解:w=\sum\limits_{i=1}\limits^n \alpha_i y_i |Phi(x_n); 平面方程为:0.5x_1 + 0.5x_2 -2 = 0

软间隔问题

在这里插入图片描述

核函数

​ 核函数即为了解决低维不可分问题,通过核函数将我们的数据转换到高维的层面,这里就不多介绍了。我们最常用的一个核函数即为高斯核函数

上一篇下一篇

猜你喜欢

热点阅读