学习笔记:机器学习之支持向量机(二)

活动地址：CSDN21天学习挑战赛

​1 线性可分支持向量机的对偶问题

   对偶问题可以降低问题的求解难度，可由线性分类问题推广到非线性分类问题.

2 构造拉格朗日函数(算法肢解)

这是最大间隔算法的原始形式

  构造拉格朗日函数将目标函数和约束条件联系起来 ,原始形式约束条件式子中有n个不等式,所以这里我们对每一个不等式约束引入一个拉格朗日乘子${\alpha }_i\ge 0,i=1,2,...,N$.
该问题的拉格朗日函数如下:$$L(w,b,\alpha )=\frac{1}{2}||w|{|}^2-\sum _i^N{\alpha }_i{y}_i(w\cdot x_i+b)+\sum _i^N{\alpha }_i$$
  原始问题的对偶问题为该拉格朗日函数的极大极小问题,即先求$L(w,b,\alpha )$对w,b的极小值,再对$\alpha$求极大值.
即:$$\underset{\alpha }{\max }\underset{w,b}{\min }L(w,b,\alpha )$$
(1)求$\underset{w,b}{\min }L(w,b,\alpha )$
  令${\theta }_0(\alpha )=\underset{w,b}{\min }L(w,b,\alpha )$
  求极值就分别对w,b求偏导等于0.
$$\begin{gathered} {\nabla }_{x}L(w,b,\alpha )=w-\sum _i^N{\alpha }_i{y}_i{x}_i=0 \\ {\nabla }_{b}L(w,b,\alpha )=-\sum _i^N{\alpha }_i{y}_i=0 \end{gathered}$$
解得w,b.
{ w = ∑ i N α i y i x i ∑ i N α i y i = 0 \left\{

\right. ⎩ ⎨ ⎧​w=i∑N​αi​yi​xi​i∑N​αi​yi​=0​
  则$$\begin{gathered} {\theta }_0(\alpha )=\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\cdot x_j)-{\sum }_{i=1}^N{\alpha }_i{y}_i({\sum }_{j=1}^N{\alpha }_i{y}_j\ast ((x_i\cdot x_j))+{\sum }_{j=1}^N{\alpha }_i \\ ={\sum }_{j=1}^N{\alpha }_i-\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\cdot x_j) \end{gathered}$$

(2 )求$\underset{\alpha }{\max }{\theta }_0(\alpha )$

{ max ⁡ α θ 0 ( α ) s . t . ∑ i = 1 N α i y i = 0 , α i ≥ 0 , i = 1 , 2 , . . . , N \left\{

\right. ⎩ ⎨ ⎧​αmax​θ0​(α)s.t.i=1∑N​αi​yi​=0,αi​≥0,i=1,2,...,N​

上式约束条件中，拉格朗日乘子大于等于0

KKT条件

则该问题中KKT条件第一条为：
$${\nabla }_{w}L=w^{\ast }-\sum _i^N{\alpha }_i^{\ast }{y}_i{x}_i=0(1)$$
对于互补松弛条件有${\alpha }_i(1-y_i(w^{\ast }\cdot x_j+b^{\ast }))=0,{\alpha }_i\ge 0$
则$1-y_i(w^{\ast }\cdot x_j+b^{\ast })=0(2)$
由（1）（2）解的原始问题中w,b
{ w ∗ = ∑ i = 1 N α i ∗ y i x i b ∗ = y j − ∑ i = 1 N α i ∗ y i ( x i ⋅ x j ) \left\{

\right. ⎩ ⎨ ⎧​w∗b∗​=i=1∑N​αi∗​yi​xi​=yj​−i=1∑N​αi∗​yi​(xi​⋅xj​)​
此时就得到分类超平面：
$$\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x_i\cdot x)-\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x_i\cdot x_j)+y_i=0$$
分类决策函数为：
$$f(x)=sign(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x_i\cdot x)-\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x_i\cdot x_j)+y_i)$$

3 线性可分支持向量机算法——最大间隔算法对偶形式

输入：数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } , x i ∈ R n , y i ∈ { − 1 , 1 } , i = 1 , 2 , . . . , N . T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\},x_i \in R^n,y_i \in\{-1,1\},i=1,2,...,N. T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)},xi​∈Rn,yi​∈{−1,1},i=1,2,...,N.
输出：分离超平面、分类决策函数

参考

https://mp.weixin.qq.com/s/886_EdhRtRFCeof0xaPDhw
https://www.bilibili.com/video/BV1HP4y1Y79e?spm_id_from=333.337.search-card.all.click&vd_source=893fb409f9a0bd0a8c04972fb40b53b3