分类超曲面算法复杂度研究

《分类超曲面算法复杂度研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《计算机学报》2010年4期，2010，33（4）分类超曲面算法复杂度研究本文得到国家自然科学基金(No.60435010,60675010),863高技术项目(No.2006AA01Z128)，国家973项目(No.2007CB311004).何清，男，1965年生，副研究员，博士生导师，主要研究领域为模糊数学、机器学习、人工智能.赵卫中，男，1981年生，博士研究生，主要研究领域为机器学习、数据挖掘.E-mail:zhaowz@ics.ict.ac.cn.史忠植，男，1941年生，研究员，博士生导师，主要研究领域为人工智能、机器学习和分布式人工智能.何清1),2)赵卫中1),2)

2、史忠植1)1)（1.中国科学院计算技术研究所智能信息处理重点实验室北京100190）2)（2.中国科学院研究生院北京100039）摘要分类超曲面算法是一种简单的基于覆盖的分类算法.实验证明该算法具有分类正确率高、速度快的优点.但是，关于该算法的相关理论问题需要深入研究.本文对该算法的几个相关理论问题进行了研究.首先给出并证明了在分割的最大层数给定时算法假设空间的VC维，在此基础上结合可能近似正确(ProbablyApproximatelyCorrect：PAC)学习框架，得出了对算法样本复杂度的估计，使得分类超曲面算法保证可PAC学习到任意目标概念.其次，分析了算法的时间复杂度和空间

3、复杂度.最后，给出了无矛盾样本集的概念，并证明当输入样本集是有限无矛盾样本集的条件下，算法一定是收敛的.关键词分类超曲面算法，VC维，PAC可学习性，样本复杂度1引言分类算法研究是机器学习的核心研究内容，分类能力是人类智能的最显著特征之一.基于拓扑学中的Jordan曲线定理，何清等[1,2,3]提出了一种通用的覆盖型分类方法——分类超曲面算法.该方法直接在原空间解决非线性分类问题，通过区域细化与区域合并获得由多个超平面组成的双侧闭曲面作为分类超曲面对空间进行划分，通过计算样本点关于分类超曲面的围绕数的奇偶性即可简单方便地判定其类别.实验表明，在二维、三维及高维空间中，分类超曲面算法分

4、类正确率高、速度快；而存储量和计算量都很小，从而能够处理海量数据.各种分类算法共有的局限性是：每种算法的推广性都依赖于测试数据分布与训练数据分布是否一致.但如何获得数据分布，如何划分可以使测试数据分布与训练数据分布一致是一个难以解决的重要问题.在分类超曲面算法方面，文献[4]通过对极小样本集的研究找到了答案，解决了为什么极小样本集会影响分类准确率的问题，还指出了极小样本集有多少种表达方式.但是，对于该算法的相关理论问题还需要深入研究.在本文中，我们研究了分类超曲面算法的几个相关理论问题，包括VC维，样本复杂度，时间复杂度，空间复杂度以及收敛性等，使分类超曲面算法的理论更加完整.本文结

5、构如下.第二节介绍了与本文相关的工作，包括VC维，PAC框架的相关概念以及分类超曲面算法的简略描述.第三节分析了分类超曲面算法的相关理论问题，其中首先证明了算法假设空间的VC维，在此基础上结合PAC框架求得了算法的样本复杂度；接着分析了算法的时间复杂度和空间复杂度；最后给出了算法收敛的条件.第四节对我们的工作进行总结.2相关工作2.1VC维的概念VC维是假设空间复杂度的度量标准.为了描述这一概念，首先引入对一个实例集合打散（Shattering）的概念[5].对于假设空间H，样本集X以及X的某个子集S，H中的每个假设h导致S的某个划分，即h将S划分为两个子集{x∈S

6、h(x)=1}以

7、及{x∈S

8、h(x)=0}.当S的每个可能的划分都可由H中的某个假设来表达时，我们就称H打散S.如果一个实例集合没有被假设空间打散，那么必然存在某个概念（划分）可被定义在实例集之上，但不能由假设空间表示.因此，H《计算机学报》2010年4期，2010，33（4）的这种打散实例集合的能力是其表示这些实例上定义的目标概念的能力.定义在实例集X上的假设空间H的VC维是可被H打散的X的最大有限子集的大小，记作VC（H）[5].如果X的任意大的子集可被H打散，则VC（H）≡∞.2.2PAC学习框架及样本复杂度为了描述学习算法L输出的假设h对真实目标概念c的逼近程度，我们引入假设h对于目标概念c

9、和实例分布D的真实错误率.假设样本集X中样本按照概率分布D随机产生.对于X中任意样本x及其目标值c(x)提供给学习算法L，学习算法L输出的假设h的真实错误率为把h应用到将来按分布D抽取的实例时期望的错误率，用表示.即，其中符号表示在实例分布D的概率.如果一个假设空间是H的机器学习算法L满足如下条件，我们就称L是可PAC学习的：给定任意的实数ε，δ满足以及，如果存在一个正整数，对于任意的目标概念c∈H和样本分布D，当样本数时，学习算法L将以至少的概率输出一个