In this introductory lecture we will discuss the role of machine translation in society, the nature of translation data, and we will also present an overview of the history of MT.

• For you to get a sense of the task, learn more about key concepts such as words, sentence, parallel corpora (the most important translation data), read chapters 1-2 of Koehn’s 2010 book.

In this session we will discuss the IBM word alignment models 1 and 2. We will view them as constrained mixture models. After motivating the models intuitively, we will develop them formally and devise an EM parameter estimation algorithm for them. We will also try to understand why the resulting optimisation problem contains multiple optima.

• Philip Schulz has made available a nice tutorial which is the basis for his lecture.

• In order to get a more concrete view of implementation, including pseudo-codes for the EM procedure, read M. Collins’s lecture notes.

• R. Moore (2004) discusses a number of problems with IBM model 1 involving 1) null words, 2) rare words, and 3) initialisation for EM. If you can understand the problems he raises and the solutions he proposes, you are really getting it about IBM1. Also, implementing some of his improvements will be worth some extra points in project 1.

• Toutanova et al. (2011) discuss the non-strict convexity of IBM1. This is related to the non-identifiability problem discussed in class.

• The original IBM paper is very dense, but if you want to go around teaching IBM models you should probably read it a few times.

• Vogel et al. 1996 revisit the assumption that alignments links are independent.

• Dyer et al. 2013 revisit the parameterisation of IBM model 2. Their model, called ‘fast_align’ achieves state-of-the-art performance and a robust and efficient implementation is available.

In this lecture we will review PCFG parsing as weighted deduction. We will then extend the idea to parsing with synchronous grammars. This lecture can be seen as background for parameter estimation and decoding/generation with CFG-structured models.

• I will discuss bitext parsing using deductive systems, if you are not familiar with that you might want to read a good tutorial.

• David Chiang has a nice tutorial on synchronous grammar. I will not stick too much to it though.

• Dyer (2010) shows that a cascade of monolingual parsers is a very neat and general way to perform bitext parsing.

• Laura Kallmeyer’s book (i.e. Parsing Beyond Context-Free Grammars) is a really good reference. Particularly, Chapter 3 on parsing as deduction.

In this lecture we will introduce phrase-based models. We will motivate the need for larger translation units than word pairs, and show how their modelling introduces a new issue: phrase segmentation. We will see how standard phrase-based SMT deals with this issue, and present estimation and inference under this model.

• Koehn et al. 2003. Statistial Phrase-Based Translation

• Kumar and Byrne (2003) present a derivation and implementation of the alignment template model using FSTs.

• On estimation:

• Marcu and Wong (2002) proposed a model that is conceptually very similar to the IBM models 1 and 2, but applied to phrases instead of words. Estimation in that model is intractable, requiring initial approximations and hard EM.

• DeNero et al. (2006) inferred phrase translation estimates in a (uniform) segmentation space constrained by word alignments trained with the IBM models. This leads to degenerate estimates.

• Mylonakis and Sima’an (2008) used word alignments and the phrase-extraction method of Koehn et al. (2003), but infer phrase-translation estimates with EM. They restrict the segmentation space to ITG derivations, and use cross-validation techniques to avoid overfitting.

• DeNero and Klein (2008) showed that estimation for phrase-based models is NP-complete.

• On inference:

• Sima’an (2002) proved that disambiguation of formal grammars (Stochastic Context-Free and Tree-Substitution Grammars) is NP-complete. The result carries over to any problem where one needs to sum over derivations (or segmentations in the case of this lecture).

• Knight (1999) proved that decoding (for word-based models) is NP-complete, and laid out the analogy between decoding and the Travelling Salesman Problem (TSP).

• Zaslavskiy et al. (2009) proposed to apply TSP solvers for decoding instead of beam-search decoding.

• Aziz et al. (2014) replace beam-search decoding by an exact coarse-to-fine search inspired by rejection sampling.

In this lecture we will present alignments models that impose explicit reordering constraints through a grammar. We will cover bitext parsing, inference and parameter estimation.

• ITG is a form of context-free transducer. Thus the more you know about context-free grammars (CFGs) and their probabilistic extensions (PCFGs), the better. You can start with M Collins’s lecture notes on PCFGs. In estimating parameters for a PCFG with EM we need expectations (as always), there is an efficient algorithm to compute those from parse forests. Again, M Collins’s has nice lecture notes on this algorithm (the Inside-Outside algorithm) as well as EM for PCFGs.

• Wu (1997) is the best introduction to ITG in the literature.

• IBM alignment models fit within a larger translation component inspired by the noisy channel approach from information theory. ITGs can also play that role, see Wu and Wong (1998).

• ITGs have a very generic vocabulary of nonterminals leading to very flat distributions. One can use the idea of state splitting to refine the vocabulary of a vanilla ITG. This is very difficul to do in terms of MLE. Blunsom et al. (2008) develop a non-parametric Bayesian model which learns how far to refine the vocabulary of a vanilla ITG. Blunsom and Cohn (2010) build on that work and propose a more efficient inference technique based on slice sampling.

• You probably want to wait until after the lecture on ‘Phrase-based models’ before you read the following papers.

• Phrase-based ITGs have never shown state-of-the-art performance because of its degenerate maximum likelihood estimates. Mylonakis and Sima’an (2010) propose a better estimation procedure.

• Neubig et al. (2011) apply non-parametric Bayesian methods to avoid degenerate maximum likelihood estimates for phrase-based ITGs.

• ITGs impose hard constraints on reordering, yet these constraints are not as unmotivated as an ad-hoc distortion limit. Zens et al. (2004) investigate the effectiveness of ITG-style constraints in a phrase-based decoder. They also compare it to IBM-style constraints (namely, distortion limit).

In this lecture we will generalise the phrase-based approach to include phrases with gaps.

• David Chiang. An introduction to synchronous grammars

• Chiang. 2007. Hierarchical Phrase-Based Translation

• Chiang. 2005. A Hierarchical Phrase-Based Model for Statistical Machine Translation

In this lecture we will talk about automatic evaluation. Evaluation in Machine Translation is dealing with automatic assesment of the translation quality. Unlike many machine learning tasks, here there is no unique gold truth to which we can compare the translation – there are many equally good translations. Also translations can be good or bad in many dimensions: morphology, syntax or semantics. Evaluation is important not only for assesing the quality of the final system but also for automatic tuning of the systems.

• A good survey of evaluation methods can be found in Chapter 8 of Koehn’s book. You can also refer to statmt’s survey page

• BLEU is the most widely used automatic evaluation metric, it is mostly a precision metric.

• BEER is a trainable metric meant for approximating human ranking of translations.

• METEOR tries to balance precision and recall.

• Read (Lopez, 2012) for a formal view of evaluation of automatic evaluation metrics (you read it right!).

• Hypothesis testing for SMT or whether two systems differ.

We will cover few algorithms that allow us to fine tune many parameters that our MT system can have (weights for language model, translation model, word penalty…).

• A survey of optimisation techniques for machine translation.

• MERT is nicely explained in Koehn’s book (Chapter 9.3.2: Powell search algorithm)

• MT tuning can be seen as a learning to rank task. In learning to rank, a typical approach is to approximate a complex ranking task by a series of pairwise ranking decision. This idea has been popularised in MT by the algorithm PRO.

• For a nice overview of large margin discriminative learning in MT refer to (Eidelman, 2012)

• For MIRA with batched updates in MT refer to (Cherry and Forster, 2012)

In this lecture we will talk about translation using FSTs, hypergraphs, translation as deduction, discuss decision rules, integration of nonlocal features (as weighted CFG-FSA intersection), and finally beam search and cube pruning.

• Part 1: FST decoding and decision rules

• Part 2: SCFG decoding and cube pruning

• Mohri (2009) surveys weighted automata algorithms.

• Lopez (2009) formalises translation as weighted deduction.

• Chiang (2007) introduces cube pruning.

• Huang and Chiang (2007) introduce algorithms for approximate forest rescoring (i.e. cube pruning and cube growing).

• Watanabe et al. (2006) introduce an interesting left-to-right hierarchical decoder based on a synchronous grammar constrained to a GNF target side (a regular grammar on the target side).

In this lecture we will talk about preordering, factorization of permutations and reordering grammar.

• Stanojevic ́ and Sima’an. 2015. Reordering Grammar Induction

• Tromble and Eisner. 2009. Learning Linear Ordering Problems for Better Translation

In this session we will see how labels can be added too Hiero to improve word order and lexical choice. We will motivate why to label Hiero grammars, and discuss what types of label have been considered in the literature.

As a first example we will look at a well known labeling approach for the target side known as syntax-augmented machine translation (SAMT). SAMT uses syntactic information from the target side.

We will then discuss how labeling can be done using only the information about hierarchical translation equivalence relations induced by word alignments. This information describes the type of reordering taking place within translation rules more directly than syntax.

The lecture will be ended with a discussion of applying labels as soft constraints (fuzzy matching) in labeling approaches, and why this is important for success.

Summary In this session students will get a better understanding of:

1. What rule nonterminal labeling is and why it is done
2. What types of labels can be constructed, using syntax, dependency and other information or just the information present in word alignments.
3. What the important differences are between source and target side labeling, both in motivation as well as in technical consequences for implementation and effects on sparsity etc.
4. What soft matching approaches for labeling are and why they are important.

• Zollmann and Venugopal. 2006. Syntax Augmented Machine Translation via Chart Parsing

• Wenniger and Sima’an. 2014. Bilingual Markov Reordering Labels for Hierarchical SMT

• Mylonakis and Sima’an (2010) describe how distributions over labels similar to SAMT labels can be learned from data using a variant of the EM algorithm known as cross-validating EM. This paper uses a combination of a labeled version of ITG in combination with phrase pairs. Labels are applied on the source side, similar to the way this is done in ``Using Syntactic Head Information in Hierarchical Phrase-Based Translation’’ but with two main differences: 1. The label distributions are learned rather than heuristically estimated. 2. The label matching constraint is enforced exactly inside the (adapted) decoder, instead of approximately by using grammar filtering.

• Chiang (2010) explains how source and target syntax can be effectively combined for improved translation. The key to the success of the proposed approach is matching the labels in a soft rather than strict way, using dedicated features that indicate substitution of label X to label Y. Another interesting thing is that there is only one labeled rule version per Hiero rule, so that the size of the grammar remains equal to unlabeled Hiero. This is significant, because for SAMT in contrast, labeling introduces many alternatively labeled variants of the same Hiero, increasing the size of the grammar drastically. Finally the paper introduces an interesting scheme to further reduce the size of the grammar, and increase decoding speed, without hampering performance.

• Li et al. (2012) describe how dependency parse information can be exploited to construct effective source labels for Hiero rules. Source labeling has a different motivation than target labeling. Target labels can be thought of as working mainly as a kind of language models. Source labels in contrast typically are used to provide a stronger context for the application of rules, by enforcing that only rules matching the source parse chart information (in this case dependency parse information) can be used by the decoder. In this paper the latter is effectively only approximated, by filtering the grammar to contain rules with right-hand-sides matching labels for any of the source side labels of sentences in the development or testing set. Note that a more precise implementation involves adapting the decoder to include a source label chart along with the input and enforce the matching with this label chart inside the decoder.

In this lecture we will discover that not all language pairs are created equal. We will discuss some problems that morphologically rich languages pose and how they are approached in machine translation.

• Soricut and Och. 2015. Unsupervised Morphology Induction Using Word Embeddings

• Sennrich and Haddow. 2015. A Joint Dependency Model of Morphological and Syntactic Structure for Statistical Machine Translation.

• Compounds have long been a problem for word- and phrase-level machine translation. Soricut and Och’s method for morphology can be extended to split compounds into their meaningful parts.

• Daiber et al. 2015. Splitting Compounds by Semantic Analogy

• Koehn and Hoang. 2007. Factored Translation Models

• Williams and Koehn. 2011. Agreement Constraints for Statistical Machine Translation into German

In the last couple of years, deep learning has proven useful in many areas. Also for machine translation, models have been proposed, in some cases reaching state-of-the-art performance. In this lecture we will look at the (now classic) encoder-decoder framework, as well as more recent models.

• Sutskever et al. 2014. Sequence to Sequence Learning with Neural Networks

• Cho et al. 2014. Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation

• One problem with the models of the background literature is that they use a single vector to represent the source sentence. Attention models address this limitation.

• Jean et al. 2015. On Using Very Large Target Vocabulary for Neural Machine Translation

• Chung et al. 2016. A Character-level Decoder without Explicit Segmentation for Neural Machine Translation

• Luong et al. 2015. Effective Approaches to Attention-based Neural Machine Translation

In this lecture we will discuss approaches to translating sentences that occur alongside images. In this context, the images can be seen as a common grounding for both languages, potentially easing the translation task.

• It will be useful to attend the Neural models for translation lecture.

• Neural sequence models for multimodal machine translation: Elliott et al. (2015)

• Multimodal target-side re-ranking Hitschler et al. (2016)

• Are You Talking to a Machine? Dataset and Methods for Multilingual Image Question Answering

In this lecture we will look at using parallel and multiply-aligned text for non-machine translation tasks, such as part-of-speech tagging and parsing. The motivation behind this line of work is the idea that good models (parsers, taggers) for high-resource languages can be transfered to low-resource languages, which do not have sufficient (annotated) data to train good models on their own. Secondly, in an unsupervised setting, multilingual data can provide cues that disambiguate across languages.

• Snyder et al. 2008Unsupervised POS tagging over two languages at once is easier/better than monolingual models.

• McDonald et al. 2011. How to apply a trained parser from language A to language B

• ‘Universal’ (at least standardised) annotation guidelines and treebanks for multiple languages.

• Non-parametric follow-up to (Snyder et al., 2008)

• Follow-up to (McDonald et al, 2011).

• Quasi-synchronous grammars for annotation projection: foundation, parser adaptation

On multilingual representations in neural models

• Hermann and Blunsom. 2014. Multilingual Models for Compositional Distributed Semantics

• Ammar et al. 2016. Massively Multilingual Word Embeddings