---
title: '如何理解SVM | 支持向量机之我见'
pubDate: 2016-05-14
tags:
  - 'ml'
description: '如何理解SVM | 支持向量机之我见'
---

**囫囵吞枣看完SVM，个人感觉如果不好好理解一些概念，或说如果知其然而不知其所以然的话，不如不看。因此我想随便写一写，把整个思路简单地整理一遍。：）**

## SVM与神经网络

支持向量机并不是神经网络，这两个完全是两条不一样的路吧。不过详细来说，线性SVM的计算部分就像一个单层的神经网络一样，而非线性SVM就完全和神经网络不一样了（是的没错，现实生活中大多问题是非线性的），详情可以参考[知乎答案](https://www.zhihu.com/question/22290096)。

这两个冤家一直不争上下，最近基于神经网络的深度学习因为AlphaGo等热门时事，促使神经网络的热度达到了空前最高。毕竟，深度学习那样的多层隐含层的结构，犹如一个黑盒子，一个学习能力极强的潘多拉盒子。有人或许就觉得这就是我们真正的神经网络，我们不知道它那数以百千计的神经元干了什么，也不理解为何如此的结构能诞生如此美好的数据 —— 犹如复杂性科学般，处于高层的我们并不能知道底层的”愚群“为何能涌现。两者一比起来，SVM似乎也没有深度学习等那么令人狂热，连Hinton都开玩笑说SVM不过是浅度学习（来自深度学习的调侃）。

不然，个人觉得相对于热衷于隐含层的神经网络，具有深厚的数学理论的SVM更值得让我们研究。SVM背后伟大的数学理论基础可以说是现今人类的伟大数学成就，因此SVM的解释性也非神经网络可比，可以说，它的数学理论让它充满了理性，这样的理性是一个理工科生向往的。就如，你渴望知道食物的来源以确定食物是否有毒，如果有毒是什么毒，这样的毒会在人体内发生了什么反应以致于让你不适 —— 我的理性驱使我这么想，一个来路不明的食物是不能让我轻易接受的。

## SVM是什么

简单点讲，SVM就是个分类器，它用于回归的时候称为SVR（Support Vector Regression），SVM和SVR本质上都一样。下图就是SVM分类：

![](https://source.mkshell.com/2016-05-14-14632059577714.jpg) （边界上的点就是支持向量，这些点很关键，这也是”支持向量机“命名的由来）

**SVM的目的：寻找到一个超平面使样本分成两类，并且间隔最大。而我们求得的w就代表着我们需要寻找的超平面的系数。**

用数学语言描述： ![](https://source.mkshell.com/2016-05-14-14632106164393.jpg) 这就是SVM的基本型。

SVM的基本型在运筹学里面属于二次规划问题，而且是凸二次规划问题（convex quadratic programming）。

## 二次规划

二次规划的问题主要用于求最优化的问题，从SVM的求解公式也很容易看出来，我们的确要求最优解。

简介： 在限制条件为 ![](https://source.mkshell.com/2016-05-14-14632121860594.png) 的条件下，找一个n 维的向量 x ，使得 ![](https://source.mkshell.com/2016-05-14-14632122006481.png) 为最小。

其中，c为n 维的向量，Q为n × n 维的对称矩阵，A为m × n 维的矩阵，b为m 维的向量。

其中，根据优化理论，如果要到达最优的话，就要符合KKT条件（Karush-Kuhn-Tucker）。

## KKT

KKT是在满足一些有规则的条件下，一个非线性规则问题能有最优解的一个充分必要条件。也就是说，只要约束条件按照这个KKT给出的规则列出，然后符合KKT条件的，就可以有最优解。这是一个广义化拉格朗日乘数的成果。

把所有的不等式约束、等式约束和目标函数全部写为一个式子 `L(a, b, x)= f(x) + a*g(x)+b*h(x)` 　　 KKT条件是说最优值必须满足以下条件： - L(a, b, x)对x求导为零 - h(x) = 0 - a\*g(x) = 0

## 对偶问题

将一个原始问题转换为一个对偶问题，懂的人知道对偶问题不过是把原始问题换了一种问法，从另一角度来求问题的解，其本质上是一样的。就好像我不能证明我比百分之五的人丑，但是我能证明我比百分之九十五的人帅，那样就够了。那么，为啥要用对偶问题，直接求原始问题不好吗？参考一下[为什么我们要考虑线性规划的对偶问题？](https://www.zhihu.com/question/26658861/answer/53394624)

而二次规划的对偶问题也是二次规划，性质、解法和原来一样，所以请放心。（只做简要介绍 最后训练完成时，大部分的训练样本都不需要保留，最终只会保留支持向量。这一点我们从图上也能看得出来，我们要确定的超平面只和支持向量有关不是吗？

![](https://source.mkshell.com/2016-05-14-14632134952575.jpg) （你看，只和支持向量有关）

然而，问题又出现了（新解法的出现总是因为新问题的出现），对于SVM的对偶问题，通过二次规划算法来求解的计算规模和训练样本成正比，开销太大。换句话来说，输入数据小的时候还好，不过小数据几乎没啥用，但是数据量大起来又计算量太大，所以就得寻找一种适合数据量大而且计算量小的解法，这个就是SMO。

## SMO

SMO，Sequential Minimal Optimization，针对SVM对偶问题本身的特性研究出的算法，能有效地提高计算的效率。SMO的思想也很简单：固定欲求的参数之外的所有参数，然后求出欲求的参数。

例如，以下是最终求得的分类函数，也就是我们SVM的目标： ![](https://source.mkshell.com/2016-05-14-14632140318075.jpg) SMO算法每次迭代只选出两个分量ai和aj进行调整，其它分量则保持固定不变，在得到解ai和aj之后，再用ai和aj改进其它分量。

如何高效也能通过SMO算法的思想看得出来 —— 固定其他参数后，仅优化两个参数，比起之前优化多个参数的情况，确实高效了。然而，与通常的分解算法比较，它可能需要更多的迭代次数。不过每次迭代的计算量比较小，所以该算法表现出较好的快速收敛性，且不需要存储核矩阵，也没有矩阵运算。说白了，这样的问题用SMO算法更好。

## 核函数

我们的SVM目的其实也简单，就是找一个超平面，引用一张图即可表述这个目的： ![](https://source.mkshell.com/2016-05-14-14632144374512.jpg)

然而现实任务中，原始样本空间也许并不能存在一个能正确划分出两类样本的超平面，而且这是很经常的事。你说说要是遇到这样的数据，怎么划分好呢：

![](https://source.mkshell.com/2016-05-14-14632143758259.jpg) 告诉我你的曲线方程吧，傻了吧~

于是引入了一个新的概念：核函数。它可以将样本从原始空间映射到一个更高维的特质空间中，使得样本在这个新的高维空间中可以被线性划分为两类，即在空间内**线性划分**。这个过程可以观看[视频](https://www.youtube.com/watch?v=3liCbRZPrZA)感受感受，由于是youtube所以我截一下图：

这是原始数据和原始空间，明显有红蓝两类： ![](https://source.mkshell.com/2016-05-14-14632147909478.jpg)

通过核函数，将样本数据映射到更高维的空间（在这里，是二维映射到三维）： ![](https://source.mkshell.com/2016-05-14-14632148908664.jpg)

而后进行切割： ![](https://source.mkshell.com/2016-05-14-14632149178576.jpg)

再将分割的超平面映射回去： ![](https://source.mkshell.com/2016-05-14-14632149709432.jpg)

![](https://source.mkshell.com/2016-05-14-14632149780244.jpg)

大功告成，这些就是核函数的目的。

再进一步，核函数的选择变成了支持向量机的最大变数（如果必须得用上核函数，即核化），因此选用什么样的核函数会影响最后的结果。而最常用的核函数有：线性核、多项式核、高斯核、拉普拉斯核、sigmoid核、通过核函数之间的线性组合或直积等运算得出的新核函数。（这里只涉及概念，不涉及数学原理）

## 软间隔

知道了上面的知识后，你不是就觉得SVM分类就应该是这样的： ![](https://source.mkshell.com/2016-05-14-14632153433430.jpg)

然而这也不一定是这样的，上图给出的是一种完美的情况，多么恰巧地两类分地很开，多么幸运地能有一个超平面能将两个类区分开来！要是这两个类有一部分掺在一起了，那又该怎么分啊： ![](https://source.mkshell.com/2016-05-14-14632157241594.jpg)

有时候如果你非要很明确地分类，那么结果就会像右边的一样 —— 过拟合。明显左边的两个都比过拟合好多了，可是这样就要求允许一些样本不在正确的类上，而且这样的样本越少越好，”站错队“的样本数量要通过实际来权衡。这就得用上”软间隔“，有软间隔必然有硬间隔，应间隔就是最开始的支持向量机，硬间隔支持向量机只能如此”明确“地分类。特意找来了这个数学解释：

![](https://source.mkshell.com/2016-05-14-14632160235765.jpg)

其中一个样本要是”站错队“就要有损失，我们的目的就是：找出总损失值最小并且能大概分类的超平面。而计算一个样本的损失的损失函数也有很多种，例如：hinge损失、指数损失、対率损失等。

只是简单地把思路整理了一遍而已。

若有错误之处请指出，更多地关注[煎鱼](http://www.jianyujianyu.com)。