英语原文共 47 页，剩余内容已隐藏，支付完成后下载完整资料
来源：《data mining and knowledge discovery》, 1998, 2(2): 121~167
用于模式识别的支持向量机入门
克里斯托弗J.C. Burges
贝尔实验室,朗讯科技
1.绪论
本文是介绍关于在SVMs背后基本思想的广泛指南。著作(Vapnik,1995;Vapnik,1998)里面很好的描述了支持向量机，但是仍然留下了需要说明从哪里开始学习的空间。虽然可以说本学科开始于70年代，但是只到现在才引起人们的注意，所以是时候该给出一个合适的介绍性的综述了。本指南集中详细介绍（dwells entirely on）模式识别问题。其中一些思想直接转到衰减估计（regression estimation）和线性算子转置，但是空间约束限制了这些话题的展开。
本指南中包括一些新的材料。所有的证明都是我自己的版本，为了使这些材料更容易被人们接受，这里强调他们既是清晰的，也是独立的（self-contained）。这样做的代价是失去高雅和一般性：一旦思路清晰了，通常就很容易带有一般性。详细的证明见附录。
处于想让读者注意相关文献的动机，我们总结一下一些近来关于SVMs的应用和延伸。在模式识别领域，SVMs被应用于孤立的手写体的识别（Cortes andVapnik, 1995; Schuml;olkopf,Burges and Vapnik, 1995; Schuml;olkopf, Burges and Vapnik, 1996;Burges and Schuml;olkopf, 1997)，目标识别（Blanz et al., 1996），语音辨认，人脸识别等。在衰减估计领域，SVMs被用于和基准时间序列语言测试，波士顿住房问题，对于PET算子转置问题等。在多数情况下，SVM的推广性能可以和竞争方法相匹配甚至更好。人们还研究了应用SVMs进行密度估计和ANOVA分解。关于SVMs的延伸，基本的SVMs不包含对问题的先验知识（例如用SVMs进行人脸识别，随机打散象素的顺序，并不影响识别的结果，而神经网络就面对这样的情况就会瘫痪）。一些还研究了如何在SVMs中引入先验知识。虽然SVMs具有很好的推广性能，但是他们在检测阶段可能速度会特别慢，(Burges, 1996; Osuna andGirosi,1998).中强调了这一点。近来的工作研究了SVMs一般基本思想，它和相关理论的联系以及SVM思想如何是与很多其他算法合为一体的。读者还可能会发现(Schuml;olkopf, 1997)中的理论非常有帮助。
对最初SVMs发展的驱动发生在guises-the bias variance tradeoff、学习能力控制，过学习等——但是基本思想是相同的。粗略的说，对于一个给定的，只有有限训练数据的学习任务，如果在对来自特殊训练数据的精度和机器的学习能力——机器无误差地学习任何训练数据的能力——之间达到很好的平衡，就可以达到最好的推广性能。学习能力过大的机器就像一个有图像记忆功能的植物学家，当碰到一个新树的时候，就会定论这不是一棵树，因为这棵树和她见过的任何树都有不同数量的叶子。如果学习能力过小的机器就像一个懒惰的植物学家，他的定论是只要是绿色的就是树。两者的推广性能都不好。对这些理论深入探讨和公式化就引出了统计学习理论的闪光点(Vapnik, 1979)。
接下来，用粗体说明向量或者矩阵；用非粗体表示向量或矩阵的元素或者标量。我们用希腊数字表示向量或者矩阵的元素，用罗马数字表示向量或者矩阵本身。使用拉格朗日乘子解决问题，假设了等式约束或不等式约束。
2. 模式识别学习机推广性能的界
有很多非平凡边界决定着学习机的学习能力和性能之间的关系。这些理论来自基于对“随着数据的增加，其平均数在什么情况下，以多快的速度，统一地逼近实际平均数（数据量趋向无穷大时的平均数）”的考虑。我们从这些边界的其中之一开始。
本文所用符号多数是延续(Vapnik, 1995)中符号。假设我们有l个观测样本。每个观测样本都是一个数对：有可靠来源的向量xiisin;RN，i= 1，。..，L 和相应的输出yi。现在假设数据来自未知的分布P（x，y），即假设数据是独立同分布的（iid），用P表示数据的累积概率分布函数，用p表示相应的概率密度函数。注意到这种假设比对每个向量x设置一个固定的y更具有一般意义：他允许对给定x有分布式的输出y。在这种情况下，数据来源就会根据固定的分布，给相应的xi标定一个yi。然而在这一章节之后，我们仍然假设对给定x有固定输出y。
现在假设我们有一个机器，其任务是学习映射xi→yi。该机器实际上是由一个可能的映射X→F（x，alpha;）集定义的，其中函数f(x,alpha;）本身是由可调参数alpha;标定的。假设机器是具有确定性的：给定输入x和一个alpha;选择，它就会有相同的输出f(x,alpha;)。一个特殊的alpha;选择，就会得出我们所谓的“已训练学习机”。例如，一个具有固定结构和对应一套权值和偏度值的参数alpha;的神经网络，在这种意义上就是一个学习机。
因此，对该训练过的学习机，就有期望的测试误差：
注意当存在概率密度函数p(x,y)，dP(x,y )就可以写成p(x,y)dxdy。这是对真实误差的一种比较好的写法，但是除非有对于P(x,y)的估计，否则这样写没有任何意义。R(alpha;)的值被称作期望风险，或者风险。这里我们称其为真实风险，以强调它是我们最终关注的值。定义在训练数据（对于固定的有限个观测样本）上的平均风险率为“经验风险”Remp（alpha;）：
注意这里没有出现概率分布函数。对于给定的参数选择alpha;和给定训练集{xi,yi}，经验风险Remp(alpha;)是确定的。
称frac12;丨y-f(x,a)丨为损失函数。对这里描述的情况，它只能取0或1.现在选择一个满足 0le;eta;le;1的eta;，那么当损失函数以概率1-eta;取这些值的时候，下面的风险边界成立(Vapnik, 1995)：
其中h是非负整数，称作VC维，它是对前面提到的学习能力的一种测度。以下我们就称（3）式的右边为“风险边界”。我们这里区分以前的命名方法：(Guyon et al.,1992)的作者把它命名为“保险风险”，但这有些不恰当，因为它实际上是风险的边界，而不是一个风险，而且它只以一个特定的概率成立，因此它不是什么“保险”。右边的第二项我们称作是“VC信任”。
对此边界，有三个关键点。第一，它和概率分布函数P(x,y)无关；假设训练数据和测试数据都是独立地来自莫一个概率分布函数P(x,y)。第二，通常左边的实际风险是不可能计算得到的。第三，如果我们知道h，我们就可以很容易计算右边的边界。因此，给定一些不同学习器（学习器只是对一族函数f(x,a)的另外一种称呼）和固定的足够小的h，通过选择使（3）式右边最小的学习器，我们就选择了使实际风险具有最小上界的学习器。这就给出了对给定任务选择学习器的原则，也是后面提到的结构风险最小化（见2.6节）的本质思想。给定一族待选择的学习器，在这个意义上说，最少对其中一个学习器，该边界是严密的，这样再好也不过了。即使对于任何一个学习器，该边界都不是严密的，存在的希望是不等式右边仍然提供关于如何使实际风险最小化的信息。该边界不对任何学习器严密为批评家提供了发牢骚攻击的理由。对此，在现阶段，我们还只能依赖实验作为检验的标准。
2.1 VC维
VC维是一个函数集{f(alpha;)}(仍然使用alpha;表示一类参数，alpha;的一个选择就对应着一个特定的函数)的特性，可以对各种函数集定义VC维。这里我们只考虑对应两类模式识别问题的函数集，于是f（x，alpha;）isin;{-1，1}，forall;X，alpha;。如果一个给定l个数据点的函数集{f(alpha;)}可以以所有种分类方法分开，并且对于每一种分类都可以从函数集{f(alpha;)}中找到一个函数来实现这一种分类。我们就说这个数据集可以被该函数集打散。一个函数集的VC维就被定义成可以被该函数集打散的数据集的最大点数。因此，如果VC维是h，那么最少存在一个包含h个数据的集合可以被打散，但并不是说每一个包含h个数据的数据集都可以打散。
2.2 中有向超平面打散数据点
假设数据空间是二维空间，且函数集中包含一个定向直线，因此对于一个给定的直线，在该直线一边的所有数据都被标定为1类，而直线另外一侧的所有数据都被标定为-1类。如图1所示，并表明了直线的哪一侧被标定为1类。因为在空间中，只能找到3点而不能找到4点可以被这个函数集打散。那么在空间中定向直线集的VC维就是3。现在考虑中的超平面。下面的定义是非常有用的（证明见附录）：
定理 1
考虑在空间中包含m个数据的数据集。选择任意一点作为原点。这些m个点可以被导向超平面打散当且仅当其余点的位置向量是线性独立的。
推论：
空间中导向超平面集的VC维是n 1。因为我们总可以找到n 1个点，并且选择一个点作为原点，那么其余各n 点的位置向量是线性独立的，但是绝不能找到n 2 个这样的点（因为中不存在 个向量是线性独立的）。该推论的一个可选择的证明和参考书目可以在(Anthony and Biggs,1995)中找到。
2.3 VC维和参数个数
因此VC维就给出了一个给定函数集的学习能力概念一个具体化形式。直观地，人们可能会认为有一些参数学习机，其VC维也很高；而参数较少的学习机，其VC维也很低。然而有一个恰恰相反的例子，根据E.Levinand J.S.Denker (Vapnik,1995)：只有一个参数的学习机却有无穷大的VC维（一个分类器集 VC 维无穷大是说它可以打散l个点，无论l多大）。定义阶梯函数考虑单一参数 函数集：
你可以选择一些l，找出可以被打散的l个点。我的选择是：
你可以如下任意配置他们的标注：
如果我选择如下的alpha;，就可以得到这样的标注：
因此该机器的VC维就是无穷大。
有趣的是，即使我们可以打散任意多的点，但是仍可能存在不能被打散的四个点。如图2 所示等间隔的四个点。这种情况可以看作：x1的相位，那么标定y1=1，要求，x2的相位mod2pi;，是2；那么由y2=1可以推出0＜＜pi;/2。类似的x3要求大于pi;/3，而在x4，pi;/3＜＜pi;/2暗示着f(x,a)=-1，这与指定的标注相矛盾。对于（4）式和空间中的导向超平面，这四个点是类推的，其中三点位于一直线上。两个数据集都不能被所选择的函数集打散。
2.4 通过最小化h来最小化边界
图3表现了（3）式右边第二项即VC信任随h的变换情况，给定95％的信任率（eta;=0.05）10000 个样本。VC信任是h的单调增函数。这对于任何l值都成立。
因此，在一些经验风险为零的学习机当中，我们想要选择对应函数集的VC 维最小的一个学习机。这样就会得出较好的实际误差的上界。一般情况下，没有零经验风险，我们就要选择使（3）式右边最小的学习机。
在采用这种技巧的过程中，我们只是使用（3）式作为约束参考。（3）式（还有一些选择的概率）给出了实际风险的上界。但是这并不能证明在具有相同经验风险的学习机中，VC较高的性能就较差。事实上，下一节就会给出一个虽然VC维无限大，性能却很好的一个学习机的例子。还注意到图中当h/l＞0.37（即eta;=0.05，l=10000）时，VC信任就会超过单位l；因此，对于较高的h/l值，边界也不能保证是严密的。
2.5 两个例子（2004.11.17）
考虑第k最近邻分类器（krsquo;th nearest neighbor classifier），k＝1。因为无论多少个数据点，都可以通过该算法（可以证明互为异类的两个点不会互相位于对方之上）成功地学习，任意的标注，所以这个函数集具有无穷大的VC维和零经验风险。因此，风险边界提供不了任何用价值的信息。事实上，对于任何具有无穷大VC维的分类器，风险边界都是无效的。然而，尽管边界是无效的，最紧邻分类器仍具有良好的性能。因此第一个例子就是一个警戒传说：无穷“学习能力”并不等于性能不好。
按照传统惯例，我们采用通过试图违反事物来理解事物的方法，看看能不能得出对于 哪些分类器，边界
全文共7645字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[143170]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
