Towards tight bounds for rule learning

ABSTRACT

While there is a lot of empirical evidence showing that traditional rule learning approaches work well in practice, it is nearly impossible to derive analytical results about their predictive accuracy. In this paper, we investigate rule-learning from a theoretical perspective. We show that the application of McAllester's PAC-Bayesian bound to rule learning yields a practical learning algorithm, which is based on ensembles of weighted rule sets. Experiments with the resulting learning algorithm show not only that it is competitive with state-of-the-art rule learners, but also that its error rate can often be bounded tightly. In fact, the bound turns out to be tighter than one of the "best" bounds for a practical learning scheme known so far (the Set Covering Machine). Finally, we prove that the bound can be further improved by allowing the learner to abstain from uncertain predictions.

REFERENCES

• 1: Blake, C., & Merz, C. (1998). UCI repository of machine learning databases.
• 2: Leo Breiman, Random Forests, Machine Learning, v.45 n.1, p.5-32, October 1 2001 [doi>10.1023/A:1010933404324 ]
• 3: William W. Cohen , Yoram Singer, A simple, fast, and effective rule learner, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.335-342, July 18-22, 1999, Orlando, Florida, United States
• 4: Cohen, W. W. (1995). Fast effective rule induction. Proc. 12th International Conf. on Machine Learning (pp. 115--123). Morgan Kaufmann.
• 5: Eibe Frank , Ian H. Witten, Generating Accurate Rule Sets Without Global Optimization, Proceedings of the Fifteenth International Conference on Machine Learning, p.144-151, July 24-27, 1998
• 6: Mostefa Golea , Peter L. Bartlett , Wee Sun Lee , Llew Mason, Generalization in decision trees and DNF: does size matter?, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.259-265, July 1998, Denver, Colorado, United States
• 7: Hoos, H. H. (1998). Stochastic local search -- methods, models, applications. Doctoral dissertation, TU Darmstadt.
• 8: Michael J. Kearns , Umesh V. Vazirani, An introduction to computational learning theory, MIT Press, Cambridge, MA, 1994
• 9: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009 ]
• 10: Yishay Mansour , David A. McAllester, Generalization Bounds for Decision Trees, Proceedings of the Thirteenth Annual Conference on Computational Learning Theory, p.69-74, June 28-July 01, 2000
• 11: Marchand, M., Shah, M., Shawe-Taylor, J., & Sokolova, M. (2003). The set covering machine with data-dependent half-spaces. Proc. 20th International Conf. on Machine Learning (pp. 520--527). Morgan Kaufmann.
• 12: Mario Marchand , John Shawe-Taylor, Learning with the Set Covering Machine, Proceedings of the Eighteenth International Conference on Machine Learning, p.345-352, June 28-July 01, 2001
• 13: David A. McAllester, PAC-Bayesian model averaging, Proceedings of the twelfth annual conference on Computational learning theory, p.164-170, July 07-09, 1999, Santa Cruz, California, United States [doi>10.1145/307400.307435]
• 14: Bernhard Pfahringer , Geoffrey Holmes , Richard Kirkby, Optimizing the Induction of Alternating Decision Trees, Proceedings of the 5th Pacific-Asia Conference on Knowledge Discovery and Data Mining, p.477-487, April 16-18, 2001
• 15: Rückert, U., & Kramer, S. (2003). Stochastic local search in k-term DNF learning. Proc. 20th International Conf. on Machine Learning (pp. 648--655). AAAI Press.
• 16: Sokolova, M., Marchand, M., Japkowicz, N., & Shawe-Taylor, J. (2003). The decision list machine. Advances in Neural Information Processing Systems 15 (pp. 921--928). MIT-Press, Cambridge, MA, USA.
• 17: Sholom M. Weiss , Nitin Indurkhya, Lightweight Rule Induction, Proceedings of the Seventeenth International Conference on Machine Learning, p.1135-1142, June 29-July 02, 2000
• 18: Ian H. Witten , Eibe Frank, Data mining: practical machine learning tools and techniques with Java implementations, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000