A statistical approach to decision tree modeling

ABSTRACT

A statistical approach to decision tree modeling is described. In this approach, each decision in the tree is modeled parametrically as is the process by which an output is generated from an input and a sequence of decisions. The resulting model yields a likelihood measure of goodness of fit, allowing ML and MAP estimation techniques to be utilized. An efficient algorithm is presented to estimate the parameters in the tree. The model selection problem is presented and several alternative proposals are considered. A hidden Markov version of the tree is described for data sequences that have temporal dependencies.

REFERENCES

• 1: Baum, L.E., Petrie, T., Soules, G., & Weiss, N. (1970). A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains. The Annals of Mathematical Statistics, 41, 164-171.
• 2: Bengio, Y., & Frasconi, P. (in press). Credit assignment through time: Alternatives to backpropagation. Neural Information Processing Systems 6. San Marco, CA: Morgan Kaufmann.
• 3: Breiman, L., Friedman, J. H., Olshen, R. A., & Stone, C. J. (1984). Classification and Regression Trees. Belmont, CA: Wadsworth International Group.
• 4: Cacciatore, T & Nowlan, S. (in press). Mixtures of controllers for jump linear and non-linear plants. Neural Information Processing Systems 6. San Mateo, CA: Morgan Kaufmann.
• 5: Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society B, 39, 1-38.
• 6: Draper, N. R., & Smith, H. (t981). Applied Regression Analysis. New York: John Wiley.
• 7: Duda, R. O., & Hart, P. E. (1973). Pattern Classification and Scene Analysis. New York: John Wiley.
• 8: Ghahramani, Z., & Jordan, M. I. (in press). Supervised learning from incomplete data via the EM approach. Neural Information Processing Systems 6. San Mateo, CA: Morgan Kaufmann.
• 9: Michael I. Jordan , Robert A. Jacobs, Hierarchical mixtures of experts and the EM algorithm, Neural Computation, v.6 n.2, p.181-214, March 1994 [doi>10.1162/neco.1994.6.2.181]
• 10: Michael I. Jordan , Lei Xu, Convergence Results for the EM Approach to Mixtures of Experts Architectures, Massachusetts Institute of Technology, Cambridge, MA, 1993
• 11: McCullagh, P. & Nelder, J.A. (1983). Generalized Linear Models. London: Chapman and Hall.
• 12: Meila, M. P., & Jordan, M. I. (1994). Learning the parameters of HMMs with auxiliary input. MIT Computational Cognitive Science Tech. Rep. 9401, Cambridge, MA.
• 13: Murthy, S. K., Kasif, S., & Salzberg, S. (1993). OCI.' A randomized algorithm for building oblique decision trees. Technical Report, Department of Computer Science, Johns Hopkins University.
• 14: Neal, R., & Hinton, G. E. (1993). A new view of the EM algorithm that justifies incremental and other variants. Submitted to Biometrika.
• 15: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 16: J. R. Quinlan , R. L. Rivest, Inferring decision trees using the minimum description length principle, Information and Computation, v.80 n.3, p.227-248, Mar. 1989 [doi>10.1016/0890-5401(89)90010-2]
• 17: Paul E. Utgoff , Carla E. Brodley, An incremental method for finding multivariate splits for decision trees, Proceedings of the seventh international conference (1990) on Machine learning, p.58-65, June 1990, Austin, Texas, United States
• 18: Xu, L., Jordan, M. I., & Hinton, G. E. (1994). An alternative mixture of experts model. MIT Computational Cognitive Science Tech. Rep. 9402, Cambridge, MA.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

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

General Terms:
Theory