支持向量机通俗导论（理解SVM的三层境界）带完整书签版本.docx

《支持向量机通俗导论（理解SVM的三层境界）带完整书签版本.docx》由会员分享，可在线阅读，更多相关《支持向量机通俗导论（理解SVM的三层境界）带完整书签版本.docx（64页珍藏版）》请在第一文库网上搜索。

1、支持向量机通俗导论（理解SVM的三层境界）作者：Ju1y、p1uskid致谢：白石、JerTy1ead本PDF制作者：吴新隆联系作者：http:/Wiuvweibo出处：http:二零一三年十二月六日于天通苑-AZ-I-刖S动笔写这个支持向量机（SUPPortVeCtOrmaChine）是费了不少劲和困难的，原因很简单，一者这个东西本身就并不好懂，要深入学习和研究下去需花费不少时间和精力，二者这个东西也不好讲清楚，尽管网上已经有朋友写得不错了（见文末参考链接），但在描述数学公式的时候还是显得不够。得益于同学白石的数学证明，我还是想尝试写一下，希望本文在兼顾通俗易懂的基础上，真真正正能足以成为一

2、篇完整概括和介绍支持向量机的导论性的文章。本文在写的过程中，参考了不少资料，包括支持向量机导论、统计学习方法及网友PIUSkid的支持向量机系列等等，于此，还是一篇学习笔记，只是加入了自己的理解和总结，有任何不妥之处，还望海涵。全文宏观上整体认识支持向量机的概念和用处，微观上深究部分定理的来龙去脉，证明及原理细节，力求逻辑清晰&通俗易懂。同时，阅读本文时建议大家尽量使用ChrOme等浏览器，如此公式才能更好的显示，再者，阅读时可拿张纸和笔出来，把本文所有定理.公式都亲自推导一遍或者直接打印下来（可直接打印网页版或本PDF,享受随时随地思考、演算的极致快感），在文稿上演算。0k,还是那句原话，有

3、任何问题，欢迎任何人随时不吝指正&赐教，感谢。第一层、了解SVM1.0、什么是支持向量机SVM要明白什么是SVM,便得从分类说起。分类作为数据挖掘领域中一项非常重要的任务，它的目的是学会一个分类函数或分类模型（或者叫做分类器），而支持向量机本身便是一种监督式学习的方法（至于具体什么是监督学习与非监督学习，请参见此系列MaChine1&DataMininH第一篇），它广泛的应用于统计分类以及回归分析中。支持向量机（SVM）是90年代中期发展起来的基于统计学习理论的一种机器学习方法，通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获

4、得良好统计规律的目的。通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，即支持向量机的学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。对于不想深究SVM原理的同学或比如就只想看看SVM是干嘛的，那么，了解到这里便足够了，不需上层。而对于那些喜欢深入研究一个东西的同学，甚至究其本质的，咱们则还有很长的一段路要走，万里长征，咱们开始迈第一步吧，相信你能走完。1.1、 线性分类OK,在讲SVM之前，咱们必须先弄清楚一个概念：线性分类器（也可以叫做感知机，这里的机表示的是一种算法，本文第三部分、证明SVM中会详细阐述）。1.1.1 ,分类标准这里我们考虑的

5、是一个两类的分类问题，数据点用X来表示，这是一个n维向量，WAT中的T代表转置，而类别用y来表示，可以取1或者-1,分别代表两个不同的类。一个线性分类器的学习目标就是要在n维的数据空间中找到一个分类超壬面，其方程可以表示为：WTX&=0上面给出了线性分类的定义描述，但或许读者没有想过：为何用y取1或者来表示两个不同的类别呢？其实，这个1或-1的分类标准起源于1ogistic回归，为了完整和过渡的自然性，咱们就再来看看这个1ogistic回归。1.1.2 1或1分类标准的起源：1ogistic回归1ogistic回归目的是从特征学习出一个0/1分类模型，而这个模型是将特性的线性组合作为自变量，由

6、于自变量的取值范围是负无穷到正无穷。因此，使用1ogistic函数（或称作Sigmoid函数）将自变量映射到（U）上，映射后的值被认为是属于y=1的概率。形式化表示就是假设函数儿(工)=g(9r)=jr；其中X是n维特征向量，函数g就是IogiStiC函数。g(z)=而的图像是可以看到，将无穷映射到了。1）。而假设函数就是特征属于y=1的概率。加(N)1-h(x)P(y=11工;。)P(y=O1笈;夕)当我们要判别一个新来的特征属于哪个类时，只需求，若大于0.5就是户1的类，反之属于Y=O类。再审视一下1，发现只蜘(喃关,4),那2r,g(z)*-dS只不过是用来映射，真实的类别决定权还在。馅

7、！当时=1,M)反之h-=o0如果我们只从尹N出发，希望模型达到的目标无非就是让训练数据中y=1的特征剂力猊的，而是y=0的特征1ogistic回归就是要学习得到。，使得正例的特征远大于0,负例的特征远小于0,强调在全部训练实例上达到这个目标。1.1.3 、形式化标示我们这次使用的结果标签是y=-i,y=1,替换在1ogistic回归中使用的y二o和y=i。同时将替换成W和b。以前的夕=瓦+配&十九&+6X,其中认为匕=1。现在我们替换为b,后面替换心工+6一心+8.(为WI+w凡+wx(即W/X)。这样，我们让=3&Mh,进一步fcX)=n(x)=fw+11也就是说除TV由y=0变为y=-1

8、,只是标记不同外，与1ogistic回归的形式化表示没区别。再明确下假设函数KX)(wrb)上面提到过我们只需考虑严酌正负问题，而不用关心g(z),因此我们这里将g(z)做一个简化，将其简单映射到y=-1和y=1上。映射关系如下：，一一I1z0虱01-1z0于此，想必已经解释明白了为何线性分类的标准一般用1或者；来标示。注：上小节来自jerry1ead所作的斯坦福机器学习课程的笔记。1.2、线性分类的一个例子下面举个简单的例子，一个二维平面(一个超平面，在二维空间中的例子就是一条直线)，如下图所示，平面上有两种不同的点，分别用两种不同的颜色表示，一种为红颜色的点，另一种则为蓝颜色的点，红颜色的

9、线表示一个可行的超平面。从上图中我们可以看出，这条红颜色的线把红颜色的点和蓝颜色的点分开来To而这条红颜色的线就是我们上面所说的超平面，也就是说，这个所谓的超平面的的确确便把这两种不同颜色的数据点分隔开来，在超平面一边的数据点所对应的y全是-1,而在另一边全是1。接着，我们可以令分类函数(提醒：下文很大篇幅都在讨论着这个分类函数)：f(x)=wrz显然，如果f(x)=0,那么X是位于超平面上的点。我们不妨要求对于所有满足f()O则对应y=1的数据点。注：上图中，定义特征到结果的输出函数U=、一”与我们之前定义的z1w工+b实质是一样的。为什么？因为无论是U=wx-b/w1xbf不影响最终优化结

10、果。卜文你将看到，当我们转化到优化max,s.t.,yi(wxi+b)1,i=1,.,n的时候，为了求解方便，会把yf(x)令为1,即yf(x)已无影响是y(wx+b),还是y(wx-b),对我们要优化的式fmax1w(有一朋友飞狗来自MarjDesiderii,看了上面的定义之后，问道：请教一下SVMfUnCtiOna1margin为7=y(wTx+b)=yf(x)中的Y是只取1和-1吗？y的唯一作用就是确保functiona1margin的非负性？真是这样的么？当然不是，详情请见本文评论下第43楼)当然，有些时候，或者说大部分时候数据并不是线性可分的，这个时候满足这样条件的超平面就根本不存

11、在(不过关于如何处理这样的问题我们后面会讲)，这里先从最简单的情形开始推导，就假设数据都是线性可分的，亦即这样的超平面是存在的。更进一步，我们在进行分类的时候，将数据点X代入f(x)中，如果得到的结果小于0,则赋予其类别-1,如果大于0则赋予类别1。如果f(x)=O,则很难办了，分到哪一类都不是。请读者注意，下面的篇幅将按下述3点走：1 .咱们就要确定上述分类函数f(x)=w.x+b(w.x表示W与X的内积)中的两个参数W和b,通俗理解的话W是法向量，b是截距(再次说明：定义特征到结果的输出函数U=WX-b,与我们最开始定义的/(1)=W7+6实质是一样的)；2 .那如何确定W和b呢？答案是寻

12、找两条边界端或极端划分直线中间的最大间隔(之所以要寻最大间隔是为了能更好的划分不同类的点，下文你将看到：为寻最大间隔，导出12wa2,继而引入拉格朗日函数和对偶变量,化为对单一因数对偶变量的求解，当然，这是后话)，从而确定最终的最大间隔分类超平面hyperp1ane和分类函数；3 .进而把寻求分类函数f(x)=w.x+b的问题转化为对w,b的最优化问题，最终化为对偶因子的求解。总结成一句话即是：从最大间隔出发(目的本就是为了确定法向量w),转化为求对变量W和b的凸二次规划问题。亦或如下图所示(有点需要注意，如读者酱爆小八爪所说：从最大分类间隔开始，就一直是凸优化问题)：*究者JU1y“(P1为

13、SI定分谢V(X)=WX冲的雪敷w),于是再找最大分类间隔，导出12wr2,继而引入拉格朗日由静，化为对单一因子对偶变量a的求解，如此，求wZ求博价，而求a的解法即为SMO。把求分类期V(XmD的词#将化到求最大分类间冽，继而再转化为对M曲优化问题，即凸二;欠奴创问题，妙阴4日120东自AgoH|前6)I幢发收w(7)1.3、 函数间隔FUnCtiOnQ1margin呵几何间隔GeOmetriCa1margin一般而言，一个点距离超平面的远近可以表示为分类预测的确信或准确程度。在超平面w*x+b=0确定的情况下，w*x+b能够相对的表示点X到距离超平面的远近，而w*x+b的符号与类标记y的符号

14、是否一致表示分类是否正确，所以，可以用量y*(w*x+b)的正负性来判定或表示分类的正确性和确信度。于此，我们便引出了定义样本到分类间隔距离的函数间隔functiona1margin的概念。1.3.1s函数间隔Functiona1margin我们定义函数间隔functiona1margin为:7=y(wx+b)=yf(x)接着，我们定义超平面(w,b)关于训练数据集T的函数间隔为超平面(w,b)关于T中所有样本点(xi,yi)的函数间隔最小值，其中，X是特征，y是结果标签，i表示第i个样本，有：-min，i(i=1,.n)然与此同时.，问题就出来了。上述定义的函数间隔虽然可以表示分类预测的正确

15、性和确信度，但在选择分类超平面时，只有函数间隔还远远不够，因为如果成比例的改变w和b,如将他们改变为2w和2b,虽然此时超平面没有改变，但函数间隔的值f(x)却变成了原来的2倍。其实，我们可以对法向量w加些约束条件，使其表面上看起来规范化，如此，我们很快又将引出真正定义点到超平面的距离-几何间隔geometrica1margin的概念(很快你将看到，几何间隔就是函数间隔除以个I1W1即yf(x)/IwI)o1.3.2、点到超平面的距离定义：几何间隔GeorneIriCa1rnargin在给出几何间隔的定义之前，咱们首先来看下，如上图所示，对于一个点X,令其垂直投影到超平面上的对应的为x,由于W是垂直于超平面的一个向量，7为样本X到分类间隔的距离，我们有1w1(I1WI1表示的是范数，关于范数的概念参见这里)又由于XO是超平面上的点，满足f(xO)=O,代入超平面的方程即可算出：w1x