SVM原理及推导

用户1332428

发布于 2018-07-30 14:57:26

6200

发布于 2018-07-30 14:57:26

正文共2249个字，22张图，预计阅读时间15分钟。

对于二类分类问题，训练集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)$$

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

Margin

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

直线距离可知

所以 $$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$

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

求导：

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

等价于最优化问题：

(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，计算

(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的样本点称为支持向量。