学习July博文总结——支持向量机(SVM)的深入理解（上）
学习July博文总结——支持向量机(SVM)的深入理解（上）
前言
本文是参照CSDN的July大神的热门博文《支持向量机通俗导论（理解SVM的三层境界》）写的。目的是因为July大神文中说，SVM理论的理解，需要一遍一遍的推导公式，直到脑中梳理下来，并可以直接推导相关公式的。本文的写作目的，是在笔者在第一次参考了July大神的博客，并手动推导公式成功后，希望通过Markdown的记录流程，进行第二遍对SVM理论的理解。另外，在笔者第一次研究SVM过程中会存在某些不懂的问题，笔者也会秉着July大神的理念——让没有机器学习理论基础的读者们看懂博文，尽量的将SVM的理论解释清楚。 再次说明，本文的最主要目的是笔者对博主July关于SVM理论介绍的二次学习，如果可以的话，也希望能给笔者的读者一些启发。
本文说明：
- 本文中涉及大量的向量，有的加了向量符号，有的没有加向量符号，但由于数量过多，且参考资料比较多，所以难以统一，笔者只能尽量的说明清楚。例如，文中的数据点xx都是向量，核函数中的K(xi,x)K(x_i, x)与K(xi→,x→)K(\overrightarrow{x_i}, \overrightarrow{x})表达的是同一个意思。
参考网址：
《支持向量机通俗导论（理解SVM的三层境界》） 《支持向量机（五）SMO算法 》
一、了解SVM
支持向量机(Support Vector Machine, SVM)，通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。
1. 分类标准的起源：Logistic回归
(1) 线性分类器
理解SVM，咱们必须先弄清楚一个概念：线性分类器。 给定一些数据点，它们分别属于两个不同的类，现在要找到一个线性分类器把这些数据分成两类。如果用x表示数据点，用y表示类别（y可以取1或者-1，分别代表两个不同的类），一个线性分类器的学习目标便是要在n维的数据空间中找到一个超平面(hyper plane)，这个超平面的方程可以表示为： ωTx+b=0(1.1.1)
- ω中的T表示转置；
- x：数据点
- y：类别（取1或-1）
对于yy取1或-1，可能有读者表示有疑问。其实1或-1的分类标准起源于logistic回归。
(2) Logistic回归
Logistic回归目的是从特征学习出一个0/1分类模型。这个模型是将特性的线性组合作为自变量，由于自变量的取值范围是负无穷到正无穷。因此，使用logistic函数（或称作sigmoid函数）将自变量映射到(0,1)上，映射后的值被认为是属于y=1的概率。
有假设函数：
- x：n维数据点；
- g：Logistic函数；
- θTx：数据点xX的特征；
（关于\thetaθ 与\omegaω的关系，后面式1.1.5中会给出解释） 而
的图像如下图1.1所示：
从图中可以看出，Logister函数将范围为负无穷到正无穷的自变量z，映射到了区间(0, 1)。 前面提到的假设函数（式1.1.2），就是类型属于y = 1的概率。 \left\{\begin{matrix} \begin{align*} & P(y=1|x;\theta)=h_\theta(x) \\ & P(y=0|x;\theta)=1-h_\theta(x) \end{align*} \end{matrix} \right. \qquad (1.1.3)
这样，当我们要判别一个新来的特征属于哪个类时，只需求h_\theta(x)hθ(x)h_\theta(x)即可，若h_\theta(x)hθ(x)h_\theta(x)大于0.5，数据点就是y=1的类；反之，属于y=0类。
注：hθ(x)只与θTx有关
如果我们只从特征θTx出发，那么我们所构建的模型的目标，就是让训练数据中，y=1y=1的特征θT≫0，且y=0的特征θT≪0。Logistic回归，就是要学习得到θ，使得正例的特征远大于0，负例的特征远小于0，而且要在全部训练实例上达到这个目标。
(3) Logistic回归变形
为了后面的使用方便，我们这里对Logistic回归进行变形。 首先，将使用的结果标签y=0与y=1替换为y=−1与y=1。展开特征θTx，如下式：
然后将上式(1.1.4)中的θ0替换为b，最后将后面的
替换为ωTx。如此，则得到了：
也就是说，除了分类值y，由y=0变为y=−1之外，线性分类函数与Logistic回归的形式
没有区别。 进一步，我们可以将假设函数
中的g(z)函数做一个简化，将其简单映射到y=−1与y=1上。映射关系如下：
2. 线性分类的一个例子
(1) 线性分类举例
下面举个简单的例子。如下图1.2所示，现在有一个二维平面，平面上有两种不同的数据，分别用圈和叉表示。由于这些数据是线性可分的，所以可以用一条直线将这两类数据分开，这条直线就相当于一个超平面，超平面一边的数据点所对应的y全是-1 ，另一边所对应的y全是1。
这个超平面可以用分类函数f(x)=ωTx+b表示，当f(x)等于0的时候，x便是位于超平面上的点，而f(x)大于0的点对应y=1的数据点，f(x)小于0的点对应y=−1的点，如下图1.3所示：
换言之，在进行分类的时候，遇到一个新的数据点xx，将xx代入f(x)f(x)中。如果f(x)f(x)小于0，则将x的类别赋为-1；如果f(x)f(x)大于0，则将x的类别赋为1。
注： 有的资料定义特征到结果的输出函数为
（后文也有用到），与这里定义的f(x)=ωTx+b本质上是一样的。 为什么呢？因为无论是
还是f(x)=ωTx+b，都不影响最终的优化结果。 下文你将看到，当我们转化到优化目标函数
的时候，为了求解方便，我们会把yf(x)令为1。即yf(x)无论是y(ωT+b)，还是y(ωT−b)，对我们要优化的目标函数
已经没有影响。
(2) y的取值意义
在July大神的博客中，有人问：SVM函数间隔中
是只取1和-1 吗？y的唯一作用就是确保函数间隔的非负性？ 此处总结July博客下面评论中的解释如下：
这个问题将问题搞混了。y是个分类标签，二分时，y就取了两个值，而刚好取了-1和1。只是因为用超平面分类时，不同的类中的点的函数值刚好有不同的符号，所以这里就用符号来进行了分类。 具体阐述如下： 1. 对于二类问题，因为y只取两个值，这两个是可以任意取的，只要是取两个值就行； 2. 支持向量机去求解二类问题，目标是求一个特征空间的超平面；而超平面分开的两类对应于超平面的函数值的符号是刚好相反的； 3. 基于上述两种考虑，为了使问题足够简单，我们取yy的值为1和-1； 4. 在取定分类标签y为-1和1之后，一个平面正确分类样本数据，就相当于用这个平面计算yf(x)>0； 5. 并且这样一来，yf(x)也有了明确的几何含义；
总而言之要明白，二类问题的标签yy是可以取任意两个值的，不管取怎样的值对于相同的样本点，只要分类相同，所有的y的不同取值都是等价的。之所以取某些特殊的值，只是因为这样一来计算会变得方便，理解变得容易。正如July大神的朋友张磊所言，svm中y取1或-1的历史原因是因为感知器最初的定义，实际取值可以任意，总能明确表示输入样本是否被误分，但是用+1、-1可以起码可以是问题描述简单化、式子表示简洁化、几何意义明确化。 举个例子：如果取yy为1与2（比如原来取-1的现在取1，原来取1的现在取2 ），那么分类正确的判定标准就变成了(y−1.5)⋅f(x)>0。所以取1和-1只是为了计算简单方便，没有实质变化，更非一定必须取一正一负。
接下来的问题是，如何确定这个超平面呢？从直观上而言，这个超平面应该是最适合分开两类数据的直线。而判定“最适合”的标准就是这条直线离直线两边的数据的间隔最大。所以，得寻找有着最大间隔的超平面。
3. 函数间隔与几何间隔
(1) 函数间隔(Functional Margin)
在超平面ωTx+b=0确定的情况下，|ωTx+b|能够表示点x到超平面的距离远近，而通过观察ωTx+b的符号与类型标记y符号是否一致，可以判断分类是否正确。 所以，我们可以用y⋅(ωT+b)的正负性来判定或表示分类的正确性。所以我们便在此处引出了函数间隔(Functional Margin)的概念。 定义函数间隔如下所示：
γ^=y(ωTx+b)=yf(x)(1.3.1)
式(1.3.1)中参数含义如下：
- x：特征；
- y：结果标签；
- i：表示第i个样本；
而超平面(ω,b)关于训练数据集TT中所有样本点(xi,yi)的函数间隔最小值，便成为超平面(ω,b)关于T的函数间隔：
γ^=minγi^(i=1,...n)(1.3.2)
(2) 几何间隔(Geometrical Margin)
上面给出了函数间隔的定义，但这样定义的函数间隔有问题。比如成比例的改变ω,b（如将他们都增大2倍），则函数间隔f(x)的值变成了原来的2倍，但此时超平面却没有改变。所以只有函数间隔远远不够。 事实上，我们可以对法向量ω\omega加些约束条件，从而引出真正定义点到超平面的距离–几何间隔（geometrical margin）的概念。 假定对于一个点xx，令其垂直投影到超平面上的对应点为x0，ω是垂直于超平面的一个向量，为样本x到超平面的距离，如下图1.4所示：
根据平面几何知识，有：
4. 最大间隔分类器(Maximum Margin Classifier)
(1) “间隔”的说明
对一个数据点进行分类，当超平面离数据点的”间隔”越大，分类的确信度(confidence)也越大。所以，为了使得分类的确信度尽量高，需要让所选择的超平面能够最大化该“间隔”值。这个间隔就是下图1.5中的Gap的一半。
(2) 最大间隔分类器的定义
至此算是将SVM的第一层讲解完毕，对于那些只关心怎么用SVM的朋友便已足够，不必再更进一层深究其更深的原理。
二、深入SVM
1. 从线性可分到线性不可分
接着考虑上一章中得到的式(1.4.3)中的目标函数：
(1) 从原始问题到对偶问题的求解
由于现在的目标函数是二次的，约束条件是线性的，所以它是一个凸二次规划问题。 这个问题可以用现成的QP (Quadratic Programming) 优化包进行求解。一言以蔽之：在一定的约束条件下，目标最优，损失最小。 此外，由于这个问题的特殊结构，还可以通过拉格朗日对偶性（Lagrange Duality）变换到对偶变量 (dual variable) 的优化问题，即通过求解与原问题等价的对偶问题（Dual Problem）得到原始问题的最优解，这就是线性可分条件下支持向量机的对偶算法。 这样做的优点在于：
- 对偶问题往往更容易求解；
- 可以自然的引入核函数，进而推广到非线性分类问题。
(2) KKT条件
(3) 对偶问题求解的3个步骤
求解这个对偶学习问题，分为三个步骤： 1. 令L(ω,b,α)关于ω和b最小化； 2. 利用SMO算法求解对偶问题中的拉格朗日乘子，求对α的极大； 3. 求参数ω,b；
注：July大神的原文中的步骤与笔者的不同，是因为笔者没有理解按照July大神的步骤。按照原文中的(2)(3)步骤的话，是已经在步骤(2)中求出了α的极大（即已经求出了α），然后又在步骤(3)中用SMO算法求了一遍α，这是笔者不能理解的。所以笔者在此按照自己的理解，把这三个步骤改了一下。如果真有读者看到了这里而且有指点意见的话，笔者感激不尽。
下面按步骤进行说明：
B. 利用SMO算法求解对偶问题中的拉格朗日乘子
(4) 线性不可分的情况
到目前为止，我们的 SVM 还比较弱，只能处理线性的情况，下面我们将引入核函数，进而推广到非线性分类问题。 让我们再来看看上述推导过程中得到的一些有趣的形式。首先就是关于我们的超平面，对于一个数据点x分类，实际上是通过把xx带入到f(x)=ωTx+b算出结果，然后根据其正负号进行类别划分的。在前面的推导中，我们得到式(2.1.8))：
2. 核函数Kernel
(1) 特征空间的隐式映射
事实上，大部分时候数据并不是线性可分的，这个时候满足这样条件的超平面就根本不存在。 在上文中，我们已经了解到了SVM处理线性可分的情况，那对于非线性的数据SVM应该怎么处理？对于非线性的情况，SVM 的处理方法是选择一个核函数\mathcal{K}(⋅,⋅)K(⋅,⋅) ，通过将数据映射到高维空间，来解决在原始空间中线性不可分的问题。 具体来说，在线性不可分的情况下，支持向量机首先在低维空间中完成计算，然后通过核函数将输入空间映射到高维特征空间，最终在高维特征空间中构造出最优分离超平面，从而把平面上本身不好分的非线性数据分开。如图2.1所示，一堆数据在二维空间无法划分，从而映射到三维空间里划分：
而在我们遇到核函数之前，如果用原始的方法，那么在用线性学习器学习一个非线性关系，需要选择一个非线性特征集，并且将数据写成新的表达形式，这等价于应用一个固定的非线性映射，将数据映射到特征空间，在特征空间中使用线性学习器，因此，考虑的假设集是如下式(2.2.1)这种类型的函数：
(2) 核函数：如何处理非线性数据
A. 原始数据的映射
来看个核函数的例子。如下图2.2所示的两类数据，分别分布为两个圆圈的形状，这样的数据本身就是线性不可分的，此时我们该如何把这两类数据分开？ 注：后面会有July大神的好友pluskid提供的gif动图说明。
上图映射之后的结果，将坐标轴经过适当的旋转，就可以很明显地看出，数据是可以通过一个平面来分开的。
上面的例子可以体现，核函数相当于将原来的分类函数：
B. 维度爆炸问题的解决
看起来问题似乎解决了：拿到了非线性数据，就找一个映射ϕ(⋅)，然后一股脑把原来的数据映射到新空间中，再做线性 SVM 即可。
而实际上并没有这么简单，原因在于可能出现维度爆炸的情况。 刚才的方法稍想一下就会发现有问题：在最初的例子里，我们对一个二维空间做映射，选择的新空间是原始空间的所有一阶和二阶的组合，得到了五个维度；如果原始空间是三维，那么我们展开后会得到19维的新空间。这样的话，维度数目是呈爆炸增长的，这给ϕ(⋅)的计算带来了非常大的困难，而且如果遇到了无穷维的计算，就根本无从计算了。 这时候仍然需要Kernel方法解决这个问题。
注：关于上述两个公式的说明
(3) 几个常用核函数
通常人们会从一些常用的核函数中选择（根据问题和数据的不同，选择不同的参数，实际上就是得到了不同的核函数）。
A. 多项式核
多项式核形式如下：
显然刚才我们举的例子是这里多项式核的一个特例(R = 1, d = 2)。
B. 高斯核
高斯核形式如下：
这个核就是最开始提到过的，会将原始空间映射为无穷维空间的那个家伙。 不过，如果σ选得很大的话，高次特征上的权重实际上衰减得非常快，所以实际上（数值上近似一下）相当于一个低维的子空间；反过来，如果σ选得很小，则可以将任意的数据映射为线性可分，当然这并不一定是好事，因为随之而来的可能是非常严重的过拟合问题。 不过总的来说，通过调控参数σ，高斯核实际上具有相当高的灵活性，也是使用最广泛的核函数之一。下图2.4所示的例子便是把低维线性不可分的数据通过高斯核函数映射到了高维空间：
C. 线性核
线性核形式如下：
这个核实际上就是原始空间中的内积，它存在的主要目的是使得“映射后空间中的问题”和“映射前空间中的问题”两者在形式上统一起来了。这里的意思是说，咱们写代码或写公式的时候，只要写个模板或通用表达式，然后再代入不同的核就可以了。这样便不用再分别写一个线性的，和一个非线性的，在形式上统一了起来。
(4) 核函数的本质
上面说了这么多，还是要在这里概括一下核函数到底是什么东西。基本上就是三点：
- 实际中，我们会经常遇到线性不可分的样例，此时，我们的常用做法是把样例特征映射到高维空间中去（如上文的图2.2与图2.3，映射到高维空间后，相关特征便被分开了，也就达到了分类的目的）；
- 但进一步，如果凡是遇到线性不可分的样例，一律映射到高维空间，那么这个维度大小是会高到可怕的（即维度爆炸，如前文说的19维甚至无穷维的例子）；
- 此时，核函数就隆重登场了，核函数的价值在于它虽然也是将特征进行从低维到高维的转换，但核函数绝就绝在它事先在低维上进行计算，而将实质上的分类效果表现在了高维上，也就如上文所说的避免了直接在高维空间中的复杂计算。
最后引用一个例程，举例说明一下核函数解决非线性问题的直观效果： 假设现在你是一个农场主，圈养了一批羊群，但为预防狼群袭击羊群，你需要搭建一个篱笆来把羊群围起来。但是篱笆应该建在哪里呢？你很可能需要依据牛群和狼群的位置建立一个分类器，比较下图这几种不同的分类器，我们可以看到SVM完成了一个很完美的解决方案。
这个例子从侧面简单说明了SVM使用非线性分类器的优势，而逻辑模式以及决策树模式都是使用了直线方法。
3. 松弛变量
在本文第一节最开始讨论支持向量机的时候，我们就假定，数据是线性可分的，亦即我们可以找到一个可行的超平面将数据完全分开。后来为了处理非线性数据，在本章第2节使用Kernel方法对原来的线性 SVM 进行了推广，使得非线性的情况也能处理。虽然通过映射ϕ(⋅)\phi(\cdot)将原始数据映射到高维空间之后，能够线性分隔的概率大大增加，但是对于某些情况还是很难处理。 例如可能并不是因为数据本身是非线性结构的，而只是因为数据有噪音。对于这种偏离正常位置很远的数据点，我们称之为outlier，在我们原来的 SVM 模型里，outlier 的存在有可能造成很大的影响，因为超平面本身就是只有少数几个支持向量组成的，如果这些支持向量里又存在 outlier 的话，其影响就很大了。比如下图2.6所示：
用黑圈圈起来的那个蓝点是一个 outlier ，它偏离了自己原本所应该在的那个半空间，如果直接忽略掉它的话，原来的分隔超平面还是挺好的。但是由于这个 outlier 的出现，导致分隔超平面不得不被挤歪了，变成途中黑色虚线所示（这只是一个示意图，并没有严格计算精确坐标），同时函数间隔也相应变小了。当然，更严重的情况是，如果这个 outlier 再往右上移动一些距离的话，我们将无法构造出能将数据分开的超平面来。 为了处理这种情况，SVM 允许数据点在一定程度上偏离一下超平面。例如上图中，黑色实线所对应的距离，就是该 outlier 偏离的距离，如果把它移动回来，就刚好落在原来的蓝色间隔边界上，而不会使得超平面发生变形了。换言之，在有松弛的情况下outline点也属于支持向量SV，同时，对于不同的支持向量，拉格朗日参数的值也不同。 在论文《Large Scale Machine Learning》中阐述了相关内容，如下图2.7所示：
把前后的结果对比一下（错误修正：图中的Dual formulation中的Minimize应为maxmize）：
4. 总结
理解到这第二层，已经能满足绝大部分人一窥SVM原理的好奇心，然对于那些想在证明层面理解SVM的则还很不够，但进入第三层理解境界之前，建议读者要有比较好的数理基础和逻辑证明能力。毕竟原作者July大神尚且吃了不少苦头，更何况笔者一个机器学习的小渣渣……
后面第三章证明SVM的部分，由于CSDN篇幅所限，所以放在下面一篇博客中。