Agreement-Based Learning

Percy Liang, Dan Klein, Michael I. Jordan

Introduction

In fields like natural language processing (NLP) and computational biology, researchers often need to model many dependent variables simultaneously. When these models include "hidden variables"—data we cannot observe directly, such as the syntactic structure of a sentence or missing nucleotides in an ancestral DNA sequence—the underlying mathematics becomes incredibly difficult.

The standard approach is to calculate the "marginal likelihood" by summing over all possible hidden states. However, for complex models, this is often computationally intractable. While researchers have previously tried splitting models into pieces (using methods like pseudolikelihood or piecewise training), those approaches generally only work when all data is observed.

This paper tackles a much harder challenge: how do we train a collection of simple models to work together when the most important information is hidden? The proposed solution is Agreement-Based Learning, a framework for training complex probabilistic models by breaking them into simpler, tractable "submodels" that are encouraged to agree on their hidden variables. This approach avoids the computational nightmare of traditional approximate inference while outperforming independent training on a variety of complex tasks.

Methods: Forcing Submodels to Agree

Agreement-Based Learning shifts the goal from finding one perfect, complex model to training multiple tractable submodels that "agree" on the hidden state.

  • The Objective Function: Instead of maximizing the likelihood of each submodel independently, the authors propose an objective that rewards parameter values where submodels assign high probability to the same hidden state ($z$) given the observed data ($x$).
  • Product EM Algorithm: They derive a variation of the Expectation-Maximization (EM) algorithm. In the "Product E-step," information from all submodels is combined to create a single joint posterior distribution over the hidden variables. In the "M-step," each submodel is updated independently using this shared information.
  • Approximations for Intractability: Because even the "agreement" step can sometimes be computationally heavy, they introduce two specialized approximations:
  • Domain-approximate product EM: Used when the search space for hidden variables is different for each submodel (e.g., asymmetric word alignment).
  • Parameter-approximate product EM: Used when the combined model structure becomes too "loopy" or complex to solve exactly (e.g., phylogenetic Hidden Markov Models).

Datasets and Applications

The authors validated their framework on three distinct real-world problems:

  1. Grammar Induction: Re-interpreting existing work on inducing syntactic structures from text.
  2. Unsupervised Word Alignment: Using the English-French Hansards data (NAACL 2003 Shared Task), consisting of 100,000 unaligned sentences for training and 137 for testing.
  3. Phylogenetic HMMs: Predicting missing nucleotides using a multiple alignment of 20,000 consecutive sites from the CFTR gene across eight eutherian species.
Phylogenetic tree showing observed species and hidden ancestral nodes.

Key Insights

  • Agreement as Regularization: Forcing submodels to agree acts as a powerful constraint. It prevents individual models from "hallucinating" patterns in the hidden data that aren't supported by the other models.
  • Tractability via Decomposition: The core insight is that you do not need to solve a massive, loopy graphical model if you can decompose it into trees or other simple structures that share a hidden state.
  • Dual Representation: By using convex duality, the authors show that the E-step is essentially an optimization over "mean parameters" (expected statistics), which allows for flexible ways to combine submodels, such as averaging their statistics.

Key Results

Word alignment submodels and Alignment Error Rate comparison.
  • Word Alignment: The "domain-approximate" approach successfully combined asymmetric English-to-French and French-to-English models. As shown above, this led to a significant reduction in the Alignment Error Rate (AER) compared to training the models independently.
  • Phylogenetic Modeling: In DNA sequence prediction, the agreement-based approach converged to high accuracy much faster than independent EM. This "convergence gap" became even more pronounced as the amount of missing (held-out) data increased from 20% to 50%.
  • Efficiency: The proposed algorithms allow for joint training using only independent, tractable E-steps, making the framework highly scalable to large datasets.

Limitations and Future Work

The authors acknowledge that their primary objective function is a "lower bound" on a properly normalized product model, and this bound can be loose if the submodels are very uncertain. Furthermore, while the two approximate algorithms (domain- and parameter-approximate) work well in practice, a complete theoretical framework relating them back to the original objective is still lacking. Future work could involve applying this framework to other domains like computer vision or developing more refined variational approximations for the E-step.

Summary updated

Abstract

The learning of probabilistic models with many hidden variables and non- decomposable dependencies is an important and challenging problem. In contrast to traditional approaches based on approximate inference in a single intractable model, our approach is to train a set of tractable submodels by encouraging them to agree on the hidden variables. This allows us to capture non-decomposable aspects of the data while still maintaining tractability. We propose an objective function for our approach, derive EM-style algorithms for parameter estimation, and demonstrate their effectiveness on three challenging real-world learning tasks.
BibTeX
@inproceedings{liang2007agreement,
  author = {Percy Liang and Dan Klein and Michael I. Jordan},
  title = {{Agreement-Based Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2007},
}
Figure