Neural networks architectures have been applied to a myriad of tasks in Natural Language Processing (NLP), mainly since the success they met following their early application to language modeling. Language models are an important component in many NLP tasks, where they provide prior knowledge on the language used. However, the cost of training a neural language model grows linearly with the number of words it considers -the number of words in the vocabulary -which makes training very large-vocabulary neural language models a difficult task. Another observation made on neural language models is that they are generally less effective on rare words than discrete models. This issue is linked to the size of the vocabulary; indeed, the particular repartition of word counts in a text (namely, its Zipfian shape) means we systematically encounter a large number of infrequent words in our corpus, number that will grow with the size of the vocabulary. This is of course even more impactful for languages with rich morphologies. Besides, since each word is associated to a particular representation, there is no relation between words that share morphological caracteristics. xix B.2 Test perplexity averaged on 5 models trained with NCE, for various input representations and output word look-up table sizes. Corresponding vocabulary sizes are given in Table 5.3a. Test perplexities are given for all words, frequent words (frequency > 10) and rare words (frequency < 10). . . . . . . . . . . . . .

This work investigates practical methods to ease training and improve performances of neural language models with large vocabularies. Despite several training tricks, the most straightforward way to limit computation time is to limit the vocabulary size, which is not a satisfactory solution for numerous tasks. Most of the existing methods used to train large-vocabulary language models revolve around avoiding the computation of the partition function, ensuring that output scores are normalized into a probability distribution. Here, we focus on sampling-based approaches, including importance sampling and noise contrastive estimation. These methods allow an approximate computation of the partition function. After examining the mechanism of self-normalization in noise-contrastive estimation, we first propose to improve its efficiency with solutions that are adapted to the inner workings of the method and experimentally show that they considerably ease training. Our second contribution is to expand on a generalization of several sampling based objectives as Bregman divergences, in order to experiment with new objectives. We use Beta divergences to derive a set of objectives from which noise contrastive estimation is a particular case.

Finally, we aim at improving performances on full vocabulary language models, by augmenting output words representation with subwords. We experiment on a Czech dataset and show that using character-based representations besides word embeddings for output representations gives better results. We also show that reducing the size of the output look-up table improves results even more.

Résumé

Les méthodes neuronales ont été appliquées avec succès à de nombreuses tâches en traitement automatique du langage (TAL) depuis leur application aux modèles de langues. Ceux-ci demeurent des composants particulièrement importants dans de nombreux systèmes de TAL, apportant des connaissances préalables sur la langue utilisée. Cependant, le coût d'entraînement des modèles de langues neuronaux augmente linéairement avec le nombre de mots qu'il considère -c'est à dire la taille de son vocabulaire -ce qui rend l'entraînement des modèles à grand vocabulaire difficile. De plus, les modèles de langues neuronaux sont en général moins efficaces sur les mots rares que les modèles discrets. Ce problème est lié à la taille du vocabulaire; en effet, la répartition des fréquences des mots dans un texte (qu'on appelle Zipfienne) implique que le nombre de mots rares dans un corpus sera systématiquement élevé. Ce phénomène a un impact plus important pour les langues à la morphologie riche. De plus, puisque chaque mot est associé à une représentation particulière, aucun usage n'est fait des similitudes morphologiques que partagent certains mots.

Le travail présenté dans cette thèse explore les méthodes pratiques utilisées pour faciliter l'entraînement et améliorer les performances des modèles de langues munis de très grands vocabulaires. La principale limite à l'utilisation des modèles de langue neuronaux est leur coût computationnel: il dépend de la taille du vocabulaire avec laquelle il grandit linéairement. La façon la plus aisée de réduire le temps de calcul de ces modèles reste de limiter la taille du vocabulaire, ce qui est loin d'être satisfaisant pour de nombreuses tâches. La plupart des méthodes existantes pour l'entraînement de ces modèles à grand vocabulaire évitent le calcul de la fonction de partition, qui est utilisée pour forcer la distribution de sortie du modèle à être normalisée en une distribution de probabilités. Ici, nous nous concentrons sur les méthodes à base d'échantillonnage, dont le sampling par importance et l'estimation contrastive bruitée. Ces méthodes permettent de calculer facilement une approximation de cette fonction de partition. L'examen des mécanismes de l'estimation contrastive bruitée nous permet de proposer des solutions qui vont considérablement faciliter l'entraînement, ce que nous montrons expérimentalement. Ensuite, nous utilisons la généralisation d'un ensemble d'objectifs basés sur l'échantillonnage comme divergences de Bregman pour expérimenter avec de nouvelles fonctions objectif.

Enfin, nous exploitons les informations données par les unités sous-mots pour enrichir les représentations en sortie du modèle. Nous expérimentons avec différentes architectures, sur le Tchèque, et montrons que les représentations basées sur les caractères permettent l'amélioration des résultats, d'autant plus lorsque l'on réduit conjointement l'utilisation des représentations de mots.

Je voudrais tout d'abord remercier Alexandre, qui a dirigé mon stage, puis ma thèse. J'ai eu la chance de bénéficier de ses encouragements et de ses conseils, en matière de recherche, d'enseignement, et de tout ce qui concerne de près ou de loin le travail d'un doctorant, pendant plus de 4 ans. Sa disponibilité et son appui, ainsi que nos discussions, ont été déterminants pour la réalisation de cette thèse.

Je voudrais ensuite remercier les membres du jury, qui ont accepté de participer à l'évaluation de ce travail, et les rapporteurs, pour leur relecture et leurs avis. Particulièrement, merci à Pierre, pour ses remarques et conseils.

Le LIMSI a été un environnement de travail on ne peut plus plaisant pendant ces années de thèse, et ce grâce aux membres des groupes TLP et ILES. D'abord, merci à Lauriane, avec qui j'ai eu la chance de partager un bureau pendant plusieurs années, et Franck, avec qui j'ai partagé beaucoup de pauses qui finissaient invariablement en discussion sur la dernière architecture neuronale à la mode. Les réunions autour du thême traduction ont été mes premiers pas dans la communauté scientifique; je tiens à en remercier les membres, mais tout particulièrement François et Guillaume pour les nombreux articles, toujours très intéressants, que j'ai pu lire grâce à eux, et pour toutes les problématiques que j'ai découvert durant ces groupes de lectures. Les doctorants qui m'ont précédé au sein de ce thême ont aussi ma gratitude: pour leurs conseils et leur aide, merci à Nicolas, Khanh, Benjamin et Yong. J'ai beaucoup aimé partager le quotidien des doctorants du LIMSI; Qu'elle ai été régulière ou plus épisodique, la compagnie de Pierre, d'Elena, de Julia et de Kevin a toujours été enrichissante. Merci aussi aux doctorants que j'ai vu arriver; Rachel, Pooyan, Yuming, Swen, Arnaud, pour le temps passé ensemble et les discussions, scientifiques ou non -et Charlotte, même si elle a su résister à l'attrait d'une thèse. Enfin, j'ai été très content de rencontrer et de passer du temps avec Aina, Syrielle, Benjamin, José et Aman, qui ont commencé leurs thèses alors que je profitais d'une prolongation, sans oublier Margot, qui l'a commencé juste après.

De nombreux membres permanents du Limsi m'ont aidé à comprendre un peu mieux le travail de chercheur et d'enseignant, et j'ai beaucoup apprécié les discussions que j'ai eu avec eux: merci à Thomas, Hélène, Hervé et Claude; et particulièrement à Marianna, pour les relations que j'ai pu nouer grâce à elle, et pour ses nombreux conseils pour l'après-thèse. Merci aussi à Leonardo et Jane, qui m'ont fait profiter de leur expérience de post-doctorants. Enfin, merci à Éric pour sa disponibilité, et à Laurence pour son aide -ainsi qu'à tous les autres membres du Limsi, à qui je dois ma gratitude.

Encore merci à Franck, Pooyan, et Syrielle, qui m'ont aidé à relire ce qui suit; à eux, à Lauriane, et à tous ceux avec qui nous avons pu passer un moment aux deux gares; et à Alexandre. Et bien sur, à ma famille et aux amis qui m'ont cotoyé, soutenu, supporté pendant ces 4 dernières années.

A Proofs on

List of Tables

Introduction

Neural networks architectures have been applied to a myriad of tasks in Natural Language Processing (NLP), mainly since the success they met following their early application to language modeling [START_REF] Schwenk | Connectionist language modeling for large vocabulary continuous speech recognition[END_REF]Bengio et al., 2003). Language models are an important component in many NLP tasks, where they provide prior knowledge on the language used. They attribute a probability to a sentence S, based on data upon which the language model is built. In language modeling, where words are the atomic units, a sentence S is a sequence of words:

S = (w 1 , . . . , w t , . . . , w |S| )
The representational power of language models is limited by how many words they have knowledge of: these words are listed in a finite vocabulary V. Usually, this vocabulary is built from the same data as the model. Hence, the language model can only represent (at most) the words that are present in the training data. The probability of S is written as:

P (S) = |S| i=1 P (w t |w 1 , . . . , w t-1 )
While probabilities given by discrete language models are based on the number of occurrences of a sequence in the training corpus, neural language models jointly learn continuous representations of words, which the model scores together. These continuous vectors, that we call embeddings, are distributed representations: the joint learning procedure of neural language models implies that embeddings are learned similar for words that have similar contexts, allowing for generalization across these contexts. The development of unsupervised methods to learn such representations [START_REF] Pascanu | On the difficulty of training recurrent neural networks[END_REF], of recurrent structures (Elman, 1990b;[START_REF] Mikolov | Recurrent neural network based language model[END_REF] -and their improvements [START_REF] Hochreiter | Long short-term memory[END_REF] -made neural architectures even more popular in NLP.

While neural language models can be used as stand-alone models, to compute the probabilities of or generate sequences of words, they are necessary to many sophisticated systems. Intuitively, improving a language model should also improve the metric associated to the task it is applied to. As a matter of fact, neural language models were applied with success to Automatic Speech Recognition (ASR) [START_REF] Schwenk | Neural network language models for conversational speech recognition[END_REF][START_REF] Schwenk | Continuous space language models[END_REF]Mnih and Hinton, 2009;[START_REF] Le | Structured output layer neural network language model[END_REF] and Statistical Machine Translation (SMT) [START_REF] Le | Continuous space translation models with neural networks[END_REF][START_REF] Schwenk | Large, pruned or continuous space language models on a gpu for statistical machine translation[END_REF][START_REF] Devlin | Fast and robust neural network joint models for statistical machine translation[END_REF][START_REF] Cho | Learning phrase representations using RNN encoder-decoder for statistical machine translation[END_REF], among many other tasks. For these tasks, a reduced vocabulary may consequently hinder performance -for example, with the recent task of neural machine translation, the translation performance decreases when the number of unknown words goes up (Cho et al., 2014a). For some tasks, a large vocabulary is necessary. Indeed, rare words may need to be represented: for example in named entity recognition, or any work on social media datasets, for which the vocabulary is very diverse due to spelling errors and informal, irregular or abbreviated words. Besides, these issues are even more pregnant for morphologically rich languages. We can take the example of Czech, which is a highly inflected language: the vocabularies generated from Czech data is far larger. For instance, the Czech words dnes, dnešní, dnešních, dnešku, dnesnímu, ... each have their own representation in a vocabulary, whereas in English, only a few words, among which today and current, would be represented. This shows the importance of being able to train large-vocabulary neural language models.

Training a neural language model is usually done by maximizing its likelihood on the data. This is maximum likelihood estimation (MLE). In practice, we minimize the negative log-likelihood (NLL):

N LL(S) = - |S| t=1 log P (w t |w 1 , . . . , w t-1 )
Computing this objective and its gradient is however slow and costly. Indeed, in order to compute the probability of the next word, we need to compute the score given by the model to each word in the associated vocabulary V and to normalize these scores, via a softmax layer. Thus, the cost of training grows linearly with |V|, which makes training very large-vocabulary language models a difficult task. Quite a few solutions have been proposed: hierarchical models modify the standard architecture of the output layer [START_REF] Morin | Hierarchical probabilistic neural network language model[END_REF]Mnih and Hinton, 2009;[START_REF] Le | Structured output layer neural network language model[END_REF]. Others, which only speed-up computation during training, approximate the training objective via sampling schemes. The most notable are importance sampling (Bengio andSénécal, 2003, 2008) and noise contrastive estimation [START_REF] Gutmann | Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics[END_REF][START_REF] Mnih | A fast and simple algorithm for training neural probabilistic language models[END_REF]. These approaches each have they own strenghs and weaknesses, but they seem to fall off for very large vocabularies [START_REF] Chen | Strategies for training large vocabulary neural language models[END_REF].

Another observation made on neural language models is that they are generally less effective on rare words than discrete models. This issue is linked to the size of the vocabulary; indeed, the particular repartition of word counts in a text (namely, its Zipfian shape) means we systematically encounter a large number of infrequent words in our corpus, number that will grow with the size of the vocabulary. This is of course even more impactful for languages with rich morphologies: the Czech words we used as examples previously are, for most of them, rare words. For these words, the number of occurences is never sufficient, and the weak generalization attained by using distributed representations does not help. Besides, since each word is associated to a particular representation, there is no relation between words that share morphological caracteristics. This implies that dnes, dnešní, dnešních and other related forms are learnt independently. To attain a better form of general-ization, language models can rely on subword units for input words, whether they are characters [START_REF] Kim | Character-aware neural language models[END_REF] or morphological features [START_REF] Botha | Compositional Morphology for Word Representations and Language Modelling[END_REF]. This also presents the advantage of vastly reducing the number of parameters needed to represent words.

In this context, the motivations for this work are twofold: first, we wish to facilitate training of large vocabulary neural language models. Secondly, we would like to improve the performances of neural language models when trained on a full vocabulary, which means that a non-negligeable number of words will be infrequent in the training data. This implies that we will work on standalone language models. We will verify their efficiency using an intrisic measure, the perplexity. We will work towards our first objective by reviewing existing strategies aiming at training large vocabularies neural language models; focusing on sampling-based methods, we will specifically analyze the inner workings of noise contrastive estimation and propose solutions to ease learning with this method. Finally, we will try to replace noise contrastive estimation and other sampling-based methods in a larger class of objective functions and experimentally explore some of them. To achieve our second objective, we will take interest in subword-based representations. In order to improve performances of neural language models on infrequent words, we will not only use them for representing input words, but also to augment output word representations.

This work is organized as follows: in Chapter 1, we review language models in general and particulary neural language models. We detail the architecture of feedforward and recurrent language models and how they are usually trained. After explaining the practical aspects of training neural language models, we outline the design choices we have made for the experiments presented subsequently. Chapter 2 describes various strategies to efficiently train large vocabularies language modelsmainly focusing on sampling-based approaches. The two main methods we discuss are importance sampling and noise contrastive estimation. In Chapter 3, we begin by extensively experimenting with the hyperparameters of importance sampling and noise contrastive estimation, as well as other related methods. In order to improve the efficiency of noise contrastive estimation, we examine the mechanism of selfnormalization and how it is affected by the frequency distribution of words in the text and the size of the vocabulary. We propose solutions that are adapted to the inner workings of the method and experimentally show that they considerably ease training. Chapter 4 will expand on a generalization of several sampling based objectives as Bregman divergences, in order to experiment with new objectives. We use Beta divergences to derive a set of objectives from which noise contrastive estimation is a particular case. Finally, in Chapter 5, we aim at improving performances on full vocabulary language models, by augmenting output word representations with subwords and experimenting with various architectures. We experiment on a Czech dataset and show that using character-based representations besides word embeddings for output representations gives better results when working on the full vocabulary. We also show that in that case, reducing the size of the output look-up table improves results even more.

The main contributions presented in the Sections 3.2 and 3.3 have been published in [START_REF] Labeau | Learning with noise-contrastive estimation: Easing training by learning to scale[END_REF], while an exploration of the results of Section 3.1.2 has been published in Labeau and Allauzen (2017a). Preliminary work on subwordbased neural architectures, applied to a different task, has been published in [START_REF] Labeau | Non-lexical neural architecture for fine-grained pos tagging[END_REF] and is presented in Annex D. We applied such architectures to language modeling with an extrinsic evaluation on machine translation, in [START_REF] Labeau | Représentations continues dérivées des caractères pour un modèle de langue neuronal à vocabulaire ouvert[END_REF]. Finally, the main contributions of Chapter 5 were first explored in Labeau and Allauzen (2017b). Language models play a key role in various Natural Language Processing tasks, such as machine translation and speech recognition. Their function is to assign probabilities to sentences, i.e to determine how likely a sentence is in a given language. As such, we can view them as prior knowledge on the language they model. The goal is to assign a low probability to sequences that are grammatically incorrect, but also to sequences that are grammatically correct and do not make sense. In this work, we will only consider statistical language models, which determine the likelihood of a sentence based only on data upon which the language model is built. A sentence S is considered as a sequence of words S = (w 1 , . . . , w t , . . . , w |S| ) Each of these words belongs to a finite vocabulary V, which contains all the words the model is able to represent. We want to assign to S a probability

P (w 1 , . . . , w |S| )
Assuming that the words composing the sentence have been generated depending on the sequence of previous words, and using the chain rule, we can write this probability as:

P (S) = |S| t=1 P (w t |w 1 , . . . , w t-1 )
We choose to write each sequence of previous words (w 1 , . . . , w t-1 ) as a context H t , transforming the probability of our sequence into a product of conditional probabilities of words given a context P (w t |H t ). Then, the generation of a word w given a context H can be modeled as depending on a multinomial distribution on the vocabulary V. Our statistical language model must learn these distributions from a dataset D, which is composed of couples (H, w). At first, to make the task easier, we can use the Markov assumption: we restrict the conditional dependency of the word w t on the n -1 previous words. Then,

P (S) = |S| t=1 P (w t |w t-n+1 , . . . , w t-1 )
We call the models using this approximation n-gram models. The choice of n is a trade-off between being able to capture longer dependencies between words, and needing more parameters to model the conditional probabilities. Increasing n also brings another issue: the data sparsity. Indeed, since each word comes from a finite vocabulary V, there are |V| n possible n-grams. With higher values of n, it is increasingly unlikely to have a particular n-gram appear in the training data D.

Historically, the first language modeling approaches are based upon counting ngram occurrences, which we will discuss in Section 1.1. To deal with the issue of data sparsity, they were improved with smoothing methods, which allow giving non-zero probabilities to sequences that were never encountered in the training data. When improved in that manner, discrete approaches are still competitive, because of their speed and how little space they need. However, they lack the ability to generalize and imply an exponential growth of their number of parameters if we are to increase n. The introduction of neural networks language models, that use continuous distributed representations of words, allowed to overcome this issue. Using a recurrent structure permitted to remove the constraint of keeping a fixed-size context, and to capture long-term dependencies. We will present these models in Section 1.2. However, training neural networks for language modeling presents numerous practical difficulties, among which computation time is not the least. It also implies making quite a lot of choices on the design of the model. In the last section (1.3), we will rapidly summarize some of these difficulties, and how they are usually addressed. We will then discuss the computational bottleneck of neural network language models, and how it relates to the size of the output vocabulary, which is the main topic of this work.

Discrete language models

Some of the most used language models are very simple: they are based on relative frequencies of sequences. Indeed, maximum likelihood estimation (MLE) on the training data D gives the following estimate:

P M LE (w t |w t-n+1 , . . . , w t-1 ) = c D (w t-n+1 , . . . , w t ) c D (w t-n+1 , . . . , w t-1 )
where c D is the number of occurrences of a sequence in the training corpus D. Usually, n is chosen to be 2 or 3, corresponding to bigram and trigram models. However, if the quantity of training data is not large enough for the size of the model we are training, there is a higher risk of never coming across word sequences that are still plausible, therefore attributing them P M LE = 0. This especially is an issue for applications such as speech recognition or machine translation, where the word sequence in question could not be outputted, even if well evaluated by the acoustic or translation model. Therefore, smoothing methods are used to adjust the MLE probabilities and prevent zero probabilities.

Smoothing

The main idea behind smoothing is to move a small amount of the probability mass attributed to n-grams seen in the data to the n-grams that are unseen. The simplest way to do so is to add a minimum number of occurrences to each sequence: this is additive smoothing. However, this offers poor performance. A variety of more complex methods exist, which are reviewed and compared in [START_REF] Chen | Regular article[END_REF], or again in [START_REF] Goodman | A bit of progress in language modeling[END_REF]. These methods usually combine high-order models (with a high value of n) with lower order models. Mostly, smoothing techniques can be divided in two categories, according to how this combination is accomplished. First, backoff models can be described by the following rule:

1.1 Discrete language models

P backof f (w t |w t-n+1 , . . . , w t-1 ) = α(w t |w t-n+1 , . . . , w t-1 ) if c D (w t-n+1 , . . . , w t ) > 0 γ t-1 t-n+1 P backof f (w t |w t-n+2 , . . . , w t-1 ) if c D (w t-n+1 , . . . , w t ) = 0 (1.1)
If the sequence has a non-zero count, we use a distribution α which is based on discounted relative frequencies. The discounting method varies: Katz smoothing (Katz, 1987) uses a ratio based on the Good-Turing estimate [START_REF] John | The population frequencies of species and the estimation of population parameters[END_REF], while other methods use an absolute discount, notably Kneser-Ney smoothing [START_REF] Kneser | Improved backing-off for m-gram language modeling[END_REF]. The discounted quantity is then attributed to the sequences which have a zero-count, backing-off to a lower order model, where γ is a normalizing factor, to ensure the distribution sums to 1.

The other category gathers interpolated models. They are the linear interpolation of higher and lower-order n-gram models: [START_REF] Jelinek | Interpolated estimation of Markov source parameters from sparse data[END_REF] and [START_REF] Witten | The zero-frequency problem: Estimating the probabilities of novel events in adaptive text compression[END_REF] give examples of such models. The main difference between the two categories resides in how they estimate the probabilities of sequences which appear in the training data: interpolated models use information from lower-order distribution, while back-off models do not. Besides comparing these methods, [START_REF] Chen | Regular article[END_REF] experiment with combining them. They propose a modified version of the Kneser-Ney smoothing which is still widely used, and a recommended discrete language model for many applications.

P interpolated (w t |w i-n+1 , . . . , w t-1 ) = λ t-1 i-n+1 c D (w i-n+1 , . . . , w t ) c D (w i-n+1 , . . . , w t-1 ) + (1 -λ t-1 i-n+1 )P interpolated (w t |w i-n+2 , . . . , w t-1 ) (1.2)

Limitations

Several aspects of discrete language models, even with smoothing, could be improved upon. As we have seen, higher-order models often use lower-order dependencies to assign probabilities, because of the data sparsity. Besides, augmenting the size of sequences the model is able to consider has an exponential cost in parameters, which forces the context to be most of the time very short. For these reasons, longer dependencies are ignored. This brings up another issue: most of the parameters are free parameters, since they directly depend on values represented by other parameters corresponding to smaller sequences. A model being able to share parameters, in order to re-use the information previously learnt for new sequences, would also be able to better generalize to unseen sequences. Various work tried to tackle these difficulties. Some types of language models directly incorporate knowledge about the language, whether it is in the form of structural information (as structured language models, described in [START_REF] Chelba | Structured language modeling[END_REF]) or by grouping words that belong to a same group together to exploit their closeness, as for class-based language models 1 (Brown et al., 1992; Kneser and Ney, 1993). However, an approach based on using continuous representations of words with neural networks for probability estimation offers a solution to all these issues.

Neural network language models

We will first describe the standard feedforward language model, introduced in Bengio et al. (2003). There are two main ideas behind this model: First, using a distributed representation, inspired by Elman (1990b); [START_REF] Hinton | Learning distributed representations of concepts[END_REF], for each word. It means that instead of representing a word as being only one element in a large vocabulary, each word is characterized by a number of features. This allows to describe a large number of objects with a relatively small number of parameters, and to generalize information to new objects easily. Secondly, making these representations continuous.Then, the smooth probability function that takes as input a fixed-length word sequence (a context) and outputs a probability distribution on V can be modeled with a neural network.

Both the parameters of the distributed representations and of the probability function are learnt jointly. Previously, several approaches applied neural networks to language modeling [START_REF] Miikkulainen | Natural language processing with modular PDP networks and distributed lexicon[END_REF][START_REF] Xu | Can artificial neural networks learn language models?[END_REF], but never to learn a large-scale model of the distribution of word sequences. However, we can mention maximum entropy language models [START_REF] Berger | A maximum entropy approach to natural language processing[END_REF], which can be assimilated to neural networks without a hidden layer.

Feedforward language models

As previously, we want to be able to assign a probability P (w 1 , . . . , w |S| ) to a sequence S. We still consider the Markov assumption to be true: we want to model P (w t |H t ) where H t = (w t-n+1 , . . . , w t-1 ) is the first n-1 words of the n-gram, while w t is the last. Then, we consider the conditional probability distribution over V as a continuous function to be learned:

P (.|H t ) = f (H t )

Word embeddings

This function is decomposed in two parts. First, the distributed representations of the words of V. These are vectors, that we note r ∈ R dr . In practice, they are represented by a Look-up matrix L ∈ R dr×|V| . Each row of this matrix is a continuous vector that corresponds to a word in the vocabulary: L = [r j ] |V| j=1 . These representations are called word embeddings. To obtain a representation of the full vocabulary. Thus, we will discuss them a little more in Section 2.1 1.2 Neural network language models context H t , we simply concatenate the word embeddings corresponding to the words of H t :

x t = [r w t-n+1 ; . . . ; r w t-1 ]

Then, x t ∈ R (n-1)dr represents the whole input sequence H t . Then, we map this vector to a conditional probability distribution over V.

Hidden layers

This is done by applying successive feature extracting layers: each layer consists in a simple linear transformation, using a weight matrix W hidden ∈ R d h ×(n-1)dr and a bias vector b hidden ∈ R d h , followed by the application of a non-linear function φ, that we call an activation function:

h t = φ(W hidden x t + b hidden )
If we stack at least one hidden layer between the input and output layers, we obtain a model called the multilayer perceptron. It has been shown [START_REF] Hornik | Multilayer feedforward networks are universal approximators[END_REF][START_REF] Cybenko | Approximation by superpositions of a sigmoidal function[END_REF] that, with at least one hidden layer, and a suitable non-linear activation function, any function continuous on a closed part of R N can be approximated -in our case, N = |V|.

Output layer

Now, we need to map the resulting hidden representation h t ∈ R d h to a probability distribution on V. This means that we need to give a probability to each word w in the vocabulary: the output of our multilayer perceptron is a vector of |V| positive values which sum to 1, that we note P Ht . Then,

P (w t = k|H t ) = P Ht k and V k=1 P Ht k = 1
We proceed with a layer whose activation function is the softmax function. First, we extract a score with a linear transformation corresponding to a specific word in the vocabulary. This first step is explicited with an intermediate scoring function s:

s(w t = k, H t ) = s Ht k = r out k h t + b out k
The vectors r out k each correspond to a word k of the vocabulary, as do the bias values b out k . They form the rows of a matrix that can be seen as the weight matrix of the output layer,

W out = [r out k ] |V| k=1
, with W out ∈ R |V|×d h , and the associated bias vector b out ∈ R |V| . Equivalently, we can see these weights as output word embeddings2 . Then, we make this score positive by applying the exponential function, and transform them into probabilities by normalizing them: The dimensions d r , d h of the word embeddings and hidden representations, and the activation function φ, are all hyperparameters, that we need to choose. We will discuss hyperparameter choices in more details in Section 1.3.2. The look-up matrix L, the hidden layer weight matrix W hidden and bias b hidden , and the output layer weight matrix W out and bias b out are parameters of the model. We gather them in one parameter vector θ, which is then the set of all the free parameters of our model. The continuous function f we learn depends on θ, and outputs a conditional probability distribution. We can then note it P θ : it is modeled by a feedforward neural network, composed of an input, hidden, and output layer. If H is fixed, we can note the conditional probability distribution associated as P H θ (.), a function over V, or as a vector P H θ ∈ R |V| .

W hidden W out

Learning with gradient descent and backpropagation

In order to learn this function, we perform maximum-likelihood estimation (MLE). The objective is to find the parameters θ which minimize the negative log-likelihood of this conditional distribution for each tuple of input context and following word (H, w) ∈ D, where D is the training set:

N LL(θ) = - (H,w)∈D log P θ (w|H) (1.4)
We can do so with the Stochastic Gradient Descent (SGD). We then need to compute the gradient to update the parameters: in practice, this is done via backpropagation [START_REF] Rumelhart | Neurocomputing: Foundations of research. chapter Learning Internal Representations by Error Propagation[END_REF]). For one training example (H, w), such an update has the form:

θ updated = θ -λ ∂ ∂θ log P θ (w|H) (1.5)
where λ is the learning rate, which can be treated as an hyperparameter. Its value can be fixed or can change during training according to various strategies that we will discuss in Section 1.3.2.

Recurrent neural network language models

One of the disadvantage of the conventional feedforward network is that the length of the input context is fixed to n -1 words. The idea of recurrent neural networks is to use a structure adapted to working with sequences, by creating at each time step a fixed-sized vector that represents all the preceding words. The idea of recurrent neural network was introduced by Elman (1990a) and applied to language modelling by [START_REF] Mikolov | Recurrent neural network based language model[END_REF].

Basic recurrent layer

Our input sequence is still S = (w 1 , . . . , w t , . . . , w |S| ). The main difference with the feedforward model is that we compute for each time step t a hidden state h t corresponding to a word w t . This state is computed using the previous hidden state and the computed representation r wt , coming from the input layer. Hence,

h t = φ(W hidden h t-1 + W input r wt )
where W hidden and W input are weights matrices, applying linear transformations respectively to the previous hidden state and the input representation. At each time step, the output conditional probability distribution (which is now conditioned on all the previous words in the sequence) is obtained in the same way as for the feedforward model:

P (w t = k|w 1 , . . . , w t-1 ) = e r out k ht+b out k |V| l=1 e r out l ht+b out l (1.6)
While the first occurrence of the model [START_REF] Mikolov | Recurrent neural network based language model[END_REF] was trained with truncated backpropagation, it was later [START_REF] Mikolov | Extensions of recurrent neural network language model[END_REF] improved with backpropagation through time [START_REF] Paul | Backpropagation through time: What it does and how to do it[END_REF]. The first one consists in applying parameter

W input W out P Ht-2 θ h t-2 W input W out W input W out h t-1 W hidden h t W hidden P Ht-1 θ P Ht θ d r |V| Figure 1.2:
Example architecture of a recurrent neural network language model, unrolled through 3 sucessive time steps.

updates using only the gradients from the current time step, while the second allows propagating the gradients through several time steps. That number is usually limited by a fixed threshold. However, there are some issues with this kind of structures. First, it is not possible to choose what to keep and what to skip in a hidden state. It is probable that information will not be kept for very long. Secondly, even if we rely on the backpropagation through time to make the model keep relevant information, in practice, it causes vanishing and exploding gradients [START_REF] Bengio | Learning long-term dependencies with gradient descent is difficult[END_REF][START_REF] Pascanu | On the difficulty of training recurrent neural networks[END_REF]. While it is possible to clip the gradient to deal with the latter, the former often implies that the model ignores long-term dependencies, since the gradient vanishes after a few time steps. Hence, a conventional recurrent neural network language model may not be able to use longer context than usual n-grams models.

LSTM and other improvements

The most widely used improvements on the recurrent structure are the Long Short-Term Memory units, or LSTMs [START_REF] Hochreiter | Long short-term memory[END_REF]. It was specifically designed to be able to retain these long-term dependencies: through the use of gates, it allows selecting the information that is retained and transmitted. It also scales the descending gradient to avoid vanishing and exploding gradients when backpropagating through time:

t t = φ(W hidden t h t-1 + W input t r wt ) f t = φ(W hidden f h t-1 + W input f r wt ) o t = φ(W hidden o h t-1 + W input o r wt ) z t = φ(W hidden z h t-1 + W input z r wt ) c t = f t c t-1 + t t z t h t = o t φ(c t ) (1.7)
which can summarized with:

h t = LST M (h t-1 , r wt )
LSTM were first applied to language modeling in [START_REF] Sundermeyer | LSTM neural networks for language modeling[END_REF], and compared to feedforward neural networks in [START_REF] Sundermeyer | Comparison of feedforward and recurrent neural network language models[END_REF]. Another popular recurrent structure, using gates to retain or forget information, is the Gated Recurrent Unit, or GRU [START_REF] Cho | Learning phrase representations using RNN encoder-decoder for statistical machine translation[END_REF], which were compared to LSTM in [START_REF] Chung | Empirical evaluation of gated recurrent neural networks on sequence modeling[END_REF]. In this work, we chose to use LSTMs for our models.

Practical considerations

Even if we possess all the basic blocks that would allow us to build our language model, many hyperparameters must be chosen. They include architectural choices, such as the number and type of layers, as well as their sizes, but also the learning procedure, the type of regularization, and other tricks that can help training. We will first explain how we evaluate our models, on which data, then what choices we need to consider, before moving on to our main topic.

Evaluation

When used for a specific application, the performance of a language model can be measured by how much it improves the system it is a part of, which is an extrinsic evaluation. However, to evaluate a language model on its own (an intrinsic evaluation), the most common used method is perplexity. It is the geometric average of the inverse probability the model assigns to the words, and is usually measured on a separate test dataset. For a sequence of N words,

P P L = N N i=1 1 P (w t |H t ) (1.8)
Equivalently, it can be described as the exponential of the cross-entropy of the test data, given the model. Intuitively, it is a measure of how informed the model is. Thus, a model attributing uniform probabilities to each word in a vocabulary V would have a perplexity of |V|, while a model attributing a probability of 1 to the right word each time would have a perplexity of 1.

However, we should remark that perplexity has drawbacks. First, it is intrinsic, and measuring the effect of the model on the task it is applied to is arguably far more important. Secondly, it is the exponential of entropy, which means perplexity improvements which seem meaningful could mean only very small entropy changes. This issue is further discussed in [START_REF] Goodman | A bit of progress in language modeling[END_REF]: the author argues that the speed and space taken by a model are often overlooked, while the gains obtained on perplexity are not always worth their cost. They also may offer almost no gain on other measures, as the word error rate. Another aspect that is sometimes overlooked is how important the quantity and quality of data available for training are, in order to obtain a reasonable performance. However, while it is relatively easy to train discrete models on large datasets, large-scale neural language models are very costly in computation time and memory.

Datasets

One of the most used benchmarks in neural language modeling is the Penn TreeBank (PTB) [START_REF] Marcus | Building a large annotated corpus of english: The penn treebank[END_REF] corpus. As it is rather small -929K training words, 73K validation words, and 82K test words -experimenting with it is not too demanding in resources. However, as argued in [START_REF] Józefowicz | Exploring the limits of language modeling[END_REF], with the increasing availability of data and computational resources, models should be tested on larger corpora, since a good performance on a small dataset may not hold on a larger one. The 1 Billion Word Benchmark dataset [START_REF] Chelba | One billion word benchmark for measuring progress in statistical language modeling[END_REF] is an open dataset commonly used as a way to compare progress of large language models. About 1% of the dataset was held-out, shuffled and divided in 50 partitions that 1.3 Practical considerations can be used as validation/test data. As we are limited in resources, we will use the PTB for most of our experiments in this work, while we will verify our results on the 1 Billion Word Benchmark when possible, using the first and second partitions as validation and test datasets.

Choosing hyperparameters

The first choices to consider are the number of hidden layers (for both feedforward and recurrent models) and their dimensions, as well as the dimension of word representations. Of course, higher dimensional representations are more expressive, but also more costly to use3 . These choices should also depend on the amount of data available. Similarly, using several stacked hidden layers can improve results. But not only is it more costly, it can also make training far more difficult, because of the phenomenon of gradient attenuation mentioned in Section 1.2.2. Although this issue was first handled by using specific initialization schemes [START_REF] Glorot | Understanding the difficulty of training deep feedforward neural networks[END_REF][START_REF] Saxe | Exact solutions to the nonlinear dynamics of learning in deep linear neural networks[END_REF], one possible solution is to use highway layers [START_REF] Kumar Srivastava | Highway networks[END_REF], which regulate the information flow (and can allow propagation of the gradient) with a gating mechanism.

The choice of the activation function also impacts heavily how easily the information circulates in the network: while the sigmoid and tanh were traditionally used, they easily saturate, which makes their gradient very small. The rectified linear unit [START_REF] Glorot | Deep sparse rectifier neural networks[END_REF], or ReLU, which is simply the function f (u) = max(0, u), is currently the most popular activation function. Being linear when non-zero, it does not saturate, and its computation is faster.

Optimization, Regularization and Initialization

The learning scheme refers to the choice of the learning rate λ used to update parameters (in Equation 1.5). It is crucial, and using strategies like iteratively drecreasing λ after seeing enough examples facilitates learning. However, we can use algorithms that adapt the learning rate to each parameter, like Adagrad (Duchi et al., 2011), which uses a cache of accumulated past gradients to normalize the learning rate. One of the most used method is Adam (Kingma and Ba, 2014), which combines several strategies including Adagrad.

Overfitting is a common issue, and especially is of concern for smaller datasets. While we could use the usual L1 and L2 regularization constraints, a neural-network specific method, dropout, was recently introduced by [START_REF] Srivastava | Dropout: A simple way to prevent neural networks from overfitting[END_REF]. Dropout keeps neurons active with a probability smaller than 1 during training, which has the effect of sampling a sub-network. While it was only efficient for feedforward networks at first, [START_REF] Zaremba | Recurrent neural network regularization[END_REF] applied it successfully to LSTMs.

How the parameters are initialized is quite important, and can drastically affect training. The initialization scheme should be chosen in accordance with the activation function. [START_REF] Glorot | Understanding the difficulty of training deep feedforward neural networks[END_REF] make the analysis that the neurons in the network should have similar output distributions, and provides advice on doing so, while [START_REF] He | Delving deep into rectifiers: Surpassing human-level performance on imagenet classification[END_REF] derive an initialization scheme specifically for ReLUs. However, a recent method called batch normalization [START_REF] Ioffe | Batch normalization: Accelerating deep network training by reducing internal covariate shift[END_REF], which we will use, normalizes the outputs of activation function into a unit Gaussian distribution, rendering initialization less impactful.

The computational bottleneck

The main limitation of neural networks language models is their expensive computational cost. This was already pointed out by Bengio et al. (2003). [START_REF] Schwenk | Neural network language models for conversational speech recognition[END_REF] provide, for the feedforward model, the number of operations needed to obtain the output distribution:

((n -1) × d r + 1) × d h + (d h + 1) × |V| (1.9)
Since, for a language model, the quantities d r and d h verify d r |V| and d h |V|, the computational cost mainly depends on the size of the vocabulary, with which it grows linearly. Early work on neural network language models proposed a certain number of training tricks to accelerate training, among which using a mini-batch, i.e parallelizing computation by forwarding (and backpropagating the gradient of) multiple examples at the same time, instead of just one. In practice, it is very efficient, and it only requires transforming the vectors x, h and P of Section 1.2 into matrices. However, the most straightforward way to limit computational time is to limit the vocabulary size. Bengio et al. (2003) proposed to remove words under a frequency threshold of the vocabulary, and to map them to a same token UNK, which represents all unknown words. That is what we will do when we do not use the full training vocabulary. An improvement on that idea is the short-list, [START_REF] Schwenk | Neural network language models for conversational speech recognition[END_REF] which limits the neural language model vocabulary size, and uses the probabilities obtained from a discrete language model for the remaining words. However, this solution limits the model capacity to generalize to less frequent words.

While the training and inference costs of a neural language model are always making their practical use difficult, we will in the next chapter mainly be interested in reducing them when they are the most impactful: for language models that use a large vocabulary.

The main drawback of Neural Probabilistic Language Models is their very long computation time. At the root of this issue lies the multinomial classification objective: its computation time is linear in the number of categories, which is the size of the target vocabulary. To understand why, we need to take a closer look at the objective function and its gradient. Our neural probabilistic language model with parameters θ outputs, for an input context H, a conditional distribution P H θ for the next word, over the vocabulary V. As explained in Section 1.2, this conditional distribution is defined using the softmax activation function:

P θ (w|H) = e s θ (w,H) w ∈V e s θ (w ,H) = e s θ (w,H) Z θ (H) (2.1)
Here, we are not interested in the network architecture and we suppose that the model outputs a scoring function s θ (w, H) which depends on it. The denominator is the partition function Z θ (H), which is used to ensure that for each input context H, output scores are normalized into a probability distribution. As explained in Section 1.2.1, the objective is to minimize the negative log-likelihood of this conditional distribution for each tuple of input context and following word (H, w) ∈ D in the training data:

N LL(θ) = - (H,w)∈D log P θ (w|H) (2.2)
Using the Stochastic Gradient Descent (SGD) to train this objective implies taking the objective gradient to make the parameter updates. For one training example (H, w), the gradient of the log-probability is computed as follows:

∂ ∂θ log P θ (w|H) = ∂ ∂θ s θ (w, H) - w ∈V P θ (w |H) ∂ ∂θ s θ (w , H) (2.3)
With the first term, we are increasing the conditional log-likelihood of the word w, while we are decreasing the conditional log-likelihood of all the other words in the vocabulary with the second. Unfortunately, explicitly computing P θ (w |H) implies computing the partition function Z θ (H), which means summing over the whole vocabulary V.

While we described in Section 1.3.3 a classic workaround consisting in using a short-list that limits the output layer of the network to the most frequent words, the model will not be able to generalize well to words out of this list. In this chapter, we will describe methods that can be used to efficiently handle large vocabularies in language modeling. We will expose the theoretical guaranties they offer, the hyperparameter choices they entail and their experimental advantages and weaknesses. Most of these methods revolve around avoiding the computation of the partition function Z θ (H). Thus, an important concept in this chapter (and the remaining of this dissertation) is the un-normalized version of a probability distribution. This is simply the exponential of the scoring function and we will denote it as a lower-case version of the normalized probability distribution:

p θ (w|H) = e s θ (w,H) = P θ (w|H)Z θ (H) (2.4)
We will rapidly present Hierarchical approaches (Section 2.1), which reorganize the structure of the output layer into a tree structure. They provide a potential O(log |V|) speedup, but at the cost of building the word hierarchy that will replace V. The main other approaches, that we will examine in detail, use sampling schemes to avoid computing the partition function. While Importance Sampling (Section 2.2) directly approximates the gradient computation, Noise Contrastive Estimation (Sec- tion 2.3.1) andrelated methods (Section 2.3.2 and2.3.3) use a discriminative objective function that doesn't require normalization and let the partition function be parametrized separately. We will also present Constrained self-normalization (Section 2.4), where the partition function is explicitly forced to be close to 1 in the objective function, which is efficient for some specific applications.

Hierarchical language models

To avoid the costly summations in the multinomial classification objective, we can modify the output layer to make this classification hierarchical. We first predict a (series of) class or cluster and, given that class, predict the following word. While class-based models have been used extensively in language modeling [START_REF] Peter | Class-based n-gram models of natural language[END_REF][START_REF] Kneser | Improved clustering techniques for classbased statistical language modelling[END_REF], they aimed at improving the model perplexity, or reducing its size. Decomposing the vocabulary into classes in order to get a speedup in computation was first applied by Goodman (2001a), to a Maximum entropy language model. An extension of this idea was then applied to Neural probabilistic language models, first by [START_REF] Morin | Hierarchical probabilistic neural network language model[END_REF]. Here, the prediction of a word from a vocabulary V is replaced by a series of O(log |V|) decisions. That process can be seen as a hierarchical decomposition of the vocabulary, following a binary tree structure. Indeed, by building a binary hierarchical clustering of the vocabulary, we can represent each word as a bit vector b(w) = (b 1 (w), . . . , b m (w)) and compute the conditional probability of the next word as:

P θ (w|H) = m i=1 P θ (b i (w)|b i-1 (w), . . . , b 1 (w), H) (2.5)
Then, the full vocabulary normalization is replaced by O(log |V|) binary normalizations. The main limitation, however, is that we need to build the tree of words, which is here done from prior knowledge. In Mnih and Hinton (2009), the procedure used to build this tree is automated and data-driven, using various feature based algorithms on the training set. It allows the model to outperform its non-hierarchical equivalents. Other work [START_REF] Mikolov | Extensions of recurrent neural network language model[END_REF] used frequency to build simple classes, while [START_REF] Zweig | Speed regularization and optimality in word classing[END_REF] explicitly minimizes the runtime of a class-based language model using dynamic programming. Another approach [START_REF] Le | Structured output layer neural network language model[END_REF] uses a short-list for the most frequent words, followed by hierarchical clustering for the rest of the vocabulary. Using the short-list avoids the drop of performance observed when all clusters are put in the leaves of the tree. Combining these last two strategies, a recently introduced method [START_REF] Grave | Efficient softmax approximation for gpus[END_REF], the adaptive softmax, also takes into account the modern matrix multiplication computation time on GPU.

Importance Sampling

Importance sampling [START_REF] Owen | Monte Carlo theory, methods and examples[END_REF] is a general sampling technique used when we want to estimate a distribution using samples from a different distribution. If we have a random variable X, a function f (X) of X with an unknown distribution and we want to estimate the expected value of f with respect to a distribution P, the ordinary Monte-Carlo estimator of µ

= E P [f (X)] is μMC = 1 k k i=1 x i ∼P f (x i ) (2.6)
However, when we can't sample from P but have access to a proposal distribution Q, we notice that by introducing the notation:

ρ(X) = P(X) Q(X)
we can obtain the following re-writing of the expectation:

E P [f (X)] = x∈X P(x)f (x) = x∈X ρ(x)Q(x)f (x) = E Q [ρ(X)f (X)] (2.7)
provided that Q(x) > 0 where P(x)f (x) = 0. Then, our estimator is:

μIS = 1 k k i=1 x i ∼Q ρ(x i )f (x i ) (2.8)
This estimator can easily be shown to be consistent (which means that as the number of available samples grows, the sequence of estimates converges in probability towards the true value) and unbiased (the expected value of the estimator is the true value of the parameter) [START_REF] Owen | Monte Carlo theory, methods and examples[END_REF]. Using this strategy, we an concentrate the sampling effort on important regions of the sampling space, hence the name importance sampling.

Application to Language Modeling

Importance sampling was first applied to neural probabilistic language models in [START_REF] Bengio | Quick training of probabilistic neural nets by importance sampling[END_REF]. The idea is to rewrite the gradient of the objective presented in Equation 2.3 as:

∂ log P θ (w|H) ∂θ = ∂ ∂θ s θ (w, H) - w ∈V P θ (w |H) ∂ ∂θ s θ (w , H) = ∂ ∂θ s θ (w, H) -E w ∼P H θ ∂ ∂θ s θ (w , H) (2.9)
The second term is an expectation with respect to P H θ that can be estimated using importance sampling with a proposal distribution Q. From Equation 2.7:

∂ ∂θ log P θ (w|H) = ∂ ∂θ s θ (w, H) - w ∈V Q(w ) P θ (w |H) Q(w ) ∂ ∂θ s θ (w , H) = ∂ ∂θ s θ (w, H) -E w ∼Q P θ (w |H) Q(w ) ∂ ∂θ s θ (w , H) (2.10)
And, from Equation 2.8, we get the gradient estimate:

∂ ∂θ log P θ (w|H) ≈ ∂ ∂θ s θ (w, H) - 1 k k i=1 ŵi ∼Q P θ ( ŵi |H) Q( ŵi ) ∂ ∂θ s θ ( ŵi , H) (2.11)
However, the reason we are using sampling is to avoid computing the partition function Z θ (H): we can only compute the un-normalized version of P H θ .

Self-normalized Importance Sampling

As described in [START_REF] Bengio | Quick training of probabilistic neural nets by importance sampling[END_REF], we need to use a different version of importance sampling, that is called ratio or self-normalized importance sampling (RIS). The idea is to normalize the weights, which we can do by applying classical importance sampling to the partition function. Indeed, if our distribution P can only be estimated up to its partition function, which means we only have access to p with p = ZP, we can write:

Z = x∈X p(x) = x∈X ω(x)Q(x) = E Q [ω(X)]
(2.12)

with

ω(x) = p(x) Q(x) (2.13)
Using the same distribution Q, to be able to re-use the samples, we obtain the estimator for Z:

Ω = k i=1 x i ∼Q ω(x i ) (2.14)
Which gives us the estimator for µ,

μRIS = k i=1 x i ∼Q 1 Ω ω(x i )f (x i ) (2.15)
Using the strong law of large numbers, we can show that the estimator μRIS converges to the wanted expectation almost surely and is therefore consistent. However, we must have Q(w) > 0 when p > 0, which is a condition a little stronger than for the classic importance sampling estimator μIS . Besides, μRIS is biased in O( 1 k ) (Hesterberg, 2003) -which makes it asymptotically unbiased.

To apply this estimator to our problem, we now write:

ω( ŵ) = p θ ( ŵ|H) Q( ŵ) (2.16)
and we obtain the following gradient update:

∂ ∂θ log P θ (w|H) = ∂ ∂θ s θ (w, H) -E w ∼Q 1 Z θ (H) p θ (w |H) Q(w ) ∂ ∂θ s θ (w , H) ≈ ∂ ∂θ s θ (w, H) - k i=1 ŵi ∼Q 1 Ω ω( ŵi ) ∂ ∂θ s θ ( ŵi , H) (2.17)

Number of samples and choice of Q

The variance of the ratio estimator is depending on the sample size in O( 1 k ) (Hesterberg, 2003): while both the bias and the variance can be reduced by augmenting the number of samples drawn from Q, it might be costly to do so. Another issue is that some of the weights ratio r i ≈ ω( ŵi ) Ω can become disproportionally large if the value of Q( ŵi ) is too small. A weight vastly larger than the others would override all other weights and mimic a situation where we have only sampled one observation. This can be measured using the effective sample size(ESS):

ESS = k i=1 r i 2 k i=1 r 2 i (2.18)
which will be largely smaller than k if weights are unbalanced. We can also look at the expression of the variance [START_REF] Classen | Advances in importance sampling[END_REF] to understand this issue:

V ar(μ RIS ) = 1 k k i=1 P θ ( ŵi |H) 2 ( ∂ ∂θ s θ ( ŵi , H) -µQ( ŵi )) 2 Q( ŵi ) (2.19)
It is clear that having Q too close to 0, especially when P H θ is not, leads to a high variance, while having Q approximately proportional to P H θ for most w leads to a smaller variance.

Experimentally, [START_REF] Bengio | Quick training of probabilistic neural nets by importance sampling[END_REF], while using the unigram distribution as Q, found that a sample size too low would cause divergence as training progresses: they used the ESS to monitor the sample size and if needed increase it during training. However, as the training advances, the number of samples necessary increases rapidly. This behavior is conjectured to be caused by the fact that the model distribution becomes increasingly complex and diverges from the unigram distribution in [START_REF] Bengio | Adaptive importance sampling to accelerate training of a neural probabilistic language model[END_REF]. The authors try to switch to more complex distributions for Q (interpolated bigram and trigram distributions), but it gave poorer resultswhich seems to be caused by the fact that these distributions are very different than those learned with neural networks. They then force their distribution Q to adapt by redistributing probability mass in order to track P H θ . This is done by interpolating a series of n-gram models of different orders. As a result, the number of samples needed seems to grow only linearly with time, instead of exponentially.

Target Sampling

A more recent approach, [START_REF] Jean | On using very large target vocabulary for neural machine translation[END_REF], applied to machine translation, partitions the training corpus and defines a subset of the vocabulary to sample from for each partition, which contains at least all target words in the partition. Formally, we obtain separate distributions Q i for each of these partitions i:

Q i ( ŵ) = 1 |V i | if ŵ ∈ V i 0 otherwise (2.20)
Using uniform probabilities on a subset of the vocabulary simplifies the estimator since the importance weights all have the same denominator. Since we choose this subset to contain at least all the target words, the necessary condition for consistency described in 2.2.1 is verified. We obtain a gradient update that is the same we would get from a softmax applied only on the set of words sampled from Q i :

P θ (w|H) ≈ exp s θ (w, H) k i=1 ŵi ∼Q i exp s θ ( ŵi , H) (2.21)
Using only subsets of the full vocabulary with uniform distributions also allows for better computational efficiency.

Complementary Sum-Sampling

The recent work of [START_REF] Botev | Complementary Sum Sampling for Likelihood Approximation in Large Scale Classification[END_REF] shows that the high variance in the standard importance sampling estimation is simply due to not including the correct class into the set of samples. They show that by summing over a subset of classes (including the correct one) to which we add the samples from Q, we dramatically reduce the estimation error at no additional cost.

Density estimation as a classification task: discriminative objectives

Noise Contrastive Estimation (NCE) was first described in Gutmann andHyvärinen (2010, 2012), as a way of estimating a parametric probabilistic model from observed data, in the case where the probability function of the model is un-normalized. The first idea is to consider the partition function Z as a separate parameter, instead of a value dependent on all the other parameters θ. Then, a parametrized distribution P θ is decomposed as: log P θ = log p θ 0 + c with parameters θ = (θ 0 , c). Here, c = -log Z gives the un-normalized model proper scaling, while the other parameters make the shape of the model match the shape of the data density distribution. However, estimating separately θ 0 and c is not possible with maximum-likelihood estimation, since we can simply choose c to be as large as we want to increase likelihood. The authors then propose an objective function which mimics maximum-likelihood estimation by learning to discriminate between examples from data or generated from a noise distribution. This method has been applied to language modeling, as well as other approaches which also use discriminative objectives and that will be described subsequently.

Noise Contrastive Estimation

With NCE, we learn the relative description of the data distribution P D to a reference noise distribution P n , by learning their ratio P D /P n . This ratio is learned by discriminating between the two distributions. Concretely, we draw k samples from the noise distribution for each tuple (H, w) ∈ D and optimize our model to perform a classification task between them. We can consider our example as coming from the following mixture:

1 k + 1 P D + k k + 1 P n (2.22)
Since we don't have access to P D but want to approach it with our model of parameters θ, we can consider the conditional class probabilities as: P (w|C = 1, H) = P θ (w|H) and P (w|C = 0, H) = P n (w|H) (2.23) which gives the posterior class probabilities:

P (C = 1|w, H) = P θ (w|H) P θ (w|H) + kP n (w|H) (2.24)
and

P (C = 0|w, H) = kP n (w|H) P θ (w|H) + kP n (w|H) (2.25)
which can be rewritten as:

P (C = 1|w, H) = σ log 1 k P θ (w|H) P n (w|H) (2.26)
The reformulation obtained in Equation 2.26 shows that training a classifier based on a logistic regression estimates the log-ratio of the two distributions: we learn P θ relatively to P n . Since we assume the class labels to be Bernouilli distributed and independent, the classification objective is given by maximizing the log-likelihood of the true examples to belong to class C = 1 and the noise samples ( ŵi ) 1≤i≤k to C = 0, which is, for one example (H, w) from D :

J H θ (w) = log P θ (w|H) P θ (w|H) + kP n (w|H) + k i=1 log kP n ( ŵi |H) P θ ( ŵi |H) + kP n ( ŵi |H) (2.27)
In order to obtain the global objective to maximize, we sum on all examples (H, w) ∈ D:

J θ = H,w∈D J H θ (w) (2.28)
This objective is proven to reach a maximum at P θ * = P D , which is unique if we have that P n > 0 whenever P D > 0 (Gutmann andHyvärinen, 2010, 2012). Besides, the authors prove that the optimal parameters θ * T obtained with an objective J T θ restricted to a sample T of the training data converge in probability towards θ * when T is large enough, assuming constraints on the model that are similar to those used in Maximum Likelihood estimation. The estimation error also behaves comparably to the estimation error of MLE: it is asymptotically following a normal distribution.

Application to language modeling

This objective does not impose any normalization constraint on our model: as indicated earlier, it is possible to estimate an un-normalized distribution p θ 0 , by parametrizing the partition function independently. However, as described by [START_REF] Mnih | A fast and simple algorithm for training neural probabilistic language models[END_REF], who first applied NCE to language modelling, this parametrization is context-dependent and we have:

log P H θ = log p H θ 0 + c H (2.29)
However, learning an additional parameter by context gets very costly as the context size increases. To avoid it, the authors argue that these context-dependent parameters c H can be put to zero, and that given the number of free parameters, the output scores for each context p H θ 0 self-normalize, which is verified in their experiments.

Density estimation as a classification task: discriminative objectives

The gradient update is the following:

∂ ∂θ J H θ (w) = kP n (w|H) P θ (w|H) + kP n (w|H) ∂ ∂θ log P θ (w|H)- k i=1 P θ ( ŵi |H) P θ ( ŵi |H) + kP n ( ŵi |H) ∂ ∂θ log P θ ( ŵi |H) (2.30)
We can note [START_REF] Mnih | A fast and simple algorithm for training neural probabilistic language models[END_REF]) that this gradient converges to the maximum likelihood estimation gradient as the number of samples k grows. Also, one advantage of the NCE over importance sampling is that the weights used here are contained between 0 and 1, for any noise distribution P n .

Choosing the noise distribution Gutmann andHyvärinen (2010, 2012) offer theoretical results on the impact of the noise distribution: the estimation error of parameters θ is asymptotically independent of P n when the ratio of noise sample by example k coming from the data is large enough. They also show that having both a noise distribution close to the data distribution and a high number of samples k will lead to a better estimation error. We can then consider the choice of the noise distribution as a trade-off between using a large number of noise samples or using a noise distribution closer to our data distribution. [START_REF] Mnih | A fast and simple algorithm for training neural probabilistic language models[END_REF] compared the use of the uniform and unigram distribution in their experiments, finding the unigram distribution to give far more accurate results. In the literature, NCE was then mainly used in the context of machine translation: [START_REF] Vaswani | Decoding with large-scale neural language models improves translation[END_REF]; [START_REF] Baltescu | Pragmatic neural language modelling in machine translation[END_REF] report results with the unigram distribution, while Zoph et al. (2016) used an uniform noise. [START_REF] Chen | Recurrent neural network language model training with noise contrastive estimation for speech recognition[END_REF] applied NCE to speech recognition, with the unigram distribution, but fixed the parameters c H to 9 instead of zero, choosing this value to be close to the log-partition function at initialization, as a trade-off between performance and convergence speed. [START_REF] Chen | Strategies for training large vocabulary neural language models[END_REF] highlighted the inconsistency of NCE training (using unigram noise) when dealing with very large vocabularies, showing very different perplexity results for close loss values.

BlackOut

BlackOut [START_REF] Shihao | Blackout: Speeding up recurrent neural network language models with very large vocabularies[END_REF] is a more recent method using a discriminative objective, with ties to both NCE and Importance sampling. We can describe this approach from two different points of view.

NCE with a re-weighted noise distribution

First, we can see it as applying NCE with a different noise distribution, that we obtain by re-weighting samples from a distribution Q, using the ratio between the learned and sampling densities. As for NCE, we can work with the un-normalized model density p θ . This re-weighted noise distribution is:

P n (w|H) = 1 k k i=1 ŵi ∼Q Q(w) Q( ŵi ) p θ ( ŵi |H) (2.31)
If we note the set of samples S k = { ŵi ∼ Q} k i=1 and the inverse probabilities q(w) = 1 Q(w) we obtain the following posterior probabilities:

P (C = 1|w, H) = q(w)p θ (w|H) q(w)p θ (w|H) + ŵi ∈S k q( ŵ)p θ ( ŵ|H) (2.32)
We obtain the objective of importance sampling, similar to a sampled softmax, when we directly maximize the likelihood of the log-ratio log ω(w) Ω . Here, instead, we apply a logistic regression:

P (C = 0|w, H) = ŵ∈S k q( ŵ)p θ ( ŵ|H) q(w)P θ (w|H) + ŵ∈S k q( ŵ)p θ ( ŵ|H) (2.33)
Using the same process as for NCE, we obtain the discriminative objective:

J H θ (w) = log    q(w)p θ (w|H) q(w)p θ (w|H) + ŵ∈S k q( ŵ)p θ ( ŵ|H)    + w ∈S k log    ŵ∈S k q( ŵ)p θ ( ŵ|H) q(w )p θ (w |H) + ŵ∈S k q( ŵ)p θ ( ŵ|H)    (2.34)
This objective offers the same theoretical guaranties as the NCE, since the authors prove the noise distribution P S k n to be a valid probability distribution. The only infringement to the NCE procedure is that the samples used in the objective are not sampled from P S k n but from Q (since we use them to build P S k n ): however, the expected value of P S k n (w|H) when we sample S k from Q verifies:

E S k ∼Q P S k n (w|H) = Q(w|H)
which shows that this approximation is still accurate.

Approximating classification probabilities with IS

If we take back the notations of Section 2.2.1:

ω( ŵi ) = p θ ( ŵi |H) Q( ŵi ) and Ω = k i=1 ω( ŵi ) (2.35)
we can see that while the method described in Section 2.2 is equivalent to directly maximizing the likelihood of the log-ratio approximated via importance sampling log ω(w) Ω , and can be seen as a weighted softmax, blackOut amounts to applying a logistic regression to this same log-ratio, which we can interpret as a posterior probability of coming from the data (C = 1):

P (C = 1|w, H) = σ log ω(w) Ω (2.36)
Then, maximizing the likelihood of classifying the true examples as such and the importance samples as noise, we obtain the following discriminative objective:

J H θ (w) = log P (C = 1|w, H) + k i=1 log(1 -P (C = 1|w, H))( ŵi |H)) (2.37)
which is the same as in Equation 2.34.

Choice of the sampling distribution Q

In [START_REF] Shihao | Blackout: Speeding up recurrent neural network language models with very large vocabularies[END_REF], the chosen sampling distribution Q is a power-raised unigram distribution:

Q = p α unigram
where α ∈ [0, 1]. This distribution can be seen as an interpolation between an uniform (α = 0) and unigram (α = 1) distribution, which is a trade-off between being able to sample from the most important part of the probability mass (the most frequent words) and the need to have Q not too close to 0, to avoid large weights which would reduce the effective sampling weights, as discussed in Section 2.2.1 for importance sampling. Experimental results show that the approach is more stable than NCE and Importance sampling and that the discriminative objective improves results over maximum likelihood estimation, which using a power-raised unigram distribution does as well. However, experiments are performed over only very small vocabularies.

Negative Sampling

The Negative Sampling algorithm was popularized by the skip-gram embedding algorithm [START_REF] Pascanu | On the difficulty of training recurrent neural networks[END_REF] and while closely linked to NCE, is not able to directly optimize the likelihood of a language model and learn conditional probabilities, as detailed in [START_REF] Dyer | Notes on noise contrastive estimation and negative sampling[END_REF]. Recently, [START_REF] Melamud | PMI matrix approximations with applications to neural language modeling[END_REF][START_REF] Melamud | A simple language model based on pmi matrix approximations[END_REF] showed Negative Sampling to be viable for language modeling. As previously, we use k samples ( ŵi ) 1≤i≤k from the unigram distribution. The objective is very simple: it maximizes the likelihood of a logistic regression that discriminates true examples from noise samples. However, here, our model directly parametrizes the log-odds with the scoring function s θ (w, H): [START_REF] Melamud | PMI matrix approximations with applications to neural language modeling[END_REF] show that optimizing this objective equates to finding a low-dimensional approximation of the shifted pointwise mutual information (PMI) matrix:

J H θ (w) = log σ(s θ (w, H)) + k i=1 log σ(-s θ ( ŵi , H)) (2.38)
s θ * (w, H) ≈ log P (w, H) P (w)P (H) -log k = log P (w|H) kP (w) (2.39)
where the probabilities P are the frequencies in the training data. We can then obtain an estimation of the conditional probability using our model score and the unigram probabilities:

P (w|H) ∝ P (w) exp s θ (w, H) (2.40)
Experiments on relatively small data give results slightly better than with NCE, but the main argument for this method is the simplicity of its objective function.

Since we directly parametrize what is in the other methods a log-ratio of our model and a noise probability, we can make the hypothesis that the learning will be more robust: the issue of unbalanced weights (caused by a noise probability too close to 0, as discussed in Sections 2.2.1 and 2.3.2) will not occur here.

Avoiding normalization by constraining the partition function

For some specific applications, focused on reducing the inference cost of a Neural Probabilistic Language Model, the techniques presented earlier are not a good solution. Hierarchical approaches are still costly and importance sampling requires normalization at testing time. Techniques based on discriminative objectives are fast during training, but since self-normalization is difficult to monitor, using a softmax may be required during testing. To be able to efficiently use a NPLM to decode for a machine translation system, [START_REF] Devlin | Fast and robust neural network joint models for statistical machine translation[END_REF] introduced Self-normalized Neural Networks, which they want to be able to use for inference without performing a softmax explicitly. Instead, they add an explicit constraint in their objective function that makes the partition function Z θ (H) as close to 1 as possible during training:

N LL Self -normalized (θ) = (H,w)∈D s θ (w, H) -α log 2 Z θ (H) (2.41)
The hyper-parameter α enables trading accuracy for self-normalization error. While this objective is not faster to train, it greatly improves inference speed, since assuming the model self-normalized in such a way allows us to only compute s θ (w|H). [START_REF] Andreas | On the accuracy of self-normalized log-linear models[END_REF] analyse the theoretical properties of self-normalized models, whether they use discriminative objectives or an explicit constraint. They proved that a procedure that makes the partition function Z θ (H) close to 1 for training contexts H also makes it close to 1 for unseen contexts. However, this result doesn't necessarily apply to a classification objective. Nonetheless, it provides intuition that sub-sampling the explicit constraint in the objective function 2.41 may not degrade results, while providing a speed-up. They experiment with the following objective:

N LL Self -normalized (θ) = (H,w)∈D s θ (w, H) - α γ H∈γH log 2 Z θ (H) (2.42)
Here, γH indicates that we sum on a fraction γ of all training contexts, ordered by frequency. Their results show that choosing γ = 0.1 keeps the performance intact. We should note that Chen et al. ( 2016) experimented with a similar objective, but without squaring the partition function, which we can interpret as a classic Negative log-likelihood objective where we normalize only for a fraction of the most frequent contexts. In their experiments, this objective behaves very similarly to the one presented in Equation 2.42.

Conclusions

In this chapter, we present a review of methods which allow avoiding the costly summations in the multinomial classification objective. While hierarchical approaches can reduce the computation time from something linear to a logarithm in V, we focused here on sampling-based approaches. Constrained objectives are only useful if we are interested in fast inference -the main methods are Importance sampling, which approximates the partition function, and Noise Contrastive Estimation, which avoids computing it. Both theses training procedures require sampling k samples from an auxiliary distribution, and the sum over the full vocabulary is replaced by a sum over these samples. Interesting variants of these methods exist: we can mention complementary sum-sampling, which reduces drastically the variance of the estimator of importance sampling, and the BlackOut algorithm, which improves on noise contrastive estimation by using a context-dependant reweighted noise distribution. In the previous chapter, we discussed several ways to handle large vocabularies when training neural languages models. We chose in this dissertation to focus on sampling-based methods, and are interested to know how these methods adjust to very large vocabularies in practice. Indeed, the vocabulary sizes commonly used in neural language models can reach very high numbers: for example, the 1 Billion Word Benchmark dataset [START_REF] Chelba | One billion word benchmark for measuring progress in statistical language modeling[END_REF], in its commonly used form, is equipped with a 800K words vocabulary. [START_REF] Józefowicz | Exploring the limits of language modeling[END_REF], who presented the best published results on this corpus, experiments with both importance sampling (IS) and noise contrastive estimation (NCE), showing the former to be far more data-efficient. As discussed earlier, other works, like [START_REF] Chen | Strategies for training large vocabulary neural language models[END_REF], question the efficiency of NCE for language modeling, since perplexity is not explicitly optimized by the objective function. Therefore, we will in this chapter extensively compare IS, NCE and derived methods.

Similarities between IS and NCE are analyzed in [START_REF] Józefowicz | Exploring the limits of language modeling[END_REF]: the authors explain that while NCE uses a surrogate binary classification task, we can see IS as using a surrogate multinomial classification task, where each of the k noise samples represents one of k + 1 categories and the last one is the data category. This leads the authors to make the hypothesis that the multinomial nature of the IS objective could make it a better choice. While we will explore more in-depth the relationship between the objectives in Chapter 4, we will here try to understand what leads to the experimental discrepancies between them. Practically, the main aspect in which the methods differ is how they handle the partition function: while, with IS, it is explicitly approximated (as explained in Section 2.2.1), with NCE, we can parametrize it separately (as described in Section 2.3.1). The fact that NCE does not explicitly optimize the log-likelihood is exactly what allows us to parametrize the partition function separately: indeed, as detailed in [START_REF] Gutmann | Estimation of unnormalized statistical models without numerical integration[END_REF], knowing the partition function, which represents the 'scale' of the model, is essential to compute the likelihood1 . Then, using a separate scaling parameter would give irrelevant results when doing maximum likelihood estimation (MLE), since we could minimize the negative log-likelihood independently of the data.

We will first study, in Section 3.1, the impact of hyperparameters (which are the number of noise samples k and the noise distribution P n ) on both NCE and IS. Obtaining disappointing results with NCE, we choose to investigate it specifically. While it is theoretically proven to converge when the partition function is parametrized separately, the scaling parameter is usually fixed and the un-normalized model therefore self-normalizes, as a side effect of the training procedure. In Section 3.2, we will compare closely the training of neural language models with MLE, IS, NCE and analyze their respective behavior. We will then show experimentally that the training instability of NCE is tied to the difficulty of the model to self-normalize and how this evolves with variants of the algorithm. Finally, in Section 3.3, we will use our analysis to propose various solutions to stabilize training and bring the performance of NCE closer to what could be expected theoretically.

Throughout the chapter, we do our analysis on the Penn Treebank (PTB) corpus. Usually, the size of the vocabulary is of 10K words. Using this vocabulary, a 3.1 Choosing k and P n : impact of the parametrization of sampling

For both IS and NCE, there are strong theoretical results that can guide us in our choices of noise distribution P n and of number of noise samples k. However, in the larger part of the published work where these methods are used for language modeling, practical considerations -which are, how easy it is to sample from P n and how much of a computational burden is using k noise samples -prevail. We will here restate these results and explore experimentally reasonable (i.e, fairly practical to implement) choices for these hyperparameters. While k is easy to control, the complexity of P n is harder to set. We choose here to experiment mainly with context-independent distributions, which are the uniform and unigram distributions. We implement the transition between the two distributions by using a distortion parameter 0 ≤ α ≤ 1 on the unigram distribution. P α n is uniform for α = 0 and unigram for α = 1; we will use additional intermediary values in our experiments. For all experiments, final perplexity results on the testing set of PTB are presented in Table 3.3.

Effects on Importance Sampling

As explained in Section 2.2.1, the bias and the variance of the self-normalized importance sampling estimator can be reduced by augmenting the number of samples k. Concerning the choice of P n , Hesterberg (2003) gives the optimal noise distribution in terms of reducing the variance. However, there is a non-zero theoretical minimal limit on the variance that can be reached with self-normalized importance sampling. Besides, even approximations of the optimal noise distribution would necessitate knowledge of the score function

∂ ∂θ s θ (w, H)
for every word w in V, which is something we want to avoid computing. Furthermore, while previous results with IS (Bengio andSénécal, 2003, 2008) were finding the method unstable and attempts at adapting P n during learning gave poor results, our experiments show that training was stable for almost all choices of hyperparameters and there was no apparent need to make P n closer to the true data distribution. In this, our experiments match those of [START_REF] Józefowicz | Exploring the limits of language modeling[END_REF]. This stability is ex- plained by the fact that the Tensorflow function used for IS3 is a little different than the algorithm described in [START_REF] Bengio | Quick training of probabilistic neural nets by importance sampling[END_REF]. Indeed, it always includes the target word in the sampled distribution, making the method closer to much more stable complementary sum-sampling [START_REF] Botev | Complementary Sum Sampling for Likelihood Approximation in Large Scale Classification[END_REF], that we described in Section 2.2.3.

In Figure 3.2 are shown training cross-entropies for models using IS, with varying k and α. On the first column of Table 3.3 are the corresponding final perplexity results on the test set. We can confirm that increasing k gives a better final perplexity and that using the unigram distribution is far more efficient than using the uniform distribution.

Effects on Noise-Contrastive Estimation

The results presented in Section 2.3.1 were that as the number k of noise samples by example increases, the choice of the noise distribution P n has less impact on the estimation accuracy. Besides, [START_REF] Gutmann | Noise-contrastive estimation: A new estimation principle for unnormalized statistical models[END_REF] explain that finding the noise distribution that minimizes the estimation error is very difficult. However, the authors also show that for a noise distribution close to the data distribution, there is a guarantee that even for small values of k, the estimation error is close to the theoretical optimum. Then, they suggest that one should first choose P n the closest to the data as possible so that noise can be sampled easily and then make k as large as computationally possible.

Training cross-entropies for models trained with NCE, with varying k and α, are presented on Figures 3.3 and 3.4. Corresponding final perplexity results are presented in the second column of Table 3.3. To not only evaluate how well the model optimizes perplexity, but also how well it performs at the task it is actually training for, we also show the mean probabilities of classifying data samples into the data class -P (C = 1|w, H), when (w, H) ∈ D -and noise samples into the noise class -P (C = 0| ŵ, H), when ŵ ∼ P n -during training. As we we could see on preliminary experiments on the 10K vocabulary, NCE is far less stable than IS. With our configuration, k needs to be of at least 100 samples for the model to attain a reasonable perplexity in 50 epochs. The top graph of Figure 3.3 shows that models with smaller values are far from reaching a similar result. However, when k varies, the classification task changes: it is easier to recognize data when k is low, and easier to recognize noise when k is high, so the second graph is harder to interpret. We can still suppose that it is having an easier classification task (a low k) that makes training less efficient.

While using a uniform distribution is not working in our case, smoothing the unigram distribution seems to make learning easier, as shown on the top graph of Figure 3.4. Still, when we get too far of the unigram distribution, learning is not as precise and the final perplexity is quite high. Looking at classification probabilities, we can see that for low values of α, it is easier to recognize data samples: again, having the classification task easier makes for a less efficient training. Finally, we can see that smoothing the unigram distribution a little is beneficial, probably thanks to having higher values of P n (w) for rare words.

Complexifying the noise distribution

In order to explore a more complex noise distribution P n , we experimented with a bigram (and so, context-dependent) distribution. Training cross-entropies and classification probabilities are shown in Figure 3.5. It is clear that the bigram distribution is far more data-efficient than the unigram and the final perplexity is also better. While the classification task uses the same k, we can also see that the model is able to learn to recognize data samples far better with a bigram distribution. While these results are very interesting, using a context-dependent distribution is very slow in practice, since sampling needs to be done example by example and cannot be done once by batch. While they show that it is indeed more efficient to use a noise distribution closer to the data distribution, these results have no practical application.

Particular case of the BlackOut algorithm

BlackOut [START_REF] Shihao | Blackout: Speeding up recurrent neural network language models with very large vocabularies[END_REF], described in Section 2.3.2) can be seen as NCE with a re-weighted, context-dependent noise distribution: the noise probability given to words is re-scaled using the model distribution on the noise samples. However, these noise samples are still obtained using the original noise distribution: we can expect We can immediately see that training is far more stable than with NCE: by averaging over all samples to obtain re-weighted noise probabilities (see Equation 2.31), BlackOut uses them more effectively. Still, augmenting k improves results. Binary classification probabilities are hard to interpret here, since reweighing the noise probabilities transforms them into two separate sets in a multinomial classification: does the sample belong to category 1 or in one of the categories 2 to k + 1 ? The probabilities of recognizing noise reflect this modification: they seem fixed to a value dependent of k. Here, we can notice that smoothing does not improve results.

Effects on Negative sampling

With negative sampling (NS, described in Section 2.3.3), the model directly parametrizes the log-odds and it learns what is, in the NCE, the ratio of the data and noise distribution, without knowing the values of P n . We expect here to avoid the stability issues caused by having unbalanced weights, coming from very small values of P n (w) for rare words. Results are shown in Figures 3.8 and 3.9 and final testing perplexities are shown in the fourth column of Table 3.3.

We can first notice that training seems indeed more stable than with NCE. Interestingly, while varying k has the same predictable effect as with NCE on binary classification probabilities, the perplexity is very differently affected: having k too high seems to worsen the performance, and k = 50 gives the best final result. The effect of distortion is similar to the effect obtained with NCE and using α = 0.75 gives the best result.

These results seem to confirm the analysis of [START_REF] Józefowicz | Exploring the limits of language modeling[END_REF] and [START_REF] Chen | Strategies for training large vocabulary neural language models[END_REF]: IS is far more data-efficient than NCE, which, learning for a different task, does not optimize perplexity and therefore does not seem adapted to language modeling. While we have explored alternatives to NCE that obtain results that are competitive with IS, we wish to analyse in depth the inner workings of NCE and how to improve its performance.

Impact of the partition function on the training behaviour of NCE

In this section, we will closely monitor the training process of the same language model, varying only the training criterion, i.e MLE, IS or NCE. We should also remember that, apart from the type of classification they learn, NCE and IS are different in how they handle the partition function. In order to better understand what happens during NCE training, we also consider an 'intermediate' model denoted as NCE normalized. This normalizes the scores into a probability distribution P θ (w|H) before computing the NCE objective function. Without any application in practice, this model allows us to better assess the impact of the normalization process.

Self-normalization is crucial for NCE

The training cross-entropies for the 4 models are drawn in the top graph of Figure 3.10. Whether they are trained with MLE or NCE, the normalized models exhibit very similar learning curves. However, while the behavior of the model trained with IS only slightly deviates from the normalized models, the un-normalized model trained with NCE takes far longer to reach a comparable cross-entropy, ending with a sensibly higher value. In the bottom graph, we can observe the values of minus the objective function4 and both of its terms (the first, data-dependent and the second, containing the noise samples) for the normalized and un-normalized models trained with NCE:

-J θ = H,w∈D -log p θ (w|H) p θ (w|H) + kP n (w) - k i=1 log kP n ( ŵi ) p θ ( ŵi |H) + kP n ( ŵi ) (3.1)
We can observe a small decrease of the second term for the normalized model, whereas for the un-normalized, it starts with high values and decreases to become closer to the normalized one. Moreover, the gap between the two data-dependent terms stays high at the end of training.

For a deeper analysis, we study the values of the partition function during training. For both the normalized and the un-normalized models, the partition function Z

-J θ = H,w∈D -log r θ (w, H) r θ (w, H) + 1 - k i=1 log 1 r θ ( ŵi , H) + 1 (3.2)
The second term of -J θ is very high for large values of r θ . Since values of P n are always smaller than 1 and k = 100, and knowing the partition function at the beginning of training is large for all contexts, we can assume that r θ ( ŵi |H) is large for a least part of the set of noise samples ( ŵi ) k i=1 . Thus, this second term is the largest part of the objective, whose minimization leads to a decrease of the model scale. However, this is done at the expense of the data-dependent term, since its score increases a little during the first few epochs. If we take a look back at its gradient:

∂ ∂θ J H θ (w) = 1 1 + r θ (w, H) ∂ ∂θ log p θ (w|H) - k i=1 r θ (w, H) r θ (w, H) + 1 ∂ ∂θ log p θ ( ŵi |H)
(3.3) we see that it is always scaled by the weight 1/(1 + r θ (w, H)), which means that the objective does not learn anything from data as long as the model scale has not decreased to a reasonable value. This shows that this 'self-normalization' mechanism is crucial for NCE, but we still need to understand what makes a scaling value reasonable.

In this section, we have shown that when scoring a word w with an input context H, the scale of the model Z θ (H) has an influence on what is learnt. Indeed, a high value of the partition function increases the value of r θ (w, H), which reduces the importance of the data-dependent term of the gradient. That proves the necessity of self-normalizing in order to learn.

Influence of the shape of P n on self-normalization

Now, we would like to understand what role the noise distribution P n is playing in learning. Let us consider again the weight of the gradient of the data-dependent

1.00e+00 1.00e+03 1.00e+06 1.00e+09 1.00e+12 1.00e+15 1.00e+18
Ranges of values taken by the partition function 10 -7 10 -6 10 -5 10 -4 10 -3 10 -2 10 -1 10 0

Last training epoch examples (H, w) for which the word w is one of the 10 most frequent according to the noise distribution P n : the lighter the color is, the higher is that proportion.

Both scales are logarithmic.

term: 1 r θ (w|H) + 1 = kP n (w) p θ (w|H) + kP n (w) .

Having higher values of P n means that the model does not need to scale back the partition function as much to be able to learn from data. Besides, if the noise distribution is correlated with the data distribution, an example with a high value of P n tends to be more frequent. Therefore the model is first able to learn from words w with the higher values of P n (w). However, the lower P n (w) is, the more difficult it is for the model to learn about w. And the associated partition function has to be closer to 1 for the data-term gradient to be meaningful.

We verify our analysis experimentally by looking at the values of the repartition function at the end of training. The histogram is shown in Figure 3.12: this time, each bin is colored according to the proportion of examples associated to the highest values of P n it contains 5 . This allows us to vizualize if the contexts associated to frequent words are less 'self-normalized'. We clearly observe that this is the case: while the majority of the partition functions have values under ≈ 100, the partition functions of contexts associated to the higher values of P n mainly take values that are far larger.

We have just shown that the frequency P n (w) of a word affects how the model learns: the higher P n (w) is, the more important the contribution of the data-term to the objective is. This has another implication: high values of P n (w) counter the effect of high values of the partition function, which means that the model does not need to self-normalize as much for contexts associated to frequent words.

How do these factors affect learning ?

To visualize how learning is affected, we propose to study histograms showing the values taken by r θ for all data and noise samples seen by the model during a training epoch. In orange, we show data samples and in blue, noise samples. As for Figure 3.12, each bin is colored according to the proportion of very high frequency words it has: the clearer it is, the more occurrences of the 10-highest frequency words it contains. As previously, the histograms displayed in this section are in log-scale. We first display these values at initialization, in Figure 3.13. We can see that ratios of occurrences of the frequent words have the lowest values. That makes sense, since the scores given by the model at initialization follow a normal distribution and those given to the most frequent words are divided by the higher values of P n .

In Figure 3.14, we show the histograms for epochs 1, 5, 10, 20 and 30, during training of a normalized model. At epoch 1, we can see that noise samples are still ordered in the same way as at initialization, with the ratios of the occurences of the most frequent words having lower values. Since the model is normalized, the 1.00e-08 1.00e-05 1.00e-02 1.00e+01 1.00e+04 1.00e+07 1.00e+10 1e-08 1e-06 0.0001 0.01 1.0 occurences of the most frequent words in data samples are learnt faster (which aligns with our analysis in Section 3.2.3). As learning progresses, we can see that there is a large number of data samples the model has no uncertainty about: the values of their ratios r θ become well-separated of the values of the ratios for noise samples.

At initialization

In Figure 3.15, we show the histograms for epochs 1, 5, 10, 20 and 30, during training of an un-normalized model. During epoch one, the values taken by the ratios are all over the place and noise samples seem uniformly distributed. During the next epochs, a clear separation between data examples values and noise samples values takes far more time to appear. The only data samples that are completely separated of noise samples at the end of training are occurences of frequent words, which was not the case for the normalized model. This seems to confirm our analysis of Section 3.2.1: for words that are not frequent, self-normalization is necessary before learning.

Easing the training of neural language models with NCE

The observations made in the previous sections show us that an higher discrepancy between high and low P n leads to a more difficult training with NCE -learning is tiered according to word frequencies. As a consequence and because of the Zipfian distribution of word frequencies, using the unigram distribution is harder as the size of the vocabulary grows. As discussed previously, two values strongly impact how a sample is learnt: first, its value of P n ; then the value of the partition function. We will in this section introduce two simple tricks to reduce the negative impact they have on training with NCE. We will verify how they interact with various values of k and α, first independently, then when used together -perplexity results on the test set of the PTB are presented in Table 3.4. Finally, we will present a summary of the best configurations of sampling based methods for a fixed k and check their efficiency on a much larger corpus: the 1 Billion Word Benchmark dataset. These results are presented in Table 3.6.

Helping the model by learning to scale

To control the partition function, we can follow a method introduced by Chen et al. ( 2015 1.00e+00 1.00e+03 1.00e+06 1.00e+09 1.00e+12 1.00e+15 1.00e+18 1e-08 1e-06 0.0001 0.01 1.0 examples (H, w) for which the word w is one of the 10 most frequent according to the noise distribution P n : the lighter the color is, the higher is that proportion. Both scales are logarithmic.

value of Z c , showing its impact. Figure 3.17 shows the histogram of the repartition of values of the partition function, for the final epoch of training a model where we learn Z c . This is to be compared with Figure 3.12, showing the same histogram, but for classic NCE. We can see that the values of the partition function are far smaller and grouped around 1. The first column of Table 3.4 shows how the choices of k and α affect this method. We can see that we obtain reasonable results even with a very low k and that smoothing the unigram distribution is only moderately helpful here. Finally, Table 3.6 shows that learning to scale achieves a similar perplexity as fixing it to the arbitrary value |V| on the PTB.

Helping the model with a well-chosen initialization

To operate on the impact of noise distribution during learning, we turn to negative sampling. We remember that with NS, the model directly parametrizes the log-odds, and we get back an estimation of the conditional probability using the model score and the noise distribution:

P (w|H) ∝ P n (w) exp s N S θ (w, H) (3.4)
Then, the initial values of r θ (w|H) = e s N S θ (w,H) simply depend on the model initialization and the initial values of the partition function are close to 1. We notice that our models trained with negative sampling avoided the initial increase in crossentropy that is visible with NCE, even when we fix or learn Z c . We believe this is due to having an initial model distribution very close to P n , which is a consequence of multiplying final scores by P n , as showed in Equation 3.4.

To verify this, we trained a NCE model for which we initialized the output bias with values of log P n (w). By looking at the repartition of the values of the ratio and partition function at initialization, showed in figure 3.18, we can check that having p θ (w|H) ≈ P n (w) mitigates the main issues described in section 3.2: first, our distribution is far closer to being normalized; then, the values of r θ (w|H) are bundled together around 1/(k + 1). Figure 3.19 presents the histograms showing the repartition of ratios r θ (w|H) during training for this method. At epoch 1, both data and noise samples for nonfrequent words are still concentrated around 1/(k + 1), whereas data samples of frequent words see their value of r θ increase and the noise samples of frequent words see their value of r θ (w|H) decrease. From epoch 5, a large number of data samples of non-frequent words have higher values of r θ and are completely separated from noise samples. At the end of training, the repartition of these ratios resembles the one obtained with the normalized model, in Figure 3.14.

The second column of Table 3.4 shows the efficiency of this method across values of k and α. Strangely, except for a few configurations, including our baseline, using this initialization jointly with learning a parameter scale Z c gives worse results than the initialization alone. We suspect this method to be efficient enough that learning a supplementary parameter (that is very impactful) makes training more difficult.

Summary of results with sampling-based algorithms

As shown in Table 3.6, with our baseline parameters choices, we get our best model on PTB by both using this initialization and learning Z c . The final perplexity is quite better than with Normalized NCE: pairing the 'learning to scale' approach 1.00e+00 1.00e+03 1.00e+06 1.00e+09 1.00e+12 1.00e+15 1.00e+18 1e-08 1e-06 0.0001 0.01 1.0 1.00e-08 1.00e-05 1.00e-02 1.00e+01 1.00e+04 1.00e+07 1.00e+10 1e-08 1e-06 0.0001 0.01 1.0 with the adapted initialization scheme makes NCE far more competitive, with no additional computational cost. Figure 3.20 also shows a learning curve far smoother than those of methods previously presented. We also present in Table 3.6 results with slight smoothing of the noise distribution, for the methods who profit from it. Results on the 1 Billion Words Benchmark are presented in the second column of Table 3.6. In this case, the vocabulary contains 64K words, which renders normalized models very difficult to use in practice6 . We trained the models for a minimum of one epoch and up to two more if models made progress on the validation set perplexity. The hyperparameters we used are shown in Table 3.5. Final results are a little different than with the PTB: initializing the output bias to P n (w) is here a little less efficient, while smoothing the noise distribution with α = 0.75 is more impactful for other sampling-based method, making IS slightly better. We suppose this is due to the shape of the noise distribution, which, being cut at 64K words, only contains frequent words. On the one hand, it makes for a more peaky distribution for very frequent words, which makes training with basic NCE more difficult. Self-normalization is harder and 3 epochs are not enough for the testing perplexity to be brought under the size of the vocabulary. On the other hand, having no long tail composed of very rare words on the noise distribution makes training a little easier for other methods, which renders our second trick less necessary.

Conclusions

In this chapter, we present an in-depth analysis of the inner workings of noise contrastive estimation and propose solutions to ease training allowing the method to reach at least comparable results with importance sampling, which is often considered more efficient. First, an exhaustive series of experiments comparing results of importance sampling (IS), noise contrastive estimation (NCE), BlackOut and negative sampling (NS) when varying the number k of noise samples and the choice of the noise distribution P n shows NCE to perform badly and IS to still outperf- An analyis of the objective function and its gradients first highlights how selfnormalization is crucial if we want the NCE to learn. However, the higher P n is, the less self-normalization has an impact on learning. That also means that infrequent words coming from data samples are harder to learn about and necessitate the model to self-normalize for the associated context. Hence, the large variance of values taken by the noise distribution has a key role in the difficulties met when using NCE, especially for language modeling with large vocabularies, because of the Zipfian shape of the unigram distribution. We verify this analysis using the monitored experiments.

Finally, we propose two solutions to ease training with NCE. First, when including a scaling parameter in the parameters of the model, the scaling process that should be attained via self-normalization can be both stable and efficient. Additional improvements can be obtained by initializing the bias of the output layer according to the noise distribution. This limits the effects of the Zipfian shape of the unigram distribution. Combining this 'learning to scale' approach with the adapted initialization scheme yields a very competitive, yet simple, training strategy for neural language models with large vocabularies and shows convincing results on both the Penn Treebank and the 1 Billion Words Benchmark. Whether we are performing maximum likelihood estimation or noise contrastive estimation, training a neural language model is done by otpimizing a function of our model parameters θ. This objective function is expressed depending on the probability distribution (or its un-normalized version) output by the model. But this objective is also commonly called loss function: that is because it is the expression of a dissimilarity between the parametrized distribution that we are learning and the distribution described by our training data. Learning is in fact minimizing this measure of divergence. For example, in the case of maximum likelihood estimation, the negative likelihood that we minimize is also the Kullback-Leibler divergence between the distribution output by the model and the data distribution: In this chapter, we will work with the divergence measures known as Bregman divergences: the Kullback-Leibler divergence or the Euclidean squared distance are examples of such divergences. We will highlight how Maximum-Likelihood Estimation and some of the sampling-based methods described in Chapter 2 have their objective functions derived from Bregman divergences, and are therefore part of a generalized estimation framework. We will do this generalization in order to gain insight on the inner workings of sampling-based algorithms and to derive new objective functions. The reasoning presented here is based on two successive generalizations. Firstly, the work of [START_REF] Pihlaja | A family of computationally efficient and simple estimators for unnormalized statistical models[END_REF], which described NCE (2.3.1) and score matching [START_REF] Hyvärinen | Estimation of non-normalized statistical models by score matching[END_REF] as part of a set of sampling-based objective functions that lead to a consistent estimation of parameters. Secondly, an extension of this set to a larger class of functions, which are Bregman divergences, in [START_REF] Gutmann | Bregman divergence as general framework to estimate unnormalized statistical models[END_REF].

N LL(θ) = - (H,w)∈D log P H θ (w) = -
In Section 4.1, we will shortly review Bregman divergences and how they can be used to design objective functions for neural probabilistic language modeling. A Bregman divergence is defined as a measure of distance corresponding to a strictly convex function: we will re-obtain methods presented earlier by using the suitable function. For example, the Kullback-Leibler divergence can be obtained by using the Bregman divergence associated to the negative entropy function on a multinomial probability distribution. By minimizing this divergence applied to the data probability distribution and the model probability distribution, we obtain the classic Maximum Likelihood Estimation objective. Some of the methods presented earlier will be obtained by using the corresponding divergence on another domain of application: instead of working with probability distributions, we will work directly with un-normalized model distributions (which we could also call measures), belonging to R |V| + , in order to avoid the costly normalization. In Section 4.2, we will present how we are able to use these divergences without any summation on the full vocabulary, and experiment with example functions presented in [START_REF] Gutmann | Bregman divergence as general framework to estimate unnormalized statistical models[END_REF]. Then, we will apply to language modeling a set of Bregman divergences presenting interesting properties (Theorem 4, [START_REF] Csiszar | Why least squares and maximum entropy? an axiomatic approach to inference for linear inverse problems[END_REF]). Also known as Beta divergences (Section 3, Cichocki and ichi Amari (2010)), they are Bregman divergences derived with a class of generalized entropy functions [START_REF] Eguchi | Entropy and divergence associated with power function and the statistical application[END_REF], obtained via a parametrized power transformation.

In Section 4.3, we will show that objectives based on a surrogate binary classification task, like NCE, can also be obtained by applying a Bregman divergence to a set of binary classification probabilities -instead of multinomial classification probabilities of words into the vocabulary. A composition function allows us to go from one divergence to its corresponding "binary classification" version. We can show that the NCE objective can be derived by applying the Bregman divergence obtained from the negative entropy function to the binary probabilities of classification. This allows us to experiment with a new series of divergences, that come from the previously used class of generalized entropies, followed by the composition function.

Language model objective functions as Bregman divergences

Bregman divergences were first described in [START_REF] Bregman | The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming[END_REF]. Their functional form provides a class of divergences between two functions, indexed by convex functions, which include several existing distance1 measures, as the Euclidean distance or the Kullback-Leibler divergence. Informally, Bregman divergences measure the distance between a convex function and its tangent hyperplane. Convexity gives these divergences interesting properties, which makes them frequently used in statistical learning. A recent characterization of Bregman divergences describes them as the loss functions for which the unique optimal predictor is the conditional expectation E[X|Z], when predicting a random variable X from observations Z [START_REF] Banerjee | On the optimality of conditional expectation as a bregman predictor[END_REF].

Learning by minimizing a Bregman divergence

The functional Bregman divergence corresponding to a function Φ : S → R, which is a strictly convex function defined on a convex set S and twice continuously differentiable on this set, is defined for all f, g ∈ S as:

D Φ (f, g) = Φ(f ) -Φ(g) -∇Φ(g) T (f -g) (4.2)
where ∇ denotes the gradient of a function. We can note that the functional definition is a generalization of the vector and point-wise versions [START_REF] Frigyik | Functional bregman divergence and bayesian estimation of distributions[END_REF]. The Bregman divergence holds several nice properties, which are detailed and proved in various works [START_REF] Yair | Parallel Optimization: Theory, Algorithms and Applications[END_REF][START_REF] Grünwald | Game theory, maximum entropy, minimum discrepancy and robust bayesian decision theory[END_REF][START_REF] Frigyik | Functional bregman divergence and bayesian estimation of distributions[END_REF]. 2 The main one is non-negativity: it stems directly from the strict convexity of Φ. We can also note the linearity and the affine invariance of the divergence with respect to Φ.

We can now specify the functional objects we will manipulate. Since we work with multinomial distributions over a vocabulary V, we can assume that our functions can be defined attributing a value to each word of that vocabulary:

f :V → R w → f (w) (4.3)
and will therefore be applied to a discrete space. Then, to simplify the objects we manipulate, f can be represented by a vector f of |V| values (f w ) w∈V , that verifies f ∈ S ⊂ R |V| . Knowing this, we can outline that in this chapter, we will only work with three possible S: first, the set of probability distributions over V noted ∆ V , where

∆ V = f : f ∈ R |V| + , w∈V f w = 1 (4.4)
Secondly, we will use R |V| + when we wish to work with un-normalized distributions. Lastly, we will use [0, 1] |V| when working with binary classification probabilities for every word in the vocabulary. However, for the sake of consistency, we will retain the functional notations f and f (w), as in the rest of this dissertation, the scores and probabilities outputed by a language model are mostly denoted as functions over V that we evaluate for a word w. In this context, and following [START_REF] Gutmann | Bregman divergence as general framework to estimate unnormalized statistical models[END_REF], it makes sense to restrict ourselves to using a specific kind of Bregman divergence: the separable Bregman divergence (Section 3.5, [START_REF] Grünwald | Game theory, maximum entropy, minimum discrepancy and robust bayesian decision theory[END_REF]). This means that the function Φ can be written as:

Φ(f ) = w∈V φ(f (w))µ V (w) (4.5)
where φ has the same properties as Φ, notably the strict convexity. Depending on our choice of S, φ is defined over [0, 1] or R + . µ V (w) represents a probability mass function over V that allows us to weight the contribution of each dimension (which represent words) to Φ, without any loss of generality. It can, in the simpler case, be the uniform distribution. This allows us to compute the divergence between f and g as a weighted sum of the divergences of their values over their domain V. This restriction on Φ is necessary in order to be able to work with un-normalized models: we do not want to have to evaluate our functions on more than one word w at a time when computing our objective function. Then, the associated divergence is written (using the linearity property):

D Φ (f, g) = w∈V D φ (f (w), g(w))µ V (w) (4.6)
From the non-negativity, we obtain that

D Φ (f, g) = 0 ⇒ f = g
We use the divergence to approximate a function representing our data by a parametric function representing our model. Assuming the first one is fixed, our problem is to minimize the Bregman divergence with respect to the second. Thus, we note f D the function representing our data, and f θ the parametric function. We then minimize the following divergences:

D Φ (f D , f θ ) = w∈V D φ (f D (w), f θ (w))µ V (w) (4.7)
which is equivalent to minimizing the objective:

L φ (f θ ) = w∈V [-φ(f θ (w)) -φ (f θ (w))(f D (w) -f θ (w))] µ V (w) (4.8)

Decomposing the objective in two terms

We can notice that our objective is divided into two parts: one that depends on the data function f D , and the second that only depends on f θ . Following Gutmann and Hirayama ( 2011) again, we re-write this objective with two distinct functions to highlight this separation:

S φ 0 (x) = -φ(x) + φ (x)x and S φ 1 (x) = φ (x) (4.9)
which satisfy, on the domain of φ:

(S φ 0 ) (x) (S φ 1 ) (x)
= x and (S φ 1 ) (x) > 0 (4.10)

Now, the objective defined in Equation 4.8 can be written:

L S φ (f θ ) = w∈V S φ 0 (f θ (w)) -S φ 1 (f θ (w))f D (w) µ V (w) (4.11)
Accounting for the context However, our multinomial distributions are conditional: they depend on a context H. Since they share their parameters θ, we cannot learn them independently with context dependent objectives, but we can define a global objective:

L S φ (f θ ) = H∈H L H S φ (f H θ )µ H (H) (4.12)
where H is the discrete set of possible contexts, and µ H (w) a probability mass function over H, with:

L H S φ (f H θ ) = w∈V S φ 0 (f H θ (w)) -S φ 1 (f H θ (w))f H D (w) µ V (w) (4.13)
We should note that this objective can be also written as the minimization of only one Bregman divergence: we can consider the functions f D and f θ to be defined over H × V. Then, if we assume that f D is included in the possible models, and that there exists a set of parameters θ * such that f θ * = f D , the non-negativity property of the Bregman divergence tells us that it is a minimum of the objective L S , while the convexity property makes it unique.

How to obtain a sample objective ?

Since our goal is to approach f D , the only way for us to obtain an usable objective is to compute the second term as a sample average over examples drawn from D. We will examine the possible ways to do so; however, the difficulty mainly resides in computing the first term efficiently.

Directly learning the data distribution

The most evident choice for our objective is to choose to directly learn the data probability distribution: we then set f D = P D and f θ = P θ , and the probability mass function µ V (w) can be the uniform distribution.

Normalized distribution and MLE

In that case, we can begin by setting S = ∆ V , as presented in Equation 4.4, and our objective is now, for a given context H:

L H S φ (P H θ ) = w∈V S φ 0 (P H θ (w)) - w∈V S φ 1 (P H θ (w))P H D (w) (4.14)
If we choose, as convex function:

φ : [0, 1] → R x → x log(x) (4.15)
which is defined at the origin by continuity. Consequently, Φ is defined as the negative entropy function:

Φ : [0, 1] |V| → R (x 1 , . . . , x |V| ) → |V| i=1 x i log(x i ) (4.16)
It is easy to compute φ (x) = log(x) + 1, which gives S φ 0 (x) = x and S φ 1 (x) = log(x) + 1 Our objective is then:

L H KL (P H θ ) = - w∈V P H D (w) log(P H θ (w)) (4.17)
which amounts to minimizing the Kullback-Leibler (KL) divergence between P D and P θ -that is exactly the MLE objective. However, this implies computing the partition function.

Working with un-normalized distributions ?

We now assume working with an un-normalized parametric distribution, which implies setting S = R |V| . In accordance with previous notation, we now note f θ = p θ . If we choose φ as the negative entropy extended to R + , for a given context H, we obtain the objective:

L H KL (p H θ ) = w∈V p H θ (w) - w∈V P H D (w) log(p H θ (w)) (4.18)
We can consider the second term as an expectation over the data distribution, and evaluate its sample average by drawing examples from the training data. However, the first term still implies summing on the whole vocabulary -and the issue persists for any other choice of φ. We should note that we could approximate the computation of our first term via importance sampling. However, since we are working with un-normalized distribution, it resembles simple importance sampling. This is probably harder to use than approximating the gradient of objective 4.17, which is self-normalized importance sampling, that is the method traditionaly used in language modeling (Section 2.2.1).

Learning un-normalized models using Bregman divergences

As explained in [START_REF] Gutmann | Noise-contrastive estimation: A new estimation principle for unnormalized statistical models[END_REF], an estimation problem can be formulated as a classification problem: by discriminating between observed data samples and noise samples, we can learn a decision boundary between the two. Since we 'know' the properties of the noise distribution, we can learn about the properties of the data distribution via this boundary. Following [START_REF] Gutmann | Bregman divergence as general framework to estimate unnormalized statistical models[END_REF], we can generalize this approach to obtain a class of objectives via Bregman divergences, which are the estimators described in [START_REF] Pihlaja | A family of computationally efficient and simple estimators for unnormalized statistical models[END_REF].

Learning by matching the ratio of data and noise distributions

Let us assume that we have access to a noise distribution P n that we can sample from, and that examples sampled from the data distribution P D (of class C = 1) and P n (of class C = 0) are mixed together, with a ratio of k noise samples by data sample, as in Section 2.3.1. We can define the ratios of distributions:

r H D (w) = P H D (w) kP n (w)
and r H θ (w) =

P H θ (w) kP n (w) (4.19)
Gutmann [START_REF] Gutmann | Bregman divergence as general framework to estimate unnormalized statistical models[END_REF] shows that learning such a ratio implies that we are learning an optimal classifier, while the inverse is not necessarily true. However, putting aside the link to the classification task, we will for now focus on the objective we obtain by choosing the probability mass function µ V (w) to be the noise distribution kP n . Both the data and the model ratio are positive: here, we have S = R |V| . The Bregman divergence associated to Φ between r H D and r H θ can be written as a function of P H θ , which gives the objective function:

L H S φ (P H θ ) = k w∈V S φ 0 P H θ (w) kP n (w) P n (w) - w∈V S φ 1 P H θ (w) kP n (w) P H D (w) (4.20)
As we have seen in Section 2.3.1, we could parametrize separately the partition function. The solution adopted then was to set these parameters to 0 and let the model self-normalize. It amounts to simply working with an un-normalized model distribution p H θ in the model ratio, which is what we will do in the remainder of this section. Then, the objective equals:

L H S φ (p H θ ) = kE ŵ∼Pn S φ 0 p H θ ( ŵ) kP n ( ŵ) -E w∼P H D S φ 1 p H θ (w) kP n (w) (4.21)
from which we obtain a working sample objective:

LH S φ (p H θ ) = kN D i=1 ŵi ∼Pn S φ 0 p H θ ( ŵi ) kP n ( ŵi ) - N D i=1 w i ∼P H D S φ 1 p H θ (w i ) kP n (w i ) (4.22)
The set of parameters θ * maximizing the global version of the sample objective LS φ defines our estimator. [START_REF] Gutmann | Bregman divergence as general framework to estimate unnormalized statistical models[END_REF] explain that it can be proven that, under some technical conditions, this estimator is consistent (converging in probability to the complete objective optimum θ * when the number of samples is large enough) with an asymptotic normal mean square error. These conditions are explicited in [START_REF] Pihlaja | A family of computationally efficient and simple estimators for unnormalized statistical models[END_REF]. They are that P n is non-zero whenever P D is, that there is uniform convergence of the sample objective towards the Bregman divergence, and model identifiability (one-to-one correspondence between θ and f θ ) which translates into having a full-rank fisher information matrix. This is a generalization of theorems 10.13 and 10.18 for proof of consistency of Maximum Likelihood Estimation in [START_REF] Wasserman | All of Statistics: A Concise Course in Statistical Inference[END_REF], under similar conditions.

Experimenting with learning un-normalized models

We have just defined a class of objective functions that can be used to train un-normalized models, derived from a Bregman divergence that we obtain from a strictly convex function φ defined on R + . [START_REF] Pihlaja | A family of computationally efficient and simple estimators for unnormalized statistical models[END_REF] gives several examples of objectives, with their associated functions S φ 0,1 . They are shown in Table 4.1, along with the corresponding function φ, and r represents the ratio p H θ (w)/kP n (w). We Name φ(r) S φ 0 (r)

S φ 1 (r) IS r log(r) -r r log r PO r 2 2 r 2 2 r NCE r log(r) -(1 + r) log(1 + r) -log 1 1+r log r 1+r InvPO -1 r -1 r -1 2r 2 InvIS -1 -log(r) log r -1 r Table 4
.1: Choices of φ corresponding to S 0 and S 1 functions presented in [START_REF] Pihlaja | A family of computationally efficient and simple estimators for unnormalized statistical models[END_REF].

can see that S φ 0 and S φ 1 correspond respectively to the noise term and minus the data term of the objective. The objective denoted as IS is obtained, again, from the negative entropy extended to the axis of positive number3 . This particular choice of φ makes the objective the same as if we applied importance sampling to the objective of Equation 4.13, and differs from the objective of Section 2.2 by not approximating the partition function. We can also re-derive the NCE objective. PO, InvPO and InvIS denote Polynomial, Inverse Polynomial and Inverse IS functions.

The S φ 0,1 functions determine how much we penalize noise and data samples depending on the relative probability mass attributed to the sample by the model compared to the noise distribution. For example, the polynomial objective, being squared on the data term, penalizes far more noise samples ŵ where the ratio p H θ ( ŵ)/kP n ( ŵ) is higher than 1. Now that we are ready to apply our objectives to language modeling, we must also be careful: we have seen in Section 3.2 that the ratio p H θ ( ŵ)/kP n ( ŵ) could take from very small to very large values. This is true even at initialisation, before the NCE objective we used could have any influence on learning. While with NCE, the functions S φ 0,1 are stable for any values of r, it clearly is not the case for the other examples presented here.

First experimental results

In a first series of experiments, we trained models on the Penn Treebank, following the same setup that is exposed at the beginning of the previous chapter, with the hyperparameters presented in Table 3.2. We tried the IS, InvIS, PO and InvPO objectives, trained with SGD with varying learning rates (1.0, 0.1, 0.01). We also tried the tricks presented at the end of the previous chapter, in Section 3.3, to ease learning. As expected, in all configurations, the scores outputed by InvPO begin to overflow during the first epoch of training. This is also mostly the case for the IS objective, but using both training tricks and a low learning rate allows the model to progress, even if learning is very slow and the perplexity reached stays very high. The InvIS objective also overflows in most cases, but when we initialize the bias to the values of P n (w), it manages to learn; however, it stagnates after reaching a test set perplexity of 900. Inversely, the PO objective seems to be learning properly, but is very slow for every learning rate, and progress seems to stop for very high test set perplexity. This is still verified when we learn a scaling parameter. However, when we initialize the bias to the values of P n (w), the model overflows too.

Power-transformed entropy and beta divergence

In order to gain a better flexibility and to avoid overflows, we investigated the use of power transformations. In the four objectives presented earlier, at least one of the functions S φ 0,1 has a linear or squared (or inverse and inverse squared) term: we would like to experiment with functions that are transformed by a power β that verifies |β| < 1. To do so, we use, as function Φ, a power entropy, parametrized by a number β ∈ R4 :

φ β (r) =          1 β(β-1) (r β -βr + β -1) if β = 0, 1 r log(r) -r + 1 if β = 1 r -log(r) -1 if β = 0 (4.23)
It is easy to verify that φ β is strictly convex for any β. We should note that here again, since Bregman divergences are affine invariant with respect to φ, modifying the constant and linear terms in the entropy above does not change the resulting objective. Knowing that, we immediately observe that this class of functions generalizes the functions φ we used to obtain the objectives IS and InvIS, for β = 1 and β = 0. We can also easily derive that PO corresponds to β = 2 and InvPO to β = -1. In fact, the class of Bregman divergences derived from the φ β functions are known as Beta-divergences [START_REF] Basu | Robust and efficient estimation by minimising a density power divergence[END_REF]). They possess an interesting property: they are the Bregman divergences that are homogeneous of degree β, which means they are characterized by their multiplicative scaling behaviour [START_REF] Csiszar | Why least squares and maximum entropy? an axiomatic approach to inference for linear inverse problems[END_REF][START_REF] Cichocki | Families of alpha-beta-and gamma-divergences: Flexible and robust measures of similarities[END_REF]:

∀λ ∈ R, D Φ β (λf, λg) = λ β D Φ β (f, g) (4.24)
In the case β = 1, we find that D Φ 1 is the KL-divergence extended to vectors of positive numbers, or I-divergence, while with β = 2, we obtain that D Φ 2 is the standard squared Euclidean distance, or L 2 norm. The functions S φ β 0,1 associated to φ β are:

S φ β 0 (r) =          r β -1 β r -1 log(r) and S φ β 1 (r) =          r β-1 -1 β-1 if β = 0, 1 log(r) if β = 1 1 -1 r if β = 0 (4.25)
Then, for our particular application, we are mainly interested in values of β that are strictly between 0 and 1. We experiment with several values, using the

From learning ratios to directly learning classification probabilities

In the previous section, we have seen that the NCE objective can be seen as the minimization of a Bregman divergence between the ratio of data and noise distributions, and the ratio of model and noise distributions. However, we had difficulties learning with other Bregman divergences derived from simple functions -and we obtained disappointing performances with working objectives. To understand the performance of NCE compared to the other objectives we experimented with, we look into the surrogate classification task. If we note the posterior class probabilities of an example coming from the data (C = 1) or the noise (C = 0) as:

P H D (C = 1|w) = P H D (w) P H D (w) + kP n (w) P H D (C = 0|w) = 1 -P H D (C = 1|w) (4.26)
and that we define similar posterior classification probabilities using the model distribution, we easily derive that:

r H θ (w) = P H θ (C = 1|w)P (C = 0) kP H θ (C = 0|w)P (C = 1) = P H θ (C = 1|w) P H θ (C = 0|w) = P H θ (C = 1|w) 1 -P H θ (C = 1|w) (4.27)
While this shows that the ratio can serve as discriminant function between the two classes, and that it allows us to learn an optimal classifier, it also gives us a direct link between the ratio and the quantity that is directly optimized when learning for a binary classification task: P H θ (C = 1|w). This quantity can be obtained from the ratio as follows:

P H θ (C = 1|w) = r H θ (w) 1 + r H θ (w) (4.28)

Minimizing the divergence between posterior classification probabilities and link to NCE

We can consider the probabilities of recognizing the data as functions defined on V taking values in [0, 1]. That means that here, we have S = [0, 1] |V| -we can then apply the general objective of Equation 4.13 to minimize the divergence between the functions P H D (C = 1|.) and P H θ (C = 1|.). The probability mass function µ V (w) is the mixture from which we draw the samples:

µ V (w) = P H D (w) + kP n (w)
We obtain the following objective:

L H S φ (P H θ (C = 1|.)) = w∈V S φ 0 (P H θ (C = 1|w)) -S φ 1 (P H θ (C = 1|w))P H D (C = 1|w) µ V (w) (4.29)
First, let us use the negative entropy of a binary random variable as convex function φ BinClassif :

φ BinClassif : [0, 1] → R p → p log(p) + (1 -p) log(1 -p) (4.30)
Then, we obtain the functions

S BinClassif 0 (p) = log 1 1 -p and S BinClassif 1 (p) = log p 1 -p (4.31)
which gives us the objective:

L H BinClassif (P H θ (C = 1|.)) = - w∈V log(P H θ (C = 0|w))µ V (w) - w∈V log(P H θ (C = 1|w)) -log(P H θ (C = 0|w)) P H D (C = 1|w)µ V (w) (4.32)
that we can factorize as:

L H BinClassif (P H θ (C = 1|.)) = - w∈V log(P H θ (C = 0|w))(1 -P H D (C = 1|w))µ V (w) - w∈V log(P H θ (C = 1|w))P H D (C = 1|w)µ V (w) (4.33)
We then use the Equations 4.26 and their model versions to re-write our objective:

L H BinClassif (P H θ (C = 1|.)) = - w∈V log kP n (w) p H θ (w) + kP n (w) kP n (w) P H D (w) + kP n (w) µ V (w) - w∈V log p H θ (w) p H θ (w) + kP n (w) P H D (w) P H D (w) + kP n (w) µ V (w) (4.34)
Here, replacing µ V by its corresponding probability mass function, we obtain:

L H BinClassif (P H θ (C = 1|.)) ∝ - w∈V log kP n (w) p H θ (w) + kP n (w) kP n (w) - w∈V log p H θ (w) p H θ (w) + kP n (w) P H D (w) = -kE ŵ∼Pn log kP n ( ŵ) p H θ ( ŵ) + kP n ( ŵ) -E w∼P H D log p H θ (w) p H θ (w) + kP n (w) (4.35
) of which the sample version is minus the NCE objective (that we maximize, whereas here we minimize the objective) described in Equation 2.27.

Establishing a link between φ Ratio and φ BinClassif

We have just shown that minimizing the Bregman divergence between the functions P H D (C = 1|.) and P H θ (C = 1|.) that associate to a word a binary probability of classification, is exactly maximizing the NCE objective. This gives us an occurrence where minimizing a Bregman divergence that we derive from φ BinClassif (the binary negative entropy) between the functions P H D (C = 1|.) and P H θ (C = 1|.) is equivalent to minimizing a Bregman divergence derived from φ Ratio (with φ Ratio N CE (r) = r log(r) -(1 + r) log(1 + r)) between the functions r H D and r H θ . We would like to be able to work with ratios, because they are obtained directly from the output of neural language models. We would also like to be optimizing more efficiently the classification task -which we can do by using a Bregman divergence applied to the classification. To conciliate both, we outline a formal way to derive a function φ adapted to working with ratios from a corresponding function φ BinClassif : this gives us an objective better adapted to classification, while still being usable directly at the output of the neural language model. Obtaining φ Ratio is simply a matter of composing φ BinClassif with a function σ which allows to obtain the classification probabilities from the ratio (as described in Equation 4.28):

σ : R + → [0, 1] r → r 1 + r (4.36)
We immediately notice that, thanks to this composition, the values manipulated during training stay between 0 and 1, which was not the case for all the objectives we experimented in Section 4.2.2. However, to obtain the right transformation, we need to account for the fact that we used different probability mass functions to integrate over V for different divergences. We then multiply φ BinClassif by the ratio of the probability mass function used in this section and the one used in Section 4.2.1. This ratio is written as:

P H D (w) + kP n (w) kP n (w) = 1 + r H D (w) (4.37)
Then, we get the transformation:

φ Ratio : R + → R r → (1 + r)φ BinClassif r 1 + r (4.38)
Proving that the obtained φ Ratio is convex ensures that we are still within our framework. Then, the divergences derived from φ Ratio and φ BinClassif verify:

D Φ Ratio (r H D , r H θ ) = D Φ BinClassif (P H D (C = 1|.), P H θ (C = 1|.))
We keep both proofs for the Appendix A.

Directly applying β-divergences to binary classification

We have seen previously that using the binary negative entropy as φ BinClassif yields the NCE objective. If we would like to extend this to the power entropy functions defined in Equation 4.23, we should mimic the derivation used to obtain NCE and use the function:

φ BinClassif β = φ β (p) + φ β (1 -p)
In that case, with β = 1, we would re-derive the NCE objective. However, we could try to simply use

φ BinClassif β (p) = φ β (p)
We experimented with both ways. While they give almost the same results in the case where β = 1, only the second one seemed to provide stable learning for the other values of β, which is a result we plan to investigate on. Applying Equation 4.38, we obtain:

φ Ratio β : R + → R r → (1 + r)φ β r 1 + r (4.39)
which gives:

φ Ratio β (r) =          1 β(β-1) (r β (1 + r) 1-β -r + β -1) if β = 0, 1 r log r 1+r -1 if β = 1 -(1 + r) log r 1+r -1 if β = 0 (4.40)
and the associated functions S φ Ratio β 0,1 are:

S φ Ratio β 0 (r) =            1 β r 1+r β -1 β if β = 0, 1 r 1+r -1 if β = 1 log r 1+r if β = 0 (4.41)
and:

S φ Ratio β 1 (r) =            1 β-1 r 1+r β-1 -1 β r 1+r β -1 β(β-1) if β = 0, 1 log r 1+r + 1 1+r if β = 1 -log r 1+r -1 r if β = 0 (4.42)
We should notice that, as for the function associated to NCE S N CE 0,1 showed in in Table 4.1, the ratio r only appears inside of the term r/(1 + r) for the functions S φ Ratio β 0,1 if β = 0. We expect learning procedures to be far more stable and resemble those of NCE.

Experimental results

For this series of experiments, we use a larger range of values for β. We experiment on the PTB again and verify the efficiency of our objectives on the 1 Billion Word Benchmark, using the same setup and hyperparameters as in the previous chapter (see Table 3.5). Again, we use both the training tricks we defined earlier.

Results are presented in Table 4.3. Here again, the influence of β on the quality of learning is clear -however, for both corpora, we match and even mildly improve the results obtained previously with NCE. , for various values of β. 'X' indicates that the model did not reach a perplexity under the size of the vocabulary within the maximal number of training epochs.

β PTB 1BW Benchmark -1.0 X X -0.25 X X 0.0 X X 0.25
For β = 1, we obtain perplexities that are very close to the equivalent results obtained with NCE at the end of the previous chapter (148.4 for the PTB and 71.3 for the 1BW Benchmark). The values of the β parameter that give the best results can be inferred by looking at previous experiments made with the Beta-divergence: indeed, for other applications, it has been shown [START_REF] Cichocki | Generalized alpha-beta divergences and their application to robust nonnegative matrix factorization[END_REF][START_REF] Basu | Robust and efficient estimation by minimising a density power divergence[END_REF] that the choice of β implies a trade-off between robustness to outliers (for β > 1) and efficiency (for β close to 1). Nevertheless, these results show that the application of these divergences to language modeling should be explored further; indeed, we believe they can be used judiciously to ease training in the difficult case of training the model with a very large vocabulary.

Conclusions

We present in this chapter a generalization of the maximum-likelihood estimation objective and of the noise contrastive estimation objective, as minimizations of Bregman divergences. We can apply these divergences to probability distributions of the data and model, but to avoid computing the partition function, we chose to work with the un-normalized distribution outputed by the model. We use a surrogate classification task, which introduces a noise distribution that we sample from: learning an optimal optimizer for this classification task can be done by minimizing the divergence between the ratios of data and noise probabilities and of model and noise probabilities.

We experiment with Bregman divergences derived from simple functions, presented in [START_REF] Pihlaja | A family of computationally efficient and simple estimators for unnormalized statistical models[END_REF]. However, given the very large range of values taken by the model ratios, these functions overflowed during learning. Using a power-transformed entropy function, determined by a parameter β, we experiment with Beta divergences. Learning is successful only for values of β for which model ratios have an exponent that is in absolute value strictly smaller than 1.

We then show that the NCE objective can be seen as a Bregman divergence applied to functions associating to each word in the vocabulary their binary classification probability. We derive a composition rule, allowing us to re-write Bregman divergences applied to these functions as divergences applied to ratios. This composition rule has the advantage of transforming the ratios into values that are in the inverval [0, 1], ensuring stability during learning. We finally experiment with these new classes of divergences, that we derive from the power-transformed entropy functions. We obtain far more convincing results, that show that the best values of β are a little higher than 1.

Chapter 5 Output Subword-based representations for language modeling

In the previous chapters of this dissertation, we mainly focused our efforts on methods designed to reduce the training time of large-vocabulary neural language models. However, large computation time is not the only practical issue met when training these models. A different, but not less important issue, affects the distributed representation of infrequent words. While in Section 1.1, we discussed how discrete models need a large number of parameters and are not able to generalize, we encounter a similar problem with continuous models as their vocabulary grow. Indeed, because of the Zipfian shape of the frequency distribution of words in a text, a large part of the vocabulary is composed by infrequent words that only occur a few times in the training data. Since they are optimized on only a few examples, the parametrized representations that are jointly learnt for these infrequent words are not suitable.

On the other hand, the discrete correspondence between a word and its embedding implies that the word structure is overlooked, even though it could provide us precious information on these infrequent words. Besides, a model should be able to use information learnt on frequent words to better represent infrequent words that are similar. Another drawback of learning a different embedding for each word, independently of their structure and frequence, is that it becomes very costly in memory as the vocabulary grows. Moreover, while these issues are already impactful for a morphologically poor language like English, for morphologically-rich languages, like Czech or German, there is a combinatorial explosion of word forms, most of which are hardly observed on training data, which renders the language modelling task even more difficult.

As we discussed previously, rare words can be replaced by a special token UNK. This can be seen as using a word class to merge very different words without any distinction. Using different word classes to handle out-of-vocabulary words (OOVs) [START_REF] Allauzen | Open vocabulary asr for audiovisual document indexation[END_REF] does not really solve this difficulty, since infrequent words are difficult to classify. A way to deal with this issue is to not stop at the level of word units, but to also use subword units. Whether they are built via a different supervised method with embedded language knowledge, or from the training data, exploiting information from subword units has been attempted many times. It has especially been the case for speech recognition, where they mainly allow to reduce the number of OOV words. While most subword-based models were focused on a specific language, [START_REF] Creutz | Morph-based speech recognition and modeling of out-of-vocabulary words across languages[END_REF] is a representative example of a model applied to several morphologically-rich languages. One of the first occurrences of general language models integrating morphological features to represent words is the factored language model [START_REF] Bilmes | Factored language models and generalized parallel backoff[END_REF] and its neural version [START_REF] Alexandrescu | Factored neural language models[END_REF]. Input words are represented by their embeddings, plus several other features, including morphemes. To alleviate the impact of OOVs, Mueller and Schuetze (2011) used morphological features for class-based predictions when input words are unknown, obtaining state-of-the-art results on English. While recurrent neural networks have shown excellent performances for character-level language modeling (Sutskever et al., 2011;Hermans and Schrauwen, 2013), the results of such models are usually worse than those that use word-level prediction, since they have to consider a far longer history of tokens to be able to predict the next one correctly. While more recent work [START_REF] Hwang | Character-level language modeling with hierarchical recurrent neural networks[END_REF] seems to obtain very satisfactory results with a supplementary word-level layer that allows a better processing of the longer history, we will in our work always use word-level prediction.

While replacing the input word embeddings with this kind of representations in neural language models has been experimented with exhaustively [START_REF] Kim | Character-aware neural language models[END_REF][START_REF] Vania | From characters to words to in between: Do we capture morphology?[END_REF][START_REF] Verwimp | Character-word LSTM language models[END_REF], the predicted words are only scored based on their word embeddings. As previously explained, if the vocabulary contains infrequent words, these representations may be barely learnt. Since we aim at improving infrequent word representations, we will, in this chapter, experiment with augmenting or replacing output word embeddings with representations built from subwords. To the best of our knowledge, such an idea has only been experimented by [START_REF] Józefowicz | Exploring the limits of language modeling[END_REF], which evaluates the use of convolutional and LSTM layers to build word representations for output words. They allow the model to trade size against perplexity, since their model performs worse than the classic softmax approach, but with far less parameters.

We will, in Section 5.1, begin with a presentation of the various architectures we will use to obtain these word representations from subwords. We then propose to study the training of a language model which augments or completely replaces output words representations with character-based representations. In Section 5.2, we will apply our model on a Czech dataset, and present a series of experiments comparing the effect of different architectures, as well as the effect of different sizes of output look-up tables. Finally, we use the results obtained in Chapter 3 to try to improve our models, and extend our experiments to English, with the PennTreebank, for comparaison.

Representing words

Usually, input and output word embeddings are parameters, stored in look-up matrices W and W out . As we explained in Section 1.2, the word embedding r word w of a word w is simply the column of W corresponding to its index in the vocabulary V: r word w = [W] w . We present in this section different ways to build embeddings r subword w as a function of a decomposition of the word w into subwords. Quite a lot of work have been recently done with models representing words as function of subwords units. Some are using morphological features, with a recursive structure (Luong et al., 2013), or an additive one [START_REF] Botha | Compositional Morphology for Word Representations and Language Modelling[END_REF]. However, language models that extract features directly from the character sequence are gaining popularity, whether they use character n-grams [START_REF] Sperr | Letter n-gram-based input encoding for continuous space language models[END_REF] [START_REF] Kim | Character-aware neural language models[END_REF] or a Bi-LSTM layer [START_REF] Ling | Finding function in form: Compositional character models for open vocabulary word representation[END_REF], as they avoid using an external morphological analyser. These types of models have also been applied with success to several other task, including learning word representations [START_REF] Qiu | Co-learning of word representations and morpheme representations[END_REF][START_REF] Cotterell | Morphological smoothing and extrapolation of word embeddings[END_REF][START_REF] Bojanowski | Enriching word vectors with subword information[END_REF][START_REF] Wieting | Charagram: Embedding words and sentences via character n-grams[END_REF], POS tagging 1 [START_REF] Plank | Multilingual part-of-speech tagging with bidirectional long short-term memory models and auxiliary loss[END_REF][START_REF] Ma | End-to-end sequence labeling via bi-directional LSTM-CNNs-CRF[END_REF][START_REF] Heigold | An extensive empirical evaluation of character-based morphological tagging for 14 languages[END_REF], Named entity recognition [START_REF] Gillick | Multilingual language processing from bytes[END_REF], Parsing [START_REF] Ballesteros | Improved transition-based parsing by modeling characters instead of words with LSTMs[END_REF] and Machine translation [START_REF] Costa-Jussà | Character-based neural machine translation[END_REF]. Recently, an exhaustive summary of previous work on building word representations by composing subword units was presented in [START_REF] Vania | From characters to words to in between: Do we capture morphology?[END_REF]. This work also compares the different types of subword unit, how they are composed, and their impact on various morphological typologies. Among those, we consider two types of representations: decomposing words into characters (or n-grams of characters), and decomposing them into a Lemma and positional tags using a morphological analysis. An example of these different decompositions is shown in Table 5.1.

Decomposition into characters

A word w is a character sequence {c 1 , .., c |w| }, where the characters belong to a character vocabulary V c . Let C ∈ R dc×|Vc| be the character embedding matrix. Then, the characters are represented by embeddings of dimension d c , {r char c 1 , .., r char c |w| }, where r char c i = [C] c i denotes the vector associated to the character c i . We can note that the character vocabulary is typically far smaller than a word vocabulary. To infer a word embedding from its character embeddings, we use two different architectures.

Using a convolution layer

First, a convolution layer [START_REF] Waibel | Readings in Speech Recognition, chapter Phoneme Recognition Using Time-delay Neural Networks[END_REF]Collobert et al., 2011), similar to layers used in Santos and Zadrozny (2014); [START_REF] Kim | Character-aware neural language models[END_REF], which applies a convolution matrix W CN N nc ∈ R dcnc×dr over a sliding window of n c characters, producing local features:

x n nc = W CN N nc (r char c n-nc+1 : .. : r char cn ) T + b CN N nc (5.1)
We add n c -1 padding vectors on each side of the word, and x n nc is a vector obtained for each of the n + n c -1 possible character n c -gram. Each coordinate [x n nc ] i of this vector depends on the corresponding column [W CN N nc ] i of the convolution matrix. We can see each of these columns as different convolution filters: using d r of these filters results in a representation of dimension d r . The embedding of w is then obtained by applying a max-pooling function, followed by an activation function φ, over each of these coordinates:

[r nc w ] i = φ |w|-nc+1 max n=1 [x n nc ] i (5.2)
We can use filters of different sizes n c 1 , . . . , n c f and concatenate their results:

1 Which is a task we also addressed with some of these architectures: see Annex D An exemple of such a layer with filters of size 3 is shown in Figure 5.1. We note this layer CharCNN (for Character Convolutional Neural Network ).

Using a recurrent layer

We use a bi-LSTM [START_REF] Hochreiter | Long short-term memory[END_REF][START_REF] Graves | Bidirectional LSTM networks for improved phoneme classification and recognition[END_REF], on characters, similarly to [START_REF] Ling | Finding function in form: Compositional character models for open vocabulary word representation[END_REF]. It combines the final states --→ h |w| and ←h 1 of two LSTMs, respectively over the character sequence and the reverse character sequence, which are computed as such:

- → h i = LST M (r char c i , --→ h i-1 ) ← - h j = LST M (r char c j , ← -- h j+1 )
We then concatenates them to obtain the representation:

r CharBiLST M w = --→ h |w| : ← - h 1 (5.4)
An example of such a layer is shown in Figure 5.2. We note it CharBiLSTM.

Decomposing morphologically

For morphologically-rich languages, the different morphological properties of a word (gender, case, ... ) are usually encoded using multiple tags, as shown in Table 5.1. Therefore, a word w is decomposed into a lemma l along with a set of associated sub-tags T = {t 1 , .., t |T | } of fixed size |T |. For a given word, a single tag can be created by the concatenation of the subtags. However, this implies a large tagset and mitigates the generalization power since some sub-tags combinations can remain unobserved on training data. In this work, we prefer a factored representation where each sub-tag is considered independently.

Lemmas, similarly to surface forms, are represented by |V l | vectors stored in a look-up matrix l ∈ R d l ×|V l | , and r lemma w = [L] w . Each sub-tag has its own vocabulary and its own look-up matrix. However, the additional cost is negligible given their small size (which we will see with Czech in Table 5.3b). To infer a word embedding from a sub-tags set, we also use two methods. The first method consists in concatenating their embeddings:

r T agConcat T = r tag 1 t 1 : . . . : r tag i t i : . . . : r tag |T | t |T | (5.5)
The second method uses a bidirectionnal LSTM on the sequence of tags T , using exactly the same structure as in Section 5.1.1:

r T agBiLST M T = --→ h |T | : ← - h 1 (5.6)
We note these layers TagsConcat and TagsBiLSTM.

In several works, an intermediate layer is used between the obtained subwordbased representations and the hidden layer. It can be seen as a way to blend together representations coming from different sources (whether it is word embeddings, the representations resulting from differently sized convolution filters, or from the two directions of a BiLSTM), instead of simply concatenating them. [START_REF] Kim | Character-aware neural language models[END_REF] uses a highway layer [START_REF] Kumar Srivastava | Highway networks[END_REF] to do so, which we use here too. Finally, [START_REF] Verwimp | Character-word LSTM language models[END_REF] implements the simpler solution of concatenating character embeddings, which we believe to be impractical to use for output representations, since it is in practice difficult to apply a highway layer to blend those character embeddings.

Application to language modeling

As previously, the experiment are conducted using a recurrent language model, with LSTMs (Section 1.2.2). Integrating subword-based output representations in a language model is straigthforward: as illustrated in Figure 5.3, we concatenate word, character-based or lemma and tags embeddings, to obtain input and output word representations. Table 5.2 summarizes the various representations we used in our experiments, for both input and output words. However, since the traditional output layer of a neural language model includes a softmax activation function, we face a significant issue: not only do we need to sum scores over the full vocabulary, we also need to compute representations using a specific subword-based layer for every word in the vocabulary, in order to compute those scores for each example. This is, of course, very costly.

Training a language model with subword-based output representations

To avoid such a heavy training cost, we train our language model with a samplingbased method, which we presented in Chapter 2. To begin, we choose importance sampling, which is used by the authors of [START_REF] Józefowicz | Exploring the limits of language modeling[END_REF] to train the model they built with character-based output representations. This allows us to only compute the subword-based representations of target words, plus the words drawn as noise samples during training. However, we still need to compute these representations for all words when doing inference.

We experimented with various ways to link the subword-based layers to the model and between themselves. We first apply a highway layer to the output representation, but it seems almost always counter-productive, rendering training more unstable. In all experiments we present, weights are not tied between input and output representations, since our preliminary experiments with tied weights always gave worst results. Besides, we do not mix structures for character-level representations (for example, using an input CharCNN and output CharLSTM) since our first experiments gave systematically worse results than using the same structures). When using different types of representations, we also kept consistency between vocabularies: if both lemmas and words are used in a model, any lemma considered unknown has its corresponding word unknown, and inversely. The same (or corresponding) vocabularies are used for all inputs representations, all outputs rep-resentation, and evaluation. The only exception is presented in Section 5.3.3. When using a character-based output representation, during evaluation, the representation of the unknown token is built from a specific unknown character token, a specific unknown lemma token, and specific unknown tags tokens that are parameters of the model.

The following experiments aim at comparing potential uses of those different subword-based word representations, and thus are not directed towards performance. For this reason, we use the same implementation for all experiments and do not specifically try to optimize the general model structure or the dimensional hyperparameters. We also use representations of the same size, indifferently of how we build them, to verify the potential gain they bring. A more complete comparaison of the systems we experiment with should take in account both the total dimension of the layers and the total number of parameters they use.

To fully exploit the potential of subword-based representations, we choose to apply our model to a morphologically complex language, Czech. We then apply our model to English with the Penn Treebank (PTB), in order to verify the impact of subword-based representations on this morphologically simpler language.

Czech data and setup

We used data from the parallel corpus News-commentary 2015, from the WMT News MT Task. The data consists in 210K word sequences, amounting in about 4,7M tokens. We divide the data into a training, development and testing sets. The development and testing sets are comprised of 10K word sequences and 150K tokens each. In our experiments, we use different vocabulary sizes, which we obtain by varying a frequency threshold f T h : words are selected when their frequency in the training data is strictly higher than the threshold. Table 5.3a shows the correspondences between vocabulary sizes and thresholds. Since this data comes from a parallel corpus, we can compare the distributions of word frequencies in English and Czech. These distributions are shown in Figure 5.4. The main difference is that the tail of the Czech distribution is far longer, which means it contains far more infrequent words than the English distribution. It also implies that the Czech vocabulary is far larger, being more than twice the size of the English vocabulary, which justifies our approach.

|V C | |V L | |V tag i | i=1..|T |
155 61364 [12,65,11,6,9,6,3,5,5,4,3,3] (b) Vocabulary sizes for subword units The lemma and tags decomposition presented in Section 5.1.2 was obtained with Morphodita [START_REF] Straková | Open-source tools for morphology, lemmatization, pos tagging and named entity recognition[END_REF]. There are 12 tag categories for Czech. Vocabulary sizes for characters, lemmas and tags are detailed in Table 5.3b. As previously mentioned, the vocabulary sizes for characters and tags are far smaller than for words and lemmas, which makes these representations far less costly in term of memory usage. The hyperparameters we use are shown in Table 5.4. We choose our subword and word embedding dimensions in order to obtain, for each type of representation, an embedding dimension of 150. In the case of the CharCNN, we use filters of 3, 5 and 7 characters, respectively of dimension 30, 50, and 70. In the case of the CharBiLSTM, each LSTM has a dimension of 75. Tags embeddings also add up to a size of 150. Finally, the input layer dimension depends on how many input representations we use, while the hidden layer size depends on the number of output representations.

Given the large size of the vocabulary, we used k = 500 noise samples by batch. As before, we backtrack learning when no progress has been made on the validation set perplexity, stopping training after 10 consecutive backtrackings.

Preliminary experiments on input representations and vocabulary sizes

First, we train 'classical' models, where we only change the type of input representation we use, and we keep the classic output representation based only on words. Since we want to evaluate the difficulty of representing infrequent words, we begin by training models with various vocabulary sizes (which are detailed in Table 5.3a). For this set of experiments, we choose models using word based input representations, character based input representations, a concatenation of both, and a concatenation of lemma and tag based input representations. To observe variability in the final perplexity results, we present the average of the results obtained on 5 models, and the standard deviation. These values are shown in Table 5.5. Note that the baseline result for the full vocabulary is a final mean perplexity of 388.1.

The larger the vocabulary is, the less stable the training is. The standard deviation especially grows when we go from excluding words that only appear twice from the vocabulary (f W T h = 2), to training with the full vocabulary (f W T h = 0). That tendency is stronger with models using only subword based representations (Char-CNN). Some of that instability can be pinned on the fact that we do not have any unkown words in the training data, which makes the associated embedding useless at evaluation. However, we suppose it mostly comes from the fact that a large number of words only appear once in the training data, and are not adequatly learned. This is probably accentuated by the fact that our training method almost never samples these words: their representation may only be updated once by epoch.

Despite these variations, it is clear that using both word-based and characterbased input representations (Words + CharCNN) is better than our baseline of only word embeddings, which still gives far better results than using only character-based input representation. The efficiency of decomposing the words as a lemma and a set of tags seems to depend on the size of the vocabulary: while it is comparatively not efficient for smaller vocabularies, it works well when we include all words, even giving the best perplexity results. It could indicate that this decomposition allows better generalization to infrequent words.

Experiments on Czech with subword-based output representations

In this section, we experiment with augmenting and replacing output representations with character-based embeddings. We also investigated working with tags, but they were difficult to use in practice. The main issue is that tags can be ambiguous across several occurrences of the same words, which is something we need to normalize in order to predict words. To do so, we tried using specific tokens, or choosing the most frequent tags, but in any configuration, using tags for output representations made the model severly overfit.

Influence of the vocabulary size

First, we would like to study the potential usefulness of subword-based output representations for various vocabulary sizes. Using the representations that gave, as a whole, the best results during the preliminary experiments (Words+CharCNN), we train models with the same vocabulary sizes than before, detailed in Table 5.3a. The mean final perplexity and standard deviation across 5 trainings are shown in Table 5.6, while the perplexity curves of the best of these 5 models are shown in Figure 5.5. Clearly, our model fails to improve upon the conventional word model when the output vocabulary size is relatively small. More precisely, models that use a Words+CharCNN output layer seem unable to learn after a few epochs. We link this behavior to the difficulty met by the authors in [START_REF] Józefowicz | Exploring the limits of language modeling[END_REF]: since most logits are tied when we use an output character-based representationas opposed to independently learned word embeddings, the function mapping from word to word representation is smoother and training becomes more difficult. They used a smaller learning rate and a low dimensional correction factor, learned for each word, as a work-around.

However, increasing the vocabulary size reduces this effect. This is especially clear with the full training vocabulary: in this setup, using a character-based rep-

Effects of the representation choice

We now experiment with various representation choices, in order to assess which combination of input and output representations gives the best performance. However, we limit these experiments to models trained with the full vocabulary, having established that, in our current configuration, augmenting output representations with subwords renders models difficult to train for smaller vocabulary sizes. Table 5.7 gathers the main experimental results.

For any input representation, augmenting the output representation with a character-based embedding, by using a Words+CharCNN output layer, improves the performance of the model. It is especially true for convolutional layers. We also can notice that the improvement is more important for models that performed badly with basic output word embeddings. When using only words as output representations, the best input representations seems to be the Lemmas+Tags input layers (with both architectures), but the Words+CharCNN/BiLSTM input layers are both close. With a Words+CharCNN output layer, all input representations give close results, except for the CharCNN layer. Among them is the best improvement on the baseline, which is a final mean perplexity of 326.3. Overall, biLSTMs perform worse than their convolution/concatenation counterparts. The mean and standard deviations are especially high when characters are used as input representation, making the decomposition into lemma and tags the best choice when using Words + CharbiLSTM output layer.

Our experiments with only character-based embeddings as output representations give results far worse than those using also word-based embeddings. Training is also far more unstable. The observations we previously made are however still valid, with the exception of a model using CharCNN layers for both input and output, which behaves better than other models using the same output representation. We believe these seemingly bad results are linked to the difficulties mentioned in [START_REF] Józefowicz | Exploring the limits of language modeling[END_REF] and in Section 5.3.1. 5.3a. Test perplexities are given for all words, frequent words (frequency > 10) and rare words (frequency < 10). In bold are the best models for a given input representation.

Influence of the word embeddings vocabulary size

Following our observations in Section 5.3.1, we assess the effect of reducing the word look-up table size for the Words+CharCNN output representation, which precedently gave the best results. We do not change the size of the event space: when constructing output representations for words under a chosen frequency, we simply do not learn a specific word representation. For example, using a threshold of f W T h = 10 means that words that appear less thant ten times won't have their own word embedding, and are represented by the unknown word token combined with their character-based representation. Results are shown in Table B.2.

We can see that for all input representations, using a specific unknown token in place of a specific word embedding for words appearing less than 5 times in 5.4 Supplementary results and conclusions training data gives the best performance, or close to, given the standard deviation among the threshold tested. Reducing the look-up table to words only appearing more than 10 times gives globally worse results, even if they are still better than if we keep the full table. Still, with the Lemmas + Tags input layer, both these values seem to give an equivalent result. However, when looking at the perplexities computed on rare words only (which are very hard to interpret given their very high standard deviation) it seems that reducing the lookup table too much damages the model performance. Since these infrequent words contribute so little to the global perplexity, this is mostly unnoticeable on the final results.

Overall, we improve again our best results, obtaining 268.2 as final mean perplexity, from a baseline of 388.1. While in our experiments, the subword-based output representations made training on smaller vocabularies stop early, they improved the full-vocabulary model performances. In this same setup, replacing independent word embeddings by the unknown token for rare words yields further improvement. It is worth noticing that this also opens the vocabulary, since our model can be used to rescore unknown words.

Supplementary results and conclusions

In this section, we verify our previous results by training the same models with NCE while applying the two training tricks developed in Chapter 3. We first update the results we obtained with importance sampling in Czech, then apply our best models to the PTB dataset.

Training with improved NCE on Czech

The main change we obtained when repeating the previous section's experiments using the improved NCE training method concerns using subword-based representations with smaller vocabularies. While, as described in Section 5.3.1, models trained with importance sampling stopped after a few epochs, with NCE, training unfolds normally, giving better results with an output Words + CharCNN layer than only word-based representations for all vocabulary sizes. These results are shown in Table 5.9. Supplementary experiments showed that the determining factor in this new result was to initalize bias weights with the unigram frequencies (in Section 3.3.2); understanding why requires further investigation.

Conclusions

In this chapter, we show how augmenting the output word embeddings of neural language models with subword-based representations can improve performance, especially on very large vocabularies. We first present several ways to decompose words into subwords and the neural architectures we use to build representations from those subwords. We describe the various layers that we use to generate input or output representations, notably the Words + CharCNN layer, that concatenates a word embedding with the output of a convolution layer based on the characters. Computing representations through this kind of layer for the whole vocabulary would be very costly, which is why we use sampling-based methods for training.

We carry out experiments on Czech, with data from the parallel corpus Newscommentary 2015. In those experiments, we train models whose output representations are simple word embeddings and models with a Words + CharCNN output layer, for various vocabulary sizes. When trained with a full vocabulary, the model equipped with augmented output representations outperforms the classical one. We then experiment with various types of input and output representations: consistently, using a concatenation of words and character-based embeddings improves the perplexity of the mode, while the performances of character-based only representations are far behind. We also obtain better results with convolution layers than with biLSTMs. Lastly, we manage to improve upon augmented models by reducing the size of the word look-up table in the Words + CharCNN output layer: we only learn output word embeddings for words that are frequent enough and use the embedding of the unknown word token for the others. The other half of these infrequent words representations are determined by their characters. While it seems to hurt the performance of the model on infrequent words, we obtain overall sizable gains in perplexity.

Finally, we reproduce these experiments with the NCE training tricks presented in Section 3, obtaining similar improvements. Besides, initializing the output bias with unigram probabilities drastically improves models trained on smaller vocabularies, making models augmented with character-based representations better than the classic models at every vocabulary size tested. We verify our results on the Penn Treebank, improving performances once by augmenting the output representations, then again by reducing the size of the output look-up table.

Conclusion

This work investigates practical methods to ease training and improve performances of neural language models with large vocabularies. The main limitation of neural language models is their expensive computational cost: it depends on the size of the vocabulary, with which it grows linearly. Despite several training tricks, the most straightforward way to limit computation time is to limit the vocabulary size, which is not a satisfactory solution for numerous tasks. Most of the existing methods used to train large-vocabulary language models revolve around avoiding the computation of the partition function, which is used to ensure that output scores are normalized into a probability distribution. While Importance Sampling (IS, Section 2.2) directly approximates the gradient computation, Noise Contrastive Estimation (NCE, Section 2.3.1) and related methods use a discriminative objective function that does not require normalization and let the partition function be parametrized separately.

In Chapter 3 we observe how IS is more efficient than NCE, accross various choices of the number k of noise samples and the noise distribution P n . We show that this difference is linked to how normalization is handled by the methods. An analyis of the NCE objective function shows that self-normalization is necessary for the method to learn. It also shows that the Zipfian shape of the unigram distribution plays an important role in the difficulties met when using NCE. We experiment with including a scaling parameter in the parameters of the model, to complement the self-normalization process. Additionally, to reduce this negative impact of the large variance of values taken by the unigram distribution, we initialize the bias of the output layer according to the noise distribution, which adapts the scaling to the word frequency. Those two approaches show convincing results on both the Penn Treebank and the 1 Billion Words Benchmark.

In Chapter 4, we show that the maximum-likelihood estimation objective and the noise contrastive estimation objective derive from the same class of divergences, called Bregman divergences. Using these divergences to solve a surrogate classification task allows us to work with un-normalized distributions. If we apply them directly to functions associating to each word in the vocabulary their binary classification probability, we obtain objective functions for which the weights manipulated are contained in the inverval [0, 1]: this makes learning stable. We experiment with parametrized Beta divergences, of which NCE is a particular case, for the parameter β = 1. Results on both the Penn Treebank and the 1 Billion Words Benchmark show that this class of objectives is especially efficient for values of β a little above 1, where the perplexities reached are slightly better than those obtained with NCE.

Computation time is not the only issue met when training large-vocabularies neural language models: a large part of the vocabulary is composed by infrequent words that are hard to represent, damaging the performances of the model. To allow better generalization for these rare words, we rely on subword units. In Chapter 5, we implement various layers building subword-based representations of words. We carry out experiments on Czech, with data from the parallel corpus News-commentary 2015. In particular, we show that appending character-based representations to output word embeddings when training a neural language model with a full vocabulary consistently improves the perplexity of the model. We also experiment with reducing the size of the output look-up table : we only learn output word embeddings for words that are frequent enough, and use the embedding of the unknown word token for the others. The other half of these infrequent words representations are determined by their characters. While the performance of the model on infrequent words seem to decrease, we overall improve on the perplexity results again.

Future work

To extend the results we obtained on NCE, experiments should be done with even larger vocabularies. Especially, we would like to explore the impact of the long tails of Zipfian distributions on training. Another interesting research direction could be to exploit the knowledge we have gained in Chapter 3 to better employ context-dependant distributions. Indeed, our experiments so far have shown interesting results with the bigram distribution (in Section 3.1.2), but it is impractical to use. We believe that an efficient use of more complex noise distribution should be explored.

Since Chapter 4 defines a class of objectives, there is certainly quite a lot of directions we would like to explore. Besides experimenting with other possible objectives, it could prove useful to re-evaluate the use of an exponential function to make the neural language model outputs positive. Indeed, it is possible to apply the divergences on any kind of convex space. Alternative objectives exploiting that fact may provide other advantages than those presented here.

The experiments we presented in Chapter 5 explore which kind of representation can prove useful. However, performances should be compared as function of the training cost, which could be the training time, but also the number of parameters used. The language model could also be adapted to predict a lemma and a set of tags instead of a word, since these vocabularies are far smaller than the word vocabulary. We could then generate an associated word exploiting these informations, using recent progress on morphological reinflection tasks. This kind of approach would be particularily interesting, since it would allow to generate words unseen during training.

Input

Abstract

In this paper we explore a POS tagging application of neural architectures that can infer word representations from the raw character stream. It relies on two modelling stages that are jointly learnt: a convolutional network that infers a word representation directly from the character stream, followed by a prediction stage. Models are evaluated on a POS and morphological tagging task for German. Experimental results show that the convolutional network can infer meaningful word representations, while for the prediction stage, a well designed and structured strategy allows the model to outperform stateof-the-art results, without any feature engineering.

Introduction

Most modern statistical models for natural language processing (NLP) applications are strongly or fully lexicalized, for instance part-of-speech (POS) and named entity taggers, as well as language models, and parsers. In these models, the observed word form is considered as the elementary unit, while its morphological properties remain neglected. As a result, the vocabulary observed on training data heavily restricts the generalization power of lexicalized models.

Designing subword-level systems is appealing for several reasons. First, words sharing morphological properties often share grammatical function and meaning, and leveraging that information can yield improved word representations. Second, a subword-level analysis can address the outof-vocabulary issue i.e the fact that word-level models fail to meaningfully process unseen word forms. This allows a better processing of morphologically rich languages in which there is a combinatorial explosion of word forms, most of which are not observed during training. Finally, using subword units could allow processing of noisy text such as user-generated content on the Web, where abbreviations, slang usage and spelling mistakes cause the number of word types to explode.

This work investigates models that do not rely on a fixed vocabulary to make a linguistic prediction. Our main focus in this paper is POS tagging, yet the proposed approach could be applied to a wide variety of language processing tasks. Our main contribution is to show that neural networks can successfully learn unlexicalized models that infer a useful word representation from the character stream. This approach achieves state of-the-art performance on a German POS tagging task. This task is difficult because German is a morphologically rich language1 , as reflected by the large number of morphological tags (255) in our study, yielding a grand total of more than 600 POS+MORPH tags. An aggravating factor is that these morphological categories are overtly marked by a handful of highly ambiguous inflection marks (suffixes). We therefore believe that this case study is well suited to assess both the representation and prediction power of our models.

The architecture we explore in section 2 differs from previous work that only consider the character level. Following (Santos and Zadrozny, 2014), it consists in two stages that are jointly learnt. The lower stage is a convolutional network that infers a word embedding from a character string of arbitrary size, while the higher network infers the POS tags based on this word embedding sequence. For the latter, we investigate different architectures of increasing complexities: from a feedforward and context-free inference to a bi-recurrent network that predicts the global sequence. Experimental results (section 4) show that the proposed approach can achieve state of the art performance and that the choice of architecture for the prediction part of the model has a significant impact.

Network Architectures

The different architectures we propose act in two stages to infer, for a sentence s = {w 1 , . . . , w |s| }, a sequence of tags {t 1 , . . . , t |s| }. Each tag belongs to the tagset T . The first stage is designed to represent each word locally, and focuses on capturing the meaningful morphological information. In the second stage, we investigate different ways to predict the tag sequence that differ in how the global information is used.

From character to word level

To obtain word embeddings, the usual approach introduced by (Bengio et al., 2003) relies on a fixed vocabulary W and each word w ∈ W is mapped to a vector of n f real valued features by a look-up matrix W ∈ R |W| * n f . To avoid the use of a fixed vocabulary, we propose to derive a word representation from a sequence of character embedding: if C denotes the finite set of characters, each character is mapped on a vector of n c features gathered in the look-up matrix C.

To infer a word embedding , we use a convolution layer [START_REF] Waibel | Readings in Speech Recognition, chapter Phoneme Recognition Using Time-delay Neural Networks[END_REF]Collobert et al., 2011), build as in (Santos and Zadrozny, 2014). As illustrated in figure 1, a word w is a character sequence {c 1 , .., c |w| } represented by their embeddings {C c 1 , .., C c |w| }, where C c i denotes the row in C associated to the character c i . A convolution filter W conv ∈ R n f × R dc * nc is applied over a sliding window of d c characters, producing local features :

x n = W conv (C c n-dc+1 : .. : C cn ) T + b conv , where x n is a vector of size n f obtained for each position n in the word 2 . The i-th element of the embedding of w is the maximum over the i-th elements of the feature vectors :

[f ] i = tanh( max 1≤n≤|s| [x n ] i )
Using a maximum after a sliding convolution window ensures that the embedding combines local features from the whole word, and selects the more 2 Two padding character tokens are used to deal with border effects. The first is added at the beginning and the second at the end of the word, as many times as it is necessary to obtain the same number of windows than the length of the word. Their embeddings are added to C.

f 1 f 2 f 3 f 4 f 5 C c1 C c2 C c3 C c4 C c5 C sow C eow

From words to prediction

To predict the tag sequence associated to a sentence s, we first use a feedforward architecture, with a single hidden layer. To compute the probability of tagging the n-th word in the sentence with tag t i , we use a window of d w word embeddings3 centered around the word w n :

x n = f n-dw -1 2 : ... : f n+ dw -1 2 , followed by a hidden and output layers:

s n = W o tanh(W h x n + b h ) + b o . (1)
The parameters of the hidden an output layers are respectively W h , b h and W o , b o .

We also experiment with a a bidirectional recurrent layer, as described in [START_REF] Graves | Hybrid speech recognition with deep bidirectional LSTM[END_REF]. The forward and backward passes allow each prediction to be conditioned on the complete past and future contexts, instead of merely a neighboring window. As illustrated in figure 2, the forward hidden state, at position n, will be computed using the previous forward hidden state and the word embedding in position n: --→ W f h and --→ W hh are the transition matrices of the forward part of the layer, and b h is the bias. The backward hidden states are computed similarly, and the hidden states of each direction are concatenated to pass through an output layer:

-→ h n = tanh( --→ W f h f n + --→ W hh --→ h n-1 + b h ) n f |T | n h f1 f2 f3 f4 f5
s n = W o ( -→ h n : ← - h n ) + b o . (2)

Inference and Training

To infer the tag sequence from the sequence of output layers defined by equations 1 or 2, we explore two strategies. The first simply applies a softmax function to the output layer of the network described in the previous section. In this case, each tag prediction is made independently of the surrounding predictions.

For sequence labeling, a more appropriate solution relies on the approach of [START_REF] Collobert | Deep learning for efficient discriminative parsing[END_REF], also used in (Santos and Zadrozny, 2014). Let consider each possible tag sequence {t 1 , . . . , t |s| } as a possible path over a sequence of hidden states. We can add a transition matrix W trans and then compute the score of a sequence as follows: The Viterbi algorithm [START_REF] Viterbi | Error bounds for convolutional codes and an asymptotically optimum decoding algorithm[END_REF] offers an exact solution to infer the path that gives the maximum score. It is worth noticing that both these strategies can be applied to the feedforward and bidirectional recurrent networks. For both strategies, the whole network can estimate conditional log-likelihood of a tag sequence given a sentence s and the set of parameters θ. This criterion can then be optimized using a stochastic gradient ascent with the back-propagation algorithm.

Related Work

The choice to consider words from the character level has recently been more and more explored. While its raw application to language modeling did not achieve clear improvement over the word-based models [START_REF] Mikolov | Subword language modeling with neural networks[END_REF], this approach shown impressive results for text generation (Sutskever et al., 2011;[START_REF] Graves | Generating sequences with recurrent neural networks[END_REF]. However, for this line of work, the main issue is to learn long range dependencies at the character level since the word level is not considered by the model.

More recently, the character level was considered as more interpretable and convenient way to explore and understand recurrent networks [START_REF] Karpathy | Visualizing and understanding recurrent networks[END_REF]. In (Zhang and Le-Cun, 2015), the authors build a text understanding model that does not require any knowledge and uses hierarchical feature extraction. Here the character level allows the model to ignore the definition a priori of a vocabulary and let the model build its own representation of a sentence or a document, directly from the character level. To some extent, our work can be considered as an extension of their work, tailored for POS tagging.

(Santos and Zadrozny, 2014) applies a very similar model to the POS tagging of Portuguese and English. (Luong et al., 2013) also descends lower than the word level, using a dictionary of morphemes and recursive neural networks to model the structure of the words. Similarly, this allows a better representation of rare and complex words, evaluated on a word similarity task.

Experiments and Results

Experiments are carried out on the Part-of-Speech and Morphological tagging tasks using the German corpus TIGER Treebank [START_REF] Brants | The TIGER treebank[END_REF]. To the best of our knowledge, the best results on this task were published in [START_REF] Mueller | Efficient higher-order CRFs for morphological tagging[END_REF], who applied a high-order CRF that includes an intensive feature engineering to five different languages. German was highlighted as having 'the most ambiguous morphology'. scribed in details in [START_REF] Fraser | Knowledge sources for constituent parsing of German, a morphologically rich and less-configurational language[END_REF], contains a training set of 40472 sentences, a development and a test set of both 5000 sentences. We consider the two tagging tasks, with first a coarse tagset (54 tags), and then a morpho-syntactical rich tagset (619 items observed on the the training set).

Experimental settings

All the models are implemented 4 with the Theano library [START_REF] Bergstra | Theano: a CPU and 236 GPU math expression compiler[END_REF]. For optimization, we use Adagrad (Duchi et al., 2011), with a learning rate of 0.1. The other hyperparameters are: the window sizes, d c and d w , respectively set to 5 and 9, the dimension of character embeddings, word embeddings and of the hidden layer, n c , n f and n h , that are respectively of 100, 200 and 200 5 . The models were trained on 7 epochs. Parameter initialization and corpus ordering are random, and the results presented are the average and standard deviation of the POS Tagging error rate over 5 runs. 4 Implementation is available at https://github. com/MatthieuLabeau/NonlexNN 5 For both the learning rate and the embedding sizes, results does not differ in a significant way in a large range of hyperparameters, and their impact resides more in convergence speed and computation time

Results

The first experiment aims to evaluate the efficiency of a convolutional encoding with the basic feedforward architecture for prediction. We compare a completely non-lexicalized model which relies only on a character-level encoding with a lexicalized model where we use conventional word embeddings stored with a fixed vocabulary6 . Results are reported in Table 1 along with with the state-of-the-art results published in [START_REF] Mueller | Efficient higher-order CRFs for morphological tagging[END_REF]. Results show that a character-level encoding yields better results than the conventional word-level encoding. Moreover, the structured inference allows the model to achieve accuracy reasonably close to the performance of a high-order CRF that uses handcrafted features. Finally, the model that uses the concatenation of both the character and word-level embeddings outperforms the state-of-the-art system on the more difficult task, without any feature engineering.

To give an idea of how a simple model would perform on such task, the reader can refer to [START_REF] Schmid | Estimation of conditional probabilities with decision trees and an application to fine-grained pos tagging[END_REF] and [START_REF] Mueller | Efficient higher-order CRFs for morphological tagging[END_REF]. For instance in the former, by choosing the most probable tag position-by-position, the error rate on the development set of the TIGER dataset is 32.7 for the simple POS Tagging task.

We further analyze the results by looking at the error rates respectively on known and unknown words 7 . From table 2, we observe that the number of unknown words wrongly labeled is divided by 3 for POS and almost divided by 2 for POS+Morph tagging, showing the ability of character-level encoding to generalize to new words. Moreover, a strictly non-lexical encoding makes slightly more mistakes on words already seen, whereas the model that concatenates both embeddings will make less mistakes for both unknown and known words.

This shows that information from the context and from the morphology are complementary, which is conjectured in [START_REF] Mueller | Efficient higher-order CRFs for morphological tagging[END_REF]) by using a morphological analyzer in complement of higher-order CRF. In the second set of experiments, we evaluate the convolutional encoding with a bidirectional recurrent network for prediction. Results are presented in the second half of Table 1. Surprisingly, this architecture performs poorly with simple inference, but clearly improves when predicting a structured output using the Viterbi algorithm, both for training and testing. Moreover, a non-lexical model trained to infer a tag sequence with the Viterbi algorithm achieves results that are close to the state-of-the-art, thus validating our approach. We consider that this improvement comes from the synergy between using a global training objective with a global hidden representation, complexifying the model but allowing a more efficient solution. Finally, the model that uses the combination of both the character and word-level embeddings yields the best results. It is interesting to notice that the predictive architecture has no influence on the results of the simple task when the prediction is 7 Unknown words refer to words present in the development or test sets, but not in the training set.

structured, but improves them on the difficult task. This also shows that the contribution of word embeddings to our model corresponds to a difference of 1.5 to 2 points in performance.

Conclusion

In this paper, we explored new models that can infer meaningful word representations from the raw character stream, allowing the model to exploit the morphological properties of words without using any handcrafted features or external tools. These models can therefore efficiently process words that were unseen in the training data. The evaluation was carried out on a POS and morphological tagging task for German. We described different architectures that act in two stages: the first stage is a convolutional network that infers a word representation directly from the character stream, while the second stage performs the prediction. For the prediction stage, we investigated different solutions showing that a bidirectional recurrent network can outperform state-of-the-art results when using a structured inference algorithm.

Our results showed that character-level encoding can address the unknown words problem for morphologically complex languages. In the future, we plan to extend these models to other tasks such as syntactic parsing and machine translation. Moreover, we will also investigate other architectures to infer word embeddings from the character level. For instance, preliminary experiments show that bidirectional recurrent network can achieve very competitive and promising results.

  Bregman divergences B Subword-based models: supplementary results with NCE C Subword-based models: supplementary results on embedding sizes influence D Previous work on subword-based POS tagging xii CONTENTS List of Figures1.1 Example architecture of a feedforward neural network language model. Here, the context size n -1 = 3, and we only use one hidden layer. . 1.2 Example architecture of a recurrent neural network language model, unrolled through 3 sucessive time steps. . . . . . . . . . . . . . . . . . 1.3 Detailed working of a LSTM Unit; see Equations 1.7. . . . . . . . . . 3.1 Training cross-entropy curves on PTB for models trained with MLE, IS and NCE on a vocabulary of 10K words. . . . . . . . . . . . . . . 3.2 Top: Training cross-entropy curves on PTB for models trained with IS and various values of the number of samples k. Bottom: Training cross-entropy curves on PTB for models trained with IS and various values of distortion α for the noise distribution P n . . . . . . . . . . . 3.3 Top: Training cross-entropy curves on PTB for models trained with NCE and various values of the number of samples k. Bottom: Corresponding curves of classification probabilities of data examples into data (+) and noise samples into noise (o). . . . . . . . . . . . . . . . 3.4 Top: Training cross-entropy curves on PTB for models trained with NCE and various values of distortion α for the noise distribution P n . Bottom: Corresponding curves of classification probabilities of data examples into data (+) and noise samples into noise (o). . . . . . . . 3.5 Left: Training cross-entropy curves on PTB for models trained with NCE with a unigram and bigram distribution as P n . Right: Corresponding curves of classification probabilities of data examples into data (+) and noise samples into noise (o). . . . . . . . . . . . . . . . 3.6 Left: Training cross-entropy curves on PTB for models trained with BlackOut and various values of the number of samples k. Right: Corresponding curves of classification probabilities of data examples into data (+) and noise samples into noise (o). . . . . . . . . . . . . . 3.7 Left: Training cross-entropy curves on PTB for models trained with BlackOut and various values of distortion α for the noise distribution P n . Right: Corresponding curves of classification probabilities of data examples into data (+) and noise samples into noise (o). . . . . . . . 3.8 Left: Training cross-entropy curves on PTB for models trained with Negative Sampling and various values of the number of samples k. Right: Corresponding curves of classification probabilities of data examples into data (+) and noise samples into noise (o). . . . . . . . 42 3.9 Left: Training cross-entropy curves on PTB for models trained with Negative Sampling and various values of distortion α for the noise distribution P n . Right: Corresponding curves of classification probabilities of data examples into data (+) and noise samples into noise (o). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.10 Top: Training cross-entropy curves on PTB with Maximum-Likelihood estimation, IS, NCE on an un-normalized model and a model normalized before application of the NCE. Bottom: Training scores (see equation 3.2) of the same un-normalized and normalized models trained with NCE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.11 Repartition of the values of the partition function Z θ (H) for all examples (H, w) during specific epochs of training on PTB with NCE. The fully colored bars represent the repartition for the un-normalized model, while the faded bars represent the repartition for the normalized model. Both scales are logarithmic. . . . . . . . . . . . . . . . . 46 3.12 Repartition of the values of the partition function Z θ (H) for all training examples (H, w), during the last epoch of training with NCE on PTB. For both this figure and figure 3.13, the colour of a bin indicates the proportion of training examples (H, w) for which the word w is one of the 10 most frequent according to the noise distribution P n : the lighter the color is, the higher is that proportion. Both scales are logarithmic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.13 Repartition of the values of the ratio r θ (w|H) for all positive training examples (H, w) in orange, and associated noise sample ( ŵi ) k i=1 , in blue, at initialization. . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.14 Repartition of the values of the ratio r θ (w|H) for all positive training examples (H, w) in orange, and associated noise sample ( ŵi ) k i=1 , in blue, during several training epochs of a normalized model with NCE on PTB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.15 Repartition of the values of the ratio r θ (w|H) for all positive training examples (H, w) in orange, and associated noise sample ( ŵi ) k i=1 , in blue, during several training epochs of an un-normalized model with NCE on PTB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.16 Training cross-entropy curves on PTB for un-normalized models trained with NCE while fixing, then learning a parameter Z c that shifts the partition function, depending on the initial value of Z c . . . . . . . . . 50 LIST OF FIGURES xv 3.17 Repartition of the values of the partition function Z θ (H) for all training examples (H, w), during the last epoch of training with NCE on PTB, where a scaling parameter Z c is learned. The color of a bin indicates the proportion of training examples (H, w) for which the word w is one of the 10 most frequent according to the noise distribution P n : the lighter the color is, the higher is that proportion. Both scales are logarithmic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.18 Repartition of the values of the partition function Z θ (H) (top) and ratio r θ (w|H) (bottom) for all training examples (H, w) at initialization, for a model whose output bias is initialized to the values of log P n (w). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.19 Repartition of the values of the ratio r θ (w|H) for all positive training examples (H, w) in orange, and associated noise sample ( ŵi ) k i=1 , in blue, during several training epochs on PTB. The model is trained with NCE, with a output bias initialized to the values of log P n (w). . 3.20 Training cross-entropy curves on PTB for un-normalized models trained with NCE, variations of NCE and alternative additions presented in Section 3.3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Example architecture of a convolutional layer CharCNN for building character-based representations of words. Here, the convolution matrix is applied on a window of 3 characters. The • symbol indicates the specific character token used for padding. . . . . . . . . . . . . . 5.2 Example architecture of a bi-recurrent layer CharBiLSTM for building character-based representations of words. . . . . . . . . . . . . . . 5.3 Example architecture of our language model, when using word embeddings and a character CNN to build both input and output word representations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Distribution of word frequencies, ordered by rank, for the English and Czech versions of the parallel corpus News-commentary 2015. . . . . 5.5 Testing perplexity curves for models trained with Words+CharCNN input representations, with IS, for various vocabulary sizes. Vocabulary sizes are given, from top to bottom, by taking f W T h = 10, 5, 2, 1, 0 in Table 5.3a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  language models . . . . . . . . . . . . . . . . . . . Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Neural network language models . . . . . . . . . . . . . . 1.2.1 Feedforward language models . . . . . . . . . . . . . . . . Word embeddings . . . . . . . . . . . . . . . . . . . . . . Hidden layers . . . . . . . . . . . . . . . . . . . . . . . . . Output layer . . . . . . . . . . . . . . . . . . . . . . . . . Learning with gradient descent and backpropagation . . . 1.2.2 Recurrent neural network language models . . . . . . . . Basic recurrent layer . . . . . . . . . . . . . . . . . . . . . LSTM and other improvements . . . . . . . . . . . . . . . 1.3 Practical considerations . . . . . . . . . . . . . . . . . . . . 1.3.1 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Choosing hyperparameters . . . . . . . . . . . . . . . . . Optimization, Regularization and Initialization . . . . . . 1.3.3 The computational bottleneck . . . . . . . . . . . . . . . .

Figure 1 . 1 :

 11 Figure 1.1: Example architecture of a feedforward neural network language model. Here, the context size n -1 = 3, and we only use one hidden layer.

  Figure 1.3: Detailed working of a LSTM Unit; see Equations 1.7.

Figure 3

 3 Figure 3.1: Training cross-entropy curves on PTB for models trained with MLE, IS and NCE on a vocabulary of 10K words.

Figure 3 . 2 :

 32 Figure 3.2: Top: Training cross-entropy curves on PTB for models trained with IS and various values of the number of samples k. Bottom: Training cross-entropy curves on PTB for models trained with IS and various values of distortion α for the noise distribution P n .

Figure 3

 3 Figure 3.3: Top: Training cross-entropy curves on PTB for models trained with NCE and various values of the number of samples k. Bottom: Corresponding curves of classification probabilities of data examples into data (+) and noise samples into noise (o).

Figure 3

 3 Figure 3.4: Top: Training cross-entropy curves on PTB for models trained with NCE and various values of distortion α for the noise distribution P n . Bottom: Corresponding curves of classification probabilities of data examples into data (+) and noise samples into noise (o).

Figure 3 . 5 :

 35 Figure 3.5: Left: Training cross-entropy curves on PTB for models trained with NCE with a unigram and bigram distribution as P n . Right: Corresponding curves of classification probabilities of data examples into data (+) and noise samples into noise (o).

Figure 3

 3 Figure 3.6: Left: Training cross-entropy curves on PTB for models trained with BlackOut and various values of the number of samples k. Right: Corresponding curves of classification probabilities of data examples into data (+) and noise samples into noise (o).

Figure 3 . 7 :

 37 Figure 3.7: Left: Training cross-entropy curves on PTB for models trained with BlackOut and various values of distortion α for the noise distribution P n . Right: Corresponding curves of classification probabilities of data examples into data (+) and noise samples into noise (o).

Figure 3

 3 Figure 3.8: Left: Training cross-entropy curves on PTB for models trained with Negative Sampling and various values of the number of samples k. Right: Corresponding curves of classification probabilities of data examples into data (+) and noise samples into noise (o).

Figure 3

 3 Figure 3.9: Left: Training cross-entropy curves on PTB for models trained with Negative Sampling and various values of distortion α for the noise distribution P n . Right: Corresponding curves of classification probabilities of data examples into data (+) and noise samples into noise (o).

Figure 3

 3 Figure 3.10: Top: Training cross-entropy curves on PTB with Maximum-Likelihood estimation, IS, NCE on an un-normalized model and a model normalized before application of the NCE. Bottom: Training scores (see equation 3.2) of the same un-normalized and normalized models trained with NCE

Figure 3

 3 Figure 3.11: Repartition of the values of the partition function Z θ (H) for all examples (H, w) during specific epochs of training on PTB with NCE. The fully colored bars represent the repartition for the un-normalized model, while the faded bars represent the repartition for the normalized model. Both scales are logarithmic.

Figure 3 .

 3 Figure 3.12: Repartition of the values of the partition function Z θ (H) for all training examples (H, w), during the last epoch of training with NCE on PTB. For both this figure and figure 3.13, the colour of a bin indicates the proportion of training examples (H, w) for which the word w is one of the 10 most frequent according to the noise distribution P n : the lighter the color is, the higher is that proportion. Both scales are logarithmic.

Figure 3 .Figure 3

 33 Figure 3.13: Repartition of the values of the ratio r θ (w|H) for all positive training examples (H, w) in orange, and associated noise sample ( ŵi ) k i=1 , in blue, at initialization.

Figure 3

 3 Figure 3.15: Repartition of the values of the ratio r θ (w|H) for all positive training examples (H, w) in orange, and associated noise sample ( ŵi ) k i=1 , in blue, during several training epochs of an un-normalized model with NCE on PTB.

  ): shifting all values of the partition function by a fixed value Z c . In practice, it means we set p θ (w|H) = e s θ (w,H) Z c . Another similar workaround consists in initializing the output bias to -log |V| Vaswani et al. (2013); Melamud et al. (2017). It has the same effect as fixing Z c = |V| and initializing the bias to 0. In Chen et al. (2015) this value is arbitrarily set to log Z c = 9. Here, we propose to learn the best shifting value by adding Z c to the model parameters θ. In this case Z c can be seen as an extra bias term that learns a normalizing constant.

Figure 3 .Figure 3

 33 Figure 3.16 represents training cross-entropy curves depending on the initial

Figure 3 .

 3 Figure 3.17: Repartition of the values of the partition function Z θ (H) for all training examples (H, w), during the last epoch of training with NCE on PTB, where a scaling parameter Z c is learned. The color of a bin indicates the proportion of training examples (H, w) for which the word w is one of the 10 most frequent according to the noise distribution P n : the lighter the color is, the higher is that proportion. Both scales are logarithmic.

Figure 3 .

 3 Figure 3.18: Repartition of the values of the partition function Z θ (H) (top) and ratio r θ (w|H) (bottom) for all training examples (H, w) at initialization, for a model whose output bias is initialized to the values of log P n (w).

Figure 3

 3 Figure 3.19: Repartition of the values of the ratio r θ (w|H) for all positive training examples (H, w) in orange, and associated noise sample ( ŵi ) k i=1 , in blue, during several training epochs on PTB. The model is trained with NCE, with a output bias initialized to the values of log P n (w).

  Figure 3.20: Training cross-entropy curves on PTB for un-normalized models trained with NCE, variations of NCE and alternative additions presented in Section 3.3.

  log P H θ (w) = D KL (P D ||P θ ) (4.1) Our knowledge on the data distribution is simply represented by examples that we sample from the training data.

Figure 5 . 1 :

 51 Figure 5.1: Example architecture of a convolutional layer CharCNN for building character-based representations of words. Here, the convolution matrix is applied on a window of 3 characters. The • symbol indicates the specific character token used for padding.

Figure 5 . 2 :

 52 Figure 5.2: Example architecture of a bi-recurrent layer CharBiLSTM for building character-based representations of words.

Figure 5 . 3 :

 53 Figure 5.3: Example architecture of our language model, when using word embeddings and a character CNN to build both input and output word representations.

2 :

 2 Detail of the various input and output representations used in our experiments. Hw indicates the use of a Highway layer.

  Vocabulary sizes for different frequency thresholds

Figure 5 . 4 :

 54 Figure 5.4: Distribution of word frequencies, ordered by rank, for the English and Czech versions of the parallel corpus News-commentary 2015.

Figure 5 . 5 :

 55 Figure 5.5: Testing perplexity curves for models trained with Words+CharCNN input representations, with IS, for various vocabulary sizes. Vocabulary sizes are given, from top to bottom, by taking f W T h = 10, 5, 2, 1, 0 in Table5.3a

Figure 1 :

 1 Figure 1: Architecture of the layer for characterlevel encoding of words.

Figure 2 :

 2 Figure 2: Bidirectional recurrent architecture for tag prediction. The upper part is used in the case of structured inference.

  1 ,tn + [s n ] tn

  3.1 Best final perplexities on the test set of the Penn Treebank (PTB) corpus obtained with MLE, IS and NCE on a vocabulary of 10K words. Best testing perplexities obtained on PTB with a full vocabulary and on the 1 Billion Word Benchmark with a vocabulary of 64K words. 'X' indicates that the model did not reach a perplexity under the size of the vocabulary within the maximal number of training epochs 50. . 4.1 Choices of φ corresponding to S 0 and S 1 functions presented in Pihlaja et al. (2012). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Best final perplexities on the test set of the Penn Treebank (PTB) corpus and of the 1 Billion Word (1BW) Benchmark, obtained with Bregman divergences derived from φ Ratio β , for various values of β. 'X' indicates that the model did not reach a perplexity under the size of the vocabulary within the maximal number of training epochs. . . . . 72 5.1 Example of subword decompositions used for a Czech word. . . . . . 77 5.2 Detail of the various input and output representations used in our experiments. Hw indicates the use of a Highway layer. . . . . . . . . 82 5.3 Various vocabulary sizes for Czech on News-commentary 2015. . . . . 83 5.4 Structural choices and hyperparameters used on the News-commentary 2015 Czech corpus experiments presented in this chapter. . . . . . . . 84 5.5 Average test perplexities obtained when training 5 models using wordbased output representations with IS, for various input representations and vocabulary sizes. Results in bold are the best models for a given vocabulary size. The underlined results are the baselines, which use only words for the input and output representations. . . . . . . . 85

3.2 Structural choices and hyperparameters used on the Penn Treebank (PTB) corpus for experiments presented in this chapter (unless specified otherwise). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Best final perplexities on the test set of the Penn Treebank (PTB) corpus obtained with IS, NCE and variations, with varying number of samples k and distortion α of the noise distribution P n . 'X' indicates that the model did not reach a perplexity under the size of the vocabulary within the maximal number of training epochs, which is 50. 3.4 Best final perplexities on the test set of the Penn Treebank (PTB) corpus obtained with NCE and the two tricks presented in this section: learning conjointly a parameter Z c and initializing the output bias to the values of P n -with varying number of samples k and distortion α of the noise distribution P n . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Structural choices and hyperparameters used on the 1 Billion Words Benchmark for experiments presented in this chapter. . . . . . . . . . 3.6 4.2 Best final perplexities on the test set of the Penn Treebank (PTB) corpus obtained with Bregman divergences derived from φ β , for various values of β such that 0 < β < 1. 'X' indicates that the model did not reach a perplexity under the size of the vocabulary within the maximal number of training epochs. . . . . . . . . . . . . . . . . . . . 4.3 5.6 Average test perplexities obtained when training 5 models using word and CharCNN input and output representations with IS, for various vocabulary sizes. Results in bold are the best models for a given vocabulary size. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.7 Average test perplexities obtained when training 5 models with IS, for various input/output representations. Results in bold are the best models for a given output representation. The underlined result is the baseline, obtained using only words for the input and output representations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.8 Test perplexity averaged on 5 models trained with IS, for various input representations and output word look-up table sizes. Corresponding vocabulary sizes are given in Table 5.3a. Test perplexities are given for all words, frequent words (frequency > 10) and rare words (frequency < 10). In bold are the best models for a given input representation. . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5.9 Average test perplexities obtained when training 5 models using word and CharCNN input and output representations with NCE, for various vocabulary sizes. . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 5.10 Average test perplexities obtained when training 5 models with NCE, for various input representations and output word look-up table sizes, on PTB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 B.1 Average test perplexities obtained when training 5 models with NCE, for various input/output representations. . . . . . . . . . . . . . . . 119

Table 3

 3 However, the model is able to reach a perplexity that is not so far from MLE and IS, and could mirror their performance with more training epochs. To work with an experimental set-up that allows us to witness even more evidently the training difficulties of NCE, we choose to use the full training vocabulary instead, which contains a little more than 44K words. When not specified otherwise, we use k = 100 noise samples drawn from the unigram distribution. Our hyperparameter choices are summarized in Table3.2. To reduce the impact of the training criterion, models are learnt for a minimum of 30 epochs. Beyond that limit, we backtrack the epoch when no progress has been made on the validation set perplexity, stopping training after 10 consecutive backtrackings 2 .

	Training method Perplexity
	MLE	66,9
	IS	71,1
	NCE	87,6

.1: Best final perplexities on the test set of the Penn Treebank (PTB) corpus obtained with MLE, IS and NCE on a vocabulary of 10K words. comparison of training cross-entropies for models trained with MLE, NCE and IS, and a comparison of final testing perplexities, are shown in Figure 3.1 and Table

3

.1. With this setting, we can observe that there are differences in the training processes and that NCE does not perform as well given the same number of training epochs.

Table 3 .

 3

2: Structural choices and hyperparameters used on the Penn Treebank (PTB) corpus for experiments presented in this chapter (unless specified otherwise).

Table 3 .

 3 3: Best final perplexities on the test set of the Penn Treebank (PTB) corpus obtained with IS, NCE and variations, with varying number of samples k and distortion α of the noise distribution P n . 'X' indicates that the model did not reach a perplexity under the size of the vocabulary within the maximal number of training epochs, which is 50.

		IS	NCE BlackOut NS
	Baseline model 168.3 306.0	169.0	228.3
	k = 5	233.9	X	248.4	252.0
	k = 10	203.1	X	250.2	255.0
	k = 25	184.6	X	216.3	268.6
	k = 50	181.0	X	181.1	196.2
	k = 250	160.3 298.0	163.7	243.0
	k = 500	153.5 235.7	157.9	302.0
	α = 0.0	366.1	X	487.4	900.9
	α = 0.25	201.9 1068.0	233.9	344.8
	α = 0.50	180.6 641.2	178.9	208.6
	α = 0.75	171.5 277.0	172.3	195.8
	P n = Bigram		269.6

  Table 3.4: Best final perplexities on the test set of the Penn Treebank (PTB) corpus obtained with NCE and the two tricks presented in this section: learning conjointly a parameter Z c and initializing the output bias to the values of P n -with varying number of samples k and distortion α of the noise distribution P n .

	NCE +	Z c ∈ θ Bias init. at log(P n ) Both
	Baseline model 179.3	151.8	148.4
	k = 5	247.3	221.4	231.5
	k = 10	299.0	204.4	198.2
	k = 25	191.9	171.2	189.6
	k = 50	184.7	157.3	167.6
	k = 250	167.0	141.6	144.3
	k = 500	164.6	137.5	138.4
	α = 0.0	335.0	322.4	275.4
	α = 0.25	201.8	205.0	193.5
	α = 0.50	178.1	172.7	159.6
	α = 0.75	173.5	155.0	156.3

Table 3 .

 3

	Hyperparameter	Value	Hyperparameter	Value
	Number of noise samples k	100	Batch size (Sentences)	1000
	Default noise distribution P n Unigram	Dropout rate	0.9
	Hidden Layer	LSTM	Optimization method	Adam
	Maximum Sentence Length	30	Learning rate	0.01
	Number of hidden layers	1		0.0001
	Word embedding dimension	512	Grad clipping value	0.0
	Hidden layer dimension	512	Maximum number of training epochs	3

5: Structural choices and hyperparameters used on the 1 Billion Words

Benchmark for experiments presented in this chapter.

Table 4 .

 4 2: Best final perplexities on the test set of the Penn Treebank (PTB) corpus obtained with Bregman divergences derived from φ β , for various values of β such that 0 < β < 1. 'X' indicates that the model did not reach a perplexity under the size of the vocabulary within the maximal number of training epochs. same hyperparameters as previously indicated, and both initializing bias with P n and learning a scaling parameter. Results are presented in Table4.2. While our newly defined objectives do learn, their performances are not satisfactory, and for the most part far from those obtained with the NCE in a similar configuration.

	β	Perplexity
	0.01	X
	0.1	404.0
	0.25	236.0
	0.5	251.8
	0.75	302.7
	0.9	593.2
	0.99	X

  Table 4.3: Best final perplexities on the test set of the Penn Treebank (PTB) corpus and of the 1 Billion Word (1BW) Benchmark, obtained with Bregman divergences derived from φ Ratio β

		338.9	X
	0.5	191.8	103.4
	0.75 167.8	79.7
	0.9	157.9	72.9
	1.0	150.2	72.6
	1.1	149.7	71.4
	1.25 144.4	71.8
	1.5	149.5	78.1
	2.0	177.2	116.9

Table 5 .

 5 , or characters composed by a convolutional layer (Santos and Zadrozny, 2014; 1: Example of subword decompositions used for a Czech word.

	Representation	Decomposition
	Word	pocátku
	Characters	p+o+c+á+t+k+u
	Character 3-grams	poc+ocá+cát+átk+tku
	Lemma + Tags	pocátek+N+MascIn+Sg+Loc+Act

Table 5 .

 5 3: Various vocabulary sizes for Czech on News-commentary 2015.

Table 5 .

 5 4: Structural choices and hyperparameters used on the News-commentary 2015 Czech corpus experiments presented in this chapter.

	Hyperparameter	Value	Hyperparameter	Value
	Number of noise samples k	500	Batch size (Sentences)	128
	Default noise distribution P n	Unigram	Dropout rate	0.5
	Hidden Layer	LSTM	Optimization method	Adam
	Maximum Sentence Length	30	Learning rate	0.001
	Number of hidden layers	2		1e 8
	Input representation dimension	d rw	Grad clipping value	0.0
	Hidden Layer dimension	d r out w	Maximum number of training epochs	5

Table 5 .

 5 5: Average test perplexities obtained when training 5 models using wordbased output representations with IS, for various input representations and vocabulary sizes. Results in bold are the best models for a given vocabulary size. The underlined results are the baselines, which use only words for the input and output representations.

	f W T h Input Representation	10	5	2	1	0
	Words	139.6 ± 1.3	168.9 ± 2.7	231.5 ± 5.2	266.6 ± 4.1	388.1 ± 6.9
	CharCNN	156.7 ± 3.1	187.8 ± 2.8	256.3 ± 3.5	281.9 ± 5.5 427.2 ± 14.1
	Words + CharCNN	130.2 ± 1.5 161.3 ± 2.5 218.9 ± 2.3 251.9 ± 4.2 378.2 ± 6.2
	Lemmas + TagsConcat 142.2 ± 3.0	176.8 ± 1.7	233.6 ± 2.4	265.3 ± 4.8 371.4 ± 6.4

Table 5 .

 5

	f W T h Output Representations	10	5	2	1	0
	Words	130.2 ± 1.5 161.3 ± 2.5 218.9 ± 2.3 251.9 ± 4.2 378.2 ± 6.2
	Words + CharCNN	635.6 ± 71.6 555.1 ± 37.3 422.6 ± 50.6 370.0 ± 20.8 327.2 ± 8.1

6: Average test perplexities obtained when training 5 models using word and CharCNN input and output representations with IS, for various vocabulary sizes. Results in bold are the best models for a given vocabulary size.

Table 5 .

 5 3a resentation improves the performance of the model. We can assume that character based representations compensate for the insufficient number of updates performed on rare words embeddings during training. Indeed, combining word and characterbased embeddings allows the model to better counteract the Zipfian shape of the word occurences distribution. Table5.7: Average test perplexities obtained when training 5 models with IS, for various input/output representations. Results in bold are the best models for a given output representation. The underlined result is the baseline, obtained using only words for the input and output representations.

	Output Representation Input Representation	Words	Words + Char CNN BiLSTM	CNN	Char	BiLSTM
	Words		388.1 ± 6.9	333.2 ± 7.0	352.6 ± 3.0	917.5 ± 35.5	1943.6 ± 82.4
	Char	CNN	427.2 ± 14.1 363.2 ± 7.6	-	783.2 ± 32.8	-
		BiLSTM 630.0 ± 15.1	-	576.4 ± 19.0	-	1983.3 ± 37.0
	Words +	CNN	378.2 ± 6.2 327.2 ± 8.1	-	827.2 ± 37.1	-
	Char	BiLSTM 376.0 ± 4.2	-	349.6 ± 11.6	-	1889.9 ± 63.3
	Lemmas +	Concat.	371.4 ± 6.4 326.3 ± 6.4 338.0 ± 5.9	828.9 ± 25.7 1990.9 ± 194.2
	Tags	BiLSTM 368.1 ± 3.0 335.4 ± 9.2 332.8 ± 7.4 821.3 ± 29.2 1856.1 ± 57.6

Table 5 .

 5 8: Test perplexity averaged on 5 models trained with IS, for various input representations and output word look-up table sizes. Corresponding vocabulary sizes are given in Table

	Input Representation	f W T h	All words	Words + CharCNN Frequent words	Rare words
		0	333.2 ± 7.0	214.8 ± 4.7	5560.6 ± 174.0
		1	317.9 ± 5.0	205.3 ± 2.7	5077.3 ± 273.2
	Words	2	303.9 ± 4.9	195.7 ± 2.9	5071.6 ± 322.7
		5	291.3 ± 4.0	188.1 ± 2.2	5049.4 ± 397.5
		10	306.5 ± 10.2	191.2 ± 6.6	7999.2 ± 459.1
		0	363.2 ± 7.6	234.2 ± 3.5	5588.5 ± 552.6
		1	356.9 ± 6.1	230.9 ± 2.9	5432.1 ± 575.2
	CharCNN	2 350.9 ± 10.7	227.8 ± 7.2	5178.9 ± 451.0
		5	355.3 ± 9.3	228.1 ± 5.3	6039.7 ± 765.3
		10	364.8 ± 13.7	227.2 ± 9.1	8582.0 ± 279.7
		0	327.2 ± 8.1	208.6 ± 4.7	5790.2 ± 631.9
	Words + CharCNN	1 2 5	291.0 ± 11.6 283.1 ± 8.1 268.2 ± 3.5	189.0 ± 7.0 184.3 ± 4.7 172.9 ± 2.2	4577.1 ± 446.0 4354.4 ± 435.2 4641.6 ± 328.6
		10	278.4 ± 8.1	174.4 ± 4.4	6725.1 ± 587.0
		0	326.3 ± 6.4	214.2 ± 5.1	5782.4 ± 538.7
	Lemma + TagsConcat.	1 2 5	312.8 ± 13.8 318.6 ± 11.3 303.7 ± 6.7	202.4 ± 8.4 204.8 ± 6.6 193.6 ± 2.3	4747.7 ± 312.8 5429.0 ± 526.0 6035.1 ± 718.3
		10	308.3 ± 3.2	192.0 ± 1.4	7378.0 ± 616.3
		0	335.4 ± 9.2	208.0 ± 4.0	5733.2 ± 573.2
	Lemma + TagsBiLSTM	1 2 5 310.3 ± 14.1 319.0 ± 10.6 314.3 ± 11.9	206.0 ± 6.9 203.8 ± 8.0 197.7 ± 7.8	5099.1 ± 301.4 4782.3 ± 221.9 5864.7 ± 526.5
		10	307.8 ± 5.8	192.6 ± 3.4	7063.3 ± 542.8

Table 5 .

 5

	f W T h Output Representations	10	5	2	1	0
	Words	136.6 ± 6.5	174.4 ± 9.3	223.3 ± 9.6	248.6 ± 8.1 389.7 ± 19.1
	Words + CharCNN	124.2 ± 7.5 150.5 ± 7.4 199.8 ± 8.1 221.6 ± 5.5 320.6 ± 4.4

9: Average test perplexities obtained when training 5 models using word and CharCNN input and output representations with NCE, for various vocabulary sizes.

  Table B.2: Test perplexity averaged on 5 models trained with NCE, for various input representations and output word look-up table sizes. Corresponding vocabulary sizes are given in Table 5.3a. Test perplexities are given for all words, frequent words (frequency > 10) and rare words (frequency < 10). Non-lexical neural architecture for fine-grained POS Tagging Matthieu Labeau, Kevin Löser, Alexandre Allauzen Université Paris-Sud and LIMSI-CNRS, Rue John von Neumann 91403 Orsay cedex France firstname.lastname@limsi.fr

	Representation	T h f W		Words + CharCNN
			All words	Frequent words	Rare words
		0 333.7 ± 12.0	218.5 ± 7.5	4431.3 ± 364.9
		1 326.4 ± 10.6	213.3 ± 6.8	4352.6 ± 449.2
	Words	2	312.9 ± 9.7	204.5 ± 6.7	4323.1 ± 263.8
		5 317.3 ± 16.2	204.8 ± 11.1	5141.5 ± 170.9
		10 314.1 ± 17.3	196.1 ± 11.1	7485.5 ± 279.5
		0 386.0 ± 12.2	252.6 ± 7.5	4857.4 ± 368.5
		1 374.1 ± 23.6	245.0 ± 15.0	4813.8 ± 308.1
	CharCNN	2	358.8 ± 7.2	235.2 ± 4.1	4557.8 ± 359.6
		5 363.7 ± 18.2	235.0 ± 12.1	5727.9 ± 454.0
		10 370.9 ± 13.7	231.6 ± 8.3	8332.6 ± 577.8
		0	311.7 ± 3.2	205.4 ± 1.9	4021.0 ± 207.0
	Words + CharCNN	1 2 288.4 ± 12.1 302.1 ± 7.4 5 297.0 ± 12.0	197.8 ± 4.8 188.7 ± 7.3 191.5 ± 7.9	4182.5 ± 280.1 3971.5 ± 391.0 4991.0 ± 215.7
		10 287.5± 10.2	180.0 ± 6.8	6735.8 ± 312.9
		0	335.7 ± 9.9	218.5 ± 7.0	4702.6 ± 267.8
	Lemma + TagsConcat.	1 328.4 ± 10.2 2 322.8 ± 6.6 5 325.9 ± 13.6	214.2 ± 7.7 208.8 ± 4.6 207.7 ± 8.9	4503.3 ± 104.6 4779.3 ± 296.6 5783.4 ± 418.3
		10 341.1 ± 22.9	212.1 ± 15.0	8368.1 ± 445.4
		0 395.9 ± 36.7	257.9 ± 24.0	5412.0 ± 476.2
	Lemma + TagsBiLSTM	1 366.8 ± 25.9 2 344.7 ± 22.6 5 324.6 ± 13.8	239.1 ± 16.1 223.8 ± 14.2 207.2 ± 8.1	5074.2 ± 522.9 4868.2 ± 244.3 5493.8 ± 269.0
		10 341.6 ± 24.2	213.5 ± 16.4	7542.6 ± 762.4

Table 1 :

 1 The corpus, de-Simple 4.22 ± 0.05 5.89 ± 0.07 13.97 ± 0.14 17.46 ± 0.14 Struct.3.90 ± 0.05 5.33 ± 0.09 12.22 ± 0.13 15.34 ± 0.13 Non-lex. Simple 3.31 ± 0.07 4.22 ± 0.07 13.50 ± 0.16 16.23 ± 0.13 Struct. 2.92 ± 0.02 3.82 ± 0.04 11.65 ± 0.11 14.43 ± 0.19 Both Simple 2.59 ± 0.05 3.34 ± 0.09 11.89 ± 0.14 14.63 ± 0.22 Struct. 2.22 ± 0.03 * 2.86 ± 0.03 * 9.11 ± 0.14 11.29 ± 0.06 ± 0.04 14.83 ± 0.11 17.54 ± 0.13 Struct. 2.21 ± 0.04 * 2.86 ± 0.05 * 8.63 ± 0.21 * 10.97 ± 0.19 * Comparison of the feedforward and bidirectional recurrent architectures for predictions, with different settings. The non-lexical encoding is convolutional. CRF refers to state-of-the-art system of[START_REF] Mueller | Efficient higher-order CRFs for morphological tagging[END_REF]. Simple and Struct. respectively denote the position-by-position and structured prediction. * indicates our best configuration.

	234

Table 2 :

 2 Error counts for known/unknown words in the test set, with a structured feedforward prediction model for the tagging task.

			Lex. Non-lex. Both
	POS	Unknown 2970	1054 1010
		Known	1974	2981 1620
	POS+Morph Unknown 5827	3472 3384
		Known	8652	10205 7232

It is possible for the input and output word embeddings to share the same parameters, which implies d r = d h . The resulting model is called log-bilinear model[START_REF] Mnih | Three new graphical models for statistical language modelling[END_REF]

For example, see the results of[START_REF] Józefowicz | Exploring the limits of language modeling[END_REF] to note the influence of dimension choices on perplexity.

Which is not even taking in account the fact that the concept of likelihood only applies to probability density functions, which are normalized.

For the sake of clarity, backtrackings are discarded from the graphs, keeping only the epochs used to obtain the final model.

Which is called sampled softmax.

Since the objective J H θ is negative, we minimize -J H θ .

Since we use the unigram distribution, it indicates here the examples who are among the 10 most frequent words.

Besides the computation time constraints, the batch size is rapidly limited by the GPU memory, while a smaller batch size also increases the computation time.

That are not formal distances: Bregman divergences in general are not.

However, the definition is not universal and may vary depending on the author's purpose. The reader may use Appendix B and C of[START_REF] Frigyik | Functional bregman divergence and bayesian estimation of distributions[END_REF] for a list of properties and proofs.

The φ corresponding to the functions for IS of[START_REF] Pihlaja | A family of computationally efficient and simple estimators for unnormalized statistical models[END_REF] is not exactly the negative entropy, but Bregman divergences are affine invariant with respect to φ.

Which is equivalent to the Tsallis q-entropy, with the relation β = q -1 ([START_REF] Eguchi | Entropy and divergence associated with power function and the statistical application[END_REF]

Besides inflected forms, German is characterized by a possibly infinite and evolving set of compound nouns.

Similarly, we use special word tokens for padding.

Every word that appears in the training set.

Remerciements

Acknowledgments

We would like to thank the anonymous reviewers for their helpful comments and suggestions. This work has been partly funded by the European Unions Horizon 2020 research and innovation programme under grant agreement No. 645452 (QT21).

Other detailed results on representation and the word embeddings vocabulary size are omitted here, but can be found in the Appendix B. They mostly confirm the two main tendancies outlined at the end of the previous section: augmenting word embeddings with subword-based output representations yields sizable improvement, while replacing independent word embeddings by the unknown token for rare words improves perplexity even more. However, some notable changes are, first, that the standard deviation is globally quite higher with NCE, especially for models using BiLSTMs. Secondly, that while the mean perplexity is overall a little higher, the models using CharBiLSTM only output representations obtain perplexities far better than with importance sampling (but are still the worst output representation).

Comparative experiments on English

In order to verify the usefulness of our setup on a morphologically simpler language, we now apply it to the PTB. When working on English, we only use characterbased representations, since the morphology does not carry as much information in English as it does in Czech. We limit our experiments to the better-performing CharCNN layers. Each input and output representations are of the same dimension, 150, and we use 2 highway layers after the input as in the rest of this chapter, while every other hyperparameter is the same than those indicated in Table 3.2. We should note that if we want to compare the obtained results to those obtained in previous chapters, we should only do so for models that use both Words + CharCNN input and output layers. Indeed, other models use smaller input and/or output dimensions and are therefore at a disadvantage. For a more detailled experimental investigation of the effect of dimension sizes, please refer to Annex C. We can see that, while augmenting the word input representation with a Char-CNN layer is not that impactful, augmenting the word ouptut representation with the same layer yields a nice improvement -and restricting the word embedding table size to a smaller value (here, we arbitrarily chose 10K words) also significantly improves perplexity. If we wish to compare our results to the perplexity obtained with the same objective at the end of Chapter 3 (which was 148.4), we can see that models using both Words + CharCNN layers reach a similar perplexity. However, we obtain this results by using a little more than half the parameters, given the small amount of parameters needed by the CharCNN layer. Besides, restricting the word embedding table size to 10K words both reduces greatly the number of parameters and improves on the final perplexity, to reach a mean value of 130.8.

Appendices

Appendix A

Proofs on Bregman divergences

Proof that φ BinClassif is convex ⇒ φ Ratio is convex Let the following function be convex:

We would like to prove that the following function is convex:

Our departure point is that ∀r, s ∈ R + , and ∀t ∈ [0, 1],

Then, ∀r, s ∈ R + , and ∀t ∈ [0, 1],

we have that:

We will now show that minimizing the Bregman divergence between the functions P H D (C = 1|.) and P H θ (C = 1|.) is equivalent to minimizing a different Bregman divergence, between the ratios of the data and noise distributions r H D , and model and noise distributions r H θ (w), that are:

Hence, we will prove that:

By using Equations 4.6, 4.2 and 4.38, we obtain that:

By taking the derivative of the composition function presented in Equation 4.38, we obtain that:

From Equation A.7, and as seen in Equation 4.39, since

We obtain the following:

Lastly,

Which finally gives: In Table C.1, all models share the same input and output representation total size: 300. We explain the difference between the (underlined) baseline result of 137.3 and the perplexity of 148.4 obtained at the end of Chapter 3 by the presence of the highway layers, which here amounts to adding 2 hidden layers. While using the same total representation sizes shows that the perplexity improvements are limited, we still improve results, while consequently decreasing the number of necessary parameters.

Appendix D Previous work on subword-based POS tagging

Titre : Mod èles de langue neuronaux: Gestion des grands vocabulaires Mots cl és : R éseaux de Neurones, Mod èles de Langue, Grands Vocabulaires R ésum é : Le travail pr ésent é dans cette th èse explore les m éthodes pratiques utilis ées pour faciliter l'entraînement et am éliorer les performances des mod èles de langues munis de tr ès grands vocabulaires. La principale limite à l'utilisation des mod èles de langue neuronaux est leur co ût computationnel: il d épend de la taille du vocabulaire avec laquelle il grandit lin éairement. La fac ¸on la plus ais ée de r éduire le temps de calcul de ces mod èles reste de limiter la taille du vocabulaire, ce qui est loin d' être satisfaisant pour de nombreuses t âches. La plupart des m éthodes existantes pour l'entraînement de ces mod èles à grand vocabulaire évitent le calcul de la fonction de partition, qui est utilis ée pour forcer la distribution de sortie du mod èle à être normalis ée en une distribution de probabilit és. Ici, nous nous concentrons sur les m éthodes à base d' échantillonnage, dont le sampling par importance et l'estimation contrastive bruit ée. Ces m éthodes permettent de calculer facilement une approximation de cette fonction de partition. L'examen des m écanismes de l'estimation contrastive bruit ée nous permet de proposer des solutions qui vont consid érablement faciliter l'entraînement, ce que nous montrons exp érimentalement. Ensuite, nous utilisons la g én éralisation d'un ensemble d'objectifs bas és sur l' échantillonnage comme divergences de Bregman pour exp érimenter avec de nouvelles fonctions objectif. Enfin, nous exploitons les informations donn ées par les unit és sous-mots pour enrichir les repr ésentations en sortie du mod èle. Nous exp érimentons avec diff érentes architectures, sur le Tch èque, et montrons que les repr ésentations bas ées sur les caract ères permettent l'am élioration des r ésultats, d'autant plus lorsque l'on r éduit conjointement l'utilisation des repr ésentations de mots.

Title : Neural language models: Dealing with large vocabularies Keywords : Neural Networks, Language Modelling, Large Vocabularies Abstract : This work investigates practical methods to ease training and improve performances of neural language models with large vocabularies. The main limitation of neural language models is their expensive computational cost: it depends on the size of the vocabulary, with which it grows linearly. Despite several training tricks, the most straightforward way to limit computation time is to limit the vocabulary size, which is not a satisfactory solution for numerous tasks. Most of the existing methods used to train large-vocabulary language models revolve around avoiding the computation of the partition function, ensuring that output scores are normalized into a probability distribution. Here, we focus on sampling-based approaches, including importance sampling and noise contrastive estimation. These methods allow an approximate computation of the partition function. After examining the mechanism of self-normalization in noise-contrastive es-timation, we first propose to improve its efficiency with solutions that are adapted to the inner workings of the method and experimentally show that they considerably ease training. Our second contribution is to expand on a generalization of several sampling based objectives as Bregman divergences, in order to experiment with new objectives. We use Beta divergences to derive a set of objectives from which noise contrastive estimation is a particular case. Finally, we aim at improving performances on full vocabulary language models, by augmenting output words representation with subwords. We experiment on a Czech dataset and show that using character-based representations besides word embeddings for output representations gives better results. We also show that reducing the size of the output look-up table improves results even more.

Universit é Paris-Saclay

Espace Technologique / Immeuble Discovery Route de l'Orme aux Merisiers RD 128 / 91190 Saint-Aubin, France