Structured Prediction of Sequences and Trees using Infinite Contexts
This addresses the challenge of capturing global dependencies in natural language processing tasks, offering an incremental improvement over existing Markov-based methods.
The paper tackles the problem of modeling global phenomena in linguistic structures by proposing a hierarchical model for structured prediction that uses infinite contexts, overcoming the limitations of Markov models. Empirical results show its potential on part-of-speech tagging and syntactic parsing compared to baseline finite-context models.
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.