积跬步以致千里,积怠惰以致深渊
注：本篇文章整理时主要参考了 周志华 的《机器学习》。
主要内容
支持向量机会接受数据点，并输出一个超平面（在二维的图中，就是一条线）以将两类分割开来。这条线就是判定边界：将红色和蓝色分割开来。
但是，最好的超平面是什么样的？对于SVM来说，它是最大化两个类别边距的那种方式，换句话说：超平面（在本例中是一条线）对每个类别最近的元素距离最远。
什么是SVM
好吧，故事是这样子的：
在很久以前的情人节，大侠要去救他的爱人，但魔鬼和他玩了一个游戏。
魔鬼在桌子上似乎有规律放了两种颜色的球，说：“你用一根棍分开它们？要求：尽量在放更多球之后，仍然适用。”
于是大侠这样放，干的不错？
然后魔鬼，又在桌上放了更多的球，似乎有一个球站错了阵营。
SVM就是试图把棍放在最佳位置，好让在棍的两边有尽可能大的间隙。
现在即使魔鬼放了更多的球，棍仍然是一个好的分界线。
然后，在SVM 工具箱中有另一个更加重要的trick。 魔鬼看到大侠已经学会了一个trick，于是魔鬼给了大侠一个新的挑战。
现在，大侠没有棍可以很好帮他分开两种球了，现在怎么办呢？当然像所有武侠片中一样大侠桌子一拍，球飞到空中。然后，凭借大侠的轻功，大侠抓起一张纸，插到了两种球的中间。
现在，从魔鬼的角度看这些球，这些球看起来像是被一条曲线分开了。
再之后，无聊的大人们，把这些球叫做「data」，把棍子 叫做「classifier」, 最大间隙trick 叫做「optimization」， 拍桌子叫做「kernelling」, 那张纸叫做「hyperplane」。
找寻最佳超平面
1）为“最佳”的超平面定性
在考虑哪一个超平面性能会更佳时，一个直观的想法就是位于两类训练样本“正中间”的划分超平面会更好一些，因为它对训练样本局部扰动的“容忍性”最好。而这个正中间的超平面一定满足这样的一个条件，那就是离它最近的正例数据和反例数据到它的距离之和最大。
所以，支持向量机算法第一步将寻找“最佳”超平面的问题转换为寻找“最大间隔”的划分超平面问题。
2）“最大间隔”由什么确定
为了更形象地表现正负样本的间隔，我们可以在分割超平面的两侧再定义两个平行的超平面H1和H2，这两个超平面分别通过正样本和负样本中离分割超平面最近的样本点。
我们定义超平面H1和H2上面的点叫做支持向量。正负样本的间隔可以定义为超平面H1和H2之间的间隔，它是分割超平面距最近正样本点距离和最近负样本点距离之和。
支持向量对于分割超平面的位置是起到关键作用的。在优化分割超平面位置之后，支持向量也显露出来，而支持向量之外的样本点则对分类并不关键。为什么这样说呢？因为即使把支持向量以外的样本点全部删除，再找到最优的分割超平面，这个超平面的位置跟原先的分割超平面的位置也是一样的。总结起来就是：支持向量包含着重构分割超平面所需要的全部信息！
支持向量机算法将寻找“最大间隔”的问题转换为不等式约束的优化问题。
所以总结一下，支持向量机分类的背后逻辑是：找到最好的超平面将训练样本正确分类 --> 最好的超平面为是正反例样本“间隔最大”的平面 --> 间隔最大的平面寻找实际上是一个不等式约束优化问题。
3）当超平面在样本空间上无法划分开训练样本时，该如何处理？
在前面的讨论中，我们假设训练样本是线性可分的，然而在现实任务中，原始样本空间内也许并不存在一个能正确划分两类样本的超平面。
对待原始数据无法线性可分的问题，一个合适的思路是将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。
如上所示有两类圆点，分别是蓝点和红点。容易发现我们不能够找到一条直线将圆点分类。即线性不可分。
但如果将一维圆点映射到二维，就容易找出能够将圆点分类的直线。
下图同样为在线性不可分的情况下映射到更高维的视觉化演示。
由于样本 xi 和 xj 映射到特征空间之后的内积因为维数可能很高，所以比较难直接计算。为了避开这个障碍，我们设计了“核函数”（kernel function），这个函数使得 xi 和 xj 在特征空间的内积等于它们在原始样本空间中通过核函数 k(xi, xj) 计算的结果。
如果我们已知合适的特征映射O(.)的具体形式，则可写出核函数 k(. , .)，但在现实任务中我们通常不知道O(.)是什么形式。
幸运的是，我们知道：只要一个对称函数所对应的核矩阵是半正定，它就能作为核函数使用，并且对于一个半正定核矩阵，总能找到一个与之对应的映射O(.)空间。
所以，我们知道了吧，对于在样本空间中无法线性可分的数据，我们不是先去找到使它线性可分的映射空间，然后通过核函数去计算的；相反，我们是得要选择一个核函数先，然后通过这个核函数去找到对应的映射特征空间，并计算在该映射空间上的最优超平面。
通过前面的讨论可知，我们希望样本在特征空间内线性可分，因此特征空间的好坏对支持向量机的性能至关重要。很显然，核函数的选择不当，很可能会导致样本被映射到一个不好的空间，导致算法性能不佳。于是，“核函数选择”成为了支持向量机的最大变数。
4）当超平面无法完全划分开训练样本时，该如何处理？
因为在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分，为了缓解该问题，一个合理的办法是允许支持向量机在一些样本上出错。这种策略被称为“软间隔”（soft margin），它允许某些样本不满足不等式约束。
当然，在最大化间隔的同时，不满足约束的样本应尽可能少。我们在之前的优化目标式子中加入了损失函数的影响，当样本落入不满足约束的空间内时，损失函数的值就会变大，使得优化目标的值向反方向移动；当样本落入满足约束的空间内时，损失函数的值减小甚至为0，使得优化目标的值向着目标方向移动。C > 0是个常数，代表着损失函数的影响力，当C无穷大时，会迫使所有的样本要满足约束；当C取有限值时，允许一些样本不满足约束。
5）支持向量回归（SVR）
支持向量机是一个二分类器，SVR就是支持向量机算法在回归模型上的应用。同前一节的方式类似，只不过这次引入的损失函数是根据回归模型的原理设计的，是一个预测结果g(x)与真实结果y之间的差值，当这个差值大于一个常数 e 时，才会被计算。
6）核方法
给定训练样本，若不考虑偏移项，则无论 SVM 还是 SVR ，学得的模型总能表示成核函数的线性组合。正因为核函数的重要性，人们发展出一系列基于核函数的学习方法，统称为“核方法”（kernel methods）
总结
[1] 支持向量机的基本思想是：基于训练集 D 在样本空间中找到一个划分超平面，将不同类别的样本分开
[2] 支持向量机的目标是：找到泛化性能最佳的那个超平面
[3] 支持向量机的计算逻辑是：第一步将寻找“最佳”超平面的问题转换为寻找“最大间隔”的划分超平面问题；第二步将寻找“最大间隔”的问题转换为不等式约束的优化问题
[4] 当超平面无法在样本空间中将训练数据划分开时，将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分
[5] 当超平面无法完全将训练数据划分开时，使用软间隔的策略，允许某些样本不满足不等式约束。具体通过引入损失函数到优化目标方程中实现。
[6] 训练好的模型的算法复杂度是由支持向量的个数决定的，而不是由数据的维度决定的。所以SVM不太容易产生overfitting。
[7] SVM训练出来的模型完全依赖于支持向量(Support Vectors)，即使训练集里面所有非支持向量的点都被去除，重复训练过程，结果仍然会得到完全一样的模型。
[8] 一个SVM如果训练得出的支持向量个数比较小，SVM训练出的模型比较容易被泛化。
