Finding Optimal Bayesian Networks with Local Structure

Topi Talvitie, Ralf Eggeling, Mikko KoivistoPGM 2018 · OpenReview

Abstract

The idea of using decision trees as local models in Bayesian networks is revisited. A class of dyadic decision trees—proposed previously only for continuous conditioning variables—is augmented by introducing recursive partitioning for categorical variables. This allows for an exact search algorithm to find the mathematically optimal structure, turning a traditionally intractable search problem into one solvable via exact dynamic programming.

Introduction

In a Bayesian Network (BN), a complex joint distribution is represented as a product of local conditional probability distributions (CPDs). Traditionally, these are represented as "Full Tables" (CPTs), which grow exponentially with the number of parent nodes. This growth often leads to overfitting and computational bottlenecks.

Decision trees, such as CART, offer a more efficient alternative by capturing context-specific independence: a variable might only depend on a specific parent if another parent takes a certain value. While decision trees make BNs more parsimonious and statistically efficient, finding the optimal tree structure is NP-hard. Consequently, most research has relied on greedy "hill-climbing" heuristics, which offer no guarantees of optimality. This paper introduces PCART (Partition-Dyadic Classification and Regression Trees), a model class that enables finding the mathematically optimal BN structure when using decision trees as local models.

The PCART Model

The PCART model bridges the gap between flexibility and searchability by imposing specific constraints on the tree structure:

  • Continuous Variables: The model uses "dyadic splits," meaning a range is only ever split at its midpoint. This significantly restricts the search space while retaining most of the statistical power of standard CART.
  • Categorical Variables: It introduces "partition" splits, allowing arbitrary recursive binary splitting of the state space.
Example of a PCART decision tree with dyadic splits for continuous variables and partition splits for categorical variables.

By restricting the split points, the authors turn the local structure search into a discrete optimization problem that can be solved exactly.

Optimization Framework

The authors propose a two-phase optimization framework to find the global optimum:

  1. Phase I (Local Scoring): A Dynamic Programming (DP) algorithm finds the optimal PCART tree for every potential parent set. To achieve high performance, the authors utilize bit-vector representations and bottom-up iteration instead of recursion. This allows the algorithm to efficiently prune the search space of possible trees.
  2. Phase II (Global Search): Once local scores are computed, state-of-the-art exact DAG solvers (such as CPBayes) are used to find the globally optimal network structure.
Bit-vector representation used in the dynamic programming algorithm to efficiently find optimal local structures.

Key Insights and Results

The approach was evaluated using synthetic benchmark networks (Alarm, Insurance, Water) and real-world UCI datasets (Mushroom, Parkinsons-Telemonitoring, etc.). Several key insights emerged:

  • Parsimony and Power: Because PCART uses fewer parameters than a full table, it is less prone to overfitting. This makes it significantly better at detecting "weak arcs"—subtle dependencies that a full-table model might dismiss as noise.
  • Better Structure Recovery: In synthetic tests, PCART variants consistently achieved lower Structural Hamming Distance (SHD) compared to standard full-table models, meaning they stayed closer to the true underlying network structure.
  • Computational Feasibility: The exact algorithm can handle networks with dozens of variables and a maximum indegree (number of parents) of 4 within a few hours. Interestingly, the DAG optimization phase was often faster for PCART than for Full Table models because the parsimonious scores allowed for more effective pruning.

Conclusion

By removing the "uncontrolled uncertainty" of greedy algorithms, PCART allows researchers to distinguish whether a model performs poorly because the model class is insufficient or because the search heuristic failed. While currently limited to moderate indegrees, the success of dyadic splits suggests a promising path forward for exact learning in high-dimensional Bayesian Networks.

Summary updated

Abstract

The idea of using decision trees as local models in Bayesian networks is revisited. A class of dyadic decision trees—proposed previously only for continuous conditioning variables—is augmented by i...
BibTeX
@inproceedings{talvitie2018finding,
  author = {Topi Talvitie and Ralf Eggeling and Mikko Koivisto},
  title = {{Finding Optimal Bayesian Networks with Local Structure}},
  booktitle = {PGM},
  year = {2018},
  url = {https://openreview.net/forum?id=NaUlzmSaohs},
}
Figure