[Stay Sharp]线性可分SVM公式--李航《统计学习方法

2018-12-25 本文已影响0人三千雨点

SVM线性可分支持向量机的最优化问题是：

$\begin{array} { l l } { \min _ { w , b } } & { \frac { 1 } { 2 } \| w \| ^ { 2 } } \\ { \text { s.t. } } & { y _ { i } \left( w \cdot x _ { i } + b \right) - 1 \geqslant 0 , \quad i = 1,2 , \cdots , N } \end{array}$

在数学中的最优化问题中，拉格朗日乘数法（以数学家约瑟夫·拉格朗日命名）是一种寻找多元函数在其变量受到一个或多个条件的约束时的极值的方法。针对以上最优化问题，我们也使用拉格朗日函数进行转换，并引入拉格朗日乘子

$L ( w , b , \alpha ) = \frac { 1 } { 2 } \| w \| ^ { 2 } - \sum _ { i = 1 } ^ { N } \alpha _ { i } y _ { i } \left( w \cdot x _ { i } + b \right) + \sum _ { i = 1 } ^ { N } \alpha _ { i }$
根据对偶性，原始问题的对偶问题是极大极小问题：

$\max _ { \alpha } \min _ { w , b } L ( w , b , \alpha )$
所以我们要
（1）先求 $\min _ { w , b } L ( w , b , \alpha )$ :

将 $L ( w , b , \alpha )$ 对 $w , b$ 求偏导得到：

$\nabla _ { w } L ( w , b , \alpha ) = w - \sum _ { i = 1 } ^ { N } \alpha _ { i } y _ { i } x _ { i } = 0$

$\nabla _ { b } L ( w , b , \alpha ) = \sum _ { i = 1 } ^ { N } \alpha _ { i } y _ { i } = 0$

得到 $w = \sum _ { i = 1 } ^ { N } \alpha _ { i } y _ { i } x _ { i }$ 以及 $\sum _ { i = 1 } ^ { N } \alpha _ { i } y _ { i } = 0$

将结果代入拉格朗日函数得到：

$\min _ { w , b } L ( w , b , \alpha ) = - \frac { 1 } { 2 } \sum _ { i = 1 } ^ { N } \sum _ { j = 1 } ^ { N } \alpha _ { i } \alpha _ { j } y _ { i } y _ { j } \left( x _ { i } \cdot x _ { j } \right) + \sum _ { i = 1 } ^ { N } \alpha _ { i }$

（2）然后再求 $\min _ { w , b } L ( w , b , \alpha )$ 对 $\alpha$ 的极大：

$\begin{array} { c l } { \max _ { \alpha } } & { - \frac { 1 } { 2 } \sum _ { i = 1 } ^ { N } \sum _ { j = 1 } ^ { N } \alpha _ { i } \alpha _ { j } y _ { i } y _ { j } \left( x _ { i } \cdot x _ { j } \right) + \sum _ { i = 1 } ^ { N } \alpha _ { i } } \\ { \text { s.t. } } & { \sum _ { i = 1 } ^ { N } \alpha _ { i } y _ { i } = 0 } \\ { } & { \alpha _ { i } \geqslant 0 , \quad i = 1,2 , \cdots , N } \end{array}$
将此极大转为极小，也就得到来原问题对等价对偶最优化问题：

$\begin{array} { c l } { \min _ { \alpha } } & { \frac { 1 } { 2 } \sum _ { i = 1 } ^ { N } \sum _ { j = 1 } ^ { N } \alpha _ { i } \alpha _ { j } y _ { i } y _ { j } \left( x _ { i } \cdot x _ { j } \right) - \sum _ { i = 1 } ^ { N } \alpha _ { i } } \\ { \text { s.t. } } & { \sum _ { i = 1 } ^ { N } \alpha _ { i } y _ { i } = 0 } \\ { } & { \alpha _ { i } \geqslant 0 , \quad i = 1,2 , \cdots , N } \end{array}$
求得 $\alpha ^ { * }$ 后也就能求得最优化 $w ^ { * } ,\beta ^ { * }$ ，对应的转换公式是：

$w ^ { * } = \sum _ { i = 1 } ^ { N } \alpha _ { i } ^ { * } y _ { i } x _ { i }$

$b ^ { * } = y _ { j } - \sum _ { i = 1 } ^ { N } \alpha _ { i } ^ { * } y _ { i } \left( x _ { i } \cdot x _ { j } \right)$

以上内容来自于李航-《统计学习方法》

[Stay Sharp]线性可分SVM公式--李航《统计学习方法

猜你喜欢

热点阅读