Abstract
In this paper we present several Bayesian algorithms for learning Tree Augmented Naive Bayes (TAN) models. We extend the results in Meila & Jaakkola (2000a) to TANs by proving that accepting a prior decomposable distribution over TAN’s, we can compute the exact Bayesian model averaging over TAN structures and parameters in polynomial time. Furthermore, we prove that the k-maximum a posteriori (MAP) TAN structures can also be computed in polynomial time. We use these results to correct minor errors in Meila & Jaakkola (2000a) and to construct several TAN based classifiers. We show that these classifiers provide consistently better predictions over Irvine datasets and artificially generated data than TAN based classifiers proposed in the literature.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Cerquides, J. (1999). Applying general Bayesian techniques to improve TAN induction. In Proceedings of the International Conference on Knowledge Discovery and Data Mining, KDD99 (pp. 292–296).
Chow, C., & Liu, C. (1968). Aproximatting discrete probability distributions with dependence trees. IEEE Transactions on Information Theory, 14, 462–497.
Domingos, P., & Pazzani, M. (1997). On the optimality of the simple Bayesian classifier under zero-one loss. Machine Learning, 29, 103–130.
Fawcett, T. (2003). Roc graphs: Notes and practical considerations for data mining researchers. Technical Report HPL-2003-4, HP Laboratories Palo Alto.
Friedman, N., Geiger, D., & Goldszmidt, M. (1997).Bayesian network classifiers. Machine Learning, 29, 131–163.
Hand, D. & Till, R. (2001). A simple generalization of the area under the roc curve to multiple class classification problems. Machine Learning, 45:2, 171–86.
Heckerman, D., Geiger, D., & Chickering, D. (1995). Learning bayesian networks: The combination of knowledge and statistical data. Machine Learning, 20, 197–243.
Ide, J., & Cozman, F. (2003). Generation of random bayesian networks with constraints on induced width, with applications to the average analysis od d-connectivity, quasi-random sampling, and loopy propagation. Technical report, University of Sao Paulo.
Katoh, N., Ibaraki, T., & Mine, H. (1981). An algorithm for finding k minimum spanning trees. SIAM J. Comput., 10:2, 247–55.
Kontkanen, P., Myllymaki, P., Silander, T., & Tirri H. (1998). Bayes Optimal Instance-Based Learning. In Machine Learning: ECML-98, Proceedings of the 10th European Conference, volume 1398 of Lecture Notes in Artificial Intelligence (pp. 77–88). Springer-Verlag.
Langley, P., Iba, W., & Thompson, K. (1992). An analysis of Bayesian classifiers. In Proceedings of the Tenth National Conference on Artificial Intelligence (pp. 223–228). AAAI Press and MIT Press.
Meila, M., & Jaakkola, T. (2000a). Tractable bayesian learning of tree belief networks. In Proc. of the Sixteenth Conference on Uncertainty in Artificial Intelligence (pp. 380–388).
Meila, M., & Jaakkola, T. (2000b). Tractable bayesian learning of tree belief networks. Technical Report CMU-RI-TR-00-15, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
Pettie, S., & Ramachandran, V. (2002). An optimal minimum spanning tree algorithm. Journal of the ACM (JACM), 49:1, 16–34.
Shoup, V. (2003). NTL: A library for doing number theory. http://www.shoup.net/ntl.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editors:
Pedro Larrañaga, Jose A. Lozano, Jose M. Peña and Iñaki Inza
Rights and permissions
About this article
Cite this article
Cerquides, J., de MÁntaras, R.L. TAN Classifiers Based on Decomposable Distributions. Mach Learn 59, 323–354 (2005). https://doi.org/10.1007/s10994-005-0470-7
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10994-005-0470-7