Proceedings

Learning Decision Lists over Tree Patterns and Its Application

Download BibTeX Cite

Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Machine Learning. Pages 995-1000.

© 1993 International Joint Conferences on Artificial Intelligence

Abstract

This paper introduces a new concept , a decision tree (or list) over tree patterns, which is a natural extension of a decision tree (or decision list) , for dealing with tree structured objects. The learnability of this class is studied within the framework of the Probably Approximately Correct learning model and the Identification in the Limit model. It is found that the class k-node-DLRTP, a subclass of decision lists over regular tree patterns, is not polynomial time PAC learnable if NP:fRP , but that the class knode-DLRTP(m), a subclass ofk-node-DLRTP where the number of variables in each tree pattern is bounded by m, is polynomial time PAC learnable. We also show that the class of decision lists over regular tree patterns is polynomial time inferable in the limit. Then we propose a more practical learning algorithm which employs heuristics based on an information theoretical evaluation function. This algorithm is applied to learning control strategies of rules in various domains , and its effectiveness is shown.

  1. [Quinlan, 1986] J. R. Quinlan. Induction of Decision Trees . Machine Learning, 1:81-106, 1986.
  2. [Quinlan and Rivest, 1989] J. R. Quinlan and R. L. Rivest. Inferring Decision Trees Using Minimum De- scription Length Principle. Information and Compu- tation, 80:227-248, 1989.
  3. [Valiant, 1984] L. G. Valiant. A Theory of Learnable. Comm. Assoc. Computing Machinery, 27:1134-1142, 1984.
  4. [Gold, 1967] E. M. Gold. Language Identification in the Limit. Information and Control, 10:447-474, 1967.
  5. [Plotkin, 1970] G. D. Plotkin. A Note on Inductive Gen- eralization. Machine Intelligence, 5:153-163, 1970.
  6. [Arimura et al., 1970] H. Arimura, T . Shinohara, and S. Otsuki. Polynomial Time Inference of Unions of Tree Pattern Languages. In Proceedings of the Sec- ond Workshop on Algorithmic Learning Theory, pages 105-114, 1991.
  7. [Rivest, 1987] R. L. Rivest. Learning Decision Lists. Ma- chine Learning, 2:229-246 , 1987.
  8. [Natarajan, 1989] B. K. Natarajan. On Learning Sets and Functions. Machine Learning, 4:67-97, 1989.
  9. [Kobayashi, 1993] S. Kobayashi. Explanation Based Learning: Extracting Corrunon Structures from Mul- tiple Training Examples PH.D. Th., Dept. of Aero- nautics, Tokyo University, 1993, in Japanese.
  10. [Arikawa et al., 1992] S. Arikawa, S. Kuhara, S. Miyano, Y. Mukouchi, A. Shinohara, and T. Shinohara. A Ma- chine Discovery from Amino Acid Sequences by Deci- sion Trees over Regular Patterns. In Proceedings of International Conference on Fifth Generation Com- puter Systems, pages 618-625, 1992.
  11. [Hyafil and Rivest, 1976] L. Hyafil and R. L. Rivest. Constructing Optimal Binary Decision Trees is NP- Complete. Information Processing Letters, 5:15-17, 1976.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards