支持向量机 SVM-学习笔记

支持向量机：一种二分类模型，其基本模型是定义在特征空间上的间隔最大的线性分类器。

1. 线性可分支持向量机
支持向量机的学习目标：在特征空间中找到一个分离超平面，将实例分到不同的类且几何间隔最大，分离超平面对应于方程w·x+b=0,其中w为法向量，b为截距。分离超平面将特征空间划分为两部分，一部分为正类（即法向量指向的一侧），一部分为负类。

与感知机的区别：
感知机：利用误分类最小策略求得分离超平面，解有无穷多个。
线性可分支持向量机：利用间隔最大化求解最优分离超平面，解唯一。
1.1 间隔
函数间隔：
y(w·x+b) 表示分类的正确性以及确信度，其中|w·x+b|表示点x距离超平面的远近，而w·x+b的符号与类标记y的符号是否一致表示分类是否正确。

• 函数间隔定义：
  对于给定的训练数据集T和超平面 (w, b)，定义超平面(w, b)关于样本点 (xi,yi) 的函数间隔为：
  
  但是当成比例的改变w和b时，虽然超平面没有改变但是函数间隔发生了变化，所以需要对w加一些约束，因此定义几何间隔。

• 几何间隔定义：
  
  ||w|| 为w的L2范数，几何间隔表示实例点到超平面的带符号距离。

• 函数间隔和几何额间隔的关系：
  
  当||w||=1时，函数间隔和几何间隔相等。

1.2 间隔最大化
间隔最大化的理解：对训练数据集找到几何间隔最大的超平面，其实是以最大的确信度对训练数据进行分类，不仅将正实例点分开，并且对最难分的实例点有足够大的确信度将其分开。

• 最大间隔分离超平面问题：
  
  由函数间隔和几个间隔的关系得到问题的转化：
  
  函数间隔 γ̂  的取值不影响最优化问题的求解，所以取 γ̂  = 1，又由于max 1||w||和min12||w||2优化问题等价，故最优化问题最终转化为一个凸二次规划问题：
  
  求解该问题的最优解w*, b*，得到最大间隔分离超平面w*·x + b* = 0。

线性可分训练数据集的最大间隔分离超平面是存在且唯一的。

1.3 支持向量和间隔边界

• 支持向量
  在线性可分的情况下，训练数据集中与分离超平面距离最近的样本点的实例称为支持向量，即使得约束条件yi(w·xi+b)-1=0成立的点。
  
  图中在H1和H2上的点即为支持向量，H1和H2相互平行称为间隔边界，两者之间的距离为间隔，其值为2||w||。可以看出分离超平面位于H1和H2的中央且与他们平行，由于支持向量在确定分离超平面中起着决定性的作用（如果支持向量发生改变，超平面也随之改变），所以称这种模型为支持向量机。

1.4 线性不可分
  通常情况下在训练数据中存在一些特异点，将这些特异点去除之后，剩下的大部分的样本点组成的集合是线性可分的。
  线性不可分意味着某些样本点(xi,yi)不能满足函数间隔大于等于1的约束条件：yi(w·xi+b)−1≥0,故对每个样本点引进一个松弛变量 ξi≥0, 使得约束条件变为：yi(w·xi+b)≥1−ξi, 目标函数变为：12||w||2+C∑Ni=1ξi,其中C为惩罚参数，所有线性不可分的线性支持向量机问题变成以下的图二次规划问题：

最小化目标函数，使得分类间隔尽量大同时使误分类点的个数尽量小。原始问题的解（w,b,ξ）存在，可以证明w的解唯一，但是b的解不唯一是一个区间，所以实际计算时可以取在所有符合条件上的样本点上的平均值。其求解过程和线性可分一样为对偶算法。

• 支持向量
  在线性不可分的情况下，对应于解 α∗i>0的样本点(xi,yi)的实例xi称为支持向量。软间隔的支持向量 xi 或者在间隔边界上，或者在间隔边界与分离超平面之间，或者在分离超平面误分一侧。