《机器学习》笔记-支持向量机（6）

刘才权

写在最前面

如今机器学习和深度学习如此火热，相信很多像我一样的普通程序猿或者还在大学校园中的同学，一定也想参与其中。不管是出于好奇，还是自身充电，跟上潮流，我觉得都值得试一试。对于自己，经历了一段时间的系统学习（参考《机器学习/深度学习入门资料汇总》），现在计划重新阅读《机器学习》[周志华]和《深度学习》[Goodfellow et al]这两本书，并在阅读的过程中进行记录和总结。这两本是机器学习和深度学习的入门经典。笔记中除了会对书中核心及重点内容进行记录，同时，也会增加自己的理解，包括过程中的疑问，并尽量的和实际的工程应用和现实场景进行结合，使得知识不只是停留在理论层面，而是能够更好的指导实践。记录笔记，一方面，是对自己先前学习过程的总结和补充。 另一方面，相信这个系列学习过程的记录，也能为像我一样入门机器学习和深度学习同学作为学习参考。

章节目录

• 间隔与支持向量
• 对偶问题
• 核函数
• 软间隔与正则化
• 支持向量回归
• 核方法

（一）间隔与支持向量

给定训练样本D={{x1, y1}, {x2, y2}, ...,{xm, ym}}, yi∈{-1, +1}，分类学习最基本的想法就是基于训练集D在样本空间找到一个划分超平面，

在样本空间中，划分超平面可通过如下线性方程来描述，

假设超平面（w，b）能将训练样本正确分类，即对于(xi, yi)∈D，令，


距离超平面最近的这几个训练样本点称为“支持向量”（support vector），两个异类支持向量到超平面的距离之和为，

称为“间隔”（margin）。
找到“最大间隔”（maximum margin）的划分超平面，就是支持向量机（Support Vector Machine，简称SVM）的基本型。

（二）对偶问题

我们对SVM基本型求解是一个凸二次规划（convex quadratic programming）问题，能直接用现成的优化计算包求解，但我们可以有更高效的办法。即对SVM的基本型使用拉格朗日算子法得到其“对偶问题”（dual problem）。

（三）核函数

在现实任务中，原始样本空间内也许并不存在一个能正确划分两类样本的超平面。对这样的问题，可以将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。如下图，

幸运的是，如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分。
令Φ(x)表示将x映射后的特征向量，于是，在特征空间中划分超平面所对应的模型可表示为，

其对偶问题是，


求解设计到计算，

，这是样本xi与xj映射到特征空间之后的内积。由于特征空间的维数可能很高，甚至可能到无穷维，因此直接计算通常是困难的。为了避开这个障碍，可以假设这样一个函数，

即xi与xj在特征空间的内积等于他们原始样本空间通过函数k(. , .)计算的结果。有了这样的函数，我们就不必直接计算高维甚至无穷维特征空间中的内积。这里的函数k(. , .)就是“核函数”（kernel function）。
“核函数选择”是支持向量机的最大变数。常用的核函数有，

此外，还可以通过函数的组合得到。

（四）软间隔与正则化

在前面的讨论中，我们一直假定训练样本在训练空间或特征空间中是线性可分的，即存在一个超平面将不同类的样本完全划分开。然而，在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分。
缓解该问题的一个办法是允许支持向量机在一些样本上出错。为此引入了“软间隔”（soft margin）的概念，如下图所示，

具体来说，前面介绍的支持向量机形式是要求所有样本均满足约束，即所有样本必须划分正确，这称为“硬间隔”（hard margin），而软间隔则是允许这样的样本不满足约束。

（五）支持向量回归

对样本（x，y），传统回归模型通常直接基于模型输出f(x)与真实输出y之间的差别来计算损失，当切仅当f(x)与y完全相同时，损失才为零。于此不同，支持向量回归（Support Vector Regression，简称SVR）假设我们能容忍f(x)与y之间最多有ε的偏差，即仅当f(x)与y之间的差别绝对值大于ε时才计算损失。如下图所示，

（六）核方法

根据“表示定理”，对于一般的损失函数和正则化项（不要求是凸函数），优化问题的最优解都可表示为核函数的线性组合。这显示出核函数的巨大威力。
人们发展出一系列基于核函数的学习方法，统称为“核方法”（kernel methods）。最常见的，是通过“核化”（即引入核函数）来将线性学习器拓展为非线性学习器。