Learning hierarchical rule sets

ABSTRACT

We present an algorithm for learning sets of rules that are organized into up to k levels. Each level can contain an arbitrary number of rules “if c then l” where l is the class associated to the level and c is a concept from a given class of basic concepts. The rules of higher levels have precedence over the rules of lower levels and can be used to represent exceptions. As basic concepts we can use Boolean attributes in the infinite attribute space model, or certain concepts defined in terms of substrings. Given a sample of m examples, the algorithm runs in polynomial time and produces a consistent representation of size O((log m)knk), where n is the size of the smallest consistent representation with k levels of rules. This implies that the algorithm learns in the PAC model. The algorithm repeatedly applies the greedy heuristics for weighted set cover. The weights are obtained from approximate solutions to previous set cover problems.

REFERENCES

• BEHW87: Alselm Blumer , Andrzej Ehrenfeucht , David Haussler , Manfred K. Warmuth, Occam's razor, Information Processing Letters, v.24 n.6, p.377-380, 6 April 1987 [doi>10.1016/0020-0190(87)90114-1]
• BHL91: Avrim Blum , Lisa Hellerstein , Nick Littlestone, Learning in the presence of finitely or infinitely many irrelevant attributes, Proceedings of the fourth annual workshop on Computational learning theory, p.157-166, August 05-07, 1991, Santa Cruz, California, United States
• Blu90: A. Blum, Learning boolean functions in an infinite attribute space, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.64-72, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100224]
• KL88: Michael Kearns , Ming Li, Learning in the presence of malicious errors, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.267-280, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62238]
• KT91: Phokion G. Kolaitis and Madhukar N. Thakur. Approximation properties of NP minimization classes. In Proceedings of the sixth Annual Structure in Complexity Theory Conference, pages 353-366, Los Alamitos, California, 1991. IEEE Computer Society Press.
• Lev89: Hector J. Levesque. Knowledge representation and reasoning. In John Mylopoulos and Micheal L. Brodie, editors, Readings in Artificial Intelligence ~4 Databases, pages 35-51, San Mateo, California, 1989. Morgan Kaufmann Publishers.
• Lia83: Franklin Mark Liang. Word Hy-phen-a-tion by Com-put-er. PhD thesis, Stanford University, California, June 1983.
• Lit88: Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
• OG90: Pekka Orponen , Russell Greiner, On the sample complexity of finding good search strategies, Proceedings of the third annual workshop on Computational learning theory, p.352-358, August 06-08, 1990, Rochester, New York, United States
• PW90: Leonard Pitt , Manfred K. Warmuth, Prediction-preserving reducibility, Journal of Computer and System Sciences, v.41 n.3, p.430-467, Dec. 1990 [doi>10.1016/0022-0000(90)90028-J]
• Riv87: Ronald L. Rivest, Learning Decision Lists, Machine Learning, v.2 n.3, p.229-246, November 1987 [doi>10.1023/A:1022607331053]
• Tou86: David S. Touretzky, The mathematics of inheritance systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1986

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Theory, Verification