（应用数学专业论文）非标准支持向量机分类误差分析.pdf

中文摘要 摘要 统计学习理论是由v a p o i k 等人提出的一种有效的样本学习下的理论 支持向 j i 机是该理论的一个成功实现 学习理论中有限数f i 的观测l p l jw l 练样本是根据样 本空间中的未知概率分布随机独立抽取的 然后 对损失函数在该分布下取期望 值 这就是标准支持向量机的思想 然而许多实际问题中往往需要处理非标准情 形的问题 因此将学习算法推广到非标准的情形具有重要的实际意义 本文基于分类问题研究了非标准支持向量机学习算法的收敛性 得到了较为 满意的结果 针对两分类问题 重点分析了非标准支持向量机基于t d r h o n o v 正则 化学习算法的一致收敛性和相对一致收敛性及其推广性误差的界 第一部分主要介绍了非标准支持向i i 机的背景知识及支持向j i 机的预备知识 第二部分阐述了支持向量机的基本思想及相关内容 第三部分着重研究了在矾b 0 v 正则化意义下的非标准支持向量机1 范效软间 隔分类器的分类误差 并给出了其推广误差的界 并进一步分析了其相对一致收 敛性 得到了较好的结果 第四部分将非标准支持向量机推广到多类分类问题 第五部分分析了前面得到的主要结果 并对未来进一步的研究方向进行了展望 关键词 非标准支持向量机 正则化 相对一致收敛性 核方法 再生核希尔伯特 空间 湖北大学硕士学位论文 a b s t r a c t 1 1 地s t a t i s t i c a ll e a r n i n gt h e o r yp r o p o s e db yv a p n i ke ta 1 i sa l le f f e c t i v el e a r n i n gt h e o r y r 1 1 忙s u p p o r tv e c t o rm a c h i n e s s v m s li st h es u c c e s s f u lr e a l i z a t i o no ft h i st h e o r y 1 1 t r a i n i n gd a t e si nt h el e a r n i n gt h e o r ya l ei n d e p e n d e n ta n di d e n t i c a l l yd i s t r i b u t e d d r a w e ra c c o r d i n gt oau n k n o w np r o b a b i l i t yd i s t r i b u t i o n t h e nt ot h el o s sf u n c t i o na n d e rt h i sd i s t r i b u t i o nt a r et h ee x p e c t e dv a l u e 1 1 l i si st h ei d e ao ft h es t a n d a r ds u p p o r t v e c t o rm a c h i n e s m a n yr e a lw o r l ds i t u a t i o n s h o w e v e r a r en o n s t a n d a r d i nt h a tm o d e l i sn o tv a l i df o rt h o s es i t u a t i o n s i ti se s s e n t i a lt op r o m o t et h el e a r n i n ga l g o r i t h mt ot h e n o n s t a n d a r ds i t u a t i o n s i nt h i sa r t i c l e w es t u d yt h ec o n v e r g e n c eo ft h el e a r n i n ga l g o r i t h mb a s eo nt h e c l a s s i f i c a t i o np r o b l e mi nt h en o n s t a n d a r ds i t u a t i o n s s p e c i a l ly w ea n a l y z et h eu n i f o r m c o n v e r g e n c ea n dt h er e l a t i v eu n i f o r mc o n v e r g e n c eo ft h en o n s t a n d a r ds u p p o r tv e c t o r m a c h i n e sb yi i 他a l r so ft h et t k h o n o vr e g u l a r i z a t i o na l g o f i t h ma n do b t a i nt h eg e n e r a l i z a o o nb o u n d sf o c u so nb i n a r yc l a s s i f i c a t i o np r o b l e m s i n t h e f i r s t p a r t w e b r i e f t h e b a s i c t h e o r y o f n o n s t a n d a r ds u p p o r t v e o t o r m a c h i n e s a n d0 u n i n et h eb a s i so fs v m i n t h es e c o n d p a n w e b r i e f t h e b a s i s o f t h es u p p o r t v c c t o r m a c h i n e s 1 1 t h i r dp a r ti st h ei m p o r t a n c eo ft h i sa r t i c l e i nt h i sp a r t w es t u o yt h ec o n v e r g e n c eo ft h er e g u l a r i z a t i o na l g o r i t h mb a s eo nt h e t h ec l a s s i f i c a t i o np r o b l e m a tf i r s t w es t u d yt h ee r r o ra n a l y s i so ft h es v m1 n o r ms o f tm a r g i nc l a s s i f i e ra n do b t a i nt h e b o u n do f i t sg e n e r a l i z a t i o ni 口 r o r i nt h es e c o n d w ef u r t h e rs t u d yo ni t sr e l a t i v eu n i f o r m c o n v e r g e n c e a n do b t a i ns a t i s f i e dr e s u l t t h e n i np a r tf o u r e x t e n s i o nt ot h en o n s t a n d a r dm u l t i e a t e g o r ys i t u a t i o n s f i n a l l y i np a r tf i v e w ca n a l y z et h em a i nr e s u l t sg o ti np r e v i o u sp a r t sa n dg i v ea p r o s p e c tf o rf l l n h e rr e s e a r c h k e yw o r d s n o n s t a n d a r ds u p p o r tv e c t o rm a c h i n e s r e g u l a r i z a t i o n r e l a t i v et m i f o r mc o n v e r g e n c e k e r c e rm e t h o d r e p r o d u c i n gk e r n e lh i i b e r ts p a c e 一 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明 所呈交的学位论文是本人在导师的指导下独立进行研究所 取得的研究成果 除了文中特别加以标注引用的内容外 本论文不包含任何其 他个人或集体已经发表或撰写的成果作品 对本文的研究做出重要贡献的个人 和集体 均已在文中以明确方式标明 本人完全意识到本声明的法律后果由本 人承担 论文作者签名 1 琵辛q 平 签名日期 硐年乡月f 6 日 学位论文使用授权说明 本学位论文作者完全了解学校关于保留 使用学位论文的规定 即 按照学校要求提交学位论文的印刷本和电子版本 学校有权保存学位论文 的印刷本和电子版 并提供目录检索与阅览服务 学校可以采用影印 缩印 数字化或其它复制手段保存论文 在不以赢利为目的的前提下 学校可以公开 学位论文的部分或全部内容 保密论文在解密后遵守此规定 论文作者签名 岱铀斗 签名日期 问够月f g 日 导师签名 签名e t 期 柱隍 垆珀 貊 第一章引言 第一章引言 学习问题是指依据经验数据选取所期望的依赖关系的问题 模式识别 函效 拟合以及概率估计等都属于数据学习的问题 传统统计学研究的是样本数目趋 向无穷大时的渐近理论 现有的学习方法也多是基于此假设 但在实际问题中样 本数目往往是有限的 因此一些理论上很优秀的学习方法在解决实际问题时的 表现却可能不尽如人意 统计学习理论是f 1 日v a l m i k 等人提出的一种小样本统计理 论 1 1 着重研究在小样本情况下的统计规律以及学习方法性质 统计学习理论为 机器学习问题建立了一个较好的理论框架 也发展了一种通用学习算法 支持向 i 机 能够较好的解决小样本学习问题 目前 统计学习理论和s v m 已经成为机 器学习领域的研究热点 2 i 1 1 学习问题简介 学习问题中 最优分类器的优化目标函数是期望风险 但是由于我们可以利 用的信息只有有限的样本 期望风险公式中的积分无法计算 因此传统的学习方 法中采用经验风险最小化 e r i v l i 拘准则 并设计算法使其最小 事实上 用e r m 准 则来代替期望风险最小并没有经过充分的理论论证 只是直观上合理的做法 尽 管可以假定在样本数目趋向于无穷大时经验风险趋近于期望风险 但在解决真实 问题时却并非如此 此外 用经验风险最小做为学习算法的目标会带来过学习的问题 产生这一 问题的原因有二个 一是样本不充分 二是学习机器的设计不合理 而且这两个问 题是相互关联的 为了使经验最小 学习系统总可以找到一个足够复杂的模型去 拟合巳知样本 甚至使经验风险为零 但是 过分复杂的模型极为依赖训练样本 丧失了推广能力 而且有限的训练样本往往并不能充分反映真实总体分布 所以 对未知的测试样本并不能作出较好的预测 可见 学习机器的复杂性与推广性之 间存在这一个根本性的矛盾 研究经验风险与真实风险的关系 以及判决风险与学习机器复杂性之间的关 系是统计学习理论的基本内容 为了研究以上问题 统计学习理论定义了一系列有关函数集学习能力的指 标 其中最重要的是v c 维 函数集的v c 维被定义为它所能打散的最大样本数目 所谓 打散 是指存在h 个样本能够被函数集中的函数按所有可能的2 种方式分 湖北大学硕士学位论文 开 v c 维反映了函数集的学习能力 v c 维越大则学习机器越复杂 统计学习理论中另一重要研究是分析了对于各种类型函数集 经验和实际风 险之间的关系 即推广性的界 对于两类分类的问题 结论是 对指示函数集中的所有函数 经验风 险r 和实际风险r 叫 之间至少1 一吁的概率满足 r w 冠q 叫 圣 h n 其中 是函数集的v c 维 n 是样本数 这一结论从理论上说明了学习机器的实 际风险是由两部分组成的 一是经验风险 另一部分称为置信范围 它和学习机 器的v c 维以及训练样本数有关 上式说明 在有限样本训练下 学习机器的v c 维 越高 复杂性越高 则置信范围越大 导致真实风险与经验风险之间可能的差别越 大 这就解释了为什么会出现过学习的现象 更有意义的是 上式说明机器学习过 程中不但要使经验风险最小 还要使v c 维尽量小以缩小置信范围 才能取得较小 的实际风险 即对未知样本有较好的推广性 从以上分析可知经验风险最小化准则在样本有限时是不合理的 统计学习理 论提出了一种被成为结构风险最 n s r m 的思想来解决这一问题 具体细节请参 考 l 在此不赘述 需要指出的是 实现s m r 的一种思路是设计函数集的某种结 构使得每个子集中都能取得最小的经验风险 然后只需选择适当的子集使得置信 范围最小 则这个子集中使经验风险最小的函数就是最优函数 支持向量机方法 实际上就是这种思想的具体实现 1 2 背景知识 支持向量机是统计学习理论中最年轻的内容 也是最实用的部分 目前仍在 不断发展之中 支持向j i 机是从线性可分情况下的最优分类面发展而来的 在这 一简单情况下 s v m 分类器实际上是把一个正负样本分离开来的分界线 在多维 情况下是超平面 定义正负样本到分类线的最短距离为分类间距m 所谓最优 分类就是要求分类线不但能将两类样本正确分开 而且使分类间距最大 如果定 义s v m 分类器的输出函数为 t 伽 z b 2 第一章引言 其中 z 是输入向 i 伽是法向 i 6 是直线截距 则分类线可表示为 埘 z b 0 由于同一条直线的表达形式不唯一 对分类线方程归一化 使得分类间距处的正 负样本满足让 l 一1 从而分类间距是m 向 可知最优分类线应当满足分 类间距m 最大 所以目标函数可以表示为 号挚 o 旷 t v i 玑 埘 而一6 l 1 1 其中弘是训练样本的类别标签 正样本 1 负样本 一1 由于s 分类器的 输出是u 加 z 一6 所以约束条件的实质是要求对训练样本都能正确分类 一般的 采用拉各朗日优化算法把上述最优分类面问题转化为对偶问题其 目标函数仅仅决定于拉各朗日乘子的集合啦 满足约束 咤n 似 呼 1 j f f i l n刚岫h n 一萎啦 1 2 玑啦 o v i n m l 其中 为训练样本个数 一旦通过训练算法得到 就可以计算出法向量加和截 距b b 衄 毛一们 v 啦 o 以上讨论都是在线性可分的情况下展开的 然而在通常情况下并不能找到一个平 面完全把正负样本分离开来 v a p n i k 在1 9 9 5 年建议为目标函数 1 1 添加松弛系数来解决上述问题 3 修改 之后的目标函数将容忍错分情况的发生 同时又对一个样本点穿越分类面的错误 3 甄 驰 l 叫 湖北大学硕士学位论文 进行不同程度的惩罚 新的目标函数为 满足约束 勃训z e n 啦 址 i 1 挑 伽 龟一b 1 6 v i 1 3 其中矗为松弛变量 其实质为表示该对应样本点偏离分类面的程度 c 为惩罚因 子 这一参数的选取体现了保持尽量宽的分类间距和容忍一定数量的分类错误这 两种选择之间的折衷 同样可以把 1 3 式转为对偶形式 其与 1 2 的区别仅仅在 于约束条件改变为 0 啦 gv 啦 注意到目标函数 1 2 中计算两个样本点之间的距离计算是采用内积运算 如 果此内积是采用欧式空间的距离则得到线性分类器 如果选取其他的内积形式则 可以把s v m 分类器进一步推广为非线性分离器 这种内积经常表示为 z f k 被称为核函数 事实上 核函数表述的不是在样本空间的距离关系 而是表示在 一高维空间中的距离关系 这样的原因在于 在低维的样本空间中的不可分总是 在某一个高维空间可分的 核函数是用原空间中的函数来表述在这个高维空间中 样本之间的距离 同时 这种处理方法又避免了去直接求取那一个从低维到高维 映射的困难 典型的核函数包括多项式函数以及高斯函数等 另外 并不是每一种 函数都可以表示这种非线性距离关系 一般需要满足m e r c e r 条件 4 引入核函数之后 s v m 分类器的输出可以表示为 4 6一 功 巧 哟鲫 问 u 第一章引言 目标函数的对偶形式是 满足约束 nnn 呼妒 口 2 呼 善 玑协 巧 啦哟一善啦 1 4 v i 0 啦 g 矾q o l 上式 1 4 目标是一个二次优化问题 而k a n 雎l 卜豳l h i 卜1 l c k c f 订 条件是二次优 化问题的充分必要条件 由此 1 4 o e 的约束条件可以改写为 瞄a 黧 由于k k t 条件每次只操作一个样本点 所以有效的利用k k t 条件对于加 速s v m 分类器训练过程是十分有意义的 由上可知 原来的s v m 算法优化的目标可以认为是总的识别错误率 对于错 误接受和错误拒绝两种错误率之间的关系并没有加以约束 然而 在实际应用中 两类错误类的关系是极为重要的 例如在身份认证系统中一般认为错误接受比错 误拒绝后果更为严重 错误拒绝率略高只是为用户使用带来了一些不便 而错误 率偏高则会使冒充者成功登录 造成用户数据的泄密 所以 尽管原来的s v m 训 练算法有着较好的推广能力 却与实际应用中的许多问题的特殊要求不相适应 为此 我们用非标准s v m 来解决这一问题 现实生活中的许多分类问题中不同类别的错分误差一般并不相等 主要有以 下几个原因 一不同样本点的损失 代价 不同 不同类型的错分有不同的损失 二 存在采样偏差 三样本空间的分布与训练样本的分布有差异 通常把在这三种情 形称为非标准情形 近来 i j ny i 等分析了前两种非标准情形下贝叶斯决策规则的形式 证明了 其与标准情形下两分类问题中贝叶斯规则的联系 本文 在l i ny i 等给出的非标准 分类情形的框架下 着重分析了错分代价不同时基于1 设h o n o v 正则化意义下的非 5 湖北大学硕士学位论文 标准s v i v l 的分类误差 并给出了其推广误差的界 对于口一范数支持向耐机及其特 例2 一范数支持向量机软间隔分类器的错分误差 d i r o n gc h e n 等已经给出了较好 的分析 这里只就1 一范数软间隔分类器的错分误差进行分析 得到了其一致收敛 性的界 为了对错分误差进行更为全面的分析 进一步对其进行了相对一致收敛 性的分析 得到了较为满意的结果 同时考虑错分损失不同及存在采样偏差情形 下的多类分类非标准支持向量机 1 3 预备知识 1 3 1 正则化方法 f g i r o s i 等研究表明 从样本学习的问题可被视为从稀疏数据进行多变量的 函数逼近 这一问题可表示为 依据某固定但未知的概率分布函数f z 暑 独立抽 取样本集 0 l 讥 z 2 暑1 2 x t 讹 由此样本信息获得未知函数 的最佳逼近 一般说来 这是一个不适定问题 于 是 a n t t k h o n o v 等人提出了解决不适定问题的方法 一种方法是v v i v a n o v 提 出的拟解的方法 5 另一种是t l k h o n o v 提出的正则化方法 6 这两种方法都对函 数集的容量进行了控制 即这两种方法都执行了结构风险最小化原则 在2 0 世纪3 0 年代 当r f i s h e r 提出他的理论体系时 不适定问题的概念还没有 发展起来 直n 2 0 世纪印年代才发展起来 不适定问题理论中主要发现了这样一 个事实 即存在很广泛的一类问题 它们的形式化的解存在 却不能用有限的资 源 计算机资源和信息资源 得到 如事件模型的辨识问题属于不适定问题 这是 在快速计算机诞生的2 0 世纪6 0 年代被发现的 人们发现 f i s h e r 的应用统计学对于 解决高维问题来说不是一个合适的工具 因为它存在 雏数灾难 问题 7 不适定问题的数字语言表述为 对于算子方程 a f t f z 一6 1 5 第一章引言 如果方程右端f z f z 叩 发生微小变化 只会引起解的微小变化 即如果对任 意s 存在j e 使得只要不等式 p 易 f 扛 m f 扛 2 6 e 成立 不等式 p e x f t t j l l t 啦 一定成立 我们称算子方程 1 5 髑解是稳定的 其中历和易表示距离分别定义在 度量空间局和b 中 算子方程 1 5 冬空间蜀中的函数映射到空间易中的函数 若方程 1 5 的解是存在的 唯一的且稳定的 我们称解算子方程 1 5 的问题 在h a d a m a r d 意义下是适定的 8 1 如果方程的解至少有一条不满足上述三条 则解 算子方程的问题就是不适定的 在学习理论中 我们考虑算子方程的解存在 唯一 但不稳定的这一类不适定问题 t i d m n o v 等于1 9 6 3 年提出了解决不适定问题的方法一正则化方法1 9 1 0 1 1 1 假设要解 到 韵连续一对一映射算子j 4 定义的算子方程 a f f 1 d 并假设方程 1 妨的解存在 正则化泛函 是一个半连续的正泛函 且 c c o 是紧的 在定 义域d w i i f 泛函w 取非负实数 函数集f f 是方程的解域 i f 贝u 化的思想是将最小化某一泛函的一个元素作为方程 1 6 的解 该琵函不 是泛函 p 见 a f 而是一个改进的泛函 马 f g a f f 7 a d 彤 1 7 其中正则化参数7 0 n k h o 肿v 已经证明了最小化泛函 1 7 n 题是稳定的 即对 于相邻函数f 雨q f 6 其e e p 2 f f 6 s6 特别地在h n b e r t 空 n e 对于线性算子a 我们可以选择泛函 等 fj f j 2 7 一 湖北大学硕士学位论文 常见的两种正则化方法是同d l 彻o v 正则化方法和i v a n o v i f 贝j j 化方法 假设q 一冗 是定义在函数集合 t z f o 0 a 上的一个处罚泛函 于是 i v a n o v 三贝r j 化方法的定义为 岛 z 1 0 a r g m 蚍i nl k p f o 约束条件为 a t z f o c c o 是常数 t d d a o n o v 正则化方法的定义为 厶 z f o a r gr a 日 i n 冠 知 a q 0 一 1 8 其中a o 是一个常数 上述式 1 7 和 1 8 函数n z f o 被称为正则化子 常数n 和a 被称为正则 化参数 它们的取值依赖于样本数目m c c m a a m 正则化方法的基本思想是 在i v a n o v 正则化方法中 当g o o 时 岛 z 一 是 z 如 的一个很好的逼近 在t t k h o n o v i f 贝l j 化方法中 当a 一0 时 以 z f o 也是 2 允 的一个好的逼近 正则化方法中 正则化子n z f o 可以有不同的取法 若咒是由线性函数组 成的 正则化子通常取加权向量的范数 1 2 1 若爿是b 柚 h 或h i l b e f t 空间 正则化 子通常取他们的范数或范数的平方0 3 在核方法研究中 我们通常取 是再生和 希尔伯特空间 其中正则化参数a e 度量了关于正则化子q 的正则化方法输 出函数的规律性 它的选取决定了正则化方法的性质 由于解i v a n o v 正则化方法需要解最优化问题 故本文中 我们只考 虑n l d l o n o v 正则化方法 1 3 2 再生核希尔伯特空间 一个学习机器总是在一定函数集上实现某种算法的 函数集的类型和性质很 大程度上决定着算法实现的难易程度 给定的函数空间称为假设空间 模型函数 集 其中的每个函数均称为假设 核机器学习是现在比较流行的一种机器学习算 法 它的思想是将数据映射到高维的特征空间 寻找特征空间的线性学习机器 而 这种线性学习机器在对偶空间是以特征映射内积的形式出现的 此时内积对应着 原始空间的核函数 通过选择核函数来代替内积后 就隐式地表示了特征映射 在 8 第一章引言 计算时只需计算核函数在成对出现的训练样本上的值 s v m 属于核机器学习的范畴 不过它选择的核为再生核 它的假设空间是由 这个核导出的再生核希尔伯特空间 再生核希尔伯特空间在逼近和正则化理论中 扮演了重要角色 下面将给出定义 定义函数 k xxx 冗 z t 一k x t 记j l t k z t 对每个固定z x j l 是x 上的函数 若k z t k t z 对 所有 z t x x 成立 则称k 是对称的 若 同时关于两个变量连续 则 称 而t 为核函数 定义1 1 设饨为 x 上函数碰l b e r t 空间 若核函数k 满足 1 x 虹 咒 2 忱 x v 7 1 f x j l 则称 为h 的再生核 由定义知 也 鲍 亿 z z z 命题1 1 若函数琢l b e r t 空间咒存在再生核膏 则它是唯一的 证明假定咒存在另外的再生核露 则由k 和露的再生性 得 琏 一亿 1 1 2 懈 一 k 一 a 配一忍 一 玩一忍 觅 恐 t 一元 t 一 虬 t 一亿 t 0 因而 对所有z t x 有j 0 t 也 t 从而 z t 霞 z t 在k z x 上成 立 命题1 2 函数i f i l b e r t 空间咒存在再生核 的充分必要条件是 对每个卫 x 点泛函疋 z 是 上的连续泛函 9 湖北大学硕士学位论文 证明若咒上存在再生核函数 则由再生核性质 1 6 z f i i 圳 l 霉 恐 t si l f l l i g t t z z 钏川 反之 若瓦是 上的连续泛函 由r i e s z 表示定理 存在如 咒使得 z 如 v f 7 称k x t 如 t 则k 是咒的再生核 定义1 2 设函数k x x r 满足条件 1 是对称的 e p k x z k x 功忱 一 x 2 对任商b l z 2 x g r 鲫l 矩阵k k l 满足z r j 白 0 则称 为正定核 若k 是连续对称正定的 则称其为m e r e e r 核 m e r e e r 核具有下面两个性质 1 m e r c e r 核是非负的 2 u k u u k 口 定义1 3 设xc 为紧集 假定x 上函数碰l b e r t 空间爿存在再生核e 且j 厶 x 线性组合在 中稠密 即 s p a n k z x 则称 为再生核希尔伯特空间 g e p r o d u c i n gk e r n e lh i l b e r ts p a c e 简写为 褂 i s 定理1 1 设函数k x x 一冗是m 鳅珂核 则存在定义在 x 上的连续函 数组成的希尔伯特空间w 满足下列性质 v t x v 何 萑f f x i 配 f 1 0 第一章引言 我们把这个性质称为再生性 满足再生性的核被称为再生核 不难得到m 饿盯核 为再生核 把咒 称作由k 导出的再生核希尔伯特空间 下面考察咒 的结构 令k xx x 一冗是m 朗嘟核 定义积分算子 t k lk b 固 q 令凡和氟 z 分别是 的特征值和特征函数 根据m 嘲定理有 令嘭 z 廊 z 则 k z z 7 包 z 奶 z j l r 他 q 奶 z j 1 在 中定义内积 奶 z 如包 z 爿 勾屯 j lj 1j l 则 关于上面定义的内积是一个r 璐 即 是由核 导出的再生核希尔伯特空 间咒肛不难验证再生性成立 z k x h 哟奶 z 包 一 奶 z h j 1j 1 q 奶 一 一 j l 对丁中的函数 功 嚣l 哟包 若令 n 1 o n 妒 z 也 z 也 z 机 z 湖北大学硕士学位论文 则 z 可以表示为 z u 妒 茁 的形式 把定义在x 上的映射 妒 妒 z 1 z 如 z 妒k z 称为特征映射 把丁称为特征空间 若q 1 m 九 z 此时 n 扛 嘶奶 毛 奶o i 1t 1 n0 0 啦 九 卸 也 功 i f f i l i f f i l n 啦k 马戤 即 z 可以写成 功 la k x 以 的表示形式 我们称 z 的这种表示形式 为 的对偶表示 基于核的学习算法的思想是将原问题转化到对偶空间求解 从而讲解转化为对偶表示 这为计算提供了很大的方便 1 4 本论文的主要工作及内容安排 本论文的主要工作是基于 l d l o n o v 正则化方法研究了两分类非标准支持向 苗机的分类误差 得到了其推广误差的界 文章的第一部分主要介绍了非标准支 持向 l 机的背景知识 及支持向艟机的预备知识 第二部分阐述了支持向 l 机的 基本思想 及支持向量机算法的研究现状 第三部分是本文的重点部分 在q i 蛆g w u 1 4 1 的基础上在t t k h o n o v 正则化意义下进行了非标准支持向量机的两分类误 差分析 得到了其一致收敛性的界 并进一步研究了其相对一致收敛性 使得误差 分析更趋于完善 第四部分研究了多分类非标准支持向量机 应用 一对余 支持 向量机方法 给出了非标准支持向量机在多分类问题中表现形式 最后 第五部分 分析了前面所得到的主要结果 并对未来进一步的研究方向进行了展望 1 2 第二章支持向量机 2 t 支持向量机简介 第二章支持向量机 支持向付机算法由贝尔实验室的v a m i k 及 其合作者提出的一类基于统计学 习理论新型机器学习方法 l 它建立在统计学习理论的v c 维理论和结构风险最 小化原则基础上 根据有限样本信息的模型的复杂性和学习能力之间寻求最佳折 衷以期获得最好韵推广能力 s v m 是统计学习理论的一种成功实现 其在模式识 别 函数逼近 信号预测 信息融合等领域 已得到了广泛应用 很多学者认为 它 正成为继模式识别和神经网络研究之后机器学习领域新的研究热点 并将推动机 器学习理论和技术豹重大发展 在2 0 世纪蚰年代后期支持向 i 机更是得到了全面深入的发展 现已成为机器 学习和数据挖掘领域的标准工具 主要原因之一是s v m 是机器学习领域若干标 准技术的集大成者 它集成了最大间隔超平面 m e 虻盯核 凸二次优化 稀疏解和 松弛变量等技术 在若干挑战性的应用中获得了目前为止最好的性能 在美国科 学杂志上 s v m 及核方法被认为是 机器学习领域非常流行的方法和成功的例子 并是一个令人瞩目的发展方向 近年来 v m 的理论已经取得了重大进展 其算 法实现策略及实际应用也发展迅速 可以确信 该技术阿研究已发展成为机器学 习中一个独立的领域 在理论和实践两方面都有着光明的前景 支持向j i 机方法的主要优点有 1 它是专门针对有限样本的情况的 其目标是得到现有信息下的最优解而不 仅仅是样本数趋于无穷大时的最优解 2 算法最终将转化为一个二次型寻优问题 从理论上说 得到的将是全局最优 点 解决了在神经网络方法中无法避免的局部极值问题 3 算法将实际问题通过非线性变换到高维的特征空间 在高维特征空间中构 造线性判别函数来实现原空间的非线性判别函数 特殊性质能保证机器有 较好的推广能力 同时它又巧妙地解决了维数问题 其算法复杂度与样本维 数无关 在s v m 方法中 只要定义不同的内积函数 就可以实现多项式逼近 贝叶斯 分类器 径向基函数方法 多层感知器网络等许多现有学习算法 1 3 湖北大学硕士学位论文 2 2 支持向量机的思想 支持向量机实现了下列思想 通过事先选择好的某一个非线性变换 将输入 向量z 映射到高维空间z 在这一特征空间中构造一个最优分类超平面 在上面的方法中会出现两个问题 一个概念性问题和一个技术性问题 1 如何找到一个推广能力好的分类超平面 概念性问题 特征空间的维数是 非常高的 分开训练数据的超平面不一定具有好的推广能力 2 计算上如何处理如此高的高维空间 技术性问题 为了在2 0 0 维空间中构造 一个4 阶或5 阶多项式 必须在数亿维空间中构造超平面 如何才能克服 罐数灾 难 问题呢 这一问题的概念部分可以通过构造最优超平面来解决 根据最优超平面的统 计性质 如果我们能够以训练样本的最大范数和间隔的比值的平方的一个小的期 望或以支持向量数的一个小的期望来构造最优超平面 则所构造的超平面的推广 能力是好的 但是 即使最优超平面具有好的推广能力并可以从理论上找到它 如何处理 高维特征空间的技术问题依然存在 然而 应注意的是 对于特征空间z 中构造最 优分类超平面 我们并不需要以显式形式考虑特征空间 我们仅仅需要计算支持 向量与特征空间的向量之间的内积 我们考虑 i i i b e r t 空间中内积的一般性质 假定 我们将向量z 舻映射到一 个i i i l l t 空间 其坐标为 z l x z n 功 根据h i l b e t t s c h m i d t 理论 h i l b e r l 空间中的内积有一个等价表达式 0 0 z l 忍 砷磊 z 1 磊 勋 骨k z l z 2 n r 0 r z l 其中 z l z 2 为满足下列条件的对称函数 定理2 1 为了保证一个连续对称函数k t 在l 2 g 空间中有一个含有正系 数的钆 0 的展开式 o o g u 口 口k 钆 u 魂 口 k 一 i 1 4 一 2 1 第二章 支持向量机 即x t t 描述了某一特征空问的内积 充分必要条件为 zz 脚 咖m d u d v 对于所有的g 岛 c 丘y g l c 为舻的一个紧子集 可用于构造支持向 i 机的t m b e n 空间中内积结构的好的性质是 对于满 足m 嘟条件的任何核函数k u 存在一个特征空间协 乱 缸 让 在这 一空间的核函数生成内积 2 1 2 3 构造支持向量机 在 高维 特征空间中生成内积允许我们构造一些决策函数 它们在输入空间 中是非线性的 扛 口 哟n y a k x 而 6 2 2 s v 而它们在特征空间z l z o o i 钆0 中等价于线性决策函数 o 口 s 哲n 肌醒 磊 戤 聋 z 6 wr f f i i 其中 z 盈 是生成特征空间中的内积的核 因此 为了构造分类函数 2 2 我 们可以利用构造线性分类超平面的方法 其中 我们使用由核k z z t 来代替 由 z 戤 定义的内积 i 为了在可分情况玑 而 n 1 下找出系数啦 充要条件是 找出泛函 n 啦一 啦哟鼽协k 盈 句 2 3 j i j 的最大值 约束条件为 口 20 i 1 2 1 1 5 o 玑 以 耐 湖北大学硕士学位论文 2 在不可分的情况下找出最优软间隔解 充分条件是 最大化泛函 2 3 约束 条件是 f 啦矾 0 0 啦 g 1 2 l i f f i l 3 最后 为了对给定的间隔1 a 找出最优解 m 蛳c 霭彘窑批c w 我们必须最大化泛函 约束条件为 l 啦执 o 0 啦 1 江1 2 z 1 构造这一类决策函敷的学习机器称为支持向量机 2 4 最优超平面 2 4 1 最优超平面的概念 给定训练集 z 1 1 锄 y t 缈 y 1 1 若挑 1 则称墨属 于i 类 否则属于i i 类 称集合 z 1 司 可被超平面z c 分离 若存在一个单 位向量鸲一个常数c 使得不等式组 毛 驴 c 妒 槲 再证唯一性 假定 妒 的最大值在两个边界点咖t 与如上达到 则由 妒 的凹 性 对处于这两点连线上任一处的内点 p 的函数值不小于 妒1 我们的目的是寻求构造最优超平面的有效方法 为此考虑该问题的等价形 式 寻找向量妒与常数6 使得 6 l 1 2 5 即 妒 b 1 若协 1 并且向量妒的范数i 训2 砂 妒具有最小值 定理2 3 在限制 2 5 下具有最小范数的向量妒与构成最优超平面的向量 具 有关系 妒 l 妒l 最优超平面与分离向量之间的间隔p 咖 i l l i 证明在限制 2 5 下取得最小范数的砂是唯一的 假定 妒 6 1 与 仍 6 2 满 足限制 2 5 并且两个向量具有相同的最小的范数i 妒1 1 2 i 仍1 2 则对任意a 0 1 可知 a 妒1 t 1 一a 如 撕 1 一a 池 满足 2 5 的限制 但j a 砂l i 1 一a 仍1 2 l l e l 构造一个新向量矿 州p 纠 由假 设则有i 矿l z p o 由于最优超平面与优化问题中的目标函数 2 8 都不是依赖向量z 的维效而是 两个向量的内积 故我们可以在高维空间甚至是无穷维h i l l 犯r t 空间中构造分类超 平面 这正克服了所谓的维数灾难 1 5 j 应该注意的 虽然最优超平面是唯一的 即确定最优超平面的向量妒与常 数6 是唯一的 但是1 f 关于支持向量的展式并不唯一 1 6 1 2 与支持向量机分类 支持向量机是从线性可分情况下的最优分类面发展而来的 对于线性不可分 的二值分类问题 用s v m 方法也可以找到一个最优分类面 使得两类无错误的分 开 并使得两类的分类间隔最大 设训练样本集为 毛 玑 1 2 毋 式中 为输入值 戤 舻 肌为输出值 弘 2 f 为样本数 最优分类面为 u 妒 z b 0 式中6 兄 u 为特征空间维数 z 为内积函数 将输入样本空间映射到高维线 性特征空间 1 9 湖北大学硕士学位论文 s v v l 将该最优分类面的求解转化成一个二次规划q p 问题 其数学形式为 m i n r m l 2 c i l 豇t 们 u 盈 1 一靠 y i l i 矗 0 i 1 2 式中矗 为松弛变量 c 为惩罚参数 c 0 g 越大表示对错误分类的惩罚越大 利用拉格朗日乘子法求解这个具有线性约束的二次优化问题 得到对偶最优 化问题为 f f m a x 啦一 啦哟弘鲫k 毛 巧 i f f i l i f f i lj 1 b t 0 m g 啦玑 o 式中啦为支持值 0 啦sc 时 对应的z t 称为支持向量 称0 幽 c 所对应 的以为标准支持向量n s v a 志 磊y 胪盖q 倒蚋 式中 k w 为标准支持向i i 擞 分类判别函数为 f m 咖 a i y i k x i 巧 6 l 其中 巧 称为核函数 核函数的思想是把本来应该在高维空间中做的操作 在输入 低维 空间中就完成 这样就解决了高的维数带来麻烦 用于模式识别的s v m 方法在分类问题中 通过使间隔最大化 以期获得较好 的推广能力 该方法已经被用来解决复杂的分类问题 成为一种强大的模式分类 方法 2 0 第二章支持向量机 2 6 支持向量机回归 支持向量机的方法也可以应用到回归问题 即实值函数估计 中 仍保留最大 间隔算法的所有主要特征 非线性函数可以通过特征空间中的学习机器得到 同 时系统的容量由与特征空间维数不相关的参数控制 同分类算法一样 学习算法 要最小化一个凸函娩并且它的解是稀疏的 为估计实值函数 我们采用二次e 不敏感函数作为损失函数的定义 即 v o x 弘一 x i i 掣一 x i e 2 x 协一b x l s v m 凝 不敏感损失回归定义为 其中 扛峨曲 忪旷 g 喜c 阳 s g 再 一弘 6 仂一l x d e 6 矗 o f o i 1 仇 这里引入了两个松弛变量 一个是在目标值之上超出 所设 另一个是在目标值之 下超出e 所设 综合前面六节的内容 我们得到s v m 实现的就是如下的思想 通过某种事先 选择的非线性映射将输入向量映射到高维特征空间 再在这个空间中构造优化间 隔的超平面 一2 1 湖北大学硕士学位论文 第三章非标准支持向量机分类误差分析 支持向量机是建立在统计学习理论的v c 维理论和结构风险最小化基础上的 学习机器 它根据有限样本信息在模型的复杂性和学习能力之间寻求最佳折衷 以期获得好的推广能力 已经在模式识别的许多领域获得了成功的应用 例如文 本分类 手写字符识别 生物序列分析等领域得到了快速发展 并表现出极好的性 能 因此 对支持向量机学习算法进行分类误差分析 具有非常重要的理论和现实 意义 然而 支持向量机学习算法的严格数学分析还有待于进一步探讨与完善 且 需要构造针对具体应用问题的支持向量机算法 支持向量机分类算法具有四个显 著特点 1 利用最大间隔的思想降低分类器的v i 维 实现结构风险最小化原则 控制 分类器的推广能力 2 利用m 部c e r 核实现线性算法的非线性化 3 稀疏性 即少量样本 支持向量 的系数不为零 就推广性而言 较少的支持向 量在统计意义上对应好的推广能力 从计算角度看 支持向量减少了核形式 判别式的计算 i 4 算法设计成凸二次规划问题 避免了多解性 至1 9 9 5 年以来 在实用算法研究 设计和实现方面已取得了丰硕的成果 可归 结为几个大的研究方向 1 提高s v m 的计算速度 以便于处理大的研究方向 如序列最小化方法 1 7 等 2 利用最优化技术改进或改造支持向量机形式 简化计算过程 如线 性s v m 8 l s s v m 1 9 等 3 依据结构风险最小化原则和支持向 i 机的某些思想提出新的算法 如u s v m 2 0 广义s v m 2 1 等算法 4 利用结构风险最小化原则 核思想和正则化技术等改造传统的线性算法 构 造出相应的核形式 如核主成分分析 2 2 等 s v m c a 于其出色的学习性能 应用领域不断扩展 因而非标准支持向量机的 研究就显得尤为重要 因为 在实际问题中不同类别的错分误差一般并不相等 主 要有以下几个原因 2 2 第三章非标准支持向量机分类误差分析 1 不同样本点的损失不同 不同类型的错分有不同的损失 一种类型的的错分 往往要比另一种类型的的错分更为严重 例如 医生将一位癌症患者诊断为 健康人所带来的后果 要比将一个健康人诊断为患者的后果严重的多 2 存在采样偏差 在某些情况下 从训练集中采样得到的样本不是完全随机 的 对于两类分类情形 从一类中随机抽取的样本与从另一类中随机抽取的 样本的比例与整个样本空同中两类之间的比例有较大差异 例如患稀有疾 病的人的数目是很少的 若取样时从所有人群中随机取样 则样本中合有患 者的数目是很少的 实际中一个普通的方法是患者和健康人群中分别取样 可按事先指定的数目从患者中随机取样 然后再从健康人中取一个数目与 前者不相上下的样本 这样我们得到的训练样本包含上述两部分 3 样本空间的分布与训练样本的分布有差异 通常把这三种情形称为非标准情形 本文主要考虑前两种情形下的非标准支 持向量机 3 1 非标准支持向量机 3 1 1 非标准支持向量机谰练算法 为了表述方便 重写标准s v m 训练的目标函数 满足约束 转化为对偶问题 知 i i z c 壹6 口 i 1 玑 埘 龟一 1 一岛 v i 3 1 nnn 呼妒 n 呼i 萋萎玑协耳 啦 一 m 3 2 i l l i 1 2 3 湖北大学硕士学位论文 满足约束 v i 0 s 啦 g 肫 o l 式中0 酬2 这一项与在线性可分情况下分界面间的最小距离有关 6 代表在线性不 可分的情况下的松弛量 即充许错分样本点偏离分界面的程度 而常数e 则表述 对这种错分情况的惩罚因子 设c 是把正样本错误分