Learning Bayesian Networks with Low Rank Conditional Probability Tables

Adarsh Barik, Jean Honorio

Abstract

Learning the exact directed structure of a Bayesian network (BN) is a fundamental challenge in machine learning, often hindered by the exponential complexity of Conditional Probability Tables (CPTs) and the limitations of observational data. This paper introduces a novel method that assumes CPTs are "low rank," allowing for the recovery of the network structure in polynomial time. By integrating Fourier analysis of set functions with compressed sensing techniques, the proposed algorithm reconstructs the directed acyclic graph (DAG) using a black-box query model with efficient sample complexity.

Introduction

Traditionally, structure learning for Bayesian networks relies on observational data, which typically only identifies a Markov equivalence class rather than the true directed structure. Interventional data can resolve this ambiguity but is often costly or impractical. Furthermore, BNs face the "curse of dimensionality": for a node with $m$ parents, the CPT requires $2^{m+1}$ entries, leading to an exponential explosion in data requirements as the number of parents grows.

This work addresses these challenges by leveraging structural sparsity within the CPTs. By assuming that real-world interactions are often "simple" or low-rank, the authors provide a framework to bypass the exponential wall and recover the exact DAG structure efficiently.

Methodology

The proposed approach rests on three theoretical pillars:

  1. Low Rank CPTs: A CPT is defined as having "rank $k$" if it can be decomposed into a sum of smaller tables, each depending on at most $k$ parents. This assumption reflects a form of functional sparsity common in practical applications.
  2. Fourier Transformation: The authors establish a connection between low-rank CPTs and Fourier analysis. Treating the CPT as a real-valued set function, they demonstrate that low-rank properties in the spatial domain correspond to sparsity in the Fourier domain.
  3. Compressed Sensing: Utilizing the sparsity of the Fourier representation, the algorithm employs $L_1$-minimization to identify the parents of each node.

The Reconstruction Algorithm

The core process involves an iterative "peeling" strategy. The algorithm identifies "terminal nodes" (nodes without children in the current set) by detecting specific Fourier signatures—specifically, terminal nodes have non-zero Fourier coefficients only for empty or singleton sets. Once a terminal node and its parents are identified, the node is removed, and the process repeats until the entire DAG is reconstructed. A hybrid version of the algorithm can also utilize observational data to identify Markov Blankets, narrowing the search space for subsequent black-box queries.

Experimental Validation

The theoretical framework was validated using synthetic Bayesian networks with $n=20$ nodes. These networks were constructed with rank-2 CPTs and designed to be "faithful," ensuring the graph structure perfectly aligned with the underlying probability distributions. A simulated black-box model provided the necessary conditional probability samples for the queries.

Results

The primary contribution of this work is the achievement of polynomial efficiency in both time and sample complexity. As shown in Table 1, the proposed method significantly outperforms existing interventional approaches that scale exponentially with the number of nodes $n$.

Table 1: Complexity comparison of the proposed algorithm against existing methods.

Key experimental findings include:

  • Polynomial Bounds: The method runs in $O(n^4k\sqrt{n} \log n)$ time, a substantial improvement over the $O(2^n)$ complexity of prior methods.
  • Exact Recovery: The Hamming distance (measuring structural error) dropped to zero as the number of queries increased, indicating perfect reconstruction of the DAG.
  • High Reliability: Metrics such as the F1 score, precision, and recall consistently approached 1.0, demonstrating the robustness of the compressed sensing approach once a critical query threshold is reached.

Discussion and Future Work

While the current framework provides a powerful solution for binary random variables, several avenues for future research remain. The restriction to binary variables is a significant limitation; extending these Fourier-based methods to categorical or continuous variables is a priority. Additionally, the reliance on a "black-box" query model assumes access to conditional probabilities that may not always be available in real-world settings. Future work will explore whether similar low-rank assumptions can be applied to purely observational or interventional datasets to further generalize the utility of this approach.

Summary updated

BibTeX
@inproceedings{barik2019learning,
  author = {Adarsh Barik and Jean Honorio},
  title = {{Learning Bayesian Networks with Low Rank Conditional Probability Tables}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=NS5TNAU-2s},
}
Figure