（运筹学与控制论专业论文）一种基于解析中心割平面法的分类算法.pdf

大连理工大学硬学位论文 摘要 本文基于支持囱量机( s v m ) 的最优解对应予翻译空间的解析中心遂一绪论，利用解 析中心割平溪法改进j o a e h i m s 提出的解决大藏模稀琉分类闻题的截平面算法，并绘蹴测 除多余约裘的两条删除准则。我们所提出的算法的舅的在于在整个约束集中寻找一小规 模的越馋用约束来傈证充分精确酶解。更准确的说，通过潮平面法迭代产生一捌连续的 愿驾题约豪区域的近议，其极限正是器约索区域的近似，糟度不超过。割平匿法被当 作约束选择方法。我们将证明这是_ 个可彳亍的策略，因为总是存在约束集中多项式级的 子集戆近戳豹代警所有麴慕。这绘我们的冀法带来了穰大鲮方癯。透过数餐实验与原算 法进行比较，表明本文所提算较原有算法有更好的数值效果。 关键词：解析中心；割平面法；支持向壁机；犬规模 一种基于解析中心割平面法的分类算法 ac l a s s i f i c a t i o na l g o r i t h mb a s e do na n a l y t i cc e n t e rc u t t i n gp l a n em e t h o d a b s t r a c t t h i sp a p e ri sb a s e do nt h et h e o r yt h a tt h eo p t i m a ls o l u t i o no ft h es u p p o r t v e c t o rm a c h i n e c o r r e s p o n d s t ot h ea n a l y t i cc e n t e ro ft h ev e r s i o ns p a c e w ei n t r o d u c et h ea n a l y t i cc e n t e r c u t t i n gp l a n em e t h o d ( a c c m e ) t o ac l a s s i f i c a t i o na l g o r i t h mp r o p o s e db yj o a c h i m s ，w h i c hi s i no r d e rt os o l v et h el a r g e s c a l ep r o b l e mw i t hs p a r s es t r u c t u r e i nt h ep a p e r ，w ep r o p o s et w o c o n s t r a i n td e l e t er u l e sw h i c hc a nd e l e t et h ec o n s t r a i n t so fn ou s e t h ea l g o r i t h mw ep r o p o s e a i m sa 童f i n d i n gas m a l ls e to fc o n s t r a i n t sf r o mt h ef u l l s i z e do p t i m i z a t i o np r o b l e mt h a te n s u r e s as u f f i c i e n t l ya c c u r a t es o l u t i o n m o r ep r e c i s e l y ，w ew i l lc o n s t r u c tan e s t e ds e q u e n c eo f s u c c e s s i v e l yt i g h t e rr e l a x a t i o n so ft h eo r i g i n a lp r o b l e mu s i n gc u t t i n gp l a n em e t h o d w ew i l l s h o wt h a tt h i si sav a l i ds t r a t e g y ，s i n c et h e r ea l w a y se x i s t sap o l y n o m i a ls i z e ds u b s e to f c o n s t r a i n t ss ot h a tt h es o l u t i o no ft h er e l a x e dp r o b l e md e f i n e db yt h i ss u b s e tf u l f i l l sa l l c o n s t r a i n t sf r o mt h ef u l lo p t i m i z a t i o np r o b l e mu pt oap r e c i s i o ne t h ei m p l e m e n t a t i o no ft h e a l t e r n a t i v ea l g o r i t h mi sp r o v e dt h a tw h a tw eh a v ed o n eh a sb e t t e rp e r f o r m a n c et h a nt h ep r i m a l a l g o r i t h m k e yw o r d s ：a n a l y t i cc e n t e r ；c u t t i n gp l a n em e t h o d ；s u p p o dv e c t o r m a c h i n e ；l a r g e s c a l ep r o b l e m 一王羔_ 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他己申请 学位或其他用途使用过的成果。与我一溺工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 作者签名： 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本q - 位论文。 学位论文肌二邋整拉壹竺塑圭丝坠釜董墼： 作孝基名：羔蓄鎏考l 聿k 二日期：肆年月上日 导师签名：二萎髦善- 0 汪日期：霍蚪t 丹乙曲 一玄 l 、b 大连瑾工大学硕学位论文 1 绪论 1 1 支持向量机的概念 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) t l - s 是c o r t e s 和v a p n i k t l j 于19 9 5 年首先 提出的，它在解狭小样本、，菲线性及离维模式识别中表现出许多特有的优势，并能够推 广应用到函数拟合、回妇分析等其他机器学习问题中。 s v m 是建立在统计学习理论( s t a t i s t i c a ll e a r n i n g + t h e o r y , s l t ) i 3 的v c 维理论和结构 风险最小化原理基础上的，根据有限的样本信息在模型的复杂性( 即对特定训练样本的 学习精度) 和学习能力( 即无错误地识别任意样本的能力) 之间寻求最佳折衷，以期获 得最好的推广能力( 或称泛化能力) 。 v a p n i k 是统计机器学习的创始人，他出版的( ( s t a t i s t i c a ll e a r n i n gt h e o r y ) ) 1 3 1 是本 完整阐述统计机器学习思想的名著。该书详绷论述了统计机器学习之所以区别予传统机 器学习的本质，就在于统计机器学习能够精确的给出学习效果，能够解答需要的样本数 等一系列阉题。统计机器学习具有坚实的理论基础，丽传统的机器学习方法( 铡如：感 知器、神经网络等) 基本上属于摸着石头过河。用传统的机器学习方法构造分类系统完 全成了一种技巧，一个入做的结果可能很好，另一个人用差不多的方法做出来却很差， 缺乏指导和原则。 所谓v c 维是对函数类的一种度量，可以简单的理解为问题的复杂程度，v c 维越 高，一个问题就越复杂。正是因为s v ! 一t 的是v c 维，后面我们可以看到，s v m 解 决问题的时候和样本的维数是无关的( 甚至样本是上万维的都可以，这使得s v m 很适 合焉来解决文本分类的阉题。姿然，有这样的能力是因为孳| 入了核函数) 。 机器学羽本质上就是一种对问题真实模型的逼近( 我们选择一个比较好的近似模 型，这个近徽模型就器罅徽一个鬏设 ，僮毫无疑问，真实模型一般是不知道的，既然真 实模型不知道，那么我们选择的假设与问题真实解之间究竟有多大差距就无法得知。 假设解与真实解的误差，就瑟珥做风险。我们选择了一个假设之后( 更直观地说，得 到了个分类器以后) ，真实误差无从得知，但我们可以用某些可以计算的量来逼近它。 最直观的想法就是使用分类器在样本数据上的分类的结果与真实结果( 因为样本是已经 标注过的数据，是准确的数据) 之间的差值来表示。这个差值烈镘经验熙险r e m p ( w ) 。 以前的机器学习方法都把经验风险最小化作为目标，但后来发现很多分类函数能够在样 本集上轻易达到1 0 0 的正确率，在寞实分类时却塌糊涂( 酃爨谓的推广能力差，或 泛化能力差) 。 一种基于解析中心割平面法的分类算法 此时的情况便是选择了一个足够复杂的分类函数( 它的v c 维很高) ，能够精确的 记住每一个样本，但对样本之外的数据一律分类错误。回顾经验风险最小化原则就会发 现，此原则适用的前提是经验风险要确实能够逼近真实风险才行，但实际上能逼近么? 答案是不能，因为样本数相对于现实世界要分类的文本数来说简直九牛一毛，经验风险 最小化原则只在这占很小比例的样本上做到没有误差，当然不能保证在更大比例的真实 文本上也没有误差。 统计学习因此而引入了泛化误差界的概念，就是指真实风险应该由两部分内容刻 画，一是经验风险，代表了分类器在给定样本上的误差；二是置信风险，代表了我们在 多大程度上可以信任分类器在未知文本上分类的结果。很显然，置信风险是没有办法精 确计算的，因此只能给出一个估计的区间，也使得整个误差只能计算上界，而无法计算 准确的值( 所以叫做泛化误差界，而不叫泛化误差) 。 置信风险与两个量有关，一是样本数量，显然给定的样本数量越大，学习结果越有 可能正确，置信风险越小；二是分类函数的v c 维，显然v c 维越大，推广能力越差， 置信风险会变大。 泛化误差界的公式为： r ( 叻r e m p ( w ) + 由( 等) ( 1 1 ) ，2 公式中冗( 计就是真实风险，r e m p ( w ) 就是经验风险，( ；) 就是置信风险。统计学 ，z 习的目标从经验风险最小化变为了寻求经验风险与置信风险的和最小，即结构风险最 小。 上面大概介绍了s v m 的理论背景，下面简单介绍s v m 的几个主要优点： 1 它是专门针对有限样本情况的，其目标是得到现有信息下的最优解而不仅仅是样 本数趋于无穷大时的最优值； 2 算法最终将转化成为一个二次型寻优问题，从理论上说，得到的将是全局最优点， 解决了在神经网络方法中无法避免的局部极值问题； 3 算法将实际问题通过非线性变换转换到高维的特征空间( f e a t u r es p a c e ) ，在高维 空间中构造线性判别函数来实现原空间中的非线性判别函数，特殊性质能保证机器有较 好的推广能力，同时它巧妙地解决了维数问题，其算法复杂度与样本维数无关。 本文主要考虑用线性支持向量机( l i n e a rs u p p o r tv e c t o rm a c h i n e s ，s v m s ) 解决二分 类问题，没有用到核函数，所以下面我们主要介绍线性支持向量机下可分与不可分的情 大连理工大学硕士学位论文 况，简单介绍非线性的情况。二分类问题是分类问题中一类重要的基本问题，它可以描 述如下：任给一个训练样本集丁= ( x ，y 。) ，( x 。，虬) ，其中 1 1 i ，吼，只 - 1 ，1 ) ，f - - 1 ，2 ，刀，以为样本个数，n 为特征个数，( 墨，以) 被称为第f 个模 式。我们的任务是要寻找一个最优分类超平面把这些样本点分开。 1 1 1 可分情况下的s v m s 我们用二维平面的情况说明其基本思想：图l 中，方形点和圆形点代表两类样本， 有颜色的点即为支持向量。h 为分类线，h 1 、h 2 分别为过各类中离分类线最近的样本 且平行于分类线的直线，它们之间的距离叫做分类间隔。所谓最优分类线就是要求分类 线不但能将两类正确分开( 训练错误率为o ) ，而且使分类间隔最大。分类线方程为 w 7 x + b = 0 ，对它进行归一化： 只【( 眄) - i - b - i 0 ( 1 2 ) ， 1 此时分类间隔等于，使间隔最大等价于使l lw l l 最小。满足条件( 1 2 ) 且使| 1w l p l | w i i二 最小的分类超平面就叫做最优分类面，h 1 、h 2 上的训练样本点就称作支持向量。 h 1 口 口 图1 1 可分情况 f i g1 1s e p a r a b l ec a s e 我们可得线性可分时分类数学模型： r g m 一种基于解析中心割平面法的分类算法 m i n 2 1w 1 1 2 ( 1 3 ) s f 卫( w 7 x ，+ b ) 1 利用l a g r a n g e 优化方法可以把上述最优分类闯题转化为其对偶闯题，鄂： 母壶善倪隅蹦，冉一；口， s 。a ， = o ( 1 4 ) 口：0 i x , 为与原问题( 1 3 ) 中每个约束条件对应的l a g r a n g e 乘子。这是一个不等式约束下 二次函数寻优的问题，存在唯一解。容易证明，解中将只有一部分( 通常是少部分) a ； 不为零，对应的样本就是支持向量。解( 1 4 ) 得到最优分类函数： 取) = s g n ( w 7 x + b ) = s g n a ( x ，x ) + ( 1 5 ) 式中的求和实际上只对支持向量进行。b 是分类阚值，可以用任一个支持囱量( 满 足( 1 1 ) 中的等号) 求得，或通过两类中任意一对支持向量取中值求得。 1 1 2 不可分情况下的$ v l i s 线性可分情况是s v m 中最为简单的一类，但是实际问题中的样本大都是线性不可 分的，本文所解决的问题的样本正是线性不可分的，所以下面我们详细介绍它的一些特 点。先看一个二维平面上样本线性不可分的示意图： 大连理工大学硕士学位论文 口 口 图1 2 不可分的情况 f i g1 2n o n s e p a r a b l ec a s e o o 图1 2 中黄色那个点，它是方形样本，这单独的一个样本，使得原本可分的问题变 成了不可分的。这样类似的问题( 仅有少数点线性不可分) 叫做“近似线性可分”的问题。 以我们人类的常识来判断，如果有一万个点都符合某种规律( 因而线性可分) ，有一个 点不符合，是不是规则就应该为它而做出修改呢? 其实我们会觉得，更有可能的是， 这个样本点本身就是错误，是噪声。所以我们会简单的忽略这个样本点，仍然使用原来 的分类器，其效果丝毫不受影响。 但这种对噪声的容错性是人的思维带来的，我们要设计的程序却不知道。由于在我 们原来优化问题的表达式中，确实要考虑所有的样本点，在此基础上寻找正负类之间的 最大几何间隔，而几何间隔本身代表的是距离，是非负的，像上面这种有噪声的情况会 使得整个问题无解。这种解法其实也叫做“硬间隔”分类法，因为硬间隔要求所有样本点 都满足和分类平面间的距离必须大于某个值。 因此由上面的例子中也可以看出，硬间隔的分类法结果容易受少数点的控制，这是 很危险的。解决方法也很简单，就是仿照人的思路，允许一些点到分类平面的距离不 满足原先的要求。由于不同的训练集各点的间距尺度不太一样，因此用软间隔( 而不是 几何间隔) 来衡量有利于我们表达形式的简洁。于是我们对样本点引入松弛变量使得程 序有容错性：只( w 7 x ，+ 6 ) 1 一鲁，善，0 。因为松弛变量是非负的，因此最终的结果是要 求间隔可以比1 小。但是当某些点出现这种间隔比1 小的情况时( 这些点也叫离群点) ， 种基于解析中心割平面法的分类算法 意味着我们放弃了对这些点的精确分类，这对我们的分类器来说是种损失。但是放弃这 些点也带来了好处，那就是使分类线不必向这些点的方向移动，因而可以得到更大的几 何间隔( 在低维空间看来，分类边界也更平滑) 。从利弊关系上看，我们得到的分类间 隔越大，好处就越多。则原来的模型就变为： 喵m i 粝n 1 wrw+2詈喜善 ( 1 6 ) w 夤2 0 刀 ，“( 1 6 ) s j v f 1 ，姐) ：只1 ( w 7 x 。+ 6 ) 1 一考， 其中c 惩罚因子，毒松弛变量。 ( 1 6 ) 的对偶问题可表示为： 叩寺晖，y j x a j y j x ；一a ， 叩i 己口， ，；x j 一乞a j s j ：a j 只= o ( 1 7 ) 百 0 5 口c ，f = 1 ，船 对这个模型有下面几点解释： 一，并非所有的样本点都有一个松弛变量与其对应。实际上只有“离群点”才有，或 者也可以这么看，所有没离群的点松弛变量都等于0 ( 对方形类来说，离群点就是在前 面图中，跑到h 2 右侧的那些方形样本点，对圆形类来说，就是跑到i - 1 1 左侧的那些圆 形样本点) 。 二，松弛变量的值实际上标示出了对应的点到底离群有多远，值越大，点就越远。 三，惩罚因子c 决定了你有多重视离群点带来的损失，当所有离群点的松弛变量的 和一定时，你定的c 越大，对目标函数的损失也越大，表示你非常不愿意放弃这些离群 点，最极端的情况是你把c 定为无限大，这样只要一个点离群，目标函数的值马上变成 无限大，就会让问题变成无解，从而退化成了硬间隔问题。 四，惩罚因子c 不是一个变量，整个优化问题在解的时候，c 是一个你必须事先指 定的值，指定这个值以后，解一下，得到一个分类器，然后用测试数据看看结果怎么样， 如果不够好，换一个c 的值，再解次优化问题，得到另一个分类器，再看看效果，如 此就是一个参数寻优的过程。 总之，该优化问题解的过程，就是先试着确定一下w ，也就是确定了图1 2 中的三 条直线，这时观察间隔有多大，离群点有多少，然后把目标函数的值算一算。再换一组 三条直线( 你可以看到，分类的直线位置如果移动了，有些原来离群的点会变得不再离 大连理工大学硕士学位论文 群，而有的本来不离群的点会变成离群点) ，再把目标函数的值算一算，如此往复( 迭 代) ，直到最终找到目标函数最小时的w 。 1 1 3 非线性s v m 国 囝 j 囝 国 o 国 国 图1 3 非线性s v m f i g1 3n o n l i n e a rs v m 非线性s v m 即用线性函数不可能分开，怎样解决非线性支持向量机呢? 可以通过 非线性变换转化为某个高维特征空间中的线性可分问题，并在特征空间中求最优分类 面，这种变换可能比较复杂，因此这种思路在一般情况下不易实现。但是注意到，在上 面的对偶问题( 1 7 ) 中，只涉及训练样本之间的内积运算x j x ；。我们用图1 3 来解释，把 二维空间上的点通过变换映射到三维空间，可以发现原本线性不可分的样本点，可以在 三维空间中线性可分了。一般地，将低维空间线性不可分的点映射到高维空间实现可分， 这就是我们处理非线性问题的方法。构造函数： 圣：x ihz j ( 1 8 ) 这里x 。是低维的输入空间的样本，而z 。是高维特征空间中样本的对应点( 例如： z ，坍一 z 3 ，3 x 2 y ，9 z y ，2 7 x ，2 7 y ，3 x y 2y 3 ) ) 。很显然解决这样的问题是很费时的，对于大 规模问题更是n ph a r d 问题。v a p n i k 通过引入核函数在一定程度上解决了这个难题。 与线性情况类似，非线性s v m 的优化模型可以表示如下： 一种基于解析中心割平面法的分类算法 喵m i 屹nl w 等豁 9 ， j z v i l ，1 ) ：只( w r ( x ，) + 6 ) 1 一鲁 其对偶问题为： m 。i n 圭叩j 咒巧吣；) 7 o ( x j ) 一口， j j 0 a ，c ， ( 1 1 0 ) 口，乃= o 一般来说，精确地表示和计算西( x ) 是很困难的，当然想计算垂( x ；) r 圣( x ；) 就更不容易。但是如果存在一个函数( x ；，x ，) 满足g ( x ，x ，) = 圣( x ，) r 圣( x ，) ，而且这个 函数比较容易计算，则上面的问题就迎刃而解了。我们称具有上述性质的函数k ( x ，y ) 为 核函数。则( 1 1 0 ) 可重写如下： m 。i n 专a , a j y j y j r ( x i , x j ) 一a ， 对于( 1 11 ) 可以运用线性s v m 的方法求解。上面的特点提供了解决些算法可能导 致的“维数灾难”问题的方法：在构造判别函数时，不是对输入空间的样本作非线性变 换，然后在特征空间中求解；而是先在输入空间比较向量( 例如求点积或是某种距离) ， 对结果再作非线性变换( 1 8 ) 。这样，大的工作量将在输入空间而不是在高维特征空间中 完成。 1 2目前国内外s v m 的研究状况 由于s v m 算法有较好的理论基础和它在一些领域的应用中表现出来的优秀的推广 能力，近年来，尽管s v m 算法的性能在计算上存在着一些问题，包括训练速度慢，算 法太复杂以至于难以实现以及预测阶段运算量太大等。但许多关于s v m 算法的研究， 包括算法本身的改进和算法的实际应用瞄2 5 】，都陆续提出。 传统的利用标准二次型优化技术解决对偶问题的方法可能是训练算法慢的主要原 因。首先，s v m 算法需要计算和存储核函数矩阵，当样本数目较大时，需要很大的内 存。例如，当样本点数目超过4 0 0 0 时，若每个元素用8 个字节存储，则存储核函数矩 o c = 。 进一步，令： 最= 瓯n r = x l p ( x ；t o ) o ) ) ( 2 。4 ) 由上面的说魂可知，t o 譬蕞，rc 冀，因诧由上面的方法可以找到一点不同于专， 且使得圈标函数达到最小，同时还有f 0 。 一般地，令， 鼠= ；n 露= p l p 0 ；气q ) o ( 2 5 ) 同时可得气为目标函数在最上的最小值。 一种基于解析中心割平面法的分类算法 通过上面的步骤得到两个序列 气) 和( ) ，如果饥) 中有一个子列收敛到丁，则由 算法的过程可知，单调递增序列 必然在丁点处收敛到某个值f ，且7 - 极为所求的最优 点。 割平面法有如下优点： ( 1 ) 不需要进行线搜索； ( 2 ) 可以解决某些具有结构的大规模复杂问题； ( 3 ) 不需要在每次迭代中都计算目标函数值和所有约束函数值，这就使得它在解决 拥有大量约束的问题上具有很大的优势； ( 4 ) 可以把一个问题分成几个子问题，这些子问题可以被顺序的或同时解决； ( 5 ) 不要求目标函数和约束函数是可微的，可以像解决凸规划问题一样解拟凸问题。 2 3d o a c hi1 1 1 5 的割平面算法 上面两节我们先介绍了一种特殊的大规模问题有结构的大规模稀疏问题，然后 又简单概括了k e l l y 割平面算法的内容。本节我们重点阐述j o a c h i m s 的割平面算、法l 8 | 。 作为t s o c h a n t a r i d i s 的最大问隔模型的一个特例，j o a c h i m s 等人发现如果把一般的二分 类问题的输出部分也看作为有结构的，可以得到与多分类问题相似的优化问题，这样对 解决大规模问题会有很大的帮助，所以他在t s o c h a n t a r i d i s 工作的基础上提出了( 1 6 ) 式 的变形【8 1 ： s t r u c t u r a lc l a s s i f i c a t i o ns v m ( p m m a l ) m i n 扫三w r w + 诺 豇v c o ，1 ) ”：吉w7 善q 聃i 善r l q 一专 1 。 ( 2 6 ) 其中l i t = ( c l ，q ) 0 ，1 ，t 松弛变量毒代表经验风险。与( 1 6 ) 式相比，( 2 ，6 ) 的约束 个数由，z 变为2 ”，而松弛变量的个数由捍变为1 。( 注意：由于分类阀值6 可以用任一个 支持向量( 满足( 1 1 ) 中的等号) 求得，或通过两类中任意一对支持向量取中值求得，所 以这里我们不妨设为o ) 。j o a c h i m s 在参考文献中证明了这两个模型等价： 定理l ：( 2 6 ) 的任何解w 也是( 1 6 ) 的解( 反之亦然) ，且有亭= 丢窑毛。 大连理工大学硕士学位论文 证明：对于( 1 6 ) ，任给一个w ，毫分别司以取得最优值，毫= m a x 0 ，1 一轨w 1 x ；) ) ， 对于( 2 6 ) 来说，任给一个w ，f 的最优值可表示为：善= e m e o a x , l _ f 土1 z i = 1e 一寺善e 弘( w l 。汀。 由于上述表达式中的函数对e 都是线性的，所以它们都可以分别被优化： 血n c = c 搿砖善q - n i = 1 q 弘( w k ) ) = 6 m a x 0 ，：1 1 礼以w l m = i n i n 鲁喜毒佗礼 ni i 因此，两者的目标函数值对于任意的w 都是相等的，随之，它们的最优值也是最小 的。 证毕 这样就可以通过求解( 2 6 ) 来间接解决( 1 6 ) 。为t f 敝( 2 6 ) ，j o a c h i m s 结合s v m s 的 特点和该模型中松弛变量仅有一个的性质引进了k e l l y 割平面法。 a l g o r i t h m1f o rt r a i n i n gc l a s s i f i c a t i o ns v m sv i a ( 2 6 ) 1 i n p u t ：t = ( x l ，乃) ，( x 。，蚝) ) ，c ，e 2 q 卜a 3 r e p e a t 4 ( w ，考) 卜a r g m i n ，脚去w r w + 钟 妣v c 出去w ，喜梆，去喜硝 ，2 z f刀i 5 f a ri = 1 ，nd o 6 q 卜j1 胛k - 1 1 0o t h e r w i s e 7 e n df o r 8 q 卜q u c 9 u n t t - t 去喜q i 1w 厂喜q 咒x ，考+ e 1 0 r e t u r n ( w ， ) a l g o r i t h ml 的目的是通过迭代选择( 2 ，6 ) 约束集中一个充分大的子集q ，来近似代替 整个约束集。算法以q = 开始迭代，先在q 上通过解决子问题的对偶来计算当前迭代 一种基于解析中心割平面法的分类算法 步的最优值( 见第四行) 。接着在第五到八行确定割平面的选择：利用第四行得到的分 类超平面检查所有被分类错误的训练样本，由此得n ( 2 6 ) 约束集中被违反的最严重的那 个约束，用来更新q ，这也是该算法与k e l l e y 割平面算法不同的地方。最后在第九行给 出停止准则：期望风险( 当前分类超平面的训练误差) 不超过经验风险 加上预测精度 e 。j o a c h i m s 证明了a l g o r i t h ml 的时间复杂度为o ( s n ) ，j 稀疏度，并且还证明迭代过程 最多会在m a x e ，等 步后结束( r = m a ) 【，0 x ，l i ) 。 大连理工大学硕士学位论文 3 解析中心割平面算法 设计一个具体的割平面算法的关键在于如何选择试探点。a l g o r i t h m1 继承k e l l y 割 平面算法对试探点的选择，即上一步迭代的最优点。这种方法简单且容易操作，但缺点 也是明显的。第一，它对某些问题效果很好，但对另外一些问题却很差，甚至对于同一 问题的不同形式都会呈现不同的表现。第二，具体实现过程中往往会呈现出极差的时间 复杂度的界。第三，迭代过程容易呈现之字形移动，而不容易收敛到最优点。实践告诉 我们，这种方法对于解决目标函数是由简单函数组合而成的线性规划非常有效。其中， 简单函数是由一些互相分离的多面体函数组成的。而本文所要解决的是一个二次规划问 题，并没有上述的特殊结构，所以我们提出另外一种试探点的选择方法。 3 1翻译空间的解析中心 t b t r a f a l i s 【1 6 】首先提出了翻译空间解析中心的概念。为了很好的阐明这个概念的 基本内容，我们先回顾一下s v m 的雏形感知器算法的基本特征。与s v m 不同， 感知器算法中约束条件的右端为o ，没有优化过程，它的主要任务是对下面的可行性问 题进行求解： ，( w x ；+ b ) 0 ， v 歹- - - 1 ，n( 3 1 ) ( 3 1 ) 0 0 任何一个可行解都对训练样本集t = ( x 。，y 。) ，( x 。，y 。) 作一个分隔。令 w = ( w ，6 ) 贸+ 1 和x ，= ( x ，1 ) 9 1 n + 1 ，感知器可简化为： x w 0 ，w = l ，九( 3 2 ) ( 3 2 ) 中每个不等式左边的系数都对应着权重空间( 即由w 构成的空间) 中的一个超 平面的法向量y ；x ，。这些超平面都是过原点的，从而将权重空间分成了7 1 个半空间。 当把第一个模式( x ，只) 引入到这个线性不等式系统中时，可行解的集合就被限制到 一个+ 1 维的半空间中了。第二个模式( 写，y 2 ) 将会把这个半空间进一步减小到一个顶 点在原点的锥体中，随后引入的模式不改变或者进一步的缩小锥体。一旦所有的模式都 被引入后，整个的训练集的锥体就被确定了。则这个锥体中所有的点w 都是( 3 2 ) 的j 个 可行解，可以看出有无限多个可行解存在，我们的任务就是寻找一个最接近这个锥体的 中心的射线作为最优解。可以发现锥体在原点处是开放的，而最优的解集合是一簇从原 点出发的射线。为了使( 3 2 ) 式可解，我们给出w 一个限n - 一种基于解析中心割平面法的分类算法 三哥7 哥：1 ( 3 3 ) 一ww = li j jl 2 、7 这个约束条件将求解区域限制在一个半径为2 的多维超球面上，这个超球面与( 3 2 ) 式所确定的可行域锥体相交的集合被定义为翻译空间( v e r s i o ns p a c e ) 。通过引入( 3 3 ) ， 我们可以得到唯一最优解，这个最优解就是翻译空间的中心，它同时也对应一个在模式 空间中离两类样本最远的超平面。直接求解这样一个中心点是比较困难的，所以我们用 解析中心来代替它。下面从内点的定义引入解析中心，定义松弛变量f 锨作为衡量当 前最优解距离约束，远近的一个标准，如果当前解违反约束时，s j 为正数：满足约束歹 时，f 将为0 。可行域的一个内点就定义为使所有的约束条件f 都为正数的点。对于可 行域的内点，松弛变量可以表示为： s ，= x ，) w 0 ，v j = 1 ，z( 3 4 ) 如何求解翻译空间的解析中心昵? 实践证明障碍函数：倪+ 专孵满足解析中心的 要求， 西s ) = 一羔1 1 1 ( ；) ，i r = ( i ，) ( 3 5 ) 求解( s ) 的最小值的过程就是求解计算距离所有约束条件最远的点的过程，障碍函 数的最小值点就被定义为翻译空间的解析中。t j ( a n a l y t i cc e n t e r ) t 1 6 1 。 综上可知，解析中心可以通过求解以下的优化问题来得到： n 血( ；) = 一1 1 1 ( ；) 户1 ( 3 ，6 1 5 j 三i r 面：15 j 一ww = l 2 大连理工大学硕士学位论文 例3 1 翻详空间 f i g3 1v e r s i o ns p a c e 图3 1 正是翻译空间在三维空间的几何表示。 3 2 解析中心割平面法 解析中心割平面法( a c c m p ) 是由j l g o f f i n 和j p v i a l 1 7 】提出的，j g o n d z i o ， o d um e r l e1 1 8 】等人把它应用于大规模问题，并得到了很好的实践效果和较好的时间复 杂度，大量数值实验也证明了该方法对不同类型的问题均有很好的效果。其基本思想就 是求解由当前约束确定的多面体的解析中心，并以此作为试探点，代入o r a c l e 中确定返 回的是由约束产生的割平面还是由目标函数产生的割平面。 s b o y d 和l v a a d e n b e r g h e 1 9 1 概括了该算法的内容，下面我们以2 2 节中的记号来 描述该算法： 解析中心割平面算法( a c c m p ) ： 种基于解析中心割平蕊法的分类算法 给定一个包含可行域置的多面体警缸| 磊名b 0 ； k ：= 0 ； 开始迭代 用3 1 节介绍的方法计算由不等式组4 2 壤构成的多瑟体的解析中心茹枞； 用z ( m ) 作为试探点，代入到o r a c l e 中； 如果，o r a c l e 返回的结果是。1 r ，算法终止； 否则，通过添加割平面a t x b 来更新鼠 a + ，= ( 4 ，a r ) r ，玩+ ，篇( b k ，6 ) 丁 如果筑+ 。然 舅f 魂+ 。z k ，) = 彩，算法终止； k ：- - - k 专王。 可以发现，算法串的每步迭代都需要计算多面体的解毒厅牵心，( 3 。6 ) 只绘出求解解柝 中心的模型，并没有给出相应的解法。我们将在第四章的具体问题中介绍如何寻找解析 中心。 a c c m p 的优点在于： ( 1 ) 所求的解析中心可能会落在可行域( s 。) 内，这可以克服k e l l y 割平面法的试探点 都不是可行点( 最后一步除终) 的缺陷。 ( 2 ) 在解析中心点确定割平面可以提高割平面的切割深度，同时也可以加快迭代进 度，铁面控制子闻题的规模。 大连理工大学硕士学位论文 4 改进的s v m 算法 我们所提出的算法的酱的在于在整个约束集中寻找一小规模的起作用约束来保证 充分糙确的解。更准确的说，通过割平面法迭代产生一列连续的原问题约束区域的近似， 其极限正是原约束区域的近似，精度不超过i e 。割平面法被当作约束选择方法。我们将 在后厦证明这是一个可行的策略，因为总是存在约束集中多项式级的子集能近似的代替 所有约束。也意味着剩余的指数级的约束没有必要考虑。这给我们的算法带来了很大的 方便。虽然a l g o r i t h m 王较k e l l y 割平面算法有很大的进步，僵它仍未能克服它的一些 缺点。首先，每步迭代选择的试探点都不是可行点( 除了最后一步) 。其次，随着迭代 的进行，子问题的规模会变得越来越大，而算法并没有给出有效的删除多余约束的方法， 只是当迭代超过1 0 0 步后，删除前5 0 个约束。这两个缺点都直接影响迭代步数。 为了解决上述问题，下面提出一些对策： 第一，由s v m s 的理论知识可知( 2 6 ) 的解是有范围的，所以，我们设计一个足够大 的多面体来包含可行域，然后在这个多面体内进行迭代。 第二，用a c c m p 代替k e l l y 割平面法，这样做的囊的是为了尽快找到可行点，避 免在最优点处呈现之字形移动( z i g z a g g i n g ) 。 第三，= 菇迭代过程中，用解析中心设计删除准则，不断舍弃一些无用的约束。 4 1算法 为了很好的应雳解析中心割平面法，作以下标记： g ， ，考) - l 露w 喜奠鼍一去喜+ 喜( c k ( ，) 0 ，薹扮 q = ( w ，考) i g ，( w ，毒) 0 ，c 。 o ，1 ” f ( w ，考) = 去w 7 w + 嘴 ( 2 6 ) 可行域的近似； 毽= ( w ，善) g ( w ，毒) 艺，v c o ，1 ，”) 则( 2 6 ) 可以简化成下面的形式： m i n 。触f ( w ，毒) s l 。 鬏： ( 4 。1 ) ( 4 2 ) ( 4 3 ) ( 4 。4 ) ( 4 5 ) 一种基于解析中心割平面法的分类算法 a l g o r i t h m1 中第四行第k 步迭代子问题的拉格朗日对偶为一个二次规划问题，我们 称之为： ( q p 子问题) ：m a x 脚a7 j - i a 7 d 人 么 s i 倪，幽= o ( 4 6 ) j = 1 i - i a ，c 兵中， a ：( 口妒，a 。) ，j ：( 业，盟) 。= ( ) 。嫱，巩= d 为原问题的海赛阵。 由s v m s 的基本知识由和( 2 6 ) 的约束条件可知： o w | f 2 - - r ，r = i 血 拓，孚，c r ，o 斟 令： q = ( w ，毒) ：1 1 - i i ：，0 毒1 ) 瓯= ( w ，善) ：- r 1 彬，i = 1 ，n ，0 考1 ) 显然，rc o c s o ，瓯即为包含足的初始多面体。 大连理工大学硕士学位论文 a l g o r i t h m2b a s e do na c c m p l 。i n p u t ：t 一 ( x ，舅) ，( x 。，兑) ，c ， 2 1 n i t ( w 。，彘) = ( o ，0 ) ，e = ( 1 ，1 ) ，k = 0 3 d o 4 ( w 纠，氍州) 卜a r g r n i n 。删f ( w ， ) s l 。s t + 1 = s tf 、g k 5 。卜 1 彭w 飘 1 l0o t h e r w i s e 6 i f ( g 。 ，= l，= l 的时间复杂度为o ( s n ) 。因为d 有七2 个元素，所以d 的复杂度为o ( k 2 s 钆) 。 第八行中解析中心的求解，参照b o y d 9 】的证明可知，其复杂度达到o ( 2 n ) 。 综上可得，对于固定的奄，每一步迭代的时间复杂度为o ( s n ) 证毕 至此，算法框架已给出。但还有两个问题没有解决： 第一，最+ ，中约束的个数非常多，如何删除一些多余的约束，使之变的更加紧凑， 这需要我们制定相应的删除准则。 第二，第十行中提到求解最+ 。的解析中心，这需要给出相应的讨论。 4 2 去掉多余约束 下面考虑如何优化最卅。很显然s + ，是由k + 1 个切割超平面g ，i = 0 ，1 ，2 ，k 与乞( 由 2 n 个简单的超平面组成) 围成的。优化& + 。就要从两个方面考虑：一方面是尽可能多的 大连瑾工大学硕士学位论文 删除咒中多余的简单超平面；另方面制定有效的删除准则来删除那些多余的切割超平 面。第一个方面是很容易的，由于邑是线性蕊数，丽瓯中的约束函数所确定的区域都是 紧致的，利用凸优化极大值的知识，可以把鼠中完全处于 ( w ，毒) l g ( w ，髻) o ) 中的那些 约束去掉。上面的叙述可以转化为在紧致区域上求解个线性函数的最大值的优化问 题： m a x g , ( w , 的 s t ( w ，髻) | 一r 式w ，r ，= l ，二，n ，w ，拦，0 考l 、7 上面的优化问题的约束区域很规则，由线性规划的知识可知最优点必然是约束区域 的某个极点。很显然约束区域有2 个极点，那么如何找到这个极点呢? 我们给出下面的 方法： lr 盟0 够卜融j ( 4 8 ) i 一，o t h e r w i s e 按照上丽的方法得到的极点即是最优点。把最优点代入冒标函数中，如果所得的值 小于0 ，则该超平面可以被删掉。同时再设一个标量： 以卜 ：删除该羹喜超平面 ( 4 9 ) 对于第二个方面，结合解析中心的特点我们设计如下的删除约束的准则： l 这个约束是宙第z 步产生的约束割平面，z 露； 2 仃p 仃7 其中仃为s 帕最大内接超球的半径，即( 4 1 0 ) 问题的目标函数值，卢是 一个固定标量，且0 零l ； 3 这个约束在墨村中不是紧的。 4 3 最q 的解析t o , l , 下面来讨论改进算法中的第十行瓯+ ，的解析中心的求法。经过4 2 节x c s , + ，的优化， 假设筑+ ，可以由下面豹形式来表示： a x b 其中， x = ( w ，髻) ，a 飒珊。+ ，b 织” 则瓯+ ，的解析中心由下面的优化问题确定： 一种基于解析中心割平面法的分类算法 m i n 一l i l ( ) 一 。 i = l s 1 a x + s = b 媳1 0 ) s 0 ，s = ( 焉，s 。) 容易看出解析中心是这样一个点：使得到多面体的各个面的距离的乘积达到最大的 那个点。 在本文中，由于其最优点必处于约束区域的内部，我们把它看作无约束优化问题， 其定义域是一个开多面体： d o