ABSTRACT
The structure of a Bayesian network (BN) encodes variable independence. Learning the structure of a BN, however, is typically of high computational complexity. In this paper, we explore and represent variable independence in learning conditional probability tables (CPTs), instead of in learning structure. A full Bayesian network is used as the structure and a decision tree is learned for each CPT. The resulting model is called full Bayesian network classifiers (FBCs). In learning an FBC, learning the decision trees for CPTs captures essentially both variable independence and context-specific independence. We present a novel, efficient decision tree learning, which is also effective in the context of FBC learning. In our experiments, the FBC learning algorithm demonstrates better performance in both classification and ranking compared with other state-of-the-art learning algorithms. In addition, its reduced effort on structure learning makes its time complexity quite low as well.
- Cheng, J., Greiner, R., Kelly, J., Bell, D., & Liu, W. (2002). Learning Bayesian networks from data: An information-theory based approach. Artificial Intelligence Journal, 137:1--2, 43--90. Google ScholarDigital Library
- Chickering, D., Heckerman, D., & Meek, C. (1997). A Bayesian approach to learning Bayesian networks with local structure. In Proceedings of Thirteenth conference on Uncertainty in Artificial Intelligence, 80--89. Morgan Kaufmann. Google ScholarDigital Library
- Cooper, G., & Herskovits, E. (1992). A Bayesian method for the induction of probabilistic networks from data. Machine Learning, 9, 309--347. Google ScholarDigital Library
- Friedman, N., Geiger, D., & Goldszmidt, M. (1997). Bayesian network classifiers. Machine Learning, 29, 131--163. Google ScholarDigital Library
- Friedman, N., & Goldszmidt, M. (1996). Learning Bayesian networks with local structure. In Proceedings of the Twelfth Conference on Uncertainty in Artificial Intelligence, 252--262. Google ScholarDigital Library
- Friedman, N., & Yakhini, Z. (1996). On the sample complexity of learning Bayesian networks. In Proceedings of twelfth conference on uncertainty in artificial intelligence, 274--282. Google ScholarDigital Library
- Heckerman, D. (1991). Probabilistic similarity networks. MIT Press. Google ScholarDigital Library
- Heckerman, D. (1999). A tutorial on learning with Bayesian networks. In M. I. Jordan (Ed.), Learning in Graphical Models, 301--354. MIT Press. Google ScholarDigital Library
- Heckerman, D., Geiger, D., & Chickering, D. M. (1995). Learning Bayesian networks. The combination of knowledge and statistical data. Machine Learning, 20, 197--243. Google ScholarDigital Library
- Keerthi, S., Shevade, S., Bhattacharyya, C., & Murthy, K. (2001). Improvements to Platt's SMO algorithm for SVM classifier design. Neural Computation, 13(3), 637--649. Google ScholarDigital Library
- Kohavi, R. (1996). Scaling up the accuracy of naive-Bayes classifiers: A decision-tree hybrid. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, 202--207. AAAI Press.Google ScholarDigital Library
- Lam, W., & Bacchus, F. (1994). Learning Bayesian belief networks: an approach based on the MDL principle. Computational Intelligence, 10(4), 269--293.Google ScholarCross Ref
- Pearl, J. (1988). Probabilistic reasoning in intelligent systems:networks of plausible inference. Morgan Kauhmann. Google ScholarDigital Library
- Platt, J. C. (1998). Fast training of support vector machines using sequential minimal optimization. Advances in Kernel Methods-Support Vector Learning. MIT Press. Google ScholarDigital Library
- Provost, F., & Fawcett, T. (1997). Analysis and visualization of classifier performance: comparison under imprecise class and cost distribution. In Proceedings of the Third International Conference on Knowledge Discovery and Data Mining, 43--48. AAAI Press.Google Scholar
- Provost, F. J., & Domingos, P. (2003). Tree induction for probability-based ranking. Machine Learning, 52(3), 199--215. Google ScholarDigital Library
- Quinlan, J. (1993). C4.5: Programs for machine learning. Morgan Kaufmann: San Mateo, CA. Google ScholarDigital Library
- Teyssier, M., & Koller, D. (2005). Ordering-based search: A simple and effective algorithm for learning bayesian networks. In Proceedings of the Twenty-first Conference on Uncertainty in Artificial Intelligence, 584--590.Google Scholar
- Webb, G. I., Boughton, J., & Wang. Z. (2005). Not so naive Bayes: Aggregating one-dependence estimators. Journal of Machine Learning, 58(1), 5--54. Google ScholarDigital Library
- Witten, I. H., & Frank, E. (2000). Data mining practical machine learning tools and techniques with Java implementation. Morgan Kaufmann. Google ScholarDigital Library
Index Terms
- Full Bayesian network classifiers
Recommendations
Discrete Bayesian Network Classifiers: A Survey
We have had to wait over 30 years since the naive Bayes model was first introduced in 1960 for the so-called Bayesian network classifiers to resurge. Based on Bayesian networks, these classifiers have many strengths, like model interpretability, ...
Bayesian Network Classifiers
Special issue on learning with probabilistic representationsRecent work in supervised learning has shown that a surprisingly simple Bayesian classifier with strong assumptions of independence among features, called naive Bayes, is competitive with state-of-the-art classifiers such as C4.5. This fact raises the ...
Boosted Bayesian network classifiers
The use of Bayesian networks for classification problems has received a significant amount of recent attention. Although computationally efficient, the standard maximum likelihood learning method tends to be suboptimal due to the mismatch between its ...
Comments