Learning Bayesian network classifiers by maximizing conditional likelihood

ABSTRACT

Bayesian networks are a powerful probabilistic representation, and their use for classification has received considerable attention. However, they tend to perform poorly when learned in the standard way. This is attributable to a mismatch between the objective function used (likelihood or a function thereof) and the goal of classification (maximizing accuracy or conditional likelihood). Unfortunately, the computational cost of optimizing structure and parameters for conditional likelihood is prohibitive. In this paper we show that a simple approximation---choosing structures by maximizing conditional likelihood while setting parameters by maximum likelihood---yields good results. On a large suite of benchmark datasets, this approach produces better class probability estimates than naive Bayes, TAN, and generatively-trained Bayesian networks.

REFERENCES

• 1: Agresti, A. (1990). Categorical data analysis. New York, NY: Wiley.
• 2: Tim Van Allen , Russell Greiner, Model Selection Criteria for Learning Belief Nets: An Empirical Comparison, Proceedings of the Seventeenth International Conference on Machine Learning, p.1047-1054, June 29-July 02, 2000
• 3: Bilmes, J., Zweig, G., Richardson, T., Filali, K., Livescu, K., Xu, P., Jackson, K., Brandman, Y., Sandness, E., Holtz, E., Torres, J., & Byrne, B. (2001). Discriminatively structured graphical models for speech recognition (Tech. Rept.). Center for Language and Speech Processing, Johns Hopkins Univ., Baltimore, MD.
• 4: Blake, C., & Merz, C. J. (2000). UCI repository of machine learning databases. Dept. Information and Computer Science, Univ. California, Irvine, CA. http://www.ics.uci.edu/~mlearn/MLRepository.html.
• 5: David Maxwell Chickering , David Heckerman, Efficient Approximations for the MarginalLikelihood of Bayesian Networks with Hidden Variables, Machine Learning, v.29 n.2-3, p.181-212, Nov./Dec. 1997 [doi>10.1023/A:1007469629108]
• 6: Chow, C. K., & Liu, C. N. (1968). Approximating discrete probability distributions with dependence trees. IEEE Transactions on Information Theory, 14, 462--467.
• 7: Gregory F. Cooper , Edward Herskovits, A Bayesian Method for the Induction of Probabilistic Networks from Data, Machine Learning, v.9 n.4, p.309-347, Oct. 1992 [doi>10.1023/A:1022649401552]
• 8: Pedro Domingos , Michael Pazzani, On the Optimality of the Simple Bayesian Classifier under Zero-One Loss, Machine Learning, v.29 n.2-3, p.103-130, Nov./Dec. 1997 [doi>10.1023/A:1007413511361]
• 9: Duda, R. O., & Hart, P. E. (1973). Pattern classification and scene analysis. New York, NY: Wiley.
• 10: Jerome H. Friedman, On Bias, Variance, 0/1—Loss, and the Curse-of-Dimensionality, Data Mining and Knowledge Discovery, v.1 n.1, p.55-77, 1997 [doi>10.1023/A:1009778005914]
• 11: Nir Friedman , Dan Geiger , Moises Goldszmidt, Bayesian Network Classifiers, Machine Learning, v.29 n.2-3, p.131-163, Nov./Dec. 1997 [doi>10.1023/A:1007465528199]
• 12: Russell Greiner , Wei Zhou, Structural extension to logistic regression: discriminative parameter learning of belief net classifiers, Eighteenth national conference on Artificial intelligence, p.167-173, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 13: David Heckerman, A tutorial on learning with Bayesian networks, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 14: David Heckerman , Dan Geiger , David M. Chickering, Learning Bayesian Networks: The Combination of Knowledge and Statistical Data, Machine Learning, v.20 n.3, p.197-243, Sept. 1995 [doi>10.1023/A:1022623210503]
• 15: Jaakkola, T., Meila, M., & Jebara, T. (1999). Maximum entropy discrimination. In Advances in neural information processing systems 12. Cambridge, MA: MIT Press.
• 16: Tony Jebara , Alex Pentland, Maximum conditional likelihood via bound maximization and the CEM algorithm, Proceedings of the 1998 conference on Advances in neural information processing systems II, p.494-500, July 1999
• 17: Keogh, E., & Pazzani, M. (1999). Learning augmented Bayesian classifiers: A comparison of distribution-based and classification-based approaches. Proc. 7th Intl. Wk-shp. on AI and Statistics (pp. 225--230).
• 18: Ron Kohavi , George H. John, Wrappers for feature subset selection, Artificial Intelligence, v.97 n.1-2, p.273-324, Dec. 1997 [doi>10.1016/S0004-3702(97)00043-X]
• 19: Lam, W., & Bacchus, F. (1994). Learning Bayesian belief networks: An approach based on the MDL principle. Computational Intelligence, 10, 269--293.
• 20: Ng, A. Y., & Jordan, M. I. (2002). On discriminative vs. generative classifiers: A comparison of logistic regression and naive Bayes. In Advances in neural information processing systems 14. Cambridge, MA: MIT Press.
• 21: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 22: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 23: Foster Provost , Pedro Domingos, Tree Induction for Probability-Based Ranking, Machine Learning, v.52 n.3, p.199-215, September 2003 [doi>10.1023/A:1024099825458]
• 24: Foster Provost , Tom Fawcett, Robust Classification for Imprecise Environments, Machine Learning, v.42 n.3, p.203-231, March 2001 [doi>10.1023/A:1007601015854]
• 25: Rubinstein, Y. D., & Hastie, T. (1997). Discriminative vs. informative learning. Proc. 3rd Intl. Conf. on Knowledge Discovery and Data Mining (pp. 49--53).
• 26: Spirtes, P., Glymour, C., & Scheines, R. (1993). Causation, prediction, and search. New York, NY: Springer.
• 27: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995