第6期 何清，等：基于超曲面的分类算法研究进展 5· 到极小样本集的方法给出了选择的训练样本，为了 Recognition Letters,2004,25(10):1165-1171. 使在其上学习得到的模型有很好的性能应满足的性 [11]许建华，张学工，李衍达.一种基于核函数的非线性感 质（包含某一极小样本集）.将从包含极小样本集这 知器算法U].计算机学报，2002,25(7)：689.695. 个目标出发，在一定的限制条件下得到一个新的样 XU Jianhua,ZHANG Xuegong,LI Yanda.A nonlinear 本集所包含实例个数的边界，并与PAC的样本复杂 perceptron algorithm based on kernel functions[J].Chi- 度理论进行比较 nese Journal of Computers,2002,25(7):689-695. [12]ZHANG Ling,ZHAN G Bo.A geometrical representa- 3结束语 tion of MeCulloch Pitts neural model and its applica- tions [J ]IEEE Transactions on Neural Networks. 总之，在基于覆盖的分类学习算法方面，基于覆 1999,10(4):925-929. 盖思想在最近10年相继提出过一些很有价值的分 [13]吴涛，张铃，张燕平.机器学习中的核覆盖算法] 类学习方法和理论分析，但是，大量的理论问题尚 计算机学报，2005,28(8)：1295,1301 未解决，H$C学习算法作为一种覆盖分类算法，其 WU Tao,ZHANG Ling,ZHANG Yanping.Kernel 性能提高以及计算复杂性、泛化能力等理论问题值 covering algorithm for machine learning [J].Chinese 得深入研究。 Journal of Computers,2005,28(8):1295-1301 [14]陶品，张钱，叶榛.构造型神经网络双交叉覆盖增 参考文献： 量学习算法[0].软件学报，2003,14(2)：194.201。 TAO Pin,ZHANG Bo.YE Zhen.An incremental bi- [1]VAPNIK V.The nature of statistical learning theory [M].New York:Springer-Verlag,1995. covering learning algorithm for constructive neural net- work[J ]Journal of Software,2003,14 (2):194 [2]VAL IANT L G.A theory of the learnable[J ]Commu nications of the ACM,1984.27(11):1134-1142. 201. [3]BLUMER A,EHRENFEUCHT A,HASSL ER D,et [15]张铃，张钱，殷海风.多层前向网络的交叉覆盖设 al.Classifying learnable geometric concepts with the 计算法U].软件学报，1999,10(7)：737.742. Vapnik-Chervonenkis dimension[A ]Proceedings of the ZHAN GLing,ZHANGBo,YIN Haifeng.An alterna- 19th Annual ACM Symposium on Theory of Computing tive covering design algorithm of multi-layer neural net- [C].Berkeley,US,1986. works[J ]Journal of Software,1999,10(7):737- [4]DANA A.Computational learning theory:survey and 742. selected bibliography [A].Proceedings of the Twenty- [16]周志华，曹存根.神经网络及其应用[M门.北京：清华大 fourth Annual ACM Symposium on Theory of Compu- 学出版社2004 ting[C].[s.1.],1992. [17]王守觉.仿生模式识别（拓扑模式识别） 一一种模式 [5]DUDA R O,HART P E.Pattern classification and 识别新模型的理论与应用[U].电子学报，2002,30 scene analysis[M].New York:John Wiley Sons, (10):1417.1420. 1973 WANG Shoujue.Bionic (topological)pattern recogni- [6]DUDA RO,HART P E,STOCKD G.模式分类[M] tion-a new model of pattern recognition theory and its 北京：机械工业出版社，2003. applications [J ]Acta Electronica Sinica,2002,30 [7]MENDEL SON S.A few notes on statistical learning the- (10):1417.1420. ory R].Advanced Lectures on Machine Learning, [18 ]WANGSJ,QU Y F,LI WJ.Face recognition:biomi- LNAI2600,2003. metic pattern recognition vs traditional recognition [J] [8]张文生，丁辉，王珏.基于邻域原理计算海量数据支 Acta Electronica Sinica,2004,32(7):1057-1061. 持向量的研究01.软件学报，2001,12(5)：711.720. [19]CAO W M,HAO F,WANG S J.The application of ZHANG Wensheng,DING Hui,WANG Jue.Study on DBF neural networks for object recognition [J].Infor- computing the support vectors of massive data based on mation Sciences-Informatics and Computer Science:An neighborhood principle [J ]Journal of Software,2001, International Journal,2004,160(1-4):153-160 12(5):711.720. [20]王守觉，王柏南.人工神经网络的多维空间几何分析及 [9]TAO Q,WANG J.Kernel projection algorithm for 其理论[]，电子学报，2002,30(1)：1-4. large-scale SVM problems[J ]Journal of Computer Sci- WANG Shoujue,WANG Bainan.Analysis and theory ence Technology,2002,17(5):556-564. of highdimension space geometry for artificial neural [10]TAO Qing,WU Gaowei,WANGJue.A generalized S networks[J].Acta Electronica Sinica,2002,30(1): 3Kalgorithm for learning SVM classifiers[J].Pattern 1.4. 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net到极小样本集的方法给出了选择的训练样本 ,为了 使在其上学习得到的模型有很好的性能应满足的性 质(包含某一极小样本集) . 将从包含极小样本集这 个目标出发 ,在一定的限制条件下得到一个新的样 本集所包含实例个数的边界 ,并与 PAC 的样本复杂 度理论进行比较. 3 结束语 总之 ,在基于覆盖的分类学习算法方面 ,基于覆 盖思想在最近 10 年相继提出过一些很有价值的分 类学习方法和理论分析 ,但是 , 大量的理论问题尚 未解决. HSC 学习算法作为一种覆盖分类算法 ,其 性能提高以及计算复杂性、泛化能力等理论问题值 得深入研究. 参考文献 : [1 ] VAPNIK V. The nature of statistical learning theory [ M]. New York : Springer2Verlag , 1995. [2 ]VAL IAN T L G. A theory of the learnable [J ]. Commu2 nications of the ACM , 1984 , 27 (11) : 1134 - 1142. [3 ]BLUMER A , EHRENFEUCH T A , HASSL ER D , et al. Classifying learnable geometric concepts with the Vapnik2Chervonenkis dimension[ A ]. Proceedings of the 19th Annual ACM Symposium on Theory of Computing [C]. Berkeley , US , 1986. [4 ]DANA A . Computational learning theory : survey and selected bibliography [ A ]. Proceedings of the Twenty2 fourth Annual ACM Symposium on Theory of Compu2 ting[C]. [ S. l. ] ,1992. [5 ] DUDA R O , HART P E. Pattern classification and scene analysis [ M ]. New York : John Wiley & Sons , 1973. [6 ]DUDA R O , HART P E , STOCK D G. 模式分类[ M]. 北京 :机械工业出版社 ,2003. [ 7 ]MENDELSON S. A few notes on statistical learning the2 ory [ R ]. Advanced Lectures on Machine Learning , LNAI 2600 , 2003. [8 ]张文生 ,丁 辉 ,王 珏. 基于邻域原理计算海量数据支 持向量的研究[J ]. 软件学报 ,2001 ,12 (5) : 711 - 720. ZHAN G Wensheng , DIN G Hui , WAN G J ue. Study on computing the support vectors of massive data based on neighborhood principle [J ]. Journal of Software , 2001 , 12 (5) :711 - 720. [ 9 ] TAO Q , WAN G J. Kernel projection algorithm for large2scale SVM problems[J ]. Journal of Computer Sci2 ence Technology , 2002 , 17 (5) : 556 - 564. [10 ] TAO Qing , WU Gaowei , WAN G J ue. A generalized S ∃ K algorithm for learning2SVM classifiers[J ]. Pattern Recognition Letters , 2004 , 25 (10) : 1165 - 1171. [11 ]许建华 , 张学工 , 李衍达. 一种基于核函数的非线性感 知器算法[J ]. 计算机学报 , 2002 ,25 (7) : 689 - 695. XU Jianhua , ZHAN G Xuegong , L I Yanda. A nonlinear perceptron algorithm based on kernel functions[J ]. Chi2 nese Journal of Computers , 2002 , 25 (7) : 689 - 695. [12 ]ZHAN G Ling , ZHAN G Bo. A geometrical representa2 tion of McCulloch2 Pitts neural model and its applica2 tions [J ]. IEEE Transactions on Neural Networks , 1999 ,10 (4) : 925 - 929. [13 ]吴 涛 ,张 铃 ,张燕平. 机器学习中的核覆盖算法[J ]. 计算机学报 ,2005 ,28 (8) :1295 - 1301. WU Tao , ZHAN G Ling , ZHAN G Yanping. Kernel covering algorithm for machine learning [J ]. Chinese Journal of Computers , 2005 , 28 (8) : 1295 - 1301. [14 ]陶 品 ,张 钹 ,叶 榛. 构造型神经网络双交叉覆盖增 量学习算法[J ]. 软件学报 ,2003 ,14 (2) :194 - 201. TAO Pin , ZHAN G Bo , YE Zhen. An incremental bi2 covering learning algorithm for constructive neural net2 work[J ]. Journal of Software , 2003 , 14 ( 2) : 194 - 201. [15 ]张 铃 ,张 钹 ,殷海风. 多层前向网络的交叉覆盖设 计算法[J ]. 软件学报 ,1999 ,10 (7) :737 - 742. ZHAN G Ling , ZHAN GBo , YIN Haifeng. An alterna2 tive covering design algorithm of multi2layer neural net2 works[J ]. Journal of Software , 1999 , 10 (7) : 737 - 742. [16 ]周志华 ,曹存根. 神经网络及其应用[ M ]. 北京 :清华大 学出版社 ,2004. [17 ]王守觉. 仿生模式识别 (拓扑模式识别) ———一种模式 识别新模型的理论与应用 [J ]. 电子学报 , 2002 , 30 (10) : 1417 - 1420. WAN G Shoujue. Bionic (topological) pattern recogni2 tion —a new model of pattern recognition theory and its applications [ J ]. Acta Electronica Sinica , 2002 , 30 (10) : 1417 - 1420. [ 18 ]WAN G S J , QU Y F , L I W J. Face recognition : biomi2 metic pattern recognition vs traditional recognition [J ]. Acta Electronica Sinica , 2004 , 32 (7) : 1057 - 1061. [19 ]CAO W M , HAO F , WAN G S J. The application of DBF neural networks for object recognition [J ]. Infor2 mation Sciences2Informatics and Computer Science : An International Journal , 2004 , 160 (1 - 4) : 153 - 160. [20 ]王守觉 ,王柏南. 人工神经网络的多维空间几何分析及 其理论[J ]. 电子学报 ,2002 ,30 (1) :1 - 4. WAN G Shoujue , WAN G Bainan. Analysis and theory of high2dimension space geometry for artificial neural networks[J ]. Acta Electronica Sinica , 2002 , 30 ( 1) : 1 - 4. 第 6 期 何 清 ,等 :基于超曲面的分类算法研究进展 ·5 ·