《计算机学报》文章摘要   全文下载
文章题目	分类超曲面算法复杂度研究
作者	何清1),2) 赵卫中1),2) 史忠植1)
作者单位	1)(中国科学院计算技术研究所智能信息处理重点实验室 北京 100190) 2)(中国科学院研究生院 北京 100039)
发表年份	2010
发表月份	4期(666—671)
文章摘要	摘要 分类超曲面算法是一种简单的基于覆盖的分类算法.实验证明该算法具有分类正确率高、速度快的优点.但是，关于该算法的相关理论问题需要深入研究.文中对该算法的几个相关理论问题进行了研究.首先给出并证明了在分割的最大层数给定时算法假设空间的VC维，在此基础上结合可能近似正确(Probably Approximately Correct，PAC)学习框架，得出了对算法样本复杂度的估计，使得分类超曲面算法保证可PAC学习到任意目标概念.其次，分析了算法的时间复杂度和空间复杂度.最后，给出了无矛盾样本集的概念，并证明当输入样本集是有限无矛盾样本集的条件下，算法一定是收敛的. 关键词 分类超曲面算法；VC维；PAC可学习性；样本复杂度 中图法分类号 TP18 DOI号 10.3724/SP.J.1016.2010.00666