Interruptible anytime algorithms for iterative improvement of decision trees

ABSTRACT

Finding a minimal decision tree consistent with the examples is an NP-complete problem. Therefore, most of the existing algorithms for decision tree induction use a greedy approach based on local heuristics. These algorithms usually require a fixed small amount of time and result in trees that are not globally optimal. Recently, the LSID3 contract anytime algorithm was introduced to allow using extra resources for building better decision trees. A contract anytime algorithm needs to get its resource allocation a priori. In many cases, however, the time allocation is not known in advance, disallowing the use of contract algorithms. To overcome this problem, in this work we present two interruptible anytime algorithms for inducing decision trees. Interruptible anytime algorithms do not require their resource allocation in advance and thus must be ready to be interrupted and return a valid solution at any moment. The first interruptible algorithm we propose is based on a general technique for converting a contract algorithm to an interruptible one by sequencing. The second is an iterative improvement algorithm that repeatedly selects a subtree whose reconstruction is estimated to yield the highest marginal utility and rebuilds it with higher resource allocation. Empirical evaluation shows a good anytime behavior for both algorithms. The iterative improvement algorithm shows smoother performance profiles which allow more refined control.

REFERENCES

• 1: C. L. Blake and C. J. Merz. UCI repository of machine learning databases, 1998.
• 2: 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]
• 3: Mark Boddy , Thomas L. Dean, Deliberation scheduling for problem solving in time-constrained environments, Artificial Intelligence, v.67 n.2, p.245-285, June 1994 [doi>10.1016/0004-3702(94)90054-X]
• 4: R. R. Bouckaert. Choosing between two learning algorithms based on calibrated tests. In ICML'03, pages 51--58, Washington, DC, USA, 2003.
• 5: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 6: L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth and Brooks, Monterey, CA, 1984.
• 7: Christopher J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, v.2 n.2, p.121-167, June 1998 [doi>10.1023/A:1009715923555]
• 8: Mark William Craven , Jude W. Shavlik, Extracting comprehensible models from trained neural networks, 1996
• 9: Saher Esmeir , Shaul Markovitch, Lookahead-based algorithms for anytime induction of decision trees, Proceedings of the twenty-first international conference on Machine learning, p.33, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015373]
• 10: Wei Fan , Haixun Wang , Philip S. Yu , Sheng Ma, Is random model better? On its accuracy and efficiency, Proceedings of the Third IEEE International Conference on Data Mining, p.51, November 19-22, 2003
• 11: Yoav Freund , Llew Mason, The Alternating Decision Tree Learning Algorithm, Proceedings of the Sixteenth International Conference on Machine Learning, p.124-133, June 27-30, 1999
• 12: Evgeniy Gabrilovich , Shaul Markovitch, Text categorization with many redundant features: using aggressive feature selection to make SVMs competitive with C4.5, Proceedings of the twenty-first international conference on Machine learning, p.41, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015388]
• 13: T. Hastie, R. Tibshirani, and J. Friedman. The elements of statistical learning: data mining, inference, and prediction. New York: Springer-Verlag, 2001.
• 14: Eric Joel Hovitz, Computation and action under bounded resources, Stanford University, Stanford, CA, 1991
• 15: Jin Huang , Jingjing Lu , Charles X. Ling, Comparing Naive Bayes, Decision Trees, and SVM with AUC and Accuracy, Proceedings of the Third IEEE International Conference on Data Mining, p.553, November 19-22, 2003
• 16: L. Hyafil and R. L. Rivest. Constructing optimal binary decision trees is NP-complete. Information Processing Letters, 5(1):15--17, 1976.
• 17: Mark Last , Abraham Kandel , Oded Maimon , Eugene Eberbach, Anytime Algorithm for Feature Selection, Revised Papers from the Second International Conference on Rough Sets and Current Trends in Computing, p.532-539, October 16-19, 2000
• 18: D. J. Lizotte, O. Madani, and R. Greiner. Budgeted learning of naive bayes classifiers. In UAI'03, Acapulco, Mexico, 2003.
• 19: O. J. Murphy , R. L. McCraw, Designing Storage Efficient Decision Trees, IEEE Transactions on Computers, v.40 n.3, p.315-320, March 1991 [doi>10.1109/12.76408]
• 20: David William Opitz, An anytime approach to connectionist theory refinement: refining the topologies of knowledge-based neural networks, University of Wisconsin at Madison, Madison, WI, 1996
• 21: Athanassios Papagelis , Dimitrios Kalles, Breeding Decision Trees Using Evolutionary Techniques, Proceedings of the Eighteenth International Conference on Machine Learning, p.393-400, June 28-July 01, 2001
• 22: J. R. Quinlan, Induction of Decision Trees, Machine Learning, v.1 n.1, p.81-106 [doi>10.1023/A:1022643204877]
• 23: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 24: Stuart Russell , Eric Wefald, Principles of metareasoning, Proceedings of the first international conference on Principles of knowledge representation and reasoning, p.400-411, December 1989
• 25: S. J. Russell and S. Zilberstein. Composing real-time systems. In IJCAI'91, pages 212--217, Sydney, Australia, 1991.
• 26: Shlomo Zilberstein , Stuart Russell, Optimal composition of real-time systems, Artificial Intelligence, v.82 n.1-2, p.181-213, April 1996 [doi>10.1016/0004-3702(94)00074-3]
• 27: Robert E. Schapire, A Brief Introduction to Boosting, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1401-1406, July 31-August 06, 1999
• 28: Yunfeng Shan , Evangelos E. Milios , Andrew J. Roger , Christian Blouin , Edward Susko, Automatic Recognition of Regions of Intrinsically Poor Multiple Alignment Using Machine Learning, Proceedings of the IEEE Computer Society Conference on Bioinformatics, p.482, August 11-14, 2003
• 29: Jude W. Shavlik , Raymond J. Mooney , Geoffrey G. Towell, Symbolic and Neural Learning Algorithms: An Experimental Comparison, Machine Learning, v.6 n.2, p.111-143, March 1991 [doi>10.1023/A:1022602303196]
• 30: Paul E. Utgoff, Incremental Induction of Decision Trees, Machine Learning, v.4 n.2, p.161-186, November 1989 [doi>10.1023/A:1022699900025]
• 31: Paul E. Utgoff , Neil C. Berkman , Jeffery A. Clouse, Decision Tree Induction Based on Efficient Tree Restructuring, Machine Learning, v.29 n.1, p.5-44, Oct. 1997 [doi>10.1023/A:1007413323501]
• 32: X. Zhu, S. Sun, S. E. Cheng, and M. Bern. Classification of protein crystallization imagery. In EMBS'04, San Francisco, CA, 2004.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Experimentation

Keywords:
anytime algorithms, anytime learning, cost-quality tradeoff, decision trees, hard concepts