The HCV induction algorithm

ABSTRACT

HCV is a heuristic attribute-based induction algorithm based on the newly-developed extension matrix approach. By dividing the positive examples (PE) of a specific class in a given example set into intersecting groups and adopting a set of strategies to find a heuristic conjunctive formula in each group which covers all the group's positive examples and none of the negative examples (NE), it can find a covering formula in form of variable-valued logic for PE against NE in low-order polynomial time. This paper presents the HCV algorithm in detail and provides a performance comparison of HCV with other inductive algorithms such as ID3 and AQ11.

REFERENCES

• Bloedorn et al. 92: E. Bloedorn, R.S. Michalski, and J. Wnek, AQ17 - A Multistrategy Constructive Learning System, Reports of Machine Learning and Inference Laboratory, Center for Artificial Intelligence, George Mason University, USA, 1992.
• Cestnik et al. 87: B. Cestnik, I. Kononenko, and I. Bratko, ASSISTANT 86: A Knowledge-Elicitation Tool for Sophisticated Users, Progress in Machine Learning, I. Bratko and N. Lavrac (Eds.), Wilmslow: Sigma Press, England, 1987.
• Clark et al. 89: Peter Clark , Tim Niblett, The CN2 Induction Algorithm, Machine Learning, v.3 n.4, p.261-283, March 1989 [doi>10.1023/A:1022641700528]
• Feigenbaum 81: E.A. Feigenbaum, Expert Systems in the 1980s, Infotech Stale of lhe Art Report on Machine Intelligence, A. Bond (Ed.), Maidenhead: Pergamon-Infotech, 1981.
• Hong 85: J. Hong, AEI: An Extension Matrix Approximate Method for the General Covering Problem, International Journal of Computer and Information Sciences, 14(1985), 6: 421-437.
• Hong et al. 87: J.R. Hong and C. Uhrik, The Extension Matrix Approach to Attribute-Based Learning, Progress in Machine Learning, I. Bratko and N. Lavrac (Eds.), Wilmslow: Sigma Press, England, 1987.
• Hunt et al. 66: E.B. Hunt, J. Marin and P.T. Stone, Experiments in Induction, Academic Press, New York, 1966.
• Michalski 75: R.S. Michalski, Variable-Valued Logic and Its Applications to Pattern Recognition and Machine Learning, Computer Science and Multiple- Valued Logic Theory and Applications, D.C. Rine (Ed.), Amsterdam: North-Holland, 1975, 506-534.
• Michalski et al. 78: R.S. Michalski and J. Larson, Selection of Most Representative Training Exampies and Incremental Generation of VL1 Hypothesis- the Underlying Methodology and Description of Programs ESEL and AQll, Tech. Report UIUCDCS-R-78-867, Dept. of Computer Science, Univ. of Illinois at Champaign-Urbana, 1978.
• Michalski et al. 86: R.S. Michalski, I. Mozetie, J. tlong and N. Lavrac, The Multi-Purpose Incremental Learning System AQ15 and Its Testing Application to Three Medical Domains, Proceedings of AAAI 1986, 1986, 1041-1045.
• Quinlan 79: J.R. Quinlan, Discovering Rules by Induction from Large Collections of Examples, Introductory Readings in Expert Systems, D. Michie (Ed.), Gordon and Breach, London, 1979, 33--46.
• Quinlan 86: J. R. Quinlan, Induction of Decision Trees, Machine Learning, v.1 n.1, p.81-106 [doi>10.1023/A:1022643204877]
• Quinlan 89: J.R. Quinlan, Requirements for Knowledge Discovery in Databases, Proceedings of IJCAI- 89 Workshop on Knowledge Discovery in Databases, Detroit, USA, 1989, xiv.
• Quinlan 92: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• Thrun et al. 91: S.B. Thrun, et al., The MONK's Problems- A Performance Comparison of Different Learning Algorithms, CMU-CS-gl-lgT, School of Computer Science, Carnegie Mellon University, 1991.
• Utgoff 89: Paul E. Utgoff, Incremental Induction of Decision Trees, Machine Learning, v.4 n.2, p.161-186, November 1989 [doi>10.1023/A:1022699900025]
• Valiant 84: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• Wu 92a: X. Wu, Optimization Problems in Extension Matrixes, Science in China, Series A, Chinese edition: 35(1992), 2: 200-207; English edition, 35(1992), 3: 363-373.
• Wu 92b: X. Wu, HCV: A Heuristic Covering Algorithm for Extension Matrix Approach, DAI Research Paper No. 578, Department of Artificial Intelligence, University of Edinburgh, 1992.
• Wu 92c: X. Wu, HCV User's Manual (Release 1.0 June 1992), DAI Technical Paper No. g, Department of Artificial intelligence, University of Edinburgh, 1992.
• Wu 92d: X. Wu, Inductive Learning: Algorithms and Frontiers, Artificial Intelligence Review, 6(1992).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

General Terms:
Algorithms