【机器学习】支持向量机原理

在支持向量机中有三个重要概念，也是组成支持向量机的重要构件，是需要时时关注的，如果文中提到它们，请一定注意：

最大间隔
高维映射
核方法

这三个构件是彼此独立又互相关联的关系。三者关系我会选择用旧式的冒险电影剧情来形容，那就是“千里之行始于‘最大间隔’，在‘高维映射’迎来升华，最后通过‘核方法’修成正果”。

支持向量机算法原理

最大间隔

支持向量机的原理说容易也真是容易，说不容易也真不容易。支持向量机说到底就是一种“线性分类器”，它以“间隔”作为损失的度量，目标通过不断调整多维的“直线”——超平面，使得间隔最大化。所谓“支持向量”，就是所有数据点中直接参与计算使得间隔最大化的几个数据点，这是支持向量机的得名由来，也是支持向量机的全部核心算法。

单就核心来看，实际上就是一种换了损失函数的线性方法。这也是为什么很多介绍支持向量机的教材的主要内容都放在怎么计算各种“间隔”上，给人一种支持向量机就是计算间隔的感觉。

这种简化方法选择突出支持向量机的基本运行逻辑，而且最大间隔说到底也就是一个计算问题，并不涉及太拗口的数学名词和太抽象的概念，在便于理解方面确实有优势。而且光靠间隔最大化，支持向量机也确实能运转起来，乍一看让人感觉这种介绍很“完整”。但这种简化方法存在一个重大问题：如果支持向量机只有间隔，那真的就成了又一种线性分类器，初学者可能很难察觉其中存在的问题，反而容易以偏概全，产生误导。

高维映射

其实，支持向量机除了间隔最大化外，还有另一大绝活就是高维映射。高维映射是支持向量机的主要卖点，也是理解支持向量机的难点。于是，另一些支持向量机的教材就选择把焦点集中在高维映射上，将支持向量机塑造为深不可测的武林高手，从而把对支持向量机的介绍推向另一个极端。

高维映射很难理解，难就难在如何用线性分类器去解决非线性可分问题。这句话很拗口，但意思很清楚，线性方法当然适合解决线性分布的数据，直觉上就能感受到它对非线性分布的数据集的无能为力，从而也能体会到支持向量机在这点上取得突破的难能可贵。

高维映射被许多教程说得神乎其神，但前面我们已经一再解释过它的原理，其核心就是通过映射，把线性不可分的数据变成线性可分，具体来说就是增加维度，如把原本排成一条直线的正负样本点“掰弯”，或者给原本平铺在同一平面上互相包围的正负样本点添加一个“漏勺”，也就是加了一维高度值，使得非线性分布出现了线性可分的差异，从而最终达到分离正负类的目的，实现用线性分类器对非线性可分样本点进行分类的效果。

核函数

说到支持向量机，除非是选择只介绍间隔最大化，否则总是免不了提到核函数（Kernel Function）这个术语。“核函数”听起来很吓人，我第一次看到时还下意识地往原子能方面靠。其实，核函数并没有那么深奥，它与前面接触的Logistics函数一样，功能就是映射，说穿了就是给线性“披”一层马甲，变成曲线或者曲面，Logistics函数就通过映射把直线变成了S型曲线。

核函数也一样。核函数不是一种函数，而是一类功能性函数，能够在支持向量机中完成高维映射这种功能的函数都称为核函数，也就是说，只要数学函数满足要求，就都可以被用作核函数。不过，无论哪种核函数，其最根本的目的就是完成高维映射，具体完成两项工作，一是增加空间的维度，二是完成对现有数据从原空间到高维空间的映射。

也就是说，核函数和高维映射虽然在讲解时拆分成两个概念，其实都是一个过程，二者可以看作因和果的关系。我们必须首先选定一款核函数，才能通过核函数将数据集进行映射，从而得到高维映射的结果。

最后需要说明的是，核函数虽然是一类函数，具体有很多“款式”，Scikit-Learn包中也提供了多种核函数的选择，但是在一次支持向量机的学习过程中，需要首先设置好选择哪种数学函数作为核函数，且在整个运行过程中都将使用这个函数进行高维映射，而不会随着学习的进程调整和改变具体的核函数。这也与Logistics回归一样，S型曲线函数很多，但Logistics回归在整个学习过程中都是使用Logistics函数作为S型曲线的映射函数，而不会在运行过程中进行另外的调整。

支持向量机的真正运行机制

为什么这里要加上“真正”两个字呢？前面也说了，光是使用间隔最大化机制，支持向量机也是可以运转的，只不过这时的支持向量机是一个删减版，实际只是又一种线性分类器，无法突破线性分类的局限，也就是无法解决非线性问题。
真正的支持向量机是由间隔最大化和高维映射两大部件组成。间隔最大化是目标，支持向量机的损失函数依靠间隔计算，能让间隔达到最大的就是支持向量机要“学习”的过程。
高维映射用于解决线性不可分问题，可以理解为对数据的“预处理”。对于那些你中有我、间不容发的非线性分布数据，首先通过核函数映射至高维，映射后的数据集呈线性分布，为使用线性方法分类创造了条件。
最后归纳一下，使用支持向量机进行分类经过三个步骤：

选取一个合适的数学函数作为核函数。
使用核函数进行高维映射，数据点在映射后由原本的线性不可分变为线性可分。
间隔最大化，用间隔作为度量分类效果的损失函数，最终找到能够让间隔最大的超平面，分类也就最终完成了。

核技巧

当你看到这一段时，心里应该清楚两点，一是支持向量机就是一台线性分类器，二是这台线性分类器可以通过高维映射来解决非线性分布问题。解决了旧问题，新的问题也随之而来：能不能把高维映射独立出来，作为一种通用化的组件，将所有非线性分布的数据集转化成线性分布，然后随便再选择一种线性分类器完成分类呢？这个问题也就是支持向量机是否能拆分的问题。

这个想法是非常好的，很多新算法就是靠这种灵光闪现才得以最终出现。不过，支持向量机并不可以拆分，原因可以用软件工程来解释：支持向量机为了兼顾理论的优雅和运行的高效，在设计上选择了紧耦合，使得两项看似可以独立完成的工作变得密不可分。

问题从何而来呢？完整的支持向量机包括了间隔最大化和高维映射，就像是一部悬疑大片的两条主线，单独拎出来看好像都没有问题，但合在一起问题就来了。又要间隔最大化又要高维映射，听起来鼓舞人心，可是细细一算就不难发现：维度越高意味着间隔最大化的计算量越大，实际运行起来效率可能非常低下，可是如果要照顾效果而削减维度，可能无法完成非线性分布数据映射成线性分布这项重要任务。两条主线互相“打架”，若一条想要完美收场，另一条就只能草草收场，总是不尽如人意。

眼看大片就要“烂尾”，这时化腐朽为神奇的核函数再次出来救场。在支持向量机中，涉及“核”的术语实际上有三个，分别是核函数、核方法（Kernel Method）和核技巧（Kernel Trick），三个术语说复杂也复杂，不过说简单也简单，核方法和核技巧就是提出需求，核函数则是给出解答。换而言之，核函数是一石二鸟，实际上是完成了两项独立的任务。

任务一是完成核方法提出的要求，就是如何将低维非线性数据映射成高维数据，从而变成线性可分。前面我们反反复复介绍的其实就是核方法的内容，但这并不是核函数的全部内容。

任务二是完成核技巧提出的要求，之所以称为“技巧”，是因为核技巧主要是提高核方法的计算效率。前面我们将高维映射和间隔最大化认为是支持向量机的两大部分，按照这种理解，数据应该首先完成高维映射，然后计算间隔，最后再进行间隔最大化，也因此产生了双主线“打架”的问题。

核技巧就是要解决这个问题。计算间隔涉及向量点积运算，如果先进行高维映射再进行向量点积运算，这会导致运算量激增，尤其是高维向量运算，由于参加运算的维度增加了，运算量也会显著增加。

核技巧简化了这个过程：只需要输入原始向量就能通过核技巧计算直接得到正确的点积结果，而不用把两个向量分别完成高维映射，再进行点积运算，即将两项工作用数学技巧一次就完成。由于无论是目标函数还是决策函数都只涉及输入样本与样本之间的内积，这一运算特点使得我们在实际使用支持向量机算法进行学习时，不需要显式地完成高维映射操作，只需要事先定义核函数即可得到等价的结果，还避免了高维向量的运算，明显提高了运算效果。能够同时满足核方法和核技巧两项要求，才是核函数完整的工作内容。

支持向量机的数学解析

点到超平面的距离

支持向量机以“间隔”作为损失函数，支持向量机的学习过程就是使得间隔最大化的过程，想了解支持向量机的运转机制，首先就得知道间隔怎么计算。而支持向量机对间隔的定义其实很简单，就是作为支持向量的点到超平面的距离的和，这里的距离就是最常见的几何距离。我们用wx+b来表示超平面，点到三维平面的距离有现成的公式可以套用：

这是初中的几何知识。类似的，对于点到N维超平面的距离r，可以用以下公式计算：

其中被除数 $wx^i+b$ 是超平面的表达式，除数 $||w||$ 就是我们前面所讲的L2范式的简略写法。点到N维超平面的距离的公式计算很简单，形式上与点到三维平面的公式类似，其实当w是三维向量时，二者就是等价的。支持向量机就使用这条公式来计算点到超平面的距离。

间隔最大化

支持向量机使用y=1表示正类的分类结果，使用y=-1表示负类的分类结果，既然y=wx+b要么大于或等于1，要么小于或等于-1，间隔是由正负类最近的两个数据点，也就是支持向量决定，因此间隔距离也就可以表示为 $\frac{2}{||w||}$ 。

我们的目的就是间隔最大化。2是一个常数，所以最大化间隔距离可以表示如下：

右边的s.t．表示suject to，意思是受到约束，我们把之前的条件写上，相当于“在……的条件下”，使得左边式子最大。分母越小，分数越大，所以左式也可以表示如下：

这个式子看起来计算很简单，就是求极值，但要注意后面多了个约束条件，问题就稍微变复杂了。这里不具体展开，只需要记得可以用拉格朗日乘子法转化成如下拉格朗日函数：

其中α被称为“拉格朗日乘子”。上式分别对w和b求导，并令导数为0，右式可转化为下式：

这时问题就变成了：

约束条件为：

这个式子通常用二次规划算法SMO（Sequential Minimal Optimization）算法求解。上面的式子转化包含大量复杂的数学概念和运算，这里只需要注意两点，一是支持向量机使用拉格朗日乘子法搭配SMO算法求得间隔最大，二是转化式的末尾为计算，也就是两个向量的内积。正因为间隔最大化可以转化为向量内积的运算，才使得高维映射可以通过核技巧进行优化。

核函数

高维映射实际上也是一种函数映射，在支持向量机中，通常采用符号φ来表示这个将数据映射到高维空间的函数，向量xi经过高维映射后就变成了 $φ(x)i$ ，这时超平面的表达式也就相应变成了 $w^Tφ(x_i)+b$

根据上述间隔最大化的拉格朗日函数，我们知道需要进行两个向量的内积运算，那么映射后的内积运算为 $φ(x_i)^Tφ(x_j)$ 。映射后向量变成高维向量，运算量将明显增加，直接运算会导致效率明显下降。

不过，我们也已经观察到，在间隔最大化的运算中只使用了高维向量内积运算的结果，而没有单独使用高维向量，也就是说，如果能较为简单地求出高维向量的内积，同样可以满足求解间隔最大化的条件。我们可以假设存在函数K，能够满足以下条件：

这里的函数K就是我们前面一再介绍的核函数。有了核函数，所有涉及 $φ(x_i)^Tφ(x_j)$ 的内积运算都可以通过 $K(x_i,x_j)$ 简单求出，这也就是为什么核函数需要一边完成核方法的高维映射，一边又要完成核技巧的求内积结果。对于已知的映射函数φ，核函数是很容易计算的，但在大多数情况下，使用支持向量机时并不知道映射函数φ的具体形式，好在数学家已经证明，在这种情况下数学函数只需要满足几个条件，就同样可以作为核函数，也就确保了核函数的存在性。