Learning a Small Mixture of Trees

M. Pawan Kumar, Daphne KollerNeurIPS 2009 · OpenReview

Abstract: The problem of approximating a given probability distribution using a simpler distribution plays an important role in several areas of machine learning, e.g. variational inference and classification. Within this context, we consider the task of learning a mixture of tree distributions. Although mixtures of trees can be learned by minimizing the KL-divergence using an EM algorithm, its success depends heavily on the initialization. We propose an efficient strategy for obtaining a good initial set of trees that attempts to cover the entire observed distribution by minimizing the $\alpha$-divergence with $\alpha = \infty$. We formulate the problem using the fractional covering framework and present a convergent sequential algorithm that only relies on solving a convex program at each iteration. Compared to previous methods, our approach results in a significantly smaller mixture of trees that provides similar or better accuracies. We demonstrate the usefulness of our approach by learning pictorial structures for face recognition.

Introduction

Researchers have developed a new way to learn "mixtures of trees"—probabilistic models that are more flexible than single trees but still computationally efficient. By switching the learning objective from the standard KL-divergence to an "inclusive" $\alpha$-divergence ($\alpha = \infty$), they created an algorithm that covers the entire data distribution with a significantly smaller number of trees, outperforming traditional methods in tasks like face recognition.

The Problem with Standard Mixtures

In machine learning, we often try to approximate complex probability distributions with simpler models. Tree-structured models are highly desirable because they allow for very fast inference, but they are often too simple to capture the nuances of real-world data. Mixtures of trees (combining multiple trees) offer a middle ground: they are more expressive but still manageable.

The standard way to learn these mixtures is using the Expectation-Maximization (EM) algorithm to minimize Kullback-Leibler (KL) divergence. However, this approach has two major flaws:

  1. Mode-seeking behavior: KL-divergence tends to focus only on the most frequent patterns (the "dominant mode") and ignores the rest of the distribution.
  2. Initialization sensitivity: EM is notorious for getting stuck in local optima, meaning the quality of the final model depends entirely on a lucky starting guess.

The authors aim to find a small, diverse set of trees that "covers" the entire observed distribution, providing a robust starting point for learning.

A Fractional Covering Approach

The core innovation is posing the learning task as a fractional covering problem using $\alpha$-divergence where $\alpha = \infty$.

  • $\alpha$-Divergence ($\alpha = \infty$): Unlike KL-divergence (where $\alpha = 1$), setting $\alpha = \infty$ makes the measure "inclusive." It minimizes the maximum ratio between the true distribution and the model's approximation. This forces the model to provide a "floor" of probability over the entire dataset, ensuring no part of the distribution is ignored.
  • Fractional Covering Framework: This mathematical setup is used to find a sparse combination of elements (in this case, trees) that satisfies a set of constraints (covering the data).

Standard fractional covering algorithms often produce "singleton" trees—models that put all their probability on a single data point—which are useless for generalizing to new data. To fix this, the authors introduced a two-step iterative process:

  1. Convex Relaxation: They solve a relaxed version of the problem using a log-barrier method to find a valid (but not yet tree-structured) distribution.
  2. Projection: They project that distribution onto the space of trees using the classic Chow-Liu algorithm.
  3. Sequential Update: Each iteration adds one new tree to the mixture until the potential function is sufficiently minimized.

Key Results and Applications

The authors evaluated their approach on two primary fronts: standard discrete datasets and a complex face recognition task.

UCI Machine Learning Repository

The method was tested on three discrete datasets—Agaricus (mushroom classification), Nursery, and Splice. These serve as benchmarks for testing how well a model handles categorical data.

Performance comparison on UCI datasets

Because the algorithm is designed as a "covering" problem, it naturally finds a very small number of trees that do the job efficiently. On the Agaricus dataset, the proposed method achieved 100% accuracy using only 3–5 trees, whereas previous methods required 12 trees to reach the same result. On the Splice dataset, they outperformed previous methods using only 2 trees.

Face Recognition

The second evaluation used a dataset containing 24,244 faces of 11 characters from the TV show Buffy the Vampire Slayer. This task involved learning "pictorial structures," which represent the spatial relationships between facial features like eyes, nose, and mouth.

Pictorial structures learned for face recognition

In this dataset, the authors' method consistently outperformed KL-divergence-based methods. As they increased the number of trees in the mixture (from 1 to 7), their accuracy improved steadily, while the KL-based method's accuracy plateaued almost immediately.

Key Insights and Limitations

  • Inclusivity Matters: By targeting the "worst-case" mismatch ($\alpha = \infty$), the algorithm naturally seeks out diverse trees. If the current mixture doesn't explain a specific cluster of data, the next tree added will specifically target that cluster.
  • Fixing the "Singleton" Problem: The transition from a pure linear programming approach to a convex relaxation was crucial. It ensured the trees learned were actually useful probabilistic models rather than just "pointers" to specific training examples.
  • Computational Speed: Each iteration of the algorithm took only 5 to 10 minutes, making it a practical choice for real-world datasets.

Future Work: While 10 minutes per iteration is reasonable, the cost of the Hessian matrix inversion in the log-barrier method scales with the number of samples ($O(m^2)$), which might become a bottleneck for extremely large datasets. The authors suggest that the framework could potentially be extended to mixtures of trees in log-probability space, which might offer different inference advantages. Finally, a theoretical connection between their fractional covering approach and Discrete AdaBoost could lead to even more efficient boosting-style algorithms for density estimation in the future.

Summary updated

Abstract

The problem of approximating a given probability distribution using a simpler distribution plays an important role in several areas of machine learning, e.g. variational inference and classification. Within this context, we consider the task of learning a mixture of tree distributions. Although mixtures of trees can be learned by minimizing the KL-divergence using an EM algorithm, its success depends heavily on the initialization. We propose an efficient strategy for obtaining a good initial set of trees that attempts to cover the entire observed distribution by minimizing the $\alpha$-divergence with $\alpha = \infty$. We formulate the problem using the fractional covering framework and present a convergent sequential algorithm that only relies on solving a convex program at each iteration. Compared to previous methods, our approach results in a significantly smaller mixture of trees that provides similar or better accuracies. We demonstrate the usefulness of our approach by learning pictorial structures for face recognition.
BibTeX
@inproceedings{kumar2009learning,
  author = {M. Pawan Kumar and Daphne Koller},
  title = {{Learning a Small Mixture of Trees}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=Sy-Wvv-uZB},
}
Figure