Bayesian networks have long been a popular medium for graphically representing the probabilistic dependencies which exist in a domain. State-of-the-art tree-augmented naive Bayes (TAN) builds maximum weighted spanning tree to represent 1-dependence relationships between attributes. In this paper, we propose to optimize the structure of TAN applying heuristic search to sort attribute and filtering technique to remove weak conditional dependencies. Extensive experimental results on 35 data sets from University of California at Irvine (UCI) machine learning repository reveal that the proposed algorithm achieves competitive generalization performance and even outperforms higher-dependence BNCs like k-dependence Bayesian network while retaining excellent strucutre complexity.

To mitigate the negative effect of classification bias caused by overfitting, semi-naive Bayesian techniques seek to mine the implicit dependency relationships in unlabeled testing instances. By redefining some criteria from information theory, Target Learning (TL) proposes to build for each unlabeled testing instance $\mathcal{P}$ the Bayesian Network Classifier BNC ${}_{\mathcal{P}}$ , which is independent and complementary to BNC ${}_{\mathcal{T}}$ learned from training data $\mathcal{T}$ . In this paper, we extend TL to Universal Target Learning (UTL) to identify redundant correlations between attribute values and maximize the bits encoded in the Bayesian network in terms of log likelihood. We take the k-dependence Bayesian classifier as an example to investigate the effect of UTL on BNC ${}_{\mathcal{P}}$ and BNC ${}_{\mathcal{T}}$ . Our extensive experimental results on 40 UCI datasets show that UTL can help BNC improve the generalization performance.