《2022年SVM算法知识入门【详解】 .pdf》由会员分享，可在线阅读，更多相关《2022年SVM算法知识入门【详解】 .pdf（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、SVM 算法知识入门【详解】本文转载自网络（一） SVM 的简介支持向量机 (Support Vector Machine) 是 Cortes 和 Vapnik 于 1995 年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中10。支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力14（或称泛化能力）。以上是经常被有关SVM 的学术文献引用的
2、介绍，我来逐一分解并解释一下。Vapnik 是统计机器学习的大牛，这想必都不用说，他出版的Statistical Learning Theory是一本完整阐述统计机器学习思想的名著。在该书中详细的论证了统计机器学习之所以区别于传统机器学习的本质，就在于统计机器学习能够精确的给出学习效果，能够解答需要的样本数等等一系列问题。与统计机器学习的精密思维相比，传统的机器学习基本上属于摸着石头过河，用传统的机器学习方法构造分类系统完全成了一种技巧，一个人做的结果可能很好，另一个人差不多的方法做出来却很差，缺乏指导和原则。所谓 VC维是对函数类的一种度量，可以简单的理解为问题的复杂程度，VC维越高， 一个
3、问题就越复杂。正是因为SVM 关注的是 VC 维，后面我们可以看到，SVM解决问题的时候，和样本的维数是无关的（甚至样本是上万维的都可以，这使得SVM 很适合用来解决文本分类的问题，当然，有这样的能力也因为引入了核函数）。结构风险最小听上去文绉绉，其实说的也无非是下面这回事。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 33 页 - - - - - - - - - - 机器学习本质上就是一种对问题真实模型的逼近（我们选择一个我们认为比较好的近似模型，这个近似模型就叫做一个假设），但毫无疑问，
4、真实模型一定是不知道的（如果知道了，我们干吗还要机器学习？直接用真实模型解决问题不就可以了？对吧，哈哈） 既然真实模型不知道， 那么我们选择的假设与问题真实解之间究竟有多大差距，我们就没法得知。比如说我们认为宇宙诞生于150 亿年前的一场大爆炸，这个假设能够描述很多我们观察到的现象，但它与真实的宇宙模型之间还相差多少？谁也说不清，因为我们压根就不知道真实的宇宙模型到底是什么。这个与问题真实解之间的误差，就叫做风险（更严格的说，误差的累积叫做风险）。我们选择了一个假设之后（更直观点说，我们得到了一个分类器以后），真实误差无从得知，但我们可以用某些可以掌握的量来逼近它。最直观的想法就是使用分类器在
5、样本数据上的分类的结果与真实结果 （因为样本是已经标注过的数据，是准确的数据） 之间的差值来表示。这个差值叫做经验风险Remp(w)。以前的机器学习方法都把经验风险最小化作为努力的目标，但后来发现很多分类函数能够在样本集上轻易达到100%的正确率，在真实分类时却一塌糊涂（即所谓的推广能力差，或泛化能力差）。此时的情况便是选择了一个足够复杂的分类函数（它的 VC维很高），能够精确的记住每一个样本，但对样本之外的数据一律分类错误。回头看看经验风险最小化原则我们就会发现，此原则适用的大前提是经验风险要确实能够逼近真实风险才行（行话叫一致），但实际上能逼近么？答案是不能，因为样本数相对于现实世界要分类
6、的文本数来说简直九牛一毛，经验风险最小化原则只在这占很小比例的样本上做到没有误差，当然不能保证在更大比例的真实文本上也没有误差。统计学习因此而引入了泛化误差界的概念，就是指真实风险应该由两部分内容刻画，一是经验风险， 代表了分类器在给定样本上的误差；二是置信风险， 代表了我们在多大程度上可以信任分类器在未知文本上分类的结果。很显然， 第二部分是没有办法精确计算的，因此只能给出一个估计的区间，也使得整个误差只能计算上界，而无法计算准确的值（所以叫做泛化误差界，而不叫泛化误差）。置信风险与两个量有关，一是样本数量， 显然给定的样本数量越大，我们的学习结果越有可能正确，此时置信风险越小；二是分类函数
7、的VC维，显然VC维越大，推广能力越差，置信风险会变大。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 33 页 - - - - - - - - - - 泛化误差界的公式为：R(w) Remp(w)+ (n/h)公式中 R(w)就是真实风险，Remp(w)就是经验风险，(n/h)就是置信风险。统计学习的目标从经验风险最小化变为了寻求经验风险与置信风险的和最小，即结构风险最小。SVM 正是这样一种努力最小化结构风险的算法。SVM 其他的特点就比较容易理解了。小样本，并不是说样本的绝对数量少（实际
8、上，对任何算法来说，更多的样本几乎总是能带来更好的效果） ，而是说与问题的复杂度比起来，SVM 算法要求的样本数是相对比较少的。非线性，是指SVM 擅长应付样本数据线性不可分的情况，主要通过松弛变量（也有人叫惩罚变量）和核函数技术来实现，这一部分是SVM 的精髓，以后会详细讨论。多说一句，关于文本分类这个问题究竟是不是线性可分的，尚没有定论， 因此不能简单的认为它是线性可分的而作简化处理，在水落石出之前，只好先当它是线性不可分的（反正线性可分也不过是线性不可分的一种特例而已，我们向来不怕方法过于通用）。高维模式识别是指样本维数很高，例如文本的向量表示，如果没有经过另一系列文章（文本分类入门 ）
9、中提到过的降维处理，出现几万维的情况很正常，其他算法基本就没有能力应付了， SVM却可以，主要是因为SVM 产生的分类器很简洁，用到的样本信息很少（仅仅用到那些称之为“ 支持向量 ” 的样本，此为后话） ，使得即使样本维数很高，也不会给存储和计算带来大麻烦 （相对照而言，kNN 算法在分类时就要用到所有样本，样本数巨大，每个样本维数再一高，这日子就没法过了 ） 。下一节开始正式讨论SVM。别嫌我说得太详细哦。SVM 入门（二）线性分类器Part 1精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共
10、 33 页 - - - - - - - - - - 线性分类器 (一定意义上 ,也可以叫做感知机) 是最简单也很有效的分类器形式.在一个线性分类器中 ,可以看到SVM形成的思路 ,并接触很多 SVM 的核心概念 .用一个二维空间里仅有两类样本的分类问题来举个小例子。如图所示C1和 C2是要区分的两个类别，在二维平面中它们的样本如上图所示。中间的直线就是一个分类函数， 它可以将两类样本完全分开。一般的， 如果一个线性函数能够将样本完全正确的分开，就称这些数据是线性可分的，否则称为非线性可分的。什么叫线性函数呢？在一维空间里就是一个点，在二维空间里就是一条直线，三维空间里就是一个平面， 可以如此想
11、象下去，如果不关注空间的维数，这种线性函数还有一个统一的名称超平面（ Hyper Plane） ！实际上， 一个线性函数是一个实值函数（即函数的值是连续的实数）， 而我们的分类问题 （例如这里的二元分类问题回答一个样本属于还是不属于一个类别的问题）需要离散的输出值，例如用1 表示某个样本属于类别C1，而用 0 表示不属于（不属于C1也就意味着属于C2） ，这时候只需要简单的在实值函数的基础上附加一个阈值即可，通过分类函数执行时得到的值大于还是小于这个阈值来确定类别归属。例如我们有一个线性函数g(x)=wx+b【看到好多人都在问g(x)=0 和 g(x)的问题，我在这里帮楼主补充一下：g(x)实
12、际是以 w 为法向量的一簇超平面，在二维空间表示为一簇直线（就是一簇平行线，他们的法向量都是w） ，而 g(x)=0 只是这么多平行线中的一条。】精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 33 页 - - - - - - - - - - 我们可以取阈值为0， 这样当有一个样本xi 需要判别的时候， 我们就看g(xi)的值。若 g(xi)0，就判别为类别C1，若 g(xi)0（记得么？这是因为我们所选的g(x)=wx+b 就通过大于0 还是小于0 来判断分类），而 yi 也大于 0；若不属
13、于该类别的话，那么 wxi+b0，而 yi 也小于 0，这意味着yi(wxi+b)总是大于0 的，而且它的值就等于|wxi+b| ！（也就是 |g(xi)| ）现在把 w 和 b 进行一下归一化，即用 w/|w|和 b/|w|分别代替原来的w 和 b，那么间隔就可以写成【点到直线的距离，做解析几何中为：D = (Ax + By + c) /sqrt(A2+B2)sqrt(A2+B2) 就相当于 |W|, 其中向量 W=A, B;(Ax + By + c) 就相当于 g(X), 其中向量 X=x,y。 】这个公式是不是看上去有点眼熟？没错，这不就是解析几何中点xi 到直线 g(x)=0 的距离公
14、式嘛！（推广一下，是到超平面g(x)=0 的距离，g(x)=0 就是上节中提到的分类超平面）小 Tips：|w|是什么符号？ |w|叫做向量 w 的范数，范数是对向量长度的一种度量。我们常说的向量长度其实指的是它的2-范数，范数最一般的表示形式为p-范数，可以写成如下表达式精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 33 页 - - - - - - - - - - 向量 w=(w1, w2, w3, wn)它的 p-范数为看看把 p 换成 2 的时候，不就是传统的向量长度么？当我们不指明p
15、 的时候，就像 |w|这样使用时， 就意味着我们不关心p 的值， 用几范数都可以；或者上文已经提到了p 的值， 为了叙述方便不再重复指明。当用归一化的w 和 b 代替原值之后的间隔有一个专门的名称，叫做几何间隔，几何间隔所表示的正是点到超平面的欧氏距离，我们下面就简称几何间隔为“ 距离 ” 。以上是单个点到某个超平面的距离 （就是间隔， 后面不再区别这两个词）定义，同样可以定义一个点的集合（就是一组样本） 到某个超平面的距离为此集合中离超平面最近的点的距离。下面这张图更加直观的展示出了几何间隔的现实含义：H 是分类面，而H1 和 H2 是平行于 H，且过离 H 最近的两类样本的直线，H1 与
16、H，H2 与 H之间的距离就是几何间隔。之所以如此关心几何间隔这个东西，是因为几何间隔与样本的误分次数间存在关系：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 33 页 - - - - - - - - - - 其中的 是样本集合到分类面的间隔，R=max |xi|i=1,.,n，即 R是所有样本中（xi 是以向量表示的第i 个样本）向量长度最长的值（也就是说代表样本的分布有多么广）。先不必追究误分次数的具体定义和推导过程，只要记得这个误分次数一定程度上代表分类器的误差。而从上式可以看出，误分
17、次数的上界由几何间隔决定！（当然，是样本已知的时候）至此我们就明白为何要选择几何间隔来作为评价一个解优劣的指标了，原来几何间隔越大的解，它的误差上界越小。因此最大化几何间隔成了我们训练阶段的目标，而且，与二把刀作者所写的不同， 最大化分类间隔并不是SVM的专利，而是早在线性分类时期就已有的思想。SVM 入门（四）线性分类器的求解问题的描述Part1上节说到我们有了一个线性分类函数，也有了判断解优劣的标准即有了优化的目标，这个目标就是最大化几何间隔，但是看过一些关于SVM的论文的人一定记得什么优化的目标是要最小化 |w|这样的说法，这是怎么回事呢？回头再看看我们对间隔和几何间隔的定义：间隔： =
18、y(wx+b)=|g(x)|几何间隔：可以看出 =|w| 几何。注意到几何间隔与|w|是成反比的，因此最大化几何间隔与最小化 |w|完全是一回事。而我们常用的方法并不是固定|w|的大小而寻求最大几何间隔，而是固定间隔（例如固定为1） ，寻找最小的 |w|。而凡是求一个函数的最小值（或最大值）的问题都可以称为寻优问题（也叫作一个规划问题），又由于找最大值的问题总可以通过加一个负号变为找最小值的问题，因此我们下面讨论的时候都针对找最小值的过程来进行。一个寻优问题最重要的部分是目标函数，顾名思义， 就是指寻优的目标。例如我们想寻找最小的|w|这件事，就可以用下面的式子表示：精品资料 - - - 欢迎
19、下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 33 页 - - - - - - - - - - 但实际上对于这个目标，我们常常使用另一个完全等价的目标函数来代替，那就是：(式 1)不难看出当 |w|2达到最小时， |w|也达到最小，反之亦然（前提当然是|w|描述的是向量的长度，因而是非负的）。之所以采用这种形式，是因为后面的求解过程会对目标函数作一系列变换，而式（1）的形式会使变换后的形式更为简洁（正如聪明的读者所料，添加的系数二分之一和平方，皆是为求导数所需）。接下来我们自然会问的就是，这个式子是否就描述了我们的问
20、题呢？（回想一下， 我们的问题是有一堆点，可以被分成两类，我们要找出最好的分类面）如果直接来解这个求最小值问题，很容易看出当 |w|=0的时候就得到了目标函数的最小值。但是你也会发现，无论你给什么样的数据，都是这个解！反映在图中，就是H1 与 H2 两条直线间的距离无限大，这个时候，所有的样本点（无论正样本还是负样本）都跑到了H1 和H2 中间，而我们原本的意图是，H1 右侧的被分为正类，H2 左侧的被分为负类，位于两类中间的样本则拒绝分类（拒绝分类的另一种理解是分给哪一类都有道理，因而分给哪一类也都没有道理） 。这下可好，所有样本点都进入了无法分类的灰色地带。精品资料 - - - 欢迎下载
21、- - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 33 页 - - - - - - - - - - 造成这种结果的原因是在描述问题的时候只考虑了目标，而没有加入约束条件，约束条件就是在求解过程中必须满足的条件，体现在我们的问题中就是样本点必须在H1 或 H2 的某一侧（或者至少在H1 和 H2 上） ，而不能跑到两者中间。我们前文提到过把间隔固定为1，这是指把所有样本点中间隔最小的那一点的间隔定为1 （这也是集合的间隔的定义，有点绕嘴），也就意味着集合中的其他点间隔都不会小于1，按照间隔的定义，满足这些条件就相当于让下面的式子
22、总是成立：yi(wxi)+b1 (i=1,2, ,l) （l 是总的样本数）但我们常常习惯让式子的值和0 比较，因而经常用变换过的形式：yi(wxi)+b-10 (i=1,2,l) （l 是总的样本数）因此我们的两类分类问题也被我们转化成了它的数学形式，一个带约束的最小值的问题：下一节我们从最一般的意义上看看一个求最小值的问题有何特征，以及如何来解。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 33 页 - - - - - - - - - - SVM 入门（五）线性分类器的求解问题的描述P
23、art2从最一般的定义上说，一个求最小值的问题就是一个优化问题（也叫寻优问题，更文绉绉的叫法是规划 Programming） ，它同样由两部分组成，目标函数和约束条件，可以用下面的式子表示：（式 1）约束条件用函数c来表示，就是constrain 的意思啦。你可以看出一共有p+q 个约束条件，其中 p 个是不等式约束，q 个等式约束。关于这个式子可以这样来理解：式中的x 是自变量，但不限定它的维数必须为1（视乎你解决的问题空间维数，对我们的文本分类来说，那可是成千上万啊）。要求 f(x)在哪一点上取得最小值 （反倒不太关心这个最小值到底是多少，关键是哪一点） ， 但不是在整个空间里找，而是在约
24、束条件所划定的一个有限的空间里找，这个有限的空间就是优化理论里所说的可行域。注意可行域中的每一个点都要求满足所有p+q 个条件， 而不是满足其中一条或几条就可以（切记，要满足每个约束），同时可行域边界上的点有一个额外好的特性，它们可以使不等式约束取得等号！而边界内的点不行。关于可行域还有个概念不得不提，那就是凸集， 凸集是指有这么一个点的集合，其中任取两个点连一条直线， 这条线上的点仍然在这个集合内部，因此说 “ 凸” 是很形象的 （一个反例是，二维平面上， 一个月牙形的区域就不是凸集，你随便就可以找到两个点违反了刚才的规定）。回头再来看我们线性分类器问题的描述，可以看出更多的东西。（式 2）
25、在这个问题中，自变量就是w，而目标函数是w 的二次函数，所有的约束条件都是w 的线性函数（哎，千万不要把xi 当成变量，它代表样本，是已知的），这种规划问题有个很有名精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 11 页，共 33 页 - - - - - - - - - - 气的称呼 二次规划（ Quadratic Programming ，QP） ，而且可以更进一步的说，由于它的可行域是一个凸集，因此它是一个凸二次规划。一下子提了这么多术语，实在不是为了让大家以后能向别人炫耀学识的渊博，这其实是我们继
26、续下去的一个重要前提，因为在动手求一个问题的解之前（好吧，我承认，是动计算机求 ） ，我们必须先问自己：这个问题是不是有解？如果有解，是否能找到？对于一般意义上的规划问题，两个问题的答案都是不一定，但凸二次规划让人喜欢的地方就在于，它有解（教科书里面为了严谨，常常加限定成分，说它有全局最优解，由于我们想找的本来就是全局最优的解，所以不加也罢） ， 而且可以找到！（当然，依据你使用的算法不同，找到这个解的速度，行话叫收敛速度，会有所不同）对比（式 2）和（式1）还可以发现，我们的线性分类器问题只有不等式约束，因此形式上看似乎比一般意义上的规划问题要简单，但解起来却并非如此。因为我们实际上并不知道
27、该怎么解一个带约束的优化问题。如果你仔细回忆一下高等数学的知识，会记得我们可以轻松的解一个不带任何约束的优化问题（实际上就是当年背得烂熟的函数求极值嘛，求导再找0 点呗，谁不会啊？笑） ，我们甚至还会解一个只带等式约束的优化问题，也是背得烂熟的，求条件极值，记得么，通过添加拉格朗日乘子，构造拉格朗日函数，来把这个问题转化为无约束的优化问题云云（如果你一时没想通，我提醒一下，构造出的拉格朗日函数就是转化之后的问题形式，它显然没有带任何条件）。读者问： 如果只带等式约束的问题可以转化为无约束的问题而得以求解，那么可不可以把带不等式约束的问题向只带等式约束的问题转化一下而得以求解呢？聪明，可以，实际
28、上我们也正是这么做的。下一节就来说说如何做这个转化，一旦转化完成，求解对任何学过高等数学的人来说，都是小菜一碟啦。SVM 入门（六）线性分类器的求解问题的转化，直观角度精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 12 页，共 33 页 - - - - - - - - - - 让我再一次比较完整的重复一下我们要解决的问题：我们有属于两个类别的样本点（并不限定这些点在二维空间中）若干，如图，圆形的样本点定为正样本（连带着，我们可以把正样本所属的类叫做正类），方形的点定为负例。我们想求得这样一个线性函数（在
29、n 维空间中的线性函数） ：g(x)=wx+b使得所有属于正类的点+代入以后有g(x+) 1，而所有属于负类的点x-代入后有g(x-) -1（之所以总跟1 比较，无论正一还是负一，都是因为我们固定了间隔为1，注意间隔和几何间隔的区别） 。代入 g(x)后的值如果在1 和-1 之间，我们就拒绝判断。求这样的 g(x)的过程就是求w（一个 n 维向量）和b（一个实数）两个参数的过程（但实际上只需要求w，求得以后找某些样本点代入就可以求得b） 。因此在求g(x)的时候， w 才是变量。你肯定能看出来，一旦求出了w（也就求出了b） ，那么中间的直线H 就知道了（因为它就是 wx+b=0 嘛，哈哈），那
30、么 H1 和 H2 也就知道了（因为三者是平行的，而且相隔的距离还是|w|决定的）。那么 w 是谁决定的？显然是你给的样本决定的，一旦你在空间中给出了精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 13 页，共 33 页 - - - - - - - - - - 那些个样本点， 三条直线的位置实际上就唯一确定了（因为我们求的是最优的那三条，当然是唯一的），我们解优化问题的过程也只不过是把这个确定了的东西算出来而已。样本确定了w，用数学的语言描述，就是w 可以表示为样本的某种组合：w= 1x1+ 2x2+ +
31、 nxn式子中的i是一个一个的数（在严格的证明过程中，这些被称为拉格朗日乘子） ，而 xi是样本点，因而是向量，n 就是总样本点的个数。为了方便描述，以下开始严格区别数字与向量的乘积和向量间的乘积，我会用1x1表示数字和向量的乘积，而用表示向量x1,x2 的内积（也叫点积，注意与向量叉积的区别）。因此 g(x)的表达式严格的形式应该是：g(x)=+b但是上面的式子还不够好，你回头看看图中正样本和负样本的位置，想像一下， 我不动所有点的位置， 而只是把其中一个正样本点定为负样本点（也就是把一个点的形状从圆形变为方形） ，结果怎么样？三条直线都必须移动（因为对这三条直线的要求是必须把方形和圆形的点
32、正确分开） ！这说明 w 不仅跟样本点的位置有关，还跟样本的类别有关（也就是和样本的“ 标签 ” 有关） 。因此用下面这个式子表示才算完整：w= 1y1x1+ 2y2x2+ + nynxn （式 1）其中的 yi 就是第 i 个样本的标签， 它等于 1 或者 -1。 其实以上式子的那一堆拉格朗日乘子中，只有很少的一部分不等于0（不等于0 才对 w 起决定作用） ，这部分不等于0 的拉格朗日乘子后面所乘的样本点，其实都落在H1 和 H2 上，也正是这部分样本（而不需要全部样本）唯一的确定了分类函数，当然， 更严格的说， 这些样本的一部分就可以确定，因为例如确定一条直线， 只需要两个点就可以，即便
33、有三五个都落在上面，我们也不是全都需要。这部分我们真正需要的样本点，就叫做支持 （撑） 向量！ （名字还挺形象吧，他们 “ 撑” 起了分界线）式子也可以用求和符号简写一下：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 14 页，共 33 页 - - - - - - - - - - 因此原来的g(x)表达式可以写为：注意式子中x 才是变量，也就是你要分类哪篇文档，就把该文档的向量表示代入到x 的位置，而所有的xi 统统都是已知的样本。还注意到式子中只有xi 和 x 是向量，因此一部分可以从内积符号中拿出来
34、，得到g(x)的式子为：发现了什么？ w 不见啦！从求w 变成了求 。但肯定有人会说， 这并没有把原问题简化呀。嘿嘿，其实简化了， 只不过在你看不见的地方，以这样的形式描述问题以后，我们的优化问题少了很大一部分不等式约束（记得这是我们解不了极值问题的万恶之源）。但是接下来先跳过线性分类器求解的部分，来看看SVM 在线性分类器上所做的重大改进核函数。SVM 入门（七）为何需要核函数生存？还是毁灭？哈姆雷特可分？还是不可分？支持向量机精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 15 页，共 33 页 -
35、- - - - - - - - - 之前一直在讨论的线性分类器,器如其名（汗，这是什么说法啊），只能对线性可分的样本做处理。 如果提供的样本线性不可分，结果很简单， 线性分类器的求解程序会无限循环，永远也解不出来。 这必然使得它的适用范围大大缩小，而它的很多优点我们实在不原意放弃，怎么办呢？是否有某种方法，让线性不可分的数据变得线性可分呢？有！其思想说来也简单，来用一个二维平面中的分类问题作例子，你一看就会明白。事先声明，下面这个例子是网络早就有的，我一时找不到原作者的正确信息，在此借用， 并加进了我自己的解说而已。例子是下面这张图：/我们把横轴上端点a 和 b 之间红色部分里的所有点定为正类
36、，两边的黑色部分里的点定为负类。试问能找到一个线性函数把两类正确分开么？不能，因为二维空间里的线性函数就是指直线，显然找不到符合条件的直线。但我们可以找到一条曲线，例如下面这一条：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 16 页，共 33 页 - - - - - - - - - - 显然通过点在这条曲线的上方还是下方就可以判断点所属的类别（你在横轴上随便找一点，算算这一点的函数值，会发现负类的点函数值一定比0 大，而正类的一定比0 小） 。这条曲线就是我们熟知的二次曲线，它的函数表达式可以写为：问
37、题只是它不是一个线性函数，但是，下面要注意看了，新建一个向量y 和 a：这样 g(x)就可以转化为f(y)=， 你可以把 y 和 a 分别回带一下， 看看等不等于原来的g(x)。用内积的形式写你可能看不太清楚，实际上f(y)的形式就是：g(x)=f(y)=ay在任意维度的空间中，这种形式的函数都是一个线性函数（只不过其中的a 和 y 都是多维向量罢了），因为自变量y 的次数不大于1。看出妙在哪了么？原来在二维空间中一个线性不可分的问题，映射到四维空间后，变成了线性可分的！ 因此这也形成了我们最初想解决线性不可分问题的基本思路向高维空间转化，使其变得线性可分。精品资料 - - - 欢迎下载 -
38、- - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 17 页，共 33 页 - - - - - - - - - - 而转化最关键的部分就在于找到x 到 y 的映射方法。遗憾的是，如何找到这个映射，没有系统性的方法（也就是说，纯靠猜和凑）。具体到我们的文本分类问题，文本被表示为上千维的向量，即使维数已经如此之高，也常常是线性不可分的，还要向更高的空间转化。其中的难度可想而知。小 Tips:为什么说f(y)=ay 是四维空间里的函数?大家可能一时没看明白。回想一下我们二维空间里的函数定义g(x)=ax+b变量 x 是一维的， 为什么说它是二维空间里
39、的函数呢？因为还有一个变量我们没写出来，它的完整形式其实是y=g(x)=ax+b即y=ax+b看看，有几个变量？两个。那是几维空间的函数？（作者五岁的弟弟答：五维的。 作者： ）再看看f(y)=ay里面的 y 是三维的变量，那f(y)是几维空间里的函数？（作者五岁的弟弟答：还是五维的。作者： ）用一个具体文本分类的例子来看看这种向高维空间映射从而分类的方法如何运作，想象一下，我们文本分类问题的原始空间是1000 维的（即每个要被分类的文档被表示为一个1000 维的向量），在这个维度上问题是线性不可分的。现在我们有一个2000 维空间里的线性函数f(x )=+b注意向量的右上角有个 哦。 它能够
40、将原问题变得可分。式中的w 和 x 都是 2000 维的向量，只不过 w 是定值，而x 是变量（好吧 ,严格说来这个函数是2001 维的 ,哈哈） ，现在我们的输入呢，是一个1000 维的向量x，分类的过程是先把x 变换为 2000 维的向量x ，然后求这个变换后的向量x 与向量 w 的内积，再把这个内积的值和b 相加，就得到了结果，看结果大于阈值还是小于阈值就得到了分类结果。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 18 页，共 33 页 - - - - - - - - - - 你发现了什么？我们
41、其实只关心那个高维空间里内积的值，那个值算出来了， 分类结果就算出来了。而从理论上说，x 是经由 x 变换来的，因此广义上可以把它叫做x 的函数（有一个 x，就确定了一个x ，对吧，确定不出第二个），而 w 是常量，它是一个低维空间里的常量 w 经过变换得到的，所以给了一个w 和 x 的值，就有一个确定的f(x )值与其对应。这让我们幻想， 是否能有这样一种函数K(w,x),他接受低维空间的输入值，却能算出高维空间的内积值 ？如果有这样的函数，那么当给了一个低维空间的输入x 以后，g(x)=K(w,x)+bf(x )=+b这两个函数的计算结果就完全一样，我们也就用不着费力找那个映射关系，直接拿
42、低维的输入往 g(x)里面代就可以了 （再次提醒， 这回的 g(x)就不是线性函数啦，因为你不能保证K(w,x)这个表达式里的x 次数不高于1 哦） 。万幸的是， 这样的 K(w,x)确实存在（发现凡是我们人类能解决的问题，大都是巧得不能再巧，特殊得不能再特殊的问题，总是恰好有些能投机取巧的地方才能解决，由此感到人类的渺小） ，它被称作核函数（核，kernel） ，而且还不止一个，事实上，只要是满足了Mercer 条件的函数，都可以作为核函数。核函数的基本作用就是接受两个低维空间里的向量，能够计算出经过某个变换后在高维空间里的向量内积值。几个比较常用的核函数，俄，教课书里都列过，我就不敲了（懒
43、！ ） 。回想我们上节说的求一个线性分类器，它的形式应该是：现在这个就是高维空间里的线性函数（为了区别低维和高维空间里的函数和向量，我改了函数的名字，并且给w 和 x 都加上了 ） ，我们就可以用一个低维空间里的函数（再一次的，这个低维空间里的函数就不再是线性的啦）来代替，精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 19 页，共 33 页 - - - - - - - - - - 又发现什么了？f(x ) 和 g(x)里的 ，y，b 全都是一样一样的！这就是说，尽管给的问题是线性不可分的， 但是我们就硬
44、当它是线性问题来求解，只不过求解过程中，凡是要求内积的时候就用你选定的核函数来算。这样求出来的再和你选定的核函数一组合，就得到分类器啦！明白了以上这些，会自然的问接下来两个问题：1 既然有很多的核函数，针对具体问题该怎么选择？2 如果使用核函数向高维空间映射后，问题仍然是线性不可分的，那怎么办？第一个问题现在就可以回答你：对核函数的选择， 现在还缺乏指导原则！各种实验的观察结果（不光是文本分类）的确表明，某些问题用某些核函数效果很好，用另一些就很差，但是一般来讲，径向基核函数是不会出太大偏差的一种，首选。（我做文本分类系统的时候，使用径向基核函数， 没有参数调优的情况下，绝大部分类别的准确和召
45、回都在85%以上， 可见。虽然 libSVM 的作者林智仁认为文本分类用线性核函数效果更佳，待考证）对第二个问题的解决则引出了我们下一节的主题：松弛变量。SVM 入门（八）松弛变量现在我们已经把一个本来线性不可分的文本分类问题，通过映射到高维空间而变成了线性可分的。就像下图这样：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 20 页，共 33 页 - - - - - - - - - - 圆形和方形的点各有成千上万个（毕竟，这就是我们训练集中文档的数量嘛，当然很大了） 。现在想象我们有另一个训练集，只比原
46、先这个训练集多了一篇文章，映射到高维空间以后 （当然，也使用了相同的核函数），也就多了一个样本点，但是这个样本的位置是这样的：就是图中黄色那个点，它是方形的，因而它是负类的一个样本，这单独的一个样本，使得原本线性可分的问题变成了线性不可分的。这样类似的问题 （仅有少数点线性不可分）叫做 “ 近似线性可分 ” 的问题。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 21 页，共 33 页 - - - - - - - - - - 以我们人类的常识来判断，说有一万个点都符合某种规律（因而线性可分），有一个点不符
47、合，那这一个点是否就代表了分类规则中我们没有考虑到的方面呢（因而规则应该为它而做出修改）？其实我们会觉得，更有可能的是，这个样本点压根就是错误，是噪声， 是提供训练集的同学人工分类时一打瞌睡错放进去的。所以我们会简单的忽略这个样本点，仍然使用原来的分类器，其效果丝毫不受影响。但这种对噪声的容错性是人的思维带来的，我们的程序可没有。由于我们原本的优化问题的表达式中， 确实要考虑所有的样本点（不能忽略某一个，因为程序它怎么知道该忽略哪一个呢？），在此基础上寻找正负类之间的最大几何间隔，而几何间隔本身代表的是距离，是非负的，像上面这种有噪声的情况会使得整个问题无解。这种解法其实也叫做“ 硬间隔 ”
48、分类法，因为他硬性的要求所有样本点都满足和分类平面间的距离必须大于某个值。因此由上面的例子中也可以看出，硬间隔的分类法其结果容易受少数点的控制，这是很危险的 （尽管有句话说真理总是掌握在少数人手中，但那不过是那一小撮人聊以自慰的词句罢了，咱还是得民主） 。但解决方法也很明显， 就是仿照人的思路， 允许一些点到分类平面的距离不满足原先的要求。由于不同的训练集各点的间距尺度不太一样，因此用间隔 （而不是几何间隔）来衡量有利于我们表达形式的简洁。我们原先对样本点的要求是：意思是说离分类面最近的样本点函数间隔也要比1 大。如果要引入容错性，就给 1 这个硬性的阈值加一个松弛变量，即允许精品资料 - -
49、 - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 22 页，共 33 页 - - - - - - - - - - 因为松弛变量是非负的，因此最终的结果是要求间隔可以比1 小。但是当某些点出现这种间隔比 1 小的情况时（这些点也叫离群点），意味着我们放弃了对这些点的精确分类，而这对我们的分类器来说是种损失。但是放弃这些点也带来了好处，那就是使分类面不必向这些点的方向移动，因而可以得到更大的几何间隔（在低维空间看来，分类边界也更平滑）。显然我们必须权衡这种损失和好处。好处很明显， 我们得到的分类间隔越大，好处就越多。回顾我们原
50、始的硬间隔分类对应的优化问题：|w|2就是我们的目标函数（当然系数可有可无），希望它越小越好，因而损失就必然是一个能使之变大的量（能使它变小就不叫损失了，我们本来就希望目标函数值越小越好）。那如何来衡量损失，有两种常用的方式，有人喜欢用而有人喜欢用其中 l 都是样本的数目。两种方法没有大的区别。如果选择了第一种，得到的方法的就叫做二阶软间隔分类器，第二种就叫做一阶软间隔分类器。把损失加入到目标函数里的时候，就需要一个惩罚因子（cost，也就是 libSVM 的诸多参数中的C） ，原来的优化问题就变成了下面这样：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载