Abstract
Symbolic induction is a promising approach to constructing decision models by extracting regularities from a data set of examples. The predominant type of model is a classification rule (or set of rules) that maps a set of relevant environmental features into specific categories or values. Classifying loan risk based on borrower profiles, consumer choice from purchase data, or supply levels based on operating conditions are all examples of this type of model-building task. Although current inductive approaches, such as ID3 and CN2, perform well on certain problems, their potential is limited by the incremental nature of their search. Genetic algorithms (GA) have shown great promise on complex search domains, and hence suggest a means for overcoming these limitations. However, effective use of genetic search in this context requires a framework that promotes the fundamental model-building objectives of predictive accuracy and model simplicity. In this article we describe COGIN, a GA-based inductive system that exploits the conventions of induction from examples to provide this framework. The novelty of COGIN lies in its use of training set coverage to simultaneously promote competition in various classification niches within the model and constrain overall model complexity. Experimental comparisons with NewID and CN2 provide evidence of the effectiveness of the COGIN framework and the viability of the GA approach.
Article PDF
Similar content being viewed by others
References
Baker, J.E. (1985). Adaptive selection methods for genetic algorithms. Proceedings First International Conference on Genetic Algorithms and their Applications. Pittsburgh, PA: Morgan Kaufmann, pp. 101–111.
Booker, L. (1989). Intelligent behavior as an adaptation to the task environment. Doctoral dissertation, Department of Computer and Communication Sciences, University of Michigan, Ann Arbor, MI.
Booker, L. (1989). Triggered rule discovery in classifier systems. Proceedings 3rd International Conference on Genetic Algorithms. Fairfax, VA: Morgan Kaufmann, pp. 265–274.
Breiman, L., Friedman, J., Olshen, R., & Stone, C. (1984). Classification and regression trees. Monterey, CA: Wadsworth.
Clark, P., & Niblett, T. (1989). The CN2 induction algorithm. Machine Learning, 3 (4), 261–283.
Currim, I., Meyer, R.J., & Le, N. (1986). A concept learning system for the inference of production models of consumer choice. Working paper, UCLA.
DeJong, K.A., & Spears, W.M. (1991). Learning concept classification rules using genetic algorithms. Proceedings 12th International Conference on Artificial Intelligence. San Mateo, CA: Morgan Kaufmann.
Eshelman, L. (1991). The CHC Adaptive Search algorithm: How to have safe search when engaging in nontraditional genetic recombination. In G.J.E. Rawlins (Ed.), Foundations of genetic algorithms. San Mateo, CA: Morgan Kaufmann.
Goldberg, D. (1985). Dynamic systems control using rule learning and genetic algorithms. Proceedings of the Ninth International Joint Conference on Artificial Intelligence (Los Angeles, California). Morgan Kaufmann, pp. 588–592.
Goldberg, D.E. (1989). Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley.
Greene, D.P. (1987). Automated knowledge acquisition: Overcoming the expert systems bottleneck. Proceedings of the Seventh International Conference on Information Systems. Pittsburgh, PA: Lawrence Erlbaum Assoc., pp. 107–117.
Greene, D.P. (1992). Inductive knowledge acquisition using genetic adaptive search. Doctoral dissertation, The Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA.
Greene, D.P., & Smith, S.F. (1987). A genetic system for learning models of consumer choice. Proceedings of the Second International Conference on Genetic Algorithms and their Applications. Boston, MA: Morgan Kaufmann, pp. 217–223.
Greene, D.P., & S.F. Smith. (1992). COGIN: Symbolic induction with genetic algorithms. Proceedings Tenth National Conference on Artificial Intelligence. San Mateo, CA: Morgan Kaufmann.
Grefenstette, J.J., Ramsey, C.L., & Schultz, A.C. (1990). Learning sequential decision rules using simulation models and competition. Machine Learning, 5 (4), 355–381.
Grefenstette, J.J. (1991). Lamarkian learning in multi-agent environments. Proceedings 4th International Conference on Genetic Algorithms. San Mateo, CA: Morgan Kaufmann, pp. 303–310.
Holland, J.H. (1975). Adaptation in natural and artificial systems. Ann Arbor, MI: University of Michigan Press.
Holland, J.H. (1986). Escaping brittleness: The possibilities of general purpose learning algorithms applied to parallel rule-based systems. In R. Michalski, J. Carbonell, and T. Mitchell (Eds.), Machine learning: An artificial intelligence approach (Vol. 2). San Mateo, CA: Morgan Kaufmann.
Koza, J. (1991). Evolving a computer program to generate random numbers using the genetic programming paradigm. Proceedings of the Fourth International Conference on Genetic Algorithms and their Applications. San Diego, CA: Morgan Kaufmann, pp. 37–44.
MacDonald, B.A., & Witten, I.H. (1989). A framework for knowledge acquisition through techniques of concept learning. IEEE Transactions on Systems Man and Cybernetics, 19 (3), 499–512.
Michalski, R.S., & Chilauski, R. (1980). Learning by being told and learning from examples. International Journal of Policy Analysis and Information Systems, 4, 210–225.
Packard, N.H. (1990). A genetic learning system for the analysis of complex data. Complex Systems, 4. 543–572.
Quinlan, J.R. (1984). Inductive inference as a tool for the construction of high-performance programs. In R. Michalski, J. Carbonell, and T. Mitchell (Eds.), Machine learning: An artificial intelligence approach (vol. 1). Palo Alto, CA: Tioga Press.
Quinlan, J.R. (1986). The effect of noise on concept learning. In R. Michalski, J. Carbonell, and T. Mitchell (Eds.), Machine learning: An artificial intelligence approach (Vol. 2). San Mateo, CA: Morgan Kaufmann.
Robertson, G.C., & Riolo, R.L. (1988). A tale of two classifier systems. Machine Learning, 3, 139–159.
Schaffer, J.D. (1984). Some experiments in machine learning using vector evaluated genetic algorithms. Doctoral dissertation, Department of Electrical Engineering, Vanderbilt University, Nashville, TN.
Smith, S.F. (1980). A learning system based on genetic adaptive algorithms. Doctoral dissertation, Department of Computer Science, University of Pittsburgh, Pittsburgh, PA.
Smith, S.F. (1983). Flexible learning of problem solving heuristics via adaptive search. Proceedings 8th International Joint Conference on AI.
Syswerda, G. (June 1989). Uniform crossover in genetic algorithms. Proceedings of the Third International Conference on Genetic Algorithms and their Applications. Fairfax, VA: Morgan Kaufman.
Wilson, S.W. (1987). Classifier systems and the animat problem. Machine Learning, 2, 199–228.
Wilson, S.W., & Goldberg, D.E. (1989). A critical review of classifier systems. Proceedings 3rd International Conference on Genetic Algorithms. Fairfax, VA: Morgan Kaufmann, pp. 244–255.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Greene, D.P., Smith, S.F. Competition-Based Induction of Decision Models from Examples. Machine Learning 13, 229–257 (1993). https://doi.org/10.1023/A:1022622013558
Issue Date:
DOI: https://doi.org/10.1023/A:1022622013558