2.1 Link extraction as a pattern recognition problem

In this section we define the link alignment problem in more technical detail. We present a geometrical pattern recognition definition of the chunk alignment problem that paves the way for the formal description of the unified algorithm in Section 4. We are trying to align a collection of source sentences {s_m} and target sentences {t_n}, where 0 ≤ m ≤ and 0 ≤ n ≤ . and are the number of source and target sentences. We are searching for the so-called link alignment sequences l^N ₁ that consists of N links (N is unknown before the search). A link sequence l^N ₁ is a list of interval pairs that jointly cover the unaligned bitext based on certain alignment coverage and continuity restrictions that depend on the search types. A single link is a interval pair that covers a square in the bitext space:

(1)\begin{eqnarray} l = \left[\; [ j_{beg}(l)\;,\; j_{end}(l) ]\;,\; [\; i_{beg}(l)\;,\; i_{end}(l) ]\; \right]\; \end{eqnarray}

We now describe different coverage and continuity restrictions for link sequences that are handled jointly by the unified search algorithm. By default, each source text position j is covered by exactly one source link interval [j_beg(l), j_end(l)]. Link source interval sequences are restricted with respect to their begin and end positions: j_beg(l) = j_end(l−1)+1 as well as j_beg(l ₀) = 0 and j _end(l_N) = . The target coverage varies for different search types. For the Type I search, the link sequence coverage is also monotone over the target text, and link target sequences are restricted as follows: i_beg(l) = i_end(l−1)+1 as well as i_beg(l ₀) = 0 and i _end(l_N) = . For the Type II alignments, each target position is covered by at most a single link, and some local chunk re-ordering is allowed. For Type III alignments, only the default source coverage is used. Here, we also allow for overlapping link sequences during the search: A link ends at each source sentence position s and the same source word position j may be covered by several links. Unaligned source and target chunks are handled based on source and target null-coverage links as well. Details depend on different search types and are explained along with the unified search algorithm. In order to process the data at the word level, we maintain the following mapping index u_S(m):

(2)\begin{eqnarray} m & \rightarrow & (\mbox{start position of $m$-th sentence}, \mbox{end position of $m$-th sentence}) \end{eqnarray}

The unified search algorithm to be defined in Section 4 is a shortest path finding algorithm. Each link sequence corresponds to a path through the bitext space, where a single link is re-presented by its link diagonal. The shortest path is restricted based on the search type restrictions described above. For a single link, the matching cost is computed as the matching score between the pair of text chunks that are covered by that link. Unlike work on word alignment algorithms, transitions between separate links are assigned zero cost, and the cost of a link sequence is defined as

(3)\begin{eqnarray} c\big(l_1^N\big) = \sum_{i=1}^N \varrho(S(l_i), T(l_i)) \end{eqnarray}

(4)\begin{eqnarray} \hat{l}_1^N = \argmin\limits_{l_1^N} c(l_1^N) \end{eqnarray}

$\hat{l}_1^N$

The link alignment search is handled as a pattern recognition problem. The source document is the input pattern that is assumed to be decomposed into chunks. Those source chunks are aligned to reference patterns that are target word chunks. In particular, the search for Type III alignments can be directly compared to a pattern recognition formulation of the SR search problem (Ney Reference Ney1984). The source chunks correspond to words in the acoustic input signal. Each document position within a chunk corresponds to an acoustic time frame in the SR search. Each time frame in the SR search is represented by an acoustic vector that is matched against the reference patterns. Similarly, each source chunk word position together with its target chunk match is re-presented by a partial feature vector, which is used in the Maximum Entropy (ME) classifier in Section 3. A sum of these local feature vectors is used to compute a matching score for the source chunk against a target chunk with which it is aligned. As the chunk alignment problem considers links of different granularity, it is a more general pattern search algorithm than the SR search in Ney (Reference Ney1984) that considers only one-to-one word-level mappings.

4.1 List processing

This section explains how the recombination function (·) and extension function (·) are computed for various alignment and link types. The approach to recombination is explained in detail for the Type I alignment search, where states are defined in (10). We define a lexicographical order on the state set Γ: the states are sorted by the target position i. Within each equivalence class, the hypotheses are then sorted by increasing score. After sorting, states σ that are equivalent to each other, i.e. whose partial link sequences end at the same target position i occur at consecutive array positions. In that list, the lowest scoring states of each such equivalence class occur first. In a single run over the list, whenever we encounter the element of a new equivalence class, we know it is the lowest scoring one, and we just keep this state in the reduced list after recombination. We can formally define the partial hypotheses order as follows:

(11)\begin{array}{lll} [i;d]<[i';d'] & {\bf iff} & (i<i') \end{array}

(12)\begin{array}{lll} h' \mbox{eq} h & {\bf iff} & \lnot (h<h') \mbox{and} \lnot (h'<h) \end{array}

The extension algorithm to compute (·) is illustrated in Algorithm 2. A list of hypotheses Γ is extended by handling each hypothesis σ∈Γ individually and appending the resulting list: (Γ) := ∪_σ∈Γ(σ). Algorithm 3 computes an auxiliary function. It generates successor links given the bitext ending position [j_end, i_end] of the preceding link l. Each state σ∈Γ is extended by L = || possible links, e.g. for a search with the 1-to-4 link set: L = 9 (including null links). For the monotone Type I alignment search, the L successor links start where the previous partial link sequence ends. For the Type II search, new sentence links are generated within a window of W = 20 target sentence positions. At each of these positions, one of the L different links can start. For the Type III alignment search, we search over a large number of candidates: there is no monotone alignment restriction and each of the L alignment types may start at any target sentence position. This search type can only be carried out in connection with the pruning described in Section 5.1, as there might be hundreds of thousands of candidates for a given source sentence. The pruning candidate set is denoted as Θ(S_m), where s_m is the m-th sentence in the source document. Here the candidate set Θ(S_m) is computed only once for each s_m. The same candidate set pruning is used for the Type I sub-sentential alignment search. Here the length of sub-sentential links is less than ten for both source and target chunks, i.e. the size of the extension set is L = 100. A link l ending at a sentence-internal position is only possible for the sub-sentential search Type I search. These partial sequences are extended monotonically as well. We use the notation l∈Θ to denote a link l whose bitext starting position coincides with the starting position of one of the candidate links. The Type II alignment search extension is handled similarly as the Type III extension and details are given in Section 5.1.

Algorithm 2

Hypotheses List Extension Function. The function computes the successor states for an hypothesis with link l that ends in bitext position [j_end, i_end]. The auxiliary function (·) is defined in Algorithm 3. The link-type set can be defined at run time. λ is a binary variable, where λ = 0 indicates a search for sentence-level and λ=1 for sub-sentential links.

Algorithm 3

Link extension function (·). The allowable link-type sets are defined in Figure 2. The functions u ⁻¹_S(j) and u ⁻¹_T(i) yield the sentence-level position of document word-level source and target position (The indexing functions u_S(·) and u_T(·) are defined in Section 2.1). As there is no cost for transitions between links, the link score d is just copied into the link extensions.

4.2 Complexity analysis

For the Type III alignment search, in analogy to the use of many-to-many links in Type I alignments, we still segment the source document into chunks. There is an exponential number of global paths to be considered as shown in Figure 5. Links that cover neighboring source chunks do not restrict each others' relative target document positions (cf. Figure 3). In particular, we allow the same target chunk to be aligned to several different source chunks ignoring the coverage restrictions of Type I or Type II search. The search is very effective in this case: The list of ‘recombined’ states collapses to just a single active state as the segmentation task focuses on the source chunk segmentation only. A possible disadvantage of the global distance definition as given in (3) is that the global path depends on the path length, and thus shorter paths with fewer links N are favored. Ney (Reference Ney1984) points out a similar disadvantage of a global path length criterion. In the context of sentence alignments, it might lead to locally wrong link boundary decisions. In Section 4, we have presented a simple solution to this problem by allowing links to overlap based on the trace-back array usage. This seems to mitigate the problem in the context of one-to-many links and Type III alignments as shown in Section 6.

Fig. 5.

Illustration of the number of source document segmentations for a Type III alignment with 2-to-1 links. At each source position two source chunks start (with the exception of path end positions). These are matched against at least a single target chunk and are shown as transition links. Here, there are at least $2^{({\cal S}-2)/2}$ different segmentation paths where is the number of source sentences.

The complexity of different search types is given in Table 1. The corpus parameters , , , and have been defined in Section 2.1. In order to compute the search algorithm complexity for each search type, we count the number of state expansions, i.e. the number of times line 15 in Algorithm 1 is executed. We ignore the complexity for the list processing functions (·) and (·). These operations can be carried out efficiently, whereas the score computation involves expensive probability look-ups based on large data structures. In Table 1, the ‘fan-out’ column gives for each complete search state σ, the maximum number of successor states generated due to the extension function (·). The ‘Rec’ column reports for each search type the maximum number of different hypotheses after the recombination has been carried out for a state list Γ. The complexity given in the last column of Table 1 is derived by multiplying the two preceding ‘fan-out’ and ‘rec’ columns. The factors and take into account that the recombination and extension operations are carried out at sentence boundaries (Types I–III), and possibly all word positions j (Type I sub-sentential alignment). Here, is the average source chunk length for the L different links. This factor is included as ‘link-internal’ states are extended deterministically in the scoring step in Algorithm 1. For the sub-sentential Type I search, the average source chunk length is = 5 (since the maximum source chunk length is 10). We note that because of the length factor , the complexity is increased more than linearly in the number of link types.

Table 1.

Search complexity for different types along with search state definition, ‘fan-out’ (number of extensions per grid-point), maximum number of hypotheses in the single beam at position j (after recombination), and overall search complexity. is the average number of source words covered by a link. W = 20 is the size of the Type II re-ordering window. The complexity for the sub-sentential search assumes a monotone alignment across the entire document bitext

5.1 Beam-search pruning

Except for the alignment Type I search, we cannot carry out a full search over the bilingual data. The link sequences l^N ₁ considered during search must be restricted appropriately. To do so, we modify previous work on extracting one-to-one sentence-level translation pairs from comparable data (Tillmann and Xu Reference Tillmann and Xu2009). During the left-to-right run over the source word-level positions j, whenever we reach the starting position of a sentence S in the source document, we compute the following candidate set of sentence-level 1-to-1-type links l_i:

(13)\begin{eqnarray} \Theta(S) = \{l_i = (S,T_i) |\; T_i\; \mbox{among the lowest scoring} \;\;\;\;\;\;\;\;\; \mbox{$N$ links with score \varrhov'($S, T_i$)}\; \} \nonumber \end{eqnarray}

For the Type III search, the links considered are restricted based on the candidate set Θ(S) as follows: Only those links l whose bitext start position is identical to one of the links l_i, i.e. i_beg(l) = i_beg(l_i) and j_beg(l) = j_beg(l_i) are considered, i.e. a many-to-many link is considered only if its lower left corner is part of the candidate set. The use of this candidate set in the extension of search hypotheses is shown in Algorithm 2. For the sub-sentential Type I alignment search, the candidate set Θ(S) restricts the number of sub-sentential links that are considered during search: the sub-sentential links l are covered entirely by one of the candidates l_i, i.e. l⊆l_i. For the Type II search, we compute the average of all link start positions i_beg(l_i). This number defines the coverage focus point, which is used to restrict the permissible target coverage vectors in the search states l, ; d. A state σ is extended with links l whose starting position i_beg(l) lies within a window of ±10 positions from that focus point. The target coverage vector ensures that each target sentence is aligned to at most a single source sentence. The candidate pruning step is not applied for the Type I sentence-level search where a full search can be carried out.

The candidate pruning step is related to similar pruning steps in SMT decoders. For a given source segment, i.e. a word or a phrase, only a restricted number of translation candidates are considered in the decoder. Apart from the candidate pruning step, no additional pruning is carried out currently, i.e. there is no global pruning based on the partial scores in the current beam at position j. Due to the candidate set computation, the algorithm's memory usage depends on the average source sentence length in a document. Similar candidate pruning techniques have also been introduced for stack-based DP decoders in SR (Ortmanns, Ney and Eiden Reference Ortmanns, Ney and Eiden1996).

5.2 Efficient lexicalized scoring

In order to make feasible the sentence-level processing pipeline described so-far in this paper, the computation of the Model-1 scoring features in (5) and (6) needs to be very efficient. That efficiency is based on the decomposition of the scoring functions into I+J terms (I τ's and J σ's) where source and target terms are treated differently. While the scoring function computation is symmetrical, the processing is organized according the source language positions. This computational ‘non-symmetry’ is exploited as follows:

• • Array access for source term σ(s, T): The computation of the source term σ(s, T) is based on translation probabilities p(s|t). For each source word s, we can retrieve all target words t for which p(s|t) > 0 just once. Those words t along with their probabilities are then stored in an array of the size of the target vocabulary. Words t that do not have an entry in the lexicon have a 0 entry in that array. We keep a separate array for each source position. This way we reduce the probability access to a simple array look-up. Generating the efficient full array data structure requires less than 50 milliseconds per source sentence.

• • Caching of target term τ(t, S): For each target word t that occurs in a candidate translation T, the value τ(t, S) can be cached: its value is independent of the other words in T. The same word t in different target sentences is processed with respect to the same source chunk S and τ(t, S) has to be computed only once. Compared with Tillmann and Xu (Reference Tillmann and Xu2009), the cache implementation to account for arbitrary links is extended as follows. We compute the caching function across sentence boundaries and store the following value for each document source position j and target word t:

  \begin{eqnarray*} c_t(j)= \sum_{k=0}^j p(t|s_k) \end{eqnarray*}
  i.e. we cache a sum of probabilities starting from source position 0. Based on this extended caching function, for any link l, we can compute all the target scores τ(t, S) in the sum σ_S→T(S, T) in (6) in constant time based on the score difference c_t(j_end(l))−c_t(j_beg(l)). Since a source document may contain hundreds of thousands of words, this caching is carried out on the basis of source language window of 20 sentences.

The efficient computation of the candidate set Θ(S) also makes use of the caching and array access techniques presented in this section.

5.3 Partial feature vector computation

We select parallel chunk pairs based on the ME classifier defined in (7). It uses the following feature types: coverage, fertility, and intersection. These are computed on the basis of a Model-1 Viterbi alignment where a probability threshold of ε=5·10⁻⁴ is used to determine word alignment links. The classifier features are defined such that they can be computed incrementally on a position-by-position basis. To do so, we process the bilingual data one source position at a time. When covering a single source position j, we compute the additional covered target positions incrementally (see Figure 4). Just for this incremental position set, we compute the feature values below: for the single source position, we compute the source lexical, fertility, coverage, and romanization features. For a single target position, we compute target lexical, fertility, and coverage features. If the single source position is mapped to several target positions, their feature values are added. In addition, we compute coverage, length, and intersection features for each source position. Once the algorithm has finished the incremental processing of a given link l, features have been computed that account for exactly |S(l)|+|T(l)| link positions. We use the following eleven features:

• Lexical Probability (f₁, f₂): Two Model-1-based features are derived from the partial sums for the two directions in (5) and (6) : σ(s_j, T) and τ(t_i, S).

• Fertility (f₃, f₄): We define the fertility of a source word s as the number of target words t∈T for which p(s|t)>ε. A high-fertility word indicates non-parallelism. Target word fertility is defined accordingly.

• Consecutive Coverage (f₅, f₆): A source word s is said to be covered if there is a target word t∈T such that its probability is above a threshold ε:p(s|t)>ε. Consecutive coverage is the number of consecutively covered source word positions to the left of the current source position j. Target coverage is defined accordingly. A long run of covered positions indicates parallelism. In order to compute the coverage features, the search state definition in (10) is modified to keep track of the previous source and target word coverage. In the partial feature vector below, if f ₅<3, we use f ₅=0 instead. The feature f ₆ is handled accordingly.

• Coverage (f₇): The number of source and target positions covered by the Viterbi path inside a link is used as a feature. High coverage indicates parallelism.

• Length (f₈, f₉): We include the source and target chunk length ratio as ratio ‘penalty’ features: J/I and I/J. These features can be compared to the length penalty in regular SMT decoding (Koehn et al. Reference Koehn, Och and Marcu2003).

• Romanization (f₁₀): For each source chunk word s, we compute its Levenshtein distance with respect to all target chunk words t_i∈T(l) at the character level. For languages with non-Latin scripts (e.g. Russian and Arabic), the transliteration into Latin is done using an appropriate scheme, e.g. the Buckwalter scheme for Arabic. For the Spanish data, the string itself is used. The transliterated source string s is denoted by tr(s). The following feature value f ₁₀ is computed as

  \begin{eqnarray*} f_{10} = \left[ 1.0 - \max\limits_{1 \leq i \leq |T|} d(tr(s), t_i) \right] \end{eqnarray*}
  Here, d(t′, t_i) is the Levenshtein distance between the transliterated source word t′ and the i-th target word T_i.

• Intersection (f₁₁): The intersection feature is defined as the number of alignment points that occur on both Viterbi Model-1 alignments: source to target S→T and target-to-source T→S.

Empirically, we find that normalizing the incremental feature values with respect to source chunk length J or target chunk length I improves classification accuracy. The sentence length normalization has been applied to all the features in our experiments. We define an auxiliary feature vector f _j as follows:

(14)\begin{eqnarray} \bar{f_j} = (f_1, f_2, f'_3, f_4/I, f'_5, f'_6, f'_7, f'_8, f'_9, f'_{10}, f'_{11})\; \end{eqnarray}

6.1 Data sources and classifier training

The Russian data come from two sources: United Nations (UN) parallel documents and some news data. The Spanish–English and the Arabic–English data are based on the Gigaword data for these languages (Mendonca, Graff and DiPersio Reference Mendonca, Graff and DiPersio2009; Parker et al. Reference Parker, Graff, Kong, Chen and Maeda2009). The corpus statistics are shown in Table 2. Here, the Russian–English UN data consist of 16, 346 document pairs. For all the languages, the data are tokenized and number-classed (i.e. numbers are replaced with a single tag $num), and the bilingual matching features are computed on this pre-processed data. In addition, if the data does not have sentence-boundary annotation, we use punctuation information to split a text stream into sentences. In Table 3, we present classification results for the ME classifier described in Section 3 in terms of precision, recall, and F-score. The table contains the results for all three language pairs.The size of the annotated data for the Spanish–English, Russian–English, and Arabic–English data is 950, 1, 030, and 1, 600 sentence pairs, respectively. Roughly 80 per cent of the data sets are used to train the classifier and the rest are used for testing. Here the classifier selection threshold θ is set on the training data and lies in a range of [0.6, 0.75] for the different language pairs. The table demonstrates the effect of using different feature sets. The simplest model uses just two lexical probability features, f ₁, f ₂ from Section 5.3. Each line adds an additional feature, i.e. the final classifier uses all the features, including the Viterbi alignment intersection feature. Including additional features does not always improve classification accuracy. The largest improvements in terms of F-score are reported for the Spanish–English data. In particular, the romanization feature improves accuracy by almost 2 per cent for this European language pair. Another important feature is the intersection feature. For the three language pairs, there is a 0.4 to 0.7 per cent improvement over the classifier results where this feature is not used. For the extraction experiments reported later in this section, we always use the classifier with the full feature set.

Table 2.

Corpus statistics for the three languages pairs on which the extraction algorithm is evaluated

Table 3.

Classifier evaluation in terms of precision/recall/F-score on the manually annotated data for the three languages pairs. The feature functions are defined in Section 5.3

6.2 Translation experiments

We evaluate the performance of the unified search algorithm for different alignment and link types in terms of BLEU (Papineni et al. Reference Papineni, Roukos, Ward and Zhu2002) test set performance. Based on the unified alignment algorithm, chunk pairs are collected from the un-aligned, document-level aligned or comparable data, and this data are added to a baseline system. Using the ME-based extraction algorithm on data with different granularity and types of sentence-level alignments leads to an increased extraction accuracy and/or extraction yield. Only for the Russian–English UN data, there is an alignment at the document level. As the sentence alignment for these document pairs is largely monotone, a search for the alignment Types I and II is used on this data (alignment types have been defined in Section 2). Here, the largest document pair consists of up to 10, 000 source and target sentences. For the Type II alignment search, the beam at a given word position j may contain tens of thousands of states. As the average sentence length is around thirty words for these source sentences, the overall search space reaches billions of states. Processing on such a document pair takes about 1 hour on a single processor. In comparison, for the Russian–English news data, no document boundaries are given and the data can only be processed at the sentence level. For each Russian source sentence, only those target sentences for which the publication date differs less than three days from the publication date of the source sentence, are considered as translation candidates. For the Spanish–English Gigaword data, we also match chunk pairs that have been published from the same news feed, e.g. from a specific news agency like AFP. In addition, the beam-search pruning in Section 5 is used to speed up the search. For this comparable data, even though there is no document alignment, the original sentence order is partially preserved and potentially good many-to-many links can be found. For this data, a sentence-level search for Type III alignments as well as a sub-sentential search for Type I alignments are carried out. Similar experiments are carried out for the comparable English–Spanish and Arabic–English data, which comes from the Gigaword corpora for the years 2003–2008. Again, no document-level alignment is provided for this data. The same three-day publication date filter and sentence-length filter are used. Using a publication date filter of five days increased the number of sentences only slightly.

For the Spanish–English data, already for the one-to-one link search, the search space is huge: link candidates are selected out of 1.08 trillion candidate pairs. There are about 20 million source sentences each of which may have hundreds of thousands of target sentence candidates after the date filter and length filter steps. Since L candidates are considered at each grid point, the overall candidate set of many-to-many links may reach several trillions. Processing the English–Spanish data takes at most two days on a cluster with 300 processors. Processing the Arabic–English data takes less then a single day on the same cluster, while processing the Russian–English UN data takes only a few hours where the un-pruned Type I search runs fastest.

Extraction results are presented for the Russian–English data in Table 4, for the Spanish–English data in Table 5, and for the Arabic–English data in Table 6. The Model-1 probability models used to compute the feature functions in Section 5.3 are trained on the baseline data as well. The Model-1 training has been carried out for two iterations, and the dictionaries are un-pruned and include function words. The Russian–English dictionaries include 97 and 73 million entries, and the Spanish–English dictionaries include 73 and 87 million entries (Source-to-English and English-to-Source, respectively). The use of large un-pruned dictionaries improved extraction recall in preliminary experiments. In the first line of each table we report the number of parallel sentences along with the number of source and target words for the baseline data. On the baseline data, we train a phrase-based system and report its lower cased BLEU score (Papineni et al. Reference Papineni, Roukos, Ward and Zhu2002) on the test sets: for the Russian–English and the Spanish–English data, we use manually collected web news data. The Russian–English data consist of 553 sentences with 20, 602 words and a single reference translation. The Spanish–English data consist of 414 sentences with 13, 474 words and a single reference translation as well. For the Arabic–English data, we use news wire broadcast data collected for the GALE (Olive et al. Reference Olive, Christianson and McCary2011) project. It consists of 683 sentences with 22, 237 words and four reference translations. In terms of parallel data extraction, we have carried out experiments for a combination of different alignment and link types. For each experiment, we report the number of extracted chunk pairs as well as the number of source and target words in the extracted parallel data. The newly extracted data are added to the baseline parallel data (we have not tried to combine the data from different extraction runs). Including the extracted parallel data leads to a significant improvement over the baseline system in all cases. In addition, when searching for Type III sentence-level alignments, we allow many-to-many links to overlap. This novel concept leads to some small improvements in the BLEU score. In Section 4, the use of overlapping link sequences based on the trace-back array has been explained in more detail.

Table 4.

BLEU scores for Russian–English phrase-based SMT systems trained on the baseline data plus some extracted data (UN or news)

Table 5.

BLEU scores for various Spanish–English phrase-based SMT systems trained on the baseline data plus some extracted data (Gigaword)}

Table 6.

BLEU scores for various Arabic–English phrase-based SMT systems trained on the baseline data plus some extracted data (Gigaword)

For the Russian–English results in Table 4, Types I and II alignments are computed for the UN data. Three different link types are extracted: one-to-one, one-to-many, and many-to-many (as shown in Figure 2) where up to four source sentences are aligned to single target sentence and vice versa. Here, the monotone Type I alignment search results are compared with the Type II search results. The Type II search increases the number of chunk pairs significantly. The additional extracted data improve the BLEU score by about 0.6 per cent only for 1-1 link types (line 2 vs. line 6). Even on the largely monotone UN data, the Type III alignment search actually outperforms the monotonic search types: the document pairs are several thousand sentences long, and some sentence re-ordering cannot be handled by the Type II re-ordering window. On this data, the Type I sub-sentential alignment search yields the best BLEU scores (see line 5). For the sub-sentential search, the allowable maximum length ratio has been increased to 4.0 and the coverage threshold has been reduced to 0.33. On the Russian–English news data (results in line 12–15), the sub-sentential search again yields the best extraction results. We carried out pairwise bootstrap re-sampling to determine whether some of the smaller BLEU differences for different search types are statistically significant. The extraction of sub-sentential fragment pairs improved the BLEU score significantly at the 95 per cent level (line 5 vs. line 9 and line 12 vs. line 13). In addition, the extraction of overlapping links improved the BLEU score significantly at the 95 per cent level as well (line 10 vs. line 11 and line 14 vs. line 15). In addition, on the Russian–English news data, we trained an SMT system on the extracted data only. This lead to only a minor drop in translation quality, as the Russian–English test data were taken from the news domain as well.

For the Spanish–English Gigaword experiments in Table 5, the Type III alignment search with 1-1 links performs best (line 3), followed by the sub-sentential search (line 2). Training a phrase-based system on just the extracted data from line 3 leads to lower BLEU performance of 45.45 (down from 46.14). While still yielding a significant BLEU improvement over just using the baseline data, the Type III alignment search with many-to-many links performs worst on this data. Some improvements are obtained by allowing the many-to-many links to overlap (line 4 vs. line 5). In future, we will try to improve translation results by allowing links to overlap for all the link and alignment types, not just the Type III search with many-to-many links. The Arabic–English Gigaword results in Table 6 also show some small improvement over just using the baseline data. Here, already the baseline training data consist of 8 million parallel sentence pairs with more than 200 million words for both source and target language. Consequently, the overall BLEU gains from including the extracted data are small, and the difference between the alignment and link search types are small as well.