A_Tutorial_on_Support_Vector_Machines_for_Pattern_Recognition的中文翻译

A_Tutorial_on_Support_Vector_Machines_for_Pattern_Recognition这篇文章的翻译，自己辛苦翻译的
All Right Reserved From: NZQ 我们注意到如果存在密度函数p(x,y),则P(x,y)可以写成p(x,y)dxdy 这是一个计算期望风险很好的途径,但是除非我们知道概率分布函数P(x,y)的 估计,否则这种方法没有什么意义。 R(ω)的数值被称为期望风险,或者直接说风险。此处我们称其为真实风险, 以强调我们最终感兴趣的是这个数值。我们定义训练集(对应固定有限个样本) 上的测量平均误差为经验风险Remp(a): R emp ∑-y-f(x;,) 注意到,上式没有出现概率分布函数。对于一个选定的参数c和固定的训练集 x;,y;,Rem()是一个固定的数值 数值y1-f(x,m)被称为损失函数,在上述情况下,其取值只能是或者 现在选定一个数值η,其中0≤η≤1。损失函数如上所述取值或,则下式 所示的界以1-η的概率成立 R()≤Rmp()+ h(og(2h)+1)-g(/4 上式中是一个非负整数,称为维( 维),是衡量上 述容量概念的一个标准。下文中我们将称公式()的右边第二项为“风险的界”。 我们从以前的术语开始探究 等作家()称它为“保证风险”(原文是 ),这样命名有一点不恰当,因为它只是风险的界而非风险;并且 它仅是提供一种确定的可能性,而非保证。对右端第二项的第二种命名方式是称 之为“VC置信区间” 我们注意到关于这个界有三个关键点。第一,明显地这个界与概率分布函数 P(x,y)无关。它仅假定训练数据与测试数据服从同一未知概率分布P(x,y)。其 次,通常没有办法具体求岀上式左端项的数值。第三,如果我们知道了的值, 我们很容易可以计算上式右端项的数值。因此,对于给定的学习机器(“学习机 器”仅表示函数集f(x,α)),选定一个固定且足够小的η,然后选择使上式右端项 最小化的学习杋器,则这个学习机器可以使真实风险的上界最小。这个理论是结 构风险最小化(见章节)的基本思想,对于为给定任务选择合理的学习机器 其提供了一个理论上的方法。给定一组学习机器,则至少有一个学习机器,相对 于其他机器来说,其界是紧的。即使对于任一学习机器来说,这个界也不是紧的, 上式右端项仍能为最小化经验风险提供一些有用的信息。这个界可能对于所有的 数集都不是紧的,使得反对者可以借此批评这一理论。目前这种情况下,一切 都只能以实验作为依据(貌似 已经证明这个界是紧的)。 维 维表征了函数集α(我们再次使用α作为一个一般的参数,确定了α也 就确定了特定的函数)的一种特性,其可以用各类函数关系进行定义。此处我 All Right Reserved From: NZQ 们仅考虑对应于两类模式识别问题的函数,所以,f(x,a)∈{-11}vx,。如 果给定的长度为的样木集可以被函数集a中的一个函数以2种方式分开,我 们则说该样木可以被这个函数集打散。函数集a的维定义为其可以打乱的 样本点最大的个数。请注意,如果喲数集的维为,则不少存在一组长度为 的样本集可以被该函数集打散,但是这并不意味着该函数集可以把任意长度为 的样本集打散。 R空间中定向超平面打散样本点 假定样本都是二维空间R2中的数据,函数集c是一个定向直线的集合,对 于一条给定直线,位于直线一侧的是类,另一侧的是类。直线的方向如图 中箭头所示,箭头所指一侧的样本点标记为类。我们可以发现,这函数集可 以打散某一长度为的样本集,却无法打散任意长度为的样本集,因此,二维 空间R2中定向直线的维是 图 二维空间R2中三个样本点被定向直线打散 现在让我们考虑维空间R中的超平面。可能要利用下述定理: 定理 维空问R中的长度为的样本集可以被相应定向超平面打散的允 要条件是,任选一个样本点作为原点,其它样本点的位置向量线性无关 推论: 维空间R中定向超平面的维是,因为我们总可以选出 个点,其中一个点作为原点,其余个点的位置向量线性无关,但是我们选不出 个点(因为维空间R中不会有个线性无关的向量)。 本推论的另一种证明方法见于 和 ()的著作,见于参考 文南3 维与参数数目 维使得函数集容量的概念得以具体化。人们直观上容易认为,参数多的 函数集维会很高,而参数少的函数集的维会很低。然而 和 ,)提出」一个很明显的反例:仅含一个参数的学习 机器可以有无穷大的维(对于分类器来说,有无穷大的维,意味着 无论有多大,它都可以打散长度为的样本集)。定义阶跃函数0(x)x∈R: All Right Reserved From: NZQ e(x)=1vx>0;6(x)=-1wx≤0。考虑如下定义的仅有一个参数的 数集 f(x,a)≡(sin(ax),x,a∈R 对于任意大的数字,可以找到按照如下方式选择的长度为的样本集, 其能被该函数集打散: X1=10 可以为指定任意标号 y1,y2 y1,y1∈{-1,1} 只需选择如下式所示的α,f(x)就能按照上式中标号分开样本集: =T(1+l19m1° () 因此,这个学习机器的维是无穷大的。 =0 图 维无限大的函数集0(sin(ax)无法打散的个点 有意思的是,尽管上述函数集可以打散某个任意长度的样本集,我们仍能找 出一个仅有个点的样本集,使其无法打散。这个样本点只是简单地均匀分布, 其标号如图所示。这种情况看作:样木点x1位于相位φ1=2nm+6处,其标号 y1=1,其中0<8<π。x2的相位对2π取余为28,令y2=1→0<8< 简单地点x3会使得6>T/3然后,在点x处,/3<8<2会使得f(x4,0)=-1, 与给定的标号相反。这四个点是空间R中有向超平面对于位于同一直线上三个点 按照公式()的一种类推。这两种情况下,哟数集都无法打散这些点集。 通过最小化最小化界 图说明了,在置信度为(n=0.05),样本数量为的情况下,公 式右端第二项是如何随变化的。对于任意的样木数 置信区间都是 的单调增数。 因此,给定一些经验风险为零的学习机器,我们应该选择维小的函数集。 这样才能有一个更小的误差上界。总体而言,对于经验误差不为零的情况,我们 应该选择使得公式右端项最小的学习机器。 注意到釆用这种策略时我们仅依据公式。公式(在给定概率下)可以给 出真实风险的上界。这并不意味着,一个具有同样的绎验风险然而维更高的 学习机器不可以有更好的泛化能力。事实上,下一节我们将给出一个例子,它有 无穷大的维然而其泛化能力同样很好。从图形中可以注意到,对于 (n=0.05且1=10000)的情况,置信区间超过了单位,所以对于吏高的 值,这个界不能保证是紧的。 All Right Reserved From: NZQ 14 12 o9cgE89> 0.8 0.6 0.4 0.2 0.10.20.30.40.50.60.7080.91 h/I= VC Dimension /Sample Size 图 置信区间随单调递增 两个案例 考虑近邻分类器,。因为任意数目的样本点和任意的标号组成的样本 集都可以被该函数集正确的学习(假设不同类的样木点不紧邻),所以这个函数 集具有无穷大的维和零经验风险。因此这个界一无所用。事实上,对于任何 具有无穷大的维的函数集来说,这个界都没有任何意义。然而,即使不遵循 使这个界最小化的原则,近邻分类器的泛化能力依然很好。因此,第一个案例警 示我们,无穷人的容量并不一定造成差的泛化能力 让我们以一种试图打破传统知识以利用传统知识的方式来理解这个理论,看 下我们是否能够提出这样一个分类器,其存在这个边界然而违反这个边界。(此 处作者的意思大概是让公式的小于等于变成大于等于)我们使公式中左边项 尽可能的大同时右边项尽可能的小,以使我们得到这样一个分类器:其真实风险 是最坏的 同时对于某些样本其经验风险为零而且其维很容易计算并远 小于(这样这个边界就不成立了)。下面有一个这样的案例,我们称其为“笔记 型分类器”(原文是 )。这个分类器包含一个有足够空间记 个训练样本类别的笔记,m≤1。对于后续所有的样本点,该分类器简单的认为 所冇样本点同属一类。假设样本点是随机选择的,而且其正类与负类数目大抵相 同。这个笔记型分类器对于前个样本点经验风险为零;对后续样本点错分概 率为;同时其维。把上述数值带入公式,可得 ≤m(21/m)+1-(/m)ln(/4 () 上式将满足任意n如果下式成立 f()=( 2)exp(4-1 ,0≤z≤1 因为f(z)单调递增而且f(z=1)=0236,所以上式成立 All Right Reserved From: NZQ 结构风险最小化 4(h3(h2 h1 h1<h2≤h3 图 依照维嵌套的函数序列 我们现在能够总结下结构风险最小化()原则( )。注意 到,公式中提到的置信区间依赖于所选择函数集,相反地经验风险与真实 风险依赖于训练过程所选择的某一特定函数。我们要从待选函数集中选择一个最 小化风险边界的子集。因为维是一个整数,所以明显地我们不能够得到平 滑变化的维。取而代之,我们介绍一种“结构”,其将整个函数集分成层层 嵌套的子集(如图)。对于每个子集,我们要么可以算出维,要么可以直 接算出所决定的界。 原则就是找出可以最小化真实风险的界的子集。这 点可以通过简单地训练学习机器做到,对于每个子集,训练的日标是找到最小 化经验风险的那个函数。然后从序列中取得经验风险与维置信区问最小的函 数 到此为止,我们已经为探索支持向量机之路铺设了基础 线性支持向量机 可分的情况 我们将以最简单的情况开始:在线性可分数据中训练线分类机(正如我们看 到的,对于更一般情况的分析一在线性不可分数据上训练非线性分类机一最后都 会转化为一个简单的二次规划问题)。再次标注训练数据{xy},i=1,…,,J,y1∈ {-1,1,x1∈R。假定我们有一个超平面可以把正类与负类分开(分类超平面)。 超平面上的点满足ox+b=0,其中o是超平面的法向量。B1o是超平面到 原点的垂育距离,其中‖是o的欧儿里得距离(范数)。用d+(d-)表小(负) 类到分类超平面的最短距离。定义d++d-为分类超平面的“裕度”(原文为 )。对于线性可分的情况,支持向量机算法就是寻找分类超平面的最大裕 度。可以具体阐述为:假定所有训练数据满足下述约束 X;·ω+b≥+1fory;=+1 X1·0+b≤-1fory1=-1 上述两式可以合为下式 (X1·ω+b)-1≥0vi 现在考虑满足公式()取等号的点(这样的点在某种程度上决定了0和) 这些点在超平面H1上:x1:ω+b=1,其含有ω且到原点的垂直距离是 All Right Reserved From: NZQ o/同样的,使得公式()取等号的点在超平面12上:x1:u+b=-1, 其含有0且到原点的垂直距离是 lo因此d+=d-=1o且裕度可 以简单地表示为/1ol注意到H1与H2是平行的(有共同的法向量)且没有样本 点落在它们之间。因此我们能够在满足约束条件公式()的情况下,通过最小 化‖ω)‖2来得到裕度最大的超平面 Origin ⊥ argin 图可分情况下的线性可分超平面。圈中样本点代表支持向量 对于典型的二维情形,我们期望其解具有图所示的情形。使得公式() 取等号的训练点(超平面H1或者H2上的点)的移动可以改变训练结果,称其为 支持向量;在图中通过圆圈标出了这些点 我们转向这个问题的一个拉格朗日方程。这个转化有两个原因。首先是约束 ()会转化成拉格朗日乘子的形式,以更好的处理。第二是通过这样重构问题, 训练数据(在训练与测试中)将会仅出现向量点乘的形式。这是一个很重要的特 性,决定了我们可以得到解决非线性情况的方法(第章)。 因此,对每个不等式约東(),我们都引入一个正的拉格朗囗乘了 ax,i=1,…,l。回想对于形如c1>0的不等式约束条件,拉格朗日方程是从 标方程中减去约束方程乘以一个正的拉格朗日乘子。对于等式约束,拉格朗日乘 子没有非负约束。拉格朗日方程如下: Lp=‖o2-2=1cy(x;:ω+b)+∑=1a 我们必须在满足约束α1>0的情况下消去Lp中含有a1的中间变量(我们称这 组特定的约束为C1),然后对于ω和来最小化L。因为目标函数本身是个凸函 数,且满足该约束的点形成的是凸集(任一线性约束都定义了一个凸集,个线 性约束同时定义了这些凸集的交集,凸集的交集仍是凸集),所以这个问题是 个凸二次规划问题。这意味着我们可以等效地求解下述“对偶”问题:在以下约束 条件下最大化Lp,L对ω和的梯度等于;c1>0(我们称这组特定的约束为C2) 这种特定的对偶形式成为对偶( )。它有这样一种特性:在 8 All Right Reserved From: NZQ 约束C2下最大化Lp与在约束C1下最小化L得到的ω,,a的值是相同的 Lp对ω与的梯度等于的约束给出了以下条件: ∑ i yixi ∑ 因为对偶问题中的约東条件与原问题相同,将其带入公式()可得: aiajyiyjxi' xi 注意到我们给了拉格朗口方程不同的标弓(原问题用,对偶问题有)以 强调这两个表达式的不同:L与L源自同一个目标函数,却有不同的约束条件 分别通过最小化L或最大化L求解。也注意到,如果我们在的条件下构造 这个问题,等价于所有的超平面都包含原点,约束()就不再成立。这对于高 维空间是一个缓和约束(原文为 ),因为它等效于降低一个自度。 支持向量训练(对于线性可分的情况)等价于在公式()和为正的约東 条件下,对α;最大化Lp,其解由公式()给出。注意到每个训练点都对应于 个拉格朗日乘子c1。在解中,那些对应于α1>0的样木点称为“攴持冋量”,位于 超平面H1或者H2上。其余所有训练点1=0,其要么位于H1或者H2上(使得公 式()等式成立),要么位于H1或者H2两侧使得公式()不等号成立。对于 这些学习机器,支持向量是训练集的决定性元素。它们最邻近决策边界;如果其 他训练点被移动(改变位置但没穿过H1或者H2),即使重新训练,也会得到同 个分类超平面 条件 在约東优化的理论与应用中, ()条件都有着至关 重要的作用。对于上述原问题, 条件可表述为( LP=ωy-∑yxw=0v=1,…,d ∑iαiyi1=0 y1(x1·(+b)-1≥0i=1,…,l a>o vi a1Gy1(x1·+b)-1)=0V 对于任何约東条件,假定可行域的下降方向与线性约束的下降方向交于一点, 则仼意带约束最优化问题(无论是否凸规划)的解都满足条件(参见 )。这个相当技术规范的假定对于每个支持向量机都成 立,因为其约束都是线性的。而且, 问题是一个凸规划(目标函数是凸函 数,可行域是凸集),对于凸规划(如果上述规范条件成立),条件是ω,b和α 为解的充要条件 )。因此,求解问题相当于寻找满足 条件的解。这导致有很多方法可以求解 问题(比如,第章中提到的原 对偶方法)。 作为一个直接的应用,我们注意到,尽管ω可以在训练过程中直接求解,國 值却只能隐含的求解。然而,通过KKT“补充条件”公式(),选择使得α1≠0的 可以很容易的计算出(注意到对每个合适的计算出所有的取平均会更合理) All Right Reserved From: NZQ 注意到我们目前为止所做的就是把问题转化为一个优化问趣,其约束比公式 (),()更易处理。求解现实中的问题往往需要数值解法。随后我们会介绍 更多。然而,我们先求解一种相对少见的情况,其是非平凡的问题(维数任意, 解不明显),但是其可以通过解析求解 最优超平面:一个案例 尽管夲节的主要目的是求解一个其支持向量可以被解析求解的非平凡模式 识别问题,此处得到的结果可用于后面的证明。对于所考虑问题,每个训练点都 被证眀是一个支持向量,这也是我们能解析求解的一个原因。 考虑将个点对称地放在半径为的球休S"-1上:更确切地说,这些点形 成了维空间对称的顶点。可以很容易地将这些点映射到维空间R+中的经 过原点的法向量为()维向量(,,)的超平面上(在这个变换中, 这些点略过维空间R,直接映射到维空间R+1)。可以确切地知道,向量 本身是用岁马数字标示,而其下标使川希腊字封表示,其下标通过下式给出 R +δ; 其中张积量(原文是 )δ当的时候为,否则为。因此,单 位圆上的三个等距点的向量(参见图)分别是 3′y6 V6 对称的一个结果就是任意两个向量之间的夹角都是相等的(等于 arccos (I/n)) lx‖2=R R 或者,更简洁地 61-(1-61) 对每个样本点任意指定一个类别标号C∈{+1,-1},我们希望找出以最大 裕度将两类样本点分开的超平面。因此,我们必须在满足约束a;>0,与等式约 東公式()的条件下,最大化公式()中的L。我们的方法是假定不存在不 等式约東而简单地求解问题。在满足等式约束公式()的情况下,若得到的解 满足约束条件α>0,ⅵi,我们就认为得到了一般的解,因为L的最大值落在可 行域内。为了利用等式约束,我们引入附加的拉格朗日乘子。因此我们寻求最大 化下式: