Part-of-Speech Tagging using Virtual Evidence and Negative Training

Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 459–466, Vancouver, October 2005. c⃝2005 Association for Computational Linguistics Part-of-Speech Tagging using Virtual Evidence and Negative Training Sheila M. Reynolds and Jeff A. Bilmes Department of Electrical Engineering University of Washington Seattle, WA 98195-2500 {sheila,bilmes}@ee.washington.edu Abstract We present a part-of-speech tagger which introduces two new concepts: virtual evi- dence in the form of an “observed child” node, and negative training data to learn the conditional probabilities for the ob- served child. Associated with each word is a flexible feature-set which can in- clude binary flags, neighboring words, etc. The conditional probability of Tag given Word + Features is implemented using a factored language-model with back-off to avoid data sparsity problems. This model remains within the framework of Dynamic Bayesian Networks (DBNs) and is conditionally-structured, but resolves the label bias problem inherent in the con- ditional Markov model (CMM). 1 Introduction A common sequence-labeling task in natural lan- guage processing involves assigning a part-of- speech (POS) tag to each word in the input text. Previous authors have used numerous HMM-based models (Banko and Moore, 2004; Collins, 2002; Lee et al., 2000; Thede and Harper, 1999) and other types of networks including maximum entropy models (Ratnaparkhi, 1996), conditional Markov models (Klein and Manning, 2002; McCallum et al., 2000), conditional random fields (CRF) (Laf- ferty et al., 2001), and cyclic dependency networks (Toutanova et al., 2003). All of these models make use of varying amounts of contextual information. In this paper, we present a new model which re- mains within the well understood framework of Dy- namic Bayesian Networks (DBNs), and we show that it produces state-of-the-art results when ap- plied to the POS-tagging task. This new model is conditionally-structured and, through the use of vir- tual evidence (Pearl, 1988; Bilmes, 2004), resolves the explaining-away problems (often described as label or observation bias) inherent in the CMM. This paper is organized as follows. In sec- tion 2 we discuss the differences between a hidden Markov model (HMM) and the corresponding con- ditional Markov model (CMM). In section 3 we de- scribe our observed-child model (OCM), introduc- ing the notion of virtual evidence, and providing an information-theoretic foundation for the use of nega- tive training data. In section 4 we discuss our exper- iments and results, including a comparison of three simple first-order models and state-of-the-art results from our feature-rich second-order OCM. For clarity, the comparisons and derivations in sections 2 and 3 are done for first-order models us- ing a single binary feature. The same ideas are then generalized to a higher order model with more fea- tures (including adjacent words). 2 Generative vs. Conditional Models In this section we discuss the tradeoffs between the generative hidden Markov model (HMM) and the conditional Markov model (CMM). For pedagogical reasons, the figures and equations are for first order models with a single word-feature. The HMM shown in Figure 1 includes a single 459 feature (the binary flag …

Content truncated to 500 words