支持向量机(Support Vector Machine)Part I

支持向量机用于解决分类问题。与感知器(PLA)相比,支持向量机不仅试图找到一个能够完美分割数据的高维平面(hyperplane),而且还希望这个平面能够尽量地胖,即平面与最近的数据点之间的距离尽可能地要大。

fatHyperPlane

给人的直观感觉是:分类平面离最近的数据点越远,越能容忍误差,因而鲁棒性越好。

1. 令w是分类平面的法向量
2. 分类器对每个数据点的所属类别的判断方法为:h(x)=sign(w^Tx+b)
3. 要完美地完成分类任务即等价于要:y_{n}(w^{T}x_{n}+b) data-recalc-dims=0" />
4. 每个数据点到分类平面的距离为:frac{1}{||w||}y_{n}(w^{T}x_{n}+b)

定义支持向量机问题如下:
underset{b,w}{max}qquad margin(b,w)
subject toqquad y_{n}(w^{T}x_{n}+b) data-recalc-dims=0" />
where qquad margin(b,w) = underset{n=1,dots ,N}{min}frac{1}{||w||}y_{n}(w^{T}x_{n}+b)
因为通过对b,w进行同等的放缩对限制条件并无影响,不妨令underset{n=1,dots ,N}{min}y_{n}(w^{T}x_{n}+b)=1
即可对上面问题进行简化:

underset{b,w}{max}qquad frac{1}{||w||}
subject to qquad underset{n=1,dots ,N}{min}y_{n}(w^{T}x_{n}+b)=1

依旧可以通过放缩对限制条件进行放松,同时将问题中的最大化专为最小化,获得了支持向量机的标准形式:

underset{b,w}{min}qquad frac{1}{2}w^Tw
subject to qquad y_{n}(w^{T}x_{n}+b)geq 1

这是一个二次规划问题,包含d+1个变量,N个限制条件

下面举个例子,在matlab中,利用cvx求解一个支持向量机,有四个数据点:
x_1=(0,0),y_1=-1
x_2=(2,2),y_1=-1
x_1=(2,0),y_1=1
x_1=(3,0),y_1=1
现要求解满足条件的支持向量机,代码如下:

求解后获得b = -1,w = [1;-1]

支持向量机的标准形式包含的是一个二次的目标函数和线性的限制条件,是一个二次规划问题,可以通过二次规划求解。

等价的二次规划问题形式如下:
underset{u}{min} qquad frac{1}{2}u^TQu+p^Tu
subject  to qquad a_m^Tugeq c_m
qquad for  m = 1,2,...,M

其中,目标中:
u = begin{bmatrix} bw end{bmatrix}
Q = begin{bmatrix} 0 quad 0^T_d �_d quad I_d end{bmatrix}
p = 0_{d+1}
限制条件为:
a^T_n = y_n[1quad x^T_n]
c_n = 1
M=N

下面仍然用cvx来求解上面例子中问题的二次规划形式,同时,我们对x进行一个非线性的变换:

求解得到:u = begin{bmatrix} -92� end{bmatrix}

即:b = -9, w =[2;0]

 

博主对于朗格朗日乘子和KKT条件不是懂,据说将上面的支持向量机标准形式转变为对应的对偶问题能够提高求解速度,支持向量机的对偶问题形式如下:

underset{alpha}{min}qquad frac{1}{2}sum_{n=1}^{N}sum_{m=1}^{N}{alpha}_n{alpha}_my_ny_mz_n^Tz_m-sum_{n=1}^{N}{alpha}_n

text{subject to}quad sum_{n=1}^{N}y_nalpha_n = 0;

qquad alpha_ngeq 0,quad text{for } n=1,2,3,dots ,N

对偶问题仍然是二次规划问题,有N个变量和N+?个限制条件,其中的alpha为拉格朗日乘数。

其解法为:

underset{alpha}{min}qquad frac{1}{2}alpha^TQ_Dalpha-1^Talpha

text{subject to} y^Talpha = 0;

qquad alpha_ngeq 0 text{for}  n=1,2,3,dots , N

Q_D矩阵中:q_{n,m}=y_ny_mz_n^Tz_m

CVX中代码示例:

求解出a为[0.0000;0.7037;0.7037;0.8889;0.2593;0.2593;0.0000],表示第2~第6个数据点为支持向量。相应的$b,w$求法如下:

w=sum_{SV}alpha_ny_nz_n

b=y_n-w^Tz_n,text{with any} SV(z_n,y_n)

Python中利用scikit-learn的SVM模块求解支持向量机方法如下,X,y以numpy.ndarray形式存储数据和标签:

本节中介绍的都是“硬”的支持向量机,Part II中会介绍“软”的支持向量机。

Leave a Reply

Your email address will not be published. Required fields are marked *