Decoding of phrase-based translation models in the general case is known to be NPcomplete, by a reduction from the traveling salesman problem (Knight, 1999) . In practice, phrase-based systems often impose a hard distortion limit that limits the movement of phrases during translation. However, the impact on complexity after imposing such a constraint is not well studied. In this paper, we describe a dynamic programming algorithm for phrase-based decoding with a fixed distortion limit. The runtime of the algorithm is O(nd!lh d+1 ) where n is the sentence length, d is the distortion limit, l is a bound on the number of phrases starting at any position in the sentence, and h is related to the maximum number of target language translations for any source word. The algorithm makes use of a novel representation that gives a new perspective on decoding of phrase-based models. 59
Introduction Phrase-based translation models (Koehn et al., 2003; Och and Ney, 2004) are widely used in statistical machine translation. The decoding problem for phrase-based translation models is known to be difficult: the results from Knight (1999) imply that in the general case decoding of phrase-based translation models is NP-complete. The complexity of phrase-based decoding comes from reordering of phrases. In practice, however, various constraints on reordering are often imposed in phrase-based translation systems. A common constraint is a "distortion limit", which places a hard constraint on how far phrases can move. The complexity of decoding with such a distortion limit is an open question: the NP-hardness result from Knight * On leave from Columbia University. (1999) applies to a phrase-based model with no distortion limit. This paper describes an algorithm for phrasebased decoding with a fixed distortion limit whose runtime is linear in the length of the sentence, and for a fixed distortion limit is polynomial in other factors. More specifically, for a hard distortion limit d, and sentence length n, the runtime is O(nd!lh d+1 ), where l is a bound on the number of phrases starting at any point in the sentence, and h is related to the maximum number of translations for any word in the source language sentence. The algorithm builds on the insight that decoding with a hard distortion limit is related to the bandwidth-limited traveling salesman problem (BTSP) (Lawler et al., 1985) . The algorithm is easily amenable to beam search. It is quite different from previous methods for decoding of phrase-based models, potentially opening up a very different way of thinking about decoding algorithms for phrasebased models, or more generally for models in statistical NLP that involve reordering. 2 Related Work Knight (1999) proves that decoding of word-to-word translation models is NP-complete, assuming that there is no hard limit on distortion, through a reduction from the traveling salesman problem. Phrasebased models are more general than word-to-word models, hence this result implies that phrase-based decoding with unlimited distortion is NP-complete. Phrase-based systems can make use of both reordering constraints, which give a hard "distortion limit" on how far phrases can move, and reordering models, which give scores for reordering steps, often penalizing phrases that move long distances. Moses (Koehn et al., 2007b ) makes use of a distortion limit, and a decoding algorithm that makes use of bit-strings representing which words have been translated. We show in Section 5.2 of this paper that this can lead to at least 2 n/4 bit-strings for an input sentence of length n, hence an exhaustive version of this algorithm has worst-case runtime that is exponential in the sentence length. The current paper is concerned with decoding phrase-based models with a hard distortion limit. Various other reordering constraints have been considered. Zens and Ney (2003) and Zens et al. (2004) consider two types of hard constraints: the IBM constraints, and the ITG (inversion transduction grammar) constraints from the model of Wu (1997) . They give polynomial time dynamic programming algorithms for both of these cases. It is important to note that the IBM and ITG constraints are different from the distortion limit constraint considered in the current paper. Decoding algorithms with ITG constraints are further studied by Feng et al. (2010) and Cherry et al. (2012) . Kumar and Byrne (2005) describe a class of reordering constraints and models that can be encoded in finite state transducers. Lopez (2009) shows that several translation models can be represented as weighted deduction problems and analyzes their complexities. 1 Koehn et al. (2003) describe a beamsearch algorithm for phrase-based decoding that is in widespread use; see Section 5 for discussion. A number of reordering models have been proposed, see for example Tillmann (2004) , Koehn et al. (2007a) and Galley and Manning (2008) . DeNero and Klein (2008) consider the phrase alignment problem, that is, the problem of finding an optimal phrase-based alignment for a sourcelanguage/target-language sentence pair. They show that in the general case, the phrase alignment problem is NP-hard. It may be possible to extend the techniques in the current paper to the phrasealignment problem with a hard distortion limit. Various methods for exact decoding of phrasebased translation models have been proposed. Zaslavskiy et al. (2009) describe the use of travel-1 An earlier version of this paper states the complexity of decoding with a distortion limit as O(I 3 2 d ) where d is the distortion limit and I is the number of words in the sentence; however (personal communication from Adam Lopez) this runtime is an error, and should be O(2 I ) i.e., exponential time in the length of the sentence. A corrected version of the paper corrects this. ing salesman algorithms for phrase-based decoding. Chang and Collins (2011) describe an exact method based on Lagrangian relaxation. Aziz et al. (2014) describe a coarse-to-fine approach. These algorithms all have exponential time runtime (in the length of the sentence) in the worst case. Galley and Manning (2010) describe a decoding algorithm for phrase-based systems where phrases can have discontinuities in both the source and target languages. The algorithm has some similarities to the algorithm we propose: in particular, it makes use of a state representation that contains a list of disconnected phrases. However, the algorithms differ in several important ways: Galley and Manning (2010) make use of bit string coverage vectors, giving an exponential number of possible states; in contrast to our approach, the translations are not formed in strictly left-to-right ordering on the source side. Background: The Traveling Salesman Problem on Bandwidth-Limited Graphs This section first defines the bandwidth-limited traveling salesman problem, then describes a polynomial time dynamic programming algorithm for the traveling salesman path problem on bandwidth limited graphs. This algorithm is the algorithm proposed by Lawler et al. (1985) 2 with small modifications to make the goal a path instead of a cycle, and to consider directed rather than undirected graphs. Bandwidth-Limited TSPPs The input to the problem is a directed graph G = (V, E), where V is a set of vertices and E is a set of directed edges. We assume that V = {1, 2, . . . , n}. A directed edge is a pair (i, j) where i, j ∈ V , and i = j. Each edge (i, j) ∈ E has an associated weight w i,j . Given an integer k ≥ 1, a graph is bandwidth-limited with bandwidth k if ∀(i, j) ∈ E, |i − j| ≤ k The traveling salesman path problem (TSPP) on the graph G is defined as follows. We will assume that vertex 1 is the "source" vertex and vertex n is the "sink" vertex. The TSPP is to find the minimum cost directed path from vertex 1 to vertex n, which passes through each vertex exactly once. An Algorithm for Bandwidth-Limited TSPPs The key idea of the dynamic-programming algorithm for TSPPs is the definition of equivalence classes corresponding to dynamic programming states, and an argument that the number of equivalence classes depends only on the bandwidth k. The input to our algorithm will be a directed graph G = (V, E), with weights w i,j , and with bandwidth k. We define a 1-n path to be any path from the source vertex 1 to the sink vertex n that visits each vertex in the graph exactly once. A 1-n path is a subgraph (V , E ) of G, where V = V and E ⊆ E. We will make use of the following definition: Definition 1. For any 1-n path H, define H j to be the subgraph that H induces on vertices 1, 2, . . . j, where 1 ≤ j ≤ n. That is, H j contains the vertices 1, 2, . . . j and the edges in H between these vertices. For a given value for j, we divide the vertices V into three sets A j , B j and C j : • A j = {1, 2, . . . , (j − k)} (A j is the empty set if j ≤ k). • B j = {1 . . . j} \ A j . 3 • C j = {j + 1, j + 2, . . . , n} (C j is the empty set if j = n). Note that the vertices in subgraph H j are the union of the sets A j and B j . A j is the empty set if j ≤ k, but B j is always non-empty. The following Lemma then applies: Lemma 1. For any 1-n path H in a graph with bandwidth k, for any 1 ≤ j ≤ n, the subgraph H j has the following properties: 1. If vertex 1 is in A j , then vertex 1 has degree one. For any vertex v ∈ A j with v ≥ 2, vertex v has degree two. 3. H j contains no cycles. Proof. The first and second properties are true because of the bandwidth limit. Under the constraint of bandwidth k, any edge (u, v) in H such that u ∈ A j , must have v ∈ A j ∪ B j = H j . This fol- lows because if v ∈ C j = {j + 1, j + 2, . . . n} and u ∈ A j = {1, 2, . . . j − k}, then |u − v| > k. Similarly any edge (u, v) ∈ H such that v ∈ A j must have u ∈ A j ∪ B j = H j . It follows that for any vertex u ∈ A j , with u > 1, there are edges (u, v) ∈ H j and (v , u) ∈ H j , hence vertex u has degree 2. For vertex u ∈ A j with u = 1, there is an edge (u, v) ∈ H j , hence vertex u has degree 1. The third property (no cycles) is true because H j is a subgraph of H, which has no cycles. It follows that each connected component of H j is a directed path, that the start points of these paths are in the set {1} ∪ B j , and that the end points of these paths are in the set B j . We now define an equivalence relation on subgraphs. Two subgraphs H j and H j are in the same equivalence class if the following conditions hold (taken from Lawler et al. (1985) ): 1. For any vertex v ∈ B j , the degree of v in H j and H j is the same. For each path (connected component) in H j there is a path in H j with the same start and end points, and conversely. The significance of this definition is as follows. Assume that H * is an optimal 1-n path in the graph, and that it induces the subgraph H j on vertices 1 . . . j. Assume that H j is another subgraph over vertices 1 . . . j, which is in the same equivalence class as H j . For any subgraph H j , define c(H j ) to be the sum of edge weights in H j : c(H j ) = (u,v)∈H j w u,v Then it must be the case that c(H j ) ≥ c(H j ). Otherwise, we could simply replace H j by H j in H * , thereby deriving a new 1-n path with a lower cost, implying that H * is not optimal. This observation underlies the dynamic programming approach. Define σ to be a function that maps a subgraph H j to its equivalence class σ(H j ). The equivalence class σ(H j ) is a data structure that stores the degrees of the vertices in B j , together with the start and end points of each connected component in H j . Next, define ∆ to be a set of 0, 1 or 2 edges between vertex (j + 1) and the vertices in B j . For any subgraph H j+1 of a 1-n path, there is some ∆, simply found by recording the edges incident to vertex (j + 1). For any H j , define τ (σ(H j ), ∆) to be the equivalence class resulting from adding the edges in ∆ to the data structure σ(H j ). If adding the edges in ∆ to σ(H j ) results in an ill-formed subgraph-for example, a subgraph that has one or more cyclesthen τ (σ(H j ), ∆) is undefined. The following recurrence then defines the dynamic program (see Eq. 20 of Lawler et al. (1985) ): α(j + 1, S) = min ∆,S :τ (S ,∆)=S α(j, S ) + c(∆) Here S is an equivalence class over vertices {1 . . . (j +1)}, and α(S, j +1) is the minimum score for any subgraph in equivalence class S. The min is taken over all equivalence classes S over vertices {1 . . . j}, together with all possible values for ∆. A Dynamic Programming Algorithm for Phrase-Based Decoding We now describe the dynamic programming algorithm for phrase-based decoding with a fixed distortion limit. We first give basic definitions for phrasebased decoding, and then describe the algorithm. Basic Definitions Consider decoding an input sentence consisting of words x 1 . . . x n for some integer n. We assume that x 1 = <s> and x n = </s> where <s> and </s> are the sentence start and end symbols respectively. A phrase-based lexicon specifies a set of possible translations in the form of phrases p = (s, t, e), where s and t are integers such that 1 ≤ s ≤ t ≤ n, and e is a sequence of m ≥ 1 target-language words e 1 . . . e m . This signifies that words x s . . . x t in the source language have a translation as e 1 . . . e m in the target language. We use s(p), t(p) and e(p) to refer to the three components of a phrase p = (s, t, e), and e 1 (p) . . . e m (p) to refer to the words in the targetlanguage string e(p). We assume that (1, 1, <s>) and (n, n, </s>) are the only translation entries with s(p) ≤ 1 and t(p) ≥ n respectively. A derivation is then defined as follows: Definition 2 (Derivations). A derivation is a sequence of phrases p 1 . . . p L such that • p 1 = (1, 1, <s>) and p L = (n, n, </s>). • Each source word is translated exactly once. • The distortion limit is satisfied for each pair of phrases p i−1 , p i , that is: |t(p i−1 ) + 1 − s(p i )| ≤ d ∀ i = 2 . . . L. where d is an integer specifying the distortion limit in the model. Given a derivation p 1 . . . p L , a target-language translation can be obtained by concatenating the target-language strings e(p 1 ) . . . e(p L ). The scoring function is defined as follows: f (p 1 . . . p L ) = λ(e(p 1 ) . . . e(p L )) + L i=1 κ(p i ) + L i=2 η × |t(p i−1 ) + 1 − s(p i )| (1) For each phrase p, κ(p) is the translation score for the phrase. The parameter η is the distortion penalty, which is typically a negative constant. λ(e) is a language model score for the string e. We will assume a bigram language model: λ(e 1 . . . e m ) = m i=2 λ(e i |e i−1 ). The generalization of our algorithm to higher-order n-gram language models is straightforward. The goal of phrase-based decoding is to find y * = arg max y∈Y f (y) where Y is the set of valid derivations for the input sentence. Remark (gap constraint): Note that a common restriction used in phrase-based decoding (Koehn et al., 2003; Chang and Collins, 2011) , is to impose an additional "gap constraint" while decoding. See Chang and Collins (2011) for a description. In this case it is impossible to have a dynamicprogramming state where word x i has not been translated, and where word x i+k has been translated, for k > d. This limits distortions further, and it can be shown in this case that the number of possible bitstrings is O(2 d ) where d is the distortion limit. Without this constraint the algorithm of Koehn et al. (2003) actually fails to produce translations for many input sentences (Chang and Collins, 2011) . H 1 = π 1 = 1, 1, <s> H 3 = π 1 = 1, 1, <s> 2, 3, we must H 4 = π 1 = 1, 1, <s> 2, 3, we must 4, 4, also H 6 = π 1 , π 2 = 1, 1, <s> 2, 3, we must 4, 4, also , 5, 6, these criticisms H 7 = π 1 , π 2 = 1, 1, <s> 2, 3, we must 4, 4, also , 5, 6, these criticisms 7, 7, seriously H 8 = π 1 = 1, 1, <s> 2, 3, we must 4, 4, also 8, 8, take 5, 6, these criticisms 7, 7, seriously H 9 = π 1 = 1, 1, <s> 2, 3, we must 4, 4, also 8, 8, take 5, 6, these criticisms 7, 7, seriously 9, 9, </s> 3, 4, 6, 7, 8, 9} induced by the full derivation H = (1, 1, <s>)(2, 3, we must)(4, 4, also)(8, 8, take)(5, 6, these criticisms)(7, 7, seriously)(9, 9</s>) . Note that H j includes the phrases that cover spans ending before or at position j. Sub-derivation H j is extended to another subderivation H j+i by incorporating a phrase of length i. Figure 1: Sub-derivations H j for j ∈ {1, The Algorithm We now describe the dynamic programming algorithm. Intuitively the algorithm builds a derivation by processing the source-language sentence in strictly left-to-right order. This is in contrast with the algorithm of Koehn et al. (2007b) , where the targetlanguage sentence is constructed from left to right. Throughout this section we will use π, or π i for some integer i, to refer to a sequence of phrases: π = p 1 . . . p l where each phrase p i = (s(p i ), t(p i ), e(p i )), as de- fined in the previous section. We overload the s, t and e operators, so that if π = p 1 . . . p l , we have s(π) = s(p 1 ), t(π) = t(p l ), and e(π) = e(p 1 ) · e(p 2 ) . . . · e(p l ), where x · y is the concatenation of strings x and y. A derivation H consists of a single phrase sequence π = p 1 . . . p L : H = π = p 1 . . . p L where the sequence p 1 . . . p L satisfies the constraints in definition 2. We now give a definition of sub-derivations and complement sub-derivations: Definition 3 (Sub-derivations and Complement Sub- -derivations). For any H = p 1 . . . p L , for any j ∈ {1 . . . n} such that ∃ i ∈ {1 . . . L} s.t. t(p i ) = j, the sub-derivation H j and the complement sub- derivationH j are defined as H j = π 1 . . . π r ,H j = π 1 . . .π r where the following properties hold: • r is an integer with r ≥ 1. • Each π i for i = 1 . . . r is a sequence of one or more phrases, where each phrase p ∈ π i has t(p) ≤ j. • Eachπ i for i = 1 . . . (r − 1) is a sequence of one or more phrases, where each phrase p ∈π i has s(p) > j. •π r is a sequence of zero or more phrases, where each phrase p ∈π r has s(p) > j. We have zero phrases inπ r iff j = n where n is the length of the sentence. • Finally, π 1 ·π 1 · π 2 ·π 2 . . . π r ·π r = p 1 . . . p L where x · y denotes the concatenation of phrase sequences x and y. Note that for any j ∈ {1 . . . n} such that i ∈ {1 . . . L} such that t(p i ) = j, the sub-derivation H j and the complement sub-derivationH j is not defined. Thus for each integer j such that there is a phrase in H ending at point j, we can divide the phrases in H into two sets: phrases p with t(p) ≤ j, and phrases p with s(p) > j. The sub-derivation H j lists all maximal sub-sequences of phrases with t(p) ≤ j. The complement sub-derivationH j lists all maximal sub-sequences of phrases with s(p) > j. Figure 1 gives all sub-derivations H j for the derivation H = p 1 . . . p 7 = (1, 1, <s>)(2, 3, we must)(4, 4, also) (8, 8, take)(5, 6, these criticisms) (7, 7, seriously)(9, 9, </s>) As one example, the sub-derivation H 7 = π 1 , π 2 induced by H has two phrase sequences: π 1 = (1, 1, <s>)(2, 3, we must)(4, 4, also) π 2 = (5, 6, these criticisms)(7, 7, seriously) Note that the phrase sequences π 1 and π 2 give translations for all words x 1 . . . x 7 in the sentence. There 63 are two disjoint phrase sequences because in the full derivation H, the phrase p = (8, 8, take), with t(p) = 8 > 7, is used to form a longer sequence of phrases π 1 p π 2 . For the above example, the complement sub-derivationH 7 is as follows: π 1 = (8, 8, take) π 2 = (9, 9, </s>) It can be verified that π 1 ·π 1 ·π 2 ·π 2 = H as required by the definition of sub-derivations and complement sub-derivations. We now state the following Lemma: Lemma 2. For any derivation H = p 1 . . . p L , for any j such that ∃i such that t(p i ) = j, the subderivation H j = π 1 . . . π r satisfies the following properties: 1. s(π 1 ) = 1 and e 1 (π 1 ) = <s>. 2. For all positions i ∈ {1 . . . j}, there exists a phrase p ∈ π, for some phrase sequence π ∈ H j , such that s(p) ≤ i ≤ t(p). For all i = 2 . . . r, s(π i ) ∈ {(j − d + 2) . . . j} 4. For all i = 1 . . . r, t(π i ) ∈ {(j − d) . . . j} Here d is again the distortion limit. This lemma is a close analogy of Lemma 1. The proof is as follows: Proof of Property 1: For all values of j, the phrase p 1 = (1, 1, <s>) has t(p 1 ) ≤ j, hence we must have π 1 = p 1 . . . p k for some k ∈ {1 . . . L}. It follows that s(π 1 ) = 1 and e 1 (π 1 ) = <s>. Proof of Property 2: For any position i ∈ {1 . . . j}, define the phrase (s, t, e) in the derivation H to be the phrase that covers word i; i.e., the phrase such that s ≤ i ≤ t. We must have s ∈ {1 . . . j}, because s ≤ i and i ≤ j. We must also have t ∈ {1 . . . j}, because otherwise we have s ≤ j < t, which contradicts the assumption that there is some i ∈ {1 . . . L} such that t(p i ) = j. It follows that the phrase (s, t, e) has t ≤ j, and from the definition of sub-derivations it follows that the phrase is in one of the phrase sequences π 1 . . . π r . Proof of Property 3: This follows from the distortion limit. Consider the complement sub-derivation H j = π 1 . . .π r . For the distortion limit to be satisfied, for all i ∈ {2 . . . r}, we must have |t(π i−1 ) + 1 − s(π i )| ≤ d We must also have t(π i−1 ) > j, and s(π i ) ≤ j, by the definition of sub-derivations. It follows that s(π i ) ∈ {(j − d + 2) . . . j}. Proof of Property 4: This follows from the distortion limit. First consider the case whereπ r is non-empty. For the distortion limit to be satisfied, for all i ∈ {1 . . . r}, we must have |t(π i ) + 1 − s(π i )| ≤ d We must also have t(π i ) ≤ j, and s(π i ) > j, by the definition of sub-derivations. It follows that t(π i ) ∈ {(j − d) . . . j}. Next consider the case whereπ r is empty. In this case we must have j = n. For the distortion limit to be satisfied, for all i ∈ {1 . . . (r − 1)}, we must have |t(π i ) + 1 − s(π i )| ≤ d We must also have t(π i ) ≤ j, and s(π i ) > j, by the definition of sub-derivations. It follows that t(π i ) ∈ {(j − d) . . . j} for i ∈ {1 . . . (r − 1)}. For i = r, we must have t(π i ) = n, from which it again follows that t(π r ) = n ∈ {(j − d) . . . j}. We now define an equivalence relation between sub-derivations, which will be central to the dynamic programming algorithm. We define a function σ that maps a phrase sequence π to its signature. The signature is a four-tuple: σ(π) = (s, w s , t, w t ). where s is the start position, w s is the start word, t is the end position and w t is the end word of the phrase sequence. We will use s(σ), w s (σ), t(σ), and w t (σ) to refer to each component of a signature σ. For example, given a phrase sequence π = (1, 1, <s>) (2, 2, we) (4, 4, also) , its signature is σ(π) = (1, <s>, 4, also). The signature of a sub-derivation H j = π 1 . . . π r is defined to be σ(H j ) = σ(π 1 ) . . . σ(π r ) . For example, with H 7 as defined above, we have σ(H 7 ) = 1, <s>, 4, also , 5, these, 7, seriously Two partial derivations H j and H j are in the same equivalence class iff σ(H j ) = σ(H j ). We can now state the following Lemma: Lemma 3. Define H * to be the optimal derivation for some input sentence, and H * j to be a subderivation of H * . Suppose H j is another subderivation with j words, such that σ(H j ) = σ(H * j ). Then it must be the case that f (H * j ) ≥ f (H j ), where f is the function defined in Section 4.1. Proof. Define the sub-derivation and complement sub-derivation of H * as H * j = π 1 . . . π r H * j = π 1 . . .π r We then have f (H * ) = f (H * j ) + f (H * j ) + γ (2) where f (. . .) is as defined in Eq. 1, and γ takes into account the bigram language modeling scores and the distortion scores for the transitions π 1 →π 1 , π 1 → π 2 , π 2 →π 2 , etc. The proof is by contradiction. Define H j = π 1 . . . π r and assume that f (H * j ) < f (H j ). Now consider H = π 1π 1 π 2π 2 . . . π rπ r This is a valid derivation because the transitions π 1 →π 1 ,π 1 → π 2 , π 2 →π 2 have the same distortion distances as π 1 →π 1 ,π 1 → π 2 , π 2 →π 2 , hence they must satisfy the distortion limit. We have f (H ) = f (H j ) + f (H * j ) + γ (3) where γ has the same value as in Eq. 2. This follows because the scores for the transitions π 1 →π 1 , π 1 → π 2 , π 2 →π 2 are identical to the scores for the transitions π 1 →π 1 ,π 1 → π 2 , π 2 →π 2 , because σ(H * j ) = σ(H j ). It follows from Eq. 2 and Eq. 3 that if f (H j ) > f (H * j ), then f (H ) > f (H * ). But this contradicts the assumption that H * is optimal. It follows that we must have f (H j ) ≤ f (H * j ). This lemma leads to a dynamic programming algorithm. Each dynamic programming state consists of an integer j ∈ {1 . . . n} and a set of r signatures: T = (j, {σ 1 . . . σ r }) Figure 2 shows the dynamic programming algorithm. It relies on the following functions: Inputs: • An integer n specifying the length of the input sequence. • A function δ(T ) returning the set of valid transitions from state T . • A function τ (T, ∆) returning the state reached from state T by transition ∆ ∈ δ(T ). • A function valid(T ) returning TRUE if state T is valid, otherwise FALSE. • A function score(∆) that returns the score for any transition ∆. Initialization: {(1, <s>, 1, <s>) T 1 = (1, }) α(T 1 ) = 0 T 1 = {T 1 }, ∀j ∈ {2 . . . n}, T j = ∅ for j = 1, . . . , n − 1 for each state T ∈ T j for each ∆ ∈ δ(T ) T = τ (T, ∆) if valid(T ) = FALSE: continue score = α(T ) + score(∆) Define t to be the integer such that T = (t, {σ 1 . . . σr}) if T / ∈ Tt Tt = Tt ∪ {T } α(T ) = score bp(T ) = (∆) else if score > α(T ) α(T ) = score bp(T ) = (∆) Return: the score of the state (n, {(1, <s>, n, </s>)}) in Tn, and backpointers bp defining the transitions leading to this state. is the score for state T . The bp(T ) variables are backpointers used in recovering the highest scoring sequence of transitions. • For any state T , δ(T ) is the set of outgoing transitions from state T . • For any state T , for any transition ∆ ∈ δ(T ), τ (T, ∆) is the state reached by transition ∆ from state T . • For any state T , valid(T ) checks if a resulting state is valid. • For any transition ∆, score(∆) is the score for the transition. We next give full definitions of these functions. Definitions of δ(T ) and τ (T, ∆) Recall that for any state T , δ(T ) returns the set of possible transitions from state T . In addition τ (T, ∆) returns the state reached when taking transition ∆ ∈ δ(T ). Given the state T = (j, {σ 1 . . . σ r }), each transition is of the form ψ 1 p ψ 2 where ψ 1 , p and ψ 2 are defined as follows: • p is a phrase such that s(p) = j + 1. • ψ 1 ∈ {σ 1 . . . σ r } ∪ {φ}. If ψ 1 = φ, it must be the case that |t(ψ 1 ) + 1 − s(p)| ≤ d and t(ψ 1 ) = n. • ψ 2 ∈ {σ 1 . . . σ r } ∪ {φ}. If ψ 2 = φ, it must be the case that |t(p) + 1 − s(ψ 2 )| ≤ d and s(ψ 2 ) = 1. • If ψ 1 = φ and ψ 2 = φ, then ψ 1 = ψ 2 . Thus there are four possible types of transition from a state T = (j, {σ 1 . . . σ r }): Case 1: ∆ = φ p φ. In this case the phrase p is incorporated as a stand-alone phrase. The new state T is equal to (j , {σ 1 . . . σ r+1 }) where j = t(p), where σ i = σ i for i = 1 . . . r, and σ r+1 = (s(p), e 1 (p), t(p), e m (p)). Case 2: ∆ = σ i p φ for some σ i ∈ {σ 1 . . . σ r }. In this case the phrase p is appended to the signa- ture σ i . The new state T = τ (T, ∆) is of the form (j , σ 1 . . . σ r ), where j = t(p), where σ i is replaced by (s(σ i ), w s (σ i ), t(p), e m (p)), and where σ i = σ i for all i = i. Case 3: ∆ = φ p σ i for some σ i ∈ {σ 1 . . . σ r }. In this case the phrase p is prepended to the signa- ture σ i . The new state T = τ (T, ∆) is of the form (j , σ 1 . . . σ r ), where j = t(p), where σ i is replaced by (s(p), e 1 (p), t(σ i ), w t (σ i )), and where σ i = σ i for all i = i. Case 4: ∆ = σ i p σ i for some σ i , σ i ∈ {σ 1 . . . σ r }, with i = i. In this case phrase p is appended to signature σ i , and prepended to signature σ i , effectively joining the two signatures together. In this case the new state T = τ (T, ∆) is of the form (j , σ 1 . . . σ r−1 ), where signatures σ i and σ i are replaced by a new signature (s(σ i ), w s (σ i ), t(σ i ), w t (σ i )), and all other signatures are copied across from T to T . Figure 3 gives the dynamic programming states and transitions for the derivation H in Figure 1 . For example, the sub-derivation H 7 = (1, 1, <s>)(2, 3, we must)(4, 4, also) , (5, 6, these criticisms)(7, 7, seriously) will be mapped to a state T = 7, σ(H 7 ) = 7, (1, <s>, 4, also), (5, these, 7, seriously) 1, σ 1 = 1, <s>, 1, <s> 3, σ 1 = 1, <s>, 3, must 4, σ 1 = 1, <s>, 4, also 6, σ 1 = 1, <s>, 4, also , σ 2 = 5, these, 6, criticisms 7, σ 1 = 1, <s>, 4, also , σ 2 = 5, these, 7, seriously 8, σ 1 = 1, <s>, 7, seriously 9, σ 1 = 1, <s>, 9, </s> σ 1 (2, 3, we must) φ σ 1 (4, 4, also) φ φ (5, 6, these criticisms) φ σ 2 (7, 7, seriously) φ σ 1 (8, 8, take) σ 2 σ 1 (9, 9, </s>) φ Figure 3 : Dynamic programming states and the transitions from one state to another, using the same example as in Figure 1 . Note that σ i = σ(π i ) for all π i ∈ H j . The transition σ 1 (8, 8, take) σ 2 from this state leads to a new state, T = 8, σ 1 = (1, <s>, 7, seriously) 4.3 Definition of score(∆) Figure 4 gives the definition of score(∆), which incorporates the language model, phrase scores, and distortion penalty implied by the transition ∆. Figure 5 gives the definition of valid(T ). This function checks that the start and end points of each signature are in the set of allowed start and end points given in Lemma 2. Definition of valid(T ) A Bound on the Runtime of the Algorithm We now give a bound on the algorithm's run time. This will be the product of terms N and M , where N is an upper bound on the number of states in the dynamic program, and M is an upper bound on the number of outgoing transitions from any state. For any j ∈ {1 . . . n}, define first(j) to be the set of target-language words that can begin at position j and last(j) to be the set of target-language ∆ Resulting phrase sequence score(∆) φ p φ (s, e 1 , t, em)ŵ(p) σ i p φ (s(σ i ), ws(σ i ), t, em)ŵ(p) + λ(e 1 |wt(σ i )) + η × |t(σ i ) + 1 − s| φ p σ i (s, e 1 , t(σ i ), wt(σ i ))ŵ(p) + λ(ws(σ i )|em) Figure 4 : Four operations that can extend a state T = (j, {σ 1 . . . σ r }) by a phrase p = (s, t, e 1 . . . e m ), and the scores incurred. We defineŵ(p) = κ(p) + m i=2 λ(e i (p)|e i−1 (p)). The functionŵ(p) includes the phrase translation model κ and the language model scores that can be computed using p alone. The weight η is the distortion penalty. + η × |t + 1 − s(σ i )| σ i p σ i (s(σ i ), ws(σ i ), t(σ i ), wt(σ i ))ŵ(p) + λ(e 1 |wt(σ i )) + η × |t(σ i ) + 1 − s| +λ(ws(σ i )|em) + η × |t + 1 − s(σ i )| Function valid(T ) Input: In addition, define singles(j) to be the set of phrases that translate the single word at position j: singles(j) = {p : s(p) = j and t(p) = j} Next, define h to be the smallest integer such that for all j, |first(j)| ≤ h, |last(j)| ≤ h, and |singles(j)| ≤ h. Thus h is a measure of the maximal ambiguity of any word x j in the input. State T = j, {σ 1 . . . σr} for i = 1 . . . r if s(σ i ) < j − d + 2 and s(σ i ) = 1 return FALSE if t(σ i ) < j − d return FALSE return TRUE Finally, for any position j, define start(j) to be the set of phrases starting at position j: start(j) = {p : s(p) = j} and define l to be the smallest integer such that for all j, |start(j)| ≤ l. Given these definitions we can state the following result: Theorem 1. The time complexity of the algorithm is O(nd!lh d+1 ). To prove this we need the following definition: Definition 4 (p-structures). For any finite set A of integers with |A| = k, a p-structure is a set of r ordered pairs {(s i , t i )} r i=1 that satisfies the following properties: 1) 0 ≤ r ≤ k; 2) for each i ∈ {1 . . . r}, s i ∈ A and t i ∈ A (both s i = t i and s i = t i are allowed); 3) for each j ∈ A, there is at most one index i ∈ {1 . . . r} such that (s i = j) or (t i = j) or (s i = j and t i = j). We use g(k) to denote the number of unique pstructures for a set A with |A| = k. We then have the following Lemmas: Lemma 4. The function g(k) satisfies g(0) = 0, g(1) = 2, and the following recurrence for k ≥ 2: g(k) = 2g(k − 1) + 2(n − 1)g(k − 2) Proof. The proof is in Appendix A. Lemma 5. Consider the function h(k) = k 2 × g(k). h(k) is in O((k − 2)!). Proof. The proof is in Appendix B. We can now prove the theorem: Proof of Theorem 1: First consider the number of states in the dynamic program. Each state is of the form (j, {σ 1 . . . σ r }) where the set {(s(σ i ), t(σ i ))} r i=1 is a p-structure over the set {1}∪ {(j − d) . . . d}. The number of possible values for {(s(σ i ), e(σ i ))} r i=1 is at most g(d + 2). For a fixed choice of {(s(σ i ), t(σ i ))} r i=1 we will argue that there are at most h d+1 possible values for {(w s (σ i ), w t (σ i ))} r i=1 . This follows because for each k ∈ {(j − d) . . . j} there are at most h possible choices: if there is some i such that s(σ i ) = k, and t(σ i ) = k, then the associated word w s (σ i ) is in the set first(k); alternatively if there is some i such that t(σ i ) = k, and s(σ i ) = k, then the associated word w t (σ i ) is in the set last(k); alternatively if there is some i such that s(σ i ) = t(σ i ) = k then the associated words w s (σ i ), w t (σ i ) must be the first/last word of some phrase in singles(k); alternatively there is no i such that s(σ i ) = k or t(σ i ) = k, in which case there is no choice associated with position k in the sentence. Hence there are at most h choices associated with each position k ∈ {(j − d) . . . j}, giving h d+1 choices in total. Combining these results, and noting that there are n choices of the variable j, implies that there are at most ng(d + 2)h d+1 states in the dynamic program. Now consider the number of transitions from any state. A transition is of the form ψ 1 pψ 2 as defined in Section 4.2.1. For a given state there are at most (d + 2) choices for ψ 1 and ψ 2 , and l choices for p, giving at most (d + 2) 2 l choices in total. Multiplying the upper bounds on the number of states and number of transitions for each state gives an upper bound on the runtime of the algorithm as O(ng(d + 2)h d+1 (d + 2) 2 l). Hence by Lemma 5 the runtime is O(nd!lh d+1 ) time. The bound g(d + 2) over the number of possible values for {(s(σ i ), e(σ i ))} r i=1 is somewhat loose, as the set of p-structures over {1} ∪ {(j − d) . . . d} in- cludes impossible values {(s i , t i )} r i=1 where for example there is no i such that s(σ i ) = 1. However the bound is tight enough to give the O(d!) runtime. Discussion We conclude the paper with discussion of some issues. First we describe how the dynamic programming structures we have described can be used in conjunction with beam search. Second, we give more analysis of the complexity of the widely-used decoding algorithm of Koehn et al. (2003) . Beam Search Beam search is widely used in phrase-based decoding; it can also be applied to our dynamic programming construction. We can replace the line for each state T ∈ T j in the algorithm in Figure 2 with for each state T ∈ beam(T j ) where beam is a function that returns a subset of T j , most often the highest scoring elements of T j under some scoring criterion. A key question concerns the choice of scoring function γ(T ) used to rank states. One proposal is to define γ(T ) = α(T ) + β(T ) where α(T ) is the score used in the dynamic program, and β(T ) = i:ws(σ i ) =<s> λ u (w s (σ i )). Here λ u (w) is the score of word w under a unigram language model. The β(T ) scores allow different states in T j , which have different words w s (σ i ) at the start of signatures, to be comparable: for example it compensates for the case where w s (σ i ) is a rare word, which will incur a low probability when the bigram w w s (σ i ) for some word w is constructed during search. The β(T ) values play a similar role to "future scores" in the algorithm of Koehn et al. (2003) . However in the Koehn et al. (2003) algorithm, different items in the same beam can translate different subsets of the input sentence, making futurescore estimation more involved. In our case all items in T j translate all words x 1 . . . x j inclusive, which may make comparison of different hypotheses more straightforward. Complexity of Decoding with Bit-string Representations A common method for decoding phrase-based models, as described in Koehn et al. (2003) , is to use beam search in conjunction with a search algorithm that 1) creates the target language string in strictly left-to-right order; 2) uses a bit string with bits b i ∈ {0, 1} for i = 1 . . . n representing at each point whether word i in the input has been translated. A natural question is whether the number of possible bit strings for a model with a fixed distortion limit d can grow exponentially quickly with respect to the length of the input sentence. This section gives an example that shows that this is indeed the case. Assume that our sentence length n is such that (n − 2)/4 is an integer. Assume as before x 1 = <s> and x n = </s>. For each k ∈ {0 . . . ((n − 2)/4 − 1)}, assume we have the following phrases for the words x 4k+2 . . . x 4k+5 : (4k + 2, 4k + 2, u k ) (4k + 3, 4k + 3, v k ) (4k + 4, 4k + 4, w k ) (4k + 5, 4k + 5, z k ) (4k + 4, 4k + 5, y k ) Note that the only source of ambiguity is for each k whether we use y k to translate the entire phrase x 4k+4 x 4k+5 , or whether we use w k and z k to translate x 4k+4 and x 4k+5 separately. With a distortion limit d ≥ 5, the number of possible bit strings in this example is at least 2 (n−2)/4 . This follows because for any setting of the variables b 4k+4 ∈ {0, 1} for k ∈ {0 . . . ((n − 2)/4 − 1)}, there is a valid derivation p 1 . . . p L such that the prefix p 1 . . . p l where l = 1 + (n − 2)/4 gives this bit string. Simply choose p 1 = (1, 1, <s>) and for l ∈ {0 . . . (n − 2)/4 − 1} choose p l +2 = (4l + 4, 4l + 5, y i ) if b 4k+4 = 1, p l +2 = (4l + 5, 4l + 5, z i ) otherwise. It can be verified that p 1 . . . p l is a valid prefix (there is a valid way to give a complete derivation from this prefix). As one example, for n = 10, and b 4 = 1 and b 8 = 0, a valid derivation is (1, 1, <s>)(4, 5, y 1 )(9, 9, z 2 )(7, 7, v 2 )(3, 3, v 1 ) (2, 2, u 1 )(6, 6, u 2 )(8, 8, w 2 )(10, 10, </s>) In this case the prefix (1, 1, <s>)(4, 5, y 1 )(9, 9, z 2 ) gives b 4 = 1 and b 8 = 0. Other values for b 4 and b 8 can be given by using (5, 5, z 1 ) in place of (4, 5, y 1 ), and (8, 9, y 2 ) in place of (9, 9, z 2 ), with the following phrases modified appropriately. Conclusion We have given a polynomial-time dynamic programming algorithm for phrase-based decoding with a fixed distortion limit. The algorithm uses a quite different representation of states from previous decoding algorithms, is easily amenable to beam search, and leads to a new perspective on phrase-based decoding. Future work should investigate the effectiveness of the algorithm in practice. A Proof of Lemma 4 Without loss of generality assume A = {1, 2, 3, . . . k}. We have g(1) = 2, because in this case the valid p-structures are {(1, 1)} and ∅. To calculate g(k) we can sum over four possibilities: Case 1: There are g(k − 1) p-structures with s i = t i = 1 for some i ∈ {1 . . . r}. This follows because once s i = t i = 1 for some i, there are g(k − 1) possible p-structures for the integers {2, 3, 4 . . . k}. Case 2: There are g(k − 1) p-structures such that s i = 1 and t i = 1 for all i ∈ {1 . . . r}. This follows because once s i = 1 and t i = 1 for all i, there are g(k − 1) possible p-structures for the integers {2, 3, 4 . . . k}. Case 3: There are (k − 1) × g(k − 2) p-structures such that there is some i ∈ {1 . . . r} with s i = 1 and t i = 1. This follows because for the i such that s i = 1, there are (k − 1) choices for the value for t i , and there are then g(k − 2) possible p-structures for the remaining integers in the set {1 . . . k}/{1, t i }. Case 4: There are (k − 1) × g(k − 2) p-structures such that there is some i ∈ {1 . . . r} with t i = 1 and s i = 1. This follows because for the i such that t i = 1, there are (k − 1) choices for the value for s i , and there are then g(k − 2) possible p-structures for the remaining integers in the set {1 . . . k}/{1, s i }. Summing over these possibilities gives the following recurrence: g(k) = 2g(k − 1) + 2(k − 1) × g(k − 2) B Proof of Lemma 5 Recall that h(k) = f (k) × g(k) where f (k) = k 2 . Define k 0 to be the smallest integer such that for all k ≥ k 0 , 2f (k) f (k − 1) + 2f (k) f (k − 2) · k − 1 k − 3 ≤ k − 2 (4) For f (k) = k 2 we have k 0 = 9. Now choose a constant c such that for all k ∈ {1 . . . (k 0 − 1)}, h(k) ≤ c × (k − 2)!. We will prove by induction that under these definitions of k 0 and c we have h(k) ≤ c(k − 2)! for all integers k, hence h(k) is in O((k − 2)!). For values k ≥ k 0 , we have h(k) = f (k)g(k) = 2f (k)g(k − 1) + 2f (k)(k − 1)g(k − 2) (5) = 2f (k) f (k − 1) h(k − 1) + 2f (k) f (k − 2) (k − 1)h(k − 2) ≤ 2cf (k) f (k − 1) + 2cf (k) f (k − 2) · k − 1 k − 3 (k − 3)! (6) ≤ c(k − 2)! (7) Eq. 5 follows from g(k) = 2g(k−1)+2(k−1)g(k− 2). Eq. 6 follows by the inductive hypothesis that h(k − 1) ≤ c(k − 3)! and h(k − 2) ≤ c(k − 4)!. Eq 7 follows because Eq. 4 holds for all k ≥ k 0 .
1 3 3.1 3.2 2. 2. 4 4.1 4.2 3. 4.2.1 4.5 5 5.1 5.2 6
Introduction Background: The Traveling Salesman Problem on Bandwidth-Limited Graphs Bandwidth-Limited TSPPs An Algorithm for Bandwidth-Limited TSPPs For any vertex For each path (connected component) in H j A Dynamic Programming Algorithm for Basic Definitions The Algorithm For all Definitions of δ(T ) and τ (T, ∆) A Bound on the Runtime of the Algorithm Discussion Beam Search Complexity of Decoding with Bit-string Representations Conclusion
Score a derivation
das muss unsere sorge gleichermaen sein
score(<s> this must also be our concern </s>)
I Phrase translation score: score(das muss, this must) +
I Language model score:
das muss unsere sorge gleichermaen sein
score(<s> this must also be our concern </s>)
I Phrase translation score: score(das muss, this must) +
I Language model score: