Sequential Local Learning for Latent Graphical Models

Sejun Park, Eunho Yang, Jinwoo ShinarXiv 2017 · arXiv

Abstract

Learning the parameters of Graphical Models (GMs) with latent variables is a fundamental challenge in machine learning, typically hindered by non-convex optimization landscapes. Traditional approaches like Expectation-Maximization (EM) often converge to local optima, while theoretically grounded spectral methods are frequently restricted to simple tree-like structures. This paper introduces a Sequential Local Learning framework that leverages marginalization and conditioning to decompose complex, loopy graphs into solvable local components. By iteratively recovering latent information, this method extends the reach of provable learning algorithms to broader classes of models, including grid graphs and Convolutional Restricted Boltzmann Machines (CRBMs).

Introduction

Graphical Models provide a robust framework for representing dependencies between variables. However, when some variables are unobserved (latent), parameter estimation becomes significantly more difficult. While latent variables increase model expressivity—as seen in Restricted Boltzmann Machines—they introduce non-convexity into the learning objective.

The standard Expectation-Maximization (EM) algorithm is widely used but lacks global convergence guarantees. Conversely, "method of moments" or spectral methods offer provable recovery but are typically limited to graphs with strict "bottleneck" properties, where a single node or a small set of nodes separates the graph. This paper addresses the gap: how to apply rigorous spectral methods to the loopy, high-degree graphs common in practical applications.

Methodology: Peeling the Onion

The proposed framework, Sequential Local Learning, avoids global non-convexity by solving the graph piece-by-piece. It relies on two primary topological operations: Marginalization and Conditioning.

Marginalization

Marginalization allows the reduction of a large GM into a smaller, more manageable structure. By identifying subsets of variables whose distributions remain invariant under specific transformations, the algorithm can focus on local neighborhoods without losing global consistency.

Figure 5: Marginalization of a subset S from a larger graph G.

As shown in Figure 5, the marginalization process (Marg(S, G)) preserves the essential dependencies within a local region S, allowing for targeted parameter estimation on a reduced node set.

Conditioning and the "Bottleneck" Transformation

The core innovation lies in using conditioning as a structural tool. In many loopy graphs, dependencies are too complex for standard spectral solvers. However, by fixing the values of a few strategically chosen variables (conditioning), one can effectively "cut" edges and break cycles.

Figure 1: Comparison between a simple bottleneck structure (a) and a more complex exclusive view (b).

Figure 1 illustrates this concept. While standard methods might only handle the simple bottleneck in (a), the sequential framework uses conditioning to transform the loopy "exclusive view" in (b) into a series of tractable bottlenecks. Once a local part of the graph is solved, the recovered latent marginals are treated as "observed," unlocking the next layer of the graph in a recursive fashion.

Key Insights

  • Local Solvers for Global Problems: The framework demonstrates that a "black-box" solver (like TensorDecomp) for small, local structures can be orchestrated to solve a large, complex system.
  • Topological Surgery: Conditioning is reframed from a statistical operation to a topological one, surgically altering graph connectivity to ensure tractability.
  • Label Consistency: To ensure that piece-wise learning results in a coherent global model, the authors introduce "Label-Consistency" constraints, preventing the arbitrary swapping of latent state labels across different local solutions.
  • EM Initialization: Even in cases where the full graph cannot be solved provably, the sequential algorithm provides a high-quality initialization for EM, significantly reducing the risk of falling into poor local optima.

Theoretical Results and Complexity

The authors provide formal proofs for the successful recovery of pairwise marginals in several challenging architectures:

  1. Grid Graphs: Where only boundary nodes are visible.
  2. Convolutional RBMs: A staple of deep learning architectures.
  3. Random Regular Graphs: Providing a general result for high-degree structures.

The algorithm maintains polynomial complexity O(|V|^{K+L}), where K and L are small constants representing the number of conditioned variables. While the cost is exponential in K, the authors show that for many practical graphs, K remains small enough for the approach to be efficient.

Conclusion

Sequential Local Learning represents a significant step forward in bridging the gap between theoretically sound spectral methods and the complex graphical models used in practice. By decomposing loopy structures through marginalization and conditioning, the framework provides a path toward provable parameter recovery in models previously considered intractable.

Summary updated

Abstract

Learning parameters of latent graphical models (GM) is inherently much harder than that of no-latent ones since the latent variables make the corresponding log-likelihood non-concave. Nevertheless, expectation-maximization schemes are popularly used in practice, but they are typically stuck in local optima. In the recent years, the method of moments have provided a refreshing angle for resolving the non-convex issue, but it is applicable to a quite limited class of latent GMs. In this paper, we aim for enhancing its power via enlarging such a class of latent GMs. To this end, we introduce two novel concepts, coined marginalization and conditioning, which can reduce the problem of learning a larger GM to that of a smaller one. More importantly, they lead to a sequential learning framework that repeatedly increases the learning portion of given latent GM, and thus covers a significantly broader and more complicated class of loopy latent GMs which include convolutional and random regular models.
BibTeX
@misc{park2017sequential,
  author = {Sejun Park and Eunho Yang and Jinwoo Shin},
  title = {{Sequential Local Learning for Latent Graphical Models}},
  year = {2017},
  eprint = {1703.04082},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1703.04082},
}
Figure