Jakob Verbeek

Keywords:

First, and foremost, I would like to

Neural Machine Translation (NMT) relies on training deep neural networks with large number of parameters on vast amounts of parallel data to learn how to translate from one language to another. One crucial factor to the success of NMT is the design of new powerful and efficient architectures. State-of-the-art systems are encoder-decoder models that first encode a source sequence into a set of feature vectors and then decode the target sequence conditioning on the source features. In this thesis we question the encoder-decoder paradigm and advocate for an intertwined encoding of the source and target so that the two sequences interact at increasing levels of abstraction. For this purpose, we introduce Pervasive Attention, a model based on two-dimensional convolutions that jointly encode the source and target sequences with interactions that are pervasive throughout the network. To improve the efficiency of NMT systems, we explore online machine translation where the source is read incrementally and the decoder is fed partial contexts so that the model can alternate between reading and writing.

We investigate deterministic agents that guide the read/write alternation through a rigid decoding path, and introduce new dynamic agents to estimate a decoding path for each sample.

We also address the resource-efficiency of encoder-decoder models and posit that going deeper in a neural network is not required for all instances. We design depth-adaptive Transformer decoders that allow for anytime prediction and sample-adaptive halting mechanisms to favor low cost predictions for low complexity instances and save deeper predictions for complex scenarios.

Résumé

Une Alternative aux Modèles Neuronaux Séquence-à-Séquence Pour la Traduction Automatique L'apprentissage profond a permis des avancées significatives dans le domaine de la traduction automatique. La traduction automatique neuronale (NMT) s'appuie sur l'entrainement de réseaux de neurones avec un grand nombre de paramètres sur une grand quantité de données parallèles pour apprendre à traduire d'une langue à une autre. Un facteur primordial dans le succès des systèmes NMT est la capacité de concevoir des architectures puissantes et efficaces. Les systèmes de pointe sont des modèles encodeur-décodeurs qui, d'abord, encodent une séquence source sous forme de vecteurs de caractéristiques, puis décodent de façon conditionne la séquence cible. Dans cette thèse, nous remettons en question le paradigme encodeur-décodeur et préconisons de conjointement encoder la source et la cible afin que les deux séquences interagissent à des niveaux d'abstraction croissants. À cette fin, nous introduisons Pervasive Attention, un modèle basé sur des convolutions bidimensionnelles qui encodent conjointement les séquences source et cible avec des interactions qui sont omniprésentes dans le réseau neuronal. Pour améliorer l'efficacité des systèmes NMT, nous étudions la traduction automatique simultanée où la source est lue de manière incrémentielle et le décodeur est alimenté en contextes partiels afin que le modèle puisse alterner entre lecture et écriture. Nous améliorons les agents déterministes qui guident l'alternance lecture / écriture à travers un chemin de décodage rigide et introduisons de nouveaux agents dynamiques pour estimer un chemin de décodage adapté au cas-par-cas. Nous abordons également l'efficacité computationnelle des modèles NMT et affirmons qu'ajouter plus de couches à un réseau de neurones n'est pas requis pour tous les cas. Nous concevons des décodeurs Transformer qui peuvent émettre des prédictions à tout moment dotés de mécanismes d'arrêt adaptatifs pour allouer des ressources en fonction de la complexité de l'instance. The i-th element of x

x i:j A slice of x starting from i and ending with j (i and j included)

x ≤i First i tokens of x x

The ceiling of x (the least integer greater than or equal to x)

x

The floor of x (greatest integer less than or equal to x) p

The probability distribution of a random variable

x ∼ p Sampling from the distribution p ∇ θ x Gradient of x w.r.t. θ

[[x = y]]

Iverson bracket; 1 if the proposition x = y is true, 0 otherwise

U(A)
The uniform distribution over the set A Chapter 1 Introduction

Context and Motivation

There are about 7000 human languages spoken worldwide (Eberhard et al., 2020), being able to communicate flawlessly between all of them is an age-old dream of mankind. In science fiction works, this dream is often materialized with the universal translator. Some variants of this device are described as telepathically reading the brain patterns of the speaker to instantly translate any alien language. Other, more plausible, collect monolingual databases to decipher new languages.

To realize this dream of seamless translation, the research field of Machine Translation (MT) aims to teach machines how to automatically translate across languages. Although the recent success of Machine translation is founded on modern computing capabilities, the field's foundations date back to the late 1940s. Inspired by the success of cryptography and recent advances in information theory [START_REF] Shannon | A Mathematical Theory of Communication[END_REF], Warren Weaver in his memorandum [START_REF] Weaver | [END_REF] made the famous claim -When I look at an article in Russian, I say, "This is really written in English, but it has been coded in some strange symbols. I will now proceed to decode." -His memorandum was one of the first publications to instigate research in mechanical translation suggesting that methods from cryptography might be useful for translation.

During the first decade of MT research, three basic approaches to MT were discussed: direct, transfer and interlingual [START_REF] Hutchins | Machine Translation: A Concise History[END_REF]. Direct translation models [START_REF] Reifler | Mechanical Translation with a Pre-editor and Writing for Mechanical Translation[END_REF][START_REF] Anthony | A Study for the Design of an Automatic Dictionary[END_REF][START_REF] Dostert | The Georgetown-IBM Experiment[END_REF] [START_REF] Vauquois | Syntaxe et Interprétation[END_REF] equivalents of source words and translation was mostly a one-to-one mapping maintaining the order of the source utterance. However, language must be considered as a system of words or particles influencing one another, to this end, indirect approaches were developed, namely, transfer and interlingual. Transfer MT models (Boitet and Nedobejkine, 1980;[START_REF] Winfield | The LRC Machine Translation System[END_REF] translate in three stages: analysis, transfer and generation. For transfer a set of linguistic rules is built to cast a wide net for the complexities of language. The other indirect method is interlingual. Interlingual MT models are based on language-neutral representations that abstracts away from the characteristics of the language itself to focus on semantics. The translation process uses an interlingua as a pivot by encoding the source into interlingua then decoding the target. These different methodologies can be illustrated with the Vauquois triangle in Figure 1.1 where they only differ in the depth of analysis and abstraction of the language. Although the intuition behind interlingua has its roots in the 1950s [START_REF] Weaver | [END_REF], research into interlingua systems was less popular and fell short of the language-neutral ideal.

Up until the late 1980s, MT systems were mostly transfer rule-based. These systems in their attempt to cover all the exceptions of language became cumbersome and exacting to the point of contradiction. With the development of computational resources new statistical datadriven approaches for MT emerged. Statistical MT (SMT) systems learn their parameters 1.1. CONTEXT AND MOTIVATION 3 from translation frequencies in parallel corpora and model the translation task as a search for the most probable translation of a given utterance. With x the source utterance and y a candidate translation, the goal is to find ŷ = arg max y p(y | x).

SMT systems [START_REF] Brown | A Statistical Approach to Language Translation[END_REF][START_REF] Peter | The Mathematics of Statistical Machine Translation: Parameter Estimation[END_REF] are based on the Bayesian noisy channel model [START_REF] Shannon | A Mathematical Theory of Communication[END_REF] where Bayes rule is used to transform the problem of maximizing p(y | x) into maximizing p(x | y)p(y). Therefore, the SMT system maximizes p(x | y) with a translation model and p(y) with a language model. Simplifying assumptions are made to learn each model; the language model is a Markov chain of order n and the translation model assumes the words to be independent from one another.

State-of-the-art SMT systems up to the surge of neural-based MT were phrase-based [START_REF] Franz | Improved Alignment Models for Statistical Machine Translation[END_REF][START_REF] Koehn | Statistical Phrase-Based Translation[END_REF] i.e. they alleviate the strong assumption of independence in the translation model and estimate probabilities over phrases. To improve their translation quality, SMT systems used log-linear models with log p(x | y) and log p(y) as features. This means optimizing the scaled features in the log-space λ 1 log p(x | y) + λ 2 log p(y) [START_REF] Franz | Discriminative Training and Maximum Entropy Models for Statistical Machine Translation[END_REF]. Log-linear models allowed for the inclusion of other features, all weighted with optimal weights λ i [START_REF] Franz | A Smorgasbord of Features for Statistical Machine Translation[END_REF]). However, with many components, optimizing the SMT systems became more difficult. In fact, each component must be optimized separately before combining all of them together.

Neural Machine Translation (NMT) is a relatively new approach that addresses the limits of SMT. The use of neural networks for MT was suggested decades ago [START_REF] Robert B Allen | Several Studies on Natural Language and Back-Propagation[END_REF][START_REF] Jordan | Recursive Distributed Representations[END_REF][START_REF] Chrisman | Learning Recursive Distributed Representations for Holistic Computation[END_REF][START_REF] Mikel | Recursive Hetero-Associative Memories for Translation[END_REF][START_REF] Castano | A Connectionist Approach to Machine Translation[END_REF], but it was not until the increase of computing power that NMT proved its potential [START_REF] Kalchbrenner | Recurrent Continuous Translation Models[END_REF]. Similar to SMT, NMT is also data-driven, however, instead of having disjoint building blocks, NMT has a single map modeled as a neural network responsible for the entire translation process.

SMT and NMT systems can be viewed as an extension of transfer-based MT systems of the 1980s with transfer rules that are not explicitly enumerated but inferred from monolingual and parallel data. Where SMT systems have different components for different types of semantic and syntactic transfer rules, NMT goes a step further and abstracts away from humanly interpretable rules by embedding language in high-dimensional vector spaces that

CHAPTER 1. INTRODUCTION Source x 1 x 2 x 3 x 4 x 1 x 2 x 3 x 4 x 1 x 2 x 3 x 4 x 1 x 2 x 3 x 4
Target are potentially language-independent [START_REF] Johnson | Google's Multilingual Neural Machine Translation System: Enabling Zero-Shot Translation[END_REF].

y
In state-of-the-art NMT systems [START_REF] Cho | Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation[END_REF][START_REF] Sutskever | Sequence to Sequence Learning with Neural Networks[END_REF][START_REF] Bahdanau | Neural Machine Translation by Jointly Learning to Align and Translate[END_REF][START_REF] Gage | Convolutional Sequence to Sequence Learning[END_REF][START_REF] Vaswani | Attention Is All You Need[END_REF] the analysis step of the Vauquois triangle (see Figure 1.1) is modeled with an encoder model and the generation with a decoder model.

In this thesis, we aim to re-assess the two-steps encoder-decoder NMT paradigm. Our view of NMT models, illustrated in Figure 1.2, put emphasis on the interaction between the source and target sequences at increasing levels of abstraction where the two sequences are jointly encoded in interwoven computational graphs. We consider the challenging task of online or simultaneous machine translation as a particular case of MT that requires an efficiently designed and controlled interaction between the source and the target sequences. We also endeavor in choosing the right level of abstraction for generation (the blue arrows in Figure 1.2) that will optimize a trade-off between the translation's quality and its computational cost.

Contributions

This thesis studies the problem of modeling neural machine translation systems and proposes alternative computational graphs to improve:

(a) The translation quality.

(b) The translation delay or lagging in the case of online machine translation.

(c) The translation's computational cost.

THESIS OUTLINE

5

(a) To address the first point, we introduce Pervasive Attention (Chapter 3), an NMT model with a computational graph different from existing encoder-decoder models. In Pervasive attention, the source and the target communicate and interact throughout the encoding process towards abstract features. To this end, our NMT model uses two-dimensional convolutional neural networks to process a grid of features where every position represents an interaction between a target and a source tokens.

(b) To improve the translation's delay in online NMT systems (Chapter 4), we first setup a common framework for online sequence-to-sequence models that will allow us to train existing deterministic decoders that alternate between reading the source and writing the target in a pre-determined fashion, and dynamic decoders that condition their decoding path on the current input. We first prove the effectiveness of the deterministic online decoders and their ability to perform well outside the delay range they were optimized for. We then adapt Pervasive Attention models for the task of online translation with both a deterministic and a dynamic decoding strategy.

Thesis Outline

To present our contributions we structure this thesis in six chapters:

Chapter 2: Background. We provide in this chapter an overview of background knowledge on the subject of Machine Translation relevant to the understanding of this thesis.

Chapter 3: Pervasive Attention. We describe in this chapter the building blocks of our Pervasive Attention models. For each block we motivate different design choices, and compare their effect on the translation's quality in an ablation study. We then compare our model to state-of-the-art sequence-to-sequence models on a few MT benchmarks.

CHAPTER 1. INTRODUCTION

Chapter 4: Online Neural Machine Translation. We introduce in this chapter our proposed framework for modeling and training online NMT models. We adapt Transformer and Pervasive Attention models for online decoding and propose dynamic decoding agents devised for Pervasive Attention models. We also study in this chapter the existing deterministic wait-k decoding models to better understand their full potential as well as their limits, and compare our dynamic Pervasive-Attention-based decoding agents to the deterministic variety.

Chapter 5: Cost-effective Decoding. We prepare in this chapter the Transformer model for the setup of anytime prediction where the NMT model is required to emit a prediction at multiple exit points of the decoder. We then describe our novel halting mechanisms to model the amount of computation required by every input and suggest an easy way to supervise these mechanisms.

Chapter 6: Conclusion. The final chapter lists our conclusions where we summarize our results and findings and provide an outlook to future research directions.

Publications

Several contributions presented in this dissertation relate to the following peer-reviewed articles:

1) Maha Elbayad, Laurent Besacier, and Jakob Verbeek. 2018a. Pervasive Attention:

2D Convolutional Neural Networks for Sequence-to-Sequence Prediction. In Proc. of CoNLL 2) Maha Elbayad, Jiatao Gu, Edouard Grave, and Michael Auli. 2020b. Depth-Adaptive Transformer. In Proc. of ICLR

The following preprint is discussed:

3) Maha Elbayad, Laurent Besacier, and Jakob Verbeek. 2020a. Improved Training Techniques for Online Neural Machine Translation

OPEN-SOURCE IMPLEMENTATION

7

The following publication is related, but is not extensively discussed in this thesis (the publication is covered in Appendix E): 4) Maha Elbayad, Laurent Besacier, and Jakob Verbeek. 2018b. Token-level and Sequencelevel Loss Smoothing for RNN Language Models. In Proc. of ACL

Open-source Implementation

Pervasive Attention models introduced in Chapter 3 of this thesis and Online NMT models described in Chapter 4 are implemented in our open-source code available at: https://github.com/elbayadm/attn2d. CHAPTER 2. BACKGROUND

Data for Neural Machine Translation

NMT systems are usually trained with parallel corpora collected from bilingual texts such as news stories, translated lectures or transcribed talks. A parallel corpus is a set of paired tokenized utterances {(x (i) , y (i) )} i∈I where I is an index set. We will refer to x as the source and to y as the target and drop the superscript (i) when processing a single sample (x, y).

The paired sequences have possibly different lengths |x| and |y|. From this set of sequences two vocabularies (set of occurring tokens) are built for each language. The utterances in the corpus can be tokenized into individual words, characters or segments. When using words as tokens, the vocabularies are very large and are consequently truncated i.e. we remove low-frequency tokens and replace them in the sequences with a special token <unk>.

Translation is, however, an open-vocabulary problem and a fixed word-vocabulary limits the capability of the model to generalize to unseen words. Tokenizing into characters on the other hand solves the issue of out-of-vocabulary words but lead to very long sequences that are hard to model. Alternatively, [START_REF] Sennrich | Neural Machine Translation of Rare Words with Subword Units[END_REF] segment the corpus into subwords with the byte pair encoding compression algorithm [START_REF] Gage | Convolutional Sequence to Sequence Learning[END_REF], BPE in short. Subwords are initialized as characters and are iteratively refined by merging the most frequent pair of subwords into a new one. With this segmentation, we can represent rare and unseen words with significantly smaller vocabularies. This type of tokenization is referred to as BPE and can be learned as two independent encodings, one for each language, or as a joint BPE on the bitexts.

In a given experiment, the data is tokenized and divided into three parts: a training set to train the model on, a development set to tune the model's hyper-parameters and a test set on which the system if evaluated and compared to existing work. We pad an end of sequence marker </s> at the end of each sequence (source and target) and include </s> as a special token in the vocabularies. A beginning of sequence marker <s> is also added to the vocabulary but is not considered part of the sequence (c.f . §2.5.1). As such, a pair (x, y) is formatted as:

x = (x 1 , x 2 , . . . , x |x|-1 , </s>), y = (y 1 , y 2 , . . . , y |y|-1 , </s>).

(2.1)

TOKEN REPRESENTATIONS 11

Abstracting away from the particular task of machine translation, the general setup of a learning problem is to learn a mapping of the input to an output label. In Natural Language Processing (NLP), the input is a sequence of tokens from a vocabulary V and the labels are either atomic, one for each token (part-of-speech tagging, named entity recognition, etc.) or global i.e. a label for the whole sequence (sentiment classification, entailment, etc.) Two major problems arise, the first is the discreteness of the input, ill-suited for statistical classifiers, and the second is the input's variable length.

We will briefly introduce continuous token representations that are well-disposed for learning in §2.2 and then look in §2.3 at sequence models used to contextualize and transform these atomic representations into sequence-level feature vectors. Special attention is given to language models in §2.4, and the whole NMT framework is put in place in §2.5. Three NMT architectures, used throughout this thesis as baselines, are described in §2.6. Finally, we discuss a few key characteristics of sequence-to-sequence models in §2.7

Token Representations

A token from a vocabulary V is represented with a feature vector. Each dimension of this vector is supposed to represent a feature with a possibly interpretable property. Conventionally, the vocabulary V is indexed and a token is represented with its index in V or equivalently with a one-hot vector in R |V| in which all entries are zero except the one corresponding to the token's index. These one-hot representations are sparse and will yield a poorly trained statistical classifier. Besides, they do not take into account the distributional hypothesis of language [START_REF] Zellig | Distributional Structure[END_REF] stating that the meaning of a word can be inferred from the contexts in which it is used.

Many algorithms were proposed to learn representations that leverage this hypothesis, some are clustering-based [START_REF] Peter | Efficient Architecture Search by Network Transformation[END_REF], others are based on the co-occurrence matrix [START_REF] Ritter | Self-Organizing Semantic Maps[END_REF][START_REF] Dumais | Using Latent Semantic Analysis to Improve Access to Textual Information[END_REF], but, the most commonly used are distributed representations also called token embeddings. These embeddings are typically the first layer in a neural language model and are learned jointly with the other parameters [START_REF] Bengio | A Neural Probabilistic Language Model[END_REF][START_REF] Schwenk | Connectionist Language Modeling for Large Vocabulary Continuous Speech Recognition[END_REF][START_REF] Bengio | A Neural Probabilistic Language Model[END_REF][START_REF] Mnih | Three New Graphical Models for Statistical Language Modelling[END_REF]Collobert CHAPTER 2. BACKGROUND and Weston, 2008). Instead of training a language model (predicting the next token in a sequence), recent works shifted to a Cloze task, where the model learns to fill in a few masked tokens (Mikolov et al., 2013a,b;[START_REF] Devlin | Bert: Pre-Training of Deep Bidirectional Transformers for Language Understanding[END_REF] or to detect tokens replaced by incorrect, yet plausible, fakes [START_REF] Clark | ELECTRA: Pre-training Text Encoders as Discriminators Rather Than Generators[END_REF].

A set of d-dimensional embeddings form a matrix E ∈ R d×V where the i-th column of E is the feature vector associated with the i-th token in V. Through the one-hot vector w of a token, the dense feature vector is retrieved with Ew.

Encoding Sequences

Let x = (x 1 , . . . , x |x| ) be a sequence of tokens from a vocabulary V and let E be an embedding matrix of V. The goal of a sequence model is to learn how to combine the token embeddings

(Ex 1 , . . . , Ex |x| ) of x into a fixed-size representation f (x).
When encoding sequences of fixed lengths, concatenating the embeddings is a valid choice [START_REF] Bengio | A Neural Probabilistic Language Model[END_REF], but if the task requires fixed-size representations for sequences of arbitrary length, a naive approach would ignore the sequence's temporal nature and encode it as an averaged bag of words:

f (x) = 1 |x| i Ex i . (2.2)
More interestingly, f could be designed to pay attention to the input's structure. In the following we will look at three majors architectures used to encode an input sequence:

convolutional, recurrent and attention-based.

Convolutional Encoders

The one-dimensional convolution is an operator with a filter ω ∈ R k , k is called the width of the convolution. Let v be a sequence of length t with elements in R. The output of the convolution is simply the dot product of the filter ω with every k-gram of v.

If v i-k :i+k is 2.3. ENCODING SEQUENCES

13

the k-gram centered on v i with k tokens on each side (k = k/2 ), the i-th output is

(v ω) i = ω v i-k :i+k . (2.3)
A narrow convolution with k ≤ t yields a shorter output (v ω) ∈ R t-k+1 , but the operator can be widened with zero-padding i.e. adding zeroes in out-of-range positions [START_REF] Kalchbrenner | A Convolutional Neural Network for Modelling Sentences[END_REF]. The normal convolution, narrow or wide, applies a filter to k-grams i.e. k contiguous terms in the sequence, however, the filter can be dilated [START_REF] Yu | Multi-Scale Context Aggregation by Dilated Convolutions[END_REF] to expand its reach. With a dilation factor l, we skip elements from the sequence with a step l.

The dilated convolution operator, denoted with l , is defined as:

(v l ω) i = k j=-k w j v i-jl .
(2.4)

We are rather interested in multi-dimensional sequences, and so the convolution operator is modified to combine the input features with a bank of filters. In this case we will denote

with V the input matrix in R d in ×t : V =     v 1 . . . v t     .
(2.5)

The number of output features d out is dictated by the number of filters ω ∈ R dout×d in ×k . The j-th channel of the output is evaluated as:

(V ω) j = d in l=1 V l ω jl .
(2.6) Time-Delay Neural Networks (TDNN). Time-delay networks [START_REF] Waibel | Phoneme Recognition Using Time-Delay Neural Networks[END_REF][START_REF] Hinton | Connectionist Learning Procedures[END_REF], were adopted as sequence models for natural language tasks in [START_REF] Collobert | A Unified Architecture for Natural Language Processing: Deep Neural Networks with Multitask Learning[END_REF]. A TDNN layer is a one-dimensional narrow convolution applied to the matrix of embeddings:

S = (Ex 1 , . . . , Ex |x| ) =     Ex 1 . . . Ex |x|     ∈ R d×|x| . (2.7) CHAPTER 2. BACKGROUND
Typical to convolutional networks [START_REF] Lecun | Gradient-based Learning Applied to Document Recognition[END_REF], these layers are stacked to gradually grow the encoder context. To capture salient segments of x and encode it into a fixed-size representation, [START_REF] Collobert | A Unified Architecture for Natural Language Processing: Deep Neural Networks with Multitask Learning[END_REF] added a max-over-time pooling layer after the TDNN. Let S N ∈ R d×t be the output of the TDNN after N convolutions, the max-pooled output is evaluated as:

∀k ∈ [1..d], Max-pool(S N ) k = max 1≤i≤t S N ki .
(2.8)

Dynamic Convolutional Neural Network (DCNN). With TDNNs, the use of narrow convolutions heavily constrain the minimum length that the model can handle, in fact, the input sequence has to be larger than the filter at every layer. [START_REF] Kalchbrenner | A Convolutional Neural Network for Modelling Sentences[END_REF] proposed a better control of the sequence length throughout the network with DCNNs. They used wide convolutions and dynamic k-max pooling that selects the k most active positions over time.

Recurrent Encoders

Recurrent neural networks [START_REF] Rumelhart | Learning Representations by Back-Propagating Errors[END_REF][START_REF] Michael | Serial Order: a Parallel Distributed Processing Approach[END_REF][START_REF] Elman | Finding Structure in Time[END_REF], RNN for short, process the sequence tokens one at a time recursively. In its vanilla form, the RNN encodes the input vectors (Ex 1 , . . . , Ex |x| ) recursively as follows:

s 0 = 0, ∀i ∈ [1..|x|], s i = nonlin W Ex i s i-1 , (2.9)
where nonlin is non-linear differentiable activation function.

Due to the recursive nature of Eq. (2.9), the state s i is an encoding of the prefix x ≤i and the final state encodes the full sequence x.

In practice, RNNs with gated units (LSTMs [START_REF] Hochreiter | Long Short-Term Memory[END_REF][START_REF] Gers | Learning to Forget: Continual Prediction with LSTM[END_REF] and GRUs [START_REF] Cho | Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation[END_REF]) replace the vanilla version for their proven ability to capture long-term dependencies in language modeling. Without loss of generality, we describe any and all RNNs with an update function g applied recursively to the feature vectors:

s 0 = 0, ∀i ∈ [1..|x|], s i = g(Ex i , s i-1 ).
(2.10)

In some NLP tasks such as sequence tagging, the labels are assumed to be conditioned on the entire sequence x. However, the previously introduced recurrent network is unidirectional i.e. the state s i is encoding only the left context x ≤i . Bi-directional recurrent networks [START_REF] Schuster | Bidirectional Recurrent Neural Networks[END_REF] exploit the context on both sides. Two separate recurrent layers scan x forwards and backwards and the output is the concatenation of their states. RNNs can also be stacked [START_REF] El | Hierarchical Recurrent Neural Networks for Long-Term Dependencies[END_REF] by simply feeding the outputs of one RNN to another. In multiple tasks stacked RNNs outperform single-layer RNNs, similar to the stacking of convolutional layers in the previous section, this allows the model to induce representations at growing levels of abstraction proportional to the layer's depth.

Attention-based Encoders

Self-attention for sentence embedding [START_REF] Lin | A Structured Self-Attentive Sentence Embedding[END_REF]) is a mechanism relating tokens within a sequence to each other in order to compute a representation of the full sequence. In this form, the only role of self-attention is to aggregate a sequence of states S computed with another sequence model, e.g. a recurrent network, into a fixed-size vector: (2.11) with weights W 1 ∈ R d×d and W 2 ∈ R d×r . The softmax operator [START_REF] Bridle | Probabilistic Interpretation of Feedforward Classification Network Outputs, with Relationships to Statistical Pattern Recognition[END_REF], applied column-wise, normalizes the column vectors into probability distributions. For a matrix X ∈ R m×n :

Attention(S) = S • softmax(nonlin(S W 1 )W 2 ) ∈ R d×r ,
∀(i, j) ∈ [1..m] × [1..n], softmax(X) ij = e x ij m i =1 e x i j .
(2.12)

The parameter r allows for computing multiple representations and possibly stacking the attention modules for more complex features. To encode the sequence in a single vector, r is set to 1.

Rather than using attention on top of recurrent models, [START_REF] Vaswani | Attention Is All You Need[END_REF] introduced a fully attentional model where the input embeddings are updated with an attention mechanism from the get-go. Their approach is based on a key-value-query dot-product attention bearing similarity to Memory Networks [START_REF] Weston | Memory Networks[END_REF][START_REF] Sukhbaatar | End-to-End Memory Networks[END_REF][START_REF] Miller | Key-Value Memory Networks for Directly Reading Documents[END_REF]. The memory in the form of key-value pairs is a representation of the context i.e. the CHAPTER 2. BACKGROUND set of token embeddings to be encoded. Each input at a given position queries the memory and assigns relevance probabilities to its content through a measure of similarity to the keys.

The relevance probabilities are then used to read the memory by taking a weighted sum of its values.

Formally, with S = (Ex 1 , . . . , Ex |x| ) the matrix of input embeddings and W Q , W K , W V maps for the queries, keys and values respectively. The attention output is:

Attention(S) = (W V S) • softmax 1 √ d (W K S) (W Q S) . (2.13)
For a fixed-size representation, these new features can simply be pooled or a special token is added to the sequence and its state is used as the sequence-level representation [START_REF] Devlin | Bert: Pre-Training of Deep Bidirectional Transformers for Language Understanding[END_REF].

Language Models

Let y = (y 1 , . . . , y |y| ) be a sequence of tokens from a vocabulary V. The role of a language model is to estimate the joint probability p(y) i.e. to assess the plausibility or fluency of y. To reduce the difficulty of modeling p(y), we leverage the order of the sequence and assume that the distribution of a given token y t is conditioned on the history y <t . With this assumption, the joint probability p(y) is broken down by the chain rule as follows:

p(y) = |y| t=1 p(y t | y <t ).
(2.14)

We refer to y <t = (y 1 , . . . , y t-1 ) as the context or the history. Each product term p(y t | y <t )

is the model's conditional probability for the t-th y t token given the history y <t . For the first term (t = 1), the only available context is the special token <s>.

A general dependence on all previous tokens grows exponentially in complexity with respect to the length of the sequence. This problem, referred to as the curse of dimensionality, leads to the consideration of the much stronger (n -1)-order Markov assumption.

Models with this assumption, also called n-gram models, condition each token's probability on the history of the most recent (n -1) tokens. In practice, n-gram models table the

LANGUAGE MODELS

conditional probabilities y t | y t-n+1:t-1 and explicitly enumerate n-grams occurring in a training corpus. As a result, the chosen n is about 4 to 6 tokens and the models generalize poorly to unseen contexts. [START_REF] Bengio | A Neural Probabilistic Language Model[END_REF] fought this curse of dimensionality with distributed representations.

More precisely, they associated distributed feature vectors or embeddings with each word in the vocabulary then learned to transform the vectors of a given sequence into a joint probability.

Formally, let E ∈ R d×|V| be the matrix of d-dimensional embeddings. A neural language model is tasked with modeling p(y t | y <t ) as a mapping of the context vectors (Ey 1 , . . . , Ey t-1 ):

p(y t | y <t ) = softmax(W p f (Ey 1 , . . . , Ey t-1 )).
(2.15)

The map W p guarantees the final output is |V|-dimensional and the softmax operator normalizes it into a probability distribution with:

∀x ∈ R |V| , softmax(x) i = e x i |V| i =1 e x i .
(2.16)

The map f in [START_REF] Bengio | A Neural Probabilistic Language Model[END_REF] is a simple feed-forward network with, as input, the concatenation of the last n -1 tokens of the history:

x = [Ey t-n+1 , . . . , Ey t-1 ] , p(y t | y <t ) = softmax(Wx + b + U • tanh(Hx + d)), (2.17)
with weights W, U, H and biases b, d. Although this work addresses the curse of dimensionality as it pertains to the handling of unseen n-grams in the training corpus, its capacity is still limited by the design of the feed-forward network where n is specified ad hoc. In other words, we can generalize better to unseen n-grams but we cannot use contexts larger than n tokens.

Recurrent Language Models

h 0 = 0, ∀t ∈ [1..|y|], h t = nonlin W Ey t h t-1 . (2.18) CHAPTER 2.

BACKGROUND

The state h t-1 is an encoding of the prefix (Ey 1 , . . . , Ey t-1 ) and we can predict the next token y t as in Eq. (2.15) with:

p(y t | y <t ) = softmax(W p h t-1 ). (2.19)

Convolutional Language Models

The first convolutional decoders for language modeling where used in ByteNet (Kalchbrenner et al., 2016b). To prevent leaking signal from future tokens, ByteNet uses masked onedimensional convolution (Oord et al., 2016b). The convolution at step i in Eq. ( 2.3) encodes the k-gram centered on y t . We can stop the leaking future signal by zeroing out the right side of the filter, effectively convolving k = k/2 tokens from the history plus the current token Ey t :

∀j > k , ω j = 0.
(2.20)

Similar to recurrent uni-directional architectures, the output of stacked masked convolutions at step t -1 encodes only the prefix y <t . Models with the particular property of encoding only past tokens are suitable for auto-regressive generation (c.f . §2.5.1).

ByteNet also uses multiplicative units [START_REF] Kalchbrenner | Video Pixel Networks[END_REF] to incorporate LSTMlike gates in the layers and wrap convolutional layers with residual connections (He et al., 2016b). Multiple of these layers are then stacked to expand the encoded context. The particularity of ByteNet resides in its encoder-decoder stacking with dynamic folding, more on this in §2.5.

ConvS2S [START_REF] Gage | Convolutional Sequence to Sequence Learning[END_REF] introduces another fully convolutional language model.

With this architecture the language model is equipped with an mechanism to attend over the source states. This architecture is detailed in §2.6.2.

Attention-based Language Models

Similar to masked convolution, the attention operator described in Eq. (2.13) can be made auto-regressive by limiting the memory access of each query to its predecessors i.e. the past

SEQUENCE-TO-SEQUENCE MODELS

19

context. With H = (Ey 1 , . . . , Ey |y| ) the matrix of token embeddings, at the j-th position, scores associated with future keys {Ey i | i > j} will be masked.

M ij =    0, i ≤ j -∞, otherwise, (2.21) Scores = 1 √ d (W K H) (W Q H), (2.22) Attention(H) = (W V H) • softmax (Scores + M) .
(2.23)

Self-attention and its masked version are the building blocks of the state-of-the-art Transformer model [START_REF] Vaswani | Attention Is All You Need[END_REF]. The Transformer model is described in §2.6.3.

Sequence-to-sequence Models

A sequence-to-sequence model is a conditioned generation framework also called encoderdecoder [START_REF] Kalchbrenner | Recurrent Continuous Translation Models[END_REF][START_REF] Cho | Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation[END_REF][START_REF] Sutskever | Sequence to Sequence Learning with Neural Networks[END_REF]. This model is capable of generating arbitrary length output sequences that are contextually appropriate given a source sequence. Sequence-to-sequence models are widely applied for a range of tasks like machine translation, speech recognition, summarization, question answering and image captioning. The most common pipeline for sequence-to-sequence models is to use an encoder that takes an input sequence and creates a contextualized representation of it.

This representation is then passed to a decoder which generates an output sequence.

We have discussed in §2.3 existing models capable of encoding a sequence and in §2.4 language models or decoders capable of generating variable length sequences. In the following, we will look at how these two modules are combined to build a sequence-to-sequence model.

Let us consider a pair of source-target sequences (x, y) embedded with matrices E x and E y respectively. For conditioned generation, we model the conditional probability p(y | x) instead of p(y). Following the same reasoning, this probability is factorized as:

p(y | x) = |y| t=1 p(y t | y <t , x).
(2.24)

CHAPTER 2. BACKGROUND Each term p(y t | y <t , x) is not only a function of the prefix y <t but also the source x.

Consequently, the map f introduced in Eq. (2.15) takes an additional input:

p(y t | y <t , x) = softmax(W p f (y <t , x)).
(2.25)

In the language models previously discussed, we represented the prefix y <t with token embeddings (E y y 1 , . . . , E y y |y| ) that are auto-regressively encoded into fixed-size states. To inject x into the input we can encode it into a fixed-size vector c (e.g. the last hidden state of an RNN or the pooled features of a ConvNet) and then include c as additional input in every atomic update of the language model [START_REF] Kalchbrenner | Recurrent Continuous Translation Models[END_REF][START_REF] Cho | Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation[END_REF]. Alternatively, with recurrent architectures, this feature-vector can be used to initialize the language model states i.e. h o = c in Eq. (2.18) [START_REF] Sutskever | Sequence to Sequence Learning with Neural Networks[END_REF].

Rather than cramming the full source sequence in a single vector c, [START_REF] Bahdanau | Neural Machine Translation by Jointly Learning to Align and Translate[END_REF], inspired by alignment models in statistical machine translation, interfaced the encoder and decoder with an attention module. At every time-step t, this module combines the source states (s 1 , . . . , s |x| ) into a context vector c t to be included in the decoder state update. c t is simply a linear combination of (s 1 , . . . , s |x| ) with weights estimated by a feed-forward network

f att . Formally: ∀j ∈ [1..|x|], tj = f att (h t-1 , s j ) = w tanh(Uh t-1 + Vs j ),
(2.26)

c t = |x| j=1 α tj s j , α t = softmax( t ) (2.27)
with w, U and V the parameters of f att . In their analysis of attention mechanisms for machine translation, Luong et al. (2015) found that modeling f att as a simple dot-product of the two vectors is a better choice. With this mechanism, the decoder decides which parts of the source sequence to focus on in order to predict y t . The score α tj could be interpreted as a soft alignment between y t and x j (see a visualization of these weights in Figure 2.1).

Conditioned Auto-regressive Generation

The ultimate goal of a sequence-to-sequence model is to generate the most likely target sequence ŷ = arg max y p(y | x). the most likely sequence with dynamic-programming algorithms (e.g. with Viterbi algorithm in O(|y|V 2 ) time), with neural language models, there are no algorithms to find the optimal output sequence in subexponential time, instead we resort to approximations.

To generate a sequence y, also called a hypothesis, we first encode the source sequence x and initiate the prefix with y 0 = <s>. From this input we estimate the output distribution p( y 1 | y 0 , x) and sample the next token from it. The sampled token is embedded and added to the model's input for the next step. We continue sampling tokens until the end of sequence marker </s> is sampled or a length limit is reached. This technique of generation is autoregressive i.e. output at a time-step is conditioned on previous outputs and can only be used for language models trained accordingly.

The straight-forward approach to approximate ŷ is greedy decoding. We previously decomposed p(y | x) into a product of local scores p(y t | y <t , x) and so greedy decoding optimizes each term individually by simply taking y t = arg max yt p(y t | y <t ) at every step.

Another option is beam-search [START_REF] Lowerre | The HARPY Speech Understanding System[END_REF]. Also used in statistical machine translation [START_REF] Koehn | Statistical Phrase-Based Translation[END_REF][START_REF] Tillmann | Word Reordering and a Dynamic Programming Beam Search Algorithm for Statistical Machine Translation[END_REF], beam-search finds a better scoring sequence by keeping track of b partial hypotheses. At every decoding step, the successors of the hypotheses are scored and only the best b remain in the beam. The hypotheses are usually scored with their log-likelihood. However, beam-search favors short sequences as a negative log-probability is added with each new token penalizing long hypotheses. To normalize the length in the finalized hypotheses (ones that emitted </s>), [START_REF] Wu | Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation[END_REF] CHAPTER 2. BACKGROUND re-score the hypotheses with:

score( y) = log p( y | x) length-norm( y) , length-norm( y) = µ + | y| µ + 1 α .
(2.28)

µ is often set to 0 and α, referred to as the length penalty, is optimized on a development set. Depending on the choice of α we will either favor shorter sequences if α < 1 or longer ones with α > 1.

To measure the quality of the generated sequence y w.r.t. to the gold standard y, the metric of choice is often BLEU [START_REF] Papineni | BLEU: a Method for Automatic Evaluation of Machine Translation[END_REF]. BLEU measures n-gram precisions, n ranging from 1 to 4, and reports their geometric average. To compute an n-gram precision, we divide the number of correct n-grams by the total number of n-grams in the hypothesis.

Evaluating a precision score per sequence leads to noisy scores, and so, the precision is macroaveraged by dividing the sum of correct n-grams by their total number in the overall corpus.

The final score is multiplied by a brevity penalty to control the length of the candidates.

BLEU is a precision score and so the higher the score the better.

Another evaluation metric is the perplexity over unseen sequences. Perplexity measures how well the model fits a set of samples; a lower perplexity indicates a better fit. For a set of N pairs {(x (i) , y (i) )} 1≤i≤N , we feed the source x (i) as well as the ground truth prefix y

(i) <t
and estimate the likelihood of correctly predicting the next token y (i)

t . The perplexity PP is evaluated as:

PP = 2 -, = 1 i |y (i) | i log p(y (i) | x (i) ).
(2.29)

Training Sequence-to-Sequence Models

We train an NMT model by estimating its parameters θ with regularized Maximum Likelihood Estimation (MLE). The parameters of a sequence-to-sequence model θ include all of the model's parameters from the encoder to the decoder and everything in-between.

Given a training set of N pairs {(x (i) , y (i) )} 1≤i≤N , we solve the following problem:

θ * = arg max θ∈Θ N i=1 log p(y (i) | x (i) ; θ) + Ω(θ), (2.30)
where Ω is a regularization function such as the widely used L 2 -regularization, also called weight decay, with Ω(θ) = θ 2 . Interestingly, all of the modules previously described are differentiable w.r.t. their parameters and so the model can be trained end-to-end with back-propagation [START_REF] Rumelhart | Learning Representations by Back-Propagating Errors[END_REF] and gradient-based optimization. In practice, the training data is batched into small sets of samples and θ is optimized with mini-batch stochastic gradient descent. In all of our experiments the reported batch-size is the number of source tokens that the model sees before every update, possibly accumulating gradients over multiple backward passes.

For gradient-based optimization, we use Adam [START_REF] Diederik | Adam: A Method for Stochastic Optimization[END_REF]. This algorithm computes adaptive learning rates from estimates of first and second moments of the gradients in order to achieve a better convergence speed.

The base learning rate follows an inverse square-root schedule with a warm-up phase [START_REF] Vaswani | Attention Is All You Need[END_REF]. The learning rate is initialized at lr 0 then linearly increased throughout T w steps up to lr max , afterwards, the learning rate is decreased proportionally to the inverse square-root of the update step t:

lr(t) = min lr 0 + lr max -lr 0 T w • t, lr max T w t .
(2.31)

We use Fairseq [START_REF] Ott | fairseq: A Fast, Extensible Toolkit for Sequence Modeling[END_REF], a toolkit for sequence modeling based on PyTorch [START_REF] Paszke | Automatic Differentiation in PyTorch[END_REF], to train all of our models.

Baseline Architectures

In the rest of this thesis we will consider an LSTM-based model with an attention mechanism [START_REF] Bahdanau | Neural Machine Translation by Jointly Learning to Align and Translate[END_REF] as an archetype of recurrent architectures. For convolutional architectures, we will use the ConvS2S model [START_REF] Gage | Convolutional Sequence to Sequence Learning[END_REF] and for attention-based models, the state-of-the-art Transformer [START_REF] Vaswani | Attention Is All You Need[END_REF]. We will describe in the following the components and particularities of each of these models. The hyper-parameters described below will be specified in the experiments sections of subsequent chapters.

Bi-LSTM

In Bi-LSTM models, the encoder is a bi-directional LSTM and the decoder is a uni-directional LSTM with dot-product attention. The encoder hidden state size is twice the size of the embeddings (d enc = 2d emb ) and the decoder hidden state has the same size as the embedding

(d dec = d emb ).
For regularization, we apply dropout [START_REF] Srivastava | Dropout: A Simple Way to Prevent Neural Networks from Overfitting[END_REF] to the input embeddings and to the output of every layer with a rate p drop .

ConvS2S

ConvS2S is a fully convolutional encoder-decoder model, the first of its kind to outperform recurrent architectures. On each side, the input is a sum of token and position embeddings.

These inputs are processed with a stack of N convolutional layers. The encoder and decoder are interfaced with a dot-product attention. Each of these components is detailed below:

Position embedding. These position embeddings encode the absolute position of a token in the sequence i.e. for x i in x we embed the index i. Similar to token embeddings, they form a matrix P with columns representing each position.

Convolutional layers. In ConvS2S, each convolution is gated [START_REF] Meng | Encoding Source Language with Convolutional Neural Network for Machine Translation[END_REF]Dauphin et al., 2017) i.e. it yields double the requested channels then use one half to gate the other.

Conv(X) = [A, B] , (2.32) Gated-conv(X) = GLU(Conv(X)) = A sigmoid(B), (2.33)
where is the Hadamard product (element-wise) and GLU is the gated linear unit, a nonlinearity using half of the input channels to scale the other half as illustrated in Figure 2.2.

BASELINE ARCHITECTURES

The convolutions are also surrounded with residual connections (He et al., 2016b). If the layer map is F then the final output is the following:

Y = γ(X + F(X)), (2.34)
with γ a scaling factor set to √ 0.5 to stabilize the feature variance.

Attention. Each layer of the decoder is equipped with a dot-product attention module. In its most generic form, this module has three input matrices, the keys K ∈ R d×|x| , the values V ∈ R d×|x| and the queries Q ∈ R d×|y| and it produces a matrix in R d×|y| :

Attention(K, V, Q) = V • softmax(K Q). (2.35)
ConvS2S particularly places a large importance on the input embeddings as they are integrated into the attention values V and queries Q. Let us consider S 0 and S N to be the initial and final states of the encoder respectively, and let us denote with H n the output of the decoder's n-th layer and with H 0 its initial input. The n-th layer performs the following transformations:

H n = γ H n-1 + Gated-conv(H n-1 ) , (2.36) Q = γ(W Q H n + H 0 ), K = S N , V = γ(S N + S 0 ), (2.37) O = Attention(K, V, Q), H n = γ(W O O + H n ).
(2.38)

Regularization. For regularization, dropout masks are applied to the input sum of token and position embeddings and to the output of each convolution before the gating and the residual connection with a rate p drop .

Transformer

This sequence-to-sequence model is based entirely on attention. The input to the Transformer encoder (resp. decoder) is a sum of token and position embeddings. This input is processed with a stack of N blocks. Each encoder block has 2 sub-blocks, multi-head self-attention and a feed-forward network. The decoder has an additional sub-block, a multi-head attention to interact with the source states. The key elements of this architecture are described below. If P is the embedding matrix with columns in R d associating the i-th position to its i-th column, then:

ω k = 10000 -2k/d , P j,i =    sin (ω k i) , if j = 2k sin π 2 + ω k i , if j = 2k + 1.
(2.39)

Each dimension of the positional encoding corresponds to a sinusoid. The wavelengths 2π/ω k progress geometrically resembling alternating bits in continuous space (c.f . Figure 2.3).

Multi-head attention. Multi-heading consists of concatenating the outputs of n H different heads, producing vector representations in R n H d h . An attention head receives key-value pairs (K, V) and queries Q, and outputs d h -dimensional columns:

Attention(K, V, Q) = (W V V) • softmax 1 √ d h (W K K) (W Q Q) , (2.40)
where the weights (W K , W V , W Q ) map the keys, values and queries to R d h . Except from the normalizing scale 1 √ d h , this attention is similar to the usual dot-product attention. In the case of self-attention, (K, V, Q) are all set to the encoder (resp. decoder) hidden states, with the appropriate masking in the decoder side (c.f . §2.4.3). For encoder-decoder interfacing the keys and values are the final encoder states and the queries are the decoder states.

Feed-forward network. The second sub-block is a point-wise feed-forward network FF consisting of two affine transformations with a non-linear function, ReLU, in between. ReLU 2.7. DISCUSSION [START_REF] Nair | Rectified Linear Units Improve Restricted Boltzmann Machines[END_REF] is defined as ReLU(x) = max(0, x).

FF(x) = W 2 ReLU(W 1 x + b 1 ) + b 2 .
(2.41)

The matrix W 1 ∈ R d FF ×d maps to a larger space, usually d FF = 4d, and W 2 ∈ R d×d FF maps back to R d .

Skip connections and normalization. Multi-head (self-)attention and the feed-forward network are surrounded with a residual connection followed with a layer-normalization [START_REF] Lei Ba | Layer Normalization[END_REF]. This normalized skip-connection is referred to as AddNorm. With F a map and LN the layer-normalization operator,

AddNorm(x) = LN(x + F(x)).
(2.42)

LN computes statistics over the channels for each sample and for each time-step, and normalizes the activations. LN has usually two learnable affine transformation parameters (β, γ). For an activation vector a ∈ R d :

µ = 1 d d k=1 a k , σ 2 = 1 d d k=1 (a k -µ) 2 , LN(a) = 1 σ γ (a -µ1) + β.
(2.43)

Compared to the rigid scaling of Eq. (2.34), this normalization scheme flexibly conditions its output for the next layer.

Regularization. For regularization, dropout masks are applied to the input sum of token and position embeddings and to the output of each layer (FF and multihead-attention) before the residual connection with a rate p drop .

Discussion

An interesting concept when looking at sequence models is that of the receptive-field. Borrowed from computer vision, the receptive-field is the size of the context window captured in a given state vector. This notion is often paired with the amount of time and computation needed to reach an unbounded receptive-field.

CHAPTER 2. BACKGROUND

x (a) A stack of two normal convolutions.

x (b) A dilated convolution on top of a normal convolution.

x x (c) A bi-directional RNN.

x (d) Self-attention. In Figure 2.4a, stacking two normal convolutions with k = 3 gives a receptive-field of 5.

With the same amount of computation, dilating the top convolution, as in Figure 2.4b, gives a receptive-field of 7. Besides the size of the receptive-field, it is important to measure the path between a teaching signal i.e. the deepest state at a given time-step directly linked to a classifier, and the input token captured in its receptive-field. This path plays an important role in the model's ability to capture long-range dependencies, since the training signal needs to traverse it forward and backward [START_REF] Hochreiter | Gradient Flow in Recurrent Nets: The Difficulty of Learning Long-Term Dependencies[END_REF]. The path in convolutional encoders is of constant length N as long as |x| ≤ 1 + N(k -1). (a) A backward RNN to encode the source and initializing the decoder with the source context vector. [START_REF] Sutskever | Sequence to Sequence Learning with Neural Networks[END_REF] x x (b) Injecting the source context vector in every decoder update [START_REF] Cho | Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation[END_REF].

Attention x x
(c) Bi-RNN with an attention interface [START_REF] Bahdanau | Neural Machine Translation by Jointly Learning to Align and Translate[END_REF]. (Kalchbrenner et al., 2016b) Figure 2.5: Interfacing the encoder and decoder. The encoder in red and the decoder in blue.

x x [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] (d) ByteNet
In each architecture we highlight the path from x 3 to the teaching signal associated with y 5 .

future and past tokens (c.f . Figure 2 With this change, the path is t + j long which is particularly short for the initial time-steps.

With an attention-mechanism in between, the path length from a target-side state to a source token is reduced to O(1).

A particular interface is introduced in ByteNet (Kalchbrenner et al., 2016b) where the decoder is placed on top of the encoder. Since the two sequences are of different lengths, the encoder is parameterized to generate a|x| + b context vectors with wide convolutions and (a, b) chosen to approximate the length of target sequences in the corpus. With that, the convolutional decoder is fed the concatenation of a context vector from the encoder and a target token embedding. This design, with the use of dilated convolutions, reduces all paths to a logarithmic length.

Conclusion

In this chapter, we have covered the background knowledge needed to understand the context of this thesis. We first described the task of neural machine translation as a source-conditioned language model and went on to review existing sequence models to encode the source and language models to generate the target. We proceeded with describing the training and testing of NMT models and detailed the baseline models that will be used in the rest of this thesis.

We emphasized some properties of NMT models we deem central to the understanding of their effectiveness. These properties will guide our design choices and motivate our contributions in the following chapters.

Chapter 3

Pervasive Attention

We present in this chapter our novel NMT model dubbed Pervasive Attention.

Introduction

Sequence-to-sequence models, introduced in Chapter 2, achieve state-of-the-art performances in a plethora of tasks, including, but not limited to, speech synthesis (Oord et al., 2016a;[START_REF] Wang | Tacotron: Towards end-to-end speech synthesis[END_REF][START_REF] Arik | Deep Voice: Real-Time Neural Text-to-Speech[END_REF], image captioning [START_REF] Vinyals | Show and Tell: A Neural Image Caption Generator[END_REF][START_REF] Xu | Show, Attend and Tell: Neural Image Caption Generation with Visual Attention[END_REF]Yao et al., 2017a), machine comprehension and question answering [START_REF] Shen | ReasoNet: Learning to Stop Reading in Machine Comprehension[END_REF][START_REF] Liang | Neural Symbolic Machines: Learning Semantic Parsers on Freebase with Weak Supervision[END_REF][START_REF] Devlin | Bert: Pre-Training of Deep Bidirectional Transformers for Language Understanding[END_REF], semantic parsing [START_REF] Liang | Neural Symbolic Machines: Learning Semantic Parsers on Freebase with Weak Supervision[END_REF] and machine translation [START_REF] Ng | Facebook FAIR's WMT19 News Translation Task Submission[END_REF]. These models are based on processing a source sequence with an encoder and using its output to condition the generation of the target sequence by a separate decoder.

We raise two limitations of the encoder-decoder design:

Limited capacity. The attention mechanism interfacing the encoder and the decoder is limited to weighting the source representations with basic similarity scores. In fact, [START_REF] Michel | Are Sixteen Heads Really Better than One?[END_REF] established that the multiple heads in Transformer layers are more important in the encoder-decoder attention layers than in self-attention ones i.e. a complex similarity measure is needed to model the source-target interaction. We speculate that enriching the similarity measure of the interface is crucial to improving sequence-to-sequence models.

Late interaction. Be it a single representation or a set of feature vectors, the encoding of the source is completed before advancing to the decoder. The decoder has only access to high-level source features. In deep RNN-based encoder-decoder models, the attention mechanism connects the last layers in the encoder and decoder. In other variants of this recurrent model, [START_REF] Wu | Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation[END_REF] connects the last encoder layer with the first layer in the decoder. The evaluated context is then injected in all subsequent decoder layers. Although this choice was made to improve the training parallelism, it allows for the decoder to interact with the source from an early stage. ConvS2S and Transformer also score the ultimate encoder states evaluating different contexts at every decoding level. These state-of-the-art models share the property of an early interaction on the decoder side. We argue that we can push this further and have the two encoder-decoder models interwoven.

We propose to build a grid of pairwise interactions between the source and target tokens and process this two-dimensional input with a deep convolutional network (ConvNet). This

PERVASIVE ATTENTION MODEL

35

way, the source and target sequences meet from the starting point and are co-encoded in increasing abstraction levels throughout the ConvNet. Moreover, this interaction or attention is pervasive in the model and is more rich and complex in its modeling of (x, y) as a pair.

We will describe in §3. ). We will end the chapter with a discussion of the reported results and a few comments on recent works related to ours ( §3.4 and §3.5).

Pervasive Attention Model

Let us consider a neural machine translation task with a source-side vocabulary V x and a target side vocabulary V y , and let (x, y) be a pair of source-target sequences. Our model consists of building a grid representation of the pair (x, y) and then processing this grid with a resolution-preserving convolutional neural network. The final features of this network are aggregated in order to have a fixed-size representation per target token. An overview of the Pervasive Attention model is provided in Figure 3.1.

Input Representation

To build the input tensor of our model, we consider embedding matrices E x ∈ R d×|Vx| and E y ∈ R d×|Vy| for the source and target-side respectively. The input to our model is a threedimensional tensor H 0 ∈ R |y|×|x|×d corresponding to a |y| × |x| grid where at each position (t, j) we concatenate the embedding of the source word x j with the embedding of the target word y t and project the concatenation to R d with the matrix

W 0 ∈ R d×2d . ∀t, j ∈ [1..|y|] × [1..|x|], H 0 tj = W 0 E y y t E x x j ∈ R d . (3.1) CHAPTER 3. PERVASIVE ATTENTION s o u r c e x target y H 0 H 1 H 1 H 2 . . . H N-1 H N-1 H N Convolutional feature maps H conv
Final features

H out Aggregate features p(y 1 |y <1 , x) • • • • • p(y |y| |y <|y| , x)
Output predictions

Convolutions

The input features H 0 are processed with a ConvNet i.e. a set of stacked convolutional layers to jointly encode at each position (t, j) the source x and the target prefix y ≤t . The main operator in these layers is a causal two-dimensional convolution. In the following we describe this operator and detail the different ConvNet designs considered in this work.

Causal convolutions. As seen in §2.4.2, auto-regressive convolutional language models use masked convolutions. This type of convolution, also called causal, guarantees that the input at time t is convolved only with elements from time t and earlier. Tied with this property is that the convolution yields an output of the same length as its input. With two-dimensional convolutions for sequence-to-sequence tasks we have two time axes, one along the source x and the other along the target y. For the task of offline translation where the source sequence

x is fully available at the beginning of decoding, we will only tend to the causality along the y-axis. With that, let W ∈ R ky×kx be a convolution filter:

a) The input at position (t, j) of the grid is convolved only with past inputs in (t , j )

where 1 ≤ t ≤ t ≤ |y| and 1 ≤ j ≤ |x|. This is achieved through zeroing out the corresponding elements of W:

∀i ∈ k y 2 ..k y , ∀j ∈ [1..k x ], W ij = 0. (3.2) b)
The convolved output has the same dimension as the input along both axes. Maintaining the y-resolution is necessary to yield the |y| outputs required. However, for the x-axis we chose to preserve the resolution in order to keep the grid interpretable and to avoid dimensionality issues we may face with short source sequences.

(1)

The input dimension is maintained with zero paddings of lengths k y -1 and k x -1 to the y and x axes respectively.

With a stack of N causal convolutions, the receptive field is grown as a function of the filter size k y × k x and the depth N. In fact, after N convolutions, the features at a given position (1) The input has to be wider than the filter, but with stacked convolutions that reduce the input dimension, we risk reducing the input beyond the size of the filter especially with short sequences. CHAPTER 3. PERVASIVE ATTENTION (t, j) encode N k x /2 source tokens to the left and to the right of x j and N k y /2 target tokens preceding y t . Our two-dimensional causal convolution is illustrated in Figure 3.2.

Skip Connections

Another key aspect of a ConvNet is the skip connections used to aggregate the outputs of its early layers to be consumed by later ones. In computer vision, these connections are critical to the training of very deep networks with hundreds of layers. In NLP, however, the architectures are wide and shallow with only 6 blocks in the state-of-the-art Transformer. We hypothesize that a good NLP model should understand the sequence at increasing levels of abstraction. Skip connections provide a direct access to the previous levels of abstraction so that the next map could infer deeper features without having to remember or store previous ones.

Let F 1 , . . . , F N be the maps associated with N layers each outputting H n . We will denote with H

n-1 the input of the n-th layer and with H conv the ultimate output of the ConvNet. We detail in the following two main types of skip connections, residual and dense. For residual connections, we distinguish four variants depending on what follows the residual summation and how the final output H conv is prepared.

Residual connections. First proposed in He et al. (2016c), these skip connections are widely adopted in vision and NLP models and consist of simply taking the sum of the features:

∀n ∈ [1..N], H 0 = H 0 , H n = F n H n-1 , H n = H n + H n-1 , H conv = N n=0 H n . (3.3)
Residual-norm connections. A particular version of residual connections is addNorm, notably used in Transformer-based architectures [START_REF] Vaswani | Attention Is All You Need[END_REF]. It follows each summation in the path with a layer-normalization (LN, see §2.6.3).

∀n

∈ [1..N], H 0 = H 0 , H n = F n H n-1 , H n = LN H n + H n-1 . (3.4)
Suppose that the features are normalized and that each layer-normalization operator amounts to an element-wise linear transformation with weights γ n (γ 0 = 1). Then addNorm changes

PERVASIVE ATTENTION MODEL

39

the simple summation of residual connections to one with geometric-like weights.

∀n

∈ [1..N], H n = n k=0 n k =k γ k H k , H conv = N n=0 N k=n γ k H n , (3.5)
where is the Hadamard product.

Residual-cumulative connections. In order to explicitly include mid-level abstractions in the final features H conv , we propose to accumulate the residual outputs of the ConvNet.

∀n ∈ [1..N], H 0 = H 0 , H n = F n H n-1 , H n = γ H n-1 + H n , (3.6) H conv = 1 √ N + 1 N n=0 H n , (3.7)
where we add a variance stabilizing multiplier γ = 1/ √ 2 after each summation. (2) The final summation in Eq. (3.7) is also stabilized by the multiplier 1/ √ N + 1. Explicitly, the inputs of the ConvNet's layers and the final aggregate H conv are weighted sums of the feature maps

(H 0 , H 1 , . . . , H N ): ∀n ∈ [0..N], H n = n k=0 α n,k H k , α n,0 = γ n , α n,k = γ n-k+1 (∀k ∈ [1..n]), (3.8) H conv = 1 √ N + 1 N n=0 β n H n , β 0 = (1 -γ N +1 ) (1 -γ) , β n = γ(1 -γ N -n+1 ) (1 -γ) (∀n ∈ [1..N]). (3.9)
At fixed n, the weights α n,k are strictly increasing with the index k i.e. far away early features are assigned lower weights. The weights β n have the opposite monotonicity and so, early layers are assigned higher weights.

Residual-gated connections. We experimented with a parameterized information flow in the ConvNet with the help of gating mechanisms similar to Highway Networks [START_REF] Rupesh | Training very Deep Networks[END_REF]. We particularly separate the encoding flow from that of aggregating the features into a final representation. Let us consider two gates: forward f n and snapshot s n . The layer's signal committed to the final features H conv is controlled with the snapshot gate. This

H 0 ∈ R d F 1 H 1 concat F 2 H 2 concat F 3 concat H 3 H conv ∈ R d+Ng H 0 ∈ R d F 1 H 1 F 2 H 2 F 3 H 3 H conv ∈ R d H 0 ∈ R d F 1 H 1 LN F 2 H 2 LN F 3 LN H 3 H conv ∈ R d H 0 ∈ R d F 1 H 1 ×γ F 2 H 2 ×γ F 3 ×γ H 3 H conv ∈ R d H 0 ∈ R d s 0 F 1 s 1 H 1 f 1 F 2 s 2 H 2 f 2 F 3 s 3 H conv ∈ R d H 3 Dense Residual Residual Norm Residual Cumulative
Residual Gated ∀n

∈ [0..N], H 0 = H 0 , H n = F n ( H n-1 ), H n = f n H n-1 + H n , (3.10) H conv = N n=0 s n (H n ). (3.11)
The gates can be better visualized in Figure 3.3. Beside controlling the information flow, the motivation behind gating the skip connections is to visualize and interpret the contribution of every layer or level of abstraction into the final features. We experimented with a few options for the forward and snapshot gates and settled on constant gates that barely affect the model's complexity and are easily interpretable. In the following the gates are channel-wise multipliers comparable to the affine transformation that follows layer-normalization:

∀n ∈ [1..N], s n , f n ∈ R d , s n (H n ) = s n H n , f n ( H n-1 + H n ) = f n ( H n-1 + H n ) (3.12)
Dense connections:. Introduced in [START_REF] Huang | Densely Connected Convolutional Networks[END_REF], they change the summations of residual connections to concatenations.

∀n ∈ [1..N], H n = F n [H 0 , H 1 , . . . , H n-1 ] , (3.13)
H conv = [H 1 , H 2 , . . . , H N ] . (3.14)
Figure 3.3 provides a schematic overview of the residual and dense skip connections.

Building Layers

Depending on the skip connection, the layer map F n should be appropriately designed. We will describe in the following the layers used with residual and dense skip connections.

Residual layer. The only constraint on a residual layer is that it yields an output of the same resolution and the same number of features as its input. To mimic a Transformer block where layers alternate between self-attention and position-wise feed forward maps, we follow each convolution with a position-wise feed-forward layer. This design separates the temporal interactions between tokens modeled with the convolutional layer from the position-wise transformations applied to each token independently with the feed-forward network. To strengthen the separation between the temporal interactions and the point-wise transformation, we use a depth-wise separable convolution [START_REF] Chollet | Xception: Deep Learning with Depthwise Separable Convolutions[END_REF]. With that, we first apply a point-wise convolution i.e. using 1-wide filters (or equivalently a position-wise affine map) and follow it with a causal-convolution applied depth-wise. A depth-wise convolution operates on each channel independently mapping them one-to-one instead of the usual summation over channels (see §2.3.1). The depth-wise separable convolution is illustrated in Figure 3.4.

The feed-forward layer, similar to the one in Transformer blocks, is built with two affine maps interleaved with a ReLU non-linearity [START_REF] Nair | Rectified Linear Units Improve Restricted Boltzmann Machines[END_REF]. Ultimately, the maps F n take the form:

F n =    Conv(k y × k x , d → d) • Conv(1 × 1, d → d) if n ≡ 1 (mod 2) Linear(d FF → d) • ReLU • Linear(d → d FF ) if n ≡ 0 (mod 2) (3.15)
Although we define the ConvNet as alternating layers, we will use the same block count as Transformer i.e. N blocks are effectively 2N layers surrounded with residual connections.

Dense layer. Since the feature maps are to be concatenated, each layer is forced to produce a small number of features. We refer to this number of features by the growth rate and denote it with g. Unlike residual-norm skip connections where we normalize the residual sum, it's common in computer vision architectures to normalize the features within the layer map. In this case, F n first normalizes its input then applies ReLU followed by a linear map to R 4g . This map controls the computational cost and memory footprint of the block by reducing the growing number of features to 4g. In fact, with d the number of the ConvNet's input feature maps, the n-th layer receives d+(n-1)g feature maps. A second ReLU • Norm follows, and the last step is the main two-dimensional causal convolution with k y × k x filters.

The composite function Conv • ReLU • Norm used twice (3) within the layer is the residual

(3) the first linear map is equivalent to a point-wise convolution unit proposed in He et al. (2016c) shown to be much easier to train with better generalization.

LN 1 ReLU Linear R d+(n-1)g → R 4g LN 2 ReLU Conv(k × k) R 4g → R g dropout Linear R d → R d Conv(k × k) R d → R d dropout Linear R d → R d FF ReLU Linear R d FF → R d dropout Dense Residual, FF Residual, Conv
Both dense and residual layers are illustrated in Figure 3.5.

On normalization. ConvNets with dense or residual connections were introduced for vision tasks and conventionally used batch-normalization [START_REF] Ioffe | Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift[END_REF]. However, this normalization scheme is not fitting for auto-regressive language modeling so we swap it with layer-normalization [START_REF] Lei Ba | Layer Normalization[END_REF]. Different from the adaptation of layer-normalization in vision architectures (e.g. in [START_REF] Wu | Group Normalization[END_REF]) where it is assumed to normalize across all channels and positions for a given sample (see Figure 3.6b), for Pervasive Attention, we normalize position-wise across channels to prohibit leakage from future positions to past ones

Aggregation for Sequence Prediction

To compute a distribution over the output vocabulary V y , we need to first yield a fixed-size representation for each token in y. However, the ConvNet final features H conv are in R |y|×|x|×d which means that, for every target position, we have to aggregate the |x| R d -vectors into a fixed-size representation. We will denote this output with H out ∈ R |y|×d . Each token y t will be predicted with H out t-1 .

Max-pooling. The simplest aggregation approach is to max-pool the |x| vectors i.e. for every channel k ∈ [1.

.d], we select the most active position:

∀t ∈ [1..|y|], ∀k ∈ [1..d], H out t-1,k = max 1≤j≤|x| H conv t-1,j,k . (3.16)
Average-pooling. Instead of selecting the most active position, we can take the average of the |x| vectors. We scale the average with the inverse square-root of the source length to stabilize the variance of the pooled features:

∀t ∈ [1..|y|], ∀k ∈ [1..d], H out t-1,k = 1 |x| 1≤j≤|x| H conv t-1,j,k .
(3.17)

Self-attention. With average-pooling, all positions contribute equally to the final features.

As an alternative, we can use self-attention to weight the |x| vectors differently:

∀t ∈ [1..|y|], H out t-1 = (H conv t-1 ) softmax H conv t-1 W 1 w 2 , (3.18) with W 1 ∈ R d×d and w 2 ∈ R d .

PERVASIVE ATTENTION MODEL

Gated max-pooling. For a fair comparison with self-attention, we prefix max-pooling with a gated-linear unit to add more weights and a non-linearity:

∀t ∈ [1..|y|], ∀k ∈ [1..d], H out t-1,k = max 1≤j≤|x| GLU(H conv t-1,j,k W), (3.19)
with W ∈ R d×2d and GLU the gated linear unit introduced in §2.6.2.

The aggregated features H out are then transformed to predictions over the output vocabulary V y with a softmax-normalized linear map of weights W p ∈ R |Vy|×d . Thus, the probability distribution for every target token is obtained as:

∀t ∈ [1..|y|], p(y t | y <t , x) = softmax(W p H out t-1 ). (3.20)
To reduce the number of the model's parameters we can tie the weights of the input embeddings E y with those of the final projection W p :

∀t ∈ [1..|y|], p(y t | y <t , x) = softmax(E y H out t-1 ). (3.21)
If the translation task uses shared vocabularies V = V x = V y , a further reduction can be achieved by tying the three matrices E x , E y and W p .

By-product alignments. If we use an attention mechanism to aggregate H conv , we can look at the softmax-normalized attention scores as soft alignments between the source and target sequences:

α tj = softmax H conv t-1 W 1 w 2 j . (3.22)
With average or max-pooling, there are no explicit alignment scores. Nonetheless, in the case of max-pooling, we can leverage the pooled positions to obtain some implicit alignments. In fact, for a given target position i, the max-pooling operator assigns the d channels to different source positions. Let us define a tj as the number of channels that voted for x j being aligned with y t . An implicit alignment between x, y is inferred by normalizing the counts a tj :

a tj = k ∈ [1..d] | j = arg max j∈[1..|x|] (H conv t-1,j,k ) , α tj = a tj |x| j=1 a tj . (3.23) x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 <s> y 1 y 2 y 3 y 4 Hypothesis ( y) p θ (y 1 |y <1 , x) p θ (y 2 |y <2 , x) p θ (y 3 |y <3 , x) p θ (y 4 |y <4 , x)

Inference

To generate a hypothesis y conditioning on the source x we initiate the two-dimensional grid with a single row corresponding to the special token <s>. The ConvNet processes this single row to emit an output distribution p θ (y 1 | y <1 , x) for the next token. The emitted distribution is then used either greedily or with beam-search to select a candidate y 1 and add another row to the grid. We keep packing rows in the grid until the model decides to stop by generating the special token </s>.

If implemented naively, at each decoding step the ConvNet has to process the growing grid from scratch, making the decoding process costly in terms of computation. To alleviate this cost we cache the activations of each causal-convolution and only process the newly decoded input with a cache of the last k y 2 rows. In Figure 3.7, with k y = 5, we retrieve the two cached rows (right panel), to this cache, we add the recent input coming from the preceding map then convolve with the filter (in blue). Once the new convolution output is evaluated, we update the cache.

Model RF Computation Sequential y-path x-path RNN + attention (Luong et al., 2015) ∞ O(Nd

2 |x|+Nd 2 |y|+d|x||y|) O(N(|x|+|y|)) O(|y|) O(1) ConvS2S (Gehring et al., 2017) O(kN) O(Nkd 2 |x|+Nkd 2 |y|+Nd|x||y|) O(N) O(|y|/k) O(1)
Transformer [START_REF] Vaswani | Attention Is All You Need[END_REF])

∞ O Nd|x| 2 +Nd|y| 2 +Nd|x||y| O(N) O(1) O(1) Pervasive Attention O(kN) O(Ndk 2 |x||y|+Nd 2 |x||y|) O(N) O(1) O(1)
Table 3.1: Properties of Pervasive Attention compared to state-of-the-art sequence-to-sequence models.

Sequence-to-sequence properties

We characterized sequence-to-sequence models in §2.7 with a few properties, namely, the receptive-field (RF), the number of sequential steps, the amount of computation performed, and the y-path and x-path defined as the maximum length of the path from a teaching signal to a token in y or a token in x respectively. With N layers in the model and features in R d , Pervasive Attention with k-wide filters has a receptive field of O(kN), N sequential steps from the stacking of layers and constant x-path and y-path due to the residual skip connections.

In terms of computation, Pervasive Attention is more expensive to train because of the term Nd 2 |x||y| induced by the linear projections of the two-dimensional grid.

Experiments

We run our first experiments on the IWSLT'14 De )En dataset [START_REF] Cettolo | Report on the 11th IWSLT evaluation campaign[END_REF] which contains transcripts of TED talks aligned at the sentence level. After ablation experiments, we validate our best models on IWSLT'15 En )Vi (Luong and Manning, 2015) and attempt to scale Pervasive Attention to large benchmarks with experiments on WMT'16 En )Ro (4) and WMT'15 De )En.

(5)

Experimental Setup

IWSLT'14 De )En. We replicate the setup of [START_REF] Edunov | Classical Structured Prediction Losses for Sequence to Sequence Learning[END_REF] and remove sentences longer than 175 words and pairs with length-ratio exceeding 1.5. We train on 160K pairs, develop on 7283 held out pairs and test on TED dev2010+tst2010-2013 (6750 pairs). All data is tokenized and lower-cased using the standard scripts from the Moses toolkit [START_REF] Koehn | Moses: Open Source Toolkit for Statistical Machine Translation[END_REF]. For open-vocabulary translation, we segment sequences using byte pair encoding [START_REF] Sennrich | Neural Machine Translation of Rare Words with Subword Units[END_REF] with 10K merge operations on the merged bi-texts. This results in a

German and English vocabularies of 8.8K and 6.6K types respectively.

IWSLT'15 En )Vi. We use the setup of Luong and Manning (2015). We train on 133K pairs, develop on TED tst2012 (1553 pairs) and test on TED tst2013 (1268 pairs). Apart from tokenizing the corpus, no other preprocessing step was done. The vocabularies are of 17K and 7.7K words in English and Vietnamese respectively.

WMT'16 En )Ro. We use the data provided by [START_REF] Lee | Deterministic Non-Autoregressive Neural Sequence Modeling by Iterative Refinement[END_REF] where we train on 608K pairs, develop on newsdev-2016 (1999 pairs) and report test results on newstest-2016 (1999 pairs). We use a joint source-target vocabulary of 35K BPE types.

WMT'15 De )En. The training data is taken from the Europarl corpus [START_REF] Koehn | Europarl: A parallel Corpus For Statistical Machine Translation[END_REF], the News Commentary [START_REF] Tiedemann | Parallel Data, Tools and Interfaces in OPUS[END_REF] and the Common Crawl corpus [START_REF] Smith | Dirt Cheap Web-Ccale Parallel Text from the Common Crawl[END_REF]. We reproduce the setup of Ma et al. (2019a); [START_REF] Arivazhagan | Monotonic Infinite Lookback Attention for Simultaneous Machine Translation[END_REF] with a joint vocabulary of 32K BPE types. We train on 4.5M pairs, develop on newstest2013 (3000 pairs)

and test on newstest15 (2169 pairs).

We report in Table 3.2 statistics relative to the length of the tokenized bi-texts for all four benchmarks.

Optimization details. To train our models we optimize label-smoothed maximum likelihood [START_REF] Szegedy | Rethinking the Inception Architecture for Computer Vision[END_REF] with a smoothing rate = 0.1. The parameters are updated using Adam (β 1 , β 2 = 0.9, 0.98) with a learning rate that follows an inverse square-root schedule. We train for a total of 50K updates and evaluate with the check-pointed weights 160K (7,19,58) (7,19,56) (0.8,1.0,1.3) Dev 7283 (6,19,59) (7,19,56) (0.8,1.0,1.3) Test 6750 (6,19,54) (6,18,52) (0.7,1.0,1.3) IWSLT'15 En )Vi Train 133K (6,16,47) (7,20,59) (0.9,1.2,1.7) Dev 1553 (6,19,59) (7,19,46) (0.9,1.2,1 hypotheses with length-penalized beam-search and measure the word-level tokenized BLEU score with respect to the references using Moses's multi-bleu.pl . (6) Training and evaluation hyper-parameters of each dataset are detailed in Table 3.3.

IWSLT'14 De )En baselines. We compare the Pervasive Attention models to three WMT'16 En )Ro baselines. We compare to Transformer small (d = 256) and base (d = 512) widely used for this dataset [START_REF] Lee | Deterministic Non-Autoregressive Neural Sequence Modeling by Iterative Refinement[END_REF]Ma et al., 2019b). For both models we use a dropout rate of p drop = 0.2. Since we are using a joint source-target dictionary, we tie the three embedding matrices E x = E y = W p .

WMT'15 De )En baselines. We compare to Transformer base (d = 512). We set the dropout rate to p drop = 0.2. We tie the matrices E x , E y and W p in this benchmark as well.

Ablation Results

In this section we aim to study the effect of four main hyper-parameters: the ConvNet connectivity, the kernel size (k y × k x ), the depth of the model N and the aggregation operator reducing the grid after the ConvNet. To allow ourselves a broad exploration of the hyperparameter space, we only train on pairs shorter than 75 tokens.

Skip connections. First we compare each of the ConvNets to select which is better suited for Pervasive Attention. We train five Pervasive Attention models with N = 14 layers, filters In the results of Table 3.4, aside from residual-norm, dense connections are outperformed by residual connections. One advantage of dense ConvNets is their small number of parameters due to the generation of a few channels per layer. In this experiment, we use a growth-rate of g = 48. Although each block generates only g channels, the inputs grow as we advance in the architecture. The memory bottleneck of the n-th dense layer is the first composite Conv • ReLU • Norm mapping form R d+(n-1)g to constant R 4g . We alleviate the memory cost with gradient checkpointing [START_REF] Chen | Training Deep Nets with Sublinear Memory Cost[END_REF] to the detriment of training speed as we double the forward-pass computational cost. Residual connections without normalization are thus the better choice for their accuracy and their manageable memory consumption. Since residual skip connections, aside from residual-norm, do not normalize their activations, we tried removing the layer-normalizations from the DenseNet as well. However, the performance deteriorates without the normalizations in each dense layer. The results of Table 3.4 also accuracy according to their depths. However, the increase in performance comes at the cost of computation and memory.

Aggregation for sequence prediction. We examine in this section the aggregation method used to reduce the ConvNet's ultimate features, H conv , into fixed-size representations.

We train four Pervasive Attention models with N = 14 layers, filters in R 11×11 and residualcumulative skip connections. In each model we reduce the source dimension differently.

Results in Table 3.5 show that between the two weightless aggregators, max and average pooling, max-pooling the source positions is the better choice. When considering parameterized aggregators, self-attention has a clear advantage in terms of perplexity. Accuracy-wise, gated max-pooling outperforms self-attention.

In the examples of Figure 3.9, the soft alignments explicitly obtained with the softmaxnormalized scores of self-attention have a high entropy. On the opposite side, max-pooling yields low-entropy alignments.

To better assess the quality of the soft alignments, we encode the full development set in teacher forcing mode i.e. we feed the true prefix y <t to predict the next target token similarly to how we measure the perplexity. Afterwards, we evaluate the entropies and coverages of the soft alignments. Whether implicit or explicit, let α tj be the alignment score between y t and x j . For every target token, we evaluate the entropy of the probability distribution α t denoted with H(α t ). To evaluate the alignment's coverage, we measure the total mass assigned to each source position and denote it with C(α, j). These measures are then averaged on the corpus level. A low entropy means the attention mechanism is confident in its consideration of the source positions and a high coverage means that no source position is overlooked.

H(α t ) = - |x| j=1 α tj >0 α tj log(α tj ), H = y |y| t=1 H(α t ) y |y| , (3.24) C(α, j) = min(1, |y| t=1 α tj ), C = x |x| j=1 C(α, j) x |x| . (3.25)
In Table 3.6, we verify that Pervasive Attention (PA) with self-attention has high entropy alignments compared to max-pooling. Self-attention has however a better coverage of the source sequence. For reference, we include in Generating better alignments (low entropy and high coverage) is not a quality we require in a good translation model; the alignment themselves are a by-product we did not optimize.

The Bi-LSTM baseline has better alignments than Transformer but the later improves the decoding accuracy by up to 3 BLEU points (see Table 3.7).

Comparison to State-of-the-art

In this section, we train our Pervasive Attention (PA) models on the full training set of IWSLT'14 DE )En and compare them to the baseline encoder-decoder models in

Analysis and Discussion

To diagnose the strengths and weaknesses of Pervasive Attention, we breakdown the IWSLT'14 De )En test set into buckets according to the reference length (|y|) and length-ratio (|y|/|x|). (a) BLEU score in length buckets <0.6 0.6-0.8 0.8-0.9 0.9-1.0 1.0-1.1 1. The size of each bucket is noted under the bucket label in the x-axis.

In Figure 3.10a, we note that Pervasive Attention is capable of translating both short and long sequences, successfully outperforming all three baselines. It is particularly better than the Transformer baseline in the extremity buckets |y| < 10 and |y| > 60. In Figure 3.10b, we see that Pervasive Attention is worse than three baselines on pairs with |y|/|x| < 0.6.

Pairs in this bucket are usually mistranslated or misaligned (see examples in Table 3.9) and the model generating the shorter hypothesis scores the higher. On average, Bi-LSTM and

Transformer generate shorter hypotheses with a corpus length-ratio (7) of 0.97 compared to the convolutional models with a ratio of 0.99. With two equally bad hypotheses, BLEU score with its brevity penalty will favor shorter ones.

The issue with outlier length-ratios is a plausible explanation for the low performance on WMT'15 De )En, particularly with the noisy ratios in common-crawl (see Table 3.2).

Related Work

The idea of building a 2D grid from parallel sequences is used in different NLP tasks especially for scoring parallel texts. This includes works on semantic matching and paraphrase (7) Evaluated as the total number of generated tokens divided by the total number of reference tokens.

CHAPTER 3. PERVASIVE ATTENTION

Source die beiden rie@@fen mich an . Reference (|y|/|x|=0.57) they called me .

PA (BLEU=34.57) the two of them called me . TF (BLEU=53.73) they called me up .

Source das hat damit zu tun , dass wir zurück@@gehen in das vier@@zehn@@te jahrhundert . Reference (|y|/|x|=0.12) century .

PA (BLEU=10.12) that has to do with the fact that we go back to the four@@th century . TF (BLEU=12.57) that has to do with us going back to the fourth century .

Source wir hatten das vo@@gt -@@zeitalter , wir hab hatten das masch@@in@@en@@zeitalter und wir beschrei@@ten nun das so genan@@nte cyber@@-@@zeitalter . Reference (|y|/|x|=0.31) the question is , what will come next ? PA (BLEU=6.13) we had the vo@@cal age , we 've had the machine age , and we 're now descri@@bing the so-@@called cyber@@-@@age . TF (BLEU=6.43) we had this bird age , we had the machine age , and we now described this called cy@@ber age .

Table 3.9: IWSLT'14 De )En: Misaligned or mistranslated samples with outlier length-ratios from the test set.

identification [START_REF] Hu | Convolutional Neural Network Architectures for Matching Natural Language Sentences[END_REF][START_REF] He | Pairwise Word Interaction Modeling with Deep Neural Networks for Semantic Similarity Measurement[END_REF][START_REF] Wan | A Deep Architecture for Semantic Matching with Multiple Positional Sentence Representations[END_REF][START_REF] Levy | Learning to Align the Source Code to the Compiled Object Code[END_REF].

For semantic matching, [START_REF] Hu | Convolutional Neural Network Architectures for Matching Natural Language Sentences[END_REF] apply 1D convolutions to each sequence separately before a series of 2D convolutions and max-poolings on a grid of the two sequences. The (Zhao et al., 2019a) 35.60 -32K Macaron Transformer [START_REF] Lu | Understanding and Improving Transformer from a Multi-Particle Dynamic System Point of View[END_REF] 35.40 42.8M 6.6K Local joint self-attention [START_REF] José Ar Fonollosa | Joint Source-Target Self Attention with Locality Constraints[END_REF] 35.70 26.8M 31K Join self-attention [START_REF] He | Layer-Wise Coordination between Encoder and Decoder for Neural Machine Translation[END_REF] 35.07 19.1M 31K DynamicConv [START_REF] Wu | Pay Less Attention with Lightweight and Dynamic Convolutions[END_REF] 35.20 35.3M 6.6K LightConv [START_REF] Wu | Pay Less Attention with Lightweight and Dynamic Convolutions[END_REF] 34.80 34.7M 6.6K Varational attention [START_REF] Deng | Latent Alignment and Variational Attention[END_REF] 33

Conclusion

In Chapter 4

Online Neural Machine Translation

In this chapter, we propose a framework for online machine translation where a sequence-to-sequence model alternates between reading the source and writing the target. We build on existing wait-k decoding models [START_REF] Dalvi | Incremental Decoding and Training Methods for Simultaneous Translation in Neural Machine Translation[END_REF]Ma et al., 2019a) and prove them to be a strong baseline that can match state-

Introduction

Sequence-to-Sequence models used in the previous chapters read the entire source sequence

x before decoding the target y. Target tokens are produced one at a time conditioned on the full source and the previously decoded prefix. This type of conditioned generation is dubbed offline decoding. In this chapter we move to online decoding. Online (equivalently simultaneous or real-time) decoding alternates between reading source tokens for context and writing target tokens. This type of decoding is desirable for applications such as real-time speech translation [START_REF] Fügen | Simultaneous Translation of Lectures and Speeches[END_REF] and as-you-type machine translation. In such scenarios, the translation model or the interpreter must emit a translation in the target language while simultaneously listening to or reading and comprehending the source input.

In an offline translation task, models are only evaluated for the quality of their outputs (e.g. with BLEU). Online models, on the other hand, are required to strike a balance between translation quality and latency or delay [START_REF] Mieno | Speed or Accuracy? A Study in Evaluation of Simultaneous Speech Translation[END_REF]. Online decoding with partial contexts is extremely challenging and a lower latency generally means decoding with smaller, insufficient contexts, therefore, outputting low quality translations. Nonetheless, when looking at the attention maps of an offline model, we notice that the decoder is only attending to a subset of the source segments and that an online decoding strategy could be devised without degrading the translation quality. In the example of Figure 4.1, the alignment is only monotonic in the first half but we can easily find an appropriate decoding path that reads the context aligned with the target token before decoding it.

In this chapter, we propose in §4.2 a universal framework for online sequence-to-sequence models with a latent variable z modeling the growing context sizes. We model z with an agent and we distinguish between two variants: deterministic and dynamic. Deterministic agents include the recently proposed wait-k models [START_REF] Dalvi | Incremental Decoding and Training Methods for Simultaneous Translation in Neural Machine Translation[END_REF]Ma et al., 2019a) that first read k tokens from the source then alternate between producing a target token and reading another source token. In contrast to the rigid wait-k decoding paths, dynamic agents are data-adaptive and dynamically switch between reading the source and writing the target. We adapt two offline sequence-to-sequence models for the task of online

A Common Framework for Online Decoding

Let (x, y) be a pair of source-target sequences of respective lengths |x| and |y|. Online decoding consists of executing a sequence of interleaved reading and writing operations, consuming tokens from the source x and producing tokens for the target y. Let z be the sequence of context sizes where z t is the number of source tokens read when decoding y t .

The decoder predicts y t conditioning on the target prefix y <t and the partial source context x ≤zt . We will refer to z as the decoding path. These decoding paths can be represented on a |y| × |x| grid, where we advance from the top left to the bottom right in a total of |x| read steps and |y| write steps (see Figure 4.1).

A translation sequence-to-sequence model with parameters θ will estimate p θ (y | x, z) CHAPTER 4. ONLINE NEURAL MACHINE TRANSLATION and an agent with parameters ϕ will model p ϕ (z | x, y), the likelihood of a decoding path z given the inputs (x, y). The conditional probability p θ (y | x) conventionally modeled by sequence-to-sequence models is now modified to include the variable z with:

p θ (y | x, z) = |y| t=1 p θ (y t | y <t , x ≤zt , z ≤t ).
(4.1)

Let Z be the set of possible decoding paths. To evaluate the likelihood of y given x we simply marginalize the joint probability p θ,ϕ (y, z | x) over Z:

log p θ,ϕ (y | x) = log z∈Z p θ,ϕ (y, z | x). (4.2)
For any choice of a distribution q, we can lower-bound the likelihood with:

log p θ,ϕ (y | x) ≥ LB(x, y, q) (4.3) LB(x, y, q) = log p θ,ϕ (y | x) -D KL (q(z) p ϕ (z | y, x)) (4.4) = H(q) + z q(z) log p θ,ϕ (z, y | x), (4.5)
where D KL is the KL-divergence and H is the entropy. With the Expectation-Maximization (EM) algorithm [START_REF] Dempster | Maximum Likelihood from Incomplete Data via the EM Algorithm[END_REF], we will alternate between computing the lower bound LB in the E-step and maximizing this bound in the M-step. The tightest lower-bound in the E-step is the one minimizing the KL-divergence D KL (q(z) p ϕ (z | y, x)) i.e. we estimate q(z) = p ϕ (z | y, x) given the current model parameters. In the M-step we hold q fixed and solve the following optimization problem:

θ * , ϕ * = arg max θ,ϕ LB(x, y, q) (4.6) = arg max θ,ϕ H(q) + z q(z) log p θ,ϕ (z, y | x). (4.7)
The entropy H(q) being a constant w.r.t. θ and ϕ, we maximize the Q-function or the expected complete data log-likelihood:

Q(x, y, q; θ, ϕ) = z q(z) log p θ,ϕ (y, z | x). (4.8)
To factorize the complete data log-likelihood log p θ,ϕ (y, z | x), we will formulate the decoding path as a sequence of READ/WRITE actions. Each sub-path (t, z t ) → (t+1, z t+1 ) corresponds

SEQUENCE-TO-SEQUENCE MODELS FOR ONLINE DECODING

67

to z t+1z t READs followed by a single WRITE. We will denote with ρ tj the probability of reading another token at position (t, j).

ρ tj = p ϕ (READ | x ≤j , y ≤t ). (4.9)
With these binary decisions along the way, we will estimate the transition probability p ϕ (z t+1 | z t ) and factorize log p ϕ (z | x, y) as:

p ϕ (z t+1 | z t ) = (1 -ρ tz t+1 ) z t+1 -1 l=zt ρ tl [[z t+1 ≥ z t ]],
(4.10)

log p ϕ (z | x, y) = |z|-1 t=1 log (1 -ρ tz t+1 ) z t+1 -1 l=zt ρ tl (4.11) = |z|-1 t=1 log(1 -ρ tz t+1 ) + z t+1 -1 l=zt log ρ tl . (4.12)
Ultimately the complete data log-likelihood is developed as:

log p θ,ϕ (y, z|x) = |y| t=1 log p θ (y t |y <t , x ≤zt , z ≤t ) + |z|-1 t=1 log(1 -ρ tz t+1 )+ z t+1 -1 l=zt log ρ tl . (4.13)
In the following, we will describe how we modify translation models to decode along a path z and estimate the terms p θ (y t | y <t , x ≤zt ). In §4.3.1, we start with Transformer models and by extension any encoder-decoder model with an attention interface, then we move to Pervasive Attention models in §4.3.2.

Sequence-to-Sequence models for Online Decoding

To adapt sequence-to-sequence models for decoding along a path z we need to provide an encoding of the partially read source x ≤zt at every time-step t. We first describe our adaptation of the attention-based Transformer and then our own convolutional Pervasive Attention model.

Attention(S) = (W V S) • softmax 1 √ d h (W K S) (W Q S) , (4.14)
where (W K , W V , W Q ) are the weights of the key, value and query mappings. If we drop the matrix form, then the i-th state is updated as:

Attention(S) i = |x| j=1 α ij W V s j , α ij = softmax(e i ) j , e ij = 1 √ d (W K s j ) (W Q s i ). (4.15)
In bi-directional wait-k models, given z t , the attention energies e ij are modified with the following M zt mask:

α ij = softmax(e i + M zt i ) j , M zt ij =    0, i, j ≤ z t -∞, otherwise. (4.16)
With this masking, the attention weights α ij are zeroed out for any position beyond z t . For the encoder to remain bi-directional every new source token that we read has to be injected in all the past source states. This means that we need to re-encode the source every time we read a new token (see an illustration of the computational graph in Figure 4.2a).

To avoid multiple forward passes for each value of z t , we simply use a uni-directional encoder (see Figure 4.2b). The energy masking to make the encoder uni-directional is similar to how we mask the decoder for auto-regressive generation ( §2.4.3). This mask is independent from the context size z t :

α ij = softmax(e i + M i ) j , M ij =    0, j ≤ i -∞, otherwise.
(4.17) For the task of online translation, the model has to simultaneously read and write. In this paradigm, we argue that the model need not remember the past source tokens that were partially translated. To test this hypothesis, we consider a locally constrained uni-directional encoder. This encoder only attends to the last ∆ tokens instead of the full history:

x 1 x 2 x 3 x 4 x 5 x 6 x 7 x z t = 4 x z t+1 = 5 s 3 (a) Bi-directional online encoder x 1 x 2 x 3 x 4 x 5 x 6 x 7 x z t = 4 x z t+1 = 5 s 3 (b) Uni-directional online encoder
α ij = softmax(e i + M ∆ i ) j , M ∆ ij =    0, i -∆ < j ≤ i -∞, otherwise.
(4.18)

In the decoder side, at every time-step t, the encoder-decoder attention modules are fed the available z t source representations (s 1 , . . . s zt ). With h t-1 the current decoder state at a given block, the attention energies are evaluated as:

∀j ∈ [1..z t ], e tj = 1 √ d (W K s j ) (W Q h t-1 ). (4.19)
With the source signal truncated to x ≤zt in the computational graph of the decoder hidden state h t-1 , we can predict the next token output probability as usual with:

p(y t |y <t , x ≤zt ) = softmax(W p h t-1 ).

(4.20)

Online Pervasive Attention

In Pervasive Attention models, the encoded context is managed with two-dimensional convolutions. We have discussed in §3.2.2 how the filters are masked to stop leakage from source x target y

x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 <s> y 1 y 2 y 3 y 4 y 5 y 6 future target positions. In a similar fashion, we mask the filters in the source direction as well, in order for the encoding to be uni-directional (see Figure 4.3 for an illustration of the bi-directional and uni-directional convolution filters).

W (a) Bi-directional source x target y x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 <s> y 1 y 2 y 3 y 4 y 5 y 6 W (b) Uni-directional
Stacking N convolutions with k × k filters progressively grows the receptive field. In online Pervasive Attention, the ConvNet's ultimate features H conv at a given position (t, j) encode N k/2 source tokens preceding x j and N k/2 target tokens preceding y t . With that, a joint encoding of x ≤zt and y <t can be aggregated from the partial grid H conv <t,≤zt i.e. cells in the top-left of position (t -1, z t ).

Unlike offline Pervasive Attention where we need a single representation per target position, in the online task, we would like to make a prediction at every position where the model would be asked to write. When predicting y t at position (t -1, z t ) of the grid, the straightforward solution would be to make a prediction based on the cell activations H conv t-1,zt (see Figure 4.4a). However, as we did in the offline model, we could consider the activations of all the source history x ≤zt . This amounts to aggregating the positions to the left of (t -1, z t ) i.e. H conv Max-pooling. In this, we simply max-pool the z t vectors i.e. for every channel k ∈ [1.

.d],

we select the most active position:

∀t ∈ [1..|y|], ∀k ∈ [1..d], H out t-1,zt,k = max 1≤j≤zt H conv t-1,j,k . (4.21)
Gated max-pooling. We prefix max-pooling with a gated-linear unit:

∀t ∈ [1..|y|], ∀k ∈ [1..d], H out t-1,zt,k = max 1≤j≤zt GLU(H conv t-1,j,k W), (4.22)
with W ∈ R d×2d and GLU the gated linear unit introduced in §2.6.2.

Self-attention. We can use self-attention to weight the z t vectors of the context:

∀t ∈ [1..|y|], H out t-1,zt = (H conv t-1,≤zt ) softmax H conv t-1,≤zt W 1 w 2 , (4.23) with W 1 ∈ R d×d and w 2 ∈ R d .
The aggregated features H out are then transformed to predictions over the output vocabulary V y with a softmax-normalized linear map of weights W p ∈ R |Vy|×d . The output probability for y t after reading z t source tokens is:

p(y t |y <t , x ≤zt ) = softmax(W p H out t-1,zt ). (4.24)
One major difference between Pervasive Attention and Transformer architectures is that in Pervasive Attention, the output hidden state at a given position (t, z t ) is independent

<s> y 1 y 2 y 3 <s> y 1 y 2 y 3 h 2 s ≤1 s ≤1 s ≤2 s ≤2 s ≤4 s ≤4 <s> y 1 y 2 y 3 h 2 s ≤1 s ≤1 s ≤3 s ≤3 s ≤4 s ≤4 (a) Transformer <s> y 1 y 2 y 3 x 1 x 2 x 3 x 4 h 1 h 1 h 2 h 2 (b) Pervasive Attention Figure 4
.5: Following two different paths leading to (y 3 , z t = 4), the hidden state h 2 used to predict y 3 is dependent on the path with a Transformer decoder (h 2 = h 2 ). With Pervasive Attention, the state at given position is independent from the path leading to it (h 2 = h 2 ).

from the decoding path z. To evaluate the output state H out t,zt , we will always aggregate the row H conv t,≤zt (see Figure 4.5b). In the receptive field of the aggregated area we match the tokens of the target prefix y <t to the tokens of the source context read so far x ≤zt i.e. we implicitly re-encode the prefix y <t to account for the previously unread source tokens. With Transformer we can end up with different states depending on the followed path. This is due to the interleaving of encoder-decoder interaction and self-attention in a stack of N decoder blocks. The encoder-decoder interaction injects a source context into the early decoder hidden states and self-attention updates these contextualized hidden states (see colored edges in

Online Decoding Agents

As introduced in §4.2, an agent estimates the likelihood of a decoding path z by emitting reading probabilities p ϕ (READ | x ≤j , y ≤t ) as we advance in the decoding grid. We will consider two types of agents, deterministic where we follow the same path for any input (x, y), and dynamic where we estimate ρ tj given the available prefixes from x and y. Depending on the agent type, we can decide on the estimation of q in the E-step and simplify the Q-function to train the agent and the underlying translation model. (horizontal) and target (vertical) grid. After reading the first k source tokens, the decoder alternates between reads and writes. In Wait-∞, also called Wait-until-End (WUE), decoding the source is fully read before any write operation.

Deterministic Agents

For our deterministic agents we use wait-k paths [START_REF] Dalvi | Incremental Decoding and Training Methods for Simultaneous Translation in Neural Machine Translation[END_REF]Ma et al., 2019a). We start by reading k source tokens then we alternate between reading and writing a single token at a time, until either the full source has been read, or the target generation has been terminated. The latent variable z wait-k and its associated READ/WRITE decisions for a wait-k path are evaluated as:

∀t ∈ [1..|y|], z wait-k t = clamp [1..|x|] (k + t -1) , (4.25) ∀(t, j) ∈ [1..|y|-1] × [1..|x|-1], ρ tj = p wait-k (READ | x ≤j , y ≤t ) = [[j < z wait-k t ]], (4.26)
where clamp The offline model is recovered with k = ∞ so that we read the full source sequence before decoding.

To train online models with deterministic decoding paths, the EM algorithm is reduced to the M-step where q is the prior distribution on Z:

Q(x, y, q; θ) = E q [log p θ (y | z, x)] . (4.27)
As the prior on Z, we consider either a single wait-k path as in Ma et al. (2019a) or multiple paths.

CHAPTER 4. ONLINE NEURAL MACHINE TRANSLATION

Optimizing a single decoding path. In this setup, we optimize a single wait-k decoding path and so the prior is a Dirac distribution centered on z wait-k i.e. Optimizing along multiple paths. Instead of optimizing a single decoding path, we can jointly optimize multiple deterministic paths. The additional loss terms may provide a richer training signal, and potentially yield models that could perform well in different regimes.

Due to the dependence of the decoder hidden states on the full decoding path z <t in the transformer-based model, it is not possible to improve over simply training in parallel across a limited set of paths. We consider a set of wait-k paths Z = {z wait-k , ∀k ∈ K} and choose a uniform prior over this set:

q(z) = 1 |K| k∈K [[z = z wait-k ]]. (4.29)
During training we encode the source sequence once, and then sample M paths z ∼ q to decode along. Formally we optimize the approximated Q-function:

Q(x, y, q; θ) = E q [log p θ (y | x, z)] ≈ 1 M M m=1 z∼q log p θ (y|x, z). (4.30)
To cover all possible wait-k paths for an input (x, y), we set K to be , we illustrate in the decoding grid the boundary wait-k path and the writing positions above it. Any path in which we write within the grayed area is optimized. In the q tj heatmap, we show the weights q tj evaluated with Eq. (4.35).

diagonal, only Z k remain with (2) :

Z k (|y|, |x|) = |y| + |x| -k |y| - |y| + |x| -k |y| + 1 . (4.31)
The first term enumerates all the paths starting with k READs from which we subtract paths crossing the diagonal of the (|y|, |x|k)-sized matrix counted via the Reflection principle [START_REF] Bertrand | Calcul des Probabilités. Gauthier-Villars. Christian Boitet and Nicolas Nedobejkine[END_REF].

When we develop the Q-function with a uniform prior over Z, the likelihood of decoding y t with z t = j is weighted by q tj , the probability in Z of using this context size.

Q(x, y, q; θ) = 1 |Z| z∈Z log p θ (y | z, x) (4.32) = 1 |Z| |y| t=1 |x| j=1 log p θ (y t |y <t , x ≤j ) z∈Z [[z t = j]] (4.33) = |y| t=1 |x| j=1
q tj log p θ (y t |y <t , x ≤j ).

(4.34)

The context size z t = j corresponds to passing through the edge (t -1, j) ) (t, j). With the constraint of remaining above the k-th diagonal:

q tj = Z k (t -1, j) Z k (|y|, |x|) [[j ≥ z wait-k t ]].
(4.35)

(2) We assume that k < |x| otherwise the only remaining path is wait-until-the-end.

CHAPTER 4. ONLINE NEURAL MACHINE TRANSLATION

Empirically, using this uniform prior over Z leads to small weights assigned to difficult regions of the grid. Such regions include the area near the diagonal where we decode with a smaller context and positions at the beginning of decoding with a short prefix to build on (see the heatmaps of q tj in Figure 4.7). To avoid biasing the training objective, we opted for a binary

q tj = [[j ≥ z wait-k t ]]
to simply select all writing positions in the area of interest. We will refer to this training with z ≥ z wait-k .

Dynamic Agents

Instead of following a pre-determined decoding path, here we adapt the decoding path dynamically to the context read and written so far. Recall that an agent estimates the reading probabilities ρ tj = p ϕ (READ | x ≤j , y ≤t ) across the grid in order to estimate the likelihood of a monotonic decoding path z and that in the M-step of the training, we optimize the Q-function:

Q(x, y, q; θ, ϕ) = E q [log p θ (y | z, x) + log p ϕ (z | y, x)] ,
(4.36)

E q [log p ϕ (z | y, x)] = E q   |z|-1 t=1 log(1 -ρ tz t+1 ) + z t+1 -1 l=zt log ρ tl   . (4.37)
Instead of estimating the posterior p ϕ (z|x, y) in the E-step as outlined in §4.2, here we use an oracle to find the optimal z given (x, y) and choose q(x) = [[z = z ]] to optimize the Q-function. This is similar to the works of Zheng et al. (2019a) and [START_REF] Arthur | Learning Coupled Policies for Simultaneous Machine Translation[END_REF] where an oracle produces READ/WRITE actions to guide the translation model.

Supervising the agent with an Oracle. To find the optimal decoding path z , we devise an oracle that leverages the emissions of the current model p θ (y|x, z). At every position (t, j)

of the decoding grid we estimate the writing and reading costs W tj and R tj respectively:

W tj = -log p θ (y t |y <t , x ≤j ), R tj = λ j |x| (λ ≥ 0). (4.38)
The reading cost R tj is designed to discourage reading the source at once especially when the writing cost at early positions is high.

ONLINE DECODING AGENTS

77

In a forward pass, we estimate the lowest cost of any path leading to a position (t, j) and denote it with -→ C tj . Then, in a backward pass, we estimate the lowest cost of any path from a position (t, j) to the end point (|y|, |x|) and denote it with -→ C tj . Both costs are evaluated recursively as follows:

∀t ∈ [1..|y|], ∀j ∈ [1..|x|], - → C t1 = t ≤t W t 1 , - → C 1j = j ≤j R 1j , (4.39) ∀t ∈ [2..|y|], ∀j ∈ [2..|x|], - → C tj = min - → C t-1,j + W tj , - → C t,j-1 + R tj , (4.40) ∀t ∈ [1..|y|], ∀j ∈ [1..|x|], - → C t|x| = t >t W t |x| , - → C |y|j = j >j R tj , (4.41) ∀t ∈ [1..|y| -1], ∀j ∈ [1..|x| -1], - → C tj = min - → C t+1,j + W t+1,j , - → C t,j+1 + R t,j+1 . (4.42)
To get z , we start from the top-left corner of the grid (t, j) = (1, 1) and advance by picking the next position with the lowest aggregate cost C = -→ C + -→ C i.e. we decide to read if C t,j+1 < C t+1,j otherwise we write.

Our oracle and by extension this dynamic agent is only viable for Pervasive Attention models where we can easily estimate the writing costs across the grid.

Modeling the dynamic agent. To model the reading probabilities ρ tj we use a ConvNet, similarly to Pervasive Attention models, to jointly encode the prefixes x ≤j and y ≤t . The ultimate ConvNet features are then mapped to [0, 1] with a sigmoid-activated affine form.

Once the target z is selected we maximize the Q-function term supervising the agent:

E q [log p ϕ (z | y, x)] = |z|-1 t=1 log(1 -ρ tz t+1 ) + z t+1 -1 l=z t log ρ tl . (4.43)
Initial experiments show that we get better READ/WRITE accuracies if we train the agent to read left of z and write right of z allowing the agent to catch up after surpassing the ideal context i.e. we optimize: In the M-step, we set q tj = 1 in the highlighted blue positions to train the translation model.

|z|-1 t=1 |x| j=1 [[j ≥ z t+1 ]] log(1 -ρ tj ) + [[j < z t+1 ]] log ρ tj . ( 4
When jointly training the agent and the online MT model, updating the MT model's parameters entails that the oracle will also update its estimate of the optimal path z . We found this joint training to be better than freezing the MT model when training the agent.

We also found that training the model to decode right of z leads to better results compared to using q = [[z = z ]] in the decoding objective. All in all, the Q-function takes the form:

Q(x, y, z ; θ, ϕ) = α |y| t=1 |x| j=1 [[j ≥ z t ]] log p θ (y t |y <t , x ≤j ) (4.45) + β |z|-1 t=1 |x| j=1 [[j ≥ z t+1 ]] log(1 -ρ tj ) + [[j < z t+1 ]] log ρ tj , (4.46)
where (α, β) are hyper-parameters balancing the two terms.

Experiments

We first experiment on the IWSLT'14 De↔En [START_REF] Cettolo | Report on the 11th IWSLT evaluation campaign[END_REF] and IWSLT'15 En↔Vi datasets (Luong and Manning, 2015). Then, we scale up to the larger benchmark of WMT'15 De )En.

(3)

Experimental Setup

IWSLT'14 De↔En. We replicate the setup of [START_REF] Edunov | Classical Structured Prediction Losses for Sequence to Sequence Learning[END_REF] and remove sentences longer than 175 words and pairs with length-ratio exceeding 1.5. We train on 160K pairs, develop on 7283 held out pairs and test on TED dev2010+tst2010-2013 (6750 pairs). All data is tokenized and lower-cased using the standard scripts from the Moses toolkit [START_REF] Koehn | Moses: Open Source Toolkit for Statistical Machine Translation[END_REF]. We segment sequences using byte pair encoding with 10K merge operations on the merged bi-texts. This results in a German and English vocabularies of 8.8K and 6.6K types respectively.

IWSLT'15 En↔Vi. We use the setup of Luong and Manning (2015). We train on 133K pairs, develop on TED tst2012 (1553 pairs) and test on TED tst2013 (1268 pairs). Apart from tokenizing the corpus, no other pre-processing step was done. The vocabularies are of 17K and 7.7K words in English and Vietnamese respectively.

WMT'15 De↔En. The training data is taken from the Europarl corpus [START_REF] Koehn | Europarl: A parallel Corpus For Statistical Machine Translation[END_REF], the News Commentary [START_REF] Tiedemann | Parallel Data, Tools and Interfaces in OPUS[END_REF] and the Common Crawl corpus [START_REF] Smith | Dirt Cheap Web-Ccale Parallel Text from the Common Crawl[END_REF]. We reproduce the setup of The hyper-parameters of the trained models in each benchmark are given in Table 4.1.

For offline comparison, we train each model for offline decoding with uni-directional and bi-directional encoding of the source sequence. Each model is decoded greedily and with beam-search (b=5) and we measure case-sensitive (4) tokenized BLEU with multi-bleu.pl (5) after reversing the byte-pair encoding.

We only evaluate with greedy decoding for online models. We measure the translation quality with BLEU and the decoding latency with the three metrics discussed in the following section. Online models trained for wait-k decoding will be evaluated for decoding along wait-k eval with k eval ∈ {1, 3, 5, 7, 9} regardless of the training k.

Latency metrics

We measure the decoding latency with Average Proportion (AP) [START_REF] Cho | Can Neural Machine Translation Do Simultaneous Translation?[END_REF], Average Lagging (AL) (Ma et al., 2019a), and Differentiable Average Lagging (DAL) [START_REF] Cherry | Thinking Slow about Latency Evaluation for Simultaneous Machine Translation[END_REF][START_REF] Arivazhagan | Monotonic Infinite Lookback Attention for Simultaneous Machine Translation[END_REF].

AP [START_REF] Cho | Can Neural Machine Translation Do Simultaneous Translation?[END_REF] measures the decoding latency by averaging the absolute delays of the decoded target tokens. Each target token incurs a delay of z t , the size of the source context it used.

AP(z) = 1 |y| |y| t=1 z t |x| . (4.47)
AP ranges between 0 and 1 where an offline evaluation (wait-∞) reaches AP=1. As noted in previous works [START_REF] Alinejad | Prediction Improves Simultaneous Neural Machine Translation[END_REF]Ma et al., 2019a;[START_REF] Arivazhagan | Monotonic Infinite Lookback Attention for Simultaneous Machine Translation[END_REF], AP is unfavorable to short sequences. With |x| = |y| = n, A wait-1 path has an AP of n+1 2n ranging from 0.75 for n = 2 to 0.5 for n → +∞. Besides this bias to long sequences, AP of the most aggressive wait-k decoding path is higher than 0.5 which means that we will not use half of the AP's range.

(4) except for IWSLT'14 De↔En where the data is lower-cased.

(5) https://github.com/moses-smt/mosesdecoder/blob/master/scripts/generic/multi-bleu.perl 4.5. EXPERIMENTS 81 Ma et al. (2019a) introduced average lagging (AL) that measures the average rate by which the decoding lags behind the ideal simultaneous policy wait-0. AL is designed so that for pairs with equal lengths (|x| = |y|), a wait-k decoding path has an AL of k i.e. lagging k tokens behind the ideal wait-0. For such a pair, AL is evaluated as:

AL = 1 τ (x, z) τ (x,z) t=1 z t -(t -1), τ (x, z) = min{t | z t = |x|} (4.48)
where τ (x, z) is the cut-off step when we finish reading the source x. For the more realistic |x| = |y|, the ideal context size (t-1) is scaled by the length-ratio |x|/|y|, in which case AL takes the form:

AL = 1 τ (x, z) τ (x,z) t=1 z t - |x| |y| (t -1). (4.49)
The summands beyond the cutoff in Eq. (4.49) will decrease the average lagging when they should not, so the straightforward solution is to ignore them completely. And so, AL assumes the tail after the cutoff τ (x, z) is generated instantly without any effect on the delay.

More recently [START_REF] Cherry | Thinking Slow about Latency Evaluation for Simultaneous Machine Translation[END_REF] and [START_REF] Arivazhagan | Monotonic Infinite Lookback Attention for Simultaneous Machine Translation[END_REF] proposed Differentiable Average Lagging (DAL) where they include the lagging terms beyond the cutoff τ .

To avoid artificially decreasing AL, they enforce a minimum delay of |x|/|y| for writing any target token. This minimum delay is accounted for with the modified context sizes z . In this chapter, we will report Average Lagging (AL) for a direct comparison with existing works (Ma et al., 2019a;Zheng et al., 2019a;[START_REF] Arivazhagan | Monotonic Infinite Lookback Attention for Simultaneous Machine Translation[END_REF][START_REF] Ma | Monotonic Multihead Attention[END_REF]

DAL = 1 |y| |y| t=1 z t - |x| |y| (t -1), z t =      z t , if t = 1 max z t , z t-1 + |x| |y| , otherwise.

Offline Models

Table 4.2 reports offline performance of Pervasive Attention (PA) and Transformer (TF) models with both a uni-directional encoder and a bi-directional encoder. Each model is evaluated with greedy decoding then with beam-search. Overall and as expected, bi-directional encoders in the offline setup are better than their uni-directional counterparts. The gain on PA is of 0.65 on average while for the Transformer models (TF) the addition of bi-directionality improves BLEU by 1.1 on average. The first two columns of Table 4.2 show that Pervasive Attention (PA) is very competitive with Transformer (TF) on the small datasets particularly with the uni-directional encoding of the source.

Online Models with Deterministic Agents

Impact of the encoder's receptive field. The offline comparison clearly favors bidirectional encoders. We will verify in this section if the superiority of bi-directional encoders Figure 4.9 shows the effect of the encoder receptive field on the quality of online decoding.

We look at two particular wait-k paths: k = 1 and k = 7. On the extreme case of k = 1 limiting the receptive field helps improve the decoding quality. On the other hand, with k = 7

the unlimited receptive field gives the best BLEU. On both cases however, the bi-directional encoder under-performs. We conclude then that the superiority of bi-directional encoders offline does not carry over to online translation. Furthermore, we argue that limiting the encoder memory makes the task of the wait-k decoders easier, particularly with small k.

In the remainder of this chapter, we use uni-directional encoders for both TF and PA architectures. Other than the uni-directionality of the Transformer encoder, we investigate in Appendix C the importance of the <s> and </s> markers in the online encoding of the source.

Max-pooling Self-attention Gated max-pooling Cell Ablation of Pervasive Attention models. We present in this section an ablation of the aggregation methods for Pervasive Attention models. This study is similar to §3.3.2 except that we focus on the features' aggregation in uni-directional models trained for wait-k decoding. Among the 3 different pool of features we considered (see Figure 4.4), pooling the full grid led to mediocre BLEU scores (less than 10 across all latency regimes) and is thus omitted in the panels of Figure 4.10. In the results of Figure 4.10, predicting with the cell features performed worse than pooling the row of features up to z t . With row-pooling, and unlike with offline models, simple max-pooling outperformed its gated version as well as self-attention, particularly when trained for the difficult wait-1 path. In the following we will default to row max-pooling for Pervasive Attention models. We show in Figure 4.11 the performance of models trained for wait-k decoding across a range of latencies. We observe that for both architectures across the 4 tasks, models trained on wait-7 generalize well on other evaluation paths. Thus, unlike Ma et al. (2019a), we note that we can train a single model to use in different latency regimes i.e. we do not have to use k eval = k to achieve better BLEU scores. This generalization to other wait-k paths is notably stronger with PA models compared to TF models that drop in performance far from the training path (e.g. k = 1 and k eval = 7). Overall, for tasks where PA performs better offline the model consistently outperforms TF online and vice versa.

Joint training on multiple paths. In the previous section, we found that training on a particular wait-k generalizes to all the other paths. To avoid tuning k and finding the optimal path for each dataset, we consider jointly optimizing multiple paths. For TF models we use k ∈ [1..|x|] and for PA z ≥ z wait-1 .

Results in Figure 4.12 show that this joint optimization, for both architectures and on two datasets, manages to achieve comparable results to training on a specific path that we have to manually select.

Experiments on the WMT15 De )En corpus. In Comparison to state-of-the-art. Figure 4.13c compares our results with state-of-the-art performances on WMT 15 De )En. Namely, the deterministic STACL wait-k (Ma et al., 2019a) and the dynamic supervised adaptive policy (SL) Zheng et al. (2019a), MoChA [START_REF] Raffel | Online and Linear-Time Attention by Enforcing Monotonic Alignments[END_REF] and MILk [START_REF] Arivazhagan | Monotonic Infinite Lookback Attention for Simultaneous Machine Translation[END_REF]. The first two models are based on Transformer base while the last two use RNMT+ (Chen et al., 2018), a recurrent architecture. For a fair comparison with RNMT+ based MILk and MoChA, we also train Transformer big, being the most comparable in terms of offline performances to RNMT+.

Our simple uni-directional wait-k model trained on multiple paths establishes a new state of the art for this task, significantly improving over STACL and SL across the full range of latency levels. It also matches the performance of MILk with a single trained model instead of having a different model trained for each latency regime.

Online Models with Dynamic Agents

In this section we train Pervasive Attention models with dynamic agents on IWSLT'14 De↔En and IWSLT'15 En↔Vi datasets. We consider three different pre-trainings or initializations for our dynamic models: translation models trained for offline decoding (k = ∞), models trained for decoding along the z wait-7 path (k = 7) and models trained to jointly optimize paths above the z wait-1 path (z ≥ z wait-1 ). These models are pre-trained for 50K updates (see §4.5.4) before initializing both the dynamic agent and the translation model. We jointly optimize the two branches with α = β = 1 for another 10K updates.

In the results of Figure 4.14, we first assess the quality of the oracle by decoding along its optimal paths z . The paths are estimated given the true target y and the full source

x forwarded in the MT model in teacher-forcing mode (see Algorithm 1). Afterwards, we decode a hypothesis by simply following z as we would with a deterministic path.

Models trained for low-latency (k = 7 and z ≥ z wait-1 in the last two columns of

4:

Decode along z : 5: t = 0, y t = <s>. 6: while y t = </s> do 7: y t = arg max yt p(y t | y <t , x ≤z t ). We use the compare-mt toolkit [START_REF] Neubig | compare-mt: A Tool for Holistic Comparison of Language Generation Systems[END_REF] to compare the outputs of our different systems on the test set of WMT'15 De )En. We look more closely at the following properties: Sentence-BLEU per bucket of difficulty. To measure the difficulty of a pair, we first estimate source-target alignments with fast-align [START_REF] Dyer | A Simple, Fast, and Effective Reparameterization of IBM Model 2[END_REF] and then infer a reference decoding path. The reference decoding path z is non-decreasing and guarantees that at a given decoding position t, z t is larger or equal than all the source positions aligned with t. Concretely, given an alignment map from the target to the source A (i.e. for each t, A(t) is a list of source indices aligned with t), we evaluate z t recursively as:

∀t ∈ [1..|y|], a t = max(A(t)), z 1 = a 1 , ∀t ∈ [2..|y|], z t = max(z t-1 , a t )
The difficulty is finally measured as the Average Lagging (AL) of the reference z.

We measure the average Sentence-BLEU per bucket of difficulty ( online MT struggles to predict its translation and eventually omits it. This method to extract challenging sentences could be used more systematically to identify weaknesses of low latency NMT.

IWSLT'14 De↔En:

In this section, we compare dynamic agents to deterministic wait-7 agents on IWSLT'14 De↔En in increasing levels of difficulty. We pick an operating point of the dynamic agent that achieves a lagging (AL) comparable to a wait-k decoder. For En )De, the dynamic agent is at (BLEU=26.98, AL=5.46) and (BLEU=26.17, AL=3.55) compared to wait-7 at (BLEU=25.41, AL=5.14) and (BLEU=23.15, AL=3.55). For De )En, the dynamic agent is at (BLEU=31.63, AL=4.73) and (BLEU=29.39, AL=2.67) compared to wait-7 at (BLEU=29.62, AL=4.25) and (BLEU=27.08, AL=2.63).

In Figure 4.16, we note that dynamic agents on En )De outperform the offline model across all difficulty ranges. However, on De )En, the dynamic model under-performs in the buckets of difficulty larger than 4. Compared to wait-k, dynamic agents achieve better accuracies across the board. PA-dynamic (AL=1.12) TF wait-7, k eval = 1 (AL=2.63)

(a) Reference: stellen sie sich dann nur zwei andere kleine änder@@ungen vor .

Source

Hypothesis i c a n r e @ @ a r @ @ r a n g e t h e s e q u e n c e w h i l e i t p l a y s . <s> ich kann die sequenz neu auf@@ rei@@ hen , während sie spielt .

Source i c a n r e @ @ a r @ @ r a n g e t h e s e q u e n c e w h i l e i t p l a y s . <s> ich kann mich auf eine neue weise re@@ ar@@ ran@@ gieren , während es spielt .

PA-dynamic (AL=3.40) TF wait-7, k eval = 1 (AL=2.56) (b) Reference: ich kann die sequenz während sie ab@@läuft um@@stellen . @ n a @ @ d o . <s> dro@@ gen@@ krieg . massen@@ ver@@ nicht@@ ung . tor@@ na@@ do .

Source

d r u g w a r . m a s s d e s t r u c t i o n . t o r @ @ n a @ @ d o . <s> dro@@ gen@@ krieg . massen@@ zerstör@@ ung . tor@@ na@@ do .

PA-dynamic (AL=2.04) TF wait-7, k eval = 5 (AL=5.42)

(a) Reference: verschiedene sprecher : dro@@gen@@krieg . massen@@ver@@nicht@@ungs@@waffen . tor@@na@@do . In the examples of Figures 4.17 and 4.18, we can see that compared to the rigid wait-k decoding, the dynamic agent effectively adapts its decoding path to the input. In 4.17a, the word 'imagine' is translated into the 3-words phrase 'stellen sie sich' while the wait-1 decoder is forced to read one more token after each write inflating its delay. In 4.17b, the agent advances to read the object 'sequence' omitted in the wait-1 translation. Similarly in 4.18b, the agent reads a large portion of the source to understand the key component of the sentence i.e. 'doing the job'. With the wait-5, 'doing the job' is mistranslated into 'dass sie das tun' (that they do that). In the example of Figure 4.18a, the agent is segmenting the source and translating a segment at a time. This leads to a considerably lower delay without affecting the translation's quality. Early neural models. One of the first works on online translation to use attention-based sequence-to-sequence models is that of [START_REF] Cho | Can Neural Machine Translation Do Simultaneous Translation?[END_REF], which uses manually designed, non-trainable, waiting criteria that dictate whether the model should READ or WRITE. [START_REF] Jaitly | An Online Sequence-to-Sequence Model Using Partial Conditioning[END_REF] reads equally-sized chunks of the source sequence and generates output sub-sequences of variable lengths, each ending with a special token marking the end of writing.

Related Work

For training, a single segmentation is chosen to optimize the likelihood of the full output CHAPTER 4. ONLINE NEURAL MACHINE TRANSLATION sequence.

Attempts to learn READ/WRITE policies. Another line of research tries to learn a read/write policy for online decoding. Replicating the HMM word alignment model used in statistical machine translation [START_REF] Vogel | HMM-Based Word Alignment in Statistical Translation[END_REF], the segment-to-segment neural transducer model of Yu et al. (2016) integrates a latent alignment variable into an LSTM-based sequenceto-sequence model where the transition probabilities are conditioned on the encoder-decoder hidden states. During training the alignment is marginalized out with a forward-backward algorithm [START_REF] Rabiner | A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition[END_REF]. However, their approach is used as an alternative to attentionbased models, not for low-latency translation. [START_REF] Luo | Learning Online Alignments with Continuous Rewards Policy Gradient[END_REF] introduce a recurrent sequence-to-sequence model with binary stochastic decision variables to either emit next output token or advance in encoding the source sequence with a uni-directional LSTM that jointly encodes the partially generated output sequence. Stochastic decisions are optimized using a standard policy gradient RL approach. Gu et al. (2017b) propose a trainable agent emitting read/write decisions modelled as an RNN fed with the encoder and decoder current hidden states. In their framework, a left-to-right recurrent sequence-to-sequence model is first pre-trained on the full bi-texts and then fine-tuned with policy gradient to optimize a reward balancing translation quality and latency.

Wait-k decoders and their improvements. [START_REF] Dalvi | Incremental Decoding and Training Methods for Simultaneous Translation in Neural Machine Translation[END_REF] used a static decoding algorithm that starts with k read operations then alternates between blocks of l write operations and l read operations. This approach outperforms the information based criteria of [START_REF] Cho | Can Neural Machine Translation Do Simultaneous Translation?[END_REF] and allows complete control of the translation delay. More recently, Ma et al. (2019a) trained a sequence-to-sequence model based on the transformer architecture [START_REF] Vaswani | Attention Is All You Need[END_REF] with an integrated "wait-k" agent that first reads k source tokens then alternate single read-writes, similar to [START_REF] Dalvi | Incremental Decoding and Training Methods for Simultaneous Translation in Neural Machine Translation[END_REF] but using l = 1. Wait-k approaches were found most effective by Zheng et al. (2019a) when trained for the specific k that is used to generate translations. This, however, requires training separate models for each potential value of k used for translation. As an alternative, Zheng et al. (2019b,a) both learn an adaptive policy to produce read/write decisions in a pre-trained offline translation model. State-of-the-art monotonic attention. [START_REF] Raffel | Online and Linear-Time Attention by Enforcing Monotonic Alignments[END_REF] propose an alternative to attention using monotonic alignments. Whereas attention requires access to the full source sequence to compute weights, monotonic alignments enable linear time computation of weights and online decoding. [START_REF] Chiu | Monotonic Chunkwise Attention[END_REF] proposed MoChA that extends monotonic attention so that the decoder attends to a chunk of the encoder states rather than focusing only on the last one. [START_REF] Arivazhagan | Monotonic Infinite Lookback Attention for Simultaneous Machine Translation[END_REF] with MILk opts for an infinite lookback rather than a limited chunk in order to boost the translation quality. Recently, [START_REF] Ma | Monotonic Multihead Attention[END_REF] adapted MILk's monotonic attention for multi-headed Transformer decoders.

Conclusion

In this chapter, we introduced a common framework for online sequence-to-sequence models with the sequence of context sizes z as a latent variable. In the first part, we adapt Transformer and Pervasive Attention models for the task of online decoding by filtering out future source signal. We showed that, unlike in offline translation, uni-directional encoders perform better than bi-directional ones in online translation. Attempts at limiting the size of the past context to a few tokens prove to be helpful for low-latency training regimes (e.g. training wait-1 decoders) with no to little effect on the mid-range delays (e.g. training wait-7 decoders).

With Pervasive Attention models, aggregating the features with max-pooling is especially efficient for training low delays (e.g. wait-1). Overall, we showed that simple wait-k decoding agents can be very effective and match the state-of-the-art dynamic agents such as MoChA and MILk. We also proved that we do not need to train wait-k models for every latency regime as some values of k generalize better in a wide range of laggings. In the second part,

Introduction

We described in §2.6.3 the Transformer model, state-of-the-art in a wide range of NLP tasks [START_REF] Devlin | Bert: Pre-Training of Deep Bidirectional Transformers for Language Understanding[END_REF][START_REF] Yang | XLNet: Generalized Autoregressive Pretraining for Language Understanding[END_REF]Liu et al., 2019b;[START_REF] Ng | Facebook FAIR's WMT19 News Translation Task Submission[END_REF]. Models based on the Transformer architecture can amount to billions of parameters. For instance, the large version of BERT [START_REF] Devlin | Bert: Pre-Training of Deep Bidirectional Transformers for Language Understanding[END_REF] has 24 blocks and 1024-dimensional features with 16 attention heads amounting to 340M parameters. For translation, the winning entry of the WMT'19 news machine translation task in English-German used an ensemble totaling two billion parameters [START_REF] Ng | Facebook FAIR's WMT19 News Translation Task Submission[END_REF]. With these large models, training becomes very expensive in terms of computation and memory usage; not only we need to store the model's parameters but also all of the intermediate activations. This cost is a huge burden both during training and test time. Larger models are more beneficial for hard examples, where the increased complexity usually leads to better results.

However, for easy examples such as translating "Thank you" into "Merci", using these models would be uncalled-for. Current evaluation pipelines for sequence-to-sequence models apply the same amount of computation regardless of whether the input is easy or hard.

In this chapter, we explore Transformer decoders that adapt the amount of computation to each input in order to achieve a satisfying trade-off between speed and accuracy at inference time. We revise the adaptive computation time (ACT) algorithm [START_REF] Graves | Adaptive Computation Time for Recurrent Neural Networks[END_REF], introduced to dynamically halt a computational cycle with recurrent neural networks, in order to adapt the computation in a uni-directional computation graph. Before using ACT, our decoder has to be capable of emitting output distributions at multiple stages of the computation graph.

We will describe in §5.2 the different methods we explored to effectively train a decoder with intermediate classifiers. In §5.3, we will detail the halting mechanisms we investigated to control the amount of computation in the decoder, and outline the training pipeline of these mechanisms. Experiments on IWSLT'14 De )En [START_REF] Cettolo | Report on the 11th IWSLT evaluation campaign[END_REF] as well as WMT'14

ANYTIME STRUCTURED PREDICTION 101

En )Fr translation tasks reported in §5.4 show that we can match the performance of well tuned baseline models at up to 76% less computation. We will end the chapter with an examination of existing work related to ours ( §5.5).

Anytime Structured Prediction

In this section we will address the problem of anytime prediction as it pertains to the design of the model. Algorithms for Anytime prediction, studied in [START_REF] Zilberstein | Using Anytime Algorithms in Intelligent Systems[END_REF], should be capable of emitting a prediction at anytime and should provide increasingly better results

given more computation time with diminishing returns. In order to emit a prediction at any computation stage, the decoder is equipped with auxiliary classifiers and losses at different These conclusions and intuitions are based on convolutional architectures for object recognition and may not translate to sequence modeling with attention-based models. In §5.2.1 we will introduce auxiliary classifiers to the Transformer decoder and outline two

t = 1 n 1 = 3 ? t = 2 n 2 = 2 t = 3 n 3 = 4 ? t = 4 n 2 = 1 t = 5 n 5 = 3 t = 6 n 6 = 2 Depth(n)
Figure 5.2: Missing inputs for self-attention. Hidden states marked with ? were not computed because the model exited earlier. These missing states are required in the computational graph of subsequent steps (blue edges).

to evaluate the increasingly deep sequence of hidden states (h n t ) 1≤n≤N :

h 0 t = Ey t , h n t = block n (h n-1 ≤t , s) (∀n ∈ [1..N]), (5.1)
where block n is the mapping associated with the n-th block and E the target-side embedding matrix. The output distribution for predicting the next token is computed by feeding the activations of the last decoder block h N t into a softmax-normalized output classifier W:

p(y t+1 | h N t ) = softmax(Wh N t ).
(5.2)

In a standard Transformer decoder, an output classifier is attached to the top of the decoder network. However, for anytime prediction, the model needs to be interruptible i.e.

capable of emitting a prediction at different exit points. We place our exit points after each block and attach an output classifier C n parameterized by W n to the output h n t of block n . The N classifiers can be parameterized with independent weights (W n ) 1≤n≤N or we can share these weights across the N blocks.

∀n ∈ [1..N], p(y t+1 | h n t ) = softmax(W n h n t ).
(5.3)

Note that block n requires not only h n-1 t , the output of the previous block at the current time-step t, but all of its past outputs h n-1 <t . These past outputs are required by the selfattention sub-block (see Figure 5.1), with its characteristic dependencies through-time. Such dependencies are present in most sequence models and bring about a particular issue to the design of anytime predictors. If we make a collective decision for the whole sequence, then all of the necessary input at a given time-step is available. However, if we treat each token of the sequence independently when it comes to the exit decision, some inputs will potentially be missing. In the example of Figure 5.2, at each step t the model decides to stop after the n t -th block. The decision to exit after n 2 = 2 in the second step obstructs the computation in the following step at the fourth block. To address the issue of missing inputs, we simply copy the last computed state to all subsequent blocks. These copied features will consequently interact with high-level features in the self-attention sub-block. Note that each self-attention will still apply its own key and value projections to the copied state.

For the model to appropriately handle the misaligned features at test time, we speculate that it must be exposed to such features in training time as well. Thus, we consider two possible ways to train an anytime decoder (see Figure 5.3): Aligned where we simply avoid mixing the states and assume all tokens will exit at the same depth, and mixed where, for each input sequence y, we sample |y| random exit decisions for the model to follow, thus exposing the model to misaligned states.

ANYTIME STRUCTURED PREDICTION

105

Aligned Training

For aligned training, we assume all the hidden states h n-1 1 , . . . , h n-1 t are available so we can properly go through self-attention. In this training mode, we optimize decoding along N constant-depth paths each associated with a classifier C n and a loss term NLL(n) (see Figure 5.3a). The term NLL(n) is the negative log-likelihood of y given x when we always exit after the n-th block:

NLL(n) = - |y| t=1 log p(y t | h n t-1 ) = - |y| t=1 log-softmax(W n h n t-1 ).
(5.4)

We jointly optimize the N paths with a compound loss L dec (x, y) which is a weighted average of N terms w.r.t. to (ω 1 , . . . ω N ) in the N-1-simplex (1) :

L dec (x, y) = N n=1 ω n NLL(n).
(5.5) and for each one we evaluate the negative log-likelihood loss:

Mixed Training

NLL(n 1 , . . . n |y| ) = - |y| t=1 log p(y t | h nt t-1 ) = - |y| t=1 log-softmax(W nt h nt t-1 ).
(5.6) When n t < N, we copy the last evaluated hidden state h n t to the subsequent layers so that the self-attention of future time steps can function as usual (see Figure 5.3b). The optimized loss is an average of the M losses.

L dec (x, y) = 1 M M m=1 NLL n (m) 1 , . . . , n (m) |y| .
(5.7)

(1) The N-1-simplex is defined as h n = block n (h n-1 ).

∆ N-1 = {(ω 1 , . . . , ω N ), N n=1 ω n = 1 ∧ ω n ≥ 0 ∀n} block n ; θ n block n+1 ; θ n+1 block n+2 ; θ n+2 . . . block N ; θ N C n ; W n C n+1 ; W n+1 C n+2 ; W n+2 C N ; W N NLL(n) NLL(n + 1) NLL(n + 2) NLL(N) γ N ∇ NLL(N) γ n+2 ∇ NLL(n + 2) γ n+1 ∇ NLL(n + 1) γ n ∇ NLL(n) ∇ NLL(N) ∇ NLL(n + 2) ∇ NLL(N) ∇ NLL(n + 1) ∇ NLL(n + 2) ∇ NLL(N)
3:

h n = scale_gradient (h n , γ n ). 4: p(y | h n ) = softmax (W n h n ) 5:
Revert gradients flowing from the next block to normal scale.

6:

if n < N then h n = scale_gradient h n , 1 γ n+1 7: end for 8: function scale_gradient(Tensor x, scale γ) 9:

return γx + (1 -γ)stop_gradient(x). 10: end function 11:
stop_gradient in PyTorch by detaching the variable from the graph with x.detach().

Adaptive Depth Estimation

Now that our decoder is equipped with auxiliary classifiers that allow it to be interruptible, we focus on the decision to be made at every exit point, either to continue or to exit. In this work, we consider a variety of mechanisms to predict the decoder block at which the model will stop and output the next token, or when it should exit to achieve a good speed-accuracy trade-off. We consider two approaches: sequence-specific depth decodes all the tokens in y by exiting at the same block ( §5.3.1) while token-specific depth determines an independent exit for each individual token ( §5.3.2).

In both paradigms, we model the distribution of exiting at time-step t with a parametric distribution q t ∈ Q where q t (n) is the probability of forwarding y t up to the n-th block and then emitting a prediction with C n . The parameters of q t are optimized with the supervision of an oracle distribution q * t by minimizing the cross-entropy H(q * t , q t ). At the sequence-level, the following compound loss is optimized:

L exit (x, y) = |y| t=1 H(q * t , q t ) .
(5.9)

Depending on the family of distributions considered Q, the exit loss (L exit ) can be backpropagated to the encoder and or decoder parameters. After pre-training the encoder-decoder model with the auxiliary prediction losses, we optimize L exit jointly with the decoding loss (Eq. (5.5)). The compound loss is balanced with a hyper-parameter α:

L(x, y) = L dec (x, y) + αL exit (x, y), (5.10)

In the following we describe for each approach the family of distributions Q we consider when optimizing L exit (see Figure 5.5) and the supervising oracle q * t .

Sequence-specific Depth

For sequence-specific depth, the exit distribution q ∈ Q and the oracle distribution q * are independent of the time-step so we drop the subscript t. We choose Q as the family of softmax-normalized linear classifiers on the average source hidden states. That is:

s = 1 |x| |x| t=1 s t , q(n | x) = softmax(W q s + b q ), (5.11)
where W q and b q are the weights and biases of the linear classifier. average-pooling, max-pooling and a special-token representation [START_REF] Devlin | Bert: Pre-Training of Deep Bidirectional Transformers for Language Understanding[END_REF] show a slight superiority of the average state. Inference with sequence-specific depth is illustrated in Figure 5.5a.

For q * , we consider two oracles to determine which of the N blocks should be selected for exit. The first is based on the sequence likelihood and the second looks at an aggregate of the correctly predicted tokens at each block. Oracles based on test metrics such as BLEU are feasible but expensive to compute since we would need to decode every training sentence N times. We leave this for future work.

Likelihood-based. For this oracle, we evaluate the likelihoods of the target sequence y

given the source x if decoded with the different predictions emitted at all the exit points.

The exit achieving the highest likelihood (or equivalently log-likelihood) is said to be the ideal exit and q * is simply the discrete distribution represented with the Kronecker delta CHAPTER 5. COST EFFECTIVE DECODING centered on it.

LL(n) = |y| t=1 log p(y t | h n t-1 ), n * (x, y) = arg max n LL(n),
(5.12)

q * (n | x, y) = [[n = n * (x, y)]], (5.13)
where we use the Iverson brackets to represent the delta distribution:

[[n = n * ]] =    1, if n = n * 0, otherwise.
(5.14)

If we assume that we are likely to get better results with increasing depths, then this oracle will, more often than not, settle on the latest exit. Therefore, instead of scoring the exits purely on their accuracies, we add a regularization term to penalize late exits (λ ≥ 0):

n * (x, y) = arg min n (LL(n) -λn) .
(5.15)

Note that q * as an oracle is only used in training time; it requires the full training input (x, y) in order to score the exits.

Correctness-based. In the previous oracle, we relied on the likelihood as a measure of the quality of an exit. However, likelihood ignores how the classifier is sampled during evaluation.

The correct token could be sampled by virtue of being the argmax of the distribution, but the confidence of the model and therefore the likelihood score is low. This is often the case if the model is undecided between synonyms or different word orders.

Instead, in this oracle we score the exits by the number of correct predictions made. For each block, we count the number of correctly predicted tokens over the sequence and choose the block with the most number of correct tokens. If tied, the earliest highest scoring block is selected. Similarly to the previous oracle, a regularization term controls the trade-off between speed and accuracy.

C(n) = {t | y t = arg max yt p( y t | h n t-1 )} , (5.16) n * (x, y) = arg max n C(n) -λn, q * (n | x, y) = [[n = n * (x, y)]].
(5.17)

Token-specific Depth

The token-specific approach can choose a different exit at every time-step. We consider three options for the family of distributions Q. The first is basic confidence thresholding, where after each block a prediction is made with the classifier C n and depending on its quality we decide whether to accept it or wait for a better prediction with deeper features. The second is softmax-normalized linear classifiers on the first decoder hidden state h 1 t . And the third is geometric distributions but with different success rates estimated from the current decoder hidden state h n t . The two last models are dubbed multinomial and geometric-like.

Confidence thresholding. Here, we base our exit policy on the quality of the predictions made at each exit point. The quality of a prediction is assessed through the classifier's confidence i.e. its maximum score

Confidence(n, t) = max y t+1 ∈V p( y t+1 | h n t ).
(5.18)

If the confidence exceeds a pre-determined threshold τ n , we accept the prediction and exit.

With this exit policy, the thresholds τ = (τ 1 , . . . , τ N-1 ) are simply tuned on the development set in order to meet the required accuracy-speed trade-off. Concretely, for a large number of iterations (in the order of 10k), we sample a sequence of thresholds τ ∼ U(0, 1) N-1 and decode the development set with the associated exit policy. We then evaluate the accuracy as a BLEU score and the computational cost of each sampled τ . At the end we pick the best performing thresholds, that is τ with the highest accuracy in various budget ranges.

Multinomial. Similar to the distributions considered for sequence-specific depth, here an affine map with parameters (W q , b q ) projects the first block hidden state to R N , and a softmax operator normalizes the scores into a proper distribution.

q t (n | x, y <t ) = softmax(W q h 1 t + b q ).
(5.19)

The use of h 1 t as a feature for the classifier is justified by the fact that the first block is mandatory; the earliest exit being right after this block.

During inference, the decoder computes it first-level state and the classifier estimates q t , the probability of each exit. The most probable exit n * t = arg max q t (n | x, y <t ) is selected and the decoder continues its forward pass up to n * t before emitting a prediction. This inference is illustrated in Figure 5.5b. Geometric-like. Instead of committing to an exit decision right after the first block, with the geometric-like variant an exit probability is estimated after each block. At time-step t, the n-th exit probability, denoted with χ n t is estimated as an affine transformation of the current decoder hidden state h n t .

∀n ∈ [1..N-1], χ n t = sigmoid(w q h n t +b q ), (5.20)

where w q and b q are parameters of the affine map. χ n t is the chance of successfully exiting right after the n-th block. Similar to a geometric distribution, q t (n) is the probability that the previous n -1 trials fail and the n-th succeeds. That is:

q t (n | x, y <t ) =        χ n t n-1 n =1 (1 -χ n t ), if n < N, N-1 n =1
(1χ n t ), otherwise.

(5.21)

During inference, we advance in the decoder and after each block we estimate the exit probability χ n t . If this exit probability exceeds a pre-determined threshold τ n then an output prediction is made and emitted, otherwise we continue in the decoder network. If no exit decision is made throughout the decoder forward pass then we default to exiting after the integral N blocks. These thresholds τ = (τ 1 , . . . , τ N-1 ) are tuned on the development set to achieve the desired accuracy-speed trade-off.

As with sequence-specific depth, in the case of multinomial and geometric-like exit distributions, a supervising oracle is needed to estimate the parameters of q ∈ Q. We consider two oracles, the first is based on a likelihood score and the second on the correctness count.

Likelihood-based. At each time-step t, we choose the block whose prediction has the highest likelihood. A regularization term is added to penalize late exits (λ ≥ 0): LL(n, t) = log p(y t | h n t-1 ), (5.22)

n * t (x, y) = arg max n LL(n, t) -λn, q * t (n|x, y) = [[n = n * t (x, y)]].
(5.23)

ADAPTIVE DEPTH ESTIMATION

113

As it is, this oracle is myopic, focusing on a single time-step. A decision at time-step t, in particular, could affect later predictions. We therefore consider smoothing the likelihood scores with an RBF kernel. Instead of only looking at future time-steps, we consider a symmetric kernel including past time-steps too.

κ(t, t ) = e -|t-t | 2 σ , LL(n, t) = |y| t =1
κ(t, t ) LL(n, t ).

(5.24)

The size of the surrounding context included in this smoothing is controlled with the kernel width σ. If σ → +∞, we revert to scoring each exit with the sequence-level likelihood used in sequence-specific depth. On the other end of the spectrum, if σ → 0 then we are scoring with the likelihood of the current step. As with other scores, these smoothed likelihoods are regularized and q * is centered on the highest scoring exit. In which case, q * t is evaluated as follows:

C(n, t) = [[y t = arg max yt p( y t | h n t-1 )]],
(5.26) To train adaptive exits models, we first pre-train the encoder-decoder model i.e. α = 0 in the compound loss of Eq. (5.10). The output classifiers are jointly trained under the aligned paradigm (see §5.2.2) for 50K updates. This pre-trained model serves as initialization for all of our adaptive models as we optimize the exit distribution parameters and finetune the encoder-decoder with α = 1. This finetuning stage lasts for another 3K updates.

κ(t, t ) = e -|t-t | 2 σ , C(n, t) = |y| t =1 κ(t, t ) C(n, t), ( 5

Training Multiple Output Classifiers

We first compare the two training regimes for anytime prediction ( §5. .6] independently. To do so, we force all samples to exit at the same point similar to a baseline with exactly n decoder blocks. In the second evaluation criterion, we sample a random exit n ∼ U([1..6]) for every decoded token. Evaluation with sampled

( 2) The equivalent of 78 epochs on IWSLT'14 En )De and 17 epochs on WMT'14 En )Fr.

Uniform n = 1 n = 2 n = 3 n = 4 n = 5 n = 6 Average -34.17 35.27 35.58 35.70 35.55 exits tests the robustness to mixed hidden states and the fixed exit evaluation simulates an ideal setting where all previous states are available.

Baseline

To select the best pre-training strategy for anytime prediction, we compare the models based on their performance on a development set. Table 5.2 shows that aligned training outperforms mixed training both for fixed exits as well as for randomly sampled exits. The latter is surprising since aligned training never exposes the self-attention mechanism to hidden states from other blocks. We suspect that this is due to the residual connections which copy Balancing the losses. With the aligned model, we experiment with different weights for scaling the output classifier losses. Instead of uniform weighting, we bias towards a range of exits, early or late, by assigning higher weights to their losses. Table 5.3 shows that weighing the classifiers equally provides the best performance on average. Adding more weight to the first exit with ω n ∝ n -1 gives the best performance at that exit. In fact unless this early Ablation of hyper-parameters. In this section, we look at the effect of the two main hyper-parameters: λ the regularization scale (see Eq. (5.23)), and the RBF kernel width σ used to smooth the scores (see Eq. (5.24)). We train Tok-LL Geometric-like models and evaluate them with thresholds τ n defaulting to 0.5 i.e. we exit if χ n t exceeds the half-way point 0.5. Figure 5.7a shows that higher values of λ naturally lead to lower exits. Figure 5.7b shows the effect of σ for two values of λ. In both curves, we see that with wide kernels i.e. coarse scores close to the sequence-level, late exits are favored. 42.20 42.64 43.11 43.22 43.23 43.41 42.97 Aligned 41.42 42.76 43.17 43.23 43.60 43.62 42.97

Table 5.6: WMT'14 En )Fr test set: BLEU scores of N independent standard transformers and the anytime prediction model. it would be in@@ toler@@ able . (a) Src: es wäre uner@@trä@@glich .

Scaling the Adaptive-depth Models

< /s>

Ref: i couldn 't bear it . you can zo@@ om in very easily and zo@@ om out . < /s> (b) Src: man kann sehr leicht rein und raus@@zo@@omen .

Ref: you can zo@@om around very simply . (c) Src: diesen trick können sie ihren freunden und nachbarn vor@@führen . danke .

Ref: there is a trick you can do for your friends and neighb@@ors . thanks . (a) Src: Chi@@rac , the Prime Minister , was there .

Ref: Chi@@rac , Premier ministre , est là .

Qualitative Results

Besides the advantageous accuracy-speed trade-offs we can attain with adaptive-depth estimation, the exits distribution for a given sample can give an insight into what a Transformer decoder considers to be a difficult task. In this section, for each hypothesis y, we will look at the sequence of selected exits (n 1 , . . . , n | y| ) and the probability scores (p 1 , . . . p | y| ) with p t = p( y t |h nt t-1 ) i.e. the confidence of the model in the sampled token at the estimated exit. Figures 5.9 and 5.10 show a few hypotheses from IWSLT'14 De )En and the WMT'14 En )Fr test sets, respectively. For each hypothesis we state the exits and the probability scores.

In Figure 5.10a, predicting 'présent' (meaning 'present') is hard. A straightforward translation is 'était là' but the model chooses 'present' which is also appropriate. In Figure 5.10c, the model uses more computation to predict the definite article 'les' since the source has omitted the article for 'passengers'. ) and near the end (rpos>0.9) of the hypotheses of three models.

1 2 3 4 5 6 0.0-0.1 0.1-0.2 0.2-0.3 0.3-0.4 0.4-0.5 0.5-0.6 0.6-0.7 0.7-0.8 0.8-0.9 0.9-1.0 Confidence 1 2 3 4 5 6 Exit 1 2 3 4 5 6

Model 1 Model 2 Model 3

Figure 5.12: WMT'14 En )Fr test set: joint histogram of the exits and the confidence scores for three models.

RELATED WORK

125

A clear trend in both benchmarks is that the model requires less computation near the end of decoding to generate the end of sequence marker </s> and the preceding full-stop when relevant. In Figure 5.11, we show the distribution of the exits at the beginning and near the end of test set hypotheses. We consider the beginning of a sequence to be the first 10% of its tokens and the end its last 10%. The exit distributions are shown for three models on WMT'14 En )Fr. Model 1 has an average exit of AE = 2.53, Model 2 exits at AE = 3.79 on average and Model 3 with AE = 4.68. Within the same models, deep exits are used at the beginning of the sequence and early exits are selected near the end. For heavily regularized models such as Model 1 with AE = 2.53, the disparity between beginning and end is less severe as the model exits early most of the time. We also observe a correlation between the model's probability scores and the amount of computation, particularly in low-cost models.

We show in Figure 5.12, for the aforementioned three models, the joint histogram of the scores and the selected exit. In both Model At the sequence level, we look at the correlation between the model's confidence evaluated as the average score 1 | y| t p t and the chosen exit in Figure 5.13b. We observe a similar behavior to token-specific exits where a higher confidence is associated with an early exit.

We also note a correlation between the source sequence length (|x|) and the chosen exit. In the joint histogram of Figure 5.13a, longer sequences exit late in the decoder and short ,easy, sequences exit earlier.

Related Work

Anytime prediction is less common in natural language processing. Until recently with the surge of pre-trained Transformer-based language representations [START_REF] Devlin | Bert: Pre-Training of Deep Bidirectional Transformers for Language Understanding[END_REF][START_REF] Radford | Language Models are Unsupervised Multitask Learners[END_REF][START_REF] Yang | XLNet: Generalized Autoregressive Pretraining for Language Understanding[END_REF], NLP architectures were tiny in comparison to computer vision networks. Consequently, there was little interest in slicing the models to improve inference speed. To our knowledge, the only existing work in adaptive computation for structured prediction is the ACT algorithm [START_REF] Graves | Adaptive Computation Time for Recurrent Neural Networks[END_REF]. ACT builds off of boosting techniques [START_REF] Schapire | The Boosting Approach to Machine Learning: An Overview[END_REF][START_REF] Grubb | Speedboost: Anytime Prediction with /niform Near-Optimality[END_REF] and estimates for an input the amount of iterations the same RNN cell need to be re-applied. Recently, Universal Transformers [START_REF] Dehghani | Universal Transformers[END_REF] used ACT to control the iterative application of a single Transformer block. [START_REF] Dehghani | Universal Transformers[END_REF] did only estimate dynamic amount of computation for language modeling tasks and fixed the number of iterations for large-scale machine translation. Besides, in their machine translation experiments, they used a wider block i.e. large embeddings and classifiers in order to pack as many weights as an entire standard Transformer in a single block.

In our work we do not increase the size of individual layers and tie the auxiliary classifiers in the large WMT'14 En )Fr benchmark, so that the number of parameters remains unchanged.

Our work considers a variety of mechanisms to estimate the depth or amount of computation needed on a sample basis.

In computer vision literature, different depth estimation methods were proposed. [START_REF] Huang | Multi-scale Dense Convolutional Networks for Efficient Prediction[END_REF] consider two evaluation setups. The first in anytime prediction where a finite computational budget B is available for each test example. The sample is forwarded through the network until the budget is depleted and the most recent prediction is emitted. The second is budgeted batch classification with a budget B allocated for a set of samples D.

In this scenario a test sample traverses the network and exits after the n-th classifier if its 5.5. RELATED WORK 127 confidence exceeds a pre-determined threshold. The confidence of a classifier is measured as the maximum value of its output distribution. To determine the thresholds, [START_REF] Huang | Multi-scale Dense Convolutional Networks for Efficient Prediction[END_REF] assumes that a sample will exit at any given point n with a fixed probability across all exit points denoted with q ∈ [0, 1]. This means that the n-th exit point will process a sample with a probability q n = 1 Z (1q) n-1 q, where Z is a normalizing constant. With cost n denoting the cost of processing an input up to the n-th classifier, the estimated budget of classifying all the samples in D

is |D| E qn [cost n ]. q is determined by solving |D| E qn [cost n ] ≤ B
and the thresholds are approximated on a development set so that the exit probability q is met. A similar approach is used in BranchyNet [START_REF] Surat Teerapittayanon | Branchynet: Fast Inference via Early Exiting from Deep Neural Networks[END_REF] where the prediction confidence is measured with the entropy of the output distribution instead. The thresholds are tuned to select a satisfying accuracy-speed trade-off. This is similar to our confidence thresholding model where the tuning was also based on the resulting trade-off between accuracy and speed. This approach turns out to be extremely expensive in the case of large output spaces. [START_REF] Bolukbasi | Adaptive Neural Networks for Efficient Inference[END_REF] train decision functions to minimize the prediction time under a tolerated classification error margin. The n-th decision function takes as input the network's features by the n-th exit point as well as the entropy of the prediction. These decision functions are trained iteratively starting from the deepest one.

The previously mentioned ACT [START_REF] Graves | Adaptive Computation Time for Recurrent Neural Networks[END_REF] trains a halting mechanism in order to break form a loop of iterative updates with an RNN cell. With each update, the halting signal is accumulated and once it exceeds a fixed threshold 1-, a prediction is emitted.

The halting signal is an affine projection of the current feature followed by a sigmoid nonlinearity. If χ n is the signal evaluated after the n-th iteration, then the prediction cost is min{n | n n=1 χ n ≤ 1 -}. The RNN and the halting module parameters are jointly trained in order to minimize the decoding loss plus a regularization term Ω = 1 -cost n=1 χ n . Our geometric-like distribution is more intuitive than accumulating halting signals as we can interpret each term as an exit probability. Our supervision with an oracle allows us to effectively train these kinds of exit distributions.

Conclusion

In this chapter we presented our work on anytime structured prediction. We introduced simple but effective methods to render sequence models capable of making predictions at different points in the network. We compared two different training paradigms to address the potential issues of misaligned states in self-attention and established that Transformer models are robust to mixed-level features. We studied in the second part a number of different mechanisms to predict the required network depth and found that a well tuned geometric-like estimation of the exit on a token basis, obtains the best trade-off between speed and accuracy.

Our Results show that the number of decoder layers can be reduced by more than three quarters at no loss in accuracy compared to a well tuned Transformer baseline.

Chapter 6 Conclusion

In this dissertation, we develop alternative methods for Neural Machine Translation (NMT) questioning the prevalent paradigm in state-of-the-art sequence-to-sequence models. We reconsider the source-target interaction in the encoding pipeline of NMT systems and build a framework for online NMT where the model alternates between reading and writing.

Asides from the source-target interaction, we explore the trade-off between the translation's computational cost and its quality and introduce an efficient NMT model with anytimeprediction capabilities. We will conclude this thesis with a summary of our contributions ( §6.1) and a discussion of the remaining challenges and open directions of inquiry ( §6.2).

Summary

Chapter 3: Pervasive Attention. We revised the shallow attention modules in encoderdecoder models and introduced Pervasive Attention, a sequence-to-sequence model that jointly encodes the source and target sequences with a two-dimensional ConvNet. Pervasive Attention enhances the interaction between the source and target sequences by letting the encoding of one sequence affect the other. We proposed different design choices pertaining to the interconnectivity of the main two-dimensional convolutions and found that accumulating features from different levels of abstraction helps. We also established that slowly growing the receptive field with 5 × 5 kernels achieves better results than abruptly integrating the full context with wide filters. To deal with the generative aspect of Pervasive Attention, we explored different methods to aggregate the ConvNet's features into fixed-size representations and studied their effect on the translation's quality as well as the source-target alignments inferred from the grid. We finally established that the quality of our model's translations on small to midsize benchmarks is competitive with state-of-the-art encoder-decoder models.

Chapter 4: Online Neural Machine Translation. In the context of online machine translation, the model is equipped with an agent to decide whether to read from the source or write to the target and is judged by both the quality and lagging of its translations.

We proposed a framework for modeling and training online NMT systems with either deterministic or dynamic decoding agents. We adapted Transformer models for online decoding and highlighted the finding that "what works best for the offline task is not guaranteed to work as well online", in particular, encoding the source context in a unidirectional or bi-directional manner. We studied the deterministic wait-k decoding models, especially their ability to operate outside the range of delays they were optimized for, and the potential of training a multitasking wait-k agent well tuned for a variety of laggings.

We also introduced dynamic decoding agents that leverage the interaction grid of Pervasive Attention models. These agents were jointly trained with the underlying NMT model and were supervised with a likelihood-based oracle using dynamic programming to estimate the optimal decoding path. We proved deterministic wait-k agents to be a strong baseline in online translation, moreover, we were able to match the quality of offline models on a few NMT benchmarks with 70% less lagging with our dynamic Pervasive Attention agents. We demonstrated the disposition of Pervasive Attention models to the task of online translation thanks to its grid of features akin to a decoding grid.

Chapter 5: Cost-effective Decoding. We tackled the problem of anytime structured prediction with Transformer models that adapt the amount of computation to each input in order to achieve a trade-off between speed or computational cost and accuracy. We first equipped our decoders with the capability of emitting output distributions at multiple stages of decoding then compared two different training paradigms, mixed and aligned, to address the potential issues of misaligned states in self-attention. We established that Transformer models are robust to mixed-level features so that we can copy low-level activations to subsequent blocks without hindering the output's quality. We proposed a number of halting mechanisms to predict the required network depth and found that estimating the exit on a token basis with a geometric-like distribution updated after each block, obtains the best trade-off between speed and accuracy. Experiments on translation benchmarks of different scales show that we can effectively match the performance of baseline models with less than 76% of the computation.

Future work

In our attempt to answer our research questions just as many new questions arose. We discuss in the following some future perspectives and open questions based on the work presented in this thesis.

Analysis and interpretability A valid criticism of NMT, and by extension most of the inference processes based on deep learning techniques, is their lack of transparency. These processes are described as a black box i.e. we can observe feature activation but we cannot understand the actual phenomenon behind it. Methods for interpreting and visualizing neural models are explored much more in vision [START_REF] Szegedy | Intriguing Properties of Neural Networks[END_REF][START_REF] Simonyan | Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps[END_REF][START_REF] Matthew | Visualizing and Understanding Convolutional Networks[END_REF][START_REF] Mahendran | Understanding Deep Image Representations by Inverting Them[END_REF][START_REF] Bau | Network Dissection: Quantifying Interpretability of Deep Visual Representations[END_REF] than in NLP. These visualization techniques consist mainly in finding inputs that maximize the activation of a neuron in order to capture humanly interpretable information about the neuron's role and how it might contribute to the final decision. Recently, the question of analyzing and interpreting NLP models has gained traction with the BlackboxNLP workshop [START_REF] Tal Linzen | Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP[END_REF](Linzen et al., , 2019)). One popular method of analysis consists of evaluating the quality of the features learned by an NMT model in other NLP tasks [START_REF] Shi | Does String-Based Neural MT Learn Source Syntax?[END_REF][START_REF] Hill | The Representational Geometry of Word Meanings Acquired by Neural Machine Translation Models[END_REF][START_REF] Adi | Fine-Grained Analysis of Sentence Embeddings Using Auxiliary Prediction Tasks[END_REF][START_REF] Belinkov | Evaluating Layers of Representation in Neural Machine Translation on Part-of-Speech and Semantic Tagging Tasks[END_REF][START_REF] Raganato | An Analysis of Encoder Representations in Transformer-Based Machine Translation[END_REF]. Although this method has its merits, it does not allow us to know more about the inner workings of the model and how the information flows in the computational graph up until outputting the final decision. Another prominent research direction is to assess the quality of the attention mechanism in a encoder-decoder model [START_REF] Tang | An Analysis of Attention Mechanisms: The Case of Word Sense Disambiguation in Neural Machine Translation[END_REF][START_REF] Jain | Attention is not Explanation[END_REF][START_REF] Marcely Zanon Boito | Empirical Evaluation of Sequence-to-Sequence Models for Word Discovery in Low-resource Settings[END_REF][START_REF] Voita | Analyzing Multi-Head Self-Attention: Specialized Heads Do the Heavy Lifting, the Rest Can Be Pruned[END_REF][START_REF] Vig | Analyzing the Structure of Attention in a Transformer Language Model[END_REF]. Conclusions on the interpretability of attention weights were contradictory and varied from one task to the other depending on the importance of the attention to the model's prediction [START_REF] Vashishth | Attention Interpretability Across NLP Tasks[END_REF] and how it was trained [START_REF] Pruthi | Learning to Deceive with Attention-Based Explanations[END_REF].

Other works go beyond the attention mechanism and provide a breakdown of the input's contribution (source and target) in each decoding step [START_REF] Shen | Relay Backpropagation for Effective Learning of Deep Convolutional Neural Networks[END_REF][START_REF] Ding | Visualizing and Understanding Neural Machine Translation[END_REF] and more broadly a quantification of the interaction between different neurons in the trained model [START_REF] Dalvi | What is One Grain of Sand in the Desert? Analyzing Individual Neurons in Deep NLP Models[END_REF][START_REF] Bau | Identifying and Controlling Important Neurons in Neural Machine Translation[END_REF][START_REF] Li | Neuron Interaction Based Representation Composition for Neural Machine Translation[END_REF].

These methods of post-hoc interpretability [START_REF] Montavon | Methods for Interpreting and Understanding Deep Neural Networks[END_REF] [START_REF] Zoph | Neural Architecture Search with Reinforcement Learning[END_REF][START_REF] Baker | Designing Neural Network Architectures Using Reinforcement Learning[END_REF][START_REF] Peter | Efficient Architecture Search by Network Transformation[END_REF] or evolutionary algorithms [START_REF] Real | Large-Scale Evolution of Image Classifiers[END_REF][START_REF] Liu | Progressive Neural Architecture Search[END_REF][START_REF] Pham | Efficient Neural Architecture Search via Parameter Sharing[END_REF][START_REF] Brock | Smash: One-Shot Model Architecture Search through Hypernetworks[END_REF][START_REF] Real | Regularized Evolution for Image Classifier Architecture Search[END_REF]Liu et al., 2019a) to automate the process of architecture design. Most of these works focus on computer vision tasks and are limited in NLP to the search of the optimal recurrent cell for language modeling [START_REF] Zoph | Neural Architecture Search with Reinforcement Learning[END_REF][START_REF] Pham | Efficient Neural Architecture Search via Parameter Sharing[END_REF]. We posit that NAS is a viable framework for finding more than recurrent cells in NLP. In the context of NMT, pairing NAS with a graph view of the source-target sequences and a clear-cut separation between position-based context (e.g. with convolution) and content-based context(e.g. with self-attention) can help us find better interpretable models for the source-source, target-target and source-target interactions. Besides the aforementioned interaction of tokens, this argument holds for other aspects addressed in this thesis, namely, the depth or level of abstraction appropriate for generation and the ideal context size in online NMT.

Unordered decoding In this thesis, and like other conventional sequence-to-sequence models, we generate target tokens auto-regressively i.e. step by step conditioning the generation on the history. This sequential decoding inhibits the parallelization of inference in convolutional and attention-based models. Recent works propose non-autoregressive decoding by iteratively refining a sequence of target tokens (Gu et al., 2017a;[START_REF] Lee | Deterministic Non-Autoregressive Neural Sequence Modeling by Iterative Refinement[END_REF]. These methods, although fast, produce low-quality translations and require explicit length modeling that remains fixed throughout the refinement process. A new research direction on the rise is insertion-deletion based decoding that allows for flexible generation orders and partially parallel inference without diminishing the translation's quality [START_REF] Stern | Insertion Transformer: Flexible Sequence Generation via Insertion Operations[END_REF][START_REF] Welleck | Non-Monotonic sequential Text Generation[END_REF]Gu et al., 2019b,a;[START_REF] Emelianenko | Sequence Modeling with Unconstrained Generation Order[END_REF][START_REF] Ruis | Insertion-Deletion Transformer[END_REF]. In the context of online machine translation, allowing the decoder to write without order restrictions will most likely mitigate the issues of duplication and omission that occurs when the decoder is asked to write with insufficient context. With that, the evaluation metrics of translation lagging (AP, AL and DAL) need to accommodate insertions and deletions to fairly measure the delay of refined translations. This will also allow for beam-search decoding in Online MT where the partially outputted candidate might be substituted with a more likely translation in the beam.

Speech recognition and speech translation Another future direction is to validate

Pervasive Attention models on other sequence transduction tasks, in particular automatic speech recognition (ASR). Similar to MT, sequence-to-sequence models with attention mechanisms have proven their worth in ASR with recurrent [START_REF] Bahdanau | End-to-End Attention-Based Large Vocabulary Speech Recognition[END_REF][START_REF] Chan | Listen, Attend and Spell: A neural Network for Large Vocabulary Conversational Speech Recognition[END_REF], convolutional [START_REF] Sercu | Very Deep Multilingual Convolutional Neural Networks for LVCSR[END_REF][START_REF] Zhang | Very Deep Convolutional Networks for End-to-End Speech Recognition[END_REF] and Transformer-based architectures [START_REF] Sperber | Self-Attentional Acoustic Models[END_REF][START_REF] Salazar | Self-Attention Networks for Connectionist Temporal Classification in Speech Recognition[END_REF][START_REF] Mohamed | Transformers with Convolutional Context for ASR[END_REF]. We expect the monotonically aligned ASR data to be an appropriate fit for Pervasive Attention.

Another task to consider is end-to-end automatic speech translation (AST) [START_REF] Bérard | End-to-End Automatic Speech Translation of Audiobooks[END_REF][START_REF] Weiss | Sequenceto-Sequence Models Can Directly Translate Foreign Speech[END_REF] where models with strong segmentation and alignment capabilities are a plus. We also experimented with prefixing the source with <s> allowing the decoder to not read any source token. When attending to <s>, its hidden state does not carry any information about the source sequence and the decoder hidden state will only encode the target decoded so far. Similarly, we add an artificial key-value pair to the source hidden states in the encoder-decoder attention mechanism. This artificial pair has a constant key and a zero value.

If picked, this pair similar to the <s>token, does not include any source information and allow the decoder to skip the attention over the source tokens. We denote this setup with add-zero.

The results in Figure C.2 show a considerable improvement (up to 1.5 BLEU points) with either options over the default encoding, particularly for k = 1. We argue that allowing the model to skip attending over the source in online translation is helpful when the source token aligned with the target token is not yet read. In chapter 4, we keep the source encoding in its default format (only </s>).

Appendix D Online Neural Machine Translation: Numerical Results

We provide in this appendix detailed results of the experiments in Chapter 4. laries, and a lazy evaluation method that significantly speeds up training. c) We experimentally validate our approach on the MSCOCO image captioning task and the WMT'14 English to French machine translation task, showing that on both tasks combining token-level and sequence-level loss smoothing improves results significantly over maximum likelihood baselines.

In the remainder of this chapter, we present our token-level and sequence-level approaches in §E.2. Experimental evaluation results based on image captioning and machine translation tasks with recurrent language models are laid out in §E.3. We end the chapter with a review of existing methods related to our work ( §E.4).

E.2 Loss Smoothing for Language Models

Let us recall that a conditional language model estimates the probability of an output sequence y given an input x, p(y | x) factorized as:

  of Sequence-to-Sequence Models for Efficient Machine Translation In recent years, deep learning has enabled impressive achievements in Machine Translation.

1

  The all-ones vector a i i-th element of the vector a a Transpose of the vector a

Figure 1 . 1 :

 11 Figure 1.1: Schematization of MT systems with the Vauquois triangle[START_REF] Vauquois | Syntaxe et Interprétation[END_REF]

  Figure 1.2: A schematization of our view of NMT systems

  (c) For the last point, we introduce depth-adaptive NMT systems based on the Transformer model (Chapter 5). We present simple yet effective methods to have MT models capable of generating output tokens at different stages of decoding. and propose a variety of halting mechanisms to determine the amount of computation required by each input. This work was done during an internship at Facebook AI research (Menlo Park, CA) hosted by Michael Auli.

Figure 2

 2 Figure 2.1: Visualisation of the attention weights α tj for a German to English translation.

  Figure 2.2: Gated linear unit (GLU).

Figure 2 . 4 :

 24 Figure2.4: The receptive-field growth in sequence models: for a select position, we highlight the receptive-field at the input level and the paths leading to it.

Figure 3 . 1 :

 31 Figure 3.1: Overview of the Pervasive Attention model.

W

  Figure 3.2: Illustration of a causal two-dimensional convolution with filter W ∈ R 5×5 . At the position marked with •, the convolution only includes signals from the highlighted blue area. The rest of W is zeroed out. The gray positions are zero-paddings to maintain the input resolution; with k x = k y = 5 the grid is padded twice on each side.

Figure 3 . 3 :

 33 Figure 3.3: Skip connections for Pervasive Attention. Each ConvNet is illustrated with N = 3 blocks.

  Figure 3.4: Depth-wise separable convolution.

Figure 3 . 5 :

 35 Figure3.5: Layers for Pervasive Attention: Residual and dense layers. For regularization, each map is followed with a dropout mask.

(Figure 3

 3 Figure 3.6: Normalization schemes for Pervasive Attention.

Figure 3

 3 Figure 3.7: Decoding with Pervasive Attention. The left-hand panel shows the stacking of rows in the grid after every new target token. The right-hand panel illustrates the caching of activations in every two-dimensional convolution.

( 6 )

 6 https://github.com/moses-smt/mosesdecoder/blob/master/scripts/generic/multi-bleu.perl CHAPTER 3. PERVASIVE ATTENTION baseline encoder-decoder models: Bi-LSTM, ConvS2S and Transformer. For a fair assessment of the different architectures, we fix a few design choices. Namely, we use input embeddings of size d = 256 (both source and target) and tie the target embeddings E y with the pre-softmax projection weights W p . After a limited search of the hyper-parameters' space, focused mainly on the depth, the kernel width and the number of attention heads when relevant, we selected the following baselines:-Bi-LSTM: Two layers in the encoder and decoder with a dropout rate p drop = 0.3.-ConvS2S: 16-layers encoder and decoder with 3-wide filters and p drop = 0.3.-Transformer small : Encoder and decoder with N = 6 blocks, n H = 4 attention heads, feed-forward network with d FF = 1024 and a dropout rate p drop = 0.3.IWSLT'15 En )Vi baselines. We compare to Transformer small (d = 256, p drop = 0.2) and Transformer base (d = 512, p drop = 0.3). We use a smaller d FF for the base model (1024 instead of 2048) following the setup of[START_REF] Ma | Monotonic Multihead Attention[END_REF]. With large d FF the model overfits the small dataset. We tie the decoder matrices E y and W p in both baselines.

Figure 3

 3 Figure 3.8: IWSLT'14 De )En development set: accuracies (beam-search decoding) with varying kernel widths k and depths N. Each marker is annotated wit the size of the target-side receptive field.

Figure 3

 3 Figure 3.9: IWSLT'14 De )En development set: Examples of alignments generated by Pervasive attention with self-attention, max-pooling and gated max-pooling aggregators. We include for reference the alignments of the Bi-LSTM and Transformer (last block) baselines.

  convolutions are then followed by a feed-forward network to estimate the matching score.They interestingly highlighted the desirable property of letting the sequences meet before their representations mature.[START_REF] He | Pairwise Word Interaction Modeling with Deep Neural Networks for Semantic Similarity Measurement[END_REF];[START_REF] Wan | A Deep Architecture for Semantic Matching with Multiple Positional Sentence Representations[END_REF] first encode the sequences with Bi-LSTMs then evaluate pairwise similarities between the words of the two sequences to build an interaction grid. WhileHe et al. (2016a) process the grid with a two-dimensional ConvNet,[START_REF] Wan | A Deep Architecture for Semantic Matching with Multiple Positional Sentence Representations[END_REF] directly use k-max pooling to aggregate and then score the pair.Similarly, for sequence alignment,[START_REF] Levy | Learning to Align the Source Code to the Compiled Object Code[END_REF] use LSTM hidden states as token representations and, similar to our work, concatenate pairwise representations and feed their input grid to a 2D ConvNet followed by a softmax to estimate soft-alignment probabilities.Recently in question-answering,[START_REF] Raison | Weaver: Deep Co-Encoding of Questions and Documents for Machine Reading[END_REF] weaved two Bi-LSTMs, one along the context dimension and the other along the question dimension in order to identify a response span in the context.More related to our work on machine translation,Kalchbrenner et al. (2016a) proposed the reencoder network where a Grid LSTM processes both sequences along its first and second dimension, allowing the model to re-encode the source sequence as it advances along the 3.5. RELATED WORK 59 target dimension. They also observed that such a structure implements an implicit form of attention. Wu et al. (2018) used a ConvNet over the 2D source-target representation, but only as a discriminator in an adversarial training setup. Similar to semantic matching models, they do not use masked convolutions, since their ConvNet is used to predict if a given source-target pair is a human or machine translation. Concurrently with our work, Bahar et al. (2018) used a 2D-LSTM layer to jointly process the source and target sequences with a similar two-dimensional layout. He et al. (2018) proposed a Transformer with layer-wise coordination where the source and target are concatenated into a single sequence that is processed by the same stack of Transformer blocks. The sub-block with encoder-decoder interaction is removed and the attention over source tokens is integrated in self-attention. Fonollosa et al. (2019) also proposed a joint processing of the source-target concatenation with additional locality constraints in self-attention. With this joint encoding, the decoder has access to the source features at various levels of abstraction instead of only attending to high-level source representations. Recently, Wu et al. (2019) revisited convolutional sequence-to-sequence models and proposed light-weight and dynamic convolutions. With light-weight convolutions, self-attention in a Transformer block is replaced with depth-wise separable uni-dimensional convolutions.Those convolutions are then made dynamic by predicting input-dependent kernels at every time-step.[START_REF] Wu | Pay Less Attention with Lightweight and Dynamic Convolutions[END_REF] use the same number of blocks as in Transformer models and progressively widen the convolution filters up to k = 31. Some incremental updates of the Transformer model includeZhao et al. (2019a) where only top-k scored positions are selected in self-attention to reduce the alignments' entropy,[START_REF] Lu | Understanding and Improving Transformer from a Multi-Particle Dynamic System Point of View[END_REF] where each self-attention module is surrounded by two feed-forward networks andZhao et al. (2019b) where both self-attention and depth-wise separable convolutions are used within each block. We list in

  this chapter we presented our work on Pervasive Attention, a sequence-to-sequence model to jointly encode the source and target sequences with a two-dimensional ConvNet. With this joint encoding, the source and target sequences meet at an early stage of encoding allowing each of them to influence the encoding of the other. We proposed different design choices for the core ConvNet focusing on the impact of the design on the receptive field and the abstraction level of the final features. Different methods to aggregate the final features were examined as to their effect on the translation quality and the informativeness of the explicit source-target alignments. Experiments on IWSLT'14 De )En show a clear advantage of a gradual and slow increase of the receptive field with small 5×5 filters and the importance of accumulating features coming from different encoding levels. Comparison to state-of-the-art encoder-decoder models on IWSLT'14 De )En, IWSLT'15 En )Vi and WMT'16 En )Ro prove the competitiveness of Pervasive Attention models. On the large and noisy WMT'15 De )En benchmark, Pervasive Attention show some sensitivity to misaligned training pairs. Future works on Pervasive Attention models should focus on solving this issue by means of data filtering or curriculum learning.

  of-the-art dynamic models. We propose to use Pervasive Attention models with their characteristic two-dimensional decoding grid for the task of online translation. With an oracle based on dynamic programming and likelihood scores, we outperform Transformer-MILk[START_REF] Ma | Monotonic Multihead Attention[END_REF] on the IWSLT'15 En )Vi benchmark. Some of the contributions presented in this chapter are published in: Maha Elbayad, Laurent Besacier, and Jakob Verbeek. 2020a. Improved Training Techniques for Online Neural Machine Translation Contents 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 A Common Framework for Online Decoding . . . . . . . . . . . . . . . . . . 4.3 Sequence-to-Sequence models for Online Decoding . . . . . . . . . . . . . . . 4.4 Online Decoding Agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 4 . 1 :

 41 Figure 4.1: Example of an online decoding path on top of the attention map of a Pervasive Attention model.

  An encoder block of Transformer models consists of a multi-head self-attention followed by a point-wise feed-forward network. The self-attention module of an encoder block is bi-directional i.e. the state at a given position includes signals from past as well as future time-steps. Transformer wait-k models introduced in Ma et al. (2019a) and used in Zheng et al. (2019b,a) maintain the bi-directionality of the encoder and re-encode the source context after each new READ. Recall that an attention module updates its input states S = (s 1 , . . . , s |x| ) of d-dimensional features with:

Figure 4 . 2 :

 42 Figure 4.2: Computational graph of s 3 in the encoder of an Online Transformer between two consecutive steps with different context sizes.

Figure 4 . 3 :

 43 Figure 4.3: Illustration of a causal two-dimensional convolution with filter W ∈ R 5×5 . At the position marked with •, the convolution only includes signals from the highlighted blue area. The rest of W is zeroed out.

Figure 4

 4 Figure 4.4: Position-wise aggregation of features in Pervasive Attention models. At every position (t -1, z t ) we consider three different areas to aggregate in order to predict the next target token.

Figure 4 .

 4 Figure 4.5a).

  Figure4.6: Wait-k decoding as a sequence of reads (red) and writes (black) over a source (horizontal) and target (vertical) grid. After reading the first k source tokens, the decoder alternates between reads and writes. In Wait-∞, also called Wait-until-End (WUE), decoding the source is fully read before any write operation.

  [a,b] (x) = max(a, min(x, b)). Examples of wait-k paths are shown in Figure 4.6.

,

  q(z) = [ [z = z wait-k ] ]. The Q-function is simply the decoding loss along z wait-k : Q(x, y, q; θ) = log p θ (y | x, z wait-k ) =|y| t=1 log p θ (y t |y <t , x ≤z wait-k t dependency on z wait-k <t is only relevant for the Transformer model where the path history matters.

Figure 4 . 7 :

 47 Figure4.7: Optimizing along multiple paths for Pervasive Attention. In the two examples z ≥ z wait-2 and z ≥ z wait-4 , we illustrate in the decoding grid the boundary wait-k path and the writing positions above it. Any path in which we write within the grayed area is optimized. In the q tj heatmap, we show the weights q tj evaluated with Eq. (4.35).

Figure 4 . 8 :

 48 Figure4.8: Illustration of the oracle optimal path z and the inferred labels supervising the agent. In the M-step, we set q tj = 1 in the highlighted blue positions to train the translation model.

  . (2019) were also motivated by the differentiability of DAL after the removal of arg min from the definition. With that, DAL can be used to regularize the training objectives of a trainable decoding agent. Other metrics include the Consecutive Wait (CW) introduced in Gu et al. (2017b) that measures the average number of source tokens read between two consecutive writes i.e. the average of the increments z tz t-1 .

  Figure 4.9: IWSLT'14 De )En and IWSLT'15 En )Vi: Impact of the encoder's receptive field on online Transformer models for wait-k decoding (k ∈ {1, 7}). Each model is evaluated along wait-k eval with k eval ∈ {1, 3, 5, 7, 9}.

Figure 4

 4 Figure 4.10: IWSLT'14 De↔En: Training Pervasive Attention models for wait-k decoding (k ∈ {1, 7, +∞}) with different aggregations of the ConvNet's features. Each model is evaluated along wait-k eval with k eval ∈ {1, 3, 5, 7, 9}.

  Transformer for online translation. In this section, we evaluate the wait-k online decoding for different TF and PA models, trained for different wait-k decoding paths. We denote with k = ∞ the wait-until-end training where the full source is read before decoding. In each figure the offline results are added for reference with their latency AL = |x|.

Figure 4 Figure 4

 44 Figure 4.11: IWSLT'14 De↔En and IWSLT'15 En↔Vi: wait-k online decoding with Pervasive attention (a,c,e,g) and Transformer (b,d,f,h). Each model is evaluated along wait-k eval with k eval ∈ {1, 3, 5, 7, 9}.

  State-of-the-art results

Figure 4 .

 4 Figure 4.13: Experimental results on WMT'15 De )En. Wait-k models are evaluated along wait-k eval with k eval ∈ {1, 3, 5, 7, 9}.

Figure 4 .

 4 Figure 4.14) have more potential than the offline model with our oracle (the first column of Figure 4.14) and are a priori a better choice for pre-training our dynamic agents. On the En )Vi task, the oracle is particularly deficient operating to the left of the deterministic wait-k decoding without improving the BLEU scores. This is probably due to the quality of the translation and proportionally the oracle's writing costs plateauing right after k eval = 2.Under such circumstances, the cost of a path is a poor indicator of the translation's quality.

  En )Viz ≥ z wait-1

Figure 4 .

 4 Figure 4.14: IWSLT'14 De↔En and IWSLT'15 En↔Vi: For different initializations, we report (a) the performance of the initialization along wait-k eval for k eval ∈ {1, 3, 5, 7, 9}, (b) the performance of an analogous TF model along the same wait-k eval , (c) the performance of the oracle under different reading costs λ, and (d) the performance of two dynamic agents supervised with the oracle using λ = 0 or λ = 1. Each dynamic agent is evaluated with different thresholds τ to decide whether to read or write. Details of the hyper-parameters can be found in Appendix D.

  Quality per level of difficulty

Figure 4 .

 4 Figure 4.15: WMT'15 De )En: Qualitative analysis of wait-k agents.

  Figure 4.15b). While BLEU of offline model naturally decreases with increasing source-target divergence, the performance loss is more important for the online models (k=∞ and k∈[1..|x|]), the multiple-

Figure 4 .

 4 Figure 4.16: IWSLT'14 De↔En: Quality per level of difficulty

Figure 4 .

 4 Figure 4.17: IWSLT'14 En )De: Examples decoded with a dynamic agent (k = ∞ initialization, λ = 1 and evaluated with τ = 0.7, BLEU=20.57, AL=0.77). The same examples are decoded with TF wait-7, k eval = 1 (BLEU=18.69, AL=2.26).

  k eval = 5 (AL=5.00) (b) Reference: denn ihr leben hing davon ab , ob sie den job richtig machten .

Figure 4 .

 4 Figure 4.18: IWSLT'14 En )De: Examples decoded with a dynamic agent (k = ∞ initialization, λ = 1 and evaluated with τ = 0.2, BLEU=26.98, AL=5.46). The same examples are decoded with TF wait-7, k eval = 5 (BLEU=25.41, AL=5.14).

  Online statistical MT. After pioneering work from[START_REF] Fügen | Simultaneous Translation of Lectures and Speeches[END_REF],[START_REF] Yarmohammadi | Incremental Segmentation and Decoding Strategies for Simultaneous Translation[END_REF] and[START_REF] He | Syntax-based Rewriting for Simultaneous Machine Translation[END_REF] proposed methods to increase the alignment monotonicity for statistical machine translation. To allow for a more flexible segmentation,[START_REF] Grissom | Don't Until the Final Verb Wait: Reinforcement Learning for Simultaneous Machine Translation[END_REF] introduced a trainable segmentation module that decides whether to write or read tokens based on the prediction of the final verb and the next token in the source sequence. This work was tailored specifically for translating verb-final languages (e.g., German and Japanese) to verb-medial languages (e.g., English) and used reinforcement learning to optimize the segmentation policy. Similarly,[START_REF] Oda | Syntax-Based Simultaneous Translation Through Prediction of Unseen Syntactic Constituents[END_REF] use a syntax-based statistical translation system to find the optimal segmentation strategy via greedy search and dynamic programming.

  Zheng et al. (2019b) train the model for decoding along two wait-k paths, but unlike our multi-wait-k, they only optimize along the two boundary paths.Zheng et al. (2019a) use supervised training based on an oracle read/write sequence derived from the pre-trained offline translation model. However, read/write probabilities have to be tuned to achieve different latency levels and models do not perform much better than wait-k models.Zheng et al. (2019c) also investigate beam search decoding for wait-k models using a target language model look-ahead.

  Some interesting techniques like gradient check-pointing can help reduce the memory usage but at the cost of a much slower training. Computation-wise, a single block is O(d 2 |x| + d|x| 2 ) expensive. With |x| the length of the sequence, computing the |x| × |x| similarity scores between d-dimensional features costs O(d|x| 2 ). Additionally, the position-wise key, value and query maps each costs O(d 2 |x|).

  exit points. Multiple works in computer vision have used early auxiliary classifiers in deep convolutional network. In Lee et al. (2015); Szegedy et al. (2015); Shen et al. (2016), these auxiliary losses were used to speed-up convergence and regularize the model by increasing the discriminativeness of the intermediate features. In Zamir et al. (2016) they were used for curriculum learning (Bengio et al., 2009). More related to our work, they are used for anytime prediction or early exiting Bolukbasi et al. (2017); Teerapittayanon et al. (2016); Wang et al. (2018); Huang et al. (2018). The later, state-of-the-art in anytime prediction for visual object recognition, raised the concern that these auxiliary losses negatively affect the late classifiers. In fact, feature extraction in ConvNets depends on how many layers are left until classification and, with auxiliary losses, the early features are prepared for short-term prediction. Their proposed model, MSDNet, uses dense skip connections to directly reach for low-level features. To train MSDNet, Huang et al. (2018) found that weighting all the losses equally works well in practice. Teerapittayanon et al. (2016) assigned more weights to early losses to encourage earlier exits. Recently, Hu et al. (2019) remarked that early losses have larger gradients that dominate the rest. They proposed adaptive loss balancing, where each loss has a weight inversely proportional to its empirical mean.

Figure 5

 5 Figure 5.3: Training regimes for decoder networks able to emit outputs at any layer. Aligned training optimizes all output classifiers C n simultaneously assuming all previous hidden states for the current layer are available. Mixed training samples M paths of random exits at which the model is assumed to have exited; missing previous hidden states are copied from below.

  Aligned training does not expose the model to misaligned states coming from different blocks and interacting within a self-attention operator. This creates a mismatch between training and testing. Mixed training reduces this discrepancy by training the model to use hidden states from different blocks of previous time-steps for self-attention. We sample M different exit sequences n

Figure 5

 5 Figure 5.4: Illustration of the computation graph with gradient manipulation. The forward pass flow is shown in dotted edges and the backward pass in blue edges. The manipulated edges are the thick edges of the graph where the gradient is scaled by γ n before entering the n-th block.

Figure 5

 5 Figure5.5: Variants of the adaptive depth prediction classifiers. Sequence-specific depth uses a multinomial classifier to choose an exit for the entire output sequence based on the encoder output s (left panel). It then outputs a token at this depth with classifier C n . The token-specific multinomial classifier determines the exit after the first block and proceeds up to the predicted depth before outputting the next token (middle panel). The token geometric-like classifier (right panel) makes a binary decision after every block to dictate whether to continue (C) to the next block or to stop (S) and emit an output distribution.

  . Similar to the likelihood-based oracle we can look at the correctness of the prediction at time-step t and smooth the scores by integrating surrounding positions.

  adaptive model is based on the choice of the family modeling the exit distribution and the oracle supervising the training of said distribution. With the different choices introduced in this section, we can train six different combinations summarized in

  2.1). Aligned training performs self-attention on aligned states and mixed training exposes self-attention to hidden states from different blocks. As baselines we show six separate standard Transformers with N ∈ [1..6] decoder blocks. All models are trained with an equal number of updates and mixed training with M = 6 paths is most comparable to aligned training since the number of losses per sample is identical. Two criteria are selected for evaluation, in the first we simply evaluate each exit n ∈ [1.

  features from lower blocks to subsequent layers and which are ubiquitous in Transformer models. Aligned training also performs very competitively to the individual baseline models.Aligned training is conceptually simple and fast. We can process a training sample with N exits in a single forward/backward pass while M passes are needed for mixed training. On our largest setup, WMT'14 En )Fr, the training time of an aligned model with six output classifiers increases only marginally by about 1% compared to a baseline with a single output classifier, keeping everything else equal. In the remainder of this work, we use the aligned mode to pre-train our anytime prediction models.

Figure 5 CHAPTER

 5 Figure 5.6: IWSLT14 De )En test set: trade-off between speed (average exit or AE) and accuracy (BLEU) for depth-adaptive methods.

Figure 5

 5 Figure 5.8: WMT'14 En )Fr test set: trade-off between speed (average exit or FLOPs) and accuracy (BLEU) for depth-adaptive methods.

Finally, we take

  the best performing models form the IWSLT'14 En )De benchmark and test them on the large WMT'14 En )Fr benchmark. Results on the test set (Figure 5.8a and Table 5.6) show that, even in a very large-scale setup, adaptive depth estimation improves on a Transformer baseline. The sequence-specific depth approach improves only marginally over the baseline. Tok-LL geometric-like can match the best baseline result of BLEU 43.41 (n = 6) by using only AE = 2.40 which corresponds to 40% of the decoder blocks. We also match the best aligned result of BLEU 43.62 (n = 6) with AE = 3.25. In this setup, Tok-LL geometric-like slightly outperforms the Tok-C counterpart. Confidence thresholding 122 CHAPTER 5. COST EFFECTIVE DECODING matches the accuracy of the n = 6 baseline with AE 2.5 or 59% fewer decoding blocks.However, confidence thresholding requires computing the output classifier at each block to determine whether to exit or continue. This is a large overhead since output classifiers predict |V| =44K types for this benchmark ( §5.4.1). To better account for this, we measure the average number of FLOPs per output token (the breakdown of the computation cost is available in Appendix B). Figure5.8b shows that the Tok-LL geometric-like approach provides a better trade-off when the overhead of the output classifiers is considered. In fact, with features in R d , the decision with a geometric-like distribution has a cost in O(d) compared to O(d |V|) with confidence thresholding.

Figure 5 . 9 :

 59 Figure5.9: Examples from the IWSLT'14 De )En test set with Tok-LL geometric-like depth estimation. Token exits are in blue and model scores (probabilities) are in gray. The '@@' are due to BPE or subword tokenization. For each example the source (Src) and the reference (Ref ) are provided in the caption.

  Src: This principle of comparison can be used for other purposes .Ref: Ce principe de comparaison peut avoir d' autres applications . Src: But passengers shoul@@dn't expect changes to happen immediately .Ref: Mais les passagers ne devraient pas s' attendre à des changements immédiats .

Figure 5 .

 5 Figure 5.10: Examples from the WMT'14 En )Fr test set with Tok-LL geometric-like depth estimation. For details see Figure 5.9.

Figure 5

 5 Figure5.11: WMT'14 En )Fr test set: exit distributions in the beginning (relative-position: rpos<0.1) and near the end (rpos>0.9) of the hypotheses of three models.

  1 and Model 2 , early exits (n ≤ 2) are used in the high confidence range [0.8 -1] and deeper exits (n ≥ 4) are used in the low-confidence range [0 -0.5]. Model 3 has a high average exit (AE = 4.68) so most tokens exit late, however, in low confidence ranges the model does not exit earlier than n = 5.

  Figure5.13: WMT'14 En )Fr test set: joint histogram of (exit, confidence score) and (exit, source length) for two sequence-level models, Seq-LL λ = 0.5 and λ = 2.

  aims at understanding what a trained model predicts. In our experiments, we find that slight changes of the architecture's design, the learning rate schedule, the number of training updates and the characteristics of the training data and how its pre-processed and batched are important factors with a considerable effect on what the model learns and how it performs. Understanding how the signal is propagated in the computational graph throughout the training phase could offer clues about the model's inner workings and how to effectively design and train better models. Neural architecture search We discussed in the previous point the interpretability of NMT models. There are different motivations behind interpreting a model's decisions and ours is to debug our models and improve their designs. Another tool for discovering better neural architectures is Neural Architecture Search (NAS). Works on NAS propose solutions based on reinforcement learning

  Figure C.2: Training Online Transformer wait-k models with different source markers.

Figure

  Figure C.2). These models fail to learn when to stop decoding and generate longer hypotheses (length-ratio > 1.1). In Figure C.2, we assist the decoders trained without </s> by forcing the end of decoding if and only if we have generated |x| target tokens. With such decoding strategy we improve the BLEU scores but they are still behind models with source </s>.

  p θ (y | x) = |y| t=1 p θ (y t | x, y <t ), (E.1) with θ the model parameters. The input x is a source sequence or an image in the contexts of machine translation and image captioning, respectively. Depending on the architecture (see §2.4), the prefixes y <t and the context x are encoded into hidden states (h t ) 1≤t≤|y| topped with a softmax-normalized linear layer to predict the next token in y. In standard teacher-forced training, the hidden states will be computed by forwarding the ground truth sequence y i.e. the model is predicting the next token given the ground truth history and not its own past predictions. In this chapter, to demarcate the ground truth output sequence, we will denote it with y and denote the hidden states evaluated in teacher-forcing mode with h t . Maximum likelihood estimation (MLE) of the model parameters θ amounts to minimizing the loss MLE (y , x) =log p θ (y | x) = -|y| t=1 log p θ (y t | h t ). (E.2)

  measure the path from a target-side state h t back to an input in the prefix y <t and the path from h t back to a source token x j . The first path is the one discussed for encoders, the second path however, depends on the way the encoder and the decoder are interfaced.

	.4c). This unbounded receptive field comes at the cost of computation time; the recursions characteristic of RNNs are not parallelizable and cost O(d 2 • |x|) in O(|x|) sequential steps. The recursion also affects the path between the teaching signal and the input, reaching a maximum length of O(|x|). Self-attention has an unbounded receptive field accessed in a single step and parallelizable computation across time-steps (c.f . Figure 2.4d). The computation cost is O(d • |x| 2 ) in O(1) sequential steps. The quadratic cost w.r.t. the sequence length |x| is especially taxing for long sequences. In sequence-to-sequence models, the only teaching signals come from the decoder. There-Model RF Computation Sequential y-path x-path fore, we CHAPTER 2. BACKGROUND RNN (Cho et al., 2014) ∞ O(N(|x|+|y|)) O(|y|) O(|x|) O(Nd 2 |x|+Nd 2 |y|) RNN (Sutskever et al., 2014) ∞ O(N(|x|+|y|)) O(|y|) O(|x|+|y|) O(Nd 2 |x|+Nd 2 |y|) RNN + attention (Luong et al., 2015) ∞ O(N(|x|+|y|)) O(|y|) O(1) O(Nd 2 |x|+Nd 2 |y|+d|x||y|) ByteNet (Kalchbrenner et al., 2016b) O(k2 N ) O(N) O(log k (|y|)) O(log k (|y||x|)) O(Nkd 2 |x|+Nkd 2 |y|) ConvS2S (Gehring et al., 2017) O(N) O(|y|/k) O(1) O(kN) O(Nkd 2 |x|+Nkd 2 |y|+Nd|x||y|) Transformer (Vaswani et al., 2017) ∞ O Nd|x| 2 +Nd|y| 2 +Nd|x||y| O(N) O(1) O(1)

Table 2

 2

	.1: Properties of sequence-to-sequence models.
	When using uni-directional recurrent networks, if the source is encoded in a single vector
	c that is injected in every update, signals from a source token x j need to travel the remaining
	of the source sequence before reaching a target state h t i.e. |x| -j + 1 edges. If c is used to initialize the decoder states this distance is |x| -j + 1 + t. Sutskever et al. (2014) opted for a backward recursion to encode x as they found it to improve over a forward encoder.

Table 2

 2

	.1 summarizes the discussed properties for a few key architectures. RF refers to the
	receptive-field and the y-path and x-path to the maximum length of the path from a teaching
	signal to a token in y or a token in x respectively. Each model has N processing layers in its
	encoder and decoder. It is worth noting that recurrent architectures are usually shallow in
	comparison to convolutional ones. The model's dimension, i.e. size of the embeddings and

  Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	This sequence-to-sequence model addresses the issue of source-target interaction
	in existing encoder-decoder models by jointly encoding the two sequences with
	a two-dimensional convolutional neural network. We propose different design
	choices for each building block of Pervasive Attention and study their effects on
	the quality of translation. Experiments on a set of MT benchmarks show results
	competitive with state-of-the-art encoder-decoder models.
	Some of the contributions presented in this chapter are published in:
	Maha Elbayad, Laurent Besacier, and Jakob Verbeek. 2018a. Pervasive
	Attention: 2D Convolutional Neural Networks for Sequence-to-Sequence
	Prediction. In Proc. of CoNLL
	Contents
	3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	3.2 Pervasive Attention Model . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	3.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	3.4 Analysis and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	3.5 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	3.6

Table 3

 3

	lr max Warm-up T w Batch-size (tokens) Epochs	0.002 4000 8K 78	0.002 4000 8K 100	0.001 4000 29K 76	0.0015 2000 460K 140
	Beam-width Length-penalty	5 1	5 1	5 0.5	5 0.6

.2: Length and length-ratio statistics in four datasets after BPE tokenization (except from IWSLT'15 En )Vi with word tokens). For each variable we measure the percentiles at 5%, 50% and 95%.

Hyper-parameter IWSLT'14 De )En IWSLT'15 En )Vi WMT'16 En )Ro WMT'15 De )En

Table 3

 3

.3: Training and evaluation hyper-parameters for the four benchmarks. The number of epochs is equivalent to 50K updates with the selected batch-size.

Table 3 .

 3 5: Performance on the development set with different aggregation mechanisms. All models have N=14 layers, filters in 11×11 and residual-cumulative skip connections.

	3.3. EXPERIMENTS

Table 3

 3

	3.3. EXPERIMENTS

.6 the entropies and coverages of alignments obtained with the Bi-LSTM and Transformer baselines. Since Transformer has 6 blocks, each with an encoder-decoder attention module, we average the heads in each block and report 6 values. For an in-depth analysis of the different attention heads in a

Table 3 .

 3 6: IWSLT'14 De )En development set: Entropies and coverages of soft alignments obtained with Pervasive Attention and two baseline encoder-decoder models.

Transformer model, we refer to

[START_REF] Tang | An Analysis of Attention Mechanisms: The Case of Word Sense Disambiguation in Neural Machine Translation[END_REF]

,

[START_REF] Voita | Analyzing Multi-Head Self-Attention: Specialized Heads Do the Heavy Lifting, the Rest Can Be Pruned[END_REF]

and

[START_REF] Michel | Are Sixteen Heads Really Better than One?[END_REF]

.

Table 3

 3

	Development	Test

.7. Pervasive Attention has N = 14 layers, filters in 11 × 11, residual-cumulative skip connections and self-attention for aggregation. We train all models with three different seeds and report the mean and standard-deviation of BLEU accuracies and perplexities. With equally sized features and classifiers, Pervasive Attention outperforms the recurrent, convolutional and attention-based baselines. IWSLT'14 En )Vi being of comparable size to IWSLT'14 De )En, we train the same model on this dataset. We also train the same model on the larger benchmark of WMT'16 En )Ro. The results in Table 3.8 show that Pervasive Attention is competitive on IWSLT'15 En )Vi outperforming Transformer base with 30% less parameters. On WMT'16 En )Ro, Pervasive Attention achieves comparable accuracies on the test set with considerably fewer parameters than Transformer models. Next, we move to the WMT'15 De )En benchmark. We use d = 512 and d FF = 2048 similar CHAPTER 3. PERVASIVE ATTENTION

Table 3 .

 3 7: IWSLT'14 De )En: Performances on the development and test sets.

				Development	Test
			#Params PPL b=1 b=5 b=1 b=5
	IWSLT'15 En )Vi	Transformer base Transformer small Pervasive Attention	44.2M 17.4M 15.2M	8.23 25.80 26.75 29.33 30.17 8.70 25.35 26.12 28.56 29.20 8.64 26.29 27.17 29.81 30.49
	WMT'16 En )Ro	Transformer base Transformer small Pervasive Attention	62.0M 20.0M 17.9M	6.07 33.63 34.06 32.56 33.26 6.13 33.83 34.37 32.95 33.46 6.03 33.69 34.25 32.87 33.54
	WMT'15 De )En	Transformer small Transformer base Pervasive Attention	19.3M 60.5M 49.0M	5.50 29.01 29.84 29.58 30.49 4.38 30.76 31.55 31.96 32.80 5.33 28.05 29.00 28.78 29.61

Table 3

 3

.8: Performances on the development and test sets of IWSLT'15 En-Vi, WMT'16 En )Ro and WMT'15 De )En.

to Transformer base and train N = 16 layers with filters in R 11×11 and residual-cumulative skip connections. We aggregate the ConvNet's ultimate features with self-attention. Results in Table

3

.8 show that Pervasive Attention is less successful in learning from large noisy datasets like WMT'15 De )En.

Table 3 .

 3 10 the results of recent works that experimented with IWSLT'14 De )En.

		CHAPTER 3. PERVASIVE ATTENTION
	MUSE (Zhao et al., 2019b) Top-k Attention	BLEU #Params |V EN | 36.30 -32K	d

Table 3 .

 3 10: State-of-the-art accuracies on IWSLT'14 De )En test set. For each model we report the total number of free parameters and the size of the final classifier (R d → R |V EN | ).

	BLEU	#Params |V Ro |	d

Table 3 .

 3 11: State-of-the-art accuracies on WMT'16 En )Ro test set (newstest-2016).

	Provilkov et al. (2019) -Transformer base Nguyen and Salazar (2019) -Transformer base Luong et al. (2015)	BLEU #Params 33.27 48.2M 32.79 52.3M 26.90 -Words-7.7K |V Vi | BPE-4K BPE-8K	d
	Transformer base Pervasive Attention	30.17 30.49	44.2M Words-7.7K 15.2M Words-7.7K

Table 3

 3

	3.6. CONCLUSION

.12: State-of-the-art accuracies on IWSLT'15 En )Vi test set (TED tst2013).

Table 3 .

 3 13: State-of-the-art accuracies on WMT'15 De )En test set (newstest-2015).

  .44)

	x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8	x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8
	<s>	<s>
	y 1	y 1
	y 2	y 2
	y 3	y 3
	y 4	y 4
	y 5	y 5
	y 6	y 6
	y 7	y 7
	(a) Optimal path z	(b) READ/WRITE supervision

  Table4.2: Offline evaluation of the Pervasive Attention (PA) and Transformer (TF) with either a uni-directional or a bi-directional encoder. We evaluate using greedy decoding and beam-search. For each task we highlight the best overall performance as well as the best uni-directional greedy decoding (best of the two first columns).

	Encoder		Uni-directional			Bi-directional
	Decoding	BLEU(b=1) BLEU(b=5) BLEU(b=1) BLEU(b=5)
	Architecture	PA	TF	PA	TF	PA	TF	PA	TF
	IWSLT'14 En )De 26.81 26.58 27.54 27.70 27.23 27.46 27.96 28.27 IWSLT'14 De )En 32.40 32.81 33.62 33.79 33.43 33.64 34.36 34.56
	IWSLT'15 En )Vi 29.22 28.90 30.20 29.65 29.81 29.33 30.49 30.17 IWSLT'15 Vi )En 26.81 25.73 27.96 26.92 27.43 28.09 28.04 29.00
	WMT'15 De )En 28.08 31.14 29.28 32.27 28.78 31.96 29.61 32.80
									, and

include Average Proportion (AP) and Differentiable Average Lagging (DAL) measures in Appendix D.

  Table 5.1. is 256. Embeddings are untied with 6 different output classifiers {W n } 1≤n≤6 . We evaluate with a single checkpoint, a beam of width 5 and a length penalty of 1. WMT'14 En )Fr. This large benchmark has 35.5M training pairs from which 26K are held out for development. Final results are reported on the test set of newstest14. The vocabulary consists of 44K joint BPE types. We train a Transformer big architecture andtie the embeddings of the encoder, the decoder and the output classifiers (W n ) 1≤n≤6 . We average the last ten checkpoints and use a beam of width 4 and length penalty of 0.6.For both benchmarks we evaluate a model by measuring tokenized BLEU. Models are optimized withAdam (Kingma and Ba, 2015). We train for 50K updates(2) on 128 GPUs with a batch size of 460K tokens for WMT'14 En )Fr and on 2 GPUs with 8K tokens per batch for IWSLT'14 De )En. To stabilize training, we re-normalize the gradients if their norm exceeds g clip = 3.

Table 5 .

 5 2: IWSLT'14 De )En development set: aligned vs. mixed training. We report BLEU scores for a uniformly sampled exit n ∼ U([1..6]) at each token, a fixed exit n ∈ [1..6] for all tokens, as well as the average BLEU over the fixed exits. As baseline we show six standard Transformer models with 1-6 blocks.

	35.93	35.37

Table D

 D

				IWSLT'14 De )En				IWSLT'14 En )De
		k eval	1	3	5	7	9	1	3	5	7	9
	k = ∞ Max-pooling	BLEU 19.78 25.89 29.72 30.34 31.30 AP 0.55 0.64 0.72 0.78 0.83 AL 1.34 2.70 4.37 6.16 7.92 DAL 1.42 3.18 5.11 6.99 8.74	18.02 23.19 25.49 26.35 26.73 0.58 0.66 0.74 0.80 0.85 1.90 3.38 5.10 6.89 8.62 2.06 3.66 5.47 7.29 9.01
	k = ∞ Gated max-pooling	BLEU 19.63 25.68 28.72 30.24 31.10 AP 0.65 0.64 0.72 0.78 0.83 AL 1.45 2.81 4.44 6.20 7.96 DAL 1.51 3.20 5.11 6.98 8.74	17.76 23.04 25.54 26.34 26.59 0.58 0.67 0.74 0.80 0.85 1.99 3.44 5.16 6.96 8.68 2.14 3.70 5.50 7.33 9.05
	k = ∞ Self-attention	BLEU 16.36 22.33 26.62 29.44 31.18 AP 0.51 0.61 0.70 0.77 0.83 AL -0.26 1.51 3.63 5.78 7.76 DAL 1.30 3.13 5.08 6.98 8.73	16.89 22.28 25.44 26.58 26.95 0.57 0.66 0.74 0.80 0.85 1.61 3.20 5.09 6.92 8.68 1.99 3.61 5.49 7.33 9.06
	k = ∞ Cell	BLEU 13.60 16.77 20.43 23.44 25.03 AP 0.51 0.61 0.71 0.78 0.83 AL -0.48 1.68 3.98 6.07 7.95 DAL 2.04 3.62 5.31 7.09 8.82	8.72 13.40 16.69 18.85 20.23 0.46 0.63 0.74 0.81 0.85 -0.25 2.81 5.21 7.12 8.80 2.44 4.26 5.86 7.56 9.18
	k = 7 Max-pooling	BLEU 19.98 26.12 28.93 30.45 31.14 AP 0.51 0.62 0.71 0.78 0.83 AL -0.27 1.78 3.93 6.00 7.90 DAL 1.40 3.20 5.12 7.00 8.77	18.43 23.17 25.33 25.99 26.52 0.57 0.66 0.74 0.80 0.85 1.73 3.34 5.12 6.94 8.67 2.10 3.70 5.50 7.33 9.05
	k = 7 Gated max-pooling	BLEU 21.11 26.63 28.96 30.58 31.18 AP 0.54 0.63 0.71 0.78 0.83 AL 0.66 2.21 4.09 6.08 7.92 DAL 1.53 3.21 5.13 6.99 8.75	17.93 22.88 25.09 25.69 25.87 0.58 0.66 0.74 0.80 0.85 1.89 3.34 5.07 6.87 8.60 2.12 3.67 5.48 7.29 9.01
	k = 7 Self-attention	BLEU 18.95 25.29 28.91 30.48 31.04 AP 0.51 0.61 0.71 0.78 0.83 AL -0.36 1.62 3.92 6.11 8.03 DAL 1.41 3.23 5.15 7.04 8.80	17.61 22.80 25.19 25.95 26.05 0.58 0.66 0.74 0.80 0.85 1.88 3.39 5.16 6.94 8.66 2.15 3.71 5.53 7.34 9.06
	k = 7 Cell	BLEU 17.73 24.90 28.34 29.67 29.98 AP 0.46 0.61 0.71 0.78 0.83 AL -1.26 1.63 3.90 5.95 7.83 DAL 1.51 3.29 5.16 7.01 8.77	17.08 21.55 24.12 25.11 25.12 0.55 0.66 0.74 0.80 0.85 1.21 3.33 5.08 6.86 8.55 2.22 3.74 5.48 7.29 8.97
	k = 1 Max-pooling	BLEU 20.63 24.69 25.96 26.56 26.80 AP 0.52 0.63 0.72 0.79 0.84 AL 0.03 2.20 4.37 6.35 8.19 DAL 1.62 3.38 5.26 7.11 8.85	18.02 23.19 25.49 26.35 26.73 0.58 0.66 0.74 0.80 0.85 1.90 3.38 5.10 6.89 8.62 2.06 3.66 5.47 7.29 9.01
	k = 1 Gated max-pooling	BLEU 20.14 23.83 24.80 24.98 24.62 AP 0.52 0.63 0.72 0.79 0.84 AL -0.02 2.11 4.31 6.28 8.13 DAL 1.62 3.40 5.31 7.16 8.90	17.76 23.04 25.54 26.34 26.59 0.58 0.67 0.74 0.80 0.85 1.99 3.44 5.16 6.96 8.68 2.14 3.70 5.50 7.33 9.05
	k = 1 Self-attention	BLEU 18.88 20.71 20.29 19.43 18.40 AP 0.54 0.66 0.75 0.81 0.85 AL 0.74 3.07 5.26 7.24 8.96 DAL 2.32 4.27 6.21 8.08 9.76	16.89 22.28 25.44 26.58 26.95 0.57 0.66 0.74 0.80 0.85 1.61 3.20 5.09 6.92 8.68 1.99 3.61 5.49 7.33 9.06
	k = 1 Cell	BLEU 18.77 20.89 19.85 18.20 14.61 AP 0.51 0.62 0.71 0.76 0.80 AL -0.11 1.96 3.95 5.54 6.78 DAL 1.69 3.46 5.33 7.12 8.83	8.72 13.40 16.69 18.85 20.23 0.46 0.63 0.74 0.81 0.85 -0.25 2.81 5.21 7.12 8.80 2.44 4.26 5.86 7.56 9.18

.1: Numerical results of Figure

4

.9 with AP, AL and DAL latency metrics.

Table D .

 D 2: Numerical results of Figure 4.10 with AP, AL and DAL latency metrics.

				Transformer				Pervasive Attention
		k eval	1	3	5	7	9	1	3	5	7	9
	k = 1	BLEU 18.89 21.24 20.81 18.98 17.24 AP 0.50 0.60 0.68 0.74 0.79 AL -0.50 1.35 3.19 4.76 6.27 DAL 1.52 3.22 5.06 6.90 8.65	20.63 24.69 25.96 26.56 26.80 0.52 0.63 0.72 0.79 0.84 0.03 2.20 4.37 6.35 8.19 1.62 3.38 5.26 7.11 8.85
	k = 3	BLEU 22.15 26.04 27.34 27.18 25.95 AP 0.54 0.62 0.70 0.77 0.81 AL 0.31 1.90 3.74 5.55 7.16 DAL 1.69 3.29 5.12 6.95 8.69	20.61 26.16 28.45 29.37 29.84 0.50 0.62 0.71 0.78 0.83 -0.30 1.89 4.11 6.13 7.99 1.46 3.27 5.17 7.04 8.79
	k = 5	BLEU 22.71 27.15 29.06 29.85 29.77 AP 0.56 0.64 0.71 0.78 0.82 AL 1.08 2.38 4.10 5.95 7.63 DAL 1.95 3.39 5.17 6.99 8.72	19.68 25.99 28.78 30.08 30.67 0.50 0.61 0.71 0.78 0.83 -0.44 1.71 3.99 6.03 7.91 1.42 3.22 5.15 7.01 8.76
	k = 7	BLEU 22.93 27.08 29.62 30.57 31.02 AP 0.58 0.65 0.72 0.78 0.83 AL 1.45 2.63 4.25 6.01 7.75 DAL 2.11 3.44 5.19 7.00 8.74	19.98 26.12 28.93 30.45 31.14 0.51 0.62 0.71 0.78 0.83 -0.27 1.78 3.93 6.00 7.90 1.40 3.20 5.12 7.00 8.77
	k = 9	BLEU 22.63 26.69 29.59 31.00 31.54 AP 0.59 0.65 0.72 0.78 0.83 AL 1.72 2.88 4.36 6.18 7.88 DAL 2.26 3.54 5.25 7.05 8.76	19.91 26.09 28.79 30.34 31.23 0.52 0.62 0.71 0.78 0.83 0.06 1.96 4.04 6.04 7.92 1.43 3.23 5.13 7.01 8.77
	k = ∞	BLEU 22.75 26.31 28.95 30.61 31.57 AP 0.57 0.65 0.72 0.79 0.83 AL 1.42 2.87 4.48 6.30 8.05 DAL 1.94 3.43 5.22 7.06 8.79	19.78 25.89 29.72 30.34 31.30 0.55 0.64 0.72 0.78 0.83 1.34 2.70 4.37 6.16 7.92 1.42 3.18 5.11 6.99 8.74
	k ∈ [1..|x|] or z ≥ z wait-1	BLEU 21.66 26.46 29.33 30.84 31.51 AP 0.51 0.62 0.71 0.78 0.83 AL -0.20 1.82 3.99 5.98 7.81 DAL 1.57 3.27 5.14 6.99 8.74	19.20 25.73 29.96 30.44 31.36 0.47 0.60 0.71 0.78 0.83 -1.26 1.28 3.81 5.97 7.90 1.38 3.23 5.15 7.03 8.78

Table D .

 D 3: IWSLT'14 De )En: numerical results of Figures 4.11 and 4.12.

				Transformer				Pervasive Attention
		k eval	1	3	5	7	9	1	3	5	7	9
	k = 1	BLEU 16.43 17.97 16.67 14.76 13.22 AP 0.57 0.65 0.71 0.76 0.81 AL 1.56 2.89 4.28 5.63 6.97 DAL 2.12 3.53 5.19 6.95 8.67	18.02 23.19 25.49 26.35 26.73 0.58 0.66 0.74 0.80 0.85 1.90 3.38 5.10 6.89 8.62 2.06 3.66 5.47 7.29 9.01
	k = 3	BLEU 17.78 22.10 23.68 22.38 20.97 AP 0.59 0.66 0.73 0.79 0.83 AL 2.00 3.32 4.85 6.36 7.81 DAL 2.31 3.65 5.33 7.07 8.75	18.12 22.34 23.91 24.34 24.58 0.57 0.66 0.74 0.80 0.85 1.54 3.27 5.10 6.95 8.68 2.14 3.74 5.54 7.36 9.07
	k = 5	BLEU 18.56 23.00 25.41 25.73 25.22 AP 0.59 0.67 0.74 0.80 0.84 AL 2.07 3.41 5.01 6.68 8.27 DAL 2.37 3.73 5.42 7.17 8.86	18.40 23.34 25.11 25.72 25.85 0.57 0.66 0.74 0.80 0.85 1.68 3.34 5.10 6.92 8.65 2.12 3.70 5.52 7.33 9.04
	k = 7	BLEU 18.69 23.15 25.41 26.37 26.35 AP 0.60 0.67 0.74 0.80 0.85 AL 2.26 3.55 5.14 6.82 8.49 DAL 2.53 3.82 5.50 7.25 8.94	18.43 23.17 25.33 25.99 26.52 0.57 0.66 0.74 0.80 0.85 1.73 3.34 5.12 6.94 8.67 2.10 3.70 5.50 7.33 9.05
	k = 9	BLEU 18.82 23.05 25.27 26.27 26.67 AP 0.60 0.67 0.74 0.80 0.85 AL 2.29 3.59 5.19 6.88 8.54 DAL 2.54 3.85 5.53 7.29 8.97	18.36 23.23 25.36 26.03 26.32 0.58 0.67 0.74 0.80 0.85 1.92 3.45 5.17 6.97 8.69 2.16 3.74 5.53 7.34 9.06
	k = ∞	BLEU 18.53 22.82 24.97 25.87 26.15 AP 0.59 0.67 0.74 0.80 0.85 AL 2.13 3.49 5.14 6.89 8.63 DAL 2.33 3.74 5.51 7.31 9.04	18.02 23.19 25.49 26.35 26.73 0.58 0.66 0.74 0.80 0.85 1.90 3.38 5.10 6.89 8.62 2.06 3.66 5.47 7.29 9.01
	k ∈ [1..|x|] or z ≥ z wait-1	BLEU 18.60 23.04 25.07 25.80 26.09 AP 0.56 0.66 0.74 0.80 0.85 AL 1.51 3.36 5.15 6.96 8.68 DAL 2.23 3.77 5.53 7.34 9.07	19.05 23.55 25.44 26.17 26.39 0.55 0.66 0.74 0.80 0.85 1.05 3.14 5.05 6.92 8.68 2.08 3.72 5.52 7.34 9.06

Table D .

 D 4: IWSLT'14 En )De: numerical results of Figure 4.11.

				Transformer				Pervasive Attention
		k eval	1	3	5	7	9	1	3	5	7	9
	k = 1	BLEU 25.72 25.88 24.13 21.69 19.94 AP 0.63 0.71 0.77 0.81 0.85 AL 2.89 4.26 5.72 7.09 8.45 DAL 3.43 4.75 6.21 7.66 9.10	26.45 27.88 28.19 28.15 28.06 0.63 0.72 0.79 0.84 0.88 2.87 4.60 6.38 8.08 9.67 3.52 5.17 6.94 8.64 10.20
	k = 3	BLEU 25.83 27.59 27.45 27.15 26.18 AP 0.64 0.72 0.79 0.83 0.87 AL 3.10 4.58 6.21 7.74 9.22 DAL 3.77 5.18 6.78 8.30 9.76	27.31 29.24 29.15 29.13 29.11 0.63 0.72 0.79 0.84 0.88 3.07 4.70 6.41 8.10 9.70 3.59 5.26 6.98 8.67 10.24
	k = 5	BLEU 26.22 28.29 28.57 28.54 28.13 AP 0.64 0.72 0.79 0.84 0.88 AL 3.20 4.74 6.35 7.98 9.50 DAL 3.82 5.31 6.92 8.53 10.00	26.90 29.00 29.18 29.26 29.27 0.63 0.72 0.79 0.84 0.88 3.08 4.67 6.39 8.11 9.70 3.61 5.22 6.97 8.68 10.24
	k = 7	BLEU 26.15 28.50 28.52 28.78 28.94 AP 0.65 0.73 0.79 0.84 0.88 AL 3.32 4.82 6.43 8.09 9.66 DAL 3.97 5.43 7.04 8.68 10.22	26.90 28.81 29.01 29.11 29.12 0.63 0.72 0.79 0.84 0.88 3.06 4.65 6.37 8.09 9.68 3.56 5.19 6.94 8.64 10.21
	k = 9	BLEU 25.59 27.90 28.38 28.72 28.78 AP 0.65 0.72 0.79 0.84 0.88 AL 3.24 4.73 6.41 8.09 9.64 DAL 3.86 5.31 7.02 8.68 10.19	26.84 29.22 29.29 29.48 29.47 0.64 0.72 0.79 0.84 0.88 3.09 4.68 6.41 8.11 9.70 3.62 5.23 6.99 8.68 10.24
	k = ∞	BLEU 26.54 28.07 28.48 28.59 28.58 AP 0.64 0.72 0.79 0.84 0.88 AL 3.00 4.57 6.26 7.99 9.58 DAL 3.50 5.10 6.82 8.54 10.09	27.28 29.06 29.23 29.21 29.25 0.64 0.72 0.79 0.84 0.88 3.08 4.67 6.39 8.10 9.68 3.59 5.22 6.96 8.66 10.21
	k ∈ [1..|x|] or z ≥ z wait-1	BLEU 26.61 28.31 28.67 28.63 28.64 AP 0.63 0.71 0.78 0.84 0.88 AL 2.80 4.41 6.14 7.88 9.48 DAL 3.32 4.90 6.64 8.38 9.94	27.35 29.27 29.57 29.65 29.67 0.63 0.72 0.79 0.84 0.88 2.91 4.65 6.39 8.11 9.69 3.56 5.21 6.97 8.66 10.22

Table D .

 D 5: IWSLT'14 En )Vi: numerical results of Figures 4.11 and 4.12.

				Transformer				Pervasive Attention
		k eval	1	3	5	7	9	1	3	5	7	9
	k = 1	BLEU AP AL DAL	8.29 0.42 -2.83 1.44	9.77 0.51 -1.03 3.19	9.07 0.60 1.21 5.21	8.48 0.66 2.89 6.98	7.53 0.72 4.72 8.83	9.37 11.41 12.52 12.53 11.47 0.43 0.55 0.65 0.72 0.78 -2.82 0.19 2.60 4.91 7.16 1.76 3.80 5.51 7.47 9.51
	k = 3	BLEU 12.37 16.10 17.21 17.42 16.58 AP 0.48 0.56 0.64 0.70 0.75 AL -1.18 0.60 2.37 4.24 6.10 DAL 1.58 3.27 5.16 6.98 8.92	12.09 15.69 17.69 19.03 19.88 0.44 0.54 0.63 0.70 0.77 -2.18 -0.26 2.07 4.13 6.40 1.36 3.19 5.13 6.95 8.84
	k = 5	BLEU 13.56 17.43 19.29 20.68 20.35 AP 0.47 0.54 0.63 0.70 0.76 AL -1.38 0.08 2.32 4.25 6.38 DAL 1.79 3.24 5.28 7.03 9.05	13.36 17.40 19.39 21.22 22.07 0.46 0.55 0.64 0.71 0.77 -1.63 0.31 2.46 4.41 6.34 1.39 3.19 5.12 6.98 8.79
	k = 7	BLEU 14.93 18.16 20.55 21.36 22.93 AP 0.50 0.56 0.64 0.71 0.76 AL -0.75 0.57 2.31 4.51 6.25 DAL 1.66 3.26 5.14 7.04 8.79	12.04 16.53 19.10 21.08 22.56 0.43 0.53 0.62 0.70 0.76 -2.65 -0.38 1.73 3.91 6.16 1.26 3.07 5.02 6.94 8.79
	k = 9	BLEU 14.56 17.75 20.48 21.70 22.96 AP 0.52 0.58 0.65 0.71 0.77 AL 0.06 1.12 2.69 4.64 6.48 DAL 1.78 3.30 5.10 7.04 8.90	12.56 16.28 19.66 21.94 22.89 0.45 0.54 0.63 0.70 0.76 -1.97 -0.22 1.88 4.02 6.07 1.29 3.09 5.02 6.94 8.78
	k = ∞	BLEU 15.46 18.03 19.93 21.70 23.35 AP 0.54 0.60 0.67 0.73 0.77 AL 0.80 2.00 3.50 5.15 6.88 DAL 1.65 3.20 5.11 6.98 8.79	10.71 14.71 17.94 20.34 22.80 0.54 0.61 0.67 0.73 0.78 1.31 2.46 3.80 5.29 6.95 1.34 3.08 5.02 6.95 8.79
	k ∈ [1..|x|] or z ≥ z wait-1	BLEU 10.19 15.74 19.35 22.23 24.11 AP 0.38 0.50 0.60 0.69 0.75 AL -3.93 -1.46 1.10 3.48 5.74 DAL 1.23 3.06 5.01 6.93 8.77	10.99 15.33 19.03 21.36 23.10 0.39 0.50 0.61 0.69 0.76 -3.68 -1.51 1.25 3.66 5.90 1.20 3.10 5.03 6.97 8.78

Table D .

 D 6: IWSLT'14 Vi )En: numerical results of Figure 4.11.

				Transformer base				Transformer big
		k eval	1	3	5	7	9	1	3	5	7	9
	k = 7	BLEU 18.30 24.62 27.08 28.43 29.01 AP 0.54 0.60 0.67 0.74 0.79 AL 0.49 2.02 3.90 5.87 7.76 DAL 2.03 3.38 5.23 7.11 8.94	19.16 24.68 27.12 28.94 29.73 0.53 0.60 0.67 0.73 0.78 0.21 1.94 3.78 5.77 7.66 1.95 3.40 5.23 7.10 8.93
	k = ∞	BLEU 20.26 22.14 23.64 25.23 26.43 AP 0.60 0.66 0.72 0.77 0.81 AL 2.60 4.26 5.81 7.42 9.07 DAL 3.55 5.05 6.70 8.29 9.88	20.37 21.45 22.94 24.79 26.13 0.59 0.65 0.71 0.76 0.81 2.42 3.69 5.28 7.08 8.73 3.74 5.07 6.69 8.32 9.93
	k ∈ [1..|x|]	BLEU 18.95 23.85 26.36 28.03 29.00 AP 0.50 0.59 0.67 0.73 0.79 AL -0.47 1.58 3.69 5.81 7.80 DAL 1.70 3.34 5.21 7.11 8.95	19.60 24.54 27.68 29.15 30.15 0.53 0.60 0.68 0.74 0.79 0.46 2.06 4.08 6.03 7.84 1.90 3.43 5.27 7.15 8.96
	k = k eval	BLEU 18.26 24.00 26.97 28.43 29.29 AP 0.51 0.60 0.67 0.74 0.79 AL -0.11 1.89 3.87 5.87 7.79 DAL 1.78 3.37 5.25 7.11 8.92

  Table D.7: WMT'15 De )En: numerical results of Figure 4.13.

		k eval	1	3	5	7	9
	Initialization k = ∞	BLEU 19.54 25.69 28.84 30.38 31.15 AP 0.56 0.64 0.72 0.78 0.83 AL 1.42 2.80 4.45 6.24 7.98 DAL 1.47 3.21 5.12 7.00 8.75
		λ	4	3	2	1	0
	Oracle	BLEU 29.46 30.96 31.85 32.24 32.57 AP 0.65 0.66 0.68 0.69 0.72 AL 3.34 3.71 4.07 4.47 5.05 DAL 6.31 6.70 7.10 7.54 8.28
		τ	0.7	0.6	0.5	0.4	0.3	0.2
	Dynamic λ = 1	BLEU 21.48 25.71 28.69 30.38 31.32 31.88 AP 0.54 0.60 0.64 0.68 0.71 0.75 AL -0.34 1.22 2.52 3.54 4.50 5.48 DAL 3.43 4.20 4.99 5.77 6.67 7.71
		τ	0.9	0.85	0.8	0.7	0.6	0.5	0.4	0.3	0.2
	Dynamic λ = 0	BLEU 23.60 26.00 27.50 29.39 30.56 31.14 31.63 32.02 32.24 AP 0.55 0.58 0.60 0.63 0.66 0.69 0.72 0.76 0.79 AL 0.66 1.40 1.91 2.67 3.32 3.98 4.73 5.65 6.86 DAL 2.62 3.05 3.47 4.25 4.97 5.72 6.56 7.59 8.93

Table D

 D

		k eval	1	3	5	7	9
	Initialization k = 7	BLEU 19.98 26.12 28.93 30.45 31.14 AP 0.51 0.62 0.71 0.78 0.83 AL -0.27 1.78 3.93 6.00 7.90 DAL 1.40 3.20 5.12 7.00 8.77
		λ	4	3	2	1	0
	Oracle	BLEU 27.51 29.10 30.02 30.51 30.80 AP 0.53 0.56 0.58 0.60 0.64 AL 0.22 0.96 1.51 1.95 2.68 DAL 4.04 4.57 5.08 5.54 6.30
		τ	0.7	0.6	0.5	0.4	0.3	0.2
	Dynamic λ = 1	BLEU 20.08 24.80 27.79 29.49 30.65 31.28 AP 0.52 0.58 0.62 0.65 0.68 0.72 AL -0.94 0.66 1.87 2.81 3.65 4.48 DAL 3.01 3.70 4.36 5.01 5.72 6.54
		τ	0.9	0.8	0.7	0.6	0.5	0.4	0.3	0.2
	Dynamic λ = 0	BLEU 23.74 27.57 28.61 29.30 30.28 30.81 31.22 31.48 AP 0.54 0.59 0.61 0.62 0.64 0.67 0.69 0.72 AL 0.37 1.65 2.06 2.39 2.92 3.46 4.03 4.73 DAL 2.38 3.18 3.53 3.86 4.48 5.09 5.74 6.50

.8: IWSLT'14 De )En: numerical results of panel (a) in Figure 4.14.

  Table D.9: IWSLT'14 De )En: numerical results of panel (b) in Figure 4.14.

		k eval	1	3	5	7	9
	Initialization z ≥ z wait-1	BLEU 19.20 25.73 28.96 30.44 31.36 AP 0.47 0.60 0.71 0.78 0.83 AL -1.26 1.28 3.81 5.97 7.90 DAL 1.38 3.23 5.15 7.03 8.78
		λ	4	3	2	1	0
	Oracle	BLEU 24.57 26.84 28.01 28.71 29.37 AP 0.45 0.49 0.52 0.54 0.60 AL -1.39 -0.45 0.16 0.66 1.58 DAL 3.15 3.76 4.27 4.73 5.64
		τ	0.8	0.7	0.6	0.5	0.4	0.3	0.2
	Dynamic λ = 1	BLEU 15.20 19.99 23.97 27.04 29.08 30.58 31.47 AP 0.44 0.51 0.57 0.61 0.64 0.68 0.71 AL -2.57 -1.01 0.35 1.60 2.56 3.51 4.47 DAL 2.42 3.03 3.70 4.35 5.00 5.74 6.62
		τ	0.9	0.85	0.8	0.75	0.7	0.6	0.5	0.4	0.35	0.3
	Dynamic λ = 0	BLEU 22.15 25.21 26.80 27.88 28.90 30.14 30.86 31.24 31.39 31.49 AP 0.51 0.55 0.58 0.60 0.61 0.64 0.67 0.69 0.71 0.72 AL -0.39 0.59 1.23 1.72 2.14 2.80 3.41 4.01 4.34 4.70 DAL 2.19 2.67 3.04 3.43 3.79 4.45 5.08 5.76 6.11 6.51

Table D .

 D 10: IWSLT'14 De )En: numerical results of panel (c) in Figure 4.14.

		k eval	1	3	5	7	9
	Initialization k = ∞	BLEU 18.54 23.27 25.38 26.19 26.50 AP 0.58 0.67 0.74 0.80 0.85 AL 2.01 3.46 5.19 6.98 8.69 DAL 2.17 3.71 5.53 7.35 9.06
		λ	6	5	4	3	2	1	0
	Oracle	BLEU 22.77 24.35 25.42 26.19 26.66 27.05 27.26 AP 0.62 0.63 0.64 0.65 0.66 0.68 0.71 AL 2.51 2.71 2.88 3.06 3.33 3.69 4.35 DAL 5.34 5.50 5.69 5.89 6.16 6.55 7.30
		τ	0.7	0.6	0.5	0.4	0.3	0.2
	Dynamic λ = 1	BLEU 21.48 25.71 28.69 30.38 31.32 31.88 AP 0.54 0.60 0.64 0.68 0.71 0.75 AL -0.34 1.22 2.52 3.54 4.50 5.48 DAL 3.43 4.20 4.99 5.77 6.67 7.71
		τ	0.9	0.85	0.8	0.7	0.6	0.5	0.4	0.3	0.2
	Dynamic λ = 0	BLEU 23.60 26.00 27.50 29.39 30.56 31.14 31.63 32.02 32.24 AP 0.55 0.58 0.60 0.63 0.66 0.69 0.72 0.76 0.79 AL 0.66 1.40 1.91 2.67 3.32 3.98 4.73 5.65 6.86 DAL 2.62 3.05 3.47 4.25 4.97 5.72 6.56 7.59 8.93

Table D .

 D 11: IWSLT'14 En )De: numerical results of panel (d) in Figure 4.14.

		k eval	1	3	5	7	9
	Initialization k = 7	BLEU 18.43 23.17 25.33 25.99 26.25 AP 0.57 0.66 0.74 0.80 0.85 AL 1.73 3.34 5.12 6.94 8.67 DAL 2.10 3.70 5.50 7.33 9.05
		λ	5	4	3	2	1	0
	Oracle	BLEU 24.12 24.94 25.69 26.24 26.70 26.93 AP 0.56 0.59 0.61 0.63 0.64 0.67 AL 0.80 1.50 2.02 2.43 2.75 3.39 DAL 4.26 4.69 5.08 5.43 5.75 6.42
		τ	0.8	0.7	0.6	0.5	0.4	0.3	0.2
	Dynamic λ = 1	BLEU 15.96 20.12 23.02 25.02 26.17 26.47 26.72 AP 0.51 0.57 0.62 0.65 0.68 0.71 0.74 AL -1.14 0.44 1.73 2.73 3.55 4.23 4.94 DAL 2.92 3.51 4.10 4.65 5.22 5.85 6.60
		τ	0.7	0.6	0.5	0.4	0.3	0.2	0.1
	Dynamic λ = 0	BLEU 24.91 25.65 26.19 26.63 26.74 26.86 26.91 AP 0.65 0.67 0.69 0.72 0.74 0.77 0.81 AL 2.92 3.38 3.88 4.42 5.06 5.88 7.11 DAL 4.12 4.65 5.20 5.81 6.55 7.46 8.77

Table D .

 D 12: IWSLT'14 En )De: numerical results of panel (e) in Figure 4.14.

		k eval	1	3	5	7	9
	Initialization z ≥ z wait-1	BLEU 19.05 23.55 25.44 26.17 26.39 AP 0.55 0.66 0.74 0.80 0.85 AL 1.05 3.14 5.05 6.92 8.68 DAL 2.08 3.72 5.52 7.34 9.06
		λ	5	4	3	2	1	0
	Oracle	BLEU 20.94 22.89 24.30 25.06 25.41 25.88 AP 0.45 0.49 0.52 0.55 0.57 0.62 AL -1.30 -0.41 0.41 0.87 1.30 2.09 DAL 3.15 3.66 4.21 4.58 4.98 5.73
		τ	0.7	0.6	0.5	0.4	0.3	0.2
	Dynamic λ = 1	BLEU 18.66 21.99 24.60 26.03 26.44 26.72 AP 0.55 0.60 0.64 0.68 0.70 0.73 AL -0.02 1.38 2.57 3.50 4.18 4.88 DAL 3.29 3.89 4.49 5.08 5.70 6.44
		τ	0.9	0.8	0.7	0.6	0.5	0.4	0.3	0.2
	Dynamic λ = 0	BLEU 20.75 23.85 25.25 25.94 26.35 26.70 26.81 26.86 AP 0.59 0.63 0.65 0.68 0.70 0.73 0.75 0.78 AL 1.69 2.53 3.07 3.57 4.10 4.67 5.34 6.19 DAL 3.00 3.73 4.31 4.88 5.47 6.14 6.90 7.85

Table D .

 D 13: IWSLT'14 En )De: numerical results of panel (f) in Figure 4.14.

		k eval	1	3	5	7	9
	Initialization k = ∞	BLEU 10.71 14.71 17.94 20.34 22.80 AP 0.54 0.61 0.67 0.73 0.78 AL 1.31 2.46 3.80 5.29 6.95 DAL 1.34 3.08 5.02 6.95 8.79
		λ	5.0	4.0	3.0	2.0	1.0	0.0
	Oracle	BLEU 24.63 25.58 26.03 26.24 26.43 26.72 AP 0.64 0.64 0.65 0.66 0.67 0.69 AL 3.54 3.65 3.89 4.16 4.36 4.82 DAL 6.47 6.59 6.86 7.14 7.38 7.92
		τ	0.8	0.7	0.6	0.5	0.4	0.3
	Dynamic λ = 1	BLEU 12.16 17.89 22.58 24.80 25.88 26.25 AP 0.44 0.53 0.59 0.63 0.66 0.68 AL -2.96 -0.58 1.69 2.93 3.83 4.45 DAL 2.91 3.55 4.24 4.83 5.41 6.00
		τ	0.8	0.7	0.6	0.5	0.4	0.3	0.2	0.1
	Dynamic λ = 0	BLEU 21.84 24.44 25.52 26.05 26.37 26.37 26.42 26.57 AP 0.56 0.61 0.63 0.66 0.68 0.71 0.74 0.79 AL 0.96 2.42 3.20 3.83 4.43 5.12 6.09 7.71 DAL 3.52 4.26 4.80 5.30 5.93 6.69 7.72 9.54

Table D .

 D 14: IWSLT'15 Vi )En: numerical results of panel (g) in Figure 4.14.

		k eval	1	3	5	7	9
	Initialization k = 7	BLEU 12.04 16.53 19.10 21.08 22.56 AP 0.43 0.53 0.62 0.70 0.76 AL -2.65 -0.38 1.73 3.91 6.16 DAL 1.26 3.07 5.02 6.94 8.79
		λ	4	3	2.0	1	0
	Oracle	BLEU 19.18 21.39 23.00 23.80 24.11 AP 0.47 0.51 0.55 0.58 0.61 AL -1.47 -0.20 0.93 1.56 2.22 DAL 3.66 4.34 5.11 5.67 6.27
		τ	0.8	0.7	0.6	0.5	0.4	0.3
	Dynamic λ = 1	BLEU 12.16 17.89 22.58 24.80 25.88 26.25 AP 0.44 0.53 0.59 0.63 0.66 0.68 AL -2.96 -0.58 1.69 2.93 3.83 4.45 DAL 2.91 3.55 4.24 4.83 5.41 6.00
		τ	0.9	0.8	0.7	0.6	0.5	0.4	0.3	0.2
	Dynamic λ = 0	BLEU 17.55 22.62 24.64 24.95 25.73 25.70 25.76 25.79 AP 0.51 0.57 0.60 0.62 0.64 0.66 0.69 0.72 AL -0.42 1.62 2.39 2.88 3.44 3.93 4.52 5.28 DAL 2.64 3.47 3.96 4.40 4.89 5.40 6.03 6.82

Table D .

 D 15: IWSLT'15 Vi )En: numerical results of panel (h) in Figure 4.14.

		k eval	1	3	5	7	9
	Initialization z ≥ z wait-1	BLEU 10.99 15.33 19.03 21.36 23.10 AP 0.39 0.50 0.61 0.69 0.76 AL -3.68 -1.51 1.25 3.66 5.90 DAL 1.20 3.10 5.03 6.97 8.78
		λ	5	4	3	2.0	1	0
	Oracle	BLEU 15.80 18.09 21.14 23.12 23.89 24.42 AP 0.36 0.40 0.46 0.51 0.54 0.59 AL -3.69 -2.62 -0.98 0.24 0.87 1.67 DAL 2.53 2.90 3.72 4.55 5.09 5.83
		τ	0.8	0.7	0.6	0.5	0.4	0.3	0.2
	Dynamic λ = 1	BLEU 12.14 18.24 22.68 24.66 25.58 26.00 26.17 AP 0.42 0.51 0.58 0.62 0.64 0.66 0.69 AL -3.20 -0.68 1.42 2.71 3.40 3.92 4.51 DAL 2.60 3.27 3.90 4.46 4.92 5.41 6.05
		τ	0.9	0.8	0.7	0.6	0.5	0.4	0.3	0.2
	Dynamic λ = 0	BLEU 17.81 23.43 24.94 25.77 26.17 26.28 26.24 26.35 AP 0.50 0.58 0.61 0.63 0.65 0.68 0.70 0.73 AL -0.78 1.53 2.46 3.17 3.67 4.23 4.86 5.72 DAL 2.54 3.47 4.05 4.63 5.15 5.71 6.38 7.33

Table D .

 D 16: IWSLT'15 Vi )En: numerical results of panel (i) in Figure 4.14.

		k eval	1	3	5	7	9
	Initialization k = ∞	BLEU 27.28 29.06 29.23 29.21 29.25 AP 0.64 0.72 0.79 0.84 0.88 AL 3.08 4.67 6.39 8.10 9.68 DAL 3.59 5.22 6.96 8.66 10.21
		λ	7	0
	Oracle	BLEU 27.85 28.87 AP 0.64 0.68 AL 2.78 3.62 DAL 5.14 6.23
		τ	0.8	0.7	0.6	0.5	0.4	0.3	0.2	0.1
	Dynamic λ = 1	BLEU 16.91 22.59 26.37 28.23 28.92 29.12 29.34 29.46 AP 0.48 0.55 0.60 0.63 0.64 0.67 0.69 0.73 AL -1.39 0.33 1.53 2.29 2.71 3.14 3.66 4.44 DAL 2.54 3.08 3.52 3.93 4.31 4.71 5.23 6.04
		τ	0.8	0.7	0.6	0.5	0.4	0.3	0.2	0.1
	Dynamic λ = 0	BLEU 27.84 28.50 28.92 29.07 29.12 29.38 29.47 29.45 AP 0.60 0.62 0.63 0.65 0.67 0.70 0.72 0.77 AL 1.80 2.17 2.46 2.79 3.18 3.72 4.39 5.43 DAL 3.24 3.58 3.91 4.28 4.70 5.21 5.91 7.06

Table D .

 D 17: IWSLT'15 En )Vi: numerical results of panel (j) in Figure4.14.

		k eval	1	3	5	7	9
	Initialization k = 7	BLEU 26.90 28.81 29.01 29.11 29.12 AP 0.63 0.72 0.79 0.84 0.88 AL 3.06 4.65 6.37 8.09 9.68 DAL 3.56 5.19 6.94 8.64 10.21
		λ	1	0
	Oracle	BLEU 27.75 28.15 AP 0.65 0.66 AL 2.81 3.02 DAL 5.29 5.57
		τ	0.8	0.7	0.6	0.5	0.4	0.3	0.2	0.1
	Dynamic λ = 1	BLEU 17.48 23.72 27.41 28.45 28.79 29.15 29.25 29.33 AP 0.49 0.56 0.60 0.63 0.64 0.66 0.69 0.72 AL -1.20 0.68 1.81 2.30 2.68 3.11 3.62 4.39 DAL 2.49 3.05 3.46 3.80 4.16 4.58 5.12 5.92
		τ	0.8	0.7	0.6	0.5	0.4	0.3	0.2	0.1
	Dynamic λ = 0	BLEU 27.86 28.44 28.68 28.76 29.05 29.26 29.31 29.30 AP 0.59 0.61 0.62 0.64 0.66 0.69 0.71 0.75 AL 1.68 2.04 2.31 2.63 3.02 3.50 4.11 5.06 DAL 3.05 3.39 3.69 4.05 4.45 4.92 5.55 6.54

Table D .

 D 18: IWSLT'15 En )Vi: numerical results of panel (k) in Figure 4.14.

		k eval	1	3	5	7	9
	Initialization z ≥ z wait-1	BLEU 27.35 29.27 29.57 29.65 29.67 AP 0.63 0.72 0.79 0.84 0.88 AL 2.91 4.65 6.39 8.11 9.69 DAL 3.56 5.21 6.97 8.66 10.22
		λ	1	0
	Oracle	BLEU 27.05 27.35 AP 0.55 0.58 AL 1.55 2.03 DAL 4.14 4.57
		τ	0.8	0.7	0.6	0.5	0.4	0.3	0.2	0.1
	Dynamic λ = 1	BLEU 17.48 23.19 27.27 28.80 29.37 29.58 29.55 29.73 AP 0.48 0.55 0.60 0.62 0.64 0.66 0.68 0.72 AL -1.41 0.34 1.65 2.18 2.62 3.00 3.48 4.23 DAL 2.43 2.97 3.43 3.73 4.07 4.44 4.93 5.73
		τ	0.8	0.7	0.6	0.5	0.4	0.3	0.2	0.1
	Dynamic λ = 0	BLEU 27.92 28.69 28.89 29.29 29.43 29.59 29.62 29.59 AP 0.59 0.61 0.63 0.64 0.66 0.68 0.71 0.75 AL 1.63 2.03 2.35 2.65 3.02 3.46 4.06 4.95 DAL 3.02 3.41 3.76 4.09 4.45 4.90 5.50 6.45

Table D .

 D 19: IWSLT'15 En )Vi: numerical results of panel (l) in Figure 4.14.

(2) Assuming the maps F n surrounded by the residual connections maintain their inputs' variance, then this multiplier guarantees the variance remains the same after the summation.

(4) http://www.statmt.org/wmt16/translation-task.html(5) http://www.statmt.org/wmt15/translation-task.html

Acknowledgments

we showed the potential of Pervasive Attention models in the task of online translation, not only under deterministic policies where we can easily optimize multiple decoding paths, but also with dynamic decoding agents supervised with likelihood-based oracles. The grid-nature of the features in Pervasive Attention allows for encoding all the paths at once which leads to an easier comparison between paths and a straight-forward optimization of multiple decoding paths. With our Pervasive attention based dynamic agents we were able to outperform or match the offline models on IWSLT'14 De↔En and IWSLT'15 En↔Vi with up to 70% less lagging.

Chapter 5

Cost Effective Decoding

In this chapter we introduce our anytime structured prediction models for Neural Machine Translation. We prepare Transformer models for anytime prediction i.e. yielding an output at different stages of the network with classifiers plugged at multiple exit points. We propose a number of different halting mechanisms to predict the required network depth and train them under the supervision of oracles. We obtain promising trade-offs between speed and accuracy reducing the computational cost by up to 75% without hindering the translation's quality.

The contributions presented in this chapter are published in: Maha Elbayad, Jiatao Gu, Edouard Grave, and Michael Auli. Figure 5.1: Transformer decoder: dependencies through-time (in blue), characteristic of the self-attention sub-block, require the outputs of the previous layer at earlier steps. A decoder block between two consecutive representations is developed on the side. The additional input for the encoder-decoder attention is the sequence of source hidden states s = (s 1 , . . . , s |x| ).

schemes for training these classifiers, aligned ( §5.2.2) and mixed ( §5.2.3). We will then explore a few variations of loss scaling and gradient manipulation to improve the overall performance of the model in §5.2.4.

Transformer with Intermediate Classifiers

Recall from §2.6.3 that a Transformer model [START_REF] Vaswani | Attention Is All You Need[END_REF] has N stacked blocks in both the encoder and decoder branches. Each block has several sub-blocks surrounded by residual skip-connections. The first sub-block is a multi-head dot-product self-attention and the second a position-wise fully connected feed-forward network. For the decoder, there is an additional sub-block after the self-attention to add source context via another multi-head attention. A decoder block is illustrated in Figure 5.1.

Let (x, y) be a pair of source-target sequences. The source x is processed with the encoder yielding a sequence of representations s = (s 1 , . . . , s |x| ). Next, the decoder generates y step-by-step. For every new token y t input to the decoder, the N decoder blocks process it CHAPTER 5. COST EFFECTIVE DECODING

Balancing the Losses

Sensitivity to the weights. Prior work in computer vision studied the effect of the weights (ω n ) 1≤n≤N on the quality of the classifiers [START_REF] Surat Teerapittayanon | Branchynet: Fast Inference via Early Exiting from Deep Neural Networks[END_REF][START_REF] Huang | Multi-scale Dense Convolutional Networks for Efficient Prediction[END_REF][START_REF] Hu | Learning Anytime Predictions in Neural Networks via Adaptive Loss Balancing[END_REF], each reaching a different conclusion. In this work, we consider five different constant scales for the aligned training: ω n = 1/N i.e. equally weighted losses, ω n ∝ n and ω n ∝ n 1/2 assigning higher weights to later exits and ω n ∝ n -1/2 and ω n ∝ n -1 assigning more weights to the early exits.

We empirically found that uniform weights achieve higher accuracies on average compared to the other weighting schemes that tend to favor a range of exits (see §5.4.2).

Manipulating the gradients. Two major concerns arise from the joint training of N classifiers plugged at varying depths of the same neural network. The first is that early classifiers receive early, close to raw, features leading to larger losses and consequently larger gradients. The second concern is that subsets of the model's parameters receive more training signals than other. In fact, the first block is trained by N loss terms while the last block is optimized by a single loss term. With these two factors, the parameters of block n , denoted with θ n wind up possessing much larger gradients in comparison to the subsequent blocks.

To balance the gradients of each block in the decoder, we regulate the gradients due to each loss term as they back-propagate through different sections of the computation graph.

Let us consider an aligned training with equal weights (ω n = 1/N). When updating θ n , the parameters of the n-th block, we use the compound gradients:

(5.8)

We are interested in calibrating the ratio of the n-th gradient to the subsequent N-n gradients when updating θ n . To this end, we scale the gradient ∇ θn NLL(n) by γ n = γ(Nn) during the update of θ n . Note that this scaling only affects θ n as we revert back to the normal scale before back-propagating to the previous blocks. The choice γ n = γ(Nn) allows us to tune the aforementioned ratio at γ:1. Figure 5.4 illustrates the computation graph under gradient manipulation. In Algorithm 2 we show how this gradient manipulation is practically achieved

Experiments

In this section we first evaluate our methods for training a Transformer model with multiple output classifiers then compare the different models for adaptive depth estimation. Initial experiments were run on IWSLT'14 En )De and our contributions were then validated on the large benchmark of WMT'14 En )Fr. and tst2010-2013. We tokenized and lower-cased all data using the standard scripts from the Moses toolkit [START_REF] Koehn | Moses: Open Source Toolkit for Statistical Machine Translation[END_REF]. For open-vocabulary translation, we segment sequences using byte pair encoding with 10K merge operations on the merged bi-texts. This results in a German and English vocabularies of around 8.8K and 6.6K types respectively.

Experimental Setup

We train a small variant of Transformer with N = 6 blocks in the encoder and decoder, n H = 4 attention heads and a per-position feed-forward network with d FF = 1024. We set the dropout rate to p drop = 0.3. exit is given a large weight, its performance is worse than a baseline with a single decoder block i.e. the deep supervision hurts the first block. Our conclusions on the first block do not translate to the other early exits n = 2 or n = 3. These exits are barely affected by the weight shifting from early to late. Adding more weight to the late exits improves their performance by up to 0.3 BLEU points. However, this comes at the cost of the early classifiers where we loose up to 2 BLEU points. A possible explanation of this dynamic is that, unlike with convolutions, the first block can abruptly compute sequence-level features from the granular token embeddings with unbounded self-attention. If a classifier is put on top of the first block, then its features have to be coarse to improve the classifier's accuracy. If optimized w.r.t. late supervision, the first self-attention can choose to compute finer features.

Gradient manipulation. Recall that with gradient manipulation we regulate at γ : 1 the ratio of the n-th gradient to the subsequent N-n gradients before updating the parameters of the n-th block. With that, γ > 1 favors the block's own classifier when updating its parameters and γ < 1 relies on deeper signal.

Table 5.4 shows that γ = 1.1 benefits the first exit, achieving the highest BLEU so far with a single block, to the detriment of later exits. Once more, similar to loss balancing, optimizing with regular, unaffected gradients has the best performance on average.

Adaptive Depth Estimation

Next, we train models with adaptive depth estimation, all initialized with an aligned model with equal weights. These models are compared in terms of accuracy (BLEU) and com- putational cost. We measure the latter as the average exit per output token (AE). We average at the corpus level and so, for sequence-specific depth, the exit is weighted with the length of the hypothesis y. As baselines we use again six separate standard Transformers with N ∈ [1..6] with a single output classifier. We also include the scores of the pre-trained anytime prediction model for fixed exits n ∈ [1..6]. The BLEU scores of these two baselines are additionally reported in Table 5.5.

We train the six combinations described in Table 5.1 with different hyper-parameters λ and σ when relevant. These hyper-parameters are tuned on the development set for a range of budgets, we specifically partition the full range of costs [1, 6] into 0.5-wide segments. At the end, we report results on the test set. For token specific halting mechanisms, the geometric-like classifiers in Figure 5.6b achieve

Appendices

Appendix A

ConvNet's activations and skip-connections

In this appendix we analyze the impact of the skip connections on Pervasive Attention. We first compare the convergence speed in To better understand the improvement achieved with cumulative skip connections, we profile the activations within the ConvNet using either standard residual skip connections or the cumulative and gated variant. For each model, we forward the development set in batches and in teacher-forcing mode. For each batch, we evaluate the mean and standard deviation of the activations at multiple points of the architecture then report the mean of the means and deviations at the corpus level. We observe that the variance of the final features APPENDIX A. CONVNET'S ACTIVATIONS AND SKIP-CONNECTIONS

with accumulated outputs is higher than with standard residual skip connections i.e. the classifier's input is more separable as it occupies a larger space. We can also visualise the lesser importance accorded to mid-level features in both the gated (forward) and cumulative

ConvNets. The features' profile is U-shaped with the activations getting larger as we approach the end of the ConvNet which means that the nearest and earliest (input embeddings) set of features are more important and contribute more to the input of the upcoming layer.

Appendix B FLOPs approximation

Timing the decoding is a noisy estimation of the speedup we can achieve with adaptive depth estimation. With a large batch size applying the same operator on a large matrix is faster on GPU than different operators applied to chunks of the same matrix. With adaptive exits samples within a batch are split depending on the chosen exit, hence we apply different operators to smaller matrices. Indexing and splitting also causes a slight overhead. To abstract away from the indirect costs of computation, we resort to counting the theoretical amount of floating point operations (FLOPs). This section details the computation of the FLOPs we report in §5.4.4. The per token FLOPs are for the decoder network only since we use an encoder of the same size for all models. We breakdown the FLOPs of every operation in Algorithm 3. We omit non-linearities, normalizations and residual connections with a first order cost. The main operations we account for are dot-products and by extension matrix-vector products since those represent the vast majority of FLOPs .

Parameters With this breakdown, the total computational cost at time-step t of a decoder block that APPENDIX B. FLOPS APPROXIMATION we actually go through, denoted with FC, is:

where the cost of mapping the source's keys and values is incurred the first time the block is called (flagged with FirstCall). This occurs at t = 1 for the baseline model but it is input-dependent with depth adaptive estimation and may never occur if all tokens exit early.

If skipped, a block still has to compute the keys and value of the self-attention block so the self-attention of future time-steps can function. We will denote this cost with FS and we have FS = 4d 2 dec . Depending on the halting mechanism, an exit prediction cost, denoted with FP, is added:

For a set of source sequences {x (i) } i∈I and generated hypotheses {y (i) } i∈I , the average flops per token is: Baseline (N blocks):

Adaptive depth:

In the case of confidence thresholding the final output prediction cost (2|V|d dec ) is already accounted for in the exit prediction cost FP.

Algorithm 3 Adaptive decoding with a geometric-like exit distribution 1: Input: source codes s, incremental state 2:

A flag signaling if s's keys and values should be evaluated. 5: end for 6: while y t = </s> do 7:

Embed the last output token y t .

8:

for n ∈ [1..N] do 9:

Self-attention.

10:

-Map the input into a key (k) and value (v). FLOPS=4d 2 dec 11:

-Map the input into a query q. FLOPS=2d 2 dec 12:

-Score the memory keys with q to get the attention weights α. FLOPS=4td dec 13:

-Map the attention output. FLOPS=2d 2 dec 14:

Encoder-Decoder interaction. -Map the input into a query q. FLOPS=2d 2 dec 20:

-Score the memory keys with q to get the attention weights α. FLOPS=4|x|d dec 21:

-Map the attention output. FLOPS=2d if n < N -1 then 29:

Skipped blocks.

30:

for

Copy and map the copied state into a key (k) and value (v). FLOPS=4d We investigate in this section the cause of the negative lagging that wait-k decoders fall into especially when decoding along the wait-1 path. Both AL and DAL are interpreted as the source steps by which we lag behind an ideal translator with values between 0 and |x|.

However, in cases where the system finishes decoding prematurely before the full source |x| is read, the lagging can be negative (better than the ideal translator). For example with |x| = 2|y|, the terms z t -|x| |y| (t -1) on the wait-1 decoding path are equal to 2t making for an average lagging of 2 -|y|+1 2 , negative for any hypothesis with more than 3 tokens. In these scenarios the usually mediocre translation quality is paired with a better than ideal delay. trained with the finish reading condition perform comparably to simply evaluating standard wait-k models with evaluation-time finish reading. Both methods score a positive AL but the standard decoding achieves better quality-delay trade-offs; the standard approach with k eval = 3 has a comparable delay to finish reading models with k eval = 1 with considerably better translation quality (+3.21 with k = 1 and +5.3 with k = 3). Forcing decoders to finish reading yields predictably larger length-ratios (total system tokens / total reference tokens) which might explain the lower BLEU scores. On the other hand, models that finish reading are marginally better in the less interesting high latency region (AL > 4.5).

In chapter 4, we default to decoding and training along the standard wait-k paths without the finish reading condition.

The source's <s> and </s> markers. In offline sequence-to-sequence models, depending on the implementation, we either append an end of sequence marker to the source x or keep it as-is. Zheng et al. (2019b) uses OpenNMT [START_REF] Klein | OpenNMT: Open-Source Toolkit for Neural Machine Translation[END_REF] and mention that the addition of </s> to the source helped improve the training of their wait-k models. In Fairseq [START_REF] Ott | fairseq: A Fast, Extensible Toolkit for Sequence Modeling[END_REF], the source is encoded with </s> by default. When removing </s>, the accuracies across latency ranges fall by up to 8 BLEU points (not included in the graphs of regardless of their semantic proximity from the ground-truth target. While such a zero-one loss is probably acceptable for coarse grained classification of images, e.g. across a limited number of basic object categories [START_REF] Everingham | The Pascal Visual Object Classes (VOC) Challenge[END_REF] it becomes problematic as the output space becomes larger and some of its elements become semantically similar to each other. This is in particular the case for tasks that involve natural language generation (captioning, translation, speech recognition) where the number of possible outputs is practically unbounded.

For natural language generation tasks, evaluation measures typically do take into account structural similarity, e.g. based on n-grams, but such structural information is not reflected in the MLE criterion. The second limitation of MLE is that training is based on predicting the next token given the input and preceding ground-truth output tokens, while at test time the model predicts conditioned on the input and the so-far generated output sequence.

Given the exponentially large output space of natural language sentences, it is not obvious that the trained language model generalizes well beyond the relatively sparse distribution of ground-truth sequences used during MLE optimization. This phenomenon is known as exposure bias [START_REF] Marc | Sequence Level Training with Recurrent Neural Networks[END_REF][START_REF] Bengio | Scheduled Sampling for Sequence Prediction with Recurrent Neural Networks[END_REF].

MLE minimizes the KL divergence between a target Dirac distribution on the ground-truth sentence(s) and the model's distribution. In this work, we build upon the loss smoothing approach by [START_REF] Norouzi | Reward Augmented Maximum Likelihood for Neural Structured Prediction[END_REF], which smooths the Dirac target distribution over similar sentences, increasing the support of the training data in the output space. We make the following main contributions: a) We propose a token-level loss smoothing approach, using word-embeddings, to achieve smoothing among semantically similar terms, and we introduce a special procedure to promote rare tokens.

b) For sequence-level smoothing, we propose to use restricted token replacement vocabu-This loss can equivalently be expressed as the KL-divergence between a Dirac delta distribution centered on the target output (with δ a (x) = 1 at x = a and 0 otherwise) and the model's distribution, either at the sequence-level or at the token-level:

Loss smoothing approaches considered in this work consists in replacing the Dirac on the ground-truth sequence with distributions with larger support. These distributions can be designed in such a manner that they reflect which deviations from ground-truth predictions are preferred over others.

E.2.1 Sequence-level Loss Smoothing

The reward augmented maximum likelihood approach of [START_REF] Norouzi | Reward Augmented Maximum Likelihood for Neural Structured Prediction[END_REF] where r(y, y ) is a reward function that measures the quality of sequence y w.r.t. y , e.g. metrics used for evaluation of natural language processing tasks can be used, such as BLEU [START_REF] Papineni | BLEU: a Method for Automatic Evaluation of Machine Translation[END_REF] or CIDEr [START_REF] Ramakrishna Vedantam | CIDEr: Consensus-Based Image Description Evaluation[END_REF]. The temperature parameter τ controls the concentration of the distribution around y . When m > 1 groundtruth sequences are paired with the same input x, the reward function can be adapted to fit this setting and be defined as r(y, {y (1) , . . . , y (m) }). The sequence-level smoothed loss function is then given by

where the entropy term H(r(y | y * )) does not depend on the model parameters θ.

In general, expectation in Eq. (E.6) is intractable due to the exponentially large output space, and replaced with a Monte-Carlo approximation: Importance sampling. For a reward based on BLEU or CIDEr , we cannot directly sample from r(y | y ) since the normalizing constant, or partition function, of the distribution is intractable to compute. In this case we can resort to importance sampling. We first sample L sequences y l from a tractable proposal distribution q(y | y ). We then compute the importance weights

where r(y k | y ) is the un-normalized reward distribution in Eq. (E.5). We finally approximate the expectation by reweighing the samples in the Monte Carlo approximation as

(E.9)

In our experiments we use a proposal distribution based on the Hamming distance, which allows for tractable stratified sampling, and generates sentences that do not stray away from the ground truth.

We propose two modifications to the sequence-level loss smoothing of Norouzi et al.

(2016): sampling to a restricted vocabulary (described in the following paragraph) and lazy sequence-level smoothing (described in section E.2.3).

Restricted vocabulary sampling. In the stratified sampling method for Hamming and edit distance rewards, instead of drawing from the large vocabulary V, containing typically in the order of 10 4 words or more, we can restrict ourselves to a smaller subset V sub more adapted to our task. We considered three different possibilities for V sub .

a) V : the full vocabulary from which we sample uniformly (default), or draw from our token-level smoothing distribution defined below in Eq. (E.10).

b) V refs : uniformly sample from the set of tokens that appear in the ground-truth sentence(s) associated with the current input. c) V batch : uniformly sample from the tokens that appear in the ground-truth sentences across all inputs that appear in a given training mini-batch.

Uniformly sampling from V batch has the effect of boosting the frequencies of words that appear in many reference sentences, and thus approximates to some extent sampling substitutions from the uni-gram statistics of the training set.

E.2.2 Token-level Loss Smoothing

While the sequence-level smoothing can be directly based on performance measures of interest such as BLEU or CIDEr, the support of the smoothed distribution is limited to the number of samples drawn during training. We propose smoothing the token-level Diracs δ y t in Eq. (E.4) to increase its support to similar tokens. Since we apply smoothing to each of the tokens independently, this approach implicitly increases the support to an exponential number of sequences, unlike the sequence-level smoothing approach. This comes at the price, however, of a naive token-level independence assumption in the smoothing.

We define the smoothed token-level distribution, similar as the sequence-level one, as a soft-max over a token-level reward function,

where τ is again a temperature parameter. As a token-level reward r(y t , y t ) we use the cosine similarity between y t and y t in a semantic word-embedding space. In our experiments we use GloVe [START_REF] Pennington | GloVe: Global Vectors for Word Representation[END_REF]; preliminary experiments with word2vec (Mikolov et al., 2013a) yielded somewhat worse results.

Promoting rare tokens. We can further improve the token-level smoothing by promoting rare tokens. To do so, we penalize frequent tokens when smoothing over the vocabulary, by subtracting β freq(y t ) from the reward, where freq(•) denotes the term frequency and β is a non-negative weight. This modification encourages frequent tokens into considering the rare ones. We experimentally found that it is also beneficial for rare tokens to boost frequent where the penalty term is strongest if both tokens have similar frequencies.

E.2.3 Combining Losses

In both loss smoothing methods presented above, the temperature parameter τ controls the concentration of the distribution. As τ gets smaller the distribution peaks around the ground-truth, while for large τ the uniform distribution is approached. We can, however, not separately control the spread of the distribution and the mass reserved for the ground-truth output. We therefore introduce a second parameter α ∈ [0, 1] to interpolate between the Dirac on the ground-truth and the smooth distribution. Using ᾱ = 1α, the sequence-level and token-level loss functions are then defined as

To benefit from both sequence-level and token-level loss smoothing, we also combine them by applying token-level smoothing to the different sequences sampled for the sequence-level smoothing. We introduce two mixing parameters α 1 and α 2 . The first controls to what extent sequence-level smoothing is used, while the second controls to what extent token-level smoothing is used. The combined loss is defined as

In our experiments, we use held out validation data to set mixing and temperature parameters.

Lazy sequence smoothing. Although sequence-level smoothing is computationally efficient compared to reinforcement learning approaches [START_REF] Marc | Sequence Level Training with Recurrent Neural Networks[END_REF][START_REF] Rennie | Self-Critical Sequence Training for Image Captioning[END_REF], it is slower compared to MLE. In particular, we need to forward each of the samples y l in Algorithm 4 Sequence-level smoothing algorithm

Input: x, y . Output: α seq (y , x). Encode x. Forward y in the graph to compute the hidden states h t . Compute the MLE loss MLE (y , x).

Forward y l in the graph to get its hidden states

the decoder in teacher-forcing mode so as to compute its hidden states h l t , which are used to compute the sequence MLE loss as

To speed up training, and since we already forward the ground truth sequence in the decoder to evaluate the MLE part of α Seq (y , x), we propose to use the same hidden states h t to compute both the MLE and the sequence-level smoothed loss. In this case:

In this manner, we only have a single instead of L + 1 decoder forwards-passes. We provide the pseudo-code for training in Algorithm 4.

E.3 Experiments

In this section, we compare sequence prediction models trained with maximum likelihood (MLE) with our token and sequence-level loss smoothing on two different tasks: image captioning and machine translation. Our methods are architecture-independent, and so, report CIDEr and BLEU scores on this internal test set. We also report results obtained on the official MS-COCO server that additionally measures METEOR [START_REF] Denkowski | Meteor Universal: Language Specific Translation Evaluation for Any Target Language[END_REF] and ROUGE-L [START_REF] Lin | ROUGE: A Package for Automatic Evaluation of Summaries[END_REF].

We experiment with both non-attentive LSTMs [START_REF] Vinyals | Show and Tell: A Neural Image Caption Generator[END_REF] and the ResNet baseline of the state-of-the-art top-down attention [START_REF] Anderson | Bottom-Up and Top-Down Attention for Image Captioning and Visual Question Answering[END_REF]. The MS-COCO vocabulary consists of 9,800 words that occur at least 5 times in the training set.

E.3.1.2 Results and discussion

Restricted vocabulary sampling. In this section, we evaluate the impact of the vocabulary subset from which we sample the modified sentences for sequence-level smoothing. We experiment with two rewards: CIDEr , which scores w.r.t. all five available reference sentences, and Hamming distance reward taking only a single reference into account. For each reward we train our (Seq) models with each of the three subsets previously described V,

V refs and V batch .

From the results in Table E.1 we note that for the inattentive models, sampling from V refs or V batch has a better performance than sampling from the full vocabulary on all metrics. In fact, using these subsets introduces a useful bias to the model and improves performance.

E.3. EXPERIMENTS 195

This improvement is most notable using the CIDEr reward that scores candidate sequences w.r.t. to multiple references, which stabilizes the scoring of the candidates.

With an attentive decoder, no matter the reward, re-sampling sentences with words from V ref rather than the full vocabulary V is better for both reward functions, and all metrics.

Lazy training. From the results of Table E.1, we see that lazy sequence-level smoothing is competitive with exact non-lazy sequence-level smoothing, while requiring roughly equivalent training time as MLE.

Overall. For reference, we include in Table E.1 baseline results obtained using MLE, and our implementation of MLE with entropy regularization (MLE+γH) [START_REF] Pereyra | Regularizing Neural Networks by Penalizing Confident Output Distributions[END_REF], as well as the RAML approach of [START_REF] Norouzi | Reward Augmented Maximum Likelihood for Neural Structured Prediction[END_REF] which corresponds to sequence-level smoothing based on the Hamming reward and sampling replacements from the full vocabulary (Seq, Hamming, V)

We observe that entropy smoothing is not able to improve performance much over MLE for the model without attention, and even deteriorates for the attention model. We improve upon RAML by choosing an adequate subset of vocabulary for substitutions. We also report the performances of token-level smoothing, where the promotion of rare tokens boosted the scores in both attentive and non-attentive models. For sequence-level smoothing, choosing a task-relevant reward with importance sampling yielded better results than plain Hamming distance. Moreover, we used the two smoothing schemes (Tok-Seq) and achieved the best results with CIDEr as a reward for sequence-level smoothing combined with a token-level smoothing that promotes rare tokens improving CIDEr from 93.59 (MLE) to 99.92 for the model without attention, and improving from 101.63 to 103.81 with attention.

Qualitative results. In Figure E.1 we showcase captions obtained with MLE and our three variants of smoothing i.e. token-level (Tok), sequence-level (Seq) and the combination (Tok-Seq). We note that the sequence-level smoothing tend to generate lengthy captions overall, which is maintained in the combination. On the other hand, the token-level smoothing allows for a better recognition of objects in the image that stems from the robust training of the classifier e.g. the carrots in the second example or the 'cement block' in the third one.

APPENDIX E. LOSS SMOOTHING FOR LANGUAGE MODELS

Ground truth:

1) an airplane on the tarmac and the glass passageway leading to its door 2) a commercial airplane hooked up to a gate at the airport 3) a jumbo jet plane with a boarding walkway attached to it 4) an airplane sitting at the gate of an airport 5) a large plain is at a airport terminal Generated:

-Baseline: a plane is parked on the side of the road -Seq: an airplane is parked on the runway at the airport -Tok: an airplane sitting on the tarmac at an airport -Tok-Seq: a large airplane sitting on top of an airport tarmac

Ground truth: 1) carrots, grapes, cheese, bread and butter in a plastic container 2) some different foods are laying out on a table 3) a tray with bread, cheese, fruits and vegetables 4) the lunch provides all the major food groups 5) a trey with some fruit inside of it Generated:

-Baseline: a tray with a variety of foods in it -Seq: a tray with a variety of fruits and vegetables -Tok: a lunch box with carrots carrots and carrots -Tok-Seq: a tray of food that includes a sandwich and some vegetables

Ground truth: 1) a child on a skateboard is performing a trick on a slab 2) a man that is standing on a skateboard on wood 3) a kid riding a skateboard across a couple of blocks 4) a person on a skateboard on a wooden rail 5) a kid that is skateboarding on some wood block Generated:

-Baseline: a man riding a skateboard down a sidewalk -Seq: a man riding a skateboard down a sidewalk -Tok: a man riding a skateboard on top o a cement block -Tok-Seq: a man riding a skateboard down a wooden bench Comparison to the state of the art. We compare our model to state-of-the-art systems on the MS-COCO evaluation server in Table E.2. We submitted a single model (Tok-Seq,

CIDEr , V refs ) as well as an ensemble of five models with different initializations trained on the training set plus 35k images from the dev set (a total of 117k images) to the MS-COCO server. The three best results on the server [START_REF] Rennie | Self-Critical Sequence Training for Image Captioning[END_REF]Yao et al., 2017b;[START_REF] Anderson | Bottom-Up and Top-Down Attention for Image Captioning and Visual Question Answering[END_REF] are trained in two stages where they first train using MLE, before switching to policy gradient methods based on CIDEr. [START_REF] Anderson | Bottom-Up and Top-Down Attention for Image Captioning and Visual Question Answering[END_REF] reported an increase of 5.8% of CIDEr on the test split after the CIDEr optimization. Moreover, Yao et al. (2017b) uses additional information about image regions to train the attributes classifiers, while [START_REF] Anderson | Bottom-Up and Top-Down Attention for Image Captioning and Visual Question Answering[END_REF] pre-trains its bottom-up attention model on the Visual Genome dataset [START_REF] Krishna | Visual Genome: Connecting Language and Vision Using Crowdsourced Dense Image Annotations[END_REF] For this task we validate the effectiveness of our approaches on two different datasets. The first is WMT'14 English to French, in its filtered version, with 12M sentence pairs obtained after dynamically selecting a "clean" subset of 348M words out of the original "noisy" 850M words [START_REF] Bahdanau | Neural Machine Translation by Jointly Learning to Align and Translate[END_REF][START_REF] Cho | Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation[END_REF][START_REF] Sutskever | Sequence to Sequence Learning with Neural Networks[END_REF]. The second benchmark is IWSLT'14 German to English consisting of around 150k pairs for training. In all our experiments we use the attentive model of [START_REF] Bahdanau | Neural Machine Translation by Jointly Learning to Align and Translate[END_REF] To assess the translation quality we report the BLEU-4 metric.

Source I think it's conceivable that these data are used for mutual benefit. Target J'estime qu'il est concevable que ces données soient utilisées dans leur intérêt mutuel. MLE Je pense qu'il est possible que ces données soient utilisées à des fins réciproques. Tok-Seq Je pense qu'il est possible que ces données soient utilisées pour le bénéfice mutuel.

Source

However, given the ease with which their behaviour can be recorded, it will probably not be long before we understand why their tails sometimes go one way, sometimes the other. Target Toutefois, étant donné la facilité avec laquelle leurs comportements peuvent être enregistrés, il ne faudra sûrement pas longtemps avant que nous comprenions pourquoi leur queue bouge parfois d'un côté et parfois de l'autre. MLE Cependant, compte tenu de la facilité avec laquelle on peut enregistrer leur comportement, il ne sera probablement pas temps de comprendre pourquoi leurs contemporains vont parfois une façon, parfois l'autre. Tok-Seq Cependant, compte tenu de la facilité avec laquelle leur comportement peut être enregistré, il ne sera probablement pas long avant que nous ne comprenons la raison pour laquelle il arrive parfois que leurs agresseurs suivent un chemin, parfois l'autre.

Source

The public will be able to enjoy the technical prowess of young skaters, some of whom, like Hyeres' young star, Lorenzo Palumbo, have already taken part in top-notch competitions.

Target

Le public pourra admirer les prouesses techniques de jeunes qui, pour certains, fréquentent déjà les compétitions au plus haut niveau, à l'instar du jeune prodige hyérois Lorenzo Palumbo.

MLE

Le public sera en mesure de profiter des connaissances techniques des jeunes garçons, dont certains, à l'instar de la jeune star américaine, Lorenzo, ont déjà participé à des compétitions de compétition. Tok-Seq Le public sera en mesure de profiter de la finesse technique des jeunes musiciens, dont certains, comme la jeune star de l'entreprise, Lorenzo, ont déjà pris part à des compétitions de gymnastique.

E.4 Related Work

Previous work aiming to improve the generalization performance of conventional language models can be roughly divided into three categories: those based on regularization, data augmentation, and alternatives to maximum likelihood estimation.

Regularization techniques are used to increase the smoothness of the function learned by E.4. RELATED WORK 199 the network, e.g. by imposing an 2 penalty on the network weights, also known as weight decay. More recent approaches mask network activations during training, as in dropout [START_REF] Srivastava | Dropout: A Simple Way to Prevent Neural Networks from Overfitting[END_REF] and its variants adapted to recurrent models [START_REF] Vu Pham | Dropout Improves Recurrent Neural Networks for Handwriting Recognition[END_REF][START_REF] Krueger | Zoneout: Regularizing RNNs by Randomly Preserving Hidden Activations[END_REF]. Instead of masking, batch-normalization [START_REF] Ioffe | Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift[END_REF] rescales the network activations to avoid saturating the network's non-linearities. Instead of regularizing the network parameters or activations, it is also possible to directly regularize based on the entropy of the output distribution [START_REF] Pereyra | Regularizing Neural Networks by Penalizing Confident Output Distributions[END_REF].

Data augmentation techniques improve the robustness of the learned models by applying transformations that might be encountered at test time to the training data. In computer vision, this is common practice, and implemented by, e.g., scaling, cropping, and rotating training images [START_REF] Lecun | Gradient-based Learning Applied to Document Recognition[END_REF][START_REF] Krizhevsky | ImageNet Classification with Deep Convolutional Neural Networks[END_REF][START_REF] Paulin | Transformation Pursuit for Image Classification[END_REF]. In natural language processing, examples of data augmentation include input noising by randomly dropping some input tokens [START_REF] Iyyer | Deep Unordered Composition Rivals Syntactic Methods for Text Classification[END_REF][START_REF] Samuel | Generating Sentences from a Continuous Space[END_REF][START_REF] Kumar | Ask me anything: Dynamic memory networks for natural language processing[END_REF], and randomly replacing words with substitutes sampled from the model [START_REF] Bengio | Scheduled Sampling for Sequence Prediction with Recurrent Neural Networks[END_REF]. [START_REF] Xie | Data Noising as Smoothing in Neural Network Language Models[END_REF] introduced data augmentation schemes for RNN language models that leverage n-gram statistics in order to mimic Kneser-Ney smoothing of n-grams models. In the context of machine translation, [START_REF] Fadaee | Data Augmentation for Low-Resource Neural Machine Translation[END_REF] modify sentences by replacing words with rare ones when this is plausible according to a pre-trained language model, and substitutes its equivalent in the target sentence using automatic word alignments. This approach, however, relies on the availability of additional monolingual data for language model training.

The de facto standard way to train RNN language models is maximum likelihood estimation (MLE) [START_REF] Cho | Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation[END_REF][START_REF] Sutskever | Sequence to Sequence Learning with Neural Networks[END_REF][START_REF] Bahdanau | Neural Machine Translation by Jointly Learning to Align and Translate[END_REF]. The sequential factorization of the sequence likelihood generates an additive structure in the loss, with one term corresponding to the prediction of each output token given the input and the preceding ground-truth output tokens. In order to directly optimize for sequence-level structured loss In order to avoid early convergence to poor local optima, they pre-train the model using MLE. [START_REF] Leblond | SeaRnn: Training RNNs with Global-Local Losses[END_REF] build on the learning to search approach to structured prediction [START_REF] Daumé | Search-Based Structured Prediction[END_REF][START_REF] Chang | Learning to Search Better than Your Teacher[END_REF] and adapts it to RNN training. The model generates candidate sequences at each time-step using all possible tokens, and scores these at sequencelevel to derive a training signal for each time step. This leads to an approach that is structurally close to MLE, but computationally expensive. In our work, we build upon the work of [START_REF] Norouzi | Reward Augmented Maximum Likelihood for Neural Structured Prediction[END_REF] by proposing improvements to sequence-level smoothing, and extending it to token-level smoothing. Our token-level smoothing approach is related to the label smoothing approach of [START_REF] Szegedy | Rethinking the Inception Architecture for Computer Vision[END_REF] for image classification. Instead of maximizing the probability of the correct class, they train the model to predict the correct class with a large probability and all other classes with a small uniform probability. This regularizes the model by preventing over-confident predictions. In natural language generation with large vocabularies, preventing such narrow over-confident distributions is imperative, since for many tokens there are nearly interchangeable alternatives.

E.5 Conclusion

We investigated the use of loss smoothing approaches to improve over maximum likelihood estimation of RNN language models. We generalized the sequence-level smoothing RAML approach of [START_REF] Norouzi | Reward Augmented Maximum Likelihood for Neural Structured Prediction[END_REF] to the token-level by smoothing the ground-truth target across semantically similar tokens. For the sequence-level, which is computationally expensive, we introduced an efficient lazy evaluation scheme, and introduced an improved re-sampling strategy. Experimental evaluation on image captioning and machine translation demonstrates the complementarity of sequence-level and token-level loss smoothing, improving over both the maximum likelihood and RAML.