1 Introduction
Statistical Machine Translation (SMT), like many natural language processing tasks, relies primarily on parallel corpora. The translation performance of SMT systems directly depends on the quantity and the quality of the available parallel data. However, such corpora are only available in large quantities for a handful of languages, including English, Arabic, Chinese and few other European languages. Much of the available parallel data is derived from parliamentary proceedings (e.g. Europarl, Canadian Hansard, etc.) and proceedings at the United Nations, though a limited amount of newswire text is also available. For most other languages, especially for less commonly used languages, parallel data is virtually non-existent.
Comparable corpora provide a possible solution to this data sparseness problem. Comparable documents are not strictly parallel, but are loose translations of each other, with overlapping information. A good example for comparable documents is the newswire text produced by multilingual news organizations such as AFP or Reuters. The degree of parallelism can vary greatly, ranging from noisy parallel documents that contain many parallel sentences, to quasi parallel documents that may cover different topics (Fung and Cheung Reference Fung and Cheung2004). The web is by far the largest source of comparable data. Wikipedia is becoming a more attractive source of comparable documents because of its structured nature.
Comparable corpora may contain parallel data in different levels of granularity. This includes: parallel documents, parallel sentences or parallel sub-sentential fragments. To simplify the process of extracting these different types of translational correspondences and to reduce the computational overhead, it can be divided into a cascade of tasks as shown in Figure 1. First, a document level alignment is identified between the two collections of comparable corpora. This results in a set of comparable document pairs, some of which may already be parallel. In the next step, a sentence level alignment is detected within the identified document pairs. Even if two comparable documents have few or no parallel sentence pairs, there could still be partially parallel sentences, which contain parallel sub-sentential fragments, including word translation pairs, named entities and long phrase pairs. These fragments are detected in the third step. The ability to identify these pairs would create a valuable resource for SMT, especially for low-resource languages.
Parallel data extraction framework.
In this paper, we present a novel phrase alignment approach to detect parallel phrase pairs embedded in comparable sentence pairs. We assume that a collection of comparable sentence pairs is already available at this stage (i.e. the first two steps in the framework in Figure 1), extracted for example using methods similar to Munteanu and Marcu (Reference Munteanu and Marcu2005) and Tillmann and Hewavitharana (Reference Tillmann and Hewavitharana2013). Our intention is to use the extracted phrases directly in the translation process, along with other phrase pairs extracted from parallel corpora. We compare the proposed approach with two other alignment methods: (1) the standard phrase extraction approach for parallel data, which relies on the Viterbi path of the word alignment, (2) a binary classifier to detect parallel phrase pairs when presented with a large collection of phrase pair candidates. We evaluate the accuracy of these approaches in detecting alignments for phrase pairs that have a known translation in a comparable sentence pair. Finally, we demonstrate the effectiveness of the extracted phrase pairs by adding them to Arabic–English and Urdu–English translation systems.
The main contributions of this paper are two-fold: (1) novel phrase alignment algorithms to extract parallel phrase pairs from comparable sentences, (2) evaluating the utility of the extracted phrases by using them directly in the MT decoder. The rest of the paper is organized as follows: In Section 2, we discuss previous work on extracting parallel data from comparable corpora. Section 3 introduces the phrase alignment problem in comparable sentences and discusses some of the challenges involved. It presents the proposed novel phrase alignment approach along with several algorithms to achieve it. It also explains other alternative alignment approaches we explore. Section 4 presents the experimental setup, results of evaluating the alignment accuracy and results of translation experiments. We conclude, in Section 5, with an analysis of the results and an outline of the direction for future work.
2 Related work
Many of the early attempts to exploit comparable corpora focused on learning bilingual word translations (Rapp Reference Rapp1995; Fung and Yee Reference Fung and Yee1998; Rapp Reference Rapp1999). The underlying assumption in these efforts is that a word and its translation appear in similar context in the respective languages, and therefore co-occurrence statistics can be used to detect them. Several context similarity measures such as term frequency (tf) and inverse document frequency (idf) have been studied by Fung and Yee (Reference Fung and Yee1998).
Cross-lingual information retrieval has been widely used to detect document level alignments in comparable corpora (Zhao and Vogel Reference Zhao and Vogel2002b; Utiyama and Isahara Reference Utiyama and Isahara2003; Munteanu and Marcu Reference Munteanu and Marcu2005). Here, a source language document is translated into the target language using a dictionary, and the resulting translation is used as a query to match against a collection of target documents. Resnik and Smith (Reference Resnik and Smith2003) find parallel article pairs from the web by exploiting the similarities in the URL structure and the structure of meta information in the articles among other clues.
Detecting sentence alignment within comparable documents has been tried in different ways. Zhao and Vogel (Reference Zhao and Vogel2002a) and Utiyama and Isahara (Reference Utiyama and Isahara2003) extend parallel sentence alignment algorithms to identify parallel sentence pairs within comparable news corpora. Munteanu and Marcu (Reference Munteanu and Marcu2005) and Fung and Cheung (Reference Fung and Cheung2004) work on non-parallel documents, and do not assume that every sentence on source document has a corresponding translation on the target document. Each source sentence is matched against candidate target sentences and the sentence pairs above a certain similarity measure is picked as parallel. Fung and Cheung (Reference Fung and Cheung2004) use cosine similarity measure for this task, while Munteanu and Marcu (Reference Munteanu and Marcu2005) use a maximum entropy classifier. The former uses an iterative refinement where previously identified sentence pairs are added to the system in later iterations. Munteanu and Marcu (Reference Munteanu and Marcu2005) demonstrates that this method can be successfully used to improve the performance of a machine translation system. Tillmann and Xu (Reference Tillmann and Xu2009) introduce a system that performs both the document selection and sentence alignment tasks in a single run without any document level pre-filtering. Such a system is useful when document level boundaries are not available in the comparable corpus.
The first attempt to detect sub-sentential fragments from comparable sentences was proposed by Munteanu and Marcu (Reference Munteanu and Marcu2006). After identifying sentence pairs that have at least partial overlap, the parallel fragments are detected using an approach inspired by signal processing. Quirk, Udupa and Menezes (Reference Quirk, Udupa and Menezes2007) later extended this work by introducing generative models that explicitly aligns comparable sentence pairs, including non-parallel sections. They showed improvements in translation performance when the method was applied on cross-domain test data. Kumano, Tanaka and Tokunaga (Reference Kumano, Tanaka and Tokunaga2007) have proposed a phrasal alignment approach for comparable corpora using the joint probability SMT model. While this approach is appealing for low-resource scenarios as it does not require any seed parallel corpus, the high computational cost is a deterrent in its applicability to large corpora. Tillmann and Hewavitharana (Reference Tillmann and Hewavitharana2011, Reference Tillmann and Hewavitharana2013) present a single unified search algorithm that can be used flexibly on all the different extraction tasks handled by the various algorithms cited above. Translation pair extraction is handled as a chunk-alignment problem with no document-level pre-filtering, and data processed directly at the sentence level. The results indicate significant gains by using the extracted parallel data, especially when using the extracted fragments. Sub-sentential fragment extraction has been explored recently for low-resource languages (Gupta, Pal and Bandyopadhyay Reference Gupta, Pal and Bandyopadhyay2013).
In all the approaches cited above, the extracted fragment data was used as additional training data to train alignment models. In contrast, this work focuses on extracting phrase pairs that can be directly used in the translation process, complementing a phrase table generated with existing parallel data. In our previous work (Hewavitharana and Vogel Reference Hewavitharana and Vogel2011, Reference Hewavitharana, Vogel, Sharoff, Reinhard, Zweigenbaum and Fung2013), we presented initial results on extracting phrase pairs from comparable sentences. This paper expands on previous work by presenting several phrase alignment algorithms that achieve this task. We also present results from translation experiments that use the extracted phrase pairs under several settings to improve translation performance.
3 Parallel phrase extraction
Figure 2 shows three sample sentences that were extracted from Gigaword Arabic and Gigaword English collections. For each comparable sentence pair, the Arabic sentence is shown first, followed by its correct English translation (in Italics). The extracted comparable English sentence is shown next. The parallel sections in each sentence are marked in boldface. In the first two sentences pairs, the English sentence contains the full translation of the Arabic sentence, but there are additional phrases on the English side that are not present on the Arabic sentence. These phrases appear at the beginning of sentence 1 and at the end of sentence 2. In sentence 3, there are parallel phrases as well as phrases that appear only on one side. The phrase ‘to Iraq’ appears only on the Arabic sentence while the phrase ‘the former Egyptian foreign minister’ appears only on the English side.
Sample comparable sentences that contain parallel phrases.
Standard word alignment and phrase alignment algorithms are formulated to work on parallel sentence pairs. Therefore, these standard algorithms are ill suited to operate on partially parallel sentence pairs. Presence of non-parallel phrases may result in undesirable word alignments. Figure 3 illustrates this phenomenon. It compares a typical word alignment pattern in a parallel sentence pair (a) to one in a non-parallel sentence pair (b). The darkness of a square indicates the strength of the word alignment probability between the corresponding word pair (i.e. Viterbi path). In Figure 3(a), we observe high probability word-to-word alignments (dark squares) over the entire length of the sentences. In Figure 3(b), we see one dark area above ‘weapons of mass destruction’, corresponding to the parallel phrase pair, and some scattered dark spots, where high frequency English words pair with high frequency Arabic words. These spurious alignments pose problems to the phrase alignment, and indicate that word alignment probabilities alone might not be sufficient to produce reliable phrase alignments in comparable sentences pairs.
Word-to-word alignment pattern for (a) a parallel sentence pair and (b) a non-parallel sentence pair.
Our aim in this paper is to address the issue of aligning comparable sentence pairs that contain parallel as well as non-parallel sections. As illustrated in Figure 3, the standard phrase extraction algorithms designed for parallel sentences fail when faced with non-parallel sentences. In this regard, in the following sections of the paper, we propose a novel phrase alignment approach to detect parallel phrases in comparable sentence pairs and compare it against other alternative approaches.
3.1 Non-Viterbi (PESA) alignment
A phrase alignment algorithm called ‘PESA’ that does not rely on the Viterbi path is described in Vogel (Reference Vogel2005). PESA identifies the boundaries of the target phrase by aligning words inside the source phrase with words inside the target phrase, and similarly for the words outside the boundaries of the phrase pair. It does not attempt to generate phrase alignments for the full sentence. Rather, it identifies the best target phrase that matches a given source phrase. PESA requires a statistical word-to-word lexicon. A seed parallel corpus is required to automatically build this lexicon.
The approach followed by PESA is particularly well suited in extracting phrase pairs from comparable sentences due to several reasons:
• It is designed to not generate a complete word alignment for the entire sentence, but to find only the target side of a source phrase embedded in the sentence. This provides the potential to devise alignment techniques, which only focuses on the parallel sections of a comparable sentence pair, ignoring non-parallel sections.
• The alignment algorithm can be bootstrapped using a lexical translation table or a bilingual dictionary. This is particularly appealing in low-resource scenarios, where available initial parallel resources may be limited.
• The ability to use as an on-demand phrase extraction method at run-time, which does not require prior extraction of phrase pairs. This method can readily be used as a way of finding auxiliary phrase pairs as needed by the translation system, when the baseline phrase table does not cover it.
We briefly explain the PESA alignment approach below. Instead of searching for all possible phrase alignments in a parallel sentence pair, this approach finds the alignment for a single source phrase S = s 1. . .sl. Assume that we have a parallel sentence pair (sJ 1, t 1I) which contains the source phrase S in the source sentence sJ 1. We want to find the target phrase T = t 1. . .tk in the target sentence tI 1 which is the translation of the source phrase.
A constrained IBM Model-1 alignment is now applied as follows:
• Source words inside the phrase boundary are aligned only with the target words inside the phrase boundary. Source words outside the phrase boundary are only aligned with target words outside the phrase boundary.
• Position alignment probability for the sentence, which is 1/I in IBM Model-1, is modified to be 1/k inside the source phrase and to 1/(I − k) outside the phrase.
Figure 4 shows the different regions. Given the source sentence and the source phrase from position j 1 to j 2, we want to find the boundaries of the target phrase, i 1 and i 2. The dark area in the middle is the phrase we want to align. The size of the blobs in each box indicates the lexical strength of the word pair. The constrained alignment probability is calculated as follows:
$$\begin{eqnarray}
p(s|t) = \left(\prod _{j=1}^{j_1-1} \sum _{i \notin (i_1 \ldots i_2)} \frac{1}{I-k} p(s_j|t_i)\right) \nonumber \\
&&\times \,\left(\prod _{j=j_1}^{j_2} \sum _{i=i_1}^{i_2} \frac{1}{k} p(s_j|t_i)\right) \\
&&\times \, \left(\prod _{j=j_2+1}^{J} \sum _{i\notin (i_1 \ldots i_2)} \frac{1}{I-k} p(s_j|t_i)\right) \nonumber
\end{eqnarray}$$
p(t|s) is similarly calculated by switching source and target sides in equation (1):
$$\begin{eqnarray}
p(t|s) = \left(\prod _{i=1}^{i_1-1} \sum _{i \notin (j_1 \ldots j_2)} \frac{1}{J-l} p(t_i|s_j)\right) \nonumber \\
&&\times \left(\prod _{i=i_1}^{i_2} \sum _{j=j_1}^{j_2} \frac{1}{l} p(t_i|s_j)\right) \\
&&\times \left(\prod _{i=i_2+1}^{I} \sum _{j\notin (j_1 \ldots j_2)} \frac{1}{J-l} p(t_i|s_j)\right) \nonumber
\end{eqnarray}$$
PESA phrase alignment.
To find the optimal target phrase boundaries, we interpolate the two probabilities in equations (1) and (2) and select the boundary (i 1, i 2) that gives the highest probability, as in equation (3).
$$\begin{equation}
(i_1,i_2) = \underset{i_1,i_2}{\operatorname{argmax}} \;\; \lbrace (1-\lambda ) \; log(p(s|t)) + \; \lambda \; log(p(t|s))\rbrace
\end{equation}$$
The value of λ is estimated using held-out data.
PESA can be used to identify all possible phrase pairs in a given parallel sentence pair by iterating over all possible n-gram in the source sentence. An important difference is that each phrase is found independently of any other phrase pair, whereas in the standard phrase extraction they are tied through the word alignment of the sentence pair.
3.2 Extending PESA alignment for comparable sentences
We want to extract parallel phrases from comparable sentence pairs using the non-Viterbi PESA alignment. The sentence pair (fJ 1, e 1I) now contains parallel sections as well as non-parallel sections. Figure 5 illustrates an example of such a sentence. The gray squares indicate parallel phrases that are common to both sentences. Black lines indicate non-parallel phrases that are present only on one side.
Phrase alignment for comparable sentences.
We extend PESA phrase alignment algorithm to comparable sentences, by explicitly modeling the non-parallel sections of the sentence.
Following Quirk et al. (Reference Quirk, Udupa and Menezes2007), we hypothesize that a monolingual model, such as an n-gram language model, is better suited to model the non-parallel sections of the comparable sentence pair. Conversely, a bilingual translation model will better model the parallel sections than a language model. i.e. if the phrase pair 
$(\tilde{f},\tilde{e})$ is parallel, then 
$P(\tilde{f},\tilde{e}) > P(\tilde{f}) \cdot P(\tilde{e})$.
We use two monolingual models, LS for the source language and LT for the target language, and two translation models, XST for source-to-target direction and XTS for target-to-source direction.
Using Bayes’ rule, we can break down the join probability Pr $(\tilde{f},\tilde{e})$ into two decompositions of translation model and language model.
$$Pr(\tilde{f},\tilde{e}) = Pr(\tilde{e}) \cdot Pr(\tilde{f}|\tilde{e}) = Pr(\tilde{f}) \cdot Pr(\tilde{e}|\tilde{f})$$
However, our models trained on limited amounts of data are only approximations. Therefore, the equation will not strictly be true and the expressions 
$ Pr(\tilde{e}) \cdot Pr(\tilde{f}|\tilde{e})$ and 
$ Pr(\tilde{f}) \cdot Pr(\tilde{e}|\tilde{f})$ may differ. Hence, we take the average of the two estimates.
Thus, the probability of aligning the phrase pair (f j 2j 1, e i 2i 1) is as follows:
$$\begin{equation}
Pr(f_{j_1}^{j_2},e_{i_1}^{i_2}) = \frac{1}{2} \left[ L_S(f_{j_1}^{j_2}) \cdot X_{TS}(e_{i_1}^{i_2}|f_{j_1}^{j_2}) \right] + \frac{1}{2} \left[ L_T(e_{i_1}^{i_2}) \cdot X_{ST}(f_{j_1}^{j_2}|e_{i_1}^{i_2}) \right]
\end{equation}$$
where
$$\begin{equation}
L_S(f_{j_1}^{j_2}) = \prod _{k=j_1}^{j_2} L_S(f_k|f_1^{k-1})
\end{equation}$$
and
$$\begin{equation}
X_{TS}(e_{i_1}^{i_2}|f_{j_1}^{j_2}) = \prod _{j=j_1}^{j_2} \sum _{i=i_1}^{i_2} \frac{1}{(i_2-i_1)} X_{TS}(f_j|e_i)
\end{equation}$$
LT(e i 2i 1) and XST(f j 2j 1|e i 2i 1) are defined similarly.
To find the best parallel phrase pair in a comparable sentence pair, we assume that the rest of the sentence outside the phrase boundaries is non-parallel. This assumption is not always true, as there can be multiple parallel phrase pairs in the sentence pair, as illustrated in Figure 5. At this point, however, we only focus on finding the best parallel phrase pair in the given comparable sentence pair. We expand the search for remaining parallel sections later.
We compute the joint probability of the sentence pairs P(f, e) as follows:
$$\begin{eqnarray}
P(f,e) = L_S(f_{1}^{j_1-1}) \cdot L_T(e_{1}^{i_1-1}) \nonumber \\
&&\times \,Pr(f_{j_1}^{j_2},e_{i_1}^{i_2}) \nonumber \\
&&\times \,L_s(f_{j_2+1}^{J}) \cdot L_T(e_{i_2+1}^{I})
\end{eqnarray}$$
and find the boundaries (j 1, j 2, i 1, i 2) of the best pair by optimizing P(f, e):
$$\begin{equation}
(i,j,k,l) = \underset{j_1,j_2,i_1,i_2}{\operatorname{argmax}} \;\; P(f,e)
\end{equation}$$
3.2.1 Phrase extraction
To extract parallel phrases from the comparable sentence pairs, we adopt the following procedure:
• Find the best parallel phrase pair: First assume that there is only one parallel phrase embedded in the comparable sentence pair, and find the best parallel phrase. This process divides the sentence pair into several regions as illustrated in Figure 4.
• Find the remaining parallel phrase pairs: Perform a greedy search in the non-blocked regions to identify remaining parallel phrases.
The following sections explain the proposed algorithm. It is important to point out that the phrase extraction algorithm does not restrict the word alignment within a phrase pair to be monotone. There can be non-monotone word alignment, as well as unaligned words within a phrase pair.
3.2.2 Find the best parallel phrase pair
The straightforward way to find the best phrase pair is by computing the alignment for every value of the boundary pairs (j 1, j 2) and (i 1, i 2) within the boundaries of the sentences and selecting the boundaries with the highest probability. This method is computationally expensive and has runtime complexity O(J 2I 2). However, most of the boundary pairs in this calculation will not produce any meaningful phase pairs. For example, the boundary pair (1,1) and (1,15) is unlikely to be a reasonable phrase alignment as it aligns a single source word with fifteen target words. Therefore, the search space can be restricted to those boundary values that have the potential to produce meaningful phrases.
We introduce minimum and maximum phrase lengths to both the source phrase (lmin, lmax) and the target phrase (kmin, kmax). The best parallel phrase is then identified using the algorithm in Algorithm 1.
Identify the best phrase translation pair in a comparable sentence pair
This search process can also be thought of as follows: From among a set of allowed phrase patterns of different sizes (e.g. 3 × 8, 4 × 6, etc.), we want to find the best placement for that pattern in the sentence that would produce the best parallel phrase pair.
The length restriction reduces the run-time complexity of the algorithm to O(c.JI), where c is the number of different source and target phrase length combinations allowed. By restricting (lmin, lmax) and (kmin, kmax), we can keep c in a manageable level. For example, if we are interested in phrases of three to seven words long in both source and target sides, then c is 25. Similar phrase length restrictions are typically enforced when extracting phrase translation pairs from parallel sentences using various heuristics to combine word-alignments (e.g. in Moses (Koehn et al. Reference Koehn, Hoang, Birch, Callison-Burch, Federico, Bertoldi, Cowan, Shen, Moran, Zens, Dyer, Bojar, Constantin and Herbst2007)).
The relationship between source phrase and target phrase is not uniform. Morphologically rich languages, such as Arabic, typically have fewer words in a sentence than English. In most Arabic–English parallel corpora (e.g. LDC), the sentence length ratio (in terms of number of words) between Arabic and English is between 1 and 1.5. We use this ratio to further restrict the search with the following conditions:
$$\begin{equation}
\frac{1}{c_1} \cdot l - c_2 \le k \le c_1 \cdot l + c_2
\end{equation}$$
where c 1 is the length ratio and c 2 is an additive constant. Both c 1 and c 2 are selected empirically using a held-out data set.
Lexical translation models used in the alignment process may contain erroneous alignments that will affect the phrase extraction process. The models could give highest score to an alignment that is not the best, or the correct one. Therefore, we select not only the best phrase pair, but all candidate phrase pairs whose scores lie within a margin of the best one. There margin boundaries are selected empirically, using a held-out data set.
Search for the remaining parallel phrases in a comparable sentence pair
3.2.3 Find remaining parallel phrases in the sentence
There are four possible regions (regions 1, 3, 5 and 7 in Figure 4, counting clockwise starting from bottom left region) in which the remaining parallel phrases can be present. To detect them, a greedy search is performed as follows:
(1) Define a set
$\mathcal{A}$ which contains tuples (i, j) to indicate the word positions that are already covered by previously identified phrase pairs. This is initialized with values from the best parallel phrase pair identified as in the previous section.(2) For each of the possible phrase pair regions of remaining word pairs, iterate over all possible placements of them in the sentence pair. They are considered as candidates only if they can be placed completed on an unaligned area. i.e. the word alignment pairs corresponding to the phrase pair are not included in
$\mathcal{A}$.(3) Out of all possible such phrase pair candidates, pick the pair that gives the best overall sentence alignment.
(4) The phrase pair is extracted as parallel only if the alignment probability is better than the previous sentence alignment probability. i.e. the phrase pair is better explained using the translation model than the language model.
$\mathcal{A}$ is updated accordingly.(5) This process is iterated until no further parallel phrases can be identified.
The search algorithm is as shown in Algorithm 2. Several computational steps in this algorithm can be reduced by incremental calculation of the partial sums of probabilities.
3.2.4 Find target boundaries for a given source phrase
Algorithms 1 and 2 above together extract all possible parallel phrase pairs from a given comparable sentence pair. This approach is appropriate when we attempt to build a phrase table from all available corpora before decoding a test set. Alternatively, PESA performs real-time phrase extraction at decoding time, where no pre-computed phrase table exits. At run-time, an appropriate target phrase needs to be extracted for the source phrase under consideration. We present a modified version of the search algorithm in Algorithm 3, where the target phrase boundaries are obtained for a given source phrase.
Algorithm to identify the best target boundaries for a given source phrase
When extracting phrases for a test set, we first generate all possible source phrases (with phrase length ranging between lmin and lmax), and extract the desired target phrases using algorithm 3 above. By restricting the search of target boundaries for only a given source phrase, we reduce the run-time complexity of the algorithm to O(c.I), where c is the number of different source and target phrase length combinations allowed. This is faster than aligning all the words in the sentence pairs as in the Viterbi alignment.
3.2.5 Additional features
In our initial experiments, we found that the phrases extracted using the equation (7) tend to have incorrect word boundaries. Most of the time, the extracted phrase contained more words on either side of the boundary. This is due to the effect of two language model scores for the left and right of the parallel phrase, where the model prefers a smaller language model score. We introduce the following additional features to better balance the phrase length. We defined the following additional features:
• Phrase Length Ratio (one feature): This is the ratio between the source phrase length and the target phrase length. i.e. |j 2 − j 1|/|i 2 − i 1|.
• Phrase Length Difference (one feature): Difference in source phrase length and the target phrase length. i.e. |j 2 − j 1| − |i 2 − i 1|.
• Target Language Model Score for outside region (two features): These scores are normalized with respect to the source or target phrase length.
• Phrase alignment score for the inside region (one feature): This is computed as in equation (4).
The phrase alignment score in equation (7) is combined with the additional features in a weighted log-linear model as follows:
$$\begin{equation}
(i_1,i_2)_{best} = \underset{(i_1,i_2)}{\operatorname{argmax}} \sum _{k=1}^{6} \lambda _k F_k (f_1^J,e_1^I,j_1,j_2)
\end{equation}$$
where Fks are feature functions as defined above and λks are the weights associated with feature function which are optimized, using a held-out data set.
3.2.6 Parameter optimization
To optimize the parameters of the extended phrase extraction model, we use a manually word-aligned parallel corpus. From this corpus, we extract parallel phrase pairs that are consistent with the underlying word alignments. Each source phrase was allowed to have multiple reference target phrases. The details of the extraction process are explained in Section 4.1.
We use the online margin infused relaxed algorithm (MIRA) (Crammer et al. Reference Crammer, Dekel, Keshet, Shalev-Shwartz and Singer2006) to obtain the optimized model weights. MIRA is defined by an update rule, which is subject to max-margin constraints with respect to a loss function that is computed for the predicted hypothesis against the reference phrase. The weights are updated after seeing each training phrase pair in each iteration. Change in the weight vector is constrained so that the margin between the hypothesis and the reference should be at least as large as the loss value. Formally, the update rule in MIRA is as follows:
$$\begin{equation}
\underset{w}{\operatorname{argmax}} \;\; ||w^{i+1} - w|| + C \cdot \sum _k \xi _k (y_t, y^{\prime })
\end{equation}$$
$$\begin{equation*}
s.t., \;\;\;\; s(x_t,y_t) - s(x_t,y_k) + \xi _k(y_t,y^{\prime }) \ge L(y_t,y^{\prime }); \;\; y^{\prime } \in best_k (x_t, w^i); \;\; \xi _k(y_t,y^{\prime }) \ge 0 \nonumber
\end{equation*}$$
where w is the weight vector, yt is the target candidate closest to the reference phrase, y′ is in the k-best candidate list, s(x, y) is the scoring function, L(yt, y′) is the computed loss. ξk is the slack variable whose value is always non-negative and C is the slack constant the determines how aggressively the weight vector is updated after each instance. The weights obtained after each update are averaged at the end of the training step in order to avoid overfitting.
We optimize the model performance toward an oracle target phrase which is selected from a k-best list of candidate target phrase translations. Reference target phrases obtained from the manual alignment may not always be reachable by the phrase extraction algorithm. This is due to the fact that we extract target candidate phrases from sentence pairs, which contain the source phrase in the source sentence, but may not always contain the reference phrase in the target sentence (i.e. an alternative translation). Thus, from the k-best list of candidate target phrases, we select an m-best list of target phrases that are closest to one or multiple references. In the experiments, we set m=1 (i.e. only the first-best oracle phrase is considered).
To compute the loss function, we use a modified smoothed version of BLEU (mBLEU). The BLEU metric is defined on the document level which considers n-gram precision (typically up to four). To compute BLEU-like scores at the phrase level, we define a smoothed version that considers only unigram matches in its computation. The smoothing technique is similar to the NIST BLEU version.Footnote 1 It is computed by adding a partial count of (1/2k) for each precision score whose matching n-gram count is zero, where k = 1 for the first n values for which the n-gram match count is zero. The loss function using the smoothed-BLEU is defined as follows:
$$\begin{equation*}
L(y_t,y^{\prime } = 1 - mBLEU(y_t, y^{\prime })
\end{equation*}$$
The error rates in training and testing sets for MIRA is evaluated in terms of normalized Levenshtein distance at word level (i.e. word error rate). This metric awards partial ‘credit’ for candidate target phrases when the reference phrase is not always reachable. With the extracted phrase pairs from the manually aligned corpus, we used a seventy five/twenty five per cent split for training/testing. Each source phrase is allowed to have multiple reference phrase pairs in the setup. We generate a ten-best target phrase candidate list for each source phrase and evaluated the error against the first best candidate. We run MIRA for ten iterations. The final averaged weight vector obtained after the optimization is used for the phrase extraction experiments in Section 4.2. Further details of the optimization is described in Gupta, Hewavitharana and Vogel (Reference Gupta, Hewavitharana and Vogel2011).
3.3 Other approaches
We compare the proposed phrase extraction with two other phrase alignment approaches.
3.3.1 Standard Viterbi alignment
We use the standard phrase extraction approach used by most phrase-based SMT systems: obtain word alignment models for both directions using IBM models (source to target and target to source), combine the Viterbi paths using one of many heuristics and extract phrase pairs from the combined alignment. We used the Moses toolkit (Koehn et al. Reference Koehn, Hoang, Birch, Callison-Burch, Federico, Bertoldi, Cowan, Shen, Moran, Zens, Dyer, Bojar, Constantin and Herbst2007) for this task. To obtain the word alignments for comparable sentence pairs, we performed a forced alignment using the models trained on parallel data.
3.3.2 Binary classifier
We use a Maximum Entropy classifier as our second alternative approach to extract parallel phrase pairs from comparable sentences. Such classifiers have been used in the past to detect parallel sentence pairs in large collections of comparable documents (Munteanu and Marcu Reference Munteanu and Marcu2005; Tillmann and Hewavitharana Reference Tillmann and Hewavitharana2013). Our classifier is similar, but we apply it at phrase level rather than at sentence level. The classifier probability is defined as
$$\begin{equation}
p(c|S,T) = \frac{exp \left( \sum _{i=1}^{n} \lambda _i f_i(c,S,T) \right)}{Z(S,T)}
\end{equation}$$
where S = sL 1 is a source phrase of length L and T = tK 1 is a target phrase of length K. c ∈ {0, 1} is a binary variable representing the two classes of phrases: parallel and not parallel. p(c|S, T) ∈ [0, 1] is the probability where a value p(c = 1|S, T) close to 1.0 indicates that S and T are translations of each other. fi(c, S, T) are feature functions that are co-indexed with respect to the class variable c. The parameters λi are the weights for the feature functions obtained during training. Z(S, T) is the normalization factor. In the feature vector for phrase pair (S, T), each feature appears twice, once for each class c ∈ {0, 1}.
The feature set we use is inspired by Munteanu (Reference Munteanu and Marcu2005), who define the features based on IBM Model-1 (Brown et al. Reference Brown, Della Pietra, Della Pietra and Mercer1993) alignments for source and target pairs. However, in our experiments, the features are computed primarily on IBM Model-1 probabilities (i.e. lexicon). We do not explicitly compute IBM Model-1 alignments. To compute coverage features, we identify alignment points for which IBM Model-1 probability is above a threshold. We produce two sets of features based on IBM Model-1 probabilities obtained by training in both directions. All the features have been normalized with respect to the source phrase length L or the target phrase length K. We use the following eleven features:
(1) Lexical probability (two features): IBM Model-1 log probabilities p(S|T) and p(T|S).
(2) Phrase length ratio (two features): source length ratio K/L and target length ratio L/K.
(3) Phrase length difference (one feature): source length minus target length, L − K.
(4) Number of words covered (two features): A source word s is said to be covered if there is a target word t ∈ T such that p(s|t) > ε, where ε = 0.5. Target word coverage is defined accordingly.
(5) Number of words not covered (two features): This is computed similarly to (4) above, but this time counting the number of positions that are not covered.
(6) Length of the longest covered sequence of words (two features).
To train the classifier, we used parallel phrase pairs extracted from a manually word-aligned corpus. In selecting negative examples, we followed the same approach as in Munteanu and Marcu (Reference Munteanu and Marcu2005): pairing all source phrases with all target phrases, but filter out the parallel pairs and those that have high length difference or a low lexical overlap, and then randomly select a subset of phrase pairs as the negative training set. The model parameters are estimated using the GIS algorithm.
4 Experiments
4.1 Alignment accuracy
To compare the performance of the three phrase alignment methods discussed so far, we need a comparable corpus containing sentences with a known parallel phrase pair embedded in them. Using a manually aligned parallel corpus, and two monolingual corpora, we obtained a test corpus as follows: For each parallel phrase pair, we search a source language corpus for sentences that contain the source phrase, and a target language corpus for sentences that contain the target phrase. We measure phrase-level exact matches, as well of unigram level precision, recall and F measure. The scores are computed for each phrase pair, and then aggregated to produce a score for the test set.
For this evaluation, we used Arabic–English language pair. We obtained a manually word aligned corpus containing 663 Arabic–English sentence pairs. From this, we selected 300 sentences, and extracted phrase pairs (up to ten words long) that are consistent with the underlying word alignment. From the resulting list of phrase pairs, we removed the fifty most frequently occurring pairs, as well as those only consisting of punctuations. Almost all high frequency phrases are function words, which are typically covered by the translation lexicon. Line 1 in Table 1 gives the n-gram type distribution for the source phrases.
n-gram type distribution of manually aligned phrase set
Using the phrase pairs extracted from the manually aligned sentences, we constructed a comparable corpus as follows:
(1) For each Arabic phrase, we search the Arabic GigawordFootnote 2 corpus for sentences that contain the phrase and select up to five sentences. Similarly, for each corresponding English phrase, we select up to five sentences from English Gigaword.Footnote 3
(2) For each phrase pair, we generate the Cartesian product of the sentences and produce a sentence pair collection. i.e. up to twenty five comparable sentence pairs were constructed for each phrase pair.
(3) Sentences that have more than hundred words were rejected. Not all phrases had a matching sentence pair in the corpus. The final comparable corpus contained 170 K sentence pairs.
Line 2 in Table 1 gives the n-gram type distribution for the phrase pairs for which we found both a source sentence and a target sentence in the monolingual corpora. As expected, the longer the phrases, the less likely it is to find them in even larger corpora. We consider the resulting set as our comparable corpus which we use to evaluate the three alignment approaches. In most sentence pairs, except for the phrase pair that we are interested in, the rest of the sentence does not typically match the other side.
We obtained the Viterbi alignment using standard word alignment techniques: IBM4 word alignment for both directions, Viterbi path combination using heuristics (grow-diag-final) and phrase extraction from two-sided training, as implemented in the Moses package (Koehn et al. Reference Koehn, Hoang, Birch, Callison-Burch, Federico, Bertoldi, Cowan, Shen, Moran, Zens, Dyer, Bojar, Constantin and Herbst2007). Because the non-parallel segments will lead the word alignment astray, this may have a negative effect on the alignment in the parallel sections. Alignment models trained on parallel data are used to generate the Viterbi alignment for the comparable sentences. We then extract the target phrases that are aligned to the embedded source phrases. A phrase pair is extracted only when the alignment does not conflict with other word alignments in the sentence pair. The alignments are not constrained to produce contiguous phrases. We allow unaligned words to be present in the phrase pair. For each source phrase, we selected the target phrase that has the least number of unaligned words.
The classifier (Section 3.3.2) is applied at the phrase level. We generate the phrase pair candidates as follows: For a given target sentence, we generate all n-grams up to length 10. We pair each n-gram with the source phrase embedded in the corresponding source sentence to generate a phrase pair. From the 170 K sentence pairs, we obtained 15.6 million phrase pair candidates. The maximum entropy classifier is then applied to the phrase pairs. For each source phrase, we pick the target candidate for which p(c = 1, S, T) has the highest value.
For the extended-PESA phrase alignment algorithm described in Section 3.2, we used both inside and outside alignments as explained earlier. For each source phrase pair, we select the best scoring target phrase using Algorithm 3.
As our goal is to use these methods to extract parallel data for low resource situations, we tested each method with several lexica, trained on different amounts of initial parallel data. Starting from the full Arabic–English parallel corpus with 127 million English tokens, we generated three additional parallel corpora, namely Large, Medium and Small, with 1/3, 1/9 and 1/27 of the original size, respectively. The three new corpora contain roughly 40 million, 13 million and 4 million English tokens. Medium and Small corpora are a better match to the resource levels for many languages. We also used data from the BTEC (Kikui et al. Reference Kikui, Sumita, Takezawa and Yamamoto2003) corpus. This corpus contains conversational data from the travel domain, which is from a different genre than the document collections. Compared to other corpora, it is much smaller (about 190 thousand English tokens).
Table 2 gives the results for all three alignment approaches. Results are presented as percentages of: exact matches found (Exact), precision (P), recall (R) and F. The Viterbi alignment gives the lowest performance. This shows that the standard phrase extraction process, which works well for parallel sentences, is ill-suited for comparable sentences. Despite the fact that the classifier incorporates several additional features including the lexical features, the performance of the extended-PESA alignment shows consistently higher precision than the classifier approach. This demonstrates that computing both inside and outside probabilities for the sentence pair helps the phrase extraction. The classifier lacks this ability because the phrase pair is evaluated in isolation, without the context of the sentence.
Alignment accuracy for the three approaches: standard Viterbi, classifier and the extended-PESA approach
Except for the BTEC corpus, the performance degradation is smaller as the lexicon size is reduced, indicating that the approaches are robust for smaller amounts of parallel data.
Instead of using token precision, an alternative method of evaluating partial matches, is to give credit based on the length of the overlap between the extracted phrase and the reference. Precision and recall can then be defined based on the longest common contiguous subsequence, similar to Bourdaillet et al. (Reference Bourdaillet, Huet, Langlais and Lapalme2010). Results we obtained using these methods were similar to the results in Table 2.
In the translation experiments below, we compare the performance of phrases extracted from the standard Viterbi alignment and the extended-PESA alignment.
4.2 Translation results
4.2.1 Arabic–English
For Arabic–English experiments, we used a large baseline parallel corpus of about ≈ 6 million sentence pairs (120 million English words). We extract comparable sentence pairs from the Gigaword Arabic and Gigaword English corpora, using a maximum entropy classifier similar to Tillmann and Hewavitharana (Reference Tillmann and Hewavitharana2013). Extracted sentence pairs with a similarity score above an empirically determined threshold were selected as parallel sentences. The remaining sentences that were below the cut-off threshold, were used for the phrase extraction experiments (see Figure 1 for the data extraction pipeline).
From the comparable sentences, two sets of phrase pairs were extracted: one using the Viterbi alignment and the other using the extended-PESA method as in Algorithm 3. The extraction process followed the same steps explained in Section 4.1, i.e. using different sizes of initial parallel data to generate translation lexica, as a simulation of various resource availability scenarios. The phrases extracted from the Viterbi alignment were sampled to include only those needed to cover the source side of the test sets.
The Algorithm 3 extracts target translations for a given set of source phrases. We used two test sets from previous MT evaluations by NIST: MT05 (≈ 1 K sentences) and MT06 (≈ 1.7 K sentences). For each test set, we generated all source n-grams up to seven words, and used them to extract phrases using Algorithm 3. The model parameters were optimized using MIRA as described in Section 3.2.6 using manually aligned data. For each source phrase, we extract up to ten target translation alternatives. From the comparable sentences, we extracted ≈ 800 K phrase pairs, out of which ≈ 100 K were new source phrases. The extracted phrases had an average length of 2.7 words (compared to 2.0 words for the phrases extracted using the Viterbi alignment).
A standard phrase-based MT decoder (Vogel Reference Vogel2003), which is similar to Moses (Koehn et al. Reference Koehn, Hoang, Birch, Callison-Burch, Federico, Bertoldi, Cowan, Shen, Moran, Zens, Dyer, Bojar, Constantin and Herbst2007) was used in the translation experiments. A 4-gram language model was trained using the English side of the corpus. As the baseline MT system, we not only use parallel data, but also the sentences extracted from comparable data (i.e. step 2 in Figure 1). Two tests from previous NIST MT evaluations were used: MT05 as the development set to optimize the decoder parameters (using MERT [Och Reference Och2003])”, and MT06 as an unseen test set.
The extracted phrases were combined with phrases extracted from different sizes of initial parallel data, (i.e. 4.5 M(Small), 13 M(Medium), 40 M(Large) and 120 M(Full) word corpora). Translation results for Arabic–English are given in Table 3, in BLEU (Papineni et al. Reference Papineni, Roukos, Ward and Zhu2002), METEOR (Banerjee and Lavie Reference Banerjee and Lavie2005) and TER (Snover et al. Reference Snover, Dorr, Schwartz, Micciulla and Makhoul2006) metrics. The results are shown for three systems:
Translation results for Arabic–English extracted phrases when combined with the extracted sentences plus different sizes of initial parallel data. Each row indicates the size of the initial parallel corpus used as the baseline system. Best results for each metric are marked in boldface
Baseline+Sentences: Phrases extracted from the initial parallel data plus the extracted parallel sentences from comparable data. This serves as the baseline for the phrase extraction step, which we try to surpass with the extracted phrases.
+Phrases(Viterbi): Phrases extracted using the Viterbi alignment when combined with phrases from Baseline+Sentences.
+Phrases(Ext-PESA): Phrases extracted using the extended-PESA approach when combined with phrases from Baseline+Sentences.
The results show that the extended-PESA phrase extraction method is consistently better than extracting phrases with the standard Viterbi algorithm. When the new phrases are added, there is an improvement in performance for the Small system. This difference is statistically significant (at ninety-five per cent level) for MT06. However, for other systems, the extracted phrases fail to improve the performance over the combined Baseline+Sentence system. Although the phrase extraction brings in additional phrases, the improvement in source side coverage compared to the phrases in the baseline system range between two per cent and five per cent for different systems. As the phrases are extracted from comparable data, the additional phrase pairs may introduce noise to the combined system. For the smallest systems with the lowest lexical coverage, the additional phrases help improve the performance. When the size of the system increases, we notice that the additional phrases starts having less effect, and leads to degradation of results.
The Arabic–English parallel corpus that we used in the experiments is larger in size compared to the parallel resources available for many other language pairs. Next, we apply the same phrase extraction pipeline to Urdu–English, which is a true low-resource language pair.
4.2.2 Urdu–English
For Urdu–English experiments, we used a parallel corpus with ≈ 55 K sentence pairs (≈ 1 million English words. Comparable sentence pairs were extracted using Urdu and English news articles from Voice of America, and BBC News, which resulted in a collection of ≈ 250 K sentence pairs. Out of this, we selected the top twenty five per cent scoring sentences as parallel (≈ 100 K sentence pairs), and combined with the baseline to produce the ‘Baseline+Extracted Top twenty five per cent’ system that serves as our baseline for the phrase extraction. We used the remaining sentences for the phrase extraction task, and extracted two sets of phrases, one each using the Viterbi alignment and the extended-PESA approach as in Algorithm 3. Two test sets from previous NIST MT evaluations (Newswire portions): MT08-NW and MT09-NW, were used as evaluation sets.
Similar to Arabic–English experiments in the previous section, we generated all source n-grams up to length 7 from the two test sets, and extracted up to ten target translations for each source n-gram. From the comparable sentences, we extracted ≈ 425 K phrase pairs, out of which ≈ 180 K were new phrase pairs. These phrases covered ≈ 20 K additional source n-grams, which is a thirty per cent increase in source n-gram coverage compared to the ‘Baseline+Extracted Top twenty five per cent’ system. The extracted phrases had an average length of 3.24 words (compared to 2.1 words for the phrases extracted using the Viterbi alignment). The Viterbi alignment added ≈ 700 K new phrase pairs which covers ≈ 50 K new source n-grams.
We combined the extracted phrases with the phrases extracted from the ‘Baseline+ Extracted Top twenty five per cent’ system and used in the translation experiments. The translation setup including the decoder and language model remained the same as in Arabic–English. We used the MT08 development set to optimize the decoder parameters using MER training. Two translation systems were built, one each from the phrases extracted using the Viterbi alignment and the extended-PESA alignment.
Translation results for Urdu–English are given in Table 4. Results are given in BLEU, METEOR and TER metrics. For each test set, the first line gives the results for the baseline. The second and third lines give the results for the phrase extraction using Viterbi approach and the proposed approach, respectively. The fourth line ‘Baseline+Extracted All’ indicates combining the baseline parallel corpus with all extracted comparable sentence pairs. The results show that the extended-PESA phrase extraction method is significantly better than the Viterbi phrase extraction. This is despite the fact that the Viterbi extraction approach adding much more phrases than the proposed approach. It is clear that much of these phrases have not helped in improving the translation performance due to the noisy nature of the translations. When the extracted phrases are combined with the baseline system, it shows statistically significant improvement (at ninety five per cent level) for both test sets, compared to all the extracted sentences (last line in Table 4). This shows that selectively extracting phrase level parallel data leads to better translation performance than generating new models with the full extracted corpus.
Translation results for Urdu–English extracted phrases when combined with the baseline corpus. Best results for each metric are marked in boldface
From the experiments with Arabic–English and Urdu–English, we can see that extracting parallel data at phrase level helps translation performance when the lexical coverage is limited. When the amount of available parallel data increases, the effect of the extracted data diminishes.
5 Conclusions and future directions
In this paper, we focused on extracting parallel phrase pairs from comparable data. The rationale for this was that by selecting only the parallel phrases from comparable sentences, we prevent the non-parallel parts from adding noise to the clean parallel data. We proposed a novel phrase alignment approach for comparable corpora, which is an extension of the PESA algorithm originally designed for parallel sentences. We proposed several algorithms to extract phrase pairs. We evaluated the proposed alignment approach with two additional methods: the standard Viterbi phrase alignment, and a maximum entropy-based binary classifier that works at phrase-level. Evaluations with Arabic–English phrase alignments showed that the proposed method has a better F-score than the other two approaches.
We evaluated the potential of the extracted phrase pairs in the context of an end-to-end translation system. Translation results with the extracted phrases for Arabic–English showed only marginal improvements in evaluation metrics, when the initial parallel corpus is small. However, for Urdu–English, which is a low-resourced language pairs, we saw 1.21 BLEU per cent improvement over the baseline. Further, the translations results showed that selectively extracting parallel phrases from comparable sentences produce better results.
The proposed models are based primarily on the word alignment probability. We also included additional features based on phrase length and target language model. Other types of features such as part-of-speech, cognates, transliteration models may help the phrase alignment process. Markup data (e.g. anchor text, image titles, urls, etc.), when available, may also be used as features. In our translation experiments, we did not distinguish phrase pairs extracted from comparable corpora from those extracted from parallel data. Alternatively, the two types of phrases could be used with different weights, giving priority to phrase pairs originated from parallel corpora. As the extracted phrases tend to be noisy, this approach may help improve the translation accuracy.
The lack of parallel data for many language pairs is the primary motivation for using comparable corpora to extract translational equivalences. When crawling comparable articles for low resource languages, we observed that these documents are available in multiple languages, giving the possibility of collecting multilingual comparable corpora. It is quite interesting to explore the current framework to extract data from multilingual corpora. Recent research on multilingual SMT has focused on using a language, usually with richer resources (e.g. English), as a pivot language to overcome the resource limitations in certain language pairs. We plan to explore a similar approach to extract data from multilingual comparable corpora to extract data for language pairs that have low resources.
