Discriminative Pruning for Discriminative ITG Alignment

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 316–324, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Discriminative Pruning for Discriminative ITG Alignment Shujie Liu†, Chi-Ho Li‡ and Ming Zhou‡ †School of Computer Science and Technology Harbin Institute of Technology, Harbin, China shujieliu@mtlab.hit.edu.cn ‡Microsoft Research Asia, Beijing, China {chl, mingzhou}@microsoft.com Abstract While Inversion Transduction Grammar (ITG) has regained more and more attention in recent years, it still suffers from the major obstacle of speed. We propose a discriminative ITG prun- ing framework using Minimum Error Rate Training and various features from previous work on ITG alignment. Experiment results show that it is superior to all existing heuristics in ITG pruning. On top of the pruning frame- work, we also propose a discriminative ITG alignment model using hierarchical phrase pairs, which improves both F-score and Bleu score over the baseline alignment system of GIZA++. 1 Introduction Inversion transduction grammar (ITG) (Wu, 1997) is an adaptation of SCFG to bilingual parsing. It does synchronous parsing of two languages with phrasal and word-level alignment as by-product. For this reason ITG has gained more and more attention recently in the word alignment commu- nity (Zhang and Gildea, 2005; Cherry and Lin, 2006; Haghighi et al., 2009). A major obstacle in ITG alignment is speed. The original (unsupervised) ITG algorithm has complexity of O(n6). When extended to super- vised/discriminative framework, ITG runs even more slowly. Therefore all attempts to ITG alignment come with some pruning method. For example, Haghighi et al. (2009) do pruning based on the probabilities of links from a simpler alignment model (viz. HMM); Zhang and Gildea (2005) propose Tic-tac-toe pruning, which is based on the Model 1 probabilities of word pairs inside and outside a pair of spans. As all the principles behind these techniques have certain contribution in making good pruning decision, it is tempting to incorporate all these features in ITG pruning. In this paper, we pro- pose a novel discriminative pruning framework for discriminative ITG. The pruning model uses no more training data than the discriminative ITG parser itself, and it uses a log-linear model to in- tegrate all features that help identify the correct span pair (like Model 1 probability and HMM posterior). On top of the discriminative pruning method, we also propose a discriminative ITG alignment system using hierarchical phrase pairs. In the following, some basic details on the ITG formalism and ITG parsing are first reviewed (Sections 2 and 3), followed by the definition of pruning in ITG (Section 4). The “Discriminative Pruning for Discriminative ITG” model (DPDI) and our discriminative ITG (DITG) parsers will be elaborated in Sections 5 and 6 respectively. The merits of DPDI and DITG are illustrated with the experiments described in Section 7. 2 Basics of ITG The simplest formulation of ITG contains three types of rules: terminal unary rules 𝑋 → 𝑋���/𝑋��� , where 𝑋��� and 𝑋��� represent words (possibly a null word, ε) in the English and foreign language respectively, and …

Content truncated to 500 words