【统计机器学习】支持向量机

【统计机器学习】支持向量机

支持向量机

支持向量机是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使他有别于感知机；支持向量机还包括核技巧，这使他成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数最小化问题。

核函数

当输入空间为欧式空间或离散集合、特征空间为希尔伯特空间时，核函数表示将输入从输入空间映射到特征空间得到的特征向量之间的内积。通过使用核函数可以学习非线性支持向量机，等价于隐式的在高维的特征空间中学习线性支持向量机。

函数间隔与集合间隔

在超平面wx+b=0确定的情况下，|wx+b|能够表示点x到距离超平面的远近，而通过观察wx+b的符号与类标记y的符号是否一致可判断分类是否正确，所以，可以用(y(wx+b))的正负性来判定或表示分类的正确性。于此，我们便引出了函数间隔（functional margin）的概念。
定义函数间隔（用表示）为：

而超平面(w，b)关于T中所有样本点(xi，yi)的函数间隔最小值（其中，x是特征，y是结果标签，i表示第i个样本），便为超平面(w, b)关于训练数据集T的函数间隔：

但这样定义的函数间隔有问题，即如果成比例的改变w和b（如将它们改成2w和2b），则函数间隔的值f(x)却变成了原来的2倍（虽然此时超平面没有改变），所以只有函数间隔还远远不够。
事实上，我们可以对法向量w加些约束条件，从而引出真正定义点到超平面的距离–几何间隔（geometrical margin）的概念。
假定对于一个点 x ，令其垂直投影到超平面上的对应点为 x0 ，w 是垂直于超平面的一个向量，为样本x到超平面的距离，如下图所示：

根据平面几何知识，有

其中||w||为w的二阶范数（范数是一个类似于模的表示长度的概念），(w/||w||)是单位向量（一个向量除以它的模称之为单位向量）。
又由于x0 是超平面上的点，满足 f(x0)=0，代入超平面的方程
，即
随即让此式
的两边同时乘以w^t，再根据w^t x₀ = -b和 w^t w= ||w||²，即可算出γ：

为了得到的绝对值，令γ乘上对应的类别 y，即可得出几何间隔（用表示）的定义：
从上述函数间隔和几何间隔的定义可以看出：几何间隔就是函数间隔除以||w||，而且函数间隔y(wx+b) = yf(x)实际上就是|f(x)|，只是人为定义的一个间隔度量，而几何间隔|f(x)|/||w||才是直观上的点到超平面的距离。

间隔最大化

对于线性可分的训练数据集来说，线性可分分离超平面有无穷多个，但是几何间隔最大的分离器是唯一的。这里的间隔最大话称为硬间隔最大化。

凸优化问题

凸优化问题是指约束最优化问题：
min_wf（w）
s.t. g_i(w) <= 0, i=1,2,3,…,k
h_i(w) = 0, i=1,2,3,…,l
其中，目标函数f（w）和约束函数g_i(w)都是Rⁿ 上连续可微的凸函数，约束函数h_i(w)是Rⁿ 上的仿射函数。
当目标函数f（w）是二次函数且约束函数g_i(w）是仿射函数时，上述凸优化问题成为凸二次规划问题。

对偶问题的求解

凸优化问题可以用用现成的QP (Quadratic Programming) 优化包进行求解。一言以蔽之：在一定的约束条件下，目标最优，损失最小。
此外，由于这个问题的特殊结构，还可以通过拉格朗日对偶性（Lagrange Duality）变换到对偶变量 (dual variable) 的优化问题，即通过求解与原问题等价的对偶问题（dual problem）得到原始问题的最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。
那什么是拉格朗日对偶性呢？简单来讲，通过给每一个约束条件加上一个拉格朗日乘子（Lagrange multiplier），定义拉格朗日函数（通过拉格朗日函数将约束条件融合到目标函数里去，从而只用一个函数表达式便能清楚的表达出我们的问题）

然后令

目标函数

KKT条件

一个最优化数学模型能够表示成下列标准形式：

KKT条件就是指上面最优化数学模型的标准形式中的最小点 x* 必须满足下面的条件：