支持向量机

支持向量机是一个功能请打并且全面的机器学习模型，它能够执行线性或非线性、回归，甚至是异常值检测任务。它是机器学习领域最受欢迎的模型之一。SVM特别适用于中小型复杂数据集的分类。

一、线性SVM分类

可以将SVM分类器视为在类别之间拟合可能的最宽的街道，因此也可以叫做大间隔分类。

注意，在街道意外的地方增加更多训练实例，不会对决策边界产生影响，也就是说它完全由街道边缘的实例所决定。SVM对特征的缩放非常敏感。

二、软间隔分类

1、硬间隔分类：如果严格地让所有实例都不在街道上，并且位于正确的一边

2、硬间隔分类的两个问题：（1）它只在数据是线性可分离的时候才有效

                                                  （2）它对于异常值非常敏感

3软间隔分类：避免这些问题，最好使用更灵活的模型。目标是尽可能在保持街道宽度和限制间隔违例(即位于街道之上，升值在错误一边的实例)之间找到良好的平衡。

4Scikit-Learn 的SVM类中，可以通过超参数C来控制这个平衡：C值越小，则街道越宽，但是间隔违例也会越多。

5三种分类器的比较

（1）LinearSVC(C=1,loss="hinge")

（2）SVM(kernel = "linear",C = 1),但是这个要慢得多，特别是对于大型训练集而言

（3）SGDClassifier(loss="hinge",alpha=1/(mC))，适用于常规梯度下降来训练线性SVM分类器。，不会像LinearSVC那样快速收敛，但是对于内存处理不了的大型数据集或是线性分类任务，它非常有效。

三、非线性SVM

在许多情况下，线性SVM分类器是有效的，并且通常出人意料的好，但是，有很多数据集远不是线性课分离的。处理非线性数据集的方法之一是添加更多特征，比如多项式特征，在某些情况下，这可能导致数据集变得线性可分离。

1多项式核——添加多项式

添加多项式特征实现起来非常简单，并且对所有的机器学习算法有效。但是，如果多项式太低阶，处理不了费换成那个复杂的数据集，而高阶则会创造出戴昂的特征，导致模型太慢。

使用SVM时，可以运用数学技巧——核技巧

它产生的结果就跟添加了许多多项式特征，甚至是非常高阶的多项式特征一样，但实际上并不需要真的添加。

2添加相似特征——用相似特征替代

（1）解决非线性问题的另一种技术是添加相似特征。这些特征经过相似函数计算得出，相似函数可以测量每个实例与一个特定地标之间的相似程度。

例：

在x1 =-2和x2 = 1处添加两个地标。接下来，采用高斯径向基函数（RBF）作为相似函数：

这是一个从0到1变化的钟形函数。实例x1=-1：它与第一个地标的距离为1，与第二个地标的距离为2因此它的新特征为 074, 030

（2）怎么选择地标：

最简单的方法时在数据集里面一个实例的位置上创建一个地标。缺点是：一个有m个实例n个特征的训练集会被转换成一个m个实例

3如何选择核函数

有那么多的核函数，该如何决定使用哪一个？有一个经验法则是，永远先从现行核函数开始尝试（LinearSVC 比 SVC（kernel =“linear”）快得多），特别是训练集非常大或特征非常多的时候。如果训练集不太大，你可以试试高斯RBF核， 大多数情况下它都非常好用。

4计算复杂度

（1）liblinear库为线性SVM实现了一个优化算法，LinearSVC正是基于该库的。这个算法不支持核技巧，不过它与训练实例的数量和特征数量几乎线性相关：其训练时间复杂度大致为O（m x n）

（2）SVC是基于libsvm库的，这个库的算法支持核技巧。训练时间复杂度通常在 和 之间，这意味着如果训练实例的数量变大，它会慢得可怕，所以这个算法完美适用于复杂但是中小型的训练集。但是，它还是可以良好适应地特征数量的增加，特别是应对稀疏特征。

四、SVM回归

SVM回归要做的是让尽可能多的实例位于街道上，在同时街道的同时还限制间隔违例，SVM回归要让尽可能多的实例位于街道上，同时限制间隔为例。街道的宽度由超参数 控制。

五、工作原理

线性SVM是通过简单地计算决策函数 来预测新实例x的分类。如果结果为正，则预测类别 是正类（1），否则为负类（0）

训练线性SVM分类器即意味着找到W和b的值，从而使这个间隔尽可能宽的同时，避免（硬间隔）或是限制（软间隔）间隔违例

（1）训练目标

要最小化||w||来得到尽可能大的间隔。但是，如果我们想要避免任何间隔违例（硬间隔），那么就要使所有正类训练集的决策函数大于1，负类训练集的决策函数小于-1。因此，我们可以将硬间隔线性SVM分类器的目标，看做一个约束优化问题，对所有实例：

公式：硬间隔线性SVM分类器的目标

使得

虽然 最小化和 结果相同，但是 有一个简单好用的导数。而 在W =0 时，是不可微的。优化算法在可微函数上的工作效果要好得多。

（2）软间隔

要达到软间隔的目标，需要引入一个松弛变量 ， 衡量的是第i个实例多大程度上允许间隔违例。现在有两个相互冲突的目标：使松弛变量越小越好从而减少间隔违例，同时还要使  最小化以增大间隔。这正是超参数C的用武之地：允许我们在两个目标之间权衡。

        支持向量机（support vector machine），故一般简称SVM，通俗来讲，它是一种二分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，这族分类器的特点是他们能够同时最小化经验误差与最大化几何边缘区，因此支持向量机也被称为最大边缘区分类器。其学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。SVM在很多诸如文本分类，图像分类，生物序列分析和生物数据挖掘，手写字符识别等领域有很多的应用。

        支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面，分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。

        假设给定一些分属于两类的2维点，这些点可以通过直线分割， 我们要找到一条最优的分割线，如何来界定一个超平面是不是最优的呢

        如图：

        在上面的图中，a和b都可以作为分类超平面，但最优超平面只有一个，最优分类平面使间隔最大化。 那是不是某条直线比其他的更加合适呢 我们可以凭直觉来定义一条评价直线好坏的标准:

        距离样本太近的直线不是最优的，因为这样的直线对噪声敏感度高，泛化性较差。 因此我们的目标是找到一条直线（图中的最优超平面），离所有点的距离最远。 由此， SVM算法的实质是找出一个能够将某个值最大化的超平面，这个值就是超平面离所有训练样本的最小距离。这个最小距离用SVM术语来说叫做间隔(margin) 。

        描述：给定一些数据点，它们分别属于两个不同的类，现在要找到一个线性分类器把这些数据分成两类。如果用x表示数据点，用y表示类别（y可以取1或者-1，分别代表两个不同的类），一个线性分类器的学习目标便是要在n维的数据空间中找到一个超平面（hyper plane），这个超平面的方程可以表示为（ wT中的T代表转置）：

        例如：现在有一个二维平面，平面上有两种不同的数据，分别用圈和叉表示。由于这些数据是线性可分的，所以可以用一条直线将这两类数据分开，这条直线就相当于一个超平面，超平面一边的数据点所对应的y全是-1 ，另一边所对应的y全是1。

        我们令分类函数为：

        当f(x) 等于0的时候，x便是位于超平面上的点，而f(x)大于0的点对应 y=1 的数据点，f(x)小于0的点对应y=-1的点，如下图所示：

        一个点距离超平面的远近可以表示分类预测的确信或准确程度，如何确定这个超平面呢？从直观上而言，这个超平面应该是最适合分开两类数据的直线。而判定“最适合”的标准就是这条直线离直线两边的数据的间隔最大。所以，得寻找有着最大间隔的超平面。

补充知识点： 点到平面的距离

        支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对线性可分的训练数据集而言，线性可分分离超平面有无穷多个(等价于感知机)，但是几何间隔最大的分离超平面是唯一的。这里的间隔最大化又称为硬间隔最大化。

        间隔最大化的直观解释是:对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也就是说，不仅将正负实例点分开，而且对最难分的实例点(离超平面最近的点)也有足够大的确信度将它们分开。这样的超平面应该对未知的新实例有很好的分类预测能力。

      按照我们前面的分析，对一个数据点进行分类， 当它的margin越大的时候，分类的confidence越大。 对于一个包含n个点的数据集，我们可以很自然地定义它的margin为所有这n个点的margin值中最小的那个。于是，为了使得分类的confidence高，我们希望所选择的超平面hyper plane能够最大化这个margin值。让所选择的超平面能够最大化这个“间隔”值，这个间隔就是下图中的Gap的一半：

为什么用几何间隔求最大的分离超平面而不用函数间隔？

例题：

我们构造了约束最优化问题，就是下面这个：

        此外，由于这个问题的特殊结构，还可以通过拉格朗日对偶性（Lagrange Duality）变换到对偶变量 (dual variable) 的优化问题，即通过求解与原问题等价的对偶问题（dual problem）得到原始问题的最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。

补充知识点： 拉格朗日乘子法学习

                     拉格朗日KKT条件

                     KKT条件介绍

                     拉格朗日对偶

         通过给每一个约束条件加上一个拉格朗日乘子（Lagrange multiplier）α，定义拉格朗日函数（通过拉格朗日函数将约束条件融合到目标函数里去，从而只用一个函数表达式便能清楚的表达出我们的问题）：

 求解这个式子的过程需要拉格朗日对偶性的相关知识。

例题：

         接下来谈谈线性不可分的情况，因为 线性可分这种假设实在是太有局限性 了。下图就是一个典型的线性不可分的分类图，我们没有办法用一条直线去将其分成两个区域，每个区域只包含一种颜色的点。

         要想在这种情况下的分类器，有两种方式， 一种是用曲线 去将其完全分开，曲线就是一种 非线性 的情况，跟之后将谈到的 核函数 有一定的关系：

         另外一种还是用直线，不过不用去保证可分性 ，就是包容那些分错的情况，不过我们得加入惩罚函数，使得点分错的情况越合理越好。其实在很多时候，不是在训练的时候分类函数越完美越好，因为训练函数中有些数据本来就是噪声，可能就是在人工加上分类标签的时候加错了，如果我们在训练（学习）的时候把这些错误的点学习到了，那么模型在下次碰到这些错误情况的时候就难免出错了。这种学习的时候学到了“噪声”的过程就是一个过拟合（over-fitting），这在机器学习中是一个大忌。

我们可以为分错的点加上一点惩罚，对一个分错的点的 惩罚函数 就是 这个点到其正确位置的距离：

        对于线性不可分的情况，我们可以用核函数让空间从原本的线性空间变成一个更高维的空间 ， 在这个高维的线性空间下，再用一个超平面进行划分 。 这儿举个例子，来理解一下如何利用空间的维度变得更高来帮助我们分类的：

        上图是一个线性不可分的图，当我们把这两个类似于椭圆形的点映射到一个高维空间后，映射函数为：

        用这个函数可以将上图的平面中的点映射到一个三维空间（z1,z2,z3)，并且对映射后的坐标加以旋转之后就可以得到一个线性可分的点集了。

        形象说明：例如世界上本来没有两个完全一样的物体，对于所有的两个物体，我们可以通过增加维度来让他们最终有所区别，比如说两本书，从(颜色，内容)两个维度来说，可能是一样的，我们可以加上作者这个维度，是在不行我们还可以加入页码，可以加入拥有者，可以加入购买地点，可以加入笔记内容等等。当维度增加到无限维的时候，一定可以让任意的两个物体可分了。

核函数定义：

核技巧在支持向量机中的应用：

常用核函数：

非线性支持向量机学习算法：

        支持向量机的学习问题可以形式化为求解凸二次规划问题。这样的凸二次规划问题具有全局最优解，并且有许多最优化算法可以用于这一一问题的求解。但是当训练样本容量很大时，这些算法往往变得非常低效，以致无法使用。所以，如何高效地实现支持向量机学习就成为一一个重要的问题。目前人们已提出许多快速实现算法本节讲述其中的序列最小最优化(sequential minimal optimization, SMO)算法。

        上述问题是要求解N个参数(α1,α2,α3,,αN)，其他参数均为已知，序列最小最优化算法(SMO)可以高效的求解上述SVM问题，它把原始求解N个参数二次规划问题分解成很多个子二次规划问题分别求解，每个子问题只需要求解2个参数，方法类似于坐标上升，节省时间成本和降低了内存需求。每次启发式选择两个变量进行优化，不断循环，直到达到函数最优值。

        整个SMO算法包括两部分，求解两个变量的 二次规划 问题和选择这两个变量的 启发式 方法。

 上面求得的(α1)new和(α2)new是在η>0的情况下求得的：

        当时为了推导公式我们直接默认它是大于0了，现在我们需要重新审视这一项（η）。这一项是原来关于的二次项的系数。我们可以分下面三种情况讨论：

（1）当η>0时 ：这个二次函数开口向上，所以要求这个二次函数的最小值，如果说极值点不在计算出的可行域的范围内，就要根据这个极值点和可行域边界值的关系来得到取最小值的地方：

①如果这个极值点在可行域左边，那么我们可以得到这个可行域内二次函数一定在单增，所以此时L应该是那个取最小值的地方。就如大括号的第三种情况。

②如果这个极值点在可行域右边，那么此时可行域内一定单减，所以此时H就是那个取最小值的地方，就是大括号里的第一种情况。

（2）当η=0时： 这个二次函数就变成了一个一次函数，那么不管这个一次函数的单调性怎样，最小值一定是在边界处取到。所以到时候计算可行域的两个边界的值，看哪个小就用哪个。

（3）当η<0时: 这个二次函数开口向下，那么此时怎么得到取最小值的点呢？很容易就能想到：最小值也是在可行域的边界处取到。很容易理解，此时开口向下，当极值点在区间内时，最小值只能在端点处取，因为极值点处是最大的。而当极值点在区间外时，区间内一定是单调的，此时最小值也只能在端点处取。通过计算比较边界处的目标函数值，哪个小取哪个。

通过以上判断求出(α2)new以后，再根据公式求出(α1)new，然后带入目标函数（1）中。即如下过程：

        上述分析是在从N个变量中已经选出两个变量进行优化的方法，下面分析如何高效地选择两个变量进行优化，使得目标函数下降的最快。

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

SVM与神经网络

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

这两个冤家一直不争上下，最近基于神经网络的深度学习因为AlphaGo等热门时事，促使神经网络的热度达到了空前最高。毕竟，深度学习那样的多层隐含层的结构，犹如一个黑盒子，一个学习能力极强的潘多拉盒子。有人或许就觉得这就是我们真正的神经网络，我们不知道它那数以百千计的神经元干了什么，也不理解为何如此的结构能诞生如此美好的数据

——

犹如复杂性科学般，处于高层的我们并不能知道底层的”愚群“为何能涌现。两者一比起来，SVM似乎也没有深度学习等那么令人狂热，连Hinton都开玩笑说SVM不过是浅度学习（来自深度学习的调侃）。

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

—— 我的理性驱使我这么想，一个来路不明的食物是不能让我轻易接受的。

SVM是什么

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

（边界上的点就是支持向量，这些点很关键，这也是”支持向量机“命名的由来）

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

用数学语言描述：

这就是SVM的基本型。

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

二次规划

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

简介：

在限制条件为

的条件下，找一个n 维的向量 x ，使得

为最小。

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

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

KKT

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

把所有的不等式约束、等式约束和目标函数全部写为一个式子

L(a, b, x)= f(x) + ag(x)+bh(x)

KKT条件是说最优值必须满足以下条件：

L(a, b, x)对x求导为零

h(x) = 0

ag(x) = 0

对偶问题

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

而二次规划的对偶问题也是二次规划，性质、解法和原来一样，所以请放心。（只做简要介绍

最后训练完成时，大部分的训练样本都不需要保留，最终只会保留支持向量。这一点我们从图上也能看得出来，我们要确定的超平面只和支持向量有关不是吗？

（你看，只和支持向量有关）

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

SMO

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

例如，以下是最终求得的分类函数，也就是我们SVM的目标：

SMO算法每次迭代只选出两个分量ai和aj进行调整，其它分量则保持固定不变，在得到解ai和aj之后，再用ai和aj改进其它分量。

如何高效也能通过SMO算法的思想看得出来 ——

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

核函数

我们的SVM目的其实也简单，就是找一个超平面，引用一张图即可表述这个目的：

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

告诉我你的曲线方程吧，傻了吧~

于是引入了一个新的概念：核函数。它可以将样本从原始空间映射到一个更高维的特质空间中，使得样本在这个新的高维空间中可以被线性划分为两类，即在空间内 线性划分 。这个过程可以观看 视频 感受感受，由于是youtube所以我截一下图：

这是原始数据和原始空间，明显有红蓝两类：

通过核函数，将样本数据映射到更高维的空间（在这里，是二维映射到三维）：

而后进行切割：

再将分割的超平面映射回去：

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

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

软间隔

知道了上面的知识后，你不是就觉得SVM分类就应该是这样的：

然而这也不一定是这样的，上图给出的是一种完美的情况，多么恰巧地两类分地很开，多么幸运地能有一个超平面能将两个类区分开来！要是这两个类有一部分掺在一起了，那又该怎么分啊：

有时候如果你非要很明确地分类，那么结果就会像右边的一样 ——

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

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

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

以上就是关于支持向量机全部的内容，包括:支持向量机、支持向量机（SVM）、SVM与Neural Network等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！