Learning Sparse Markov Network Structure via Ensemble-of-Trees Models

Yuanqing Lin, Shenghuo Zhu, Daniel D. Lee, Ben TaskarAISTATS 2009

Introduction

Learning the structure of Markov Networks—undirected graphical models that represent dependencies between variables—is a fundamental challenge in machine learning. Applications range from genetic regulatory networks to semantic analysis of text. However, the task is computationally intensive due to the intractability of the partition function, a normalization constant required for general graphs. Traditional approaches often rely on oversimplified models, Gaussian assumptions, or local pseudo-likelihood approximations that may fail to capture global network properties.

This paper proposes a "Goldilocks" solution: the Ensemble-of-Trees (ET) model. By representing a complex network as a weighted mixture of all possible spanning trees, the authors provide a framework that is both expressive enough for real-world dependencies and mathematically structured for efficient computation.

Methodology

The core of the proposed approach is the ET model, which defines a probability distribution as a mixture over the set of all spanning trees in a graph.

The Matrix Tree Theorem

A key innovation is the application of the Matrix Tree Theorem. This mathematical result allows the summation over an exponential number of spanning trees to be computed in closed form via the determinant of a matrix. This transformation turns a "super-exponential" problem into a tractable linear algebra operation.

Optimization and Parameterization

The authors simplify the ET model by using "plug-in" estimators for node and edge marginals, focusing optimization solely on the structural parameters ($\beta$). Because the resulting objective function is non-convex, the authors employ Projected Gradient Descent (PGD). To mitigate the risk of local optima, the algorithm is initialized by solving a convex upper-bound relaxation of the problem.

Experimental Evaluation

The ET model was evaluated against state-of-the-art methods using synthetic and real-world datasets:

  • Gaussian Networks: 50-node and 200-node simulations with varying connectivity, including power-law distributions.
  • Binary Networks: Discrete simulations compared against $l_1$-regularized logistic regression ($l_1$ LR).
  • Blog Post Dataset: A network of 1,000 high-ranking words from ~18,000 blog posts to test semantic discovery.

Key Results and Discussion

Accuracy and Data Efficiency

The ET model demonstrates significant advantages in structure recovery, measured by Hamming distance (the number of edge errors). A notable finding is the model's performance in low-sample regimes. In binary network simulations, the ET approach significantly outperformed $l_1$ LR methods when data was scarce.

Comparison of Hamming distance for ET and $l_1$ LR methods in binary networks, demonstrating ET's efficiency in low-sample regimes.

In Gaussian settings, the ET model also showed competitive performance across various graph topologies compared to $l_1$-regularized Gaussian Markov Networks ($l_1$ GMN), often converging to lower error rates more quickly as sample sizes increased.

Comparison of Hamming distance for ET and $l_1$ GMN across various Gaussian network configurations.

Natural Regularization

Unlike methods that require manual tuning of $l_1$-norm penalties ($\lambda$) to achieve sparsity, the ET model is inherently sparse. The mathematical structure of the mixture model naturally penalizes complexity, favoring explanations that use fewer trees. This reduces the need for tedious hyperparameter search.

Semantic Discovery

On real-world blog data, the model successfully identified meaningful semantic clusters. For instance, the word "Apple" was correctly linked to related tech terms ("iPhone", "Mac") and industry peers ("Microsoft"), demonstrating the model's ability to capture relevant dependencies in high-dimensional data.

Conclusion and Future Work

The Ensemble-of-Trees model offers a robust, computationally efficient alternative for learning sparse Markov Network structures. Its primary strengths lie in its natural sparsity and high data efficiency. However, the authors note that the model's preference for simplicity can occasionally lead to over-sparsity in very dense networks. Future research will focus on refining the regularization properties and exploring the theoretical links between ET sparsity patterns and general Markov Network structures.

Summary updated

BibTeX
@article{lin2009learning,
  author = {Yuanqing Lin and Shenghuo Zhu and Daniel D. Lee and Ben Taskar},
  title = {{Learning Sparse Markov Network Structure via Ensemble-of-Trees Models}},
  journal = {AISTATS},
  year = {2009},
}
Figure