Effective and efficient structure learning with pruning and model averaging strategies
This work addresses the computational complexity and noise sensitivity in Bayesian Network structure learning, offering an incremental improvement for researchers and practitioners in machine learning and data analysis.
The paper tackles the problem of learning Bayesian Network structures by introducing the Model Averaging Hill-Climbing (MAHC) algorithm, which combines aggressive pruning and model averaging strategies to achieve effective and efficient results, especially in noisy data conditions.
Learning the structure of a Bayesian Network (BN) with score-based solutions involves exploring the search space of possible graphs and moving towards the graph that maximises a given objective function. Some algorithms offer exact solutions that guarantee to return the graph with the highest objective score, while others offer approximate solutions in exchange for reduced computational complexity. This paper describes an approximate BN structure learning algorithm, which we call Model Averaging Hill-Climbing (MAHC), that combines two novel strategies with hill-climbing search. The algorithm starts by pruning the search space of graphs, where the pruning strategy can be viewed as an aggressive version of the pruning strategies that are typically applied to combinatorial optimisation structure learning problems. It then performs model averaging in the hill-climbing search process and moves to the neighbouring graph that maximises the objective function, on average, for that neighbouring graph and over all its valid neighbouring graphs. Comparisons with other algorithms spanning different classes of learning suggest that the combination of aggressive pruning with model averaging is both effective and efficient, particularly in the presence of data noise.