SVM原理及推导

2018-06-04 本文已影响25人 CodingFish

前言：蛋疼的简书，不支持MathJax 编辑公式，所以请看我的个人博客：

http://mcgrady.cn/2018/03/13/svm/#more

对于二类分类问题，训练集T={(${ x }{ 1 }$,${ y }{ 1 }$),(${ x }{ 2 }$,${ y }{ 2 }$),...,(${ x }{ n }$,${ y }{ n }$)}，其类别${ y }_{ n }\in ${-1，1}，线性SVM通过学习得到分离超平面：

$$ w\bullet x+b=0 $$
以及相应的分类决策函数：
$$f\left( x \right) =sign(w\bullet x+b)$$

有如下图所示的分离超平面，哪一个超平面的分类效果更好呢？

image

Margin

直观上，超平面B1的分类效果更好一些。将距离分离超平面最近的两个不同类别的样本点称为支持向量（support vector）的，构成了两条平行于分离超平面的长带，二者之间的距离称之为margin。显然，margin更大，则分类正确的确信度更高（与超平面的距离表示分类的确信度，距离越远则分类正确的确信度越高）。

image

直线距离可知

image

所以
$$Margin=\frac { 2 }{ \parallel w\parallel } $$

目标函数

约束条件

对于所有点，还要求分类正确，即：
$$w\bullet x+b\ge 1\quad \quad \quad if\quad { y }{ i }=+1$$$$ w\bullet x+b\ge -1\quad \quad \quad if\quad { y }{ i }=-1$$$${ y }_{ i }(w\bullet x+b)-1\ge 0$$

最大化Margin

$$\max { M } =\frac { 2 }{ \parallel w\parallel } \Rightarrow \min { \frac { 1 }{ 2 } { w }^{ T }w } $$

最优化问题

Minimize $\Phi (w)=\frac { 1 }{ 2 } { w }^{ T }w$
Subject to ${ y }_{ i }(w\bullet x+b)-1\ge 0$

引入拉格朗日乘子法了，优化的目标变为：

image

求导：

image

带入拉格朗日函数，对偶问题转为

image

等价于最优化问题：

image

(1)求得${ \alpha }^{ * }={ ({ \alpha }{ 1 }^{ * },{ \alpha }{ 2 }^{ * },...,{ \alpha }{ N }^{ * }) }^{ T }$
(2)计算
${ \omega }^{ * }=\sum { i=1 }^{ N }{ { \alpha }{ i }^{ * } } { y }{ i }{ x }{ I }$
并选择${ \alpha }{ * }$的一个正分量 ${ \alpha }_{ j }^{ * }$>0，计算

image

(3)求得分离超平面
${ \omega }^{ * }\bullet x+b=0$
分类决策函数：
$$f\left( x \right) =sign({ \omega }^{ * }\bullet x+b)$$
在线性可分SVM中，${ \omega }^{ * }$和${ b }^{ * }$只依赖于训练数据中对应于${ \alpha }{ i }^{ * }$>0的样本点$({ x }{ i },{ y }{ i })$，其他样本点对${ \omega }^{ * }$和${ b }^{ * }$没有影响。我们将训练数据中对应${ \alpha }{ i }^{ * }$>0的样本点称为支持向量

Example

image

Soft Margin

image

求解

image

Non-linear SVMs

image

利用高维空间，数据更好的可分（优点），又避免了高维空间计算复杂（缺点）

image

Linear核：主要用于线性可分的情形。参数少，速度快，对于一般数据，分类效果已经很理想了。
RBF核：主要用于线性不可分的情形。参数多，分类结果非常依赖于参数。有很多人是通过训练数据的交叉验证来寻找合适的参数，不过这个过程比较耗时。个人体会是：使用libsvm，默认参数，RBF核比Linear核效果稍差。通过进行大量参数的尝试，一般能找到比linear核更好的效果
多项式核函函数
字符串核函数