线性支持向量机（1）

支持向量机的学习策略就是间隔最大化，形式转化为求解凸二次规划问题。该算法就是求解凸二次规划的最优化算法。

当训练数据线性可分时候，通过硬间隔最大化，学习线性分类器，称为硬间隔支持向量机；当训练数据近似线性可分时，通过软间隔最大化，学习线性分类器，称为软间隔最大化；当数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。

给定特定空间的训练数据集：T={(x₁,y₁),(x₂,y₂),...(x_n,y_n)}

y_i为-1，+1的二分类，x_i表示第i个特征向量 ，yi为x_i的类标记，(x_i,y_i)为样本点。

学习的目标是从特征空间找到一个分离超平面，能将实例划分到不同的类。一般来说，当数据可分的时候，能将两类数据分离开来的超平面有无数个，对应于方程wx+b=0，线性可分支持向量机利用间隔最大化求最优分离超平面，这时解是唯一的。

定义：给定线性可分训练数据集，通过间隔最大化或等价求解相应的凸二次规划问题学习得到的分离超平面为：

及相应的分类决策函数表示为：

称为线性可分支持向量机。

一般来说，点距离分离超平面的远近可以表示分类预测的确信程度，在超平面wx+b=0确定的情况下，|wx+b|能够相对表示点x距离超平面的远近，wx+b的符号与y是否一致可用于表示是否分类正确，故用y(wx+b)来表示分类的正确性和确信度，这就是函数间隔。

对于给定数据集T和超平面(w,b)，定义超平面(w,b)关于样本点(x_i,y_i)的函数间隔为：

r=y_i(wx_i+b)

定义超平面(w,b)关于训练数据集T的函数间隔为超平面(w,b)关于T中所有样本点(x_i,y_i)的函数间隔最小值，即

r^'=min(y_i(wx_i+b))

对于超平面wx+b=0，由于等比例的改变w和b值，对超平面并未产生影响；然而对应的函数间隔会有相应等比例的变化，因此需要对超平面的法向量加以约束(如规范化)，则这时间隔是确定的，且函数间隔变成几何间隔。

对给定超平面(w,b)及其法向量w,点A表示实例x_i，类别标记y_i=+1，点A与超平面(w,b)的距离可表示为:

||w||表示为w的L₂范数。以上为点A在超平面正侧的情况，其在负侧的情况y_i=-1，其表示为上式结果加负号。这时满足w，b的缩放对结果不产生影响；

以二维空间为例，几何间隔就是点到直线的距离，三维以上是点到超平面距离。

注：在点到直线的过程中，以学习的点(x_i,y_i)到直线ax+by+c=0为例，点到线的距离为：

在二维空间中，r_i的距离等价于后式的d(x,y)，以上和几何间隔在维度为2的时候的表达形式有相同之处。

这时点x_i到超平面(w,b)的距离是：

超平面(w,b)关于样本点(x_i,y_i)的几何距离一般就是实例点到超平面的带符号距离，当样本点被正确分类的时候就是实例点到超平面的距离。

因此函数间隔和几何间隔有如下关系：

上式的分母表示函数距离（函数间隔），等式左边表示几何距离（几何间隔）。

如果||w||=1，那么函数间隔和几何间隔相等。如果超平面参数w和b成比例的改变（超平面没有改变），函数间隔也按此比例改变，而几何间隔不变。

间隔最大化：

支持向量机学习的基本思想是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。这里间隔最大化也称为硬间隔最大化，该问题可以表示为下面的约束最优化问题：

也即超平面到每个样本点的几何间隔至少是r，且求得最大化的r

上式可以通过调整转为如下表达式：

取=1代入上式最优化问题，由于最大化等价于最小化，因此线性可分支持向量机最优化问题可以表示为如下：

上式中将转为1的原因在于其取值的变化可以等价于w，b的缩放，同时该表达式中w，b的缩放因为||w||的引入已不对几何间隔产生影响，因此该式子的求解等价于之前2个式子的求解。这是一个凸二次规划问题。

凸二次规划问题指约束最优化问题：

其中，目标函数f(x)和gi(w)都是Rⁿ上的连续可微的凸函数，约束函数h_i(w)是Rⁿ上的仿射函数。

当目标函数f(w)是二次函数且约束函数g_i(w)是仿射函数时，上述凸最优化问题成为凸二次规划问题。

通过求解约束最优化问题w,b，可以得到最大间隔分离超平面及分类决策函数，即线性可分支持向量机模型。

最大间隔法算法:

输入：线性可分数据集T={(x₁,y₁),(x₂,y₂),...(x_n,y_n)}，y_i分别取0和1

输出：最大间隔分离超平面和分类决策函数

(1) 构造并求解约束最优化问题

求解最优化的w和b

(2) 得到分类超平面：wx+b=0和分类决策函数: f(x)=sign(wx+b)

 在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量，支持向量是使约束条件式等号成立的点，即

y_i(wx_i+b)-1=0

对于y_i=+1的正例点，支持向量机在超平面

wx+b=1

对y_i=-1的负例点，支持向量在超平面：

wx+b=-1