Joint Space Neural Probabilistic Language Model for Statistical Machine Translation

A neural probabilistic language model (NPLM) provides an idea to achieve the better perplexity than n-gram language model and their smoothed language models. This paper investigates application area in bilingual NLP, specifically Statistical Machine Translation (SMT). We focus on the perspectives that NPLM has potential to open the possibility to complement potentially `huge' monolingual resources into the `resource-constraint' bilingual resources. We introduce an ngram-HMM language model as NPLM using the non-parametric Bayesian construction. In order to facilitate the application to various tasks, we propose the joint space model of ngram-HMM language model. We show an experiment of system combination in the area of SMT. One discovery was that our treatment of noise improved the results 0.20 BLEU points if NPLM is trained in relatively small corpus, in our case 500,000 sentence pairs, which is often the case due to the long training time of NPLM.


Introduction
A neural probabilistic language model (NPLM) [3,4] and the distributed representations [25] provide an idea to achieve the better perplexity than n-gram language model [47] and their smoothed language models [26,9,48]. Recently, the latter one, i.e. smoothed language model, has had a lot of developments in the line of nonparametric Bayesian methods such as hierarchical Pitman-Yor language model (HPYLM) [48] and Sequence Memoizer (SM) [51,20], including an application to SMT [36,37,38]. A NPLM considers the representation of data in order to make the probability distribution of word sequences more compact where we focus on the similar semantical and syntactical roles of words. For example, when we have two sentences "The cat is walking in the bedroom" and "A dog was running in a room", these sentences can be more compactly stored than the n-gram language model if we focus on the similarity between (the, a), (bedroom, room), (is, was), and (running, walking). Thus, a NPLM provides the semantical and syntactical roles of words as a language model. A NPLM of [3] implemented this using the multi-layer neural network and yielded 20% to 35% better perplexity than the language model with the modified Kneser-Ney methods [9].
There are several successful applications of NPLM [41,11,42,10,12,14,43]. First, one category of applications include POS tagging, NER tagging, and parsing [12,7]. This category uses the features provided by a NPLM in the limited window size. It is often the case that there is no such long range effects that the decision cannot be made beyond the limited windows which requires to look carefully the elements in a long distance. Second, the other category of applications include Semantic Role Labeling (SRL) task [12,14]. This category uses the features within a sentence. A typical element is the predicate in a SRL task which requires the information which sometimes in a long distance but within a sentence. Both of these approaches do not require to obtain the best tag sequence, but these tags are independent. Third, the final category includes MERT process [42] and possibly many others where most of them remain undeveloped. The objective of this learning in this category is not to search the best tag for a word but the best sequence for a sentence. Hence, we need to apply the sequential learning approach. Although most of the applications described in [11,10,12,14] are monolingual tasks, the application of this approach to a bilingual task introduces really astonishing aspects, which we can call "creative words" [50], automatically into the traditional resource constrained SMT components. For example, the training corpus of word aligner is often strictly restricted to the given parallel corpus. However, a NPLM allows this training with huge monolingual corpus. Although most of this line has not been even tested mostly due to the problem of computational complexity of training NPLM, [43] applied this to MERT process which reranks the n-best lists using NPLM. This paper aims at different task, a task of system combination [1,29,49,15,13,35]. This category of tasks employs the sequential method such as Maximum A Posteriori (MAP) inference (Viterbi decoding) [27,44,33] on Conditional Random Fields (CRFs) / Markov Random Fields (MRFs).
Although this paper discusses an ngram-HMM language model which we introduce as one model of NPLM where we borrow many of the mechanism from infinite HMM [19] and hierarchical Pitman-Yor LM [48], one main contribution would be to show one new application area of NPLM in SMT. Although several applications of NPLM have been presented, there have been no application to the task of system combination as far as we know.
The remainder of this paper is organized as follows. Section 2 describes ngram-HMM language model while Section 3 introduces a joint space model of ngram-HMM language model. In Section 4, our intrinsic experimental results are presented, while in Section 5 our extrinsic experimental results are presented. We conclude in Section 5.

Ngram-HMM Language Model
Generative model Figure 1 depicted an example of ngram-HMM language model, i.e. 4-gram-HMM language model in this case, in blue (in the center). We consider a Hidden Markov Model (HMM) [40,21,2] of size K which emits n-gram word sequence w i , . . . , w i−K+1 where h i , . . . , h i−K+1 denote corresponding hidden states. The arcs from w i−3 to w i , · · · , w i−1 to w i show the back-off relations appeared in language model smoothing, such as Kneser-Ney smoothing [26], Good-Turing smoothing [24], and hierarchical Pitman-Yor LM smoothing [48]. In the left side in Figure 1, we place one Dirichlet Process prior DP(α, H), with concentration parameter α and base measure H, for the transition probabilities going out from each hidden state. This construction is borrowed from the infinite HMM [2,19]. The observation likelihood for the hidden word h t are parameterized as in w t |h t ∼ F (φ ht ) since the hidden variables of HMM is limited in its representation power where φ ht denotes output parameters. This is since the observations can be regarded as being generated from a dynamic mixture model [19] as in (1), the Dirichlet priors on the rows have a shared parameter.
In the right side in Figure 1, we place Pitman-Yor prior PY, which has advantage in its power-law behavior as our target is NLP, as in (2): where α is a concentration parameter, θ is a strength parameter, and G i is a base measure. This construction is borrowed from hierarchical Pitman-Yor language model [48].
Inference We compute the expected value of the posterior distribution of the hidden variables with a beam search [19]. This blocked Gibbs sampler alternate samples the parameters (transition matrix, output parameters), the state sequence, hyper-parameters, and the parameters related to language model smoothing. As is mentioned in [19], this sampler has characteristic in that it adaptively truncates the state space and run dynamic programming as in (3): where u t is only valid if this is smaller than the transition probabilities of the hidden word sequence h 1 , . . . , h K . Note that we use an auxiliary variable u i which samples for each word in the sequence from the distribution u i ∼ Uniform(0, π (hi−1,hi) ). The implementation of the beam sampler consists of preprocessing the transition matrix π and sorting its elements in descending order.
Initialization First, we obtain the parameters for hierarchical Pitman-Yor process-based language model [48,23], which can be obtained using a block Gibbs sampling [32].
Second, in order to obtain a better initialization value h for the above inference, we perform the following EM algorithm instead of giving the distribution of h randomly. This EM algorithm incorporates the above mentioned truncation [19]. In the E-step, we compute the expected value of the posterior distribution of the hidden variables. For every position h i , we send a forward message α(h i−n+1:i−1 ) in a single path from the start to the end of the chain (which is the standard forward recursion in HMM; Hence we use α). Here we normalize the sum of α considering the truncated variables u i−n+1:i−1 .
Then, for every position h j , we send a message β(h i−n+2:i , h j ) in multiple paths from the start to the end of the chain as in (5), This step aims at obtaining the expected value of the posterior distribution (Similar construction to use expectation can be seen in factored HMM [22]). In the M-step, using this expected value of the posterior distribution obtained in the E-step to evaluate the expectation of the logarithm of the complete-data likelihood.

Joint Space Model
In this paper, we mechanically introduce a joint space model. Other than the ngram-HMM language model obtained in the previous section, we will often encounter the situation where we have another hidden variables h 1 which is irrelevant to h 0 which is depicted in Figure 2. Suppose that we have the ngram-HMM language model yielded the hidden variables suggesting semantic and syntactical role of words. Adding to this, we may have another hidden variables suggesting, say, a genre ID. This genre ID can be considered as the second context which is often not closely related to the first context. This also has an advantage in this mechanical construction that the resulted language model often has the perplexity smaller than the original ngram-HMM language model. Note that we do not intend to learn this model jointly using the universal criteria, but we just concatenate the labels by different tasks on the same sequence. By this formulation, we intend to facilitate the use of this language model. It is noted that those two contexts may not be derived in a single learning algorithm. For example, language model with the sentence context may be derived in the same way with that with the word context. In the above example, a hidden semantics over sentence is not a sequential object. Hence, this can be only considering all the sentence are independent. Then, we can obtain this using, say, LDA.

Extrinsic Evaluation: Task of System Combination
We applied ngram-HMM language model to the task of system combination. For given multiple Machine Translation (MT) outputs, this task essentially combines the best fragments among given MT outputs to recreate a new MT output. The standard procedure consists of three steps: Minimum Bayes Risk decoding, monolingual word alignment, and monotonic consensus decoding. Although these procedures themselves will need explanations in order to understand the following, we keep the main text in minimum, moving some explanations (but not sufficient) in appendices. Note that although this experiment was done using the ngram-HMM language model, any NPLM may be sufficient for this purpose. In this sense, we use the term NPLM instead of ngram-HMM language model.

Features in Joint Space
The first feature of NPLM is the semantically and syntactically similar words of roles, which can be derived from the original NPLM. We introduce the second feature in this paragraph, which is a genre ID.
The motivation to use this feature comes from the study of domain adaptation for SMT where it becomes popular to consider the effect of genre in testset. This paper uses Latent Dirichlet Allocation (LDA) [5,46,6,45,33] to obtain the genre ID via (unsupervised) document classification since our interest here is on the genre of sentences in testset. And then, we place these labels on a joint space.
LDA represents topics as multinomial distributions over the W unique word-types in the corpus and represents documents as a mixture of topics. Let C be the number of unique labels in the corpus. Each label c is represented by a W -dimensional multinomial distribution φ c over the vocabulary. For document d, we observe both the words in the document w (d) as well as the document labels c (d) . Given the distribution over topics θ d , the generation of words in the document is captured by the following generative model.The parameters α and β relate to the corpus level, the variables θ d belong to the document level, and finally the variables z dn and w dn correspond to the word level, which are sampled once for each word in each document.
Using topic modeling in the second step, we propose the overall algorithm to obtain genre IDs for testset as in (5). 1. Fix the number of clusters C, we explore values from small to big where the optimal value will be searched on tuning set. Modified Process in System Combination Given a joint space of NPLM, we need to specify in which process of the task of system combination among three processes use this NPLM. We only discuss here the standard system combination using confusion-network. This strategy takes the following three steps (Very brief explanation of these three is available in Appendix): • Minimum Bayes Risk decoding [28] (with Minimum Error Rate Training (MERT) process [34] • Monolingual word alignment • (Monotone) consensus decoding (with MERT process) Similar to the task of n-best reranking in MERT process [43], we consider the reranking of nbest lists in the third step of above, i.e. (monotone) consensus decoding (with MERT process). We do not discuss the other two processes in this paper.
On one hand, we intend to use the first feature of NPLM, i.e. the semantically and syntactically similar role of words, for paraphrases. The n-best reranking in MERT process [43] alternate the probability suggested by word sense disambiguation task using the feature of NPLM, while we intend to add a sentence which replaces the words using NPLM. On the other hand, we intend to use the second feature of NPLM, i.e. the genre ID, to split a single system combination system into multiple system combination systems based on the genre ID clusters. In this perspective, the role of these two feature can be seen as independent. We conducted four kinds of settings below.
(A) -First Feature: N-Best Reranking in Monotonic Consensus Decoding without Noise -NPLM plain In the first setting for the experiments, we used the first feature without considering noise. The original aim of NPLM is to capture the semantically and syntactically similar words in a way that a latent word depends on the context. We will be able to get variety of words if we condition on the fixed context, which would form paraphrases in theory.
We introduce our algorithm via a word sense disambiguation (WSD) task which selects the right disambiguated sense for the word in question. This task is necessary due to the fact that a text is natively ambiguous accommodating with several different meanings. The task of WSD [14] can be written as in (6): where k ranges over all possible features, f (feature k i ) is an indicator function whose value is 1 if the feature exists, and 0 otherwise, g(synset i , k) is a parameter for a given synset and feature, θ is a collection of all these parameters in g(synset i , k), and Z is a normalization constant. Note that we use the term "synset" as an analogy of the WordNet [30]: this is equivalent to "sense" or "meaning". Note also that NPLM will be included as one of the features in this equation. If features include sufficient statistics, a task of WSD will succeed. Otherwise, it will fail. We do reranking of the outcome of this WSD task.
On the one hand, the paraphrases obtained in this way have attractive aspects that can be called "a creative word" [50]. This is since the traditional resource that can be used when building a translation model by SMT are constrained on parallel corpus. However, NPLM can be trained on huge monolingual corpus. On the other hand, unfortunately in practice, the notorious training time of NPLM only allows us to use fairly small monolingual corpus although many papers made an effort to reduce it [31]. Due to this, we cannot ignore the fact that NPLM trained not on a huge corpus may be affected by noise. Conversely, we have no guarantee that such noise will be reduced if we train NPLM on a huge corpus. It is quite likely that NPLM has a lot of noise for small corpora. Hence, this paper also needs to provide the way to overcome difficulties of noisy data. In order to avoid this difficulty, we limit the paraphrase only when it includes itself in high probability.
(B)-First Feature: N-Best Reranking in Monotonic Consensus Decoding with Noise -NPLM dep In the second setting for our experiment, we used the first feature considering noise. Although we modified a suggested paraphrase without any intervention in the above algorithm, it is also possible to examine whether such suggestion should be adopted or not. If we add paraphrases and the resulted sentence has a higher score in terms of the modified dependency score [39] (See Figure 3), this means that the addition of paraphrases is a good choice. If the resulted score decreases, we do not need to add them. One difficulty in this approach is that we do not have a reference which allows us to score it in the usual manner. For this reason, we adopt the naive way to deploy the above and we deploy this with pseudo references. (This formulation is equivalent that we decode these inputs by MBR decoding.) First, if we add paraphrases and the resulted sentence does not have a very bad score, we add these paraphrases since these paraphrase are not very bad (naive way). Second, we do scoring between the sentence in question with all the other candidates (pseudo references) and calculate an average of them. Thus, our second algorithm is to select a paraphrase which may not achieve a very bad score in terms of the modified dependency score using NPLM.
(C) -Second Feature: Genre ID -DA (Domain Adaptation) In the third setting of our experiment, we used only the second feature. As is mentioned in the explanation about this feature, we intend to splits a single module of system combination into multiple modules of system combi-  Figure 3: By the modified dependency score [39], the score of these two sentences, "John resigned yesterday" and "Yesterday John resigned", are the same. Figure shows c-structure and f-structure of two sentences using Lexical Functional Grammar (LFG) [8].
nation according to the genre ID. Hence, we will use the module of system combination tuned for the specific genre ID, 1 .
(D) -First and Second Feature -COMBINED In the fourth setting we used both features. In this setting, (1) we used modules of system combination which are tuned for the specific genre ID, and (2) we prepared NPLM whose context can be switched based on the specific genre of the sentence in test set. The latter was straightforward since these two features are stored in joint space in our case.
Experimental Results ML4HMT-2012 provides four translation outputs (s1 to s4) which are MT outputs by two RBMT systems, APERTIUM and LUCY, PB-SMT (MOSES) and HPB-SMT (MOSES), respectively. The tuning data consists of 20,000 sentence pairs, while the test data consists of 3,003 sentence pairs.
Our experimental setting is as follows. We use our system combination module [16,17,35], which has its own language modeling tool, MERT process, and MBR decoding. We use the BLEU metric as loss function in MBR decoding. We use TERP 2 as alignment metrics in monolingual word alignment. We trained NPLM using 500,000 sentence pairs from English side of EN-ES corpus of EUROPARL 3 .
The results show that the first setting of NPLM-based paraphrased augmentation, that is NPLM plain, achieved 25.61 BLEU points, which lost 0.39 BLEU points absolute over the standard system combination. The second setting, NPLM dep, achieved slightly better results of 25.81 BLEU points, which lost 0.19 BLEU points absolute over the standard system combination. Note that the baseline achieved 26.00 BLEU points, the best single system in terms of BLEU was s4 which achieved 25.31 BLEU points, and the best single system in terms of METEOR was s2 which achieved 0.5853. The third setting achieved 26.33 BLEU points, which was the best among our four settings. The fourth setting achieved 25.95, which is again lost 0.05 BLEU points over the standard system combination.
Other than our four settings where these settings differ which features to use, we run several different settings of system combination in order to understand the performance of four settings. Standard system combination using BLEU loss function (line 5 in Table 2), standard system combination using TER loss function (line 6), system combination whose backbone is unanamously taken from the RBMT outputs (MT input s2 in this case; line 11), and system combination whose backbone is selected by the modified dependency score (which has three variations in the figure; modDep preci-sion, recall and Fscore; line 12, 13 and 14). One interesting characteristics is that the s2 backbone (line 11) achieved the best score among all of these variations. Then, the score of the modified dependency measure-selected backbone follows. From these runs, we cannot say that the runs related to NPLM, i.e. (A), (B) and (D), were not particularly successful. The possible reason for this was that our interface with NPLM was only limited to paraphrases, which was not very successfuly chosen by reranking.  Table 2: This table shows single best performance, the performance of the standard system combination (BLEU and TER loss functions), the performance of four settings in this paper ((A),. . .,(D)), the performance of s2 backboned system combination, and the performance of the selection of sentences by modified dependency score (precision, recall, and F-score each).

Conclusion and Perspectives
This paper proposes a non-parametric Bayesian way to interpret NPLM, which we call ngram-HMM language model. Then, we add a small extension to this by concatenating other context in the same model, which we call a joint space ngram-HMM language model. The main issues investigated in this paper was an application of NPLM in bilingual NLP, specifically Statistical Machine Translation (SMT). We focused on the perspectives that NPLM has potential to open the possibility to complement potentially 'huge' monolingual resources into the 'resource-constraint' bilingual resources. We compared our proposed algorithms and others. One discovery was that when we use a fairly small NPLM, noise reduction may be one way to improve the quality. In our case, the noise reduced version obtained 0.2 BLEU points better.
Further work would be to apply this NPLM in various other tasks in SMT: word alignment, hierarchical phrase-based decoding, and semantic incorporated MT systems in order to discover the merit of 'depth' of architecture in Machine Learning.