Penalized Expectation Propagation for Graphical Models over Strings

Ryan Cotterell, Jason EisnerNAACL 2015 · OpenReview

TL;DR

This paper introduces Penalized Expectation Propagation (PEP), a new inference algorithm for graphical models that handles complex, string-valued variables. PEP uses a structured sparsity penalty to create simpler, faster messages, achieving significant speedups over existing methods in phonological inference tasks with minimal accuracy loss.

What Problem Does This Paper Address?

Graphical models are powerful tools for reasoning about uncertain linguistic structures, but they often struggle with variables that can take on an infinite number of values, such as strings. Standard inference algorithms like Belief Propagation (BP) can become computationally intractable when dealing with these complex, string-valued variables, as the messages passed between variables can grow exponentially large. While Expectation Propagation (EP) offers a way to approximate these messages by projecting them onto a fixed family of functions, it can still be slow if that family is too expressive. This paper tackles the challenge of making inference in graphical models with string-valued variables both accurate and computationally efficient.

Methods

The core contribution is Penalized Expectation Propagation (PEP). PEP builds upon Expectation Propagation (EP), which approximates messages by fitting them to a chosen family of distributions (e.g., n-gram models). The novelty of PEP lies in introducing a structured sparsity penalty to the EP objective. This penalty encourages "simpler" messages, which in this context means messages that can be represented by smaller, more efficient finite-state machines.

Specifically, the authors:

  • Adapt EP for string-valued variables: They show how to represent messages as log-linear models (specifically, variable-order n-gram models) and how to update these models.
  • Introduce a structured sparsity penalty: This penalty is designed to favor messages that use fewer parameters, effectively controlling the complexity of the underlying finite-state machines. The penalty is inspired by regularizers that encourage structured sparsity, but here it's used to improve runtime rather than generalization.
  • Develop optimization techniques: They propose proximal gradient methods and a greedy growing approach to optimize the penalized objective, allowing for efficient computation of the sparse messages.

Datasets

The paper uses surface phonological forms from the CELEX database for their experiments. They analyze data from 3 languages, observing 100 to 500 words per language. This dataset is used to model the discovery of underlying phonological forms for morphemes.

Key Insights and Ideas

  • Sparsity for Speed: The key insight is that for inference, we don't necessarily need the most accurate possible message representation. Instead, a "good enough" representation that is computationally cheaper can lead to significant overall speedups. The structured sparsity penalty directly targets this trade-off.
  • Structured Penalty Matters: The authors emphasize that a structured penalty is important. It's not just about reducing the number of parameters (like a simple L1 penalty), but about favoring simpler structures (e.g., fewer n-grams, or n-grams that build upon existing ones) which translate to more efficient finite-state machines.
  • PEP as a "Goldilocks" Algorithm: The structured sparsity penalty allows PEP to find a "Goldilocks number" of n-grams – enough to approximate the message well, but not so many that it becomes computationally prohibitive.
  • Adaptive Featurization: The penalty naturally leads to an adaptive featurization process, where the complexity of the message representation grows only as much as needed to capture the essential information.

Key Results

  • Substantial Speedup: PEP achieved significant speedups (shown in Figure 3) compared to a strong baseline (adaptive pruning) and other EP variants (unigram, bigram, trigram). For example, PEP was much faster than trigram EP, while being nearly as accurate.
  • Competitive Accuracy: Despite the speed improvements, PEP maintained accuracy comparable to or better than the baseline, and significantly better than simpler EP approximations (unigram/bigram).
  • Trade-off Control: Figure 4 demonstrates that the parameter $\lambda$ effectively controls the trade-off between the number of features (and thus speed) and accuracy. Increasing $\lambda$ reduces the number of features and runtime, with accuracy degrading gracefully.

Limitations and Future Work

  • Parameter Tuning: The authors acknowledge that choosing the penalty parameter $\lambda$ is a hyperparameter that needs tuning.
  • Future Work - Anytime PEP: They propose an extension where $\lambda$ is reduced dynamically during inference. This would create an "anytime algorithm" whose beliefs gradually approach the full BP beliefs, offering a spectrum of accuracy-speed trade-offs.
  • Future Work - Broader Applicability: The authors believe PEP will be broadly useful in NLP for modeling rich phonological, morphological, and orthographic processes, especially for low-resource languages and social media data. They are releasing their code package to facilitate this.

Summary updated

Abstract

We present penalized expectation propagation (PEP), a novel algorithm for approximate inference in graphical models. Expectation propagation is a variant of loopy belief propagation that keeps messages tractable by projecting them back into a given family of functions. Our extension, PEP, uses a structuredsparsity penalty to encourage simple messages, thus balancing speed and accuracy. We specifically show how to instantiate PEP in the case of string-valued random variables, where we adaptively approximate finite-state distributions by variable-order n-gram models. On phonological inference problems, we obtain substantial speedup over previous related algorithms with no significant loss in accuracy.
BibTeX
@inproceedings{cotterell2015penalized,
  author = {Ryan Cotterell and Jason Eisner},
  title = {{Penalized Expectation Propagation for Graphical Models over Strings}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2015},
  url = {https://openreview.net/forum?id=rkZBuX-dZB},
}
Figure