支持向量机
2021-9-30
| 2023-8-6
0  |  阅读时长 0 分钟
type
status
date
slug
summary
tags
category
icon
password
Property

原理

支持向量机(Support Vecor Machine，SVM)虽然诞生只有短短的二十多年，但是自一诞生便由于它良好的分类性能席卷了机器学习领域，并牢牢压制了神经网络领域好多年。如果不考虑集成学习的算法，不考虑特定的训练数据集，在分类算法中的表现SVM说是排第一估计是没有什么异议的。
SVM是一个二元分类算法，线性分类和非线性分类都支持。经过演进，现在也可以支持多元分类，同时经过扩展，也能应用于回归问题。

线性支持向量机的硬间隔最大化模型

回顾感知机模型

感知机的模型就是尝试找到一条直线，能够把二元数据隔离开。放到三维空间或者更高维的空间，感知机的模型就是尝试找到一个超平面，能够把所有的二元类别隔离开。
notion image
对于这个分离的超平面，定义为。在超平面 上方的定义 ，在超平面 下方的定义 。可以看出满足这个条件的超平面并不止一个。那么这么多的可以分类的超平面，哪个是最好的呢？或者说哪个是泛化能力最强的呢?
 
接着看感知机模型的损失函数优化，它的思想是让所有误分类的点(定义为M)到超平面的距离和最小，即最小化下式：
当 和成比例的增加，比如，当分子的和扩大N倍时，分母的L2范数也会扩大N倍。也就是说，分子和分母有固定的倍数关系。那么可以固定分子或者分母为1，然后求另一个即分子自己或者分母的倒数的最小化作为损失函数，这样可以简化损失函数。感知机模型中采用的是保留分子，固定分母 ，即最终感知机模型的损失函数为：
如果不是固定分母，改为固定分子，作为分类模型有没有改进呢？
 

函数间隔与几何间隔

在分离超平面固定为的时候， 表示点到超平面的相对距离，通过观察 和是否同号来判断分类是否正确。这里引入函数间隔的概念，定义函数间隔 为：
可以看到，它就是感知机模型里面的误分类点到超平面距离的分子。对于训练集中个样本点对应的个函数间隔的最小值，就是整个训练集的函数间隔。
 
函数间隔并不能正常反应点到超平面的距离，在感知机模型里也提到，当分子成比例的增长时，分母也是成倍增长。为了统一度量，需要对法向量加上约束条件，这样就得到了几何间隔，定义为：
几何间隔才是点到超平面的真正距离，感知机模型里用到的距离就是几何距离
 

支持向量

感知机模型可以找到多个可以分类的超平面将数据分开，并且优化时希望所有的点都被准确分类。但是实际上离超平面很远的点已经被正确分类，它对超平面的位置没有影响。我们最关心是那些离超平面很近的点，这些点很容易被误分类。如果可以让离超平面比较近的点尽可能的远离超平面，最大化几何间隔，那么分类效果会更好一些。SVM的思想起源正起于此。
 
如下图所示，分离超平面为，如果所有的样本不光可以被超平面分开，还和超平面保持一定的函数距离（下图函数距离为1），那么这样的分类超平面是比感知机的分类超平面优的。可以证明，这样的超平面只有一个。和超平面平行的保持一定的函数距离的这两个超平面对应的向量定义为支持向量，如下图虚线所示。
notion image
支持向量到超平面的距离为，两个支持向量之间的距离为
 

SVM模型目标函数与优化

SVM的模型是让所有点到超平面的距离大于一定的距离，也就是所有的分类点要在各自类别的支持向量两边，用数学式子表示为：
一般取函数间隔为1，这样优化函数定义为：
也就是说，要在约束条件下，最大化。这和感知机的优化方式不同，感知机是固定分母优化分子，而SVM是固定分子优化分母，同时加上了支持向量的限制。
 
由于的最大化等同于的最小化，这样SVM的优化函数等价于：
由于目标函数是凸函数，同时约束条件不等式是仿射的，根据凸优化理论，可以通过拉格朗日函数将优化目标转化为无约束的优化函数，这和最大熵模型中的目标函数的优化方法一样。具体的，优化函数转化为：
由于引入了朗格朗日乘子，优化目标变成：
和最大熵模型一样的，这个优化函数满足KKT条件，也就是说，可以通过拉格朗日对偶将优化问题转化为等价的对偶问题来求解。
 
也就是说，现在要求的是：
从上式中，可以先求优化函数对于和的极小值。接着再求拉格朗日乘子的极大值。
首先我们来求基于和的极小值，即
这个极值可以通过对和分别求偏导数得到：
从上两式子可以看出，已经求得了和的关系，只要后面接着能够求出优化函数极大化对应的，就可以求出了，至于b，由于上两式已经没有b，所以最后的b可以有多个。
好了，既然已经求出和的关系，就可以带入优化函数消去了。定义:
现在将替换为 的表达式以后的优化函数：
其中，(1)式到(2)式用到了范数的定义 , (2)式到(3)式用到了上面的 ， (3)式到(4)式把和样本无关的 提前，(4)式到(5)式合并了同类项，(5)式到(6)式把和样本无关的提前，(6)式到(7)式继续用到，（7）式到(8)式用到了向量的转置。由于常量的转置是其本身，所有只有向量被转置，（8）式到(9)式用到了上面的 ，（9）式到(10)式使用了 的乘法运算法则，（10）式到(11)式仅仅是位置的调整。
注意： 时，并不能推导出，比如有2组,分别是(-2,3,2)和(3，2，1)
 
从上面可以看出，通过对 极小化以后，优化函数 仅仅只有向量做参数。只要能够极大化，就可以求出此时对应的 ，进而求出.
对 求极大化的数学表达式:
可以去掉负号，即为等价的极小化问题：
 
只要求出上式极小化时对应的 向量就可以求出 了。具体怎么极小化上式得到对应的，一般需要用到SMO算法。这里，假设通过SMO算法得到了对应的的值。
那么根据，可以求出对应的的值：
求 则稍微麻烦一点。注意到，对于任意支持向量 ，都有
假设有S个支持向量，则对应求出S个 ，理论上这些 都可以作为最终的结果， 但是一般采用一种更健壮的办法，即求出所有支持向量所对应的，然后将其平均值作为最后的结果。注意到对于严格线性可分的SVM， 的值是有唯一解的，也就是这里求出的所有都是一样的，这里这么写是为了和后面加入软间隔后的SVM的算法描述一致。
怎么得到支持向量呢？根据KKT条件中的对偶互补条件 ，如果 则有 即点在支持向量上，否则如果 则有 ，即样本在支持向量上或者已经被正确分类。
 

线性可分SVM的算法过程

输入是线性可分的 个样本 ，为维特征向量， 为二元输出，值为1，或者-1
输出是分离超平面的参数和和分类决策函数
 
算法过程如下：
  1. 构造约束优化问题
  1. 用SMO算法求出上式最小时对应的向量的值向量
  1. 计算
  1. 找出所有的S个支持向量
      2. 即满足 对应的样本 ，通过 ，计算出每个支持向量 对应的 ，计算出这些 。 所有的 对应的平均值即为最终的
 
最终的分类超平面为：
最终的分类决策函数为：
 
线性可分SVM的学习方法对于非线性的数据集是没有办法使用的， 有时候不能线性可分的原因是线性数据集里面多了少量的异常点，由于这些异常点导致了数据集不能线性可分， 那么怎么可以处理这些异常点使数据集依然可以用线性可分的思想呢？
 

线性支持向量机的软间隔最大化模型

线性分类SVM面临的问题

有时候本来数据的确是可分的，也就是说可以用 线性分类SVM的学习方法来求解，但是却因为混入了异常点，导致不能线性可分，比如下图，本来数据是可以按下面的实线来做超平面分离的，可以由于一个橙色和一个蓝色的异常点导致我们没法按照之前的方法来分类。
notion image
 
另外一种情况没有这么糟糕到不可分，但是会严重影响模型的泛化预测效果，比如下图，本来如果不考虑异常点，SVM的超平面应该是下图中的红色线所示，但是由于有一个蓝色的异常点，导致学习到的超平面是下图中的粗虚线所示，这样会严重影响分类模型预测效果。
notion image
如何解决这些问题呢？SVM引入了软间隔最大化的方法来解决。
 

线性分类SVM的软间隔最大化

所谓的软间隔，是相对于硬间隔说的，可以认为之前线性分类SVM的学习方法属于硬间隔最大化
硬间隔最大化的条件：
 
如何可以软间隔最大化呢？
SVM对训练集里面的每个样本 引入了一个松弛变量 ，使函数间隔加上松弛变量大于等于1，也就是说：
对比硬间隔最大化，可以看到对样本到超平面的函数距离的要求放松了，之前是一定要大于等于1，现在只需要加上一个大于等于0的松弛变量能大于等于1就可以了。当然，松弛变量不能白加，这是有成本的，每一个松弛变量 对应了一个代价，这个就得到了软间隔最大化的SVM学习条件如下：
 
是由于松弛变量的引入导致的损失，为惩罚参数，可以理解为一般回归和分类问题正则化时候的参数。 越大对误分类的惩罚越大， 无穷大的时候其实就变成了硬间隔支持向量机了， 越小对误分类的惩罚越小。也就是说，希望尽量小，误分类的点尽可能的少。 是协调两者关系的正则化惩罚系数。在实际应用中，需要调参来选择。
加入松弛变量， 值不唯一
 

线性分类SVM的软间隔最大化目标函数的优化

将软间隔最大化的约束问题用拉格朗日函数转化为无约束问题如下：
其中 均为拉格朗日系数
 
也就是说现在要优化的目标函数是：
这个优化目标也满足KKT条件，可以通过拉格朗日对偶将优化问题转化为等价的对偶问题来求解如下：
可以先求优化函数对于 的极小值, 接着再求拉格朗日乘子 和 的极大值。
 
首先来求优化函数对于 的极小值，这个可以通过求偏导数求得：
利用上面的三个式子去消除和了：
其中，(1)式到(2)式用到了 ，(2)式到(3)式合并了同类项，(3)式到(4)式用到了范数的定义 ，(4)式到(5)式用到了上面的 ， (5)式到(6)式把和样本无关的提前，(6)式到(7)式合并了同类项，(7)式到(8)式把和样本无关的提前，(8)式到(9)式继续用到 ，（9）式到(10)式用到了向量的转置。由于常量的转置是其本身，所有只有向量被转置，（10）式到(11)式用到了上面的 ，（11）式到(12)式使用了 的乘法运算法则，（12）式到(13)式仅仅是位置的调整
 
这个式子线性可分SVM的一样，唯一不一样的是约束条件，优化目标的数学形式：
对于 这3个式子，可以消去，只留下，也就是说 。 同时将优化目标函数变号，求极小值，如下：
这就是软间隔最大化时的线性可分SVM的优化目标形式，和硬间隔最大化的线性可分SVM相比，仅仅是多了一个约束条件 。依然可以通过SMO算法来求上式极小化时对应的向量就可以求出和了。

软间隔最大化时的支持向量

在硬间隔最大化时，支持向量比较简单，就是满足 就可以了。根据KKT条件中的对偶互补条件 ，如果 则有 即点在支持向量上，否则如果 则有 ，即样本在支持向量上或者已经被正确分类。
在软间隔最大化时，则稍微复杂一些，因为对每个样本 引入了松弛变量 。从下图来研究软间隔最大化时支持向量的情况，第 个点到对应类别支持向量的距离为 。根据软间隔最大化时KKT条件中的对偶互补条件
notion image
我们有：
a) 如果 ,那么 ，即样本在间隔边界上或者已经被正确分类，图中所有远离间隔边界的点
b) 如果 ，那么 ，即点在间隔边界上
c) 如果 ，说明这是一个可能比较异常的点，需要检查此时
  • 如果 ，那么点被正确分类，但是却在超平面和自己类别的间隔边界之间，如图中的样本2和4
  • 如果 ，那么点在分离超平面上，无法被正确分类
  • 如果 ，那么点在超平面的另一侧，也就是说，这个点不能被正常分类，如图中的样本1和3
 
补充：
首先要明确软间隔最大化的优化目标函数中，KKT的三个条件:
条件一：
条件二：
条件三：
  • 当时，KKT条件一显然成立，根据条件三得 ，而为了使KKT条件二要成立，则松弛变量，三个条件都成立，说明样本点正确分类，正确分类就说明 ，也就是说样本点要么在间隔边界上，要么在远离间隔边界的地方；
  • 当时，由条件三可知，而条件二要成立，则，此时为了满足条件一可知 必须成立，则 必须成立，说明样本点必在间隔边界上;
  • 当 ，由条件三知， ，进而得出条件二恒成立， 的取值不固定，但是它的基本约束条件为 ，于是分情况讨论：
    • 如果 ，为了使条件一成立则 ，说明样本点在间隔边界和分类超平面之间
    • 如果 ，为了使条件一成立则 ，说明样本点在分类超平面上
    • 如果 ，为了使条件一成立则 ，说明样本点在分类超平面的另一侧，为误分类点
 

软间隔最大化的线性可分SVM的算法过程

输入是线性可分的 个样本 ，其中为维特征向量。 为二元输出，值为1，或者-1.
输出是分离超平面的参数 和分类决策函数
算法过程如下：
  1. 选择一个惩罚系数 ，构造约束优化问题
  1. 用SMO算法求出上式最小时对应的 向量的值 向量
  1. 计算
  1. 找出所有的S个支持向量对应的样本
      2. 通过 ，计算出每个支持向量 对应的 ，计算出这些 ，所有的 对应的平均值即为最终的 。
      由于引入了软间隔，所以此时并不是所有的支持向量都满足，一般来说，此时支持向量满足的是，而不同的支持向量其 不同，所以对应的b需要平均
 
最终的分类超平面为：
最终的分类决策函数为：
 

合页损失函数

线性支持向量机还有另外一种解释如下：
其中 称为合页损失函数(hinge loss function)，下标+表示为：
也就是说，如果点被正确分类，且函数间隔大于1，损失是0，否则损失是 ，如下图中的绿线。在下图还可以看出其他各种模型损失和函数间隔的关系：对于0-1损失函数，如果正确分类，损失是0，误分类损失1， 如下图黑线，可见0-1损失函数是不可导的。对于感知机模型，感知机的损失函数是 ，这样当样本被正确分类时，损失是0，误分类时，损失是 ，如下图紫线。对于逻辑回归之类和最大熵模型对应的对数损失，损失函数是 ，如下图红线所示。
notion image
线性可分SVM通过软间隔最大化，可以解决线性数据集带有异常点时的分类处理，但是现实生活中的确有很多数据不是线性可分的，这些线性不可分的数据也不是去掉异常点就能处理这么简单。

线性不可分支持向量机与核函数

线性可分SVM的硬间隔最大化和软间隔最大化的算法对线性可分的数据有很好的处理，但是对完全线性不可分的数据没有办法。这里就来探讨SVM如何处理线性不可分的数据，重点讲述核函数在SVM中处理线性不可分数据的作用。

回顾多项式回归

在线性回归中提到了如何将多项式回归转化为线性回归
比如一个只有两个特征的次方多项式回归的模型：
令 ，这样就得到了下式：
又重新回到了线性回归，这是一个五元线性回归，可以用线性回归的方法来完成算法。对于每个二元样本特征 ，得到一个五元样本特征 ，通过这个改进的五元样本特征把不是线性回归的函数变回线性回归。
也就是说，对于二维的不是线性的数据，将其映射到了五维以后，就变成了线性的数据。
这给了我们启发，也就是说对于在低维线性不可分的数据，在映射到了高维以后，就变成线性可分的了。这个思想同样可以运用到SVM的线性不可分数据上。也就是说，对于SVM线性不可分的低维特征数据，可以将其映射到高维，就能线性可分，此时就可以运用线性可分SVM的算法思想了。
 

核函数的引入

回顾线性可分SVM的优化目标函数：
注意到上式低维特征仅仅以内积的形式出现，如果定义一个低维特征空间到高维特征空间的映射 （比如2维到5维的映射），将所有特征映射到一个更高的维度，让数据线性可分，就可以继续按之前的方法来优化目标函数，求出分离超平面和分类决策函数了。也就是说现在的SVM的优化目标函数变成：
可以看到，和线性可分SVM的优化目标函数的区别仅仅是将内积替换为。
看起来似乎这样就已经完美解决了线性不可分SVM的问题了，但是事实是不是这样呢？假如是一个2维特征的数据，可以将其映射到5维来做特征的内积，如果原始空间是三维，可以映射到到19维空间，似乎还可以处理。但是如果低维特征是100个维度，1000个维度呢？那么要将其映射到超级高的维度来计算特征的内积。这时候映射成的高维维度是爆炸性增长的，这个计算量实在是太大了，而且如果遇到无穷维的情况，就根本无从计算了。
怎么办？核函数该隆重出场了！
假设是一个从低维的输入空间（欧式空间的子集或者离散集合）到高维的希尔伯特空间的映射。那么如果存在函数，对于任意 ，都有：
那么就称为核函数。
仔细观察上式可以发现， 的计算是在低维特征空间来计算的，它避免了在刚才提到了在高维维度空间计算内积的恐怖计算量。也就是说，我们可以好好享受在高维特征空间线性可分的红利，却避免了高维特征空间恐怖的内积计算量。
 
至此，总结下线性不可分时核函数的引入过程：
遇到线性不可分的样例时，常用做法是把样例特征映射到高维空间中去(如多项式回归）但是遇到线性不可分的样例，一律映射到高维空间，那么这个维度大小是会高到令人恐怖的。此时，核函数就体现出它的价值了，核函数的价值在于它虽然也是将特征进行从低维到高维的转换，但核函数好在它在低维上进行计算，而将实质上的分类效果（利用了内积）表现在了高维上，这样避免了直接在高维空间中的复杂计算，真正解决了SVM线性不可分的问题。
 
为什么高维或者无穷维一定线性可分？
严格说升维到高维或者无穷维不一定线性可分，但是一般来说，升维到高维后线性可分的概率大大增加。如果这个核函数不好，还可以用其他的和函数试一试，总有合适的核函数让升维后的数据变得“更加可能”线性可分
没有内积不能用核函数，所以一般要求都是希尔伯特空间
 

核函数

事实上，核函数的研究非常的早，要比SVM出现早得多，当然，将它引入SVM中是最近二十多年的事情。对于从低维到高维的映射，核函数不止一个。那么什么样的函数才可以当做核函数呢？这是一个有些复杂的数学问题，这里不多介绍。
由于一般说的核函数都是正定核函数，这里直说明正定核函数的充分必要条件。一个函数要想成为正定核函数，必须满足他里面任何点的集合形成的Gram矩阵是半正定的。也就是说,对于任意的 对应的Gram矩阵 是半正定矩阵，则 是正定核函数。
从上面的定理看，它要求任意的集合都满足Gram矩阵半正定，所以自己去找一个核函数还是很难的，怎么办呢？还好牛人们已经帮我们找到了很多的核函数，而常用的核函数也仅仅只有那么几个。

线性核函数

线性核函数（Linear Kernel）其实就是线性可分SVM，表达式为：
线性可分SVM可以和线性不可分SVM归为一类，区别仅仅在于线性可分SVM用的是线性核函数。

多项式核函数

多项式核函数（Polynomial Kernel）是线性不可分SVM常用的核函数之一，表达式为：
其中， 都需要自己调参定义。

高斯核函数

高斯核函数（Gaussian Kernel），在SVM中也称为径向基核函数（Radial Basis Function,RBF），它是非线性分类SVM最主流的核函数，libsvm默认的核函数就是它。表达式为：
其中， 大于0，需要自己调参定义。

Sigmoid核函数

Sigmoid核函数（Sigmoid Kernel）也是线性不可分SVM常用的核函数之一，表达式为：
其中， 都需要自己调参定义。
 

分类SVM的算法小结

引入了核函数后，SVM算法才算是比较完整了。现在对分类SVM的算法过程做一个总结，不再区别是否线性可分。
输入是 个样本 ，其中 为n维特征向量。y为二元输出，值为1，或者-1
输出是分离超平面的参数和分类决策函数
 
算法过程如下：
  1. 选择适当的核函数 和一个惩罚系数 ， 构造约束优化问题
  1. 用SMO算法求出上式最小时对应的向量的值向量
  1. 得到 ，此处可以不直接显式的计算 ：
      2. 因为我们的算法的目的是得到分类超平面，即
      而由于
      这样分类超平面可以表示为：
      而最后一个式子从核函数可以算出，顾不需要先显式计算
  1. 找出所有的S个支持向量
      2. 即满足 对应的样本 ，通过 ，计算出每个支持向量 对应的 ，计算出这些 。所有的对应的平均值即为最终的
 
最终的分类超平面为：
最终的分类决策函数为：

SMO算法

SVM优化目标函数

回顾下优化目标函数：
解要满足的KKT条件的对偶互补条件为：
根据这个KKT条件的对偶互补条件有：
由于，令 ，则有：
 

SMO算法的基本思想

上面这个优化式子比较复杂，里面有 个变量组成的向量需要在目标函数极小化的时候求出。直接优化时很难的。SMO算法则采用了一种启发式的方法。它每次只优化两个变量，将其它变量都视为常数。由于 ，假如将 固定，那么之间的关系也确定了，这样SMO算法将一个复杂的优化算法转化为一个比较简单的两变量优化问题。
为了后面表示方便定义
由于 都成了常量，所有的常量都从目标函数去除，这样目标优化函数变成下式：
 

SMO算法目标函数的优化

为了求解上面含有这两个变量的目标优化问题，首先分析约束条件，所有的 都要满足约束条件，然后在约束条件下求最小。
根据上面的约束条件 ，又由于 均只能取值1或者-1, 这样 在[0,C]和[0,C]形成的盒子里面，并且两者的关系直线的斜率只能为1或者-1，也就是说 的关系直线平行于[0,C]和[0,C]形成的盒子的对角线，如下图所示：
notion image
 
由于 的关系被限制在盒子里的一条线段上，所以两变量的优化问题实际上仅仅是一个变量的优化问题。不妨假设最终是 的优化问题。由于采用的是启发式的迭代法，假设上一轮迭代得到的解是 ，假设沿着约束方向 未经剪辑的解是 。本轮迭代完成后的解为
由于 必须满足上图中的线段约束。假设L和H分别是上图中 所在的线段的边界，有：
而对于L和H，也有限制条件如果是上面左图中的情况，则
如果是上面右图中的情况，有：
也就是说，假如通过求导得到的 ，则最终的 应该为：
那么如何求出 呢？很简单，只需要将目标函数对 求偏导数即可。
 
整理下目标函数
为了简化叙述，令 ，
其中
令
这样优化目标函数进一步简化为：
由于 ，并且 ，可以得到 用 表达的式子为：
将上式带入目标优化函数，就可以消除 ,得到仅仅包含 的式子。
 
现在开始通过求偏导数来得到
整理上式有：
将 带入上式，有：
得到了 的表达式：
利用上面讲到的 和 的关系式，就可以得到我们新的 了。利用 和 的线性关系，也可以得到新的 。
 

SMO算法两个变量的选择

SMO算法需要选择合适的两个变量做迭代，其余的变量做常量来进行优化，那么怎么选择这两个变量呢？

第一个变量的选择

SMO算法称选择第一个变量为外层循环，这个变量需要选择在训练集中违反KKT条件最严重的样本点。对于每个样本点，要满足的KKT条件：
一般来说，首先选择违反 这个条件的点。如果这些支持向量都满足KKT条件，再选择违反 和 的点。

第二个变量的选择

SMO算法称选择第二个变量为内层循环，假设在外层循环已经找到了 , 第二个变量 的选择标准是让 有足够大的变化。由于 定了的时候， 也确定了，所以要想 最大，只需要在 为正时，选择最小的 作为 ， 在 为负时，选择最大的 作为 ，可以将所有的 保存下来加快迭代。
如果内存循环找到的点不能让目标函数有足够的下降， 可以采用遍历支持向量点来做 ，直到目标函数有足够的下降， 如果所有的支持向量做 都不能让目标函数有足够的下降，可以跳出循环，重新选择

计算阈值b和差值

在每次完成两个变量的优化之后，需要重新计算阈值b。当 时，有
于是新的 为：
计算出为：
可以看到上两式都有 ，因此可以将 用 表示为：
同样的，如果 , 那么有：
最终的 为：
得到了 我们需要更新 ：
其中，S是所有支持向量 的集合。
 

SMO算法总结

输入是 个样本 ，为 维特征向量。 为二元输出，值为1或-1，精度e（e其实就是每轮迭代更新的变化阈值，如果某一轮迭代更新的变化小于e，说明已经差不多找到了局部最优解了，可以停止迭代了）
输出是近似解
  1. 取初值
  1. 按照前面方法选择 ，接着前面的方法选择 ，求出新的
  1. 按照下式求出
  1. 利用 和 的关系求出
  1. 按照前面的方法计算 和
  1. 在精度e范围内检查是否满足如下的终止条件：
  1. 如果满足则结束，返回 ,否则转到步骤2

线性支持回归

SVM回归模型的损失函数度量

回顾下前面SVM分类模型中，目标函数是让 最小，同时让各个训练集中的点尽量远离自己类别一边的的支持向量，即 。如果是加入一个松弛变量 ，则目标函数是 ，对应的约束条件变成：
但是现在是回归模型，优化目标函数可以继续和SVM分类模型保持一致为 ，但是约束条件呢？不可能是让各个训练集中的点尽量远离自己类别一边的的支持向量，因为是回归模型，没有类别。对于回归模型，目标是让训练集中的每个点 ，尽量拟合到一个线性模型 。对于一般的回归模型，我用均方差作为损失函数，但是SVM不是这样定义损失函数的。
SVM需要我们定义一个常量 ，对于某一个点 ，如果 ，则完全没有损失，如果 ，则对应的损失为 ，这个均方差损失函数不同，如果是均方差，那么只要 ，那么就会有损失。
如下图，在蓝色条带里面的点都是没有损失的，外面的点的是有损失的，损失大小为红色线的长度。
notion image
 
SVM回归模型的损失函数度量为：
 

SVM回归模型的目标函数的原始形式

定义目标函数如下：
和SVM分类模型相似，回归模型也可以对每个样本 加入松弛变量 ，但是由于这里用的是绝对值，实际上是两个不等式，也就是说两边都需要松弛变量，定义为 ，则SVM回归模型的损失函数度量在加入松弛变量之后变为：
依然和SVM分类模型相似，可以用拉格朗日函数将目标优化函数变成无约束的形式，也就是拉格朗日函数的原始形式如下：
其中 均为拉格朗日系数。
 

SVM回归模型的目标函数的对偶形式

目标是
和SVM分类模型一样，这个优化目标也满足KKT条件，可以通过拉格朗日对偶将优化问题转化为等价的对偶问题来求解如下：
可以先求优化函数对于 的极小值，接着再求拉格朗日乘子 的极大值。
首先求优化函数对于 的极小值，这个可以通过求偏导数求得：
把上面4个式子带入 去消去 ，最终得到的对偶形式为：
对目标函数取负号，求最小值可以得到和SVM分类模型类似的求极小值的目标函数如下：
对于这个目标函数，依然可以用SMO算法来求出对应的 ，进而求出回归模型系数 。
 

SVM回归模型系数的稀疏性

在SVM分类模型中，KKT条件的对偶互补条件为： ，而在回归模型中，对偶互补条件类似如下：
根据松弛变量定义条件，如果 ，有 ，此时 这样要满足对偶互补条件，只有 。
 
定义样本系数系数
根据上面 的计算式 ，发现此时 ，也就是说 不受这些在误差范围内的点的影响。对于在边界上或者在边界外的点， ，此时 。
 
 
 
 
SVM算法的主要优点有：
  • 解决高维特征的分类问题和回归问题很有效，在特征维度大于样本数时依然有很好的效果
  • 仅仅使用一部分支持向量来做超平面的决策，无需依赖全部数据
  • 有大量的核函数可以使用，从而可以很灵活的来解决各种非线性的分类回归问题
  • 样本量不是海量数据的时候，分类准确率高，泛化能力强
SVM算法的主要缺点有：
  • 如果特征维度远远大于样本数，则SVM表现一般
  • SVM在样本量非常大，核函数映射维度非常高时，计算量过大，不太适合使用
  • 非线性问题的核函数的选择没有通用标准，难以选择一个合适的核函数
  • SVM对缺失数据敏感
 
 
 
 
 
 

代码

从零实现

 

scikit-learn实现

scikit-learn中SVM的算法库分为两类，一类是分类的算法库，包括SVC， NuSVC和LinearSVC 3个类。另一类是回归算法库，包括SVR， NuSVR和LinearSVR 3个类。相关的类都包在sklearn.svm模块之中
对于SVC， NuSVC，和LinearSVC 3个分类的类，SVC和 NuSVC差不多，区别仅仅在于对损失的度量方式不同，而LinearSVC从名字就可以看出，他是线性分类，也就是不支持各种低维到高维的核函数，仅仅支持线性核函数，对线性不可分的数据不能使用；同样的，对于SVR， NuSVR，和LinearSVR 3个回归的类， SVR和NuSVR差不多，区别也仅仅在于对损失的度量方式不同，LinearSVR是线性回归，只能使用线性核函数。
使用这些类的时候，如果有经验知道数据是线性可以拟合的，那么使用LinearSVC去分类 或者LinearSVR去回归，它们不需要我们去慢慢的调参去选择各种核函数以及对应参数， 速度也快。如果对数据分布没有什么经验，一般使用SVC去分类或者SVR去回归，这就需要我们选择核函数以及对核函数调参了。什么特殊场景需要使用NuSVC分类 和 NuSVR 回归呢？如果我们对训练集训练的错误率或者说支持向量的百分比有要求的时候，可以选择NuSVC分类 和 NuSVR ，它们有一个参数来控制这个百分比。

SVM分类算法库的重要参数：

SVC， NuSVC和LinearSVC 3个类
惩罚系数C
SVC， LinearSVC ：默认为1，一般需要通过交叉验证来选择一个合适的C。一般来说，如果噪音点较多时，C需要小一些。
NuSVC没有这个参数，它通过另一个参数nu来控制训练集训练的错误率，等价于选择了一个C，让训练集训练后满足一个确定的错误率
nu
LinearSVC 和SVC没有这个参数，它们使用惩罚系数C来控制惩罚力度
NuSVC ：nu代表训练集训练的错误率的上限，或者说支持向量的百分比下限，取值范围为(0,1]，默认是0.5，它和惩罚系数C类似，都可以控制惩罚的力度
核函数 kernel
LinearSVC没有这个参数，LinearSVC限制了只能使用线性核函数
SVC， NuSVC ：
‘linear’即线性核函数，‘poly’即多项式核函数， ‘rbf’即高斯核函数， ‘sigmoid’即sigmoid核函数，默认是高斯核'rbf'，当然也可以自定义核函数
如果选择了这些核函数， 对应的核函数参数在后面有单独的参数需要调：
  • 线性核函数（Linear Kernel）表达式为： ，就是普通的内积，LinearSVC 和 LinearSVR 只能使用它
  • 多项式核函数（Polynomial Kernel）是线性不可分SVM常用的核函数之一：
      • ，其中 都需要自己调参定义
  • 高斯核函数（Gaussian Kernel），在SVM中也称为径向基核函数（Radial Basis Function,RBF），它是libsvm默认的核函数，当然也是scikit-learn默认的核函数。表
      • 其中，大于0，需要自己调参定义。
      一般情况下，对非线性数据使用默认的高斯核函数会有比较好的效果
  • Sigmoid核函数（Sigmoid Kernel）也是线性不可分SVM常用的核函数之一：
      • 其中 都需要自己调参定义
还有一种选择为"precomputed"，即预先计算出所有的训练集和测试集的样本对应的Gram矩阵，这样直接在对应的Gram矩阵中找对应的位置的值。
 
正则化参数penalty
LinearSVC ：仅仅对线性拟合有意义，可以选择‘l1’即L1正则化 或者 ‘l2’即L2正则化。默认是L2正则化，如果需要产生稀疏话的系数的时候，可以选L1正则化,这和线性回归里面的Lasso回归类似
SVC和NuSVC没有这个参数
是否用对偶形式优化dual
LinearSVC ：这是一个布尔变量，控制是否使用对偶形式来优化算法，默认是True，即采用分类算法对偶形式来优化算法。如果样本量比特征数多，此时采用对偶形式计算量较大，推荐dual设置为False，即采用原始形式优化
SVC和NuSVC没有这个参数
核函数参数degree
LinearSVC没有这个参数
SVC， NuSVC ：
如果在kernel参数使用了多项式核函数 'poly'，那么就需要对这个参数进行调参。这个参数对应 中的 默认是3。一般需要通过交叉验证选择一组合适的
核函数参数gamma
LinearSVC没有这个参数
SVC， NuSVC ：
如果在kernel参数使用了多项式核函数 'poly'，高斯核函数‘rbf’, 或者sigmoid核函数，那么就需要对这个参数进行调参，对应
默认为'auto'，即
核函数参数coef0
LinearSVC没有这个参数
SVC， NuSVC ：如果在kernel参数使用了多项式核函数 'poly'，或者sigmoid核函数，那么就需要对这个参数进行调参，对应
样本权重class_weight
指定样本各类别的的权重，主要是为了防止训练集某些类别的样本过多，导致训练的决策过于偏向这些类别。这里可以自己指定各个样本的权重，或者用“balanced”，如果使用“balanced”，则算法会自己计算权重，样本量少的类别所对应的样本权重会高。当然，如果样本类别分布没有明显的偏倚，则可以不管这个参数，选择默认的"None”
分类决策decision_function_shape
LinearSVC没有这个参数，使用multi_class参数替代
SVC， NuSVC ：
可以选择'ovo'或者‘ovo’
分类决策multi_class
LinearSVC ：可以选择 ‘ovr’ 或者 ‘crammer_singer’
‘ovr’和SVC和nuSVC中的decision_function_shape对应的‘ovr’类似。
'crammer_singer'是一种改良版的'ovr'，说是改良，但是没有比’ovr‘好，一般在应用中都不建议使用
SVC和nuSVC没有这个参数，使用decision_function_shape参数替代
缓存大小cache_size
LinearSVC计算量不大，因此不需要这个参数
SVC， NuSVC ：在大样本的时候，缓存大小会影响训练速度，因此如果机器内存大，推荐用500MB甚至1000MB。默认是200，即200MB.
 
 
 

SVM回归算法库的重要参数：

SVR， NuSVR和LinearSVR 3个类
惩罚系数C
即为SVM分类模型原型形式和对偶形式中的惩罚系数C，默认为1，一般需要通过交叉验证来选择一个合适的C。一般来说，如果噪音点较多时，C需要小一些。在分类模型里面，nuSVC使用了nu这个等价的参数控制错误率，就没有使用C，为什么nuSVR仍然有这个参数呢，不是重复了吗？这里的原因在回归模型里面，除了惩罚系数C还有还有一个距离误差ϵ来控制损失度量，因此仅仅一个nu不能等同于C，也就是说回归错误率是惩罚系数C和距离误差 共同作用的结果。
nu
LinearSVR 和SVR没有这个参数，它们使用 来控制错误率
nuSVR：nu代表训练集训练的错误率的上限，或者说支持向量的百分比下限，取值范围为(0,1]，默认是0.5，通过选择不同的错误率可以得到不同的距离误差，也就是说这里的nu的使用和LinearSVR 和SVR的 参数等价
距离误差epsilon
LinearSVR 和SVR ：训练集中的样本需满足
nuSVR没有这个参数，用nu控制错误率
核函数 kernel
LinearSVR没有这个参数，LinearSVR限制了只能使用线性核函数
SVR， nuSVR ：
‘linear’即线性核函数, ‘poly’即多项式核函数, ‘rbf’即高斯核函数, ‘sigmoid’即sigmoid核函数，默认是高斯核'rbf'，当然也可以自定义核函数
如果选择了这些核函数， 对应的核函数参数在后面有单独的参数需要调：
  • 线性核函数（Linear Kernel）表达式为： ，就是普通的内积，LinearSVC 和 LinearSVR 只能使用它
  • 多项式核函数（Polynomial Kernel）是线性不可分SVM常用的核函数之一，表达式为： ，其中 都需要自己调参定义,比较麻烦
  • 高斯核函数（Gaussian Kernel），在SVM中也称为径向基核函数（Radial Basis Function,RBF），它是libsvm默认的核函数，当然也是scikit-learn默认的核函数。表达式为： 其中，大于0，需要自己调参定义。一般情况下，对非线性数据使用默认的高斯核函数会有比较好的效果
  • Sigmoid核函数（Sigmoid Kernel）也是线性不可分SVM常用的核函数之一，表达式为： ， 其中 都需要自己调参定义
还有一种选择为"precomputed"，即我们预先计算出所有的训练集和测试集的样本对应的Gram矩阵，这样直接在对应的Gram矩阵中找对应的位置的值。
 
正则化参数penalty
LinearSVR：仅仅对线性拟合有意义，可以选择‘l1’即L1正则化 或者 ‘l2’即L2正则化。默认是L2正则化，如果我们需要产生稀疏话的系数的时候，可以选L1正则化,这和线性回归里面的Lasso回归类似
SVR和nuSVR没有这个参数
是否用对偶形式优化dual
LinearSVR ：这是一个布尔变量，控制是否使用对偶形式来优化算法，默认是True，即采用分类算法对偶形式来优化算法。如果样本量比特征数多，此时采用对偶形式计算量较大，推荐dual设置为False，即采用原始形式优化
SVR和nuSVR没有这个参数
核函数参数degree
LinearSVR没有这个参数
SVR和nuSVR ：
如果在kernel参数使用了多项式核函数 'poly'，那么就需要对这个参数进行调参。这个参数对应 中的 默认是3。一般需要通过交叉验证选择一组合适的
核函数参数gamma
LinearSVR 没有这个参数
SVR和nuSVR ：
如果在kernel参数使用了多项式核函数 'poly'，高斯核函数‘rbf’, 或者sigmoid核函数，那么就需要对这个参数进行调参，对应
默认为'auto'，即
核函数参数coef0
LinearSVR 没有这个参数
SVR和nuSVR ：如果在kernel参数使用了多项式核函数 'poly'，或者sigmoid核函数，那么就需要对这个参数进行调参，对应
损失函数度量loss
LinearSVR ：
可以选择为‘epsilon_insensitive’ 和 ‘squared_epsilon_insensitive’
如果选择‘epsilon_insensitive’ ，则损失度量满足，是默认的SVM回归的损失度量标准形式。
如果选择为 ‘squared_epsilon_insensitive’ , 则损失度量满足，此时可见会少一个松弛系数。其优化过程我们在SVM原理系列里没有讲，但是目标函数优化过程是完全相似的。
一般用默认的‘epsilon_insensitive’就足够了
 
SVR和NuSVR没有这个参数
缓存大小cache_size
LinearSVR计算量不大，因此不需要这个参数
SVR和nuSVR ：在大样本的时候，缓存大小会影响训练速度，因此如果机器内存大，推荐用500MB甚至1000MB。默认是200，即200MB
 
 

其他的调参要点：

  • 一般推荐在做训练之前对数据进行归一化，当然测试集中的数据也需要归一化
  • 在特征数非常多的情况下，或者样本数远小于特征数的时候，使用线性核，效果已经很好，并且只需要选择惩罚系数C即可
  • 在选择核函数时，如果线性拟合不好，一般推荐使用默认的高斯核'rbf'，这时主要需要对惩罚系数C和核函数参数进行艰苦的调参，通过多轮的交叉验证选择合适的惩罚系数C和核函数参数
  • 理论上高斯核不会比线性核差，但是这个理论却建立在要花费更多的时间来调参上，所以实际上能用线性核解决问题尽量使用线性核
 
 
 
 
 
 
多分类案例
notion image
 
 
notion image
相关文章 :
数据分析
  • Scikit-Learn
    • 感知机K近邻法(KNN)
    目录