Graph Algorithms for Multiparallel Word Alignment

Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 8457–8469 November 7–11, 2021. c⃝2021 Association for Computational Linguistics 8457 Graph Algorithms for Multiparallel Word Alignment Ayyoob Imani∗1, Masoud Jalili Sabet∗1, Lütfi Kerem ¸Senel1, Philipp Dufter1, François Yvon2, Hinrich Schütze1 1Center for Information and Language Processing (CIS), LMU Munich, Germany 2Université Paris-Saclay, CNRS, LISN, France {ayyoob, masoud, lksenel, philipp}@cis.lmu.de, francois.yvon@limsi.fr Abstract With the advent of end-to-end deep learning approaches in machine translation, interest in word alignments initially decreased; however, they have again become a focus of research more recently. Alignments are useful for ty- pological research, transferring formatting like markup to translated texts and can be used in the decoding of machine translation sys- tems. At the same time, massively multilin- gual processing is becoming an important NLP scenario and pretrained language and machine translation models that are truly multilingual are proposed. However, most alignment algo- rithms rely on bitexts only and do not leverage the fact that many parallel corpora are multi- parallel. In this work, we exploit multiparal- lelity of corpora by representing an initial set of bilingual alignments as a graph and then predicting additional edges in the graph. We present two graph algorithms for edge predic- tion: one inspired by recommender systems and one based on network link prediction. Our experimental results show absolute improve- ments of F1 of up to 28% over the baseline bilingual word aligner in different datasets. 1 Introduction Word alignment is a challenging NLP task that plays an essential role in statistical machine trans- lation and is useful for neural machine translation (Alkhouli and Ney, 2017; Alkhouli et al., 2016; Koehn et al., 2003). Other applications of word alignments include bilingual lexicon induction, an- notation projection, and typological analysis (Shi et al., 2021; Rasooli et al., 2018; Müller, 2017; Lewis and Xia, 2008). With the advent of deep learning, interest in word alignment initially de- creased. However, recently a new wave of publica- tions has again drawn attention to the task (Jalili Sa- bet et al., 2020; Dou and Neubig, 2021; Marchisio et al., 2021; Wu and Dredze, 2020). ∗ Equal contribution - random order. Figure 1: Bilingual alignments of a verse in English, German, Spanish, and French. Two of the alignment edges not found by the bilingual method are German “Schritt” to French “pas” and Spanish “largo” to En- glish “thousand miles”. By looking at the structure of the entire graph, one can infer the correctness of these two edges. In this paper we propose MPWA (MultiParal- lel Word Alignment), a framework that employs graph algorithms to exploit the information latent in a multiparallel corpus to achieve better word alignments than aligning pairs of languages in iso- lation. Starting from translations of a sentence in multiple languages in a multiparallel corpus, MPWA generates bilingual word alignments for all language pairs using any available bilingual word aligner. MPWA then improves the quality of word alignments for a target language pair by inspect- ing how they are aligned to …

Content truncated to 500 words