Learning Discrete Bayesian Networks from Continuous Data

Yi-Chun Chen, Tim Allan Wheeler, Mykel John Kochenderfer

Introduction

Bayesian networks (BNs) are essential for modeling causality and uncertainty, yet most standard algorithms are optimized for discrete data. In practice, real-world datasets—ranging from medical metrics to sensor readings—are predominantly continuous. Bridging this gap typically involves discretization, but common methods like uniform-width binning often ignore variable dependencies, leading to suboptimal models. Advanced techniques such as the Minimum Description Length (MDL) principle offer better accuracy but suffer from cubic computational complexity ($O(n^3)$) and low sensitivity, frequently "under-discretizing" and missing subtle but critical boundaries.

This paper presents a principled Bayesian method for discretizing continuous variables within the context of learning Bayesian networks. By integrating a variable's Markov blanket into the discretization process, the proposed approach achieves superior model accuracy with quadratic computational complexity ($O(n^2)$).

Methodology

The core of the proposed approach is a Bayesian discretization method that optimizes binning policies relative to the global network structure rather than treating discretization as an isolated preprocessing step.

Markov Blanket Integration and Factorization

Unlike marginal methods that evaluate variables in isolation, this approach considers a variable’s Markov blanket—comprising its parents, children, and spouses. This ensures that the discretization preserves the probabilistic relationships defined by the network. The likelihood term is factored according to this blanket, allowing for efficient evaluation of discretization edges.

The factorization of the likelihood term based on the Markov blanket.

Computational Efficiency and Simultaneous Learning

By employing a specific prior that encourages edges between well-separated values, the optimization problem is reduced to $O(n^2)$ using dynamic programming. This is a significant improvement over the $O(n^3)$ complexity of MDL-based methods. Furthermore, the authors introduce an algorithm that alternates between structure learning (using the K2 algorithm) and discretization refinement. As the network structure evolves, the discretization is updated to maintain alignment with the learned dependencies.

The paper also defines integer representations for discretization policies, such as the number of instances before an edge ($\lambda$) or within an interval ($\gamma$), facilitating clear data handling.

Example of variable assignments and discretization policy representations.

Experimental Evaluation

The method was evaluated using several UCI Machine Learning Repository datasets (e.g., Auto MPG, Wine, Housing, Iris) and synthetic data designed to test sensitivity to sample size.

Key Results

  • Improved Log-Likelihood: Across all real-world datasets, the Bayesian method consistently achieved higher mean cross-validated log-likelihoods than MDL. For instance, on the Auto MPG dataset, the Bayesian method scored -26.04 compared to -30.40 for MDL.
  • Enhanced Sensitivity: The Bayesian approach utilizes factorial terms in its objective function, making it more sensitive to data variations than the count-ratio-based MDL. This allows it to identify meaningful discretization edges that MDL often overlooks.
  • Superior Data Fit: Qualitative analysis indicates that the resulting probability densities from Bayesian discretization closely mirror the original continuous distributions, whereas MDL frequently failed to create any edges for the same data.
  • Faster Convergence: On synthetic datasets, the Bayesian method converged to optimal discretization edges with significantly fewer samples than its MDL counterpart.

Discussion and Future Work

The transition from cubic to quadratic complexity represents a major gain in scalability, making the method viable for medium-sized datasets common in scientific research. However, the authors note that for networks exceeding 100 variables, the $O(n^2)$ cost may still be prohibitive, suggesting that greedy heuristic approximations might be necessary for high-dimensional data.

Future research directions include relaxing the restriction that edges must be placed at midpoints between unique observed values and extending the framework to cluster high-cardinality categorical variables. By treating discretization as an integral part of the modeling process, this work provides a robust foundation for learning more accurate and efficient Bayesian networks from continuous data.

Summary updated

BibTeX
@article{chen2017learning,
  author = {Yi-Chun Chen and Tim Allan Wheeler and Mykel John Kochenderfer},
  title = {{Learning Discrete Bayesian Networks from Continuous Data}},
  journal = {J. Artif. Intell. Res.},
  year = {2017},
  doi = {10.1613/jair.5371},
}
Figure