1、支持向量机通俗导论（理解支持向量机通俗导论（理解 SVMSVM 的三层境界）的三层境界）在本文中，你将看到，理解 SVM 分三层境界，第一层、了解 SVM(你只需要对 SVM 有个大致的了解，知道它是个什么东西便已足够)；第二层、深入 SVM(你将跟我一起深入 SVM 的内部原理，通宵其各处脉络，以为将来运用它时游刃有余)；第三层、证明 SVM(当你了解了所有的原理之后，你会有大笔一挥，尝试证明它的冲动)；第一层、了解第一层、了解 SVM1.0、什么是支持向量机、什么是支持向量机 SVM然在进入第一层之前， 你只需了解什么是支持向量机 SVM 就够了， 而要明白什么是 SVM，便得从分类说起。
2、分类作为数据挖掘领域中一项非常重要的任务，目前在商业上应用最多(比如分析型CRM 里面的客户分类模型，客户流失模型，客户盈利等等，其本质上都属于分类问题)。而分类的目的则是学会一个分类函数或分类模型(或者叫做分类器)，该模型能吧数据库中的数据项映射到给定类别中的某一个，从而可以用于预测未知类别。其实，若叫分类，可能会有人产生误解，以为凡是分类就是把一些东西或样例按照类别给区分开来，实际上，分类方法是一个机器学习的方法，分类也成为模式识别，或者在概率统计中称为判别分析问题。你甚至可以想当然的认为，分类就是恰如一个商场进了一批新的货物，你现在要根据这些货物的特征分门别类的摆放在相关的架子上， 这一
3、过程便可以理解为分类， 只是它由训练有素的计算机程序来完成。说实话，上面这么介绍分类可能你不一定内心十分清楚。我来举个例子吧，比如心脏病的确诊中，如果我要完全确诊某人得了心脏病，那么我必须要进行一些高级的手段，或者借助一些昂贵的机器，那么若我们没有那些高科技医疗机器怎么办？还怎么判断某人是否得了心脏病呢？当然了，古代中医是通过望、闻、问、切“四诊”，但除了这些，我们在现代医学里还是可以利用一些比较容易获得的临床指标进行推断某人是否得了心脏病。如作为一个医生，他可以根据他以往诊断的病例对很多个病人(假设是 500 个)进行彻底的临床检测之后，已经能够完全确定了哪些病人具有心脏病，哪些没有。因为，
4、在这个诊断的过程中，医生理所当然的记录了他们的年龄，胆固醇等 10 多项病人的相关指标。那么，以后，医生可以根据这些临床资料，对后来新来的病人通过检测那对后来新来的病人通过检测那 10 多项年龄、胆固醇等指标多项年龄、胆固醇等指标，以此就能推断或者判定病人是否有心脏病推断或者判定病人是否有心脏病，虽说不能达到 100%的标准，但也能达到 80、90%的正确率，而这一根据以往临场病例指标分析来推断新来的病例的技术，即成为分类 classification 技术。OK，既然讲到了病例诊断这个例子，接下来咱们就以这个例子来简单分析下 SVM。假定是否患有心脏病与病人的年龄和胆固醇水平密切相关，下表对
5、应 10 个病人的临床数据(年龄用x1表示，胆固醇水平用x2表示)：这样，问题就变成了一个在二维空间上的分类问题，可以在平面直角坐标系中描述如下：根据病人的两项指标和有无心脏病，把每个病人用一个样本点来表示，有心脏病者用“+”形点表示，无心脏病者用圆形点，如下图所示：如此我们很明显的看到，是可以在平面上用一条直线把圆点和“+”分开来的。当然，事实上，还有很多线性不可分的情况，下文将会具体描述。So，本文将要介绍的支持向量机 SVM 算法便是一种分类方法。所谓支持向量机，顾名思义，分为两个部分了解，一什么是支持向量(简单来说，就是支持 or 支撑平面上把两类类别划分开来的超平面的向量点，下文将具
6、体解释)，二这里的“机”是什么意思。我先来回答第二点：这里的“机（machine,机器）”便是一个算法。在机器学习领域，常把一些算法看做是一个机器，如分类机(当然，也叫做分类器)，而支持向量机本身便是一种监督式学习的方法(什么是监督学习与非监督学习，请参见第一篇)，它广泛的应用于统计分类以及回归分析中。支持向量机(SVM)是 90 年代中期发展起来的基于统计学习理论的一种机器学习方法，通过寻求结构化风险最小来提高学习机泛化能力， 实现经验风险和置信范围的最小化， 从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。对于不想深究 SVM 原理的同学(比如就只想看看 SVM 是干嘛的)，
7、那么，了解到这里便足够了，不需上层。而对于那些喜欢深入研究一个东西的同学，甚至究其本质的，咱们则还有很长的一段路要走，万里长征，咱们开始迈第一步吧(相信你能走完)。1.1、线性分类、线性分类OK，在讲 SVM 之前，咱们必须先弄清楚一个概念：线性分类器(也可以叫做感知机，这里的机表示的还是一种算法，本文第三部分、证明 SVM 中会详细阐述)。这里我们考虑的是一个两类的分类问题，数据点用 x 来表示，这是一个 n 维向量，而类别用 y 来表示， 可以取 1 或者 -1 ， 分别代表两个不同的类。 一个线性分类器就是要在 n 维的数据空间中找到一个超平面，其方程可以表示为：wTx+b=0对应的几何
8、示意图如下：1.2、线性分类的一个例子、线性分类的一个例子来理论可能读者看不懂，咱们来直接举一个例子吧，且举最简单的例子，一个二维平面(一个超平面，在二维空间中的例子就是一条直线)，如下图所示，平面上有两种不同的点，分别用两种不同的颜色表示，一种为红颜色的点，另一种则为蓝颜色的点，红颜色的线表示一个可行的超平面。从上图中我们可以看出，这条红颜色的线把红颜色的点和蓝颜色的点分开来了。而这条红颜色的线就是我们上面所说的超平面， 也就是说， 这个所谓的超平面的的确确便把这两种不同颜色的数据点分隔开来，在超平面一边的数据点所对应的y全是 -1 ，而在另一边全是 1 。接着，我们可以令分类函数（下文将一
9、直用蓝色表示分类函数）f(x)=wTx+b，显然，如果f(x)=0，那么x是位于超平面上的点。我们不妨要求对于所有满足f(x)0则对应y=1的数据点。（有一朋友飞狗来自 Mare_Desiderii， 看了上面的定义之后， 问道： 请教一下 SVM functional margin 为=y(wTx+b)=yf(x)中的 Y 是只取 1 和-1 吗？y 的唯一作用就是确保 functional margin 的非负性？真是这样的么？当然不是，详情请见本文评论下第 43 楼）当然，有些时候（或者说大部分时候）数据并不是线性可分的，这个时候满足这样条件的超平面就根本不存在(不过关于如何处理这样的问
10、题我们后面会讲)， 这里先从最简单的情形开始推导，就假设数据都是线性可分的，亦即这样的超平面是存在的。更进一步， 我们在进行分类的时候， 将数据点x代入f(x)中， 如果得到的结果小于 0 ，则赋予其类别 -1 ，如果大于 0 则赋予类别 1 。如果f(x)=0，则很难办了，分到哪一类都不是(后续会说明此种情况)。1.3、函数间隔、函数间隔Functional margin 与几何间隔与几何间隔 Geometrical margin一般而言，一个点距离超平面的远近可以表示为分类预测的确信或准确程度。在超平面w*x+b=0 确定的情况下，|w*x+b|能够相对的表示点 x 到距离超平面的远近，而
11、 w*x+b的符号与类标记 y 的符号是否一致表示分类是否正确，所以，可以用量 y*(w*x+b)的正负性来判定或表示分类的正确性和确信度，于此，我们便引出了函数间隔 functional margin 的概念。1.3.1、函数间隔、函数间隔 Functional margin我们定义函数间隔 functional margin 为：=y(wTx+b)=yf(x)，接着，我们定义超平面(w，b)关于训练数据集 T 的函数间隔为超平面(w，b)关于 T 中所有样本点(xi，yi)的函数间隔最小值，即：=mini(i=1，.n)然与此同时，问题就出来了。上述定义的函数间隔虽然可以表示分类预测的正确
12、性和确信度，但在选择分类超平面时，只有函数间隔还远远不够，因为如果成比例的改变 w 和 b，如将他们改变为 2w 和 2b，虽然此时超平面没有改变，但函数间隔的值 f(x)却变成了原来的改变(代进去一眼便看出来了)。其实，我们可以对法向量 w 加些约束条件，使其表面上看起来规范化，如此，我们很快又将引出真正定义点到超平面的距离-几何间隔几何间隔 geometricalmargin 的概念。1.3.2、点到超平面的距离定义：几何间隔、点到超平面的距离定义：几何间隔 Geometrical margin在给出几何间隔的定义之前，咱们首先来看下，如上图所示，对于一个点x，令其垂直投影到超平面上的对应
13、的为x0，由于w是垂直于超平面的一个向量，我们有x=x0+ww（|w|表示的是范数， 关于范数的概念参见： http:/ 分开相除的形式，如本文参考文献及推荐阅读条目 9，其中，|w|为 w 的二阶泛数）不过，这里的是带符号的，我们需要的只是它的绝对值，因此类似地，也乘上对应的类别y即可，因此实际上我们定义 几何间隔几何间隔 geometrical margin 为：=y=w（代人相关式子可以得出：yi*(w/|w| + b/|w|)）正如本文评论下读者 popol1991 留言： 函数间隔 y*(wx+b)=y*f(x)实际上就是|f(x)|， 只是人为定义的一个间隔度量；而几何间隔|f(x
14、)|/|w|才是直观上的点到超平面距离。想想二维空间里的点到直线公式：假设一条直线的方程为 ax+by+c=0,点 P 的坐标是(x0,y0)，则点到直线距离为|ax0+by0+c|/sqrt(a2+b2)。如下图所示：那么如果用向量表示，设 w=(a,b),f(x)=wx+c,那么这个距离不正是|f(p)|/|w|么？OK，下图中 xi，和 xj 分别到超平面的距离：1.4、最大间隔分类器、最大间隔分类器 Maximum Margin Classifier 的定义的定义于此，我们已经很明显的看出，函数间隔 functional margin 和几何间隔 geometricalmargin 相
15、差一个w的缩放因子。按照我们前面的分析，对一个数据点进行分类，当它的 margin 越大的时候，分类的 confidence 越大。对于一个包含n个点的数据集，我们可以很自然地定义它的 margin 为所有这n个点的 margin 值中最小的那个。于是，为了使得分类的 confidence 高，我们希望所选择的超平面 hyper plane 能够最大化这个margin 值。通过上节，我们已经知道：1、functional margin 明显是不太适合用来最大化的一个量，因为在 hyper plane 固定以后，我们可以等比例地缩放w的长度和b的值，这样可以使得f(x)=wTx+b的值任意大，亦
16、即 functional margin可以在 hyper plane 保持不变的情况下被取得任意大，2、而 geometrical margin 则没有这个问题，因为除上了w这个分母，所以缩放w和b的时候的值是不会改变的，它只随着 hyper plane 的变动而变动，因此，这是更加合适的一个 margin 。这样一来，我们的 maximum margin classifier 的目标函数可以定义为：max 当然，还需要满足一些条件，根据 margin 的定义，我们有其中=w(等价于 = / w，故有稍后的 =1 时， = 1 / |w|)，处于方便推导和优化的目的，我们可以令=1(对目标函数
17、的优化没有影响，至于为什么，请见本文评论下第 42 楼回复) ，此时，上述的目标函数 转化为(其中，s.t.，即 subject to 的意思，它导出的是约束条件)：通过求解这个问题，我们就可以找到一个 margin 最大的 classifier ，如下图所示，中间的红色线条是 Optimal Hyper Plane ，另外两条线到红线的距离都是等于另外两条线到红线的距离都是等于的的( 便是上文所定义的 geometrical margin，当令=1时， 便为 1/|w|，而我们上面得到的目标函数便是在相应的约束条件下，要最大化这个 1/|w|值)：通过最大化 margin ， 我们使得该分类
18、器对数据进行分类时具有了最大的 confidence 。但，这个最大分类间隔器到底是用来干嘛的呢？很简单，SVM 通过使用最大分类间通过使用最大分类间隙隙Maximum Margin Classifier 来设计决策最优分类超平面来设计决策最优分类超平面，而为何是最大间隔，却不是最小间隔呢？因为最大间隔能获得最大稳定性与区分的确信度，从而得到良好的推广能力(超平面之间的距离越大，分离器的推广能力越好，也就是预测精度越高，不过对于训练数据的误差不一定是最小的.2012.08.21updated)。So，对于什么是 Support Vector Machine ，我们可以先这样理解，如上图所示，我
19、们可以看到 hyper plane 两边的那个 gap 分别对应的两条平行的线 （在高维空间中也应该是两个 hyper plane）上有一些点，显然两个超平面 hyper plane 上都会有点存在，否则我们就可以进一步扩大 gap ，也就是增大的值了。这些点，就叫做 support vector。下文 1.5节将更为具体描述。1.5、到底什么是、到底什么是Support Vector上节，我们介绍了 Maximum Margin Classifier，但并没有具体阐述到底什么是 SupportVector，本节，咱们来重点阐述这个概念。咱们不妨先来回忆一下上节 1.4 节最后一张图：可以看到
20、两个支撑着中间的 gap 的超平面，它们到中间的纯红线 separating hyperplane 的距离相等，即我们所能得到的最大的 geometrical margin。而“支撑”这两个超平面的必定会有一些点，而这些“支撑”的点便叫做支持向量 Support Vector。很显然，由于这些 supporting vector 刚好在边界上，所以它们是满足y(wTx+b)=1（还记得我们把 functional margin 定为 1 了吗？上节中：“处于方便推导和优化的目的，我们可以令 =1”），而对于所有不是支持向量的点，也就是在“阵地后方”的点，则显然有y(wTx+b)1。当然，通常除
21、了 K-Nearest Neighbor 之类的 Memory-basedLearning 算法，通常算法也都不会直接把所有的点记忆下来，并全部用来做后续 inference中的计算。不过，如果算法使用了 Kernel 方法进行非线性化推广方法进行非线性化推广的话，就会遇到这个问题了。Kernel 方法在下文第二部分 2.2 节中介绍）。OK，到此为止，算是了解到了 SVM 的第一层，对于那些只关心怎么用 SVM 的朋友便已足够，不必再更进一层深究其更深的原理。第二层、深入第二层、深入 SVM2.1、从线性可分到线性不可分、从线性可分到线性不可分当然，除了在上文中所介绍的从几何直观上之外，支持
22、向量的概念也可以从其优化过程的推导中得到。虽然上文 1.4 节给出了目标函数，却没有讲怎么来求解。现在就让我们来处理这个问题。回忆一下之前得到的目标函数（subject to 导出的则是约束条件）：这个问题等价于（w 由分母变成分子，从而也有原来的 max 问题变为 min 问题，很明显，两者问题等价）：1.到这个形式以后，就可以很明显地看出来，它是一个凸优化问题，或者更具体地说，它是一个二次优化问题目标函数是二次的，约束条件是线性的。这个问题可以用任何现成的 QP(Quadratic Programming) 的优化包进行求解。所以，我们的问题到此为止就算全部解决了。2.虽然这个问题确实是一
23、个标准的 QP 问题，但是它也有它的特殊结构，通过 Lagrange Duality 变换到对偶变量 (dual variable) 的优化问题之后，可以找到一种更加有效的方法来进行求解，而且通常情况下这种方法比直接使用通用的 QP 优化包进行优化要高效得多。也就说，除了用解决 QP 问题的常规方法之外，还可以应用拉格朗日对偶性，通过求解对偶问题得到最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。ok， 接下来，你将看到“对偶变量对偶变量 dual variable 的优化问题的优化问题”等类似
24、的关键词频繁出现，便是解决此凸优化问题的第二种更为高效的解-对偶变量的优化求解.至于上述提到，关于什么是 Lagrange duality，简单地来说，通过给每一个约束条件加上一个 Lagrange multiplier(拉格朗日乘值)：，我们可以将约束条件融和到目标函数里去(也就是说把条件融合到一个函数里头，现在只用一个函数表达式便能清楚的表达出我们的问题)：然后我们令容易验证， 当某个约束条件不满足时， 例如yi(wTxi+b)F 是从输入空间到某个特征空间的映射，这意味着建立非线性学习器分为两步：1.首先使用一个非线性映射将数据变换到一个特征空间 F，2.然后在特征空间使用线性学习器分类
25、。在上文我提到过对偶形式，而这个对偶形式就是线性学习器的一个重要性质，这意味着假设可以表达为训练点的线性组合，因此决策规则可以用测试点和训练点的内积来表示：如果有一种方式可以在特征空间中直接计算内积在特征空间中直接计算内积(xi (x)，就像在原始输入点的函数中一样， 就有可能将两个步骤融合到一起建立一个非线性的学习器， 这样直接计算法的这样直接计算法的方法称为核函数方法，方法称为核函数方法，于是，核函数便横空出世了。这里我直接给出一个定义：核是一个函数 K，对所有 x，z(-X，满足，这里是从 X 到内积特征空间 F 的映射。3、总而言之，举个简单直接点的例子，则是如果不是用核技术，就会先计
26、算线性映射phy(x1)和 phy(x2),然后计算这两个特征的内积， 使用了核技术之后， 先把 phy(x1)和 phy(x2)的通用表达式子：=k( )计算出来，注意到这里的表示内积，k( , )就是对应的核函数，这个表达往往非常简单，所以计算非常方便。.OK，接下来，咱们就进一步从外到里，来探探这个核函数的真面目。2.2.1、如何处理非线性数据、如何处理非线性数据在 2.1 节中我们介绍了线性情况下的支持向量机，它通过寻找一个线性的超平面来达到对数据进行分类的目的。不过，由于是线性方法，所以对非线性的数据就没有办法处理了。举个例子来说，则是如下图所示的两类数据，分别分布为两个圆圈的形状，
27、这样的数据本身就是线性不可分的，你准备如何把这两类数据分开呢(下文将会有一个相应的三维空间图)？上图所述的这个数据集，就是用两个半径不同的圆圈加上了少量的噪音生成得到的，所以，一个理想的分界应该是一个“圆圈”而不是一条线（超平面）。如果用X1和X2来表示这个二维平面的两个坐标的话，我们知道一条二次曲线（圆圈是二次曲线的一种特殊情况）的方程可以写作这样的形式：a1X1+a2X21+a3X2+a4X22+a5X1X2+a6=0注意上面的形式，如果我们构造另外一个五维的空间，其中五个坐标的值分别为Z1=X1,Z2=X21,Z3=X2,Z4=X22,Z5=X1X2，那么显然，上面的方程在新的坐标系下可
28、以写作：i=15aiZi+a6=0关于新的坐标Z，这正是一个 hyper plane 的方程！也就是说，如果我们做一个映射:R2R5，将X按照上面的规则映射为Z，那么在新的空间中原来的数据将变成线性可分的，从而使用之前我们推导的线性分类算法就可以进行处理了。这正是 Kernel 方法处理非线性问题的基本思想。2.2.2、特征空间的隐式映射：核函数、特征空间的隐式映射：核函数再进一步描述 Kernel 的细节之前，不妨再来看看这个例子映射过后的直观例子。当然，你我可能无法把 5 维空间画出来，不过由于我这里生成数据的时候就是用了特殊的情形，具体来说，我这里的超平面实际的方程是这个样子（圆心在X2
29、轴上的一个正圆）：a1X21+a2(X2c)2+a3=0因此我只需要把它映射到Z1=X21,Z2=X22,Z3=X2这样一个三维空间中即可，下图即是映射之后的结果，将坐标轴经过适当的旋转，就可以很明显地看出，数据是可以通过一个平面来分开的：现在让我们再回到 SVM 的情形，假设原始的数据时非线性的，我们通过一个映射()将其映射到一个高维空间中，数据变得线性可分了，这个时候，我们就可以使用原来的推导来进行计算，只是所有的推导现在是在新的空间，而不是原始空间中进行。当然，推导过程也并不是可以简单地直接类比的，例如，原本我们要求超平面的法向量w，但是如果映射之后得到的新空间的维度是无穷维的（确实会出
30、现这样的情况，比如后面会提到的高斯核Gaussian Kernel），要表示一个无穷维的向量描述起来就比较麻烦。于是我们不妨先忽略过这些细节，直接从最终的结论来分析，回忆一下，我们上一次上一次 2.1 节节中得到的最终的分类函数是这样的：现在则是在映射过后的空间，即：而其中的也是通过求解如下也是通过求解如下 dual 问题问题而得到的：这样一来问题就解决了吗？似乎是的：拿到非线性数据，就找一个映射，然后一股脑把原来的数据映射到新空间中，再做线性 SVM 即可。不过事实上没有这么简单！其实刚才的方法稍想一下就会发现有问题：在最初的例子里，我们对一个二维空间做映射，选择的新空间是原始空间的所有一阶
31、和二阶的组合，得到了五个维度；如果原始空间是三维，那么我们会得到 19 维的新空间，这个数目是呈爆炸性增长的，这给的计算带来了非常大的困难，而且如果遇到无穷维的情况，就根本无从计算了。所以就需要 Kernel 出马了。不妨还是从最开始的简单例子出发，设两个向量和，而即是到前面 2.2.1 节节说的五维空间的映射，因此映射过后的内积为：（公式说明：上面的这两个推导过程中，所说的前面的五维空间的映射，这里说的前面便是文中 2.2.1 节的所述的映射方式，仔细看下 2.2.1 节的映射规则，再看那第一个推导，其实就是计算 x1，x2 各自的内积，然后相乘相加即可，第二个推导则是直接平方，去掉括号，也
32、很容易推出来）另外，我们又注意到：二者有很多相似的地方，实际上，我们只要把某几个维度线性缩放一下，然后再加上一个常数维度，具体来说，上面这个式子的计算结果实际上和映射之后的内积的结果是相等的。区别在于什么地方呢？1.一个是映射到高维空间中，然后再根据内积的公式进行计算；2.而另一个则直接在原来的低维空间中进行计算直接在原来的低维空间中进行计算， 而不需要显式地写出映射后的结果而不需要显式地写出映射后的结果。（公式说明：上面之中，最后的两个式子，第一个算式，是带内积的完全平方式，可以拆开，然后，通过凑一个得到，第二个算式，也是根据第一个算式凑出来的）回忆刚才提到的映射的维度爆炸，在前一种方法已经
33、无法计算的情况下，后一种方法却依旧能从容处理，甚至是无穷维度的情况也没有问题。我们把这里的计算两个向量在隐式映射过后的空间中的内积的函数叫做核函数的计算两个向量在隐式映射过后的空间中的内积的函数叫做核函数 (KernelFunction) ，例如，在刚才的例子中，我们的核函数为：核函数能简化映射空间中的内积运算简化映射空间中的内积运算刚好“碰巧”的是， 在我们的 SVM 里需要计算的里需要计算的地方数据向量总是以内积的形式出现地方数据向量总是以内积的形式出现的。对比刚才我们上面写出来的式子，现在我们的分分类函数类函数为：其中由如下 dual 问题计算而得：（细心的读者读至此处，对于：“转换成求
34、 maxL(w,b,)后怎么求的值呢？”，可能依然心存疑惑，没关系，我告诉你，在本文文末的参考文献及推荐阅读的条目 9：统计学习方法李航著，中的第 7 章第7.4 节、SMO-序列最小最优化算法的内有提到关于 a 的求解过程，读者有兴趣可以参考之）这样一来计算的问题就算解决了，避开了直接在高维空间中进行计算，而结果却是等价的！当然，因为我们这里的例子非常简单，所以我可以手工构造出对应于的核函数出来，如果对于任意一个映射，想要构造出对应的核函数就很困难了。最理想的情况下，我们希望知道数据的具体形状和分布，从而得到一个刚好可以将数据映射成线性可分的，然后通过这个得出对应的进行内积计算。然而，第二步
35、通常是非常困难甚至完全没法做的。不过，由于第一步也是几乎无法做到，因为对于任意的数据分析其形状找到合适的映射本身就不是什么容易的事情，所以，人们通常都是“胡乱”选择映射的，所以，根本没有必要精确地找出对应于映射的那个核函数，而只需要“胡乱”选择一个核函数即可我们知道它对应了某个映射， 虽然我们不知道这个映射具体是什么。由于我们的计算只需要核函数即可， 所以我们也并不关心也没有必要求出所对应的映射的具体形式。当然，也并不是任意的二元函数都可以作为核函数，所以除非某些特殊的应用中可能会构造一些特殊的核（例如用于文本分析的文本核，注意其实使用了 Kernel 进行计算之后，其实完全可以去掉原始空间是
36、一个向量空间的假设了， 只要核函数支持， 原始数据可以是任意的“对象”比如文本字符串），通常人们会从一些常用的核函数中选择（根据问题和数据的不同，选择不同的参数，实际上就是得到了不同的核函数），例如：多项式核，显然刚才我们举的例子是这里多项式核的一个特例（）。虽然比较麻烦，而且没有必要，不过这个核所对应的映射实际上是可以写出来的，该空间的维度是，其中是原始空间的维度。高斯核，这个核就是最开始提到过的会将原始空间映射为无穷维空间的那个家伙。不过，如果选得很大的话，高次特征上的权重实际上衰减得非常快，所以实际上（数值上近似一下）相当于一个低维的子空间；反过来，如果选得很小，则可以将任意的数据映射为
37、线性可分当然，这并不一定是好事，因为随之而来的可能是非常严重的过拟合问题。不过，总的来说，通过调控参数，高斯核实际上具有相当高的灵活性，也是使用最广泛的核函数之一。下图所示的例子便是把低维线性不可分的数据通过高斯核函数映射到了高维空间：线性核，这实际上就是原始空间中的内积。这个核存在的主要目的是使得“映射后空间中的问题”和“映射前空间中的问题”两者在形式上统一起来了(意思是说，咱们有的时候，写代码，或写公式的时候，只要写个模板或通用表达式，然后再代入不同的核，便可以了，于此，便在形式上统一了起来，不用再分别写一个线性的，和一个非线性的)。OK，下面是本人根据上文内容做的推导(点击查看：大图地址
38、)，读者来信，向我提出了一个问题：In a SVM without using slack variables, if we remove one of the support vectorsfrom the training set, what will happen to the maximal margin? List all thepossibilities and give a sample for each possible situation, i.e., generate a training set,indicate which point is to be removed
39、and clarify the change of the maximal margin.大意是：在没有松弛变量的 svm 中，如果我们移去训练集中的一个支持向量，那最大margin 会怎么变化呢？列举出所有的可能，每种情况给出一个例子。也就是，举出一个训练集，指出移去哪个点，并指明最大 margin 怎么变。解答：你可能会说最终的 maximal margin 会变大，会变小，或不变？但一切依据呢？与其胡乱猜测，不如实际推导.计算.证明！接下来，咱们回顾下上文所有图片截取自上文：maximum margin 就是remove 后(w,b)变了，w 一变，maximum margin 自然也就
40、会变了，至于如何变，请读者继续计算看具体结果。此外，还可以看看这里的分析：http:/www.cs.berkeley.edu/russell/classes/cs194/f11/assignments/a2/a2-solution.pdf。与此同时，读者自会发现到：上文中很大一部分篇幅都是在阐述怎么求及优化这个最大间隔分类超平面，包括后面的下面，就是这两个步骤，第一步：第二步、对求极大如下所示：再到后来，有了核函数，也不过是为了方便对对偶因子的求解自此，你看到，上文中各个知识点是可以联系起来的，没一个步骤也都是一步一步推导下来的。2.3、使用松弛变量处理、使用松弛变量处理 outliers 方
41、法方法在本文第一节最开始讨论支持向量机的时候，我们就假定，数据是线性可分的，亦即我们可以找到一个可行的超平面将数据完全分开。后来为了处理非线性数据，在上文 2.2 节使用 Kernel 方法对原来的线性 SVM 进行了推广，使得非线性的的情况也能处理。虽然通过映射将原始数据映射到高维空间之后，能够线性分隔的概率大大增加，但是对于某些情况还是很难处理。 例如可能并不是因为数据本身是非线性结构的， 而只是因为数据有噪音。对于这种偏离正常位置很远的数据点，我们称之为 outlier ，在我们原来的 SVM 模型里，outlier 的存在有可能造成很大的影响，因为超平面本身就是只有少数几个 suppo
42、rtvector 组成的，如果这些 support vector 里又存在 outlier 的话，其影响就很大了。例如下图：用黑圈圈起来的那个蓝点是一个 outlier ，它偏离了自己原本所应该在的那个半空间，如果直接忽略掉它的话，原来的分隔超平面还是挺好的，但是由于这个 outlier 的出现，导致分隔超平面不得不被挤歪了，变成途中黑色虚线所示（这只是一个示意图，并没有严格计算精确坐标），同时 margin 也相应变小了。当然，更严重的情况是，如果这个 outlier 再往右上移动一些距离的话，我们将无法构造出能将数据分开的超平面来。为了处理这种情况，SVM 允许数据点在一定程度上偏离一下超
43、平面。例如上图中，黑色实线所对应的距离，就是该 outlier 偏离的距离，如果把它移动回来，就刚好落在原来的超平面上，而不会使得超平面发生变形了。具体来说，原来的约束条件现在变成其中称为松弛变量 (slack variable) ， 对应数据点允许偏离的 functional margin的量。当然，如果我们运行任意大的话，那任意的超平面都是符合条件的了。所以，我们在原来的目标函数后面加上一项，使得这些的总和也要最小：其中是一个参数，用于控制目标函数中两项（“寻找 margin 最大的超平面”和“保证数据点偏差量最小”）之间的权重。注意，其中是需要优化的变量（之一），而是一个事先确定好的常量
44、。完整地写出来是这个样子：用之前的方法将限制或约束条件加入到目标函数中，得到新的拉格朗日函数，如下所示：分析方法和前面一样，转换为另一个问题之后，我们先让针对、和最小化：将带回并化简，得到和原来一样的目标函数：不过，由于我们得到，而又有（作为 Lagrange multiplier 的条件），因此有，所以整个 dual 问题现在写作：和之前的结果对比一下，可以看到唯一的区别就是现在 dual variable多了一个上限。而 Kernel 化的非线性形式也是一样的，只要把换成即可。这样一来，一个完整的，可以处理线性和非线性并能容忍噪音和 outliers 的支持向量机才终于介绍完毕了。更多，请
45、参考 pluskid 的此支持向量机系列。2.4、小结、小结综上所述，对于一个线性可分的两类问题，我们可以通过 g(x)=wT*x+w0=0 确定一个分类面把这两类分开。 我们的目的是为了建立一个这样的分类面， 事实上这样的分类面不是唯一确定的。 在感知器里我们通过梯度下降法优化出一个分类器初始值的选择、 迭代步长等的不同得到的分类器也不同。那么我们需要在这些分离器里找一个最好的。如图所示，我们可以认为 direction2 的分类效果要比direction1 的分类效果要好，因为direction2 的裕量比 direction1 大。我们需要在这各个分类器中选择一个最优的。SVM 是根据统
46、计学习理论依照结构风险最小化的原则提出的，要求实现两个目的：1）两类问题能够分开（经验风险最小）2）margin 最大化（风险上界最小）既是在保证风险最小的子集中选择经验风险最小的函数。把样本到分类面的距离进行归一化处理后我们得到里分类面最近的样本 g(x) = 1。这样我们就有边界 margin：， 这里满足这样条件的样本点就是我们所谓的支持向量。这样我们就转化为一个优化问题 Sergios Theodoridis：建立拉格朗日方程并引入 KKT 条件得到：由上式得到判别函数式：对于不是线性可分的问题，我们可以通过加入松弛子 C 来解决：由以上讨论我们得到判别函数只与向量的內积有关，因此我们
47、可以选择一个非线性变换将 x 映射到高维空间，在低维空间不可分的问题映射到高维空间后就有可能是线性可分的。这里我们不需要知道是什么形式的只需要关注內积运算即可。 由此， 可以通过构造核函数实现：这里的核函数的选择没有特别的方式，在 Chih-Wei Hsu 中推荐使用径向基函数。OK，理解到这第二层，已经能满足绝大部分人一窥 SVM 原理的好奇心，然对于那些想在证明层面理解 SVM 的则还很不够，但进入第三层理解境界之前，你必须要有比较好的数理基础和逻辑证明能力，不然你会跟我一样，吃不少苦头的。第三层、证明第三层、证明 SVM说实话，凡是涉及到要证明的东西.理论，便一般不是怎么好惹的东西。绝大
48、部分时候，看懂一个东西不难，但证明一个东西则需要点数学功底，进一步，证明一个东西也不是特别难，难的是从零开始发明创造这个东西的时候，则显艰难(因为任何时代，大部分人的研究所得都不过是基于前人的研究成果，前人所做的是开创性工作，而这往往是最艰难最有价值的，他们被称为真正的先驱。牛顿也曾说过，他不过是站在巨人的肩上。你，我则更是如此)。正如陈希孺院士在他的著作数理统计学简史的第 4 章、最小二乘法中所讲：在科研上诸多观念的革新和突破是有着很多的不易的，或许某个定理在某个时期由某个人点破了，现在的我们看来一切都是理所当然， 但在一切没有发现之前， 可能许许多多的顶级学者毕其功于一役，耗尽一生，努力了
49、几十年最终也是无功而返。OK， 以下内容基本属于自己在看支持向量机导论一书的理解， 包括自己对一些证明的理解，还是读书笔记。本部分导述本部分导述3.1 节线性学习器一部分中，主要阐述 3 个东西，感知机算法，松弛变量，及最小二乘理论，同时，基本上是贴的用相机拍的照片（为什么？懒）；3.2 节、核函数特征空间；3.3 节、SMO 算法；3.4 节、简略谈谈 SVM 的应用。3.1、线性学习器、线性学习器3.1.1、感知机算法、感知机算法这个感知机算法是 1956 年提出的，年代久远，依然影响着当今，当然，可以肯定的是，此算法亦非最优，后续会有更详尽阐述。不过，有一点，你必须清楚，这个算法是为了干
50、嘛的：不断的训练试错以期寻找一个合适的超平面(是的，就这么简单)。下图算是读书笔记，若看不清，可以点击查看：大图（后面一大堆的证明不过是为了证明上述感知机算法在线性条件下收敛，说白了，为了得到一个界，不至于无穷循环下去）。3.1.2、松弛变量、松弛变量（点击查看大图：左图，右图）针对上面左图的说明：我们知道，当分类出现了误差，要么就是被误分，要么就是没有以正常的间隔被分开：被误分。如上面左图所示，如果一切正常的话，那么 xi 出现的位置不该是那里，而是该左图中左边那个箭头所示，被“拉回去”，而既然出现在了这个不正常的位置，那么有什么后果内，这就导致了所谓的被误分，使得最终的松弛变量0；同理，o
