SVM（一）：线性支持向量机

1.1 问题定义

（1） 划分超平面

二维样本空间中，划分平面可以表示为： W₁X₁ +W₂X₂ + b = 0

在高维样本空间中，划分超平面定义如下：

其中，w = (W₁, W₂. . . , W_d )为法向量，决定了超平面的方向；b 为位移，决定了超平面与原点之间的距离。

设空间中任一点x 在超平面的投影为x ′，则

2） 点到超平面的距离

样本空间中任意点x到超平面的距离为

其中， 为w 的L2范数。

（3）支持向量、间隔

假设超平面能将训练样本正确分类，即对于(_{x i , y i}) ∈ D

由于w 与 b 可任意缩放，令r = 1

如下图所示，距离超平面最近的训练样本点是得上式等号成立，称为支持向量（Support vector）。

支持向量到超平面的距离之和为 ，称为间隔（margin）。

（4）最优超平面

能将两类样本划分的超平面有无数多个，具有最大分类间隔的超平面，称为最优超平面。

为找到具有最大间隔的划分超平面，需要

1.2 对偶问题

目标函数 是凸函数，同时约束条件不等式是仿射的，是一个凸二次规划（convex quadratic programming）问题，可以用优化计算包求解（适用于维度较低的情况）。另一种更高效的办法是，通过拉格朗日函数（对每条约束添加拉格朗日乘子_{α i}≥0）将的优化目标转化为无约束的优化函数

其中α = ( α 1 , α 2 , . . . , α m )

由于引入了朗格朗日乘子，优化目标变成：

该优化函数满足满足KTT条件，即

对于任意训练样本( _{x i , y i}) ，必有α i = 0 或 _{y i} f ( _{x i} ) = 1 。

若 α i= 0，则该样本不会在求和式中出现，也就不会对f ( x )有任何影响；

若_{α i}> 0，则必有_{y i}f ( _{x i} ) =  1，该样本点在最大间隔边界上，是一个支持向量。

这显示出支持向量基的一个重要性质：最终模型仅与支持向量有关

因此，根据拉格朗日对偶条件，原问题的对偶问题如下：

极大极小问题：先求优化函数对于w 和b 极小值，再求拉格朗日乘子α 的极大值

L ( w , b , α ) 关于w 和b 极小值可以通过对w 和b分别求偏导得到：

将w 的值代入L ( w , b , α )

原问题最终转换为如下形式的对偶问题：

此时，优化函数仅有α 做为参数，可采用SMO（Sequential Minimal Optimization）求解。

1.3 问题求解

SMO算法则采用了一种启发式的方法，它每次只优化两个变量，将其他的变量都视为常数，将复杂的优化算法转化为一个简单的两变量优化问题.

由于 .假如将α 3 , α 4 , . . . , α m 固定，那么α 1 , α 2 之间的关系也确定了。初始化参数后，SMO不断执行以下两个步骤直至收敛：

选取一对需更新的变量_{α i} 和α _j

固定_{α i}和 α _j以外的参数，求解获得更新后的_{α i}和α _j

解出最优化对应的α的值α *后，可求出

对于任意支持向量(X _s , y _s  ) 都有y s f ( X _s  ) = 1，即

S为所有支持向量的集合，即满足_{α s}> 0 对应的样本( X _s , y _s )，理论上可任意选取支持向量通过上式，求得b

一般采取一种更为鲁棒的方法，即计算出每个支持向量(X _s ,y _s ) 对应的b s ∗ 对其求平均值得到

最终得到分类超平面w ^{∗ T} x+b ^∗ = 0 ，分类决策函数为 f ( x ) = s i g n (  w ^{∗ T} x+b ^∗ )