支持向量机–SVM

支持向量机的发明人--Vapink
样本数很少的情况下使用支持向量机算法会得到一个比较好的结果
1
2

SVM–线性

概念：能画一条直线将训练样本集分为两类，如下图class1与class2
这样的样本集被称为--线性可分样本集（Linear Separable）
样本集无法画一条直线将其分开--非线性可分样本集(Non-Linear Separable)
1
2
3

线性可分样本集若存在一条直线可以分开两类别的样本，那么一定会存在无数条直线可以将其分开
1

两个问题：

1.有以下三条线，那条线是最好的？
1

(2)号线，(2)号线的容错率是最大的
1

\\

2.怎么有一个标准来定义(2)号线？
1

定义一个标准（性能指标），（2）号线的性能指标最大
将线平行的向两侧移动，直到某个样本在直线上为止，两条线的距离为d，d为性能指标
使得样本到直线最小距离的最大，且该直线到两不同标签样本点最近距离一样（处在中间，到两侧距离都为d/2）
1
2
3

d：间隔(Margin)

直线向两侧移动擦到的向量（样本点）叫支持向量（画出直线的方法只与支持向量有关，这也就是为什么支持向量能应用在小样本的训练上）

定义

定义训练数据与标签 ( x 1 , y 1 ) , ( x 2 , y 2 ) , ( x 3 , y 3 ) . . . . ( x n , y n ) x 为向量， y 为标签， X = [ x 11 x 12 x 13 ] x 1 , x 2 , x 3 为样本特征 ( 通常在实际中样本特征有很多，表示有很多维度 ) y i 表示标签，为了推导方便 y i 取 ± 1 定义训练数据与标签(x_1,y_1),(x_2,y_2),(x_3,y_3)....(x_n,y_n)\hspace{50cm} \\ x为向量，y为标签，X=

\\ x_1,x_2,x_3为样本特征 \left( 通常在实际中样本特征有很多，表示有很多维度 \right) \\ y_i表示标签，为了推导方便y_i取\pm1 定义训练数据与标签(x1​,y1​),(x2​,y2​),(x3​,y3​)....(xn​,yn​)x为向量，y为标签，X=⎣ ⎡​x11​x12​x13​​⎦ ⎤​​​x1​,x2​,x3​为样本特征(通常在实际中样本特征有很多，表示有很多维度)yi​表示标签，为了推导方便yi​取±1
2.
线性模型 : ( W , b ) , W ⊺ X + b = 0 ( 超平面 ) W = [ w 11 w 12 w 13 ] , b 为常数 通过训练的数据，在限定模型的下算出待定参数 W 和 b ，当确定 W 和 b 取值后这个算法就完成了 线性模型:\left( W,b\right),\mathbf{W}^\intercal X+b=0\left( 超平面\right)\hspace{50cm} \\W=

[w11w12w13]" role="presentation" style="position: relative;">⎡⎣⎢w11w12w13⎤⎦⎥$$\left[\begin{array}{c}{w}_{11}\\ w_{12}\\ w_{13}\end{array}\right]$$

,b为常数 \\ 通过训练的数据，在限定模型的下算出待定参数W和b，当确定W和b取值后这个算法就完成了\hspace{50cm} 线性模型:(W,b),W⊺X+b=0(超平面)W=⎣ ⎡​w11​w12​w13​​⎦ ⎤​​​,b为常数通过训练的数据，在限定模型的下算出待定参数W和b，当确定W和b取值后这个算法就完成了
3.一个训练集线性可分(Linear Separable)是指：
{ ( x i , y i ) } , i = 1 ∼ n ∃ ( W , b ) , 使 : 对 ∀ i = 1 ∼ n , 有 : ( 1 ) 若 y i = + 1 , 则 W ⊺ X + b ≥ 0 ( 2 ) 若 y i = − 1 , 则 W ⊺ X + b < 0 即 , y i [ W ⊺ X i + b ] ≥ 0 \left\{ (x_i,y_i)\right\},i=1\sim n\\ {\exists}(W,b),使: 对{\forall}i=1\sim n,有:\\ (1)若y_i=+1,则\mathbf{W}^\intercal X+b\ge0\\ (2)若y_i=-1,则\mathbf{W}^\intercal X+b<0\\ 即,y_i

[W⊺Xi+b]" role="presentation" style="position: relative;">[W⊺Xi+b]$$\left[\begin{array}{c}{\mathbf{W}}^{⊺}{X}_i+b\end{array}\right]$$

\ge0 {(xi​,yi​)},i=1∼n∃(W,b),使:对∀i=1∼n,有:(1)若yi​=+1,则W⊺X+b≥0(2)若yi​=−1,则W⊺X+b<0即,yi​[W⊺Xi​+b​]​​≥0
使得间隔最大的超平面是如何构造的？

支持向量机的优化问题(凸优化问题、二次规划问题)

1. 最小化 ( 1 2 ) ∣ ∣ W ∣ ∣ 2 2. 限制条件 ( S u b j e c t   t o ) : y i [ W ⊺ x i + b ] ≥ 1 ( i = 1 ∼ n ) ( 支持向量到超平面的距离为 1 ，则所有其他向量到超平面距离大于 1 ，标签 y i 保证距离为正， y i = ± 1 ) 1.最小化(\frac{1}{2})||W||^2 \hspace{50cm} \\ 2.限制条件(Subject\ to):y_i

\ge1(i=1\sim n)(支持向量到超平面的距离为1，则所有其他向量到超平面距离大于1，标签y_i保证距离为正，y_i=\pm1) 1.最小化(21​)∣∣W∣∣22.限制条件(Subject to):yi​[W⊺xi​+b​]​​≥1(i=1∼n)(支持向量到超平面的距离为1，则所有其他向量到超平面距离大于1，标签yi​保证距离为正，yi​=±1)

事实一 : W ⊺ x + b = 0 与 a W ⊺ x + b = 0 是在同一平面， a ∈ R + 若 ( W ， b ) 满足公式，则 ( a W , a b ) 也满足公式 ( 1 ) 事实二 : 点到平面的距离公式 : 平面 : w 1 x + w 2 y + b = 0 ( w 1 x 1 + w 2 x 2 + b = 0 , 即 [ w 1 , w 2 ] [ x 1 x 2 ] + b = 0 ) , 则 ( x 0 , y 0 ) 到此平面的距离为 : d = ∣ w 1 x 0 + w 2 y 0 + b ∣ w 1 2 + w 2 2 向量 X 0 到超平面 W ⊺ x + b = 0 ( [ w 1 , w 2 , . . . w n ] 向量 X 0 到超平面 W ⊺ x + b = 0 ( [ w 1 , w 2 , . . . w n ] [ x 1 x 2 . . x n ] + b = 0 ) 的距离 : d = ∣ W ⊺ X 0 + b ∣ ∣ ∣ W ∣ ∣ 事实一:\mathbf{W}^\intercal x+b=0与a\mathbf{W}^\intercal x+b=0是在同一平面，a\in R^+\hspace{50cm}\\ 若(W，b)满足公式，则(aW,ab)也满足公式(1)\hspace{50cm} \\ \\ 事实二:点到平面的距离公式: \hspace{50cm}\\ 平面:w_1x+w_2y+b=0(w_1x_1+w_2x_2+b=0,即[w1,w2]

+b=0), 则(x_0,y_0)到此平面的距离为: \hspace{50cm}\\ d=\frac{|w_1x_0+w_2y_0+b|}{\sqrt{w_1^2+w_2^2}}\\ \\ 向量X_0到超平面\mathbf{W}^\intercal x+b=0([w_1,w_2,...w_n]向量X_0到超平面\mathbf{W}^\intercal x+b=0([w_1,w_2,...w_n] +b=0 )的距离: \\ d=\frac{|\mathbf{W}^\intercal X_0+b|}{||W||} 事实一:W⊺x+b=0与aW⊺x+b=0是在同一平面，a∈R+若(W，b)满足公式，则(aW,ab)也满足公式(1)事实二:点到平面的距离公式:平面:w1​x+w2​y+b=0(w1​x1​+w2​x2​+b=0,即[w1,w2][x1​x2​​]+b=0),则(x0​,y0​)到此平面的距离为:d=w12​+w22​ ​∣w1​x0​+w2​y0​+b∣​向量X0​到超平面W⊺x+b=0([w1​,w2​,...wn​]向量X0​到超平面W⊺x+b=0([w1​,w2​,...wn​]⎣ ⎡​x1​x2​..xn​​⎦ ⎤​+b=0)的距离:d=∣∣W∣∣∣W⊺X0​+b∣​

$$\begin{gathered} 我们可以用a去缩放(W,b)->(aW,ab)最终使在(所有)支持向量X_0上有: \\ |{\mathbf{W}}^{⊺}{X}_0+b|=1(分子为1)，例如: \\ d=\frac{|{{\mathbf{W}}_1}^{⊺}{X}_0+b_1|}{||W_1||}=\frac{|{\mathbf{a}{\mathbf{W}}_1}^{⊺}{X}_0+a{b}_1|=1}{||a{W}_1||}=\frac{1}{||W||} \\ 此时，支持向量机与平面的距离只与||W||有关: \\ d=\frac{1}{||W||} \end{gathered}$$

二次规划问题

二次规划：
1.目标函数是二次项
2.限制条件一次项
（图像为二元函数）
要么无解，要么只有一个极值
1
2
3
4
5

梯度下降

我的另一篇博客–梯度下降