Low-Dimensional Discriminative Reranking

2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 699–709, Montr´eal, Canada, June 3-8, 2012. c⃝2012 Association for Computational Linguistics Low-Dimensional Discriminative Reranking Jagadeesh Jagarlamudi Department of Computer Science University of Maryland College Park, MD 20742, USA jags@umiacs.umd.edu Hal Daum´e III Department of Computer Science University of Maryland College Park, MD 20742, USA hal@umiacs.umd.edu Abstract The accuracy of many natural language pro- cessing tasks can be improved by a reranking step, which involves selecting a single output from a list of candidate outputs generated by a baseline system. We propose a novel fam- ily of reranking algorithms based on learning separate low-dimensional embeddings of the task’s input and output spaces. This embed- ding is learned in such a way that prediction becomes a low-dimensional nearest-neighbor search, which can be done computationally ef- ficiently. A key quality of our approach is that feature engineering can be done separately on the input and output spaces; the relationship between inputs and outputs is learned auto- matically. Experiments on part-of-speech tag- ging task in four languages show significant improvements over a baseline decoder and ex- isting reranking approaches. 1 Introduction Mapping inputs to outputs lies at the heart of many Natural Language Processing applications. For ex- ample, given a sentence as input: part-of-speech (POS) tagging involves finding the appropriate POS tag sequence (Thede and Harper, 1999); pars- ing involves finding the appropriate tree structure (Kubler et al., 2009) and statistical machine trans- lation (SMT) involves finding correct target lan- guage translation (Brown et al., 1993). The accuracy achieved on such tasks can often be improved signif- icantly with the help of a discriminative reranking step (Collins and Koo, 2005; Charniak and John- son, 2005; Shen et al., 2004; Watanabe et al., 2007). For the POS tagging, reranking is relative less ex- plored due to the already higher accuracies in En- glish (Collins, 2002), but it is shown to improve ac- curacies in other languages such as Chinese (Huang et al., 2007). In this paper, we propose a novel ap- proach to discriminative reranking and show its ef- fectiveness in POS tagging. Reranking allows us to use arbitrary features defined jointly on input and output spaces that are often difficult to incorporate into the baseline decoder due to the computational tractability issues. The effectiveness of reranking depends on the joint features defined over both input and output spaces. This has led the community to spend substantial efforts in defining joint features for reranking (Fraser et al., 2009; Chiang et al., 2009). Unfortunately, developing joint features over the input and output space can be challenging, espe- cially in problems for which the exact mapping be- tween the input and the output is unclear (for in- stance, in automatic caption generation for images, semantic parsing or non-literal translation). In con- trast to prior work, our approach uses features de- fined separately within the input and output spaces, and learns a mapping function that can map an ob- ject from …

Content truncated to 500 words