SVM All You Need to Know

本文主要介绍SVM 相关内容，包括理论原理、在线性可分条件下的公式推导和 SVM的应用特点。最后综合 LR 和 Decision Tree的这篇博客，给出了一些小的建议。

SVM 理论

支持向量机分为三个部分，线性可分支持向量机、线性支持向量机、非线性支持向量机。

SVM 原理

SVM 是一种二类分类模型。它的基本模型是在特征空间中寻找间隔最大化的分离超平面的线性分类器。

当训练样本线性可分时，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机；当训练数据近似线性可分时，引入松弛变量，通过软间隔最大化，学习一个线性分类器，即线性支持向量机；当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。以上各种情况下的数学推到应当掌握，硬间隔最大化（几何间隔）、学习的对偶问题、软间隔最大化（引入松弛变量）、非线性支持向量机（核技巧）。

SVM 为什么采用间隔最大化

当训练数据线性可分时，存在无穷个分离超平面可以将两类数据正确分开。感知机利用误分类最小策略，求得分离超平面，不过此时的解有无穷多个。线性可分支持向量机利用间隔最大化求得最优分离超平面，这时，解是唯一的。另一方面，此时的分隔超平面所产生的分类结果是最鲁棒的，对未知实例的泛化能力最强。可以借此机会阐述一下几何间隔以及函数间隔的关系。

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

一是对偶问题往往更易求解，当我们寻找约束存在时的最优点的时候，约束的存在虽然减小了需要搜寻的范围，但是却使问题变得更加复杂。为了使问题变得易于处理，我们的方法是把目标函数和约束全部融入一个新的函数，即拉格朗日函数，再通过这个函数来寻找最优点。二是可以自然引入核函数，进而推广到非线性分类问题。

为什么 SVM 要引入核函数

当样本在原始空间线性不可分时，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。而引入这样的映射后，所要求解的对偶问题的求解中，无需求解真正的映射函数，而只需要知道其核函数。核函数的定义：K(x,y)=<ϕ(x),ϕ(y)>，即在特征空间的内积等于它们在原始样本空间中通过核函数 K 计算的结果。一方面数据变成了高维空间中线性可分的数据，另一方面不需要求解具体的映射函数，只需要给定具体的核函数即可，这样使得求解的难度大大降低。

为什么SVM对缺失数据敏感

这里说的缺失数据是指缺失某些特征数据，向量数据不完整。SVM 没有处理缺失值的策略。而 SVM 希望样本在特征空间中线性可分，所以特征空间的好坏对SVM的性能很重要。缺失特征数据将影响训练结果的好坏。

SVM 核函数之间的区别

一般选择线性核和高斯核，也就是线性核与 RBF 核。线性核：主要用于线性可分的情形，参数少，速度快，对于一般数据，分类效果已经很理想了。 RBF 核：主要用于线性不可分的情形，参数多，分类结果非常依赖于参数。有很多人是通过训练数据的交叉验证来寻找合适的参数，不过这个过程比较耗时。如果 Feature 的数量很大，跟样本数量差不多，这时候选用线性核的 SVM。如果 Feature 的数量比较小，样本数量一般，不算大也不算小，选用高斯核的 SVM。

以上是几个问题在面试中遇到 SVM 算法时，几乎是必问的问题，另外，大家一定要做到自己可以推导集合间隔、函数间隔以及对偶函数，并且理解对偶函数的引入对计算带来的优势。

支持向量

如图所示，上面只有三个点与求解的优化问题有关，它们就叫做支持向量。

SVM公式推导(线性可分条件下)

假定样本空间如下 $$ { ( x _ { 1 } , y _ { 1 } ) , ( x _ { 2 } , y _ { 2 } ) , \ldots , ( x _ { N } , y _ { N } ) } $$

共有N个向量，其中$x_k$是一个特征向量而不是一个单一数值。

假设超平面能够将训练样本正确分类，那么就有以下的式子成立：

这是一个二分类问题，所以$y=+1 $或者$ y=−1$。那么我们就可以得到

$$ y = \begin{cases} +1 & w^Tx +b > 0 \\
-1 & w^Tx +b <0 \end{cases}$$

上面是逻辑回归的思路，没有一点的缓冲余地。如实SVM 使用下面的判别式：

$$ y = \begin{cases} +1 & w^Tx +b >= +1 \\
-1 & w^Tx +b <= -1 \end{cases}$$

上面距离超平面最近的几个训练样本点使上式的等号成立，这几个训练样本被称为支持向量，两个异类支持向量到超平面的距离

那么，我们可以得到 $$ y _ { i } \cdot ( w ^ { T } x _ { i } + b ) \geq 1 , i = 1,2 , \ldots , N $$

因为我们现在只讨论线性可分情况下的支持向量机，那么在这个样本空间中一定存在一个超平面可以将样本集按照y的值分割城两个部分，这个超平面可以表示为

$$ w ^ { T } x + b = 0 $$

根据这个超平面的表达式以及第一步推到中我们得到的结果，可以得到这个样本集中任意一个样本点距离超平面的距离：

$$ \gamma = \frac { | w ^ { T } x + b | } { | w | } \geq \frac { 1 } { | w | } $$

两个异类支持向量到超平面的距离之和，也称为间隔，为

$$ \gamma = \frac { 2 } { | w | } $$

由此，根据第一步和第三步的结果，我们可以得到最基本的目标函数：

$$\arg \max _ { w , b } \frac { 2 } { | w | } , \text {s.t. } y _ { i } ( w ^ { T } x _ { i } + b ) \geq 1 , i = 1,2 , \ldots , N$$

我们还可以对这个目标函数进一步做变化：

$$\arg \min _ { w , b } \frac { 1 } { 2 } | w | ^ { 2 }, \text {s.t. } y _ { i } ( w ^ { T } x _ { i } + b ) \geq 1 , i = 1,2 , \ldots , N $$

我们无法继续直接进行计算了，因此引入拉格朗日乘子

$$ L ( w , b , \alpha ) = \frac { 1 } { 2 } | w | ^ { 2 } + \sum _ { i } \alpha _ { i } [ 1 - y _ { i } ( w ^ { T } x _ { i } + b ) ] $$

对w和b分别求L的偏导，并令其偏导数等于0： $$\frac { \partial L } { \partial w } = w - \sum _ { i } \alpha _ { i } y _ { i } x _ { i } = 0 \Rightarrow w = \sum _ { i } \alpha _ { i } y _ { i } x _ { i }$$ $$\frac { \partial L } { \partial b } = \sum _ { i } \alpha _ { i } y _ { i } = 0$$
将第七步得到的w和b代入L函数

至此，我们的目标函数已经变成了

$$ \arg \max _ { \alpha } ( \sum _ { i } \alpha _ { i } - \frac { 1 } { 2 } \sum _ { i } \sum _ { j } \alpha _ { i } \alpha _ { j } y _ { i } y _ { j } x _ { i } ^ { T } x _ { j } ) $$

$$ \text { s.t. } \sum _ { i } \alpha _ { i } y _ { i } = 0 $$

$$ \alpha _ { i } \geq 0 , i = 1,2 , \ldots , N $$

用数值方法解出α以后，我们带入式子 7就可以得到

$$ w^ { * } = \sum _ { i } \alpha _ { i } ^ { * } y _ { i } x _ { i } $$

SVM的特点

SVM的优点：就是当大量的特征出现的时候，使用SVM handle large feature spaces; 然而此时 LR 不是一个很好的选择。

SVM can handle large feature spaces which makes them one of the favorite algorithms in text analysis which almost always results in huge number of features where logistic regression is not a very good choice.

SVM Pros:

Can handle large feature space
Can handle non-linear feature interactions
Do not rely on entire data

SVM Cons:

Not very efficient with large number of observations
It can be tricky to find appropriate kernel sometimes

核函数的作用：

核函数是将原始空间线性不可分，映射到一个高纬的特征空间，使得样本在这个维度变得线性可分。
核函数的种类：分为线性核函数和高斯核函数。前者参数少，计算量小，如果是特征数量比较大，那么是可以考虑线性核函数；如果特征数量比较小，可以考虑高斯核函数。

TakeOff

首先使用 LR 进行尝试，不妨试一下 DT，然后如果特征比较多，但是数据量不是很多，这个时候使用SVM。 Always start with logistic regression, if nothing then to use the performance as baseline See if decision trees (Random Forests) provide significant improvement. Even if you do not end up using the resultant model, you can use random forest results to remove noisy variables Go for SVM if you have large number of features and number of observations are not a limitation for available resources and time 附上链接： https://www.edvancer.in/logistic-regression-vs-decision-trees-vs-svm-part2/

文章目录