Aligning words using matrix factorisation

Aligning words using matrix factorisation Cyril Goutte, Kenji Yamada and Eric Gaussier Xerox Research Centre Europe 6, chemin de Maupertuis F-38240 Meylan, France Cyril.Goutte,Kenji.Yamada,Eric.Gaussier@xrce.xerox.com Abstract Aligning words from sentences which are mutual translations is an important problem in different set- tings, such as bilingual terminology extraction, Ma- chine Translation, or projection of linguistic fea- tures. Here, we view word alignment as matrix fac- torisation. In order to produce proper alignments, we show that factors must satisfy a number of con- straints such as orthogonality. We then propose an algorithm for orthogonal non-negative matrix fac- torisation, based on a probabilistic model of the alignment data, and apply it to word alignment. This is illustrated on a French-English alignment task from the Hansard. 1 Introduction Aligning words from mutually translated sentences in two different languages is an important and dif- ficult problem. It is important because a word- aligned corpus is typically used as a first step in or- der to identify phrases or templates in phrase-based Machine Translation (Och et al., 1999), (Tillmann and Xia, 2003), (Koehn et al., 2003, sec. 3), or for projecting linguistic annotation across languages (Yarowsky et al., 2001). Obtaining a word-aligned corpus usually involves training a word-based trans- lation models (Brown et al., 1993) in each directions and combining the resulting alignments. Besides processing time, important issues are completeness and propriety of the resulting align- ment, and the ability to reliably identify general N- to-M alignments. In the following section, we in- troduce the problem of aligning words from a cor- pus that is already aligned at the sentence level. We show how this problem may be phrased in terms of matrix factorisation. We then identify a number of constraints on word alignment, show that these constraints entail that word alignment is equivalent to orthogonal non-negative matrix factorisation, and we give a novel algorithm that solves this problem. This is illustrated using data from the shared tasks of the 2003 HLT-NAACL Workshop on Building le droit de permis ne augmente pas the licence fee does not increase Figure 1: 1-1, M-1, 1-N and M-N alignments. and Using Parallel Texts (Mihalcea and Pedersen, 2003). 2 Word alignments We address the following problem: Given a source sentence f = f1 . . . fi . . . fI and a target sentence e = e1 . . . ej . . . eJ, we wish to find words fi and ej on either side which are aligned, ie in mutual corre- spondence. Note that words may be aligned without being directly “dictionary translations”. In order to have proper alignments, we want to enforce the fol- lowing constraints: Coverage: Every word on either side must be aligned to at least one word on the other side (Possibly taking “null” words into account). Transitive closure: If fi is aligned to ej and eℓ, any fk aligned to eℓ must also de aligned to ej. Under these constraints, there are only 4 types of alignments: 1-1, 1-N, M-1 and M-N (fig. …

Content truncated to 500 words