An analytical comparison of some rule-learning programs (Q1069315)

To become a mature science, Artificial Intelligence needs more theoretical work. One form this should take is the analytic comparison of existing programs to extract precise techniques from the code, compare similar techniques, expose faults, and extend successful techniques. In this spirit, we compare the rule-learning programs of \textit{P. Brazdil} [A model for error detection and correction. Ph. D. Thesis, Univ. Edinburgh (1981)], \textit{P. Langley} [Language acquisition through error recovery. CIP Working Paper 432, Carnegie-Mellon Univ., Pittsburgh, PA (1981)], \textit{T. M. Mitchell}, \textit{P. E. Utgoff}, \textit{B. Nudel} and \textit{R. Banerji} [Proc. 7th Int. Joint Conf. Artif. Intell., Vancouver, BC, 1981, 127-134 (1981); Machine Learning, 163-190 (Tioga, Palo Alto, CA, 1983)], \textit{E. Shapiro} [Proc. 7th Int. Joint Conf. Artif. Intell., Vancouver, BC, 1981, 446-451 (1981)], and \textit{D. A. Waterman} [Artif. Intell. 1, 121-170 (1970; Zbl 0203.490)]. Each of these programs has two main parts: a criticism for identifying faulty rules and a modifier for correcting them. To aid comparison we describe the techniques of the various authors using a uniform notation. We find several similarities in the techniques used by the various authors and uncover the relations between them. We compare the rule-learning programs with the concept- learning programs of \textit{J. R. Quinlan} [Exp. Syst. in the Micro- Electron. Age, 168-201 (Edinburgh, 1979)] and \textit{R. M. Young}, \textit{G. D. Plotkin} and \textit{R. F. Linz} [Proc. 5th Int. Joint Conf. Artif. Intell., Cambridge, MA, 1977, 285 (1977)]. The two types of program have much in common, and many of the rule-modifying techniques are subsumed by the techniques of Young et al. Quinlan's program is able to learn disjunctive concepts that are more general than those that can be learned by most of the other programs.