西瓜书第六章--支持向量机

6.1间隔与支持向量

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

在这里普及一下线性超平面的知识：首先超平面分为线性的和非线性的，线性的一般来说就是SVM法来分类，非线性的就是用核方法来映射到高维空间使之有线性的性质。简要介绍一下超平面的一些性质:

法向量恒垂直于超平面。
和法向量相同的点代入超平面方程恒大于零，否则恒小于等于零（下面计算间隔距离时候的假设可以看出）
法向量和位移项确定唯一一个超平面
等倍缩放法向量和偏移值超平面不变

在样本空间中，划分超平面方程可通过如下线性方程来描述：W^TX + b = 0 ，其中W是法向量，b是位移项决定了超平面与原点之间的距离，我们将w，b结合起来写成（w ,b）,则样本空间中任意一点到超平面（w ,b）可写出：

其推导及其简单，我们中学学过了空间中一点(x₀,y₀)到直线 Ax+By+C=0 的距离为：

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

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

这就是SVM得基本型。

6.2对偶问题

对于上面给出的基本型：

细说一下kkt条件的运用：

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

KKT条件：

关于kkt条件推荐一条博客：https://www.cnblogs.com/ooon/p/5723725.html

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

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

极大极小转化一下就得到第三步的式子。

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

SMO算法：

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

第一步：选取一对需更新的变量 α_i和 α_j
第二步：固定 α_i和 α_j 以外的参数, 求解对偶问题更新 α_i和 α_j

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

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

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

6.3核函数

核函数是基于实际的来源的，我们遇到线性不可分的情况时候，比如：

这种分界面就是非线性的，我们该怎么处理呢？回答是：将样本从原始空间映射到一个更高维的特征空间, 使得样本在这个特征空间内线性可分.如下图所示

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

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

那么什么样的函数可以作为核函数呢？我们有Mercer定理(充分非必要)：只要一个对称函数所对应的核矩阵半正定, 则它就能作为核函数来使用.核矩阵和常用的核函数如下图所示：

下面给出一个映射例子：

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

注意上面的形式，如果我们构造另外一个五维的空间，其中五个坐标的值分别为Z₁=X₁,Z₂=X₁²,Z₃=X₂,Z₄=X₂²,Z₅=X₁X₂ ,那么显然可以映射成功。下面简单讲一下核函数的解释；

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

这是常用的核函数：

下面举出几个核函数的简单性质：

6.4软间隔与正则化

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

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

解释一下该模型：

第一项是一直以来最大化间隔都想要优化的项，略；
第二项基于不满足约束的样本也应尽可能少这一理念，引入了“0/1损失函数”，当样本(x_i,y_i) 不满足约束时，损失函数取值为1，第二项的取值为C，满足约束时则为0。也就是说，不满足约束的样本越多(n)时，第二项的取值越大(n*C)，则越偏离我们想要优化的方向（最小化）。于是，最小化该方程的最优解保证了不满足约束的样本也应尽可能少的要求。

值得注意的是，当C取无穷大时，最小化该方程的最优解迫使所有样本均满足约束，也就是将书上的(6.29)等价于前面硬间隔的(6.6)。

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

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

构建拉格朗日函数：

得出对偶问题：

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

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

通过替换上面结构风险和经验风险两个部分, 可以得到许多其他学习模型如：对数几率回归(Logistic Regression) 最小绝对收缩选择算子(LASSO)。

从经验风险最小化的角度看，结构风险表述了我们希望获得具有何种性质的模型（如复杂度最小的模型），有助于削减假设空间，从而降低了最小训练误差的过拟合风险。从降低过拟合风险这个角度看，上图所写的一般形式可称为“正则化问题”（第6.1节也是从降低过拟合的角度出发取||w||² 正则化）。于是，结构风险称为正则化项，C称为正则化常数。