Sparse Regression for Machine Translation

Regression can be used to find mappings between the source and target feature sets derived from given parallel corpora. Transduction learning uses a subset of the training examples that are closely related to the test set without using the model induced by the full training set. In the context of statistical machine translation, translations are performed at the sentence level and this enables us to select a few training instances for each test instance to guide the translation process. This also gives us a computational advantage when considering the high dimensionality of the problem.

The goal in transductive regression based machine translation (RegMT) is both reducing the computational burden of the regression approach by reducing the dimensionality of the training set and the feature set and also improving the translation quality by using transduction. In an idealized feature mapping matrix where features are word sequences, we would like to observe few target features for each source feature close to permutation matrices with one nonzero item for each column. $L_{1}$ regularization helps us achieve solutions close to the permutation matrices by increasing sparsity.

We compare $L_{1}$ regularized regression with other regression techniques and show that it achieves better performance in estimating target features and in generating the translations during graph decoding. We present encouraging results on German and Spanish to English translation tasks. We also replace the phrase table of a phrase-based decoder, Moses [Koehn et al., 2007], with the feature mappings we find with the RegMT model.

Related Work: Regression techniques can be used to model the relationship between strings [Cortes et al., 2007]. Wang et al. [Wang et al., 2007] applies a string-to-string mapping approach to machine translation by using ordinary least squares regression and $n$-gram string kernels to a small dataset. Later they use $L_{2}$ regularized least squares regression [Wang and Shawe-Taylor, 2008]. Although the translation quality they achieve is not better than Moses [Koehn et al., 2007], which is accepted to be the state-of-the-art, they show the feasibility of the approach. Serrano et al. [Serrano et al., 2009] use kernel regression to find translation mappings from source to target feature vectors and experiment with translating hotel front desk requests. Locally weighted regression solves separate weighted least squares problems for each instance [Hastie et al., 2009], weighted by a kernel similarity function.

Outline: Section 2 gives an overview of regression based machine translation, which is used to find the mappings between the source and target features of the training set. We present $L_{1}$ regularized transductive regression for alignment learning and the instance selection method used. In section 3, we compare the performance of $L_{1}$ versus $L_{2}$ regularized regression results in effectively estimating the target features. In section 4, we present the graph decoding results on German-English and Spanish-English translation tasks. Section 5 compares the results obtained with Moses with different learning settings. The last sections present our contributions.

Let X and Y correspond to the sets of tokens that can be used in the source and target strings, then, $m$ training instances are represented as $(\textbf{x}_{1},\textbf{y}_{1}),\ldots,(\textbf{x}_{m},\textbf{y}_{m})\in X^{*}\times Y^{*},$ where $(\textbf{x}_{i},\textbf{y}_{i})$ corresponds to a pair of source and target language token sequences for $1\leq i\leq m$. Our goal is to find a mapping $f:X^{*}\rightarrow Y^{*}$ that can convert a source sentence to a target sentence sharing the same meaning in the target language (Figure 1).

We define feature mappers $\Phi_{X}:X^{*}\rightarrow F_{X}=\mathbb{R}^{N_{X}}$ and $\Phi_{Y}:Y^{*}\rightarrow F_{Y}=\mathbb{R}^{N_{Y}}$ that map each string sequence to a point in high dimensional real number space. Let $\textbf{M}_{X}\in\mathbb{R}^{N_{X}\times m}$ and $\textbf{M}_{Y}\in\mathbb{R}^{N_{Y}\times m}$ such that $\textbf{M}_{X}=[\Phi_{X}(\textbf{x}_{1}),\ldots,\Phi_{X}(\textbf{x}_{m})]$ and $\textbf{M}_{Y}=[\Phi_{Y}(\textbf{y}_{1}),\ldots,\Phi_{Y}(\textbf{y}_{m})]$. The ridge regression solution using $L_{2}$ regularization is found by minimizing the following cost:

Two main challenges of the regression based machine translation (RegMT) approach are learning the regression function, $h:F_{X}\rightarrow F_{Y}$, and solving the pre-image problem, which, given the features of the estimated target string sequence, $h(\Phi_{X}(\textbf{x}))=\Phi_{Y}(\hat{\textbf{y}})$, attempts to find $\textbf{y}\in Y^{*}$: $\textbf{y}=\operatornamewithlimits{arg\,min}_{\textbf{y}\in Y^{*}}||h(\Phi_{X}(\textbf{x}))-\Phi_{Y}(\textbf{y})||^{2}$.

We experiment with different regression techniques and compare their performance to $L_{2}$ and lasso. We show that lasso is able to identify features better than other techniques we compared while making less error.

We use the German-English (de-en) parallel corpus of size about $1.6$ million sentences from the WMT’10 [Callison-Burch et al., 2010] to select training instances. For development and test sentences, we select randomly among the sentences whose length is in the range $[10,20]$ and target language bigram coverage in the range $[0.6,1]$. We select $20$ random instances from each target coverage decimal fraction (i.e. 20 from $[0.6,0.7]$, 20 from $[0.7,0.8]$, etc.) to obtain sets of $100$ sentences. We create in-domain dev, dev2, and test sets following this procedure and making sure that test set source sentences do not have exact matches in the training set. We use $n$-spectrum weighted word kernel [Taylor and Cristianini, 2004] as feature mappers which considers all word sequences up to order $n$:

where $\textbf{x}[i\!\!:\!\!j]$ denotes a substring of x with the words in the range $[i,j]$, $I(.)$ is the indicator function, and $p$ is the number of words in the feature. Features used are $1$-grams, $2$-grams, or $1$&$2$-grams.

We demonstrate machine translation results using graph decoding on the German-English test set as well as in a constrained translation domain from Spanish to English (es-en) using the categorized EuTrans corpus [Serrano et al., 2009]. The corpus provides a more restricted translation environment for decoding and contains 9000 training, 1000 development, and 3000 test sentences.

We perform graph-based decoding by first generating a De Bruijn graph from the estimated $\hat{\textbf{y}}$ [Cortes et al., 2007] and then finding Eulerian paths with maximum path weight. We use four features when scoring paths: (1) estimation weight from regression, (2) language model score, (3) brevity penalty as found by $e^{\alpha(l_{R}-|s|/|path|)}$ for $l_{R}$ representing the length ratio from the parallel corpus and $|path|$ representing the length of the current path, (4) future cost as in Moses [Koehn et al., 2007] and weights are tuned using MERT [Och, 2003] on the de-en dev set.

For de-en, we built a Moses model using default settings with maximum sentence length set to $80$ using $5$-gram language model where about $1.6$ million sentences were used for training and $1000$ random development sentences including dev used for tuning. We obtained $0.3422$ BLEU score on test. Regression results for increasing training data can be seen in Figure 2 where $2$-grams are used for decoding. We see a large BLEU gain of lasso over $L_{2}$ in our transductive learning setting although the performance is lower than Moses.

For es-en, Moses achieves $.9340$ BLEU on the full test set. Regression results for increasing training data can be seen in Figure 3 where $1$&$2$-grams are used for decoding. We see that lasso performs better than $L_{2}$ in the beginning when we use smaller number of training instances but it performs worse as the training set size increase. The red line corresponds to the Moses baseline. These results are comparable to previous work [Serrano et al., 2009].

We demonstrate that sparse $L_{1}$ regularized regression performs better than $L_{2}$ regularized regression. Graph based decoding can provide an alternative to state of the art phrase-based decoding system Moses in translation domains with small vocabulary and training set size.

Moses uses some extra reordering features, lexical weights, and phrase translation probabilities in both translation directions. Therefore we also experiment with decoding using Moses.

We interpret the coefficient matrix W as the phrase table and perform experiments with Moses using the new phrase table we obtain. These experiments show whether we can effectively use W as the phrase table in a phrase-based decoder. In our transductive learning framework, a W matrix is created for each test sentence and this replaces the phrase table. We modify Moses such that it reloads the phrase table before translating each test sentence. Moses use a default translation table limit (--ttable-limit) of $20$ entries per source phrase, which limits the number of translation options considered for each source phrase.

We obtain direct and indirect translation probabilities for the target phrase entries for each source phrase. We obtain the scores for a given source test sentence S as follows ¹¹1$p(t_{f}|s_{f})$ is the direct phrase translation probability and corresponds to $p(e|f)$ in Moses. Similarly, $p(s_{f}|t_{f})$ is the inverse phrase translation probability and corresponds to $p(f|e)$ in Moses.:

where $\mathcal{F}(F_{Y})$ is the set of target features found in the training set and $\mathcal{F}(\Phi_{X}(S))$ return the source features of source test sentence $S$ where $\mathcal{F}(.)$ return the features used in a given domain. $s_{f}$ are chosen from the feature set of the source test sentence and $t_{f}$ from where $\textbf{W}[t_{f},s_{f}]>0$. This choice of summing over source features found in the source test sentence helps us discriminate among target feature alternatives better than summing over all source features found in the training set. We also find that by summing over the positive entries for features selected from $\mathcal{F}(F_{Y})$ rather than selecting from the top $N$ aligned target features, we increase the precision in the phrase translation scores by increasing the denominator for frequently observed phrases.

We retain the phrase penalty to obtain $3$ scores for each phrase table entry: $p(s_{f}|t_{f}),p(t_{f}|s_{f}),2.718$, where the last score is used for the phrase penalty. To compare the performance with Moses, we use the option -score-options ’--NoLex’ during training, which removes the scores coming from lexical weights in phrase table entries, leaving $3$ scores similar to the scores used in the RegMT phrase table. Instead of adding extra lexical weights, we remove it to measure the difference between the phrase tables better.

We use transductive regression techniques to learn mappings between source and target features of given parallel corpora and use these mappings to generate machine translation outputs. The results show the effectiveness of using $L_{1}$ regularization versus $L_{2}$ used in ridge regression. We introduce dice instance selection method for proper selection of training instances, which plays an important role to learn correct feature mappings We show that $L_{1}$ regularized regression performs better than $L_{2}$ regularized regression both in regression measurements and in the translation experiments using graph decoding. We present encouraging results when translating from German to English and Spanish to English.

We also demonstrate results when the phrase table of a phrase-based decoder is replaced with the mappings we find with the regression model. We observe that RegMT model achieves lower performance than Moses system built individually for each test sentence. RegMT model may need a larger training set size for achieving better performance when the mappings are used as the phrase table.

$F_{1}$ measure is giving us a metric that correlates with BLEU without performing the translation step.