Non-projective parsing for statistical machine translation

Non-Projective Parsing for Statistical Machine Translation Xavier Carreras Michael Collins MIT CSAIL, Cambridge, MA 02139, USA {carreras,mcollins}@csail.mit.edu Abstract We describe a novel approach for syntaxbased statistical MT, which builds on a variant of tree adjoining grammar (TAG). Inspired by work in discriminative dependency parsing, the key idea in our approach is to allow highly flexible reordering operations during parsing, in combination with a discriminative model that can condition on rich features of the sourcelanguage string. Experiments on translation from German to English show improvements over phrase-based systems, both in terms of BLEU scores and in human evaluations. 1 Introduction Syntax-based models for statistical machine translation (SMT) have recently shown impressive results; many such approaches are based on either synchronous grammars (e.g., (Chiang, 2005)), or tree transducers (e.g., (Marcu et al., 2006)). This paper describes an alternative approach for syntax-based SMT,which directly leverages methods from non-projective dependency parsing. The key idea in our approach is to allow highly flexible reordering operations, in combination with a discriminative model that can condition on rich features of the source-language input string. Our approach builds on a variant of tree adjoining grammar (TAG; (Joshi and Schabes, 1997)) (specifically, the formalism of (Carreras et al., 2008)). The models we describe make use of phrasal entries augmented with subtrees that provide syntactic information in the target language. As one example, when translating the sentence wir m¨ ussen auch diese kritik ernst nehmen from German into English, the following sequence of syntactic phrasal entries might be used (we show each English syntactic fragment above its associated German sub-string): S NP we VP must ADVP also NP these criticisms ADVP seriously VP take wir m¨ussen auch diese kritik ernst nehmen TAG parsing operations are then used to combine these fragments into a full parse tree, giving the final English translation we must also take these criticisms seriously. Some key aspects of our approach are as follows: •We impose no constraints on entries in the phrasal lexicon. The method thereby retains the full set of lexical entries of phrase-based systems (e.g., (Koehn et al., 2003)).1 •The model allows a straightforward integration of lexicalized syntactic language models—for example the models of (Charniak, 2001)—in addition to a surface language model. •The operations used to combine tree fragments into a complete parse tree are significant generalizations of standard parsing operations found in TAG; specifically, they are modified to be highly flexible, potentially allowing any possible permutation (reordering) of the initial fragments. As one example of the type of parsing operations that we will consider, we might allow the tree fragments shown above for these criticisms and take to be combined to form a new structure with the sub-string take these criticisms. This step in the derivation is necessary to achieve the correct English word order, and is novel in a couple of respects: first, these criticisms is initially seen to the left of take, but after the adjunction this order is reversed; second, and more unusually, the treelet for seriously has been skipped over, with the result that the German words translated at this point (diese,kritik, and nehmen) form a non-contiguous sequence. More generally, we will allow any two 1Note that in the above example each English phrase consists of a completely connected syntactic structure; this is not, however, a required constraint, see section 3.2 for discussion. tree fragments to be combined during the translation process, irrespective of the reorderings which are introduced, or the non-projectivity of the parsing operations that are required. The use of flexible parsing operations raises two challenges that will be a major focus of this paper. First, these operations will allow the model to capture complex reordering phenomena, but will in addition introduce many spurious possibilities. Inspired by work in discriminative dependency parsing (e.g., (McDonald et al., 2005)), we add probabilistic constraints to the model through a discriminative model that links lexical dependencies inthe target language to features of the source language string. We also investigate hard constraints on the dependency structures that are created during parsing. Second, there is a need to develop efficient decoding algorithms for the models. We describe approximate search methods that involve a significant extension of decoding algorithms originally developed for phrase-based translation systems. Experiments on translation from German to English show a 0.5% improvement in BLEU score over a phrase-based system. Human evaluations show that the syntax-based system gives a significant improvement over the phrase-based system. The discriminative dependency model gives a 1.5% BLEU point improvement over a basic model that does not condition on the source language string; the hard constraints on dependency structures give a 0.8% BLEU improvement. 2 Relationship to Previous Work A number of syntax-based translation systems have framed translation as a parsing problem, where search for the most probable translation is achieved using algorithms that are generalizations of conventional parsing methods. Early examples of this work include (Alshawi, 1996; Wu, 1997); more recent models include (Yamada and Knight, 2001; Eisner, 2003; Melamed, 2004; Zhang and Gildea, 2005; Chiang, 2005; Quirk et al., 2005; Marcu et al., 2006; Zollmann and Venugopal, 2006; Nesson et al., 2006; Cherry, 2008; Mi et al., 2008; Shen et al., 2008). The majority of these methods make use of synchronous grammars, or tree transducers, which operate over parse trees in the source and/or target languages. Reordering rules are typically specified through rotations or transductions stated at the level of contextfree rules, or larger fragments, within parse trees. These rules can be learned automatically from corpora. A critical difference in our work is to allow arbitrary reorderings of the source language sentence (as in phrase-based systems), through the use of flexible parsing operations. Rather than stating reordering rules at the level of source or target language parse trees, we capture reordering phenomena using a discriminative dependency model. Other factors that distinguish us from previous work are the use of all phrases proposed by a phrase-based system, and the use of a dependency language model that also incorporates constituent information (although see (Charniak et al., 2003; Shen et al., 2008) for related approaches). 3 A Syntactic Translation Model 3.1 Background Our work builds on the variant of tree adjoining grammar (TAG) introduced by (Carreras et al., 2008). In this formalism the basic units in the grammar are spines, which associate tree fragments with lexical items. These spines can be combined using a sister-adjunction operation (Rambow et al., 1995), to form larger pieces of structure.2For example, we might have the following operation: NP there S VP is ⇒S NP there VP is In this case the spine for there has sister-adjoined into the Snode in the spine for is; we refer to the spine for there as being the modifier spine, and the spine for is being the head spine. There are close connections to dependency formalisms: in particular in this operation we see a lexical dependency between the modifier word there and the head word is. It is possible to define syntactic language models, similar to (Charniak, 2001), which associate probabilities with these dependencies, roughly speaking of the form P(wm, sm|wh, sh, pos, σ), where wmand smare the identities of the modifier word and spine, wh and share the identities of the head word and spine, pos is the position in the head spine that is being adjoined into, and σis some additional state (e.g., state that tracks previous modifiers that have adjoined into the same spine). 2We also make use of the r-adjunction operation defined in (Carreras et al., 2008), which, together with sister-adjunction, allows us to model the full range of structures found in the Penn treebank. S NP there VP is NP NPB no hierarchy PP of NP discrimination es gibt keine hierarchie der diskriminierung Figure 1: A training example consisting of an English (target language) tree and a German (source language) sentence. In this paper we will also consider treelets, which are a generalization of spines, and which allow lexical entries that include more than one word. These treelets can again be combined using a sister-adjunction operation. As an example, consider the following operation: VP be ADJP able SG to VP respond ⇒VP be ADJP able SG to VP respond In this case the treelet for to respond sister-adjoins into the treelet for be able. This operation introduces a bi-lexical dependency between the modifier word to and the head word able. 3.2 S-phrases This section describes how phrase entries from phrase-based translation systems can be modified to include associated English syntactic structures. These syntactic phrase-entries (from here on referred to as “s-phrases”) will form the basis of the translation models that we describe. We extract s-phrases from training examples consisting of a source-language string paired with a target-language parse tree. For example, consider the training example in figure 1. We assume some method that enumerates a set of possible phrase entries for each training example: each phrase entry is a pair h(i, j),(k, l)ispecifying that source-language words fi. . . fjcorrespond to target-language words ek. . . elin the example. For example, one phrase entry for the example might be h(1,2),(1,2)i, representing the pair hes gibt ⇒there isi. In our experiments we use standard methods in phrase-based systems (Koehn et al., 2003) to define the set of phrase entries for each sentence in training data. es gibt keine hierarchie der S NP there VP is DT no NP NPB hierarchy PP of Figure 2: Example syntactic phrase entries. We show German sub-strings above their associated sequence of treelets.4 For each phrase entry, we add syntactic information to the English string. To continue our example, the resulting entry would be as follows: es gibt ⇒S NP there VP is To give a more formal description of how syntactic structures are derived for phrases, first note that each parse tree tis mapped to a TAG derivation using the method described in (Carreras et al., 2008). This procedure uses the head finding rules of (Collins, 1997). The resulting derivation consists of a TAG spine for each word seen in the sentence, together with a set of adjunction operations which each involve a modifier spine and a head spine. Given an English string e=e1. . . en, with an associated parse tree t, the syntactic structure associated with a substring ek. . . el(e.g., there is) is then defined as follows: •For each word in the English sub-string, include its associated TAG spine in t. •In addition, include any adjunction operations in twhere both the head and modifier word are in the sub-string ej. . . ek. In the above example, the resulting structure (i.e., the structure for there is) is a single treelet. In other cases, however, we may get a sequence of treelets, which are disconnected from each other. For example, another likely phrase-entry for this training example is hes gibt keine ⇒there is noi resulting in the first lexical entry in figure 2, which has two treelets. Allowing s-phrases with multiple treelets ensures that all phrases used by phrasebased systems can be used within our approach. As a final step, we add additional alignment information to each s-phrase. Consider an s-phrase which contains source-language words f1. . . fnpaired with target-language words e1. . . em. The alignment information is a vector h(a1, b1)...(am, bm)ithat specifies for each word eiits alignment to words fai. . . fbiin the source language. For example, for the phrase en- try hes gibt ⇒there isia correct alignment would be h(1,1),(2,2)i, specifying that there is aligned to es, and is is aligned to gibt (note that in many, but not all, cases ai=bi, i.e., a target language word is aligned to a single source language word). The alignment information in s-phrases will be useful in tying syntactic dependencies created in the target language to positions in the source language string. In particular, we will consider discriminative models (analogous to models for dependency parsing, e.g., see (McDonald et al., 2005)) that estimate the probability of targetlanguage dependencies conditioned on properties of the source-language string. Alignments may be derived in a number of ways; in our method we directly use phrase entries proposed by a phrasebased system. Specifically, for each target word ei in a phrase entry hf1. . . fn, e1. . . emifor a training example, we find the smallest5phrase entry in the same training example that includes eion the target side, and is a subset of f1. . . fnon the source side; the word eiis then aligned to the subset of source language words in this “minimal” phrase. In conclusion, s-phrases are defined as follows: Definition 1 An s-phrase is a 4-tuple hf, e, t, ai where: fis a sequence of foreign words; eis a sequence of English words; tis a sequence of treelets specifying a TAG spine for each English word, and potentially some adjunctions between these spines; and ais an alignment. For an sphrase qwe will sometimes refer to the 4 elements of qas f(q),e(q),t(q)and a(q). 3.3 The Model We now introduce a model that makes use of sphrases, and which is flexible in the reorderings that it allows. To provide some intuition, and some motivation for the use of reordering operations, figure 3 gives several examples of German strings which have different word orders from English. The crucial idea will be to use TAG adjunction operations to combine treelets to form a complete parse tree, but with a complete relaxation on the order in which the treelets are combined. For example, consider again the example given in the introduction to this paper. In the first step of a derivation that builds on these treelets, the treelet 5The “size” of a phrase entry is defined to be ns+nt where nsis the number of source language words in the phrase, ntis the number of target language words. 1(a) [die verwaltung] [muss] [k¨unftig] [schneller] [reagieren] [k¨onnen] 1(b) the administration must be able to respond more quickly in future 1(c) NP the admin. . . S VP must PP in future ADVP more quickly SG to VP respond VP be ADJP able 2(a) [meiner ansicht nach] [darf] [der erweiterungsprozess] [nicht] [unn¨otig] [verz¨ogert] [werden] 2(b) in my opinion the expansion process should not be delayed unnecessarily 2(c) PP in my opinion S VP should NP the . . . process RB not ADVP unnecessarily VP delayed VP be Figure 3: Examples of translations. In each example (a) is the original German string, with a possible segmentation marked with “[“ and “]”; (b) is a translation for (a); and (c) is a sequence of phrase entries, including syntactic structures, for the segmentation given in (a). for these criticisms might adjoin into the treelet for take, giving the following new sequence: S NP we VP must ADVP also ADVP seriously VP V take NP these criticisms In the next derivation step seriously is adjoined to the right of take, giving the following treelets: S NP we VP must ADVP also VP V take NP these criticisms ADVP seriously In the final step the second treelet adjoins into the VP above must, giving a parse tree for the string we must also take these criticisms seriously, and completing the translation. Formally, given an input sentence f, a derivation dis a pair hq, πiwhere: •q=q1. . . qnis a sequence of s-phrases such that f=f(q1)⊕f(q2)⊕...⊕f(qn)(where u⊕v denotes the concatenation of strings uand v). •πis a set of adjunction operations that connects the sequence of treelets contained in ht(q1), t(q2),...,t(qn)iinto a parse tree in the target language. The operations allow a complete relaxation of word order, potentially allowing any of the n!possible orderings of the nsphrases. We make use of both sister-adjunction and r-adjunction operations, as defined in (Carreras et al., 2008).6 6In principle we allow any treelet to adjoin into any other treelet—for example there are no hard, grammar-based constraints ruling out the combination of certain pairs of nonterminals. Note however that in some cases operations will have probability 0under the syntactic language model introduced later in this section. DT no NP NPB hierarchy PP of NP discrimination ⇒NP NPB hierarchy PP of NP DT no discrimination Figure 4: A spurious derivation step. The treelets arise from [keine] [hierarchie der] [diskriminierung]. Given a derivation d=hq, πi, we define e(d) to be the target-language string defined by the derivation, and t(d)to be the complete targetlanguage parse tree created by the derivation. The most likely derivation for a foreign sentence f is arg maxd∈G(f)score(d), where G(f)is the set of possible derivations for f, and the score for a derivation is defined as7 score(d) = scoreLM (e(d)) + scoreSY N (t(d)) +scoreR(d) + n X j=1 scoreP(qj)(1) The components of the model are as follows: •scoreLM (e(d)) is the log probability of the English string under a trigram language model. •scoreSY N (t(d)) is the log probability of the English parse tree under a syntactic language model, similar to (Charniak, 2001), that associates probabilities with lexical dependencies. •scoreR(d)will be used to score the parsing operations in π, based on the source-language string and the alignments in the s-phrases. This part of the model is described extensively in section 4.1 of this paper. •scoreP(q)is the score for an s-phrase q. This score is a log-linear combination of various features, including features that are commonly found in phrase-based systems: for example log P(f(q)|e(q)),log P(e(q)|f(q)), and lexical translation probabilities. In addition, we include a feature log P(t(q)|f(q), e(q)), which captures the probability of the phrase in question having the syntactic structure t(q). Note that a model that includes the terms scoreLM (e(d)) and Pn j=1 scoreP(qj)alone would essentially be a basic phrase-based model (with no distortion terms). The terms scoreSY N (t(d)) and scoreR(d)add syntactic information to this basic model. A key motivation for this model is the flexibility of the reordering operations that it allows. However, the approach raises two major challenges: 7In practice, MERT training (Och, 2003) will be used to train relative weights for the different model components. Constraints on reorderings. Relaxing the operations in the parsing model will allow complex reorderings to be captured, but will also introduce many spurious possibilities. As one example, consider the derivation step shown in figure 4. This step may receive a high probability from a syntactic or surface language model—no discrimination is a quite plausible NP in English—but it should be ruled out for other reasons, for example because it does not respect the dependencies in the original German (i.e., keine/no is not a modifier to diskriminierung/discrimination in the German string). The challenge will be to develop either hard constraints which rule out spurious derivation steps such as these, or soft constraints, encapsulated in scoreR(d), which penalize them. Efficient search. Exact search for the derivation which maximizes the score in Eq. 1 cannot be accomplished efficiently using dynamic programming (as in phrase-based systems, it is easy to show that the decoding problem is NP-complete). Approximate search methods will be needed. The next two sections of this paper describe solutions to these two challenges. 4 Constraints on Reorderings 4.1 A Discriminative Dependency Model We now describe the model scoreRintroduced in the previous section. Recall that πspecifies kadjunction operations that are used to build a full parse tree, where k≥nis the number of treelets within the sequence of s-phrases q=hq1. . . qni. Each of the kadjunction operations creates a dependency between a modifier word wmwithin a phrase qm, and a head word whwithin a phrase qh. For example, in the example in section 3.3 where these criticisms was combined with take, the modifier word is criticisms and the head word is take. The modifier and head words have TAG spines smand shrespectively. In addition we can define (am, bm)to be the start and end indices of the words in the foreign string to which the word wmis aligned; this information can be recovered because the s-phrase qmcontains alignment information for all target words in the phrase, including wm. Similarly, we can define (ah, bh)to be alignment information for the head word wh. Finally, we can define ρto be a binary flag specifying whether or not the adjunction operation involves reordering (in the take criticism example, this flag is set to true, because the order in En- VP DT N NP N criticismsthese take nehmenernstwir m¨ ussen auch diese kritik Figure 5: An adjunction operation that involves the modifier criticisms and the head take. The phrases involved are underlined; the dotted lines show alignments within s-phrases between English words and positions in the German string. The Γ-dependency in this case includes the head and modifier words, together with their spines, and their alignments to positions in the German string (kritik and nehmen). glish is reversed from that in German). This leads to the following definition: Definition 2 Given a derivation d=hq, πi, we define Γ(d)to be the set of Γ-dependencies in d. Each Γ-dependency is a tuple hwm, sm, am, bm, wh, sh, ah, bh, ρiof elements as described above. Figure 5 gives an illustration of how an adjunction creates one such Γ-dependency. The model is then defined as scoreR(d) = X γ∈Γ(d) scorer(γ, f) where scorer(γ, f)is a score associated with the Γ-dependency γ. This score can potentially be sensitive to any information in γor the sourcelanguage string f; in particular, note that the alignment indices (am, bm)and (ah, bh)essentially anchor the target-language dependency to positions in the source-language string, allowing the score for the dependency to be based on features that have been widely used in discriminative dependency parsing, for example features based on the proximity of the two positions in the sourcelanguage string, the part-of-speech tags in the surrounding context, and so on. These features have been shown to be powerful in the context of regular dependency parsing, and our intent is to leverage them in the translation problem. In our model, we define scoreras follows. We estimate a model P(y|γ, f)where y∈ {−1,+1}, and y= +1 indicates that a dependency does exist between wmand wh, and y=−1indicates that a dependency does not exist. We then define scorer(γ, f) = log P(+1|γ, f) To estimate P(y|γ, f), we first extract a set of labeled training examples of the form hyi, γi,fiifor i= 1 . . . N from our training data as follows: for each pair of target-language words (wm, wh) seen in the training data, we can extract associated spines (sm, sh)from the relevant parse tree, and also extract a label yindicating whether or not a head-modifier dependency is seen between the two words in the parse tree. Given an s-phrase in the training example that includes wm, we can extract alignment information (am, bm)from the sphrase; wecan extract similar information (ah, bh) for wh. The end result is a training example of the form hy, γ, fi.8We then estimate P(y|γ, f)using a simple backed-off model that takes into account the identity of the two spines, the value for the flag r, the distance between (am, bm)and (ah, bh), and part-of-speech information in the source language. 4.2 Contiguity of π-Constituents We now describe a second type of constraint, which limits the amount of non-projectivity in derivations. Consider again the kadjunction operations in π, which are used to connect treelets into a full parse tree. Each adjunction operation involves a head treelet that dominates a modifier treelet. Thus for any treelet t, we can consider its descendants, that is, the entire set of treelets that are directly or indirectly dominated by t. We define a π-constituent for treelet tto be the subset of source-language words dominated by tand its descendants. We then introduce the following constraint on π-constituents: Definition 3 (π-constituent constraint.) A πconstituent is contiguous iff it consists of a contiguous sequence of words in the source language. A derivation πsatisfies the π-constituent constraint iff all π-constituents that it contains are contiguous. In this paper we constrain all derivations to satisfy the π-constituent constraint (future work may consider probabilistic versions of the constraint). The intuition behind the constraint deserves more discussion. The constraint specifies that the modifiers to each treelet can appear in any order around the treelet, with arbitrary reorderings or non-projective operations. However, once a treelet has taken all its modifiers, the resulting πconstituent must form a contiguous sub-sequence 8To be precise, there may be multiple (or even zero) sphrases which include wmor wh, and these s-phrases may include conflicting alignment information. Given nmdifferent alignments seen for wm, and nhdifferent alignments seen for wh, we create nm×nhtraining examples, which include all possible combinations of alignments. of the source-language string. As one set of examples, consider the translations in figure 3, and the example given in the introduction. These examples involve reordering of arguments and adjuncts within clauses, a very common case of reordering in translation from German to English. The reorderings in these translations are quite flexible, but in all cases satisfy the π-constituent constraint. As an illustration of a derivation that violates the constraint, consider again the derivation step shown in figure 4. This step has formed a partial hypothesis, no discrimination, which corresponds to the German words keine and diskriminierung, which do not form a contiguous substring in the German. Consider now a complete derivation, which derives the string there is hierarchy of no discrimination, and which includes the π-constituent no discrimination shown in the figure (i.e., where the treelet discrimination takes no as its only modifier). This derivation will violate the π-constituent constraint.9 5 Decoding We now describe decoding algorithms for the syntactic models: we first describe inference rules that are used to combine pieces of structure, and then describe heuristic search algorithms that use these inference rules. Throughout this section, for brevity and simplicity, we describe algorithms that apply under the assumption that each s-phrase has a single associated treelet. The generalization to the case where an s-phrase may have multiple treelets is discussed in section 5.3. 5.1 Inference Rules Parsing operations for the TAG grammars described in (Carreras et al., 2008) are based on the dynamic programming algorithms in (Eisner, 2000). A critical idea in dynamic programming algorithms such as these is to associate constituents in a chart with spans of the input sentence, and to introduce inference rules that combine constituents into larger pieces of structure. The crucial step in generalizing these algorithms to the nonprojective case, and to translation, will be to make use of bit-strings that keep track of which words in the German have already been translated in a chart entry. To return to the example from the introduction, again assume that the selected s-phrases 9Note, however, that the derivation step show in figure 4 will be considered in the search, because if discrimination takes additional modifiers, and thereby forms a π-constituent that dominates a contiguous sub-string in the German, then the resulting derivation will be valid. 0. Data structures: Qifor i= 1 ...nis a set of hypotheses for each length i,Sis a set of chart entries 1. S ← ∅ 2. Initialize Q1...Qnwith basic chart entries derived from phrase entries 3. For i= 1 . . . n 4. For any A∈BEAM(Qi) 5. If Scontains a chart entry with the same signature as A, and which has a higher inside score, 6. continue 7. Else 8. Add Ato S 9. For any chart entry Cthat can be derived from Atogether with another chart entry B∈ S, add Cto the set Qjwhere j=length(C) 10. Return Qn, a set of items of length n Figure 6: A beam search algorithm. A dynamicprogramming signature consists of the regular dynamicprogramming state for the parsing algorithm, together with the span (bit-string) associated with a constituent. segment the German input into [wir m¨ ussen auch] [diese kritik] [ernst] [nehmen], and the treelets are as shown in the introduction. Each of these treelets will form a basic entry in the chart, and will have an associated bit-string indicating which German words have been translated by that entry. These basic chart entries can then be combined to form larger pieces of structure. For example, the following inferential step is possible: NP/0001100 these criticisms VP/0000001 V take ⇒VP/0001101 V take NP these criticisms We have shown the bit-string representation for each consituent: for example, the new constituent has the bit-string 0001101 representing the fact that the non-contiguous sub-strings diese kritik and nehmen have been translated at this point. Any two constituents can be combined, providing that the logical AND of their bit-strings is all 0’s. Inference steps such as that shown above will have an associated score corresponding to the TAG adjunction that is involved: in our models, both scoreSY N and scoreRwill contribute to this score. In addition, we add state—specifically, word bigrams at the start and end of constituents— that allows trigram language model scores to be calculated as constituents are combined. 5.2 Approximate Search There are 2npossible bit-strings for a sentence of length n, hence the search space is of exponential size; approximate algorithms are therefore required in search for the highest scoring derivation. Figure 6 shows a beam search algorithm which makes use of the inference rules described in the previous section. The algorithm stores sets Qi for i= 1 . . . n, where nis the source-language sentence length; each set Qistores hypotheses of length i(i.e., hypotheses with an associated bitstring with iones). These sets are initialized with basic entries derived from s-phrases. The function BEAM(Qi)returns all items within Qithat have a high enough score to fall within a beam (more details for BEAM are given below). At each iteration (step 4), each item in turn is taken from BEAM(Qi)and added to a chart; the inference rules described in the previous section are used to derive new items which are added to the appropriate set Qj, where j > i. We have found the definition of BEAM(Qi)to be critical to the success of the method. As a first step, each item in Qireceives a score that is a sum of an inside score (the cost of all derivation steps used to create the item) and a future score (an estimate of the cost to complete the translation). The future score is based on the source-language words that are still to be translated—this can be directly inferred from the item’s bit-string—this is similar to the use of future scores inPharoah (Koehn et al., 2003), and in fact we use Pharoah’s future scores in our model. We then give the following definition, where Nis a parameter (the beam size): Definition 4 (BEAM) Given Qi, define Qi,j for j= 1 . . . n to be the subset of items in Qiwhich have their j’th bit equal to one (i.e., have the j’th source language word translated). Define Q′ i,j to be the Nhighest scoring elements in Qi,j. Then BEAM(Qi) = ∪n j=1Q′ i,j. To motivate this definition, note that a naive method would simply define BEAM(Qi)to be the Nhighest scoring elements of Qi. This definition, however, assumes that constituents which form translations of different parts of a sentence have scores that can be compared—an assumption that would be true if the future scores were highly accurate, but which quickly breaks down when future scores are inaccurate. In contrast, the definition above ensures that the top Nanalyses for each of the nsource language words are stored at each stage, and hence that all parts of the source sentence are well represented. In experiments, the naive approach was essentially a failure, with parsing of some sentences either failing or being hopelessly inefficient, depending on the choice of N. In contrast, definition 4 gives good results. System BLEU score Syntax-based 25.2 Syntax (no ScoreR) 23.7 (-1.5) Syntax (no π-c constraint) 24.4 (-0.8) Table 1: Development set results showing the effect of removing ScoreRor the π-constituent constraint. 5.3 Allowing Multiple Treelets per s-Phrase The decoding algorithms that we have described apply in the case where each s-phrase has a single treelet. The extension of these algorithms to the case where a phrase may have multiple treelets (e.g., see figure 2) is straightforward, but for brevity the details are omitted. The basic idea is to extend bit-string representations with a record of “pending” treelets which have not yet been included in a derivation. It is also possible to enforce the π-constituent constraint during decoding, as well as a constraint that ensures that reordering operations do not “break apart” English sub-strings within s-phrases that have multiple treelets (for example, for the s-phrase in figure 2, we ensure that there is no remains as a contiguous sequence of words in any translation using this s-phrase). 6 Experiments We trained the syntax-based system on 751,088 German-English translations from the Europarl corpus (Koehn, 2005). A syntactic language model was also trained on the English sentences in the training data. We used Pharoah (Koehn et al., 2003) as a baseline system for comparison; the s-phrases used in our system include all phrases, with the same scores, as those used by Pharoah, allowing a direct comparison. For efficiency reasons we report results on sentences of length 30 words or less.10 The syntax-based method gives a BLEU (Papineni et al., 2002) score of 25.04, a 0.46 BLEU point gain over Pharoah. This result was found to be significant (p= 0.021) under the paired bootstrap resampling method of Koehn (2004), and is close to significant (p= 0.058) under the sign test of Collins et al. (2005). Table 1 shows results for the full syntax-based system, and also results for the system with the discriminative dependency scores (see section 4.1) and the π-contituent constraint removed from the system. In both cases we see a clear impact of these components of the model, with 1.5 and 0.8 BLEU point decrements respectively. 10Both Pharoah and our system have weights trained using MERT (Och, 2003) on sentences of length 30 words or less, to ensure that training and test conditions are matched. R: in our eyes , the opportunity created by this directive of introducing longer buses on international routes is efficient . S: the opportunity now presented by this directive is effective in our opinion , to use long buses on international routes . P: the need for this directive now possibility of longer buses on international routes to is in our opinion , efficiently . R: europe and asia must work together to intensify the battle against drug trafficking , money laundering , international crime , terrorism and the sexual exploitation of minors . S: europe and asia must work together in order to strengthen the fight against drug trafficking , money laundering , against international crime , terrorism and the sexual exploitation of minors . P: europe and asia must cooperate in the fight against drug trafficking , money laundering , against international crime , terrorism and the sexual exploitation of minors strengthened . R: equally important for the future of europe - at biarritz and later at nice - will be the debate on the charter of fundamental rights . S: it is equally important for the future of europe to speak on the charter of fundamental rights in biarritz , and then in nice . P: just as important for the future of europe , it will be in biarritz and then in nice on the charter of fundamental rights to speak . R: the convention was thus a muddled system , generating irresponsibility , and not particularly favourable to well-ordered democracy . S: therefore , the convention has led to a system of a promoter of irresponsibility of the lack of clarity and hardly coincided with the rules of a proper democracy . P: the convention therefore led to a system of full of lack of clarity and hardly a promoter of the irresponsibility of the rules of orderly was a democracy . Figure 7: Examples where both annotators judged the syntactic system to give an improved translation when compared to the baseline system. 51 out of 200 translations fall into this category. These examples were chosen at random from these 51 examples. Ris the human (reference) translation; Sis the translation from the syntax-based system; Pis the output from the baseline (phrase-based) system. Syntax PB = Total Syntax 51 3 7 61 PB 1 25 11 37 = 21 14 67 102 Total 73 42 85 200 Table 2: Human annotator judgements. Rows show results for annotator 1, and columns for annotator 2. Syntax and PB show the number of cases where an annotator respectively preferred/dispreferred the syntax-based system. = gives counts of translations judged to be equal in quality. In addition, we obtained human evaluations on 200 sentences chosen at random from the test data, using two annotators. For each example, the reference translation was presented to the annotator, followed by translations from the syntax-based and phrase-based systems (in a random order). For each example, each annotator could either decide that the two translations were of equal quality, or that one translation was better than the other. Table 2 shows results of this evaluation. Both annotators show a clear preference for the syntaxbased system: for annotator 1, 73 translations are judged to be better for the syntax-based system, with 42 translations being worse; for annotator 2, 61 translations are improved with 37 being worse; both annotators’ results are statistically significant with p < 0.05 under the sign test. Figure 7 shows some translation examples where the syntax-based system was judged to give an improvement. 7 Conclusions and Future Work We have described a translation model that makes use of flexible parsing operations, critical ideas being the definition of s-phrases, Γ-dependencies, the π-constituent constraint, and an approximate search algorithm. A key area for future work will be further development of the discriminative dependency model (section 4.1). The model of scorer(γ, f)that we have described in this paper is relatively simple; in general, however, there is the potential for scorerto link target language dependencies to arbitrary properties of the source language string f(recall that γcontains a head and modifier spine in the target language, along with positions in the source-language string to which these spines are aligned). For example, we might introduce features that: a) condition dependencies created in the target language on dependency relations between their aligned words in the source language; b) condition target-language dependencies on whether they are aligned to words that are in the same clause or segment in the source language string; or, c) condition the grammatical roles of nouns in the target language on grammatical roles of aligned words in the source language. These features should improve translation quality by giving a tighter link between syntax in the source and target languages, and would be easily incorporated in the approach we have described. Acknowledgments We would like to thank Ryan McDonald for conversations that were influential in this work, and Meg Aycinena Lippow and Ben Snyder for translation judgments. This work was supported under the GALE program of the Defense Advanced Research Projects Agency, Contract No. HR0011-06-C-0022.