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.
Introduction
In Natural Language Processing (NLP), Markov assumptions are ubiquitous. Models like Hidden Markov Models (HMMs) and Probabilistic Context-Free Grammars (PCFGs) assume that the next state or rule expansion depends only on a small, fixed window of preceding context. While this locality makes computation tractable, it fails to capture the long-range dependencies inherent in natural language. Decisions made at the root of a syntactic tree often influence choices deep within its branches.
This paper introduces a generative framework for structured prediction that moves beyond finite context. By utilizing Bayesian non-parametrics, the proposed model conditions every generation decision on its entire vertical history, effectively creating an infinite-order Markov model for both sequences and trees.
Methodology
The Infinite-Order Model
The core innovation lies in how context is defined. For sequences, the context is the entire preceding string. For trees, the context is the "vertical history"—the sequence of ancestor nodes leading back to the root. By treating this vertical path as a string, the authors can apply techniques from infinite-order language modeling to tree structures.
Smoothing with Hierarchical Pitman-Yor Processes (HPYP)
Increasing context depth leads to extreme data sparsity. To estimate probabilities for contexts never seen during training, the model employs a Hierarchical Pitman-Yor Process (HPYP). This provides a recursive smoothing mechanism: if a context of length $n$ is unknown, the model "backs off" to the context of length $n-1$, and so on, down to the base distribution.
The HPYP is particularly suited for language because it naturally models power-law distributions, capturing the "heavy-tailed" nature of linguistic data more accurately than standard Dirichlet processes.
Inference and Prediction
The unbounded state space makes standard dynamic programming (like Viterbi or CYK) inapplicable. The authors propose two main inference strategies:
- A* Search: A top-down heuristic search that uses a standard PCFG to estimate the "cost-to-go," guiding the search through the infinite context space.
- MCMC Sampling: Using Metropolis-Hastings to sample trees from a proposal distribution (a simple PCFG) and re-scoring them with the infinite-context model. Final predictions are made using Minimum Bayes Risk (MBR) decoding.
Empirical Evaluation
The model was tested on syntactic parsing (Penn Treebank) and Part-of-Speech (POS) tagging (English, Danish, and Swedish).
- Syntactic Parsing: The model achieved an F1 score of 76.74 on the Penn Treebank, a significant improvement over the baseline PCFG (58.91). It performed comparably to models using manually tuned, finite vertical contexts, demonstrating its ability to automatically learn the appropriate context depth.
- POS Tagging: The generative model showed strong performance, notably outperforming the discriminative Stanford Tagger on Danish (95.55% vs 93.66% accuracy).
Conclusion
The infinite-context model successfully breaks the "Markov ceiling" by allowing for unbounded vertical history in structured prediction. While computationally more demanding than local models, its ability to capture global dependencies and automatically smooth over sparse data makes it a powerful tool for complex linguistic tasks. Future work aims to incorporate horizontal context and improve the efficiency of the sampling algorithms.
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