Efficient and Accurate Learning of Bayesian Networks using Chi-Squared Independence Tests
Yi Tang, Sargur N. Srihari · 2013
Bayesian network structure learning is a well-known NP-complete problem, whose solution is of importance in machine learning. Two algorithms are proposed, both of which assess dependency between variables using the chi-squared test of independence between pairs of variables and the log-likelihood evaluation criterion for the network. The first determines the effect of adding a potential edge (in both directions) on the loglikelihood. The second uses K-L divergence to determine direction, and edges to be included are determined by thresholding normalized chi-squared statistics. Experiments on multinomial data show that the proposed algorithms are more efficient and accurate than an optimized branch and bound algorithm, and human experts. 1.