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

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

本文证明了示例学习中的最大复合问题（ＭＧＣ）是ＮＰ难题，给出了求解最大复合问题的近似算法，并将此示例学习算法应用于手写数字识别．实验证明，基于最大复合的学习算法和ＡＱ１５相比，速度快、得到的公式少、匹配精度高．

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.