示例学习的最大复合问题及算法  

THE MAXIMUM COMPLEX PROBLEM IN LEARNING FROM EXAMPLES AND ITS GREEDY ALGORITHM

作　　者：陈彬[1] 洪家荣[1] 

机构地区：[1]哈尔滨工业大学计算机科学与工程系

出　　处：《计算机学报》1997年第2期139-144,共6页Chinese Journal of Computers

摘　　要：本文证明了示例学习中的最大复合问题（ＭＧＣ）是ＮＰ难题，给出了求解最大复合问题的近似算法，并将此示例学习算法应用于手写数字识别．实验证明，基于最大复合的学习算法和ＡＱ１５相比，速度快、得到的公式少、匹配精度高．In this article, the maximum general complex problem (MGC) in learning from examples is proved to be NP-hard, and an approximate solution to the problem is proposed and applied to hand-written numeral recognition. Compared with AQ15 , the algorithm based on maximum general complex runs faster and generates fewer rules and gives higher accuracy.

关 键 词：示例学习 最大复合问题 NP难题 机器学习 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]