Hidden-Variable Models for Discriminative Reranking

Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 507–514, Vancouver, October 2005. c⃝2005 Association for Computational Linguistics Hidden–Variable Models for Discriminative Reranking Terry Koo MIT CSAIL maestro@mit.edu Michael Collins MIT CSAIL mcollins@csail.mit.edu Abstract We describe a new method for the repre- sentation of NLP structures within rerank- ing approaches. We make use of a condi- tional log–linear model, with hidden vari- ables representing the assignment of lexi- cal items to word clusters or word senses. The model learns to automatically make these assignments based on a discrimina- tive training criterion. Training and de- coding with the model requires summing over an exponential number of hidden– variable assignments: the required sum- mations can be computed efficiently and exactly using dynamic programming. As a case study, we apply the model to parse reranking. The model gives an F– measure improvement of ≈ 1.25% be- yond the base parser, and an ≈ 0.25% improvement beyond the Collins (2000) reranker. Although our experiments are focused on parsing, the techniques de- scribed generalize naturally to NLP struc- tures other than parse trees. 1 Introduction A number of recent approaches in statistical NLP have focused on reranking algorithms. In rerank- ing methods, a baseline model is used to generate a set of candidate output structures for each input in training or test data. A second model, which typi- cally makes use of more complex features than the baseline model, is then used to rerank the candidates proposed by the baseline. Reranking approaches have given improvements in accuracy on a number of NLP problems including parsing (Collins, 2000; Charniak and Johnson, 2005), machine translation (Och and Ney, 2002; Shen et al., 2004), informa- tion extraction (Collins, 2002), and natural language generation (Walker et al., 2001). The success of reranking approaches depends critically on the choice of representation used by the reranking model. Typically, each candidate struc- ture (e.g., each parse tree in the case of parsing) is mapped to a feature–vector representation. Previous work has generally relied on two approaches to rep- resentation: explicitly hand–crafted features (e.g., in Charniak and Johnson (2005)) or features defined through kernels (e.g., see Collins and Duffy (2002)). This paper describes a new method for the rep- resentation of NLP structures within reranking ap- proaches. We build on the intuition that lexical items in natural language often fall into word clusters (for example, president and chairman might belong to the same cluster) or fall into distinct word senses (e.g., bank might have two distinct senses). Our method involves a hidden–variable model, where the hidden variables correspond to an assignment of words to either clusters or word–senses. Lexical items are automatically assigned their hidden values using unsupervised learning within a discriminative reranking approach. We make use of a conditional log–linear model for our task. Formally, hidden variables within the log–linear model consist of global assignments, where a global assignment entails an assignment of every word in the sentence to some hidden cluster or sense …

Content truncated to 500 words