Latent Tree Models and Approximate Inference in Bayesian Networks

Yi Wang, Nevin Lianwen Zhang, Tao ChenAAAI 2008 · OpenReview

Abstract

We propose a novel method for approximate inference in Bayesian networks (BNs). The idea is to sample data from a BN, learn a latent tree model (LTM) from the data offline, and when online, make inference with the LTM instead of the original BN. Because LTMs are tree-structured, inference takes linear time. In the meantime, they can represent complex relationship among leaf nodes and hence the approximation accuracy is often good. Empirical evidence shows that our method can achieve good approximation accuracy at low online computational cost.

1. Introduction

Bayesian Networks (BNs) are fundamental tools for reasoning under uncertainty. However, their practical application is often limited by the computational complexity of inference, which is known to be NP-hard. In dense networks, exact inference becomes mathematically intractable, necessitating approximate methods. While techniques like Loopy Belief Propagation (LBP) exist, they may suffer from convergence issues or high computational costs in extremely complex models.

This paper introduces LTAB (Latent Tree Approximation of Bayesian networks), a framework that bridges the gap between model expressivity and inferential efficiency. By approximating a complex BN with a Latent Tree Model (LTM), LTAB enables online probabilistic queries to be answered in linear time.

2. The LTAB Framework

The LTAB algorithm operates in two distinct phases: an intensive offline learning phase and a high-speed online inference phase.

2.1 Offline Learning and Model Simplification

The offline phase begins by generating a large synthetic dataset from the target BN using logic sampling. From this data, a tree structure is learned by hierarchically clustering variables based on Mutual Information. To capture dependencies without introducing cycles, "latent" (hidden) variables are introduced as parents of correlated nodes.

A critical component of LTAB is the regularization and simplification of the learned model. The complexity of the LTM is controlled by a parameter $C$, which defines the maximum cardinality (number of states) for latent variables. This parameter serves as a tunable "knob" to balance approximation accuracy against computational speed. After structure learning, the Expectation-Maximization (EM) algorithm is employed to optimize parameters, followed by pruning redundant hidden nodes to ensure the model remains as lean as possible.

Figure 1: The transformation process from a complex Bayesian network (a) to a simplified Latent Tree Model (d) through intermediate latent tree (b) and regularized (c) stages.

2.2 Online Inference

Once the LTM is established, it serves as the surrogate for the original BN. Because the model is a tree, inference can be performed in linear time relative to the number of nodes using standard algorithms like Clique Tree Propagation (CTP). This predictability in runtime is a significant advantage for real-time systems where computational budgets are tight.

3. Experimental Evaluation

The researchers evaluated LTAB across eight benchmark networks, including standard models like ALARM and INSURANCE, as well as densely connected networks such as MILDEW and BARLEY.

3.1 Accuracy and the Cardinality Trade-off

Experiments demonstrated that increasing the latent cardinality $C$ consistently reduces the KL divergence between the LTM and the original BN distribution, indicating improved accuracy. However, this improvement follows a curve of diminishing returns, where excessively high $C$ values may lead to overfitting on the sampled data.

Figure 2: Average KL divergence vs. latent cardinality C for the WIN95PTS network, illustrating the trade-off between model complexity and approximation accuracy.

3.2 Computational Performance

In dense networks where exact inference is notoriously slow, LTAB achieved speedups of two to three orders of magnitude compared to exact CTP. Furthermore, it significantly outperformed LBP in speed while maintaining competitive, and in some cases superior, accuracy. For instance, in the MILDEW and BARLEY networks, LTAB provided a "middle ground" that was structurally simple enough for fast inference but expressive enough to capture nuanced relationships.

4. Conclusion and Future Work

LTAB provides a robust method for fast approximate inference by leveraging the structural advantages of latent trees. While the offline training phase is computationally expensive—sometimes requiring weeks for EM convergence—the resulting models offer unparalleled online performance. Future research may focus on reducing offline training time and adapting the framework for dynamic networks where the underlying structure evolves over time.

Summary updated

Abstract

We propose a novel method for approximate inference in Bayesian networks (BNs). The idea is to sample data from a BN, learn a latent tree model (LTM) from the data offline, and when online, make inference with the LTM instead of the original BN. Because LTMs are tree-structured, inference takes linear time. In the meantime, they can represent complex relationship among leaf nodes and hence the approximation accuracy is often good. Empirical evidence shows that our method can achieve good approximation accuracy at low online computational cost.
BibTeX
@inproceedings{wang2008latent,
  author = {Yi Wang and Nevin Lianwen Zhang and Tao Chen},
  title = {{Latent Tree Models and Approximate Inference in Bayesian Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
  url = {https://openreview.net/forum?id=ryZtC6gO-S},
}
Figure