支持向量机的基本原理

(资料图片仅供参考)

什么是支持向量机

？

支持向量机（SVM）是一种 二分类模型 ，可以处理线性和非线性的 分类问题 。SVM 的主要思想是将样本映射到 高维空间 中，并在该空间中找到一个最优的 超平面 ，将不同类别的样本分开。它的基本模型是在特征空间中寻找 间隔最大化 的分离超平面的 线性分类器 。

超平面: 是n维欧氏空间中(n-1)维度的子空间。(绿色直线)

支持向量: 离分类超平面 (Hyperplane) 最近的样本点。(虚线上的点)

间隔最大化 :以充分大的确信度对训练样本进行分类。

硬间隔 :完全分类正确，损失值位0。

软间隔 :允许一定量的样本分类误差。

支持向量机的过程推导

SVM三类模型

１. 线性可分支持向量机／硬间隔支持向量机

２.线性支持向量机／软间隔支持向量机

３.非线性支持向量机

0１

线性可分SVM与硬间隔最大化

线性可分SVM是训练 数据线性可分 的情况下，通过 硬间隔最大化 ，学习一个线性的分类器。

间隔、对偶、核函数

间隔

给定训练样本集D={(x1,y1),(x2,y2),…,(xm，ym)}，yi∈{-1,+1},分类学习最基本的想法就是基于训练集D在样本空间中找到一个超平面，将不同类别的样本分开。

在样本空间中，划分超平面可以通过如下线性方程来描述：

其中，w为法向量，决定了超平面的方向； b为位移项，决定了超平面与原点之间的距离。显然，划分超平面可被法向量w和位移b确定，我们将其记为（w,b）样本空间任意点x到超平面（w，b）的距离可以写为

假设超平面（w，b）能将训练样本正确分类，即对于（x i ，y i ）∈D，

若yi=+1，则有

若yi=-1，则有

令

如图6.2所示，距离超平面最近的这几个训练样本点使式（6.3）的等号成立，它们被称为“支持向量”，两个异类支持向量到超平面的距离之和为（6.4），被成为 间隔 。

SVM为什么采用 间隔 最大化?

采用间隔最大化所得决策边界与两侧最近的数据点有着最大的距离，这意味着决策边界具有最强的容错性，不容易受到噪声数据的干扰。直观的理解就是，如果决策边界抖动，最不容易撞上样本点进而导致误判。

欲找到具有“最大间隔”的划分超平面，也就是要找到能够满足式（6.3）中约束的参数w和b，使得间隔最大，即

（6.5）式可以重写为：

这就是支持向量机的 基本型 。

对偶

对式（6.6）使用 拉格朗日乘子法 可以得到其“对偶问题”。

求解线性可分支持向量机的最优化问题，很多时候会将它 转化为对偶问题来求解 ，也就是应用拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解，即线性可分支持向量机的对偶算法（dual algorithm）。

为什么要将求解SVM的原始问题转换为对偶问题?

对偶问题将原始问题中的约束转为了对偶问题中的等式约束， 降低了算法计算的的复杂度。

在原始问题下，求解的复杂度与样本的维度有关，即w的维度。 在对偶问题下，只与样本数量有关，即拉格朗日算子的个数。

如果是做线性分类，且样本维度低于样本数量的话，在原问题下求解就好了;但如果是做非线性分类，那就会涉及到升维 (比如使用高斯核做核函数，其实是将样本升到无穷维)，升维后的样本维度往往会远大于样本数量，此时显然在对偶问题下求解会更好。

而且 方便核函数的引入，进而推广到非线性分类问题 。

拉格朗日函数可以写为：

经过计算得到的对偶问题为：

通过上式求出α 后，就可以求出w , b 从而得到模型：

还有一宝后文见呦

0２

线性 SVM 与软间隔最大化

线性支持向量机在训练 数据近似线性可分 的情况下，通过 软间隔最大化 ，学习一个线性的分类器。

我们前面一直假定训练样本在样本空间或特征空间中是线性可分的。但在现实任务中，线性不可分的情形才是最常见的，退一步说，即使恰好找到了某个核函数使得训练集在特征空间中线性可分也是很难断定这个貌似线性可分的结果是否是过拟合造成的。因此需要允许支持向量机犯错， 由此引出 “软间隔” 的概念。

我们在原模型上加入一个 正则项 ，正则项由 惩罚系数C 和 松弛变量 组成。其中，惩罚系数C是一个超参数，是由我们自己设置的 ，并且带上限制条件。

经过变换后，我们同样可以求解拉格朗日对偶问题，即将原问题转化为对偶问题求解。

事实上，我们引进的松弛变量ξ是一个损失函数的整体。 但这个损失函数非凸，非连续，所以我们选则用“替代损失函数”来取代。 松弛变量的替代损失函数 包括一下三类：

假如采用hinge损失，我们的原始问题目标函数会变成：

综上所述，软间隔目标函数就是一个 正则化问题。

Ω(f)为正则化项，C为正则化常数。而正则化目的就是为了 防范过拟合问题 ，这就是我们引入软间隔的初衷。

03

非线性 SVM与核函数

非线性支持向量在训练 数据线性不可分 的情况下，通过使用 核技巧 及 软间隔最大化 ，学习非线性分类器。

第三宝：“核函数”

SVM为什么要引入核函数?

如果我们要处理的分类问题更加复杂，甚至不能像上面一样近似线性可分。在这种情况下找到的超平面分错的程度太高不太可接受。

对于这样的问题，一种解决方案是将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分，然后再运用 SVM 求解，如下图所示：

当我们使用映射函数 把这两个类似于椭圆形的点映射到三维空间 后，对映射后的坐标加以旋转之后就可以得到一个线性可分的点集如下图。

引入这样的映射后，所要求解的对偶问题的求解中，无需求解真正的映射函数，而只需要知道其核函数。核函数的定理如下：

带核的SVM为什么能分类非线性问题？

核函数的本质是两个函数的內积，而这个函数在SVM中可以表示成对于输入值的高维映射。注意核并不是直接对应映射，核只不过是一个內积。

那么有哪些常用的核函数呢？我们要如何选择核函数?

如果特征维数很大，跟样本数量差不多，选用逻辑回归或者 SVM+线性核。线性核在维度高的情况下训练速度快。

如果特征维数比较小，样本数量一般，不算大也不算小，选用 SVM+高斯核;

如果特征维数比较小，而样本数量很多，由于求解最优化问题的时候，目标函数涉及两样本计算内积，使用高斯核明显计算量会大于线性核，所以手动添加一些特征使得线性可分，然后可以用 LR 或者 SVM+线性核。

04

支持向量机的优化方法

要想求解上述凸优化问题， KKT条件 是极小值点（而且是全局极小）存在的充要条件。

那么什么是KKT条件呢？

首先让我们来看一下 拉格朗日乘子法 为什么长这样？

首先想象一下f(x)的最小值，可以想象成一个碗的最底部。

现在出现了等式约束条件h(x)。

刚刚碗的最底部已经不满足现在这个约束条件了。f(x)与h(x)相切的地方，也许才是符合我们条件的最优值。

而在这个极值点

，这就是新的极值点条件。而实际上把右侧挪到左侧就变为了

，再求偏导为0，这就与之前的条件等价了。注意图中虽然是反向，但这里有可能是同向，有可能是反向，所以对λ 并没有做要求。这其实就是 拉格朗日乘子法 。

同理，如果是多个等式约束：

一样重复刚才的操作，然后求梯度就得到向量λ。

若是不等式约束，可行域就变成了一块区域。

如果是<=，则先取反成为>=。

对于不等式约束有两种情况，一种是极值点在可行域内部，一种是极值点仍然在与等值线相切的地方（而这种就和等式约束的情况是一致的）。

对于第一种情况，这个不等式约束等于没有，

依然求解

为了后面方便比较，此时可以写成

.......................(1)

对于第二种情况，与前面阐述的等式约束的情况相同

........................(2)

而在这个极小值处，可以知道， 和 的方向刚好相反。因为 指向g(x)>0的一侧，而 就指向可行域的那一侧。而这就说明 一定是大于等于0的， 表示它们方向相反。

(2)于是就可以变为

.........................(3)

将（1）和（3）结合到一起可以写为：

将前面的等式约束写到一起，则为

当有多个约束条件时，变为

这个方程组就是所谓的KKT条件。它的含义是我们原始问题的极值点一定满足这个条件（不是极值点也可能满足），是取得极值的必要条件。

总的来看，KKT条件解决的是带有约束、非线性规划最优解的问题，根据约束形式可分为等式和不等式或两种情况混合的情形，针对这三种情形，KKT条件给出了通用的公式化解决方案，满足KKT条件的点称为K-T点，K-T点同时也是非线性规划的最优解。

SMO算法

直接求出m个变量组成的α似乎很是困难，序列最小化 SMO采用了一种启发式的方法，用于快速求解SVM。

基本思路为：如果所有变量的解满足最优化问题的KKT条件，那么就得到了最优解。 SMO算法与 坐标下降法 的思想差不多，不同的是，SMO算法是一次迭代优化 两个α 而不是一个。 它选择凸二次规划的两个变量，其他的变量保持不变，然后根据这两个变量构建一个二次规划问题，这个二次规划关于这两个变量解会更加的接近原始二次规划的解，通过这样的子问题划分可以大大增加整个算法的计算速度。

坐标下降是通过循环使用不同坐标方向, 每次固定其他元素, 只沿一个坐标方向进行优化, 以达到目标函数的局部最小。SMO 每步同时选择两个变量 αi 和 αj 进行优化, 并固定其他参数, 以保证不违背约束。

支持向量机的相关问题

SVM为什么对噪声以及缺失值敏感?

当噪声出现的过多的话，或者当噪声出现并成为支持向量的时候，噪声对模型影响是巨大的;

这里的缺失值是指缺失某些特征数据，向量数据不完整。因为SVM不像决策树一样有处理缺失值的策略，所以如果存在缺失值，这些数据在该特征维度很难正确的分类，将影响到训练结果的好坏。

SVM如何处理多分类问题?

一般有两种做法:

一种是 直接法 ，直接在目标函数上修改，将多个分类面的参数求解合并到个最优化问题里面。看似简单但是计算量却非常的大。

另外一种做法是 间接法 : 对训练器进行组合。其中比较典型的有一对一和一对多。

一对多 :就是对每个类都训练出一个分类器，由于SVM是二分类，所以将此二分类器的两类设定为目标类为一类，其余类为另外一类。这样针对K个类可以训练出K个分类器，当有一个新的样本来的时候，用这K个分类器来测试，哪个分类器的概率高，那么这个样本就属于哪一类。这种方法效果不太好，偏差比较高。

一对一 :针对任意两个类训练出一个分类器，如果有K类，一共训练出C(2,k)个分类器，这样当有一个新的样本要来的时候，用这C(2,k) 个分类器来测试，每当被判定属于某一类的时候，该类就加一，最后票数最多的类别被认定为该样本的类。

不平衡样本会对SVM的结果产生影响吗?

不平衡样本会对结果产生影响，超平面会靠近样本少的类别。

原因如下:因为使用的是软间隔分类，而如果所有的类别都使用同样的惩罚系数，则由于优化目标里面最小化惩罚量，所以靠近少数样本时，其惩罚量会小一些。

解决方法如下:

对正例和负例赋予不同的C值，例如正例远少于负例，则正例的C值取得较大，这种方法的缺点是可能会偏离原始数据的概率分布;

对训练集的数据进行预处理即对数量少的样本以某种策略进行采样，增加其数量或者减少数量多的样本，典型的方法如: 随机插入法，缺点是可能出现 overfitting，较好的是SMOTE，其缺点是只能应用在具体的特征空间中，不适合处理那些无法用特征向量表示的问题，当然增加样本也意味着训练时间可能增加；

基于核函数的不平衡数据处理

SVM和逻辑回归的异同点

相同点

都为分类算法；

不考虑核函数，都为线性分类面；

都为有监督学习算法；

都为判别式模型；

都可以增加不同的正则化项，如L1、L2等。在很多实验中，两种算法的结果很接近。

不同点

LR是参数模型，SVM是非参数模型

从目标函数来看，SVM使用的是合页损失函数hinge loss；逻辑回归使用的是交叉熵损失函数

SVM样本只考虑局部边界点；而逻辑回归考虑的是全局点；

SVM在非线性问题上引入核函数；而逻辑回归不用；

SVM依赖于数据之间的距离进行分类，需要预先标准化；而逻辑回归不用；

SVM损失函数自带正则化，结构风险最小化（在训练误差和模型复杂度之间寻求平衡），可以防止过拟合，达到真实误差最小。

逻辑回归相对来说模型更简单，好理解，特别是大规模线性分类时比较方便。而SVM的理解和优化相对复杂，SVM转化为对偶问题后,分类只需要计算与少数几个支持向量的距离,这个在进行复杂核函数计算时优势很明显,能够大大简化模型和计算。

支持向量机的应用场景

低价值用户模型分析

本案例依托数据科学云平台提供的算子，对用户数据进行分析，区分出低价值用户，并通过分类算法进行模型训练，将模型应用于实际业务中，自动对用户做分类，识别出低价值用户。

模型分析的关键步骤如下：

支持向量机模型构建

支持向量机模型评估

支持向量机的优缺点

优点

使用核函数可以向高维空间进行映射

使用核函数可以解决非线性的分类

分类思想很简单，就是将样本与决策面的间隔最大化

分类效果较好

缺点

对大规模训练样本难以实施

解决多分类问题存在困难

对缺失数据敏感，对参数和核函数的选择敏感