Dynamic Trees: A Structured Variational Method Giving Efficient Propagation Rules

Amos J. Storkey

Introduction

Hierarchical models, such as quadtrees, are widely used in image processing due to their ability to facilitate fast, exact inference. However, their fixed structures often result in "blocky" artifacts because spatially adjacent pixels may be distant within the hierarchy. Dynamic Trees (DTs) address this by allowing each node to stochastically select its parent, creating a mixture of possible tree structures that eliminates rigid boundaries.

A Dynamic Tree allows nodes to choose parents, creating a flexible mixture of structures.

While DTs offer greater flexibility, they make exact inference computationally intractable due to the exponential growth of possible tree configurations. Previous approaches relied on Mean Field approximations, which assume independence between nodes in the posterior. This assumption often fails to capture the high correlations inherent in tree structures, leading to suboptimal data interpretations.

Structured Variational Inference

This paper proposes a Structured Variational Approach that preserves dependencies between node states and tree structures. Instead of a fully factorized approximating distribution, the method employs a distribution $Q(Z, X)$ where the state of a node $X$ is conditionally dependent on the chosen tree structure $Z$.

The resulting approximation is itself a dynamic tree, enabling the model to capture the conditional dependencies that Mean Field ignores. The author derives efficient "propagation rules" for optimizing parameters, which function similarly to standard Belief Propagation (BP). Notably, these updates can be completed in just two passes—one upward and one downward—with $O(n)$ complexity, making the method significantly more efficient than iterative variational schemes.

Experimental Results

The method was evaluated on synthetic problems to compare against exact ground truths. In a 1D Markovian process experiment involving 150 cases, the structured method consistently outperformed the Mean Field approach.

KL divergence comparison: The structured method consistently achieves lower error (KL divergence) than the Mean Field approach.

Key findings include:

  • Improved Accuracy: On a 4-layer test network, the structured variational method achieved an average KL divergence of 5.5, outperforming Loopy Belief Propagation (7.0).
  • Lower Free Energy: The structured approach provided a tighter bound on the true log-likelihood of the data compared to Mean Field.
  • Symmetry Breaking Avoidance: Unlike Mean Field, which often suffers from "spontaneous symmetry breaking" (where high-level nodes polarize and flatten the tree), the structured approach maintains correlations and explores alternative structural interpretations.

Conclusion

The structured variational method provides a theoretical and practical bridge between variational inference and exact inference on graphs. By utilizing a more complex but structured approximation, the author achieves a more stable and efficient update algorithm. While the current model assumes independent parent selection for each node, future work could explore more complex structural priors to further enhance image segmentation and modeling tasks.

Summary updated

Abstract

Dynamic trees are mixtures of tree structured belief networks. They solve some of the problems of fixed tree networks at the cost of making exact inference intractable. For this reason approximate methods such as sampling or mean field approaches have been used. However, mean field approximations assume a factorized distribution over node states. Such a distribution seems unlickely in the posterior, as nodes are highly correlated in the prior. Here a structured variational approach is used, where the posterior distribution over the non-evidential nodes is itself approximated by a dynamic tree. It turns out that this form can be used tractably and efficiently. The result is a set of update rules which can propagate information through the network to obtain both a full variational approximation, and the relevant marginals. The progagtion rules are more efficient than the mean field approach and give noticeable quantitative and qualitative improvement in the inference. The marginals calculated give better approximations to the posterior than loopy propagation on a small toy problem.
BibTeX
@inproceedings{storkey2000dynamic,
  author = {Amos J. Storkey},
  title = {{Dynamic Trees: A Structured Variational Method Giving Efficient Propagation Rules}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2000},
  url = {https://openreview.net/forum?id=S4vo3lrRJa},
}
Figure