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.
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.
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