Learning General Latent-Variable Graphical Models with Predictive Belief Propagation

Borui Wang, Geoffrey J. GordonAAAI 2020 · OpenReview

Abstract

Learning general latent-variable probabilistic graphical models is a key theoretical challenge in machine learning and artificial intelligence. All previous methods, including the EM algorithm and the spectral algorithms, face severe limitations that largely restrict their applicability and affect their performance. In order to overcome these limitations, in this paper we introduce a novel formulation of message-passing inference over junction trees named predictive belief propagation, and propose a new learning and inference algorithm for general latent-variable graphical models based on this formulation. Our proposed algorithm reduces the hard parameter learning problem into a sequence of supervised learning problems, and unifies the learning of different kinds of latent graphical models into a single learning framework, which is local-optima-free and statistically consistent. We then give a proof of the correctness of our algorithm and show in experiments on both synthetic and real datasets that our algorithm significantly outperforms both the EM algorithm and the spectral algorithm while also being orders of magnitude faster to compute.

Introduction

Latent-variable probabilistic graphical models (LVGMs) are essential for capturing hidden structures in data, but learning them is notoriously difficult. Traditionally, researchers have relied on two main approaches: Expectation-Maximization (EM) and Spectral Learning. EM is flexible but prone to local optima and slow convergence. Spectral methods avoid local optima but are often restricted to specific structures like trees and struggle with continuous variables. This paper introduces Predictive Belief Propagation (PBP) to bridge this gap, offering a framework that is flexible, theoretically sound, and computationally efficient.

Methodology: Predictive Belief Propagation

The core innovation is Predictive Belief Propagation (PBP). In standard belief propagation, a "message" summarizes the "past" part of a graph to perform inference in the "future." PBP redefines this: a message is a set of predictions about future observable variables given the past.

Conceptual comparison between Predictive Belief Propagation (PBP) and Conventional Belief Propagation. In PBP, messages encode predictions about future observable variables.

The approach involves three key steps:

  1. Junction Tree Conversion: General graphs are converted into junction trees by clustering variables into cliques.
  2. Two-Stage Regression (2SR): Instead of iterative likelihood maximization, the algorithm uses two-stage linear regression to learn "message operators" (tensors). This transforms an unsupervised problem into a supervised one.
  3. Hilbert Space Embeddings: To handle continuous variables, kernel methods embed probability distributions into infinite-dimensional spaces, allowing tensor algebra via the "kernel trick."

By defining messages in terms of observable variables (the "core group"), the algorithm bypasses the need to explicitly learn hidden variable parameters, drawing inspiration from Predictive State Representations (PSRs).

Experimental Evaluation

The authors evaluated PBP on synthetic datasets and the UCI Handwritten Digit Recognition dataset. The synthetic tests measured KL divergence convergence to ground truth, while the digit recognition task compared classification accuracy against EM and spectral baselines.

Key Results

  • Computational Efficiency: PBP demonstrated a significant speed advantage. It was orders of magnitude faster to train than both standard and online EM.
  • Accuracy and Data Efficiency: On the digit recognition task, PBP achieved ~95% accuracy, outperforming spectral (~85%) and EM (~75%) methods. Notably, PBP maintained high performance even with small training datasets.
  • Theoretical Consistency: The authors proved that the PBP estimator is statistically consistent, ensuring convergence to the correct distribution as data increases.
Comparison of training time across different algorithms. PBP is orders of magnitude faster than standard and online EM algorithms as the training data size increases.

Conclusion and Future Work

PBP provides a unified, local-optima-free framework for learning latent graphical models. While highly effective, the complexity of the underlying junction tree algorithm can be a bottleneck for very dense graphs with high treewidth. Future work may explore automated kernel selection for continuous variables and further optimizations for scaling to massive, complex graphs.

Summary updated

Abstract

Learning general latent-variable probabilistic graphical models is a key theoretical challenge in machine learning and artificial intelligence. All previous methods, including the EM algorithm and the spectral algorithms, face severe limitations that largely restrict their applicability and affect their performance. In order to overcome these limitations, in this paper we introduce a novel formulation of message-passing inference over junction trees named predictive belief propagation, and propose a new learning and inference algorithm for general latent-variable graphical models based on this formulation. Our proposed algorithm reduces the hard parameter learning problem into a sequence of supervised learning problems, and unifies the learning of different kinds of latent graphical models into a single learning framework, which is local-optima-free and statistically consistent. We then give a proof of the correctness of our algorithm and show in experiments on both synthetic and real datasets that our algorithm significantly outperforms both the EM algorithm and the spectral algorithm while also being orders of magnitude faster to compute.
BibTeX
@inproceedings{wang2020learning,
  author = {Borui Wang and Geoffrey J. Gordon},
  title = {{Learning General Latent-Variable Graphical Models with Predictive Belief Propagation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=Q8hAhFwwFY},
}
Figure