Convex Structure Learning in Log-Linear Models: Beyond Pairwise Potentials

Mark Schmidt, Kevin P. MurphyAISTATS 2010 · OpenReview

Abstract

Previous work has examined structure learning in log-linear models with $\ell_1$-regularization, largely focusing on the case of pairwise potentials. In this work we consider the case of models with potentials of arbitrary order, but that satisfy a hierarchical constraint. We enforce the hierarchical constraint using group $\ell_1$-regularization with overlapping groups, and an active set method that enforces hierarchical inclusion allows us to tractably consider the exponential number of higher-order potentials. We use a spectral projected gradient method as a sub-routine for solving the overlapping group $\ell_1$-regularization problem, and make use of a sparse version of Dykstra’s algorithm to compute the projection. Our experiments indicate that this model gives equal or better test set likelihood compared to previous models.

Introduction

In the field of graphical models, structure learning typically focuses on identifying interactions between variables. Historically, researchers have concentrated on pairwise potentials—edges between two nodes—due to their computational tractability. However, pairwise models often fail to capture complex dependencies where three or more variables interact in ways that are not simply the sum of their parts.

The primary obstacle to learning higher-order interactions is the exponential growth of the search space ($2^p$ for $p$ variables). This paper introduces a convex formulation for learning these structures, ensuring global optimality while maintaining computational feasibility through hierarchical constraints and efficient optimization techniques.

Methodology

The authors propose a Hierarchical Log-Linear Model (HLLM) framework that combines several innovative techniques:

  1. Hierarchical Inclusion Restriction: This principle dictates that a high-order interaction (e.g., between variables A, B, and C) is only included if all its subsets (AB, BC, AC) are already present in the model. This significantly prunes the search space.
  2. Overlapping Group $\ell_1$-Regularization: To enforce the hierarchy in a convex manner, a penalty is applied to overlapping groups of parameters. If a "parent" interaction is zeroed out by the penalty, its "children" (higher-order interactions) are also forced to zero.
  3. Active Set Method: Instead of evaluating all $2^p$ possible interactions, the algorithm starts with a simple model and incrementally adds "boundary" groups—higher-order interactions whose subsets are already active—only when they violate optimality conditions.
  4. Optimization via SPG and Dykstra: The resulting non-differentiable problem is solved using a Spectral Projected Gradient (SPG) method. The complex task of projecting onto the intersection of many overlapping constraints is handled by a sparse version of Dykstra’s cyclic projection algorithm.
  5. Pseudo-Likelihood: For large-scale datasets, the authors utilize a pseudo-likelihood approximation to avoid the intractable calculation of the global partition function.

Experimental Evaluation

The HLLM-L1 approach was evaluated against standard $\ell_1$ and $\ell_2$ regularized pairwise and fixed-order "threeway" models across a diverse set of datasets, including image labels (VOC), user ratings (Jokes), gene expression (Yeast), and sensor data (Traffic, AWMA).

Test-set negative log-likelihood across various datasets as a function of the regularization parameter. HLLM-L1 (solid red line) consistently achieves the lowest error across multiple domains.

As illustrated in the results above, HLLM-L1 consistently achieves lower test-set negative log-likelihood (indicating better predictive performance) than competing models. A detailed view of the optimization landscape for a single dataset (below) highlights how the hierarchical model finds a superior global minimum.

Detailed view of test-set negative log-likelihood for a representative dataset, highlighting the performance advantage of the hierarchical L1 model.

The algorithm automatically discovered interactions of significant depth, reaching up to 6-way interactions in the VOC10 image data and 5-way interactions in the Jokes and AWMA datasets.

Key Insights and Conclusion

The success of HLLM-L1 underscores several key points:

  • Hierarchy as a Computational Tool: The hierarchical constraint is not just a statistical preference but a vital filter that makes the exponential search space manageable.
  • The Pairwise Bottleneck: Empirical evidence suggests that the common "pairwise assumption" is often a bottleneck in machine learning performance.
  • Convexity Matters: By providing a convex formulation, the authors ensure that the discovered structure is globally optimal for the given objective, avoiding the local optima issues of greedy search methods.

While the approach is more computationally intensive than training simple pairwise models, it offers a robust path forward for capturing the complex, high-order dependencies inherent in real-world data. Future work may explore accelerated gradient methods and techniques to handle variables with larger state spaces.

Summary updated

Abstract

Previous work has examined structure learning in log-linear models with $\ell_1$-regularization, largely focusing on the case of pairwise potentials. In this work we consider the case of models with potentials of arbitrary order, but that satisfy a hierarchical constraint. We enforce the hierarchical constraint using group $\ell_1$-regularization with overlapping groups, and an active set method that enforces hierarchical inclusion allows us to tractably consider the exponential number of higher-order potentials. We use a spectral projected gradient method as a sub-routine for solving the overlapping group $\ell_1$-regularization problem, and make use of a sparse version of Dykstra’s algorithm to compute the projection. Our experiments indicate that this model gives equal or better test set likelihood compared to previous models.
BibTeX
@inproceedings{schmidt2010convex,
  author = {Mark Schmidt and Kevin P. Murphy},
  title = {{Convex Structure Learning in Log-Linear Models: Beyond Pairwise Potentials}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2010},
  url = {https://openreview.net/forum?id=VRl3OmVFr7},
}
Figure