Probabilistic Word Alignment under the L0-norm

Proceedings of the Fifteenth Conference on Computational Natural Language Learning, pages 172–180, Portland, Oregon, USA, 23–24 June 2011. c⃝2011 Association for Computational Linguistics Probabilistic Word Alignment under the L0-norm Thomas Schoenemann Center for Mathematical Sciences Lund University, Sweden Abstract This paper makes two contributions to the area of single-word based word alignment for bilingual sentence pairs. Firstly, it integrates the – seemingly rather different – works of (Bodrumlu et al., 2009) and the standard prob- abilistic ones into a single framework. Secondly, we present two algorithms to opti- mize the arising task. The first is an iterative scheme similar to Viterbi training, able to han- dle large tasks. The second is based on the in- exact solution of an integer program. While it can handle only small corpora, it allows more insight into the quality of the model and the performance of the iterative scheme. Finally, we present an alternative way to handle prior dictionary knowledge and dis- cuss connections to computing IBM-3 Viterbi alignments. 1 Introduction The training of single word based translation mod- els (Brown et al., 1993b; Vogel et al., 1996) is an es- sential building block for most state-of-the-art trans- lation systems. Indeed, even more refined transla- tion models (Wang and Waibel, 1998; Sumita et al., 2004; Deng and Byrne, 2005; Fraser and Marcu, 2007a) are initialized by the parameters of single word based ones. The exception is here the joint approach of Marcu and Wong (2002), but its refine- ment by Birch et al. (2006) again relies on the well- known IBM models. Traditionally (Brown et al., 1993b; Al-Onaizan et al., 1999) single word based models are trained by the EM-algorithm, which has the advantageous property that the collection of counts can be de- composed over the sentences. Refinements that also allow symmetrized models are based on bipartite graph matching (Matusov et al., 2004; Taskar et al., 2005) or quadratic assignment problems (Lacoste- Julien et al., 2006). Recently, Bodrumlu et al. (2009) proposed the first method that treats a non- decomposable problem by handling all sentence pairs at once and via integer linear programming. Their (non-probabilistic) approach finds dictionaries with a minimal number of entries. However, the ap- proach does not include a position model. In this work we combine the two strategies into a single framework. That is, the dictionary sparsity objective of Bodrumlu et al. will become a regu- larity term in our framework. It is combined with the maximal alignment probability of every sentence pair, where we consider the models IBM-1, IBM-2 and HMM. This allows us to write dictionary spar- sity as the (non-convex) L0 norm of the dictionary parameters of the respective models. For supervised training, regularity terms are quite common, e.g. (Taskar et al., 2005; Lacoste-Julien et al., 2006). For the unsupervised problem addressed in this paper they have recently been introduced in the form of posterior constraints (Ganchev et al., 2010). In related fields of NLP lately Dirichlet pri- ors have been investigated, e.g. (Johnson, 2007). We present …

Content truncated to 500 words