西瓜书 第6章、支持向量机 6.1-6.5

支持向量机

一、间隔与支持向量

  分类学习的基本思想就是基于训练集在样本空间找到一个划分超平面，将不同类别的样本分开，但是能将样本分开的有很多应该找那个最中间的超平面，因为其容忍度最好。如下图所示应该用最中间的红色面

线性超平面：

  超平面分为线性的和非线性的，线性的一般来说就是SVM法来分类，非线性的就是用核方法来映射到高维空间使之有线性的性质。

超平面性质:

1. 法向量恒垂直于超平面。
2. 和法向量相同的点代入超平面方程恒大于零，否则恒小于等于零（下面计算间隔距离时候的假设可以看出）
3. 法向量和位移项确定唯一一个超平面
4. 等倍缩放法向量和偏移值超平面不变
5. 在样本空间中，划分超平面方程可通过如下线性方程来描述：WTX + b = 0 ，其中W是法向量，b是位移项决定了超平面与原点之间的距离，将w，b结合起来写成（w ,b）,则样本空间中任意一点到超平面（w ,b）可写出：
   

推导:
空间中一点(x0,y0)到直线 Ax+By+C=0 的距离为：

  通过类比可以得到 r 的表达式。下面是计算间隔距离：

  通过以上定义可以知道一个点到超平面的最小距离是 1/||w|| ,因为假设的就是 W^TX + b = ±1 ，这些最小点我们称之为支持向量，我们的优化目标就是知道一个最合适的超平面是使得间隔最大。具体的距离直观图如下：

这就是SVM得基本型。

二、对偶问题

对于上面给出的基本型有：

kkt条件的运用：

首先列出拉格朗日无约束优化的式子

KKT条件：

根据上述KKT条件的第一个结论：

求导后得到 w 和 b 的表达式，如上图第二步所示。将 w* 代入式子得：

极大极小转化一下就得到第三步的式子。
  其中主要思想就是利用拉格朗日函数进行对优化式子的改造使 SVM基本型变成无约束的式子，由于 0.5||w||^2 是凸函数，所以根据凸函数的性质局部极小值点就是全局最小值点，我们对其求导得极值即可。所以通过求偏导我们解决到了 w 和 b 的取值优化问题，接下来只剩下一个参数就是引入的 α 的优化问题，也就是上述最后的第三步的式子。下面就是对剩下的唯一参数的优化了：SMO算法

SMO算法：

  二次规划问题可以通过二次规划算法来解,但是问题规模正比于样本数, 实际任务中很难接受.一个常用的高效算法就是SMO(Sequential Minimal Optimization, 序列最小化优化算法) SMO的基本思路是如下两个步骤迭代：

1. 选取一对需更新的变量 αi 和 αj
2. 固定 αi 和 αj 以外的参数, 求解对偶问题更新 αi 和 αj

仅考虑 αi 和 αj 时, 对偶问题的约束变为：

  将具有闭式解的二次规划解出来即可得到 α 的解。最后如何确定偏移项呢？注意到任何支持向量(xs,ys) 都有 ys * f (s) =1 即:

  其中：s = { i | αi >0, i = 1,2,3…m}为所有支持向量的下标集，理论上可以选任何支持向量进行求解获得 b ，但是现实中通常采用一种更加鲁棒的做法：使用所有支持向量求解的平均值：

三、核函数

  核函数是基于实际的来源的，遇到线性不可分的情况时候，比如：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

  这种分界面就是非线性的，将样本从原始空间映射到一个更高维的特征空间, 使得样本在这个特征空间内线性可分.如下图所示

则前面的支持向量表达式变成：

  但是核映射是很难处理的，最好是设计一个对应的函数就可以直接使用性质，所以把上面的内积表示成：

Mercer定理(充分非必要)：

只要一个对称函数所对应的核矩阵半正定, 则它就能作为核函数来使用.核矩阵和常用的核函数如下图所示：

下面给出一个映射例子：

一条二次曲线（圆圈是二次曲线的一种特殊情况）的方程可以写作这样的形式：

  注意上面的形式，如果我们构造另外一个五维的空间，其中五个坐标的值分别为 Z1=X1,Z2=X12,Z3=X2,Z4=X22,Z5=X1X2 ,那么显然可以映射成功。

核函数的解释；

式子1是映射到高维空间中，然后再根据内积的公式进行计算；式子2直接在原来的低维空间中进行计算，而不需要显式地写出映射后的结果。

常用的核函数：

几个核函数的简单性质：

四、软间隔与正则化

  现实中, 很难确定合适的核函数使得训练样本在特征空间中线性可分; 同时一个线性可分的结果也很难断定是否是有过拟合造成的，所以引入软间隔的概念, 允许支持向量机在一些样本上不满足约束。

  具体来说，前面介绍的支持向量机形式就是要求所有样本均满足6.3式，即所有样本都必须正确划分，这就是硬间隔，而软间隔就是允许某些样本不满足约束：yi(wTxi+b>=1) >= 1,当然在最大化间隔的同时，不满足约束的样本应该尽可能少，于是优化目标写成：

模型解释：

1. 第一项是一直以来最大化间隔都想要优化的项，略
2. 第二项基于不满足约束的样本也应尽可能少这一理念，引入了“0/1损失函数”，当样本(xi,yi) 不满足约束时，损失函数取值为1，第二项的取值为C，满足约束时则为0。也就是说，不满足约束的样本越多(n)时，第二项的取值越大(n*C)，则越偏离我们想要优化的方向（最小化）。于是，最小化该方程的最优解保证了不满足约束的样本也应尽可能少的要求。
     值得注意的是，当C取无穷大时，最小化该方程的最优解迫使所有样本均满足约束，也就是将书上的(6.29)等价于前面硬间隔的(6.6)。

三种常用的替代损失函数：

  接下来，按之前的步骤就是开始使用拉格朗日乘子法求对偶问题，但是这里的0/1损失函数非凸非连续，数学性质不太好，使得式(6.29)不易直接求解。于是，这里使用具有较好的数学性质的代替损失函数(如它们通常是凸的连续函数且是0/1损失函数的上界)。若使用hinge损失，则：

构建拉格朗日函数：

得出对偶问题：

对于软间隔支持向量机，KKT条件要求：

支持向量机更一般的格式：

  通过替换上面结构风险和经验风险两个部分, 可以得到许多其他学习模型 如：对数几率回归(Logistic Regression) 最小绝对收缩选择算子(LASSO)。
  从经验风险最小化的角度看，结构风险表述了我们希望获得具有何种性质的模型（如复杂度最小的模型），有助于削减假设空间，从而降低了最小训练误差的过拟合风险。从降低过拟合风险这个角度看，上图所写的一般形式可称为正则化问题（第1节也是从降低过拟合的角度出发取 ||w||^2 正则化）。于是，结构风险称为正则化项，C 称为正则化常数。

五、支持向量回归

本节从分类问题转向了回归问题，介绍了相对于传统回归问题上对损失的严格定义，支持向量回归（SVR）则对模型输出和真实输出设有容许偏差，只有超过偏差才计算损失。凭此建立了SVR模型，并还是采用第2节的方法进行求解。 由于落入中间间隔带的样本不计算损失, 从而使得模型获得稀疏性。

于是SVR问题可形式化为：

注：对于式(6.43)的第二项：正则化常数 *经验风险，其思路与式(6.29)处的一致。若样本对应的输出值之差在间隔带内(∣f(xi)−y∣≤ε 其值取0；若差落在间隔带之外，其值取其到间隔带的距离。也就是说，ε -不敏感损失函数(经验风险)表征了对应样本在模型上的损失程度大小。

  由与间隔带两侧的松弛程度可有所不同，这里引入两个松弛变量 ξi 和 ξˆi ，分别对应两侧的松弛程度，将式(6.43)重写为

接下来就还是拉格朗日函数求对偶问题和KKT的套路：

同样满足KKT条件:

此外，易知 αi 和 ^αi 至少有一个为 0 。