A fast finite-state relaxation method for enforcing global constraints on sequence decoding

Proceedings of the Human Language Technology Conference of the North American Chapter of the ACL, pages 423–430, New York, June 2006. c⃝2006 Association for Computational Linguistics A fast finite-state relaxation method for enforcing global constraints on sequence decoding Roy W. Tromble and Jason Eisner Department of Computer Science and Center for Language and Speech Processing Johns Hopkins University Baltimore, MD 21218 {royt,jason}@cs.jhu.edu Abstract We describe finite-state constraint relaxation, a method for ap- plying global constraints, expressed as automata, to sequence model decoding. We present algorithms for both hard con- straints and binary soft constraints. On the CoNLL-2004 se- mantic role labeling task, we report a speedup of at least 16x over a previous method that used integer linear programming. 1 Introduction Many tasks in natural language processing involve sequence labeling. If one models long-distance or global properties of labeled sequences, it can be- come intractable to find (“decode”) the best labeling of an unlabeled sequence. Nonetheless, such global properties can improve the accuracy of a model, so recent NLP papers have considered practical techniques for decod- ing with them. Such techniques include Gibbs sampling (Finkel et al., 2005), a general-purpose Monte Carlo method, and integer linear program- ming (ILP), (Roth and Yih, 2005), a general-purpose exact framework for NP-complete problems. Under generative models such as hidden Markov models, the probability of a labeled sequence de- pends only on its local properties. The situation improves with discriminatively trained models, such as conditional random fields (Lafferty et al., 2001), which do efficiently allow features that are functions of the entire observation sequence. However, these features can still only look locally at the label se- quence. That is a significant shortcoming, because in many domains, hard or soft global constraints on the label sequence are motivated by common sense: • For named entity recognition, a phrase that appears multiple times should tend to get the same label each time (Finkel et al., 2005). • In bibliography entries (Peng and McCallum, 2004), a given field (author, title, etc.) should be filled by at most one substring of the in- put, and there are strong preferences on the co- occurrence and order of certain fields. • In seminar announcements, a given field (speaker, start time, etc.) should appear with at most one value in each announcement, al- though the field and value may be repeated (Finkel et al., 2005). • For semantic role labeling, each argument should be instantiated only once for a given verb. There are several other constraints that we will describe later (Roth and Yih, 2005). A popular approximate technique is to hypothe- size a list of possible answers by decoding without any global constraints, and then rerank (or prune) this n-best list using the full model with all con- straints. Reranking relies on the local model being “good enough” that the globally best answer appears in its n-best list. Otherwise, reranking can’t find it. In this paper, we propose “constraint relaxation,” a simple exact alternative to reranking. As in rerank- ing, …

Content truncated to 500 words