支持向量机算法的研究及其应用(3)

（１）经验风险依赖于学习机器所选定的函数ｆ（ａ，ｘ），这样，我们可以通过控制ａ来控制经验风险。

（２）ＶＣ维ｈ依赖于学习机器所工作的函数集合（如前所述）。为了获得对ｈ的控制，可以将函数集合结构化，建立ｈ与各函数子结构之间的关系，通过控制对函数结构的选择来达到控制ＶＣ维ｈ的目的。具体做法如下，

首先，运用以下的方法将函数集合｛ｆ（ｘ，ａ），ａ∈Ｆ）结构化。考虑函数嵌套子集的集合，如图】．２［Ｖａｐｎｉｋ，１９９５］所示，

墨ｃ是ｃ…ｃ≮匕…［鼠…

其中，Ｓｋ＝｛ｆ（ｘ，ａ）：ａ∈Ｆｔ），并且有（１．４）

∥＝Ｕ＆

ｋ（１．５）

结构Ｓ中的任何元素墨（或一个函数集合）拥有一个有限的ＶＣ维％；且

岛≤吃≤，…，≤吃，…（１．６）

图１．２由函数的嵌套子集决定的函数的集合如果给定一组样本（ｘｌ，Ｍ），（ｘ２，儿），…，（＿，Ｙ｛），结构风险最小化原理在函

算法

浙江大学博士学位论文

数子集Ｓ＾中选择一个函数ｆ（ｘ，乜，ｋ）来最小化经验风险，同时，Ｓ女确保置信风险是最小的。

以上的思想就称为“结构风险最小化归纳原理”。为了进一步说明，请看图１．３［Ｖａｐｎｉｋ，１９９５１，已知一个嵌套的函数子集序列Ｓｌ，是，…，Ｓｎ，它们的ＶＣ维分别对应为岛，琏，…，亿。而且有如≤如≤，…，≤吃。图中给出了真实风险、经验风险与置信风险分别与ＶＣ维ｈ的函数变化关系曲线。显然随着ｈ的增加，经验风险Ｒ。。（日）递减，这是因为ｈ增加，根据ｖｃ维的定义，对应的函数集合的描述能力增加，学习机器的学习能力就增强，可以使有限样本的经验风险

ｂ

很快地收敛，甚至于变为０；根据式（１．１），置信风险Ｖ（；）随着ｈ的增加而增

ｆ

加；这样，真实风险Ｒ（口）是一个凹型曲线。所以，要获得最小的真实风险，就需要折中考虑经验风险与置信风险的取值。

过学习欠学习

风险

Ｃ维

图１．３结构风险最小归纳原理图

根据这一分析，可以得到两种运用结构风险最小化归纳原理构造的学习机

算法

第一章绪论

器的思路：

（１）给定了一个函数集合，按照上面的方法来组织一个嵌套的函数结构，在每个子集中求取最小经验风险，然后选择经验ＪｘＬ险与置信风险之和最小的子集。当子集数目较大的时候，此方法较为费时。甚至于不可行。

（２）构造函数集合的某种结构，使得在其中的各函数子集均可以取得最小的经验风险（例如，使得训练误差为Ｏ）。然后，在这些子集中选择适当的子集使得置信风险最小，则相应的函数子集中使得经验风险最小的函数就是所求解的最优函数。

支持向量机采用的就是方法（２），将在下面做详细介绍。

１．４支持向量机算法的发展历史和现状

作为ＳＶＭ的奠基者Ｖ．Ｖａｐｎｉｋ早在６０年代就开始了统计学习理论的研究

Ｎｅｃｅｓｓａｒｙａｎｄ

ＣｏｎｄｉｔｉｏｎｓｆｏｒｔｈｅＵｎｉｆｏｒｍｓＣｏｎｖｅｒｇｅｎｃｅｏｆＡｖｅｒａｇｅｓｔｏＥｘｐｅｃｔｅｄ

１９８２年，在“ＥｓｔｉｍａｔｉｏｎｏｆＤｅｐｅｎｄｅｎｃｅｓＢａｓｅｄｏｎＥｍｐｉｒｉｃａｌＤａｔａ”一书中，Ｖａｐｎｉｋ进一步提出了具有划时代意义的结构风险最小化原理，堪称为ＳＶＭ１９９２年，Ｂｏｓｅｒ，ＧｕｙｏｎａｎｄＶａｐｎｉｋ在“ＡＴｒａｉｎｉｎｇＡｌｇｏｒｉｔｈｍｆｏｒＯｐｔｉｍａｌ１９９３年，Ｃｏｒｔｅｓ和Ｖａｐｎｉｋ在“ＴｈｅＳｏｆｔＭａｒｇｉｎＣｌａｓｓｉｆｉｅｒ”一书中，进一步１９９５年，ＶＶａｐｎｉｋ在“ＴｈｅｎａｔｕｒｅｏｆＳｔａｔｉｓｔｉｃａｌＬｅａｒｎｉｎｇＴｈｅｏｒｙ”一书中，１９９７年，ｖＶａｐｎｉｋ，Ｓ．Ｇｏｋｏｗｉｃｈ和Ａ．Ｓｍｏｌａ，发表的“ＳｕｐｐｏｒｔＶｅｃｔｏｒＭｅｔｈｏｄＦｕｎｃｔｉｏｎＡｐｐｒｏｘｉｍａｔｉｏｎ，ＲｅｇｒｅｓｓｉｏｎＥｓｔｉｍａｔｉｏｎａｎｄＳｉｇｎａｌＰｒｏｃｅｓｓｉｎｇ”一文中，由于ＳＶＭ算法的潜在应用价值，吸引了国际上众多的知名学者，近几年１９９７ａ；ＳｃｈＯｌｋｏｐｆ，１９９８ａ；Ｓｍｏｌａ，１９９８ａ；Ｂｅｍｎｅｔｔ，１９９８；Ｗｅｓｔｏｎ，１９９９ａ；Ｚｈａｎｇ１９９８ｂ；Ｂｕｒｇｅｓ，１９９７；Ｂｕｒｇｅｓ，１９９８；Ｂｕｒｇｅｓ，１９９９；Ｓｃｈ６１ｋｏｐｆ，１９９７ｂ］所述。值得一【Ｖａｐｎｉｋ，１９６３］，１９７１年，Ｖ．Ｖａｐｎｉｋ和Ａ．Ｃｈｅｒｖｏｎｅｎｋｉｓ在“ＴｈｅＳｕｆｆｉｃｉｅｎｔＶａｌｕｅｓ”一文中，提出了ＳＶＭ的一个重要的理论基础—＿Ｖｃ维理论。Ｖ算法的基石。ＭａｒｇｉｎＣｌａｓｓｉｆｉｅｒｓ”～书中，提出了最优边界分类器［Ｂｏｓｅｒ，１９９２］。探讨了非线性最优边界的分类问题［Ｃｏｒｔｅｓ，１９９３１。完整地提出了ＳＶＭ分类。ｆｏｒ详细介绍了基于ＳＶＭ方法的回归算法和信号处理方法。出现了许多发展和改进的支持向量机算法，如文献［ＳｃｈＳｌｋｏｐｆ，１９９６；Ｓｃｈｆｌｋｏｐｆ，Ｘｕｅ—Ｇｏｎｇ，１９９９１所述。有关非线性ＳＶＭ中核的研究方法，如文献［Ｓｃｈ６１ｋｏｐｆ，提的是：１９９８年，Ｓｍｏｌａ在他的博士论文中详细研究了ＳＶＭ算法中各种核的机理和应用，为进一步完善ＳＶＭ非线性算法做出了重要的贡献［Ｓｍｏｌａ，１９９８ｂ】。

算法

浙江大学博上学位论文

ＳＶＭ在模式识别领域已经有了一些应用，如手写体数字识另ｌＪ［Ｓｃｈ６１ｋｏｐｆ，１９９５；Ｙａｎｇ，１９９４；Ｙａｎｇ，１９９７】、人脸识别与人脸检测ｆＯｓｕｎａ，１９９７ａ；Ｏｓｕｎａ，１９９７ｂ］、以及文本分类［Ｊｏａｃｈｉｍｓ，１９９７；Ｊｏａｃｈｉｍｓ，１９９８；Ｊｏａｃｈｉｍｓ，１９９９１等各种领域［Ｋｒｅ／Ｊｅｌ，１９９９；ＣａｉＹｕ—Ｄｏｎｇ，２００２１。此外，ＳＶＭ还很好地应用于时间序列分析

【Ｍｕｋｈｅｒｊｅｅ，１９９７１和回归分析［Ｄｒｕｃｋｅｒ，１９９７；Ｋｗｏｋ，１９９８；Ｓｃｈ６１ｋｏｐｆ，１９９８］等领域的研究。例如，ＭＩＴ、ＢｅｌｌＬａｂ和微软研究所等已成功地将ＳＶＭ算法应用于动态图象的人脸跟踪，信号处理，语音识别，图象分类和控制系统等诸多领域［Ｃｏｒｔｅｓ，１９９５；Ｇｕｙｏｎ，１９９７；Ｅｏｓｕｎａ，１９９７；Ｖａｐｎｉｋ，１９９７】。

１．５支持向量机基本方法

假定大小为ｚ的训练样本集｛（ｘ，，Ｙ，），ｉ＝１，２，…，，｝，由二类别组成，如果ｘ，∈Ｒ‘Ⅳ’属于第１类，则标记为正（咒＝】），如果属于第２类，则标记为负（儿＝一１１。学习的目标是构造一个决策函数，将测试数据尽可能正确地分类。针对训练样本集为线性或者非线性两种情况分别讨论。

５．１线性情况１

如果存在分类超半囱

∞ ｘ＋ｂ＝０（１．７）

使得

∞裂兰Ｚ＝一１０，１Ｘｂ ．＋≤一，Ｙｉ＝一，＝１，，…，ｆ１，ｉ乩２，…，，∽ｓ，

则称训练集是线性可分的，其中∞．ｘ表示向量∞∈Ｒ‘Ⅳ’与ｘ∈Ｒ‘Ⅳ’的内积。式（１．７）和式（１．８）中的∞∈Ｒ‘…，ｂ∈Ｒ‘１’都进行了规范化，使每类样本集中与分类超平面距离最近的数据点满足式（１．８）的等式要求。对于式（１．８ …… 此处隐藏：1540字，全部文档内容请下载后查看。喜欢就下载吧 ……