Approximate Learning of High Dimensional Bayesian Network Structures via Pruning of Candidate Parent Sets

Area of Science:

• Computer Science
• Artificial Intelligence
• Machine Learning

Background:

• Exact learning of Bayesian Network (BN) structures is computationally infeasible for complex, high-dimensional networks.
• Approximate learning algorithms offer speed but often at the cost of accuracy.
• Existing score-based algorithms face challenges with very large numbers of variables.

Purpose of the Study:

• To explore a novel strategy for pruning candidate parent sets in score-based BN structure learning.
• To enhance the efficiency of learning algorithms for high-dimensional Bayesian Networks.
• To analyze the trade-off between pruning aggressiveness, learning speed, and model accuracy.

Main Methods:

• Developed a pruning strategy to reduce the size of candidate parent sets during BN structure learning.
• Integrated this pruning phase into existing score-based algorithms.
• Evaluated the impact of different pruning levels on learning speed and model fitting accuracy.

Main Results:

• Demonstrated that pruning candidate parent sets can significantly improve learning speed for high-dimensional BN problems.
• Quantified the relationship between the level of pruning and the resulting loss in accuracy.
• Showcased that aggressive pruning is often necessary for tractable approximate solutions in complex networks.

Conclusions:

• The proposed pruning strategy is an effective addition to score-based algorithms for tackling high-dimensional BN learning.
• Careful tuning of pruning levels is essential to achieve desired speed-accuracy trade-offs.
• This approach offers a viable path towards approximate solutions for computationally intensive network structures.