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:
- Model Complexity: How do you represent an "infinite" context without your parameter count exploding?
- 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