Estimating Dependency Structure as a Hidden Variable

Marina Meila, Michael I. Jordan

Introduction

This paper introduces the mixture of trees model, a powerful probabilistic framework that treats the dependency structure of data as a hidden variable. By combining the computational efficiency of tree-structured graphs with the flexibility of mixture models, the authors provide a method to model complex, dynamically changing relationships in data without the exponential computational costs typically associated with general belief networks.

The Problem: Fixed vs. Conditional Dependencies

In traditional probabilistic modeling (such as standard neural networks or belief networks), the "map" of how variables depend on one another is usually fixed. However, in the real world, dependencies are often conditional. For example, in a medical database, the relationship between a patient's height and weight might be very different if the patient is a professional athlete versus someone with a specific metabolic disease.

While general graphical models can represent these complex relationships, they often suffer from "NP-hard" computational demands when it comes to learning the structure or performing inference. The authors seek a middle ground: a model flexible enough to capture these changing dependencies but simple enough to remain computationally tractable.

Methodology: Mixture of Trees

The authors propose using a Mixture of Trees. A single tree-structured distribution is computationally "cheap"—likelihoods and marginals can be calculated in linear time. By creating a mixture (a weighted sum) of these trees, the model becomes a "universal approximator," capable of representing any distribution if given enough components.

The core contribution is a learning algorithm that combines two well-known techniques:

  1. Expectation-Maximization (EM): Used to handle the "hidden" part of the model. In the E-step, the algorithm estimates which tree component likely generated each data point. In the M-step, it updates the trees.
  2. The Chow-Liu Algorithm: This is the "secret sauce" for the M-step. For each component in the mixture, the algorithm calculates the mutual information between all pairs of variables and uses a Minimum Spanning Tree (MST) algorithm to find the optimal tree structure.

The authors also extend this to Maximum a Posteriori (MAP) estimation by introducing priors. Specifically, they use Minimum Description Length (MDL) priors to penalize overly complex trees, effectively "pruning" edges to favor simpler, disconnected structures (forests) when the data doesn't justify a full tree.

Experiments and Key Results

The model was evaluated on three types of data to test structure recovery, classification, and density estimation.

Structure Recovery

On synthetic data (30,000 datapoints generated from a known mixture of 5 trees over 30 variables), the algorithm correctly recovered the original tree structures in 9 out of 10 trials. The single failure was attributed to a component with a very low mixing weight (only 2% of the data).

Classification

The model was tested on the Australian Credit Dataset (UCI Repository), a real-world classification task involving 690 instances with 14 attributes. The mixture of trees outperformed mixtures of factorial distributions (which assume variables are independent within a component) and achieved results comparable to state-of-the-art decision trees of the era.

Classification accuracy on the Australian Credit dataset

Density Estimation and Compression

The authors used binary vector representations of handwritten digits (64-dimensional for single digits and 128-dimensional for pairs) for density estimation and compression tests. The Mixture of Trees (MT) was the "absolute winner" for compressing single digits, outperforming Helmholtz Machines and other complex models. It ranked second for paired digits, proving its strength as a density estimator.

Compression performance comparison on single and paired digits

Key Insights

  • Structure as a Hidden Variable: The most elegant idea here is treating the topology of the network itself as the latent variable. The model doesn't just learn the weights of a fixed graph; it learns which graph to use for which data point.
  • Efficiency via Trees: By restricting each component to a tree structure, the authors bypass the "exponential explosion" of general belief networks. The M-step remains exact and efficient because of the MST approach.
  • Universal Approximation: A single tree is limited, but a mixture of trees is not. This allows the model to capture non-linear, high-order dependencies by piece-wise linear (tree-like) approximations.
  • Edge Pruning as Regularization: Using MDL priors allows the algorithm to automatically decide if a variable is irrelevant for a specific component by simply not drawing an edge to it.

Limitations and Future Work

  • Local Optima: Like all EM-based approaches, the algorithm is sensitive to initialization and can get stuck in local optima.
  • Independence in Pairs: While the model was great at compressing digits, the authors noted it struggled to "discover" the fundamental independence between two randomly paired digit images, treating them as a single complex density instead.
  • Scalability to High Dimensions: While quadratic in the number of variables, the cost of computing all-pairs mutual information could become a bottleneck for extremely high-dimensional datasets (e.g., thousands of variables) without further optimization.

Summary updated

Abstract

This paper introduces a probability model, the mixture of trees that can account for sparse, dynamically changing dependence relationships. We present a family of efficient algorithms that use EM and the Minimum Spanning Tree algorithm to find the ML and MAP mixture of trees for a variety of priors, including the Dirichlet and the MDL priors.
BibTeX
@inproceedings{meila1997estimating,
  author = {Marina Meila and Michael I. Jordan},
  title = {{Estimating Dependency Structure as a Hidden Variable}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1997},
}
Figure