# Properties of Bayesian Belief Network Learning Algorithms

arXiv: https://arxiv.org/abs/1302.6792 · HTML: https://mlsanity.com/paper/1302.6792/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2013.

## Built on by (most cited first, 13 of 13)

- [A survey of Bayesian Network structure learning](https://mlsanity.com/paper/2109.11415/) (2021)
- [The impact of prior knowledge on causal structure learning](https://mlsanity.com/paper/2102.00473/) (2021)
- [Causal Discovery with Fewer Conditional Independence Tests](https://mlsanity.com/paper/2406.01823/) (2024)
- [Effective and efficient structure learning with pruning and model averaging strategies](https://mlsanity.com/paper/2112.00398/) (2021)
- [Open problems in causal structure learning: A case study of COVID-19 in the UK](https://mlsanity.com/paper/2305.03859/) (2023)
- [The Impact of Variable Ordering on Bayesian Network Structure Learning](https://mlsanity.com/paper/2206.08952/) (2022)
- [Integrating Probabilistic Trees and Causal Networks for Clinical and Epidemiological Data](https://mlsanity.com/paper/2501.15973/) (2025)
- [Probabilistic Multi-Dimensional Classification](https://mlsanity.com/paper/2306.06517/) (2023)
- [An Efficient Procedure for Computing Bayesian Network Structure Learning](https://mlsanity.com/paper/2407.17072/) (2024)
- [MEC-IP: Efficient Discovery of Markov Equivalent Classes via Integer Programming](https://mlsanity.com/paper/2410.18147/) (2024)
- [Binned semiparametric Bayesian networks for efficient kernel density estimation](https://mlsanity.com/paper/2506.21997/) (2025)
- [Learning Bayesian and Markov Networks with an Unreliable Oracle](https://mlsanity.com/paper/2603.09563/) (2026)
- [Transfer learning for nonparametric Bayesian networks](https://mlsanity.com/paper/2604.01021/) (2026)

## Abstract (arXiv)

Bayesian belief network learning algorithms have three basic components: a measure of a network structure and a database, a search heuristic that chooses network structures to be considered, and a method of estimating the probability tables from the database. This paper contributes to all these three topics. The behavior of the Bayesian measure of Cooper and Herskovits and a minimum description length (MDL) measure are compared with respect to their properties for both limiting size and finite size databases. It is shown that the MDL measure has more desirable properties than the Bayesian measure when a distribution is to be learned. It is shown that selecting belief networks with certain minimallity properties is NP-hard. This result justifies the use of search heuristics instead of exact algorithms for choosing network structures to be considered. In some cases, a collection of belief networks can be represented by a single belief network which leads to a new kind of probability table estimation called smoothing. We argue that smoothing can be efficiently implemented by incorporating it in the search heuristic. Experimental results suggest that for learning probabilities of belief networks smoothing is helpful.