支持向量机入门

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