Adrien Lardilleux
email: adrien.lardilleux@limsi.fr

Franc ¸ois Yvon
email: francois.yvon@limsi.fr

Yves Lepage
email: yves.lepage@waseda.jp

Hierarchical Sub-sentential Alignment with Anymalign

We present a sub-sentential alignment algorithm that relies on association scores between words or phrases. This algorithm is inspired by previous work on alignment by recursive binary segmentation and on document clustering. We evaluate the resulting alignments on machine translation tasks and show that we can obtain state-ofthe-art results, with gains up to more than 4 BLEU points compared to previous work, with a method that is simple, independent of the size of the corpus to be aligned, and directly computes symmetric alignments. This work also provides new insights regarding the use of "heuristic" alignment scores in statistical machine translation.

Introduction

Sub-sentential alignment consists in identifying translation units in sentence-aligned parallel corpora, i.e. in texts in which each sentence has been matched with its translation. This task constitutes the first step in the process of training most datadriven machine translation (MT) systems (statistical or example-based). The most prominent approach nowadays is phrase-based statistical machine translation (SMT), where the core model is a translation table derived from sub-sentential mappings. This table consists in a pre-computed list of phrase1 pairs, where each (source, target) pair is associated with a certain number of scores loosely reflecting the likelihood that source translates to target.

The problem of identifying sub-sentential mappings from parallel texts, e.g. between isolated words or n-grams of words, is well-known, and numerous proposals have been put forward to perform this task. Those methods roughly fall into two main categories. On the one hand, the probabilistic approach, introduced by [START_REF] Brown | A statistical approach to language translation[END_REF], considers the problem of identifying links between words or groups of words in parallel sentences. This approach consists in defining a probabilistic model of the parallel corpus, the parameters of which are estimated by a global maximization process which simultaneously considers all possible associations in the corpus. The goal is to determine the best set of alignment links between all source and target words of every parallel sentence pair. The most famous representatives in this category are the IBM models [START_REF] Brown | The mathematics of statistical machine translation: Parameter estimation[END_REF] for aligning isolated words, which have given rise to an impressive series of variants and amendments (see e.g. [START_REF] Vogel | Hmm-based word alignment in statistical translation[END_REF][START_REF] Wu | Stochastic inversion transduction grammar and bilingual parsing of parallel corpora[END_REF][START_REF] Deng | HMM word and phrase alignment for statistical machine translation[END_REF][START_REF] Liang | Alignment by agreement[END_REF][START_REF] Fraser | Getting the structure right for word alignment: LEAF[END_REF][START_REF] Ganchev | Better alignments = better translations?[END_REF], to cite a few). Generalizing word alignment models to phrase alignment proves to be a much more difficult problem, and in the view of work of [START_REF] Marcu | A phrasebased, joint probability model for statistical machine translation[END_REF] and [START_REF] Vogel | PESA: Phrase pair extraction as sentence splitting[END_REF], such alignments are generally produced by heuristically combining asymmetric 1-n word alignments ("oriented") in both directions [START_REF] Koehn | Statistical phrase-based translation[END_REF][START_REF] Denero | Tailoring word alignments to syntactic machine translation[END_REF]. Once the set of alignment links is constituted, it is possible to assign scores to each pair of segments extracted.

On the other hand, associative approaches (also called heuristic by [START_REF] Och | A systematic comparison of various statistical alignment models[END_REF]), were introduced by [START_REF] Gale | Identifying word correspondences in parallel texts[END_REF]. They do not rely on an alignment model: in order to detect translations, they rely on independence statistical measures such as, for instance, Dice coefficient, mutual information [START_REF] Gale | Identifying word correspondences in parallel texts[END_REF][START_REF] Fung | K-vec: A new approach for aligning parallel texts[END_REF], or likelihood ratio [START_REF] Dunning | Accurate methods for the statistics of surprise and coincidence[END_REF]-see also more recent work by [START_REF] Melamed | Models of translational equivalence among words[END_REF] and by [START_REF] Moore | Association-based bilingual word alignment[END_REF]. Computations are generally limited to a list of association candidates precomputed using patterns and filters, for instance, by focusing exclusively on the most frequent word n-grams. In this approach, a local maximisation process is used, where each sentence is processed independently. Alignment links can then be computed, using for instance the greedy algorithm proposed by [START_REF] Melamed | Models of translational equivalence among words[END_REF] (competitive linking).

The probabilistic approach is the most widely used, mainly due to its tight integration with SMT, of which it constitutes a cornerstone since the introduction of IBM models [START_REF] Brown | The mathematics of statistical machine translation: Parameter estimation[END_REF]. The two approaches have shown complementary strengths and weaknesses, as acknowledged by e.g. [START_REF] Johnson | Improving translation quality by discarding most of the phrasetable[END_REF], where phrase associations extracted from word alignments are filtered out according to statistical association measures.

Anymalign, introduced in [START_REF] Lardilleux | Samplingbased multilingual alignment[END_REF]Lardilleux et al., 2011a), aims at extracting sub-sentential associations, addressing a number of issues that are often overlooked. It can process any number of languages simultaneously, it does not make any distinction between source and target, is amenable to massive parallelism, scales easily, and is very simple to implement. Anymalign's association scores have proven to produce better results than state-of-the-art methods on bilingual lexicon constitution tasks (evaluation performed by comparing word associations with reference dictionaries). However, Anymalign's phrase tables are not as good as those obtained with standard methods (evaluation performed with standard MT metrics) (Lardilleux et al., 2011b). One possible explanation for these contrasted results is that, Anymalign does not compute any alignment at the word or at the phrase level; instead, it directly computes translation tables along with their associated scores. Those tables have very different profiles than those obtained with probabilistic methods, mainly in terms of their n-gram distribution [START_REF] Luo | Improving sampling-based alignment by investigating the distribution of n-grams in phrase translation tables[END_REF]. In particular, despite recent improvements (Lardilleux et al., 2011b), the quantity of long n-grams produced remains relatively small compared with Moses's translation tables.

In this paper, we complement Anymalign with a simple alignment algorithm, so as to better understand its current limitations. The resulting alignments improve Anymalign's phrase tables to a point where they can be used to obtain state-of-the art results. In passing, we also propose a computationally cheap way to compute ITG alignments based on arbitrary word level association scores.

The rest of this paper is organized as follows: Section 2 describes the alignment method in detail, Section 3 presents an evaluation on machine translation tasks and an analysis of the results, and Section 4 concludes and discusses further prospects.

Description of the Method

In a nutshell, out method segments pairs of parallel sentences in two parts, linking the two resulting target segments with their proper translation amongst the two source segments (monotonous or inverted translation), and repeats this process recursively on the segment pairs thus obtained.

This work is strongly inspired by that of [START_REF] Wu | Stochastic inversion transduction grammar and bilingual parsing of parallel corpora[END_REF] and [START_REF] Deng | Segmentation and alignment of parallel text for statistical machine translation[END_REF]. The former introduces inversion transduction grammars, which generate synchronized binary parse trees in source and target languages. This formalism models both variable-length associations at leaf (terminal) nodes, and reorderings (inversions) at any level of the parse tree. As we are only interested in computing alignment based on arbitrary lexical association scores, we will dispense here from using the full apparatus of stochastic grammars, yielding algorithms that are computationally much cheaper. The latter uses a similar concept, where more or less coarse bisegments are extracted from non-sentence-aligned parallel texts by iteratively recursively applying a top-down binary segmentation algorithm. We reproduce the same approach here at the sentence level, using different local association scores.

Alignment Matrix

Our starting point are (1) a sentence-aligned bitext; and (2) a function w measuring the strength of the translation link between any source and target pair of words. Several definitions of w are possible; it is nevertheless natural to define it endogenously from word occurrences in the bitext. The scores we will first use will be obtained using Anymalign's output. We will see later that they lead to better results than scores obtained using other standard measures.

In the following, the score w(s,t) between a source word s and a target word t is defined as the product of the two translation probabilities p(s|t) × p(t|s), produced by Anymalign: 17,717 + 4,057 + 2,007 151,190 + 17,717 + 10,865 + 6,284 + 4,057 + 3,742 + 2,007 × 17,717 + 4,057 + 2,007 17,717 + 4,057 + 2,007 + 122 0.121 Figure 1: Computing a score between source word pays and target word country from a subset of a translation table produced by Anymalign with the French and English parts of the Europarl corpus [START_REF] Koehn | Europarl: A parallel corpus for statistical machine translation[END_REF].

w(s, c) = p(s|t) × p(t|s) = ∑ N n=1 [ [(s,t)∈(S n ,T n )] ]k n ∑ N n =1 [ [s∈S n ] ]k n × ∑ N n=1 [ [(s,t)∈(S n ,T n )] ]k n ∑ N n =1 [ [t∈T n ] ]k n = (∑ N n=1 [ [(s,t)∈(S n ,T n )] ]k n) 2 (∑ N n =1 [ [s∈S n ] ]k n )×(∑ N n =1 [ [t∈T n ] ]k n ) where: • [[x]] = 1 if x is true, 0 otherwise; • N
an indicator of the quality of the entry; it is just the number of times the translation pair has been produced by Anymalign (see (Lardilleux et al., 2011a) for details).

This computation is illustrated on Figure 1.

What we do here is tantamount to a very simplified version of the algorithm that is used to train standard translation models: starting with lexical associations, we derive by heuristic means an optimal (Viterbi) alignment, from which the translation tables are finally computed. Our procedure is much simpler, though, as we do not iterate the procedure (like in EM training) and directly manipulate symmetric representations at the phrase level.

Segmentation Criterion

The segmentation criterion described hereafter is inspired by the work of [START_REF] Zha | Bipartite graph partitioning and data clustering[END_REF] on document clustering. Their problem consists in computing the optimal joint clustering of a bipartite graph representing occurrences of terms inside a set of documents. We adapt it to the search of the best alignment between words of a source sentence and those of a target sentence.

To this end, we consider a pair of sentences (S, T ) from the parallel corpus, where the source sentence S is made up of I source words and the target sentence T is made up of J target words: S = [s 1 . . . s I ] and T = [t 1 . . .t J ]. Moreover, we consider "split" indices x and y which define a binary segmentation of the source and target sentences (the "." symbol refers to the concatenation of word strings): The choice of x and y will be guided by the sum W of the association scores between each source and target words of a block (X,Y ) ∈ {A, Ā} × {B, B}:

S = A. Ā with A = [s 1 . . . s x-1 ] and Ā = [s x . . . s I ] T = B. B with B = [t 1 . . .t y-1 ] and B = [t y . . .t J ] B B t 1 . . . t y-1 t y . . . t J s 1 A . . . W (A, B) W (A, B) s x-1 s x Ā . . . W ( Ā, B) W ( Ā, B) s I
W (X,Y ) = ∑ s∈X,t∈Y w(s,t)
These notations are summarized in Fig. 2.

Then, we define the total score of a segmentation:

cut(X,Y ) = W (X, Ȳ ) +W ( X,Y ) Note that cut(X,Y ) = cut( X, Ȳ ).
In our case, a low value indicates that the association scores between the words of X and that of Ȳ on the one hand, and between the words of X and that of Y on the other hand, are low; in other words, those two blocks are unlikely to correspond to good translations, contrarily to (X,Y ) and ( X, Ȳ ). We would thus like to identify the pair (x, y) that leads to the lowest possible value of cut(X,Y ).

As pointed out by [START_REF] Zha | Bipartite graph partitioning and data clustering[END_REF], this quantity tends to produce unbalanced segments (document clusters in their case) because of the absence of normalisation, which warrants its replacement by:

Ncut(X,Y ) = cut(X,Y ) cut(X,Y )+2×W (X,Y ) + cut( X, Ȳ ) cut( X, Ȳ )+2×W ( X, Ȳ )
This variant adds a density constraint on (X,Y ) and ( X, Ȳ ), which is partially satisfied by the introduction of the denominators in the above expression. Its values are in the range [0, 2].

Our problem eventually consists in determining the pair (x, y) that minimizes Ncut. Although efficient search methods exist and are commonly used in graph theory, our "graphs" (pairs of sentences) are small in practice: about 30 words per sentence in average in the Europarl corpus used in the following experiments. We thus content ourselves with determining the best segmentation through an exhaustive enumeration.

Alignment Algorithm

We can now recursively segment and align a pair of sentences. At each step, we test every possible pair (x, y) of indices in order to determine procedure align(S, T ) :

if length(S) = 1 or length(T ) = 1 : link each word of S to each word of T stop procedure the lowest Ncut. The worst case happens when the matrix is cut in the most unbalanced possible way; the complexity of the algorithm is thus cubic (O(I × J × min(I, J))) in the length of the input sentences. Using a greedy strategy only delivers suboptimal solutions, yet it does so much faster than exact ITG parsing, which is cubic in the product I × J [START_REF] Wu | Stochastic inversion transduction grammar and bilingual parsing of parallel corpora[END_REF]. For a given pair (x, y), two values are computed: one corresponds to a monotonous alignment (Ncut(A, B)) and the other one to an inversion of the two segments (Ncut(A, B)). We then apply the process recursively on each of the two segment pairs that correspond to the minimal Ncut. It ends when one of the segments contains only one word and produces 1-n or n-1 alignments. In this approach, all words are aligned. By considering different stopping criteria, eg. based on thresholds on Ncut, variants of the algorithm are readily obtained, which enable to balance the granularity of the alignment its precision, by choosing to build larger and safer blocks (m-n alignments) instead of smaller and less sure ones. We leave this for future work. Figure 3 presents the complete algorithm, and Fig. 4 illustrates the process on two actual examples. In the following, we refer to this algorithm under the name of "Cutnalign."

minNcut = 2 (X,Y ) = (S, T ) for each (i, j) ∈ {2 . . . I} × {2 . . . J} : if Ncut(A, B) < minNcut : minNcut = Ncut(A, B) (X,Y ) = (A, B) if Ncut(A, B < minNcut : minNcut = Ncut(A, B) (X,Y ) = (A, B) align(X,Y ) align( X, Ȳ )
The algorithm itself is independent of the size of the parallel corpus to align, because each sentence pair is processed independently. Aligning a corpus can thus easily be made parallel: the total running time is divided by the number of available processors. Another advantage is that the alignments produced are symmetric during the whole process, contrary to more widely spread models such as IBM models that produce better result when run in both translation directions and their outputs combined using heuristics.

Evaluation

Description of Experiments

Our alignment method is evaluated within a phrase-based SMT system. We use the Moses toolkit [START_REF] Koehn | Moses: Open source toolkit for statistical machine translation[END_REF], and data extracted from the Europarl corpus [START_REF] Koehn | Europarl: A parallel corpus for statistical machine translation[END_REF], in three languages: Finnish-English (agglutinating language-isolating language), French-Spanish, and Portuguese-Spanish (very close languages). For each pair, we use a training set made up of 350,000 sentence pairs (avg.: 30 words/sentence in English), and development and test sets made up of 2,000 sentence pairs each. The systems are optimized with MERT [START_REF] Och | Minimum error rate training in statistical machine translation[END_REF]. Unless otherwise specified, a lexicalized reordering model is used. Translations are evaluated using BLEU [START_REF] Papineni | BLEU: a method for automatic evaluation of machine translation[END_REF] and TER2 [START_REF] Snover | A study of translation edit rate with targeted human annotation[END_REF].

Five approaches are compared:

MGIZA++ [START_REF] Gao | Parallel implementations of word alignment tool[END_REF], implements the IBM models [START_REF] Brown | The mathematics of statistical machine translation: Parameter estimation[END_REF] and the HMM of [START_REF] Vogel | Hmm-based word alignment in statistical translation[END_REF]. Integrated to Moses, it remains the reference in the domain. It is run with default settings: 5 iterations of IBM1, HMM, IBM3, and IBM4, in both directions (source to target and target to source). The alignments are then made symmetric and a translation table is produced from the alignments using Moses tools (grow-diag-finaland heuristic for phrase pair extraction).

Anymalign (Lardilleux et al., 2011a), used to directly build the translation tables. As this tool can be stopped at any time, its running time is set so that it runs for the same duration as MGIZA++. The same experiment is repeated by varying the length of output phrases from 1 to 4 (see (Lardilleux et al., 2011b) for details). In the following, we refer to it under the names "Anymalign-1" to "Anymalign-4."

The reordering model used in this configuration is a simple distance-based model, because Anymalign alone cannot provide the information required for a lexicalized reordering model.

Anymalign + Cutnalign: we apply the algorithm described in previous section to each of the four translation tables produced by Anymalign-1 to Anymalign-4. Although every intermediary segmentation step (all possible rectangles in Fig. 4) actually corresponds to a phrase pair that could be extracted and fit in a phrase-table, in our experiments, we only rely on terminal alignment points, that are then passed to the Moses toolkit to build new translation tables (using again the grow-diag-final-and the level of budgetary implementation ; le 0.037 ε 0.001

ε ε ε niveau ε 0.591 ε ε ε ε d' ε ε 0.003 ε ε ε exécution ε ε ε ε 0.060 ε budgétaire ε ε ε 0.659 ε ε ; ε ε ε ε ε 0.287
finally , what our fellow citizens are demanding is the right to information . enfin 0.607 0.001

ε ε 0 ε ε 0 ε ε ε ε ε ε , 0.001 0.445 ε ε ε ε ε ε ε 0.001 ε 0.001 ε 0.001 c' ε ε 0.001 ε ε ε ε 0 0.036 0.001 ε ε ε ε est ε ε 0.001 ε ε ε ε 0 0.223 0.016 ε 0.001 ε 0.001 un ε ε ε ε ε ε ε ε 0.005 ε ε ε ε ε droit ε ε ε ε ε ε ε 0 ε ε 0.084 ε ε ε à ε ε ε ε ε ε 0.001 ε 0.001 0.003 0.001 0.018 ε ε l' ε ε ε ε ε ε ε ε 0.002 0.009 ε 0.002 ε ε information ε ε ε ε ε ε ε ε ε ε ε ε 0.499 ε que ε ε 0.002 ε ε ε 0.001 ε 0.002 0.001 ε 0.001 ε ε réclament 0 0 ε ε ε ε ε 0.152 ε ε 0 0 0 ε nos ε ε ε 0.171 0.004 0.001 ε ε ε ε ε ε ε ε concitoyens 0 ε ε 0.001 0.323 0.009 ε ε ε ε 0 ε 0 ε . ε ε ε ε ε ε ε ε 0.001 0.001 ε ε ε 0.954
Figure 4: Two examples of segmentation-alignment. The number in each cell corresponds to the value of the function w, with 0 < ε ≤ 0.001. A null value indicates that the two words never appear together in the translation table. Alignment points retained by the algorithm, i.e. at maximum level of recursion, are in boldface. In the first example, the translation is monotonous except for the name/adjective inversion (exécution budgétaire/budgetary implementation), therefore most alignment links are along the diagonal.

The second example, more complex, attests for the inversion of propositions inside the sentence.

heuristic). This approach yields more phrase pairs as it allows to extract together segments on both sides of a split point, e.g. le niveau/the level.

Simple probabilities + Cutnalign: the purpose of this configuration is to evaluate the choice of w, rather than the algorithm itself. To this end, we use a very simple association score: the probability that a source word and a target word are translations of one another (product of the two translation probabilities), where this probability is computed from their co-occurrence counts over the training corpus. The definition of w is thus the same as in Sec. 2.1, with two minor differences: (1) counts are directly computed over the training bitext; and

(2) k n = 1, ∀n.

Anymalign + Cutnalign / MGIZA++: This is a combination of the MGIZA++ and Anyma-lign+Cutnalign approaches. We do this by taking the union of the two alignment sets. In pratice, we simply concatenate the two alignment files produced by the aligners, and duplicate the training bicorpus so that we end up with a new, twice as large, training bicorpus and alignment file, from which the phrase table is extracted.

In terms of runtime, although Cutnalign is currently implemented in a high-level programming language (Python) and its complexity is cubic in the length of the sentence pairs to process, the fact that each sentence pair can be aligned independently makes it amenable to massive parallelism if numerous CPUs are available.

Results

Results are in Table 1. For each task, using the basic version of Anymalign yields worse scores than MGIZA++-based system, even though extending the phrase length reduces this gap by roughly a half, except for the Finnish-English pair. Those results are in line with (Lardilleux et al., 2011b).

Cutnalign leads to significant gains in all configurations: from 1.6 to 4.6 BLEU points (fr-en, Anymalign-1 + Cutnalign), with an average gain of 2.6 BLEU and 2.7 TER points. Anymalign + Cutnalign is still 1.1 to 1.6 BLEU points below in Finnish-English relatively to MGIZA++ but produces results of comparable quality in French-English and Portuguese-Spanish.

The "simple probabilities + Cutnalign" configuration produces intermediary quality results, generally between "basic" Anymalign and Anymalign + Cutnalign. This shows that the function w has a significant impact on the behavior of the alignment method. Assuming the function used in these experiments is one of the simplest possible, there is ample room here for improvements. Merging both phrase tables is almost always the best strategy, at the most of much larger models.

Analysis of Alignments

One motivation for proposing this new alignment method is that Anymalign still lacks the ability to extract long n-gram translations in sufficient quantity. In this section, we study some characteristics of the alignments thus produced (see Table 1).

Regarding translation tables first, we observe that those obtained from Cutnalign contain many more entries than those produced by Anymalign alone3 (three times more in average), except for Anymalign-1 in Finnish-English. Nevertheless, they are still much smaller than tables obtained from MGIZA++, as they contain twice less entries in average. In addition, the average length of those entries is almost equal to that of those in MGIZA++'s translation tables, while those produced by Anymalign are much shorter: producing a translation table from alignment links allows to make up for the lack of long n-grams as desired.

Secondly, we study the alignment links themselves. The column "Links" of Table 1 shows that our method produces more alignment links than MGIZA++: between 1.5 and 3 times more, depending on the task. The last column gives the main reason: alignment blocks extracted by our method, i.e. rectangles obtained at maximal recursion depth, are always longer than minimum blocks obtained from MGIZA++'s alignments (+ 26% in average). Since we systematically align all source words with all target words in such a rectangle, and since all words of a sentence pair are therefore necessarily aligned, the total number of alignments produced is naturally high. This also explains the fact that the number of entries in our translation tables is always much lower than those obtained from MGIZA++, as the latter produces 0-1 alignments that are at the origin of numerous phrases extracted during the constitution of the table by Moses (grow-diag-finaland heuristic by default) [START_REF] Ayan | Going beyond AER: An extensive analysis of word alignments and their impact on MT[END_REF]. Despite this, alignments produced by our method lead to state-of-the-art scores in two machine translation tasks over three in our experiments.

Conclusion

We have presented a sub-sentential alignment method based on a recursive binary segmentation process of the alignment matrix between a source sentence and its translation. Inspired by work on alignment by [START_REF] Wu | Stochastic inversion transduction grammar and bilingual parsing of parallel corpora[END_REF] and [START_REF] Deng | Segmentation and alignment of parallel text for statistical machine translation[END_REF] and work on document clustering by [START_REF] Zha | Bipartite graph partitioning and data clustering[END_REF], we have shown that despite its simplicity, this method leads to state-of-the-art results in two tasks over three in our experiments. When fed with Anymalign's scores, it yields significant gains (up to 4.6 BLEU points in French-English) in comparison with Anymalign alone. These experiments confirm that Anymalign's main handicap concerns the translation of long n-grams. A complementary alignment step, strictly speaking, is thus desired in order to improve its results in machine translation. The alignment method proposed here is simple, symmetric with respect to the translation direction, and the use of local computations makes it scale up easily. Many improvements are possible, amongst which the use of early stopping criteria during segmentation of the alignment matrix so as to trade alignment granularity for confidence; the use more sophisticated metrics for scoring blocks, or the exploration of richer (e.g. ternary) segmentation schemes, enabling to account for more complex linguistic constructs.

Figure 2 :

 2 Figure 2: Schematic representation of the segmentation of a pair of sentences S = A. Ā and T = B. B.

Figure 3 :

 3 Figure 3: Recursive alignment algorithm.

Table 1 :

 1 Summary of results obtained in our experiments. The first two columns (BLEU and TER) report performance in machine translation. The two middle columns diplay various characteristics of the translation tables: the number of entries and their length in words. The last two columns present characteristics of the alignments prior to the production of the translation table: average number of alignment links per training sentence pair and average length of the source part of minimal blocks extracted (translations of the phrases that are consistent with word alignments).

	Task	System	BLEU (%)	TER (%)	Entries (millions)	Length of entries	Links	Length of extracted blocks
	MGIZA++		22.27 62.92	22.2	3.24	26	1.16
	Anymalign-1		18.68 67.30	11.8	1.87
	Anymalign-2		17.86 68.60	4.4	2.09
	Anymalign-3		18.06 68.13	3.0	2.32
	Anymalign-4		18.06 68.53	2.1	2.42
	Anymalign-1 + Cutnalign	21.14 63.74	7.7	3.26	62	1.45
	fi-en Anymalign-2 + Cutnalign	21.14 64.69	7.5	3.27	69	1.48
	Anymalign-3 + Cutnalign	20.83 64.18	7.3	3.29	73	1.50
	Anymalign-4 + Cutnalign	20.64 64.52	7.1	3.29	78	1.53
	Simple prob. + Cutnalign	19.09 67.09	5.5	3.23	74	1.78
	Anymalign-1 + Cutnalign / MGIZA++ 22.66 62.45	27.0	3.24	44	1.30
	Anymalign-2 + Cutnalign / MGIZA++ 22.68 62.91	26.9	3.24	47	1.31
	Anymalign-3 + Cutnalign / MGIZA++ 22.73 62.82	26.8	3.24	49	1.32
	Anymalign-4 + Cutnalign / MGIZA++ 22.78 62.11	26.7	3.24	52	1.33
	MGIZA++		29.65 55.25	25.6	4.29	31	1.17
	Anymalign-1		25.10 59.36	6.1	1.27
	Anymalign-2		26.60 58.16	6.3	1.99
	Anymalign-3		27.02 57.96	3.9	2.29
	Anymalign-4		26.85 58.00	2.6	2.42
	Anymalign-1 + Cutnalign	29.65 55.22	12.9	4.21	50	1.49
	fr-en Anymalign-2 + Cutnalign	29.69 55.44	13.1	4.22	48	1.48
	Anymalign-3 + Cutnalign	29.26 55.49	13.0	4.23	50	1.49
	Anymalign-4 + Cutnalign	29.16 55.46	12.8	4.23	52	1.51
	Simple prob. + Cutnalign	27.97 56.85	10.2	3.95	54	1.62
	Anymalign-1 + Cutnalign / MGIZA++ 30.02 54.81	31.9	4.24	41	1.32
	Anymalign-2 + Cutnalign / MGIZA++ 29.91 54.88	31.9	4.24	40	1.32
	Anymalign-3 + Cutnalign / MGIZA++ 30.22 54.94	31.9	4.24	41	1.32
	Anymalign-4 + Cutnalign / MGIZA++ 29.91 54.87	31.8	4.24	42	1.33
	MGIZA++		38.53 48.46	32.2	4.30	30	1.09
	Anymalign-1		35.20 50.89	5.7	1.26
	Anymalign-2		36.80 49.60	5.9	1.99
	Anymalign-3		36.82 49.67	3.7	2.26
	Anymalign-4		36.96 49.80	2.4	2.37
		+ Cutnalign	37.35 49.55	17.9	4.30	50	1.32
	pt-es Anymalign-2 + Cutnalign	38.96 48.04	18.0	4.30	48	1.32
	Anymalign-3 + Cutnalign	38.55 48.40	17.7	4.31	50	1.33
	Anymalign-4 + Cutnalign	38.56 48.37	17.3	4.31	54	1.35
	Simple prob. + Cutnalign	37.71 49.04	13.9	4.09	50	1.41
	Anymalign-1 + Cutnalign / MGIZA++ 38.77 48.12	37.7	4.25	40	1.20
	Anymalign-2 + Cutnalign / MGIZA++ 38.69 48.39	37.9	4.25	39	1.20
	Anymalign-3 + Cutnalign / MGIZA++ 38.94 48.12	37.8	4.25	40	1.20
	Anymalign-4 + Cutnalign / MGIZA++ 38.82 48.18	37.8	4.25	42	1.21

In this context, a phrase is a sequence of words and does not necessarily correspond to a syntactic phrase.

Proceedings of the 16thEAMT Conference, 28-30 May 2012, Trento, Italy

Contrary to BLEU, lower scores are better.

These tables were produced by running Anymalign for an identical amount of time in all configurations, which explains why larger values of the length parameter lead to smaller tables-see details in(Lardilleux et al., 2011b).