🚩 Home / machine learning / SVM.md

SVM

发明人:Vapnik(俄)

适用于小样本

(1)线性模型

线性可分(Linear Separable),非线性可分(Non-linear Separable)

d:间隔(Margin)

将平行线插到的向量叫支持向量(Support Vectors),分割线的确定只需要使用到支持向量,所以适用于小样本。

定义:

(1)训练数据及标签 (X1, Y1), (X2, Y2) ...(Xn, Yn),其中X是一个向量,Y是标签,如果是二分类问题则Y只能取两个值(如-1, +1)之一

(2)线性模型,(ω,b)ω维度与X相同。b是一个常数。下面的方程定义一个超平面。

$$ω^TX+b=0$$

(3)线性可分定义,一个训练集({(Xi, Yi)} i = 1N)线性可分是指存在一个(ω,b)对任意的i=1N有:

a.若Yi = +1,则 W^TXi + b ≥ 0

b.若Yi = -1,则 W^TXi + b < 0

支持向量机的优化问题(凸优化问题,二次规划问题)如下:

$$Min\quad||ω||^2$$

限制条件(Subject To):

$$y_i[ω^TX_i+b] \geq 1$$

二次规划问题(Quadratic Programming):

(1)目标函数是二次项(2)限制条件是一次项=》要么无解要么只有一个解

点到平面距离:(可相应转化为到超平面)

$$d=\frac{|ω^TX+b|}{||ω||}$$

可以使用a去缩放(ω,b)→ (aω, ab)使得所有的支持向量Xi有:

$$|aω^TX_i+ab|=1$$

此时支持向量与平面距离为:

$$d=\frac{1}{||aω||}$$

所以最小化ω可以使得d最大化。

本课程没有讲如何求解二次规划的问题,我在网上找了一些教程没怎么看懂,涉及到朗格朗日乘子法和KKT条件,拉格朗日乘子法还比较好懂,KKT条件就不懂了。以后有机会再看吧,当前就把SVM转化到求解二次规划问题,然后让一些程序包来求解二次规划。

(2)非线性模型

最小化:

$$\frac{1}{2}||ω||^2 + C\sum^{N}_{i=1}{ζ_i}$$

限制条件:

$$y_i[w^Tx_i+b] \ge 1 - ζ_i$$

$$ζ_i \ge 0$$

ζi是松弛变量。

其中C∑ζi是正则项(Regulation Term),C是一个事先设定的参数。

定义一个高维映射φ(x),使得x →φ(x)

例子:x1=[0,0]∈C1,x2=[1,1]∈C1,x3=[1,0]∈C2,x4=[0,1]∈C2,可定义φ:x=[a,b]→φ(x)=[a^2,b^2,a,b,ab]

如何选取φ?

(1)φ为无限维

我们可以不知道无限维映射的显示表达,我们只要知道一个核函数(kernel Function)

$$K(x_1,x_2)=φ(x_1)^Tφ(x_2)$$

则(1)这个优化式仍然可解。

常用核函数:

1.高斯核函数

$$K(x_1,x_2)=e^{-\frac{||x_1-x_2||^2}{2σ^2}}$$

2.多项式核函数,d是多项式阶数

$$K(x_1,x_2)=(x_1^Tx_2+1)^d$$

K(x1,x2)能写成φ(x1)^Tφ(x2)的充要条件:Mercer's Theorem

1.K(x1,x2)=K(x2,x1)

2.任意常数Ci,Xi(i=1~N)有∑∑CiCjK(xi,xj)≥0

优化理论:

(1)《Convex optimization》 凸优化

(2)《Nonlinear programming》

原问题(prime problem):

最小化:

$$f(w)$$

限制条件:

$$g_i(w)\le0 \quad (1=1-K)$$

$$h_i(w)=0 \quad (i=1-M)$$

对偶问题(dual problem):

定义一个函数:

$$L(w,\alpha,\beta)=f(w)+\sum^{K}{i=1}{\alpha_ig_i(w)}+\sum^{M}{i=1}{\beta_ih_i(w)}=f(w)+\alpha^Tg(w)+\beta^Th(w)$$

对偶问题定义:

最大化Θ(α,β)=inf{L(w,α,β)}限制条件αi≥0(i=1~K),其中inf是求最小值

定理:如果w是原问题的解,而α,β*是对偶问题的解则有:

$$f(w^*)\ge\Theta(\alpha^*,\beta^*)$$

定义:G=f(w*)-Θ(α,β)≥0,G叫原问题与对偶问题的间距(Duality Gap)。

对于某些特定优化问题,可以证明G=0.

强对偶定理:若f(w)为凸函数且g(w)=Aw+b h(w)=Cw+d,则此优化问题的原问题与对偶问题的间距为0.即f(w*)=Θ(α,β)

上述问题转化为对偶问题:

最小化:

$$\frac{1}{2}||\omega||^2-C\sum^{N}_{i=1}{\zeta_i}$$

限制条件:

$$1+\zeta_i-y_i\omega^T\psi(x_i)-y_ib\le0$$

$$\zeta_i\le0$$

对偶问题:

最大化 :

$$\theta(\alpha,\beta)=inf\quad\frac{1}{2}||\omega||^2-C\sum^{N}{i=1}{\zeta_i}+\sum^{N}_{i=1}{\beta_i\zeta_i}+\sum^{N}{i=1}{\alpha_i}[1+\zeta_i-y_i\omega^T\psi(x_i)-y_ib]$$

限制条件:

$$\alpha_i\ge0$$

$$\beta_i\ge0$$

上述最大化函数最终可化简为:(这个化简是对inf内的变量求偏导,取极值,然后带入化简)

$$\theta(\alpha,\beta)=\sum^{N}{i=1}{\alpha_i}-\frac{1}{2}\sum^{N}_{i=1}{\sum^{N}{j=1}{\alpha_i\alpha_jy_iy_jK(x_i,x_j)}}$$

限制条件:

$$0\le\alpha_i\le C$$

$$\sum^{N}_{i=1}{\alpha_iy_i}=0$$

该问题也是一个凸优化问题,SMO算法可解。

测试流程:

$$若 \quad \omega^2\psi(x)+b\ge0,则y=+1 \atop 若 \quad \omega^2\psi(x)+b\lt0,则y=-1$$

而:

$$\omega^T\psi(x)=\sum^{N}_{i=1}{[\alpha_iy_i\psi(x_i)]^T\psi(x)}=\sum^{N}_{i=1}{\alpha_iy_iK(x_i,x)}$$

因此不需要求出w。

SVM算法:

(1)训练流程

输入{(xi,yi)} 1=1~N

解优化问题:最大化

$$\theta(\alpha,\beta)=\sum^{N}{i=1}{\alpha_i}-\frac{1}{2}\sum^{N}_{i=1}{\sum^{N}{j=1}{\alpha_i\alpha_jy_iy_jK(x_i,x_j)}}$$

限制条件:

$$0\le\alpha_i\le C$$

$$\sum^{N}_{i=1}{\alpha_iy_i}=0$$

可使用SMO算法解出,可求出所有阿尔法。

然后算b找一个阿尔法,0<α<C

$$b=\frac{1-y_i\sum^{N}_{j=1}{\alpha_jy_iK(x_i,x_j)}}{y_i}$$

(2)测试流程

输入测试样本X:

$$若 \sum^{N}_{i=1}{\alpha_iy_iK(x_i,x)+b\ge0},则y=+1 \atop 若\sum^{N}_{i=1}{\alpha_iy_iK(x_i,x)}+b\lt0,则y=-1$$

应用: