Structured Prediction of Sequences and Trees Using Infinite Contexts

Ehsan Shareghi, Gholamreza Haffari, Trevor Cohn, Ann E. Nicholson

In the world of Natural Language Processing (NLP), we often rely on Markov assumptions—the idea that the next word or tag only depends on a few preceding ones. While computationally convenient, this "locality" is a lie. Language is full of long-range dependencies where a decision made at the root of a sentence tree might fundamentally change a choice made several branches down.

This paper, "Structured Prediction of Sequences and Trees using Infinite Contexts," introduces a way to stop pretending context is finite. By leveraging Bayesian non-parametrics, the authors propose a model that can look back at an unbounded history of decisions to predict the next piece of a linguistic structure.

TL;DR

The authors propose a hierarchical, infinite-order Markov model for sequences and trees that conditions every generation decision on its entire vertical history. By using a hierarchical Pitman-Yor process for smoothing and MCMC for inference, they outperform standard finite-context models in syntactic parsing and part-of-speech tagging.

What Problem Does This Paper Address?

Most structured prediction models (like HMMs or PCFGs) are "local." A Probabilistic Context-Free Grammar (PCFG), for example, decides how to expand a node based solely on that node's label, ignoring how it got there. While "parent annotation" (looking one level up) helps, it quickly leads to data sparsity: the more context you add, the fewer examples you have in your training data to estimate probabilities.

The challenge is twofold:

  1. Model Complexity: How do you represent an "infinite" context without your parameter count exploding?
  2. Inference: Standard dynamic programming (like the CYK algorithm) breaks when the state space depends on an unbounded history.

Methods

The authors bridge the gap between language modeling (where infinite-order models like the "Sequence Memoizer" exist) and structured prediction.

1. The Infinite-Order Model

Instead of a fixed $n$-gram window, the model conditions the probability of a rule $r$ on an unbounded vertical history $u$ (the chain of ancestors leading to the root).

2. Smoothing with Hierarchical Pitman-Yor Processes (HPYP)

To handle the sparsity of long contexts, they use a Hierarchical Pitman-Yor Process. Think of this as a sophisticated, recursive "back-off" strategy. If the model hasn't seen a specific 10-level deep ancestor chain before, it automatically smooths that probability using the 9-level chain, then the 8-level, and so on, down to the empty context. This is organized efficiently in a trie (prefix tree) structure.

3. Inference Algorithms

Since they can't use standard dynamic programming, they propose two alternatives:

  • A* Search: A top-down search that uses a standard PCFG to estimate the "cost-to-go," helping the model navigate the massive search space of possible trees.
  • MCMC Sampling: They use Metropolis-Hastings to sample trees from a proposal distribution (a simple PCFG) and then score them using the infinite-context model. They combine these samples using Minimum Bayes Risk (MBR) decoding to find the most robust structure.

Datasets

The model was evaluated on two core NLP tasks:

  • Syntactic Parsing: Using the Penn Treebank (PTB), focusing on standard splits (Sections 2-21 for training, 23 for testing).
  • Part-of-Speech (POS) Tagging: Using English (PTB), and Danish/Swedish datasets from the NAACL-HLT 2012 Shared Task on Grammar Induction.

Key Insights and Ideas

  • Vertical History is Key: The "aha moment" is that the vertical path to the root in a tree is analogous to the linear history in a sequence. By treating the ancestor chain as a "string" of context, they can apply sequence-based non-parametric smoothing to trees.
  • Power-Law Resilience: The Pitman-Yor process is specifically chosen because it follows a power-law distribution, which matches the "long tail" of natural language much better than standard Dirichlet processes.
  • MCMC > A*: For complex tasks like parsing, MCMC sampling combined with MBR decoding proved more effective than A* search. The sampling approach was better at escaping local optima in the massive search space created by infinite contexts.

Key Results

  • Parsing: The model achieved an F1 score of 76.74 on the Penn Treebank. While not beating the absolute state-of-the-art discriminative parsers (which use many more hand-engineered features), it significantly outperformed the baseline PCFG (58.91) and matched models that use manually tuned finite vertical contexts.
  • POS Tagging: The model consistently improved over the PCFG/HMM baselines. Notably, for Danish, it outperformed the well-known Stanford Tagger (95.55% vs 93.66% token accuracy), which is impressive for a generative model competing against a feature-rich discriminative one.
  • Adaptability: The model "self-corrects"—it uses as much context as the data supports, effectively capturing long-range dependencies without the user having to specify a fixed $n$.

Limitations and Future Work

  • Computational Cost: Inference is significantly slower than standard Markov models. The reliance on MCMC or A* means it isn't yet a "drop-in" replacement for high-speed production systems.
  • Generative Constraints: As a generative model, it's harder to incorporate the arbitrary, overlapping features that discriminative models (like CRFs) handle easily.
  • Future Directions: The authors suggest moving beyond just "vertical" context to include "horizontal" context (neighboring branches) and exploring more efficient sampling methods to speed up the system.

Reference: Shareghi, E., Haffari, G., Cohn, T., & Nicholson, A. (2015). Structured Prediction of Sequences and Trees using Infinite Contexts. arXiv:1503.02417v1 [cs.LG].

Summary updated

Abstract

Linguistic structures exhibit a rich array of global phenomena, however commonly used Markov models are unable to adequately describe these phenomena due to their strong locality assumptions. We propose a novel hierarchical model for structured prediction over sequences and trees which exploits global context by conditioning each generation decision on an unbounded context of prior decisions. This builds on the success of Markov models but without imposing a fixed bound in order to better represent global phenomena. To facilitate learning of this large and unbounded model, we use a hierarchical Pitman-Yor process prior which provides a recursive form of smoothing. We propose prediction algorithms based on A* and Markov Chain Monte Carlo sampling. Empirical results demonstrate the potential of our model compared to baseline finite-context Markov models on part-of-speech tagging and syntactic parsing.
BibTeX
@inproceedings{shareghi2015structured,
  author = {Ehsan Shareghi and Gholamreza Haffari and Trevor Cohn and Ann E. Nicholson},
  title = {{Structured Prediction of Sequences and Trees Using Infinite Contexts}},
  booktitle = {ECML/PKDD},
  year = {2015},
  doi = {10.1007/978-3-319-23525-7\_23},
}

Loading related content...

Figure