线性可分SVM摘记

⎧​目标函数值：∥λw∥λγ^​​约束函数：　yi​λ(wTxi​+b)≥λγ^​,∀ xi​​

qquad

qquad

显然，权值

(

w

,

b

)

(boldsymbol w,b)

(w,b) 与其同比例的缩放值

(

λ

w

,

λ

b

)

(lambdaboldsymbol w,lambda b)

(λw,λb) 对于约束最优化问题（2）而言是没有影响的。

qquad

∙

quadbullet

∙　构造凸二次规划问题

qquad

在约束最优化问题（2）中，可以简单地取函数间隔

γ

^

=

1

hatgamma=1

γ^​=1。

假设待求解的权值为

(

w

,

b

)

(boldsymbol w,b)

(w,b)， 样本

x

boldsymbol x

x 到

w

T

x

+

b

=

0

boldsymbol w^Tboldsymbol x+b=0

wTx+b=0 的几何间隔为

γ

^

∥

w

∥

dfrac{hatgamma}{Vertboldsymbol wVert}

∥w∥γ^​​
函数间隔

γ

^

=

1

hatgamma=1

γ^​=1 时的几何间隔写为

1

∥

λ

′

w

∥

dfrac{1}{Vertlambda^{prime}boldsymbol wVert}

∥λ′w∥1​，也就是

(

w

,

b

)

(boldsymbol w,b)

(w,b) 缩放为了

(

λ

′

w

,

λ

′

b

)

,

 

λ

′

=

1

/

γ

^

(lambda^{prime}boldsymbol w,lambda^{prime}b), lambda^{prime}=1/hatgamma

(λ′w,λ′b), λ′=1/γ^​
而

w

T

x

+

b

=

0

boldsymbol w^Tboldsymbol x+b=0

wTx+b=0 和

λ

′

w

T

x

+

λ

′

b

=

0

lambda^{prime}boldsymbol w^Tboldsymbol x+lambda^{prime}b=0

λ′wTx+λ′b=0 是同一个分类面

qquad

那么，约束最优化问题（2）就可以写为：

max

⁡

w

,

b

 

γ

^

∥

w

∥

 

s

.

t

.

   

y

i

(

w

T

x

i

+

b

)

≥

γ

^

,

 

∀

 

x

i

⟹

γ

^

=

1

max

⁡

w

,

b

 

1

∥

w

∥

 

s

.

t

.

   

y

i

(

w

T

x

i

+

b

)

≥

1

,

 

∀

 

x

i

qquadqquadtextcolor{darkblue}{begin{aligned}&max_{boldsymbol w,b} dfrac{hatgamma}{Vertboldsymbol wVert}\ & s.t. y_i(boldsymbol w^Tboldsymbol x_i+b) ge hatgamma, forall boldsymbol x_iend{aligned}}quadoverset{hatgamma=1}Longrightarrowqquadtextcolor{royalblue}{begin{aligned}&max_{boldsymbol w,b} dfrac{1}{Vertboldsymbol wVert}\ & s.t. y_i(boldsymbol w^Tboldsymbol x_i+b) ge 1, forall boldsymbol x_iend{aligned}}

​w,bmax​ ∥w∥γ^​​ s.t.   yi​(wTxi​+b)≥γ^​, ∀ xi​​⟹γ^​=1​​w,bmax​ ∥w∥1​ s.t.   yi​(wTxi​+b)≥1, ∀ xi​​

qquad

qquad

又由于

max

⁡

 

1

∥

w

∥

⟺

min

⁡

 

1

2

∥

w

∥

2

max dfrac{1}{Vertboldsymbol wVert}Longleftrightarrowmin dfrac{1}{2}Vertboldsymbol wVert^2

max ∥w∥1​⟺min 21​∥w∥2，因此可以构造出一个凸二次规划问题

qquad

约束最优化问题（3）

min

⁡

w

,

b

 

1

2

∥

w

∥

2

 

s

.

t

.

   

y

i

(

w

T

x

i

+

b

)

≥

1

,

∀

 

x

i

qquadqquadqquadtextcolor{indigo}{begin{aligned}&min_{boldsymbol w,b} dfrac{1}{2}Vertboldsymbol wVert^2\ & s.t. y_i(boldsymbol w^Tboldsymbol x_i+b) ge 1,quad forall boldsymbol x_iend{aligned}}

​w,bmin​ 21​∥w∥2 s.t.   yi​(wTxi​+b)≥1,∀ xi​​

qquad

3. 支持向量

qquad

支持向量

(

support vector

)

(text{support vector})

(support vector) 是指距离分类面最近的训练样本（红色 + 点），两个（红色点线）超平面

w

T

x

+

b

=

1

boldsymbol w^Tboldsymbol x+b=1

wTx+b=1 和

w

T

x

+

b

=

−

1

boldsymbol w^Tboldsymbol x+b=-1

wTx+b=−1 之间的距离，称为间隔

(

margin

)

(text{margin})

(margin)。

qquad

qquad

考察该凸二次规划最优化问题：

min

⁡

w

,

b

 

1

2

∥

w

∥

2

 

s

.

t

.

   

y

i

(

w

T

x

i

+

b

)

≥

1

,

∀

 

x

i

qquadqquadqquadbegin{aligned}&min_{boldsymbol w,b} dfrac{1}{2}Vertboldsymbol wVert^2\ & s.t. y_i(boldsymbol w^Tboldsymbol x_i+b) ge 1,quad forall boldsymbol x_iend{aligned}

​w,bmin​ 21​∥w∥2 s.t.   yi​(wTxi​+b)≥1,∀ xi​​

qquad

支持向量也是使得约束条件的等式成立的点，即：

y

(

w

T

x

+

b

)

=

1

y(boldsymbol w^Tboldsymbol x+b)=1

y(wTx+b)=1。在线性可分的情况下，选择不同的点作为支持向量，就可以确定不同的分离超平面

w

T

x

+

b

=

0

boldsymbol w^Tboldsymbol x+b=0

wTx+b=0。

• （正例的）支持向量 ${\mathbf{x}}_i,y_i=+1:y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)=1\Rightarrow H_1:{\mathbf{w}}^T{\mathbf{x}}_i+b=1$
• （负例的）支持向量 ${\mathbf{x}}_j,y_j=-1:y_j({\mathbf{w}}^T{\mathbf{x}}_j+b)=1\Rightarrow H_2:{\mathbf{w}}^T{\mathbf{x}}_j+b=-1$
• 两个超平面 $H_1$

qquad

qquad

【写在最后】SVM的资料太多了，越写越觉得没什么特别的内容值得去写。攒在草稿箱里太久，发出来就当留个记录吧。