模式识别 —— 第六章 支持向量机（SVM）与核（Kernel）

模式识别 —— 第六章 支持向量机（SVM）与核（Kernel）

开始之前先推荐一个个人感觉把SVM讲的特别好的课程视频（尤其是转对偶问题那一部分），浙大胡浩基老师手写板书讲的，真的草履虫都能看懂！

点一下 嗖~就过去

硬间隔与软间隔区别如下：

硬间隔
完全分类准确，只在数据是线性可分离的时候才有效。其损失函数不存在，损失值为0。但它对异常值非常敏感，无法很好的泛化。

软间隔
要避免这些问题，最好使用更灵活的模型。目标是尽可能在保持最大间隔宽度和限制间隔违例之间找到良好的平衡，这就是软间隔分类。

所以软间隔允许一定量的样本分类错误；优化函数包括两个部分，一部分是点到平面的间隔距离，一部分是误分类的损失个数；C是惩罚系数，误分类个数在优化函数中的权重值；权重值越大，误分类的损失惩罚的越厉害。

硬间隔（Hard-Margin）

我们想找到一个超平面让其线性可分，数学表述如下：

a式子与b式子合并可得到下面的统一表示。

现在我们想让在这个分界线（面）附近的点（即支持向量）离它尽量远一点。由点到直线距离公式来使得Margin最大。

然后我们想办法将最大化Margin转化为下面这个优化问题：

怎么转化的呢？首先我们有两个事实条件：

之后：

此时，对于非支持向量那就相当于$|w^T{x}_0+b|>1$
把y写进去来代替绝对值符号的作用就可以得到新的限制条件$y(w^T{x}_0+b)\ge 1$

最后我们为了后续求导方便，我们可以在目标函数处多加一个$\frac{1}{2}$，如下：

这样就变成了一个凸优化的问题，即要么无解、要么只有一个极值。因此局部极值就是最值。

软间隔（Soft-Margin）

SVM对训练集里面的每个样本$(x_i,y_i)$引入了一个松弛变量${\xi }_i\ge 0$,使函数间隔加上松弛变量大于等于1，也就是说条件变量改为如下:

$$yi(w\bullet xi+b)\ge 1-\xi i$$

加入松弛变量${\xi }_i$后，损失函数就需要改写为:
$$min\frac{1}{2}||w_i|{|}^2+C\sum _{i=1}^n{\xi }_i$$

$$s.t.y_i(w^T{x}_i+b)\ge 1-{\xi }_i(i=1,2,...m)$$

$${\xi }_i\ge 0(i=1,2,...m)$$

这里，C>0为惩罚参数，可以理解为我们一般回归和分类问题正则化时候的参数。C越大，对误分类的惩罚越大，C越小，对误分类的惩罚越小。

也就是说，我们希望$\frac{1}{2}||w_i|{|}^2$尽量小，误分类的点尽可能的少。C是协调两者关系的正则化惩罚系数。在实际应用中，需要调参来选择。

核kernel

对于在低维线性不可分的数据，在映射到了高维以后，就变成线性可分的了。例如：

左边是在二维空间的投影，我们没办法找到一条直线将两个类别区分开。但是如果我们将二维空间映射到三维空间的话，我们就可以找到一个超平面在三维中线性可分。

就像是三体中狄奥伦娜能进入四维空间后轻易的取人脑子一样。

维度越高线性可分就越容易。但是映射成的高维维度是爆炸性增长的，这个计算量实在是太大了，而且如果遇到无穷维的情况，就根本无从计算了。这就要用到我们的核函数了。

核函数的价值在于它虽然也是将特征进行从低维到高维的转换，但核函数好在它在低维上进行计算，而将实质上的分类效果（利用了内积）表现在了高维上，这样避免了直接在高维空间中的复杂计算，真正解决了SVM线性不可分的问题。

线性核函数
线性核函数（Linear Kernel）其实就是內积，如下：
$$K(x,y)=x\bullet y$$

多项式核函数
多项式核函数（Polynomial Kernel）是线性不可分SVM常用的核函数之一，公式如下：
$$K(x,y)=(\gamma x\bullet y+r{)}^d$$

高斯核函数
高斯核函数（Gaussian Kernel），在SVM中也称为径向基核函数（Radial Basis Function,RBF），它是非线性分类SVM最主流的核函数。libsvm默认的核函数就是它。公式如下：

$$K(x,y)=e^{-\frac{||x-y|{|}^2}{2{\sigma }^2}}$$

对偶问题

这部分建议看视频部分的讲解，讲的真的超级棒！

这里我们采用的是拉格朗日乘子将其转化成对偶问题，思路如下：

硬间隔优化问题的对偶转变

按照上述思路，首先我们将限制条件转换成$a(x)\le 0$的形式：

之后我们构建拉格朗日常数：

因为是求最值，所以我们求导进行回代：

考点

这是我们这学期的期末考试题，老师提前透露的。也是类似上面的推导，只不过要简单一点再。

就是如果目标函数不是$w^T{x}_i+b$而是$w^T{x}_i$，请进行对偶问题的转换。其实是变简单了，不用对b进行求导回代了。解法如下：

可恶啊，背面画着图透过来了。算了，凑合看吧，其实结果是一样的。

软间隔优化问题的对偶转变