Theory of Alignment Generators and Applications to Statistical Machine Translation

1 Introduction

Statistical Machine Translation (SMT) is a data driven approach to Machine Translation [Brown et al., 1993], [AlOnaizan et al., 1999], [Berger et al., 1996]. Two of the fundamental problems in SMT are [Brown et al., 1993]:

Viterbi Alignment has a lot of applications in Natural Language Processing [Wang and Waibel, 1998], [Marcu and Wong, 2002]. While there exist simple polynomial time algorithms for computing the Viterbi Alignment for IBMModels 1-2, only heuristics are known for Models 3-5. Recently, [Udupa and Maji, 2005a] showed that the computation of Viterbi Alignment is NP-Hard for IBMModels 3-5.

Decoding algorithm is an essential component of all SMT systems [Wang and Waibel, 1997], [Tillman and Ney, 2000], [Och et al., 2001], [Germann et al., 2003], [Udupa et al., 2004]. The problem is known to be NP-Hard for IBMModels 1-5 when the language model is a bigram model [Knight, 1999].

Unless P = NP, it is unlikely that there exist polynomial time algorithms for either Viterbi Alignment or Decoding. Therefore, there is a lot of interest in finding fast heuristics to find acceptable solutions for the problems.

Previous approaches to the Viterbi Alignment problem have focussed on defining a graph over all possible alignments where the connectivity is based on local modifications. The best known algorithm for Decoding (both in terms of speed and translation quality) employs a greedy search algorithm. However, these approaches can look at only polynomial number of alignments in polynomial time.

In this paper, we characterize exponentially large subspaces of the solution space of Viterbi Alignment and Decoding. We propose polynomial time optimal dynamic programming algorithms to solve Viterbi Alignment and Decoding when the search space is restricted to a particular subspace. There are exponentially many such subspaces. So, we perform a local search on these subspaces under a suitable neighbourhood relation. Though, there is no polynomial bound on the number of iterations of the local search, experiments show that our algorithms procduce better solutions in significantly less time than the current algorithms.

We introduce the notion of an alignment generator in Section 2. There are m! distinct alignment generators (where m is the length of the source language sentence). Each alignment generator (gi, where 1 ≤ i ≤ m!) is associated with an exponentially large subspace of alignments (Ai). The solution space of Viterbi Alignment and Decoding can be written as the union of these subspaces. We next consider the graph induced on the set of Ais by a neighbourhood relation and perform local search on this graph. The explicit mathematical definition of Ai and the neighbourhood relation are presented in Section 3. We present polynomial time optimal algorithms for Viterbi Alignment and Decoding over a particular Ai (Section 4 and Section 5 respectively). Experiments show that our search algorithms produce better solutions taking subtantially less time than current algorithms (Section 6).

2 Preliminaries

IBMModels 1-5 assume that there is a hidden alignment between the source and target sentences.

Definition 1 (Alignment) An alignment is a function a(m, l) : {1, . . . ,m} → {0, 1, . . . , l}.

{1, . . . ,m} is the set of source positions and {0, 1, . . . , l} is the set of target positions. The target position 0 is known as the null position. We denote a(m, l) (j) by a(m, l) j . The fertility of the target position i in alignment a(m, l) is φi =

∑mj=1 δ (a(m, l) j , i). If φi = 0, then the target position i is an infertile position, otherwise it is a fertile position. Let {k, . . . , k + γ - 1} ⊆ {1, . . . , l} be the longest range of consecutive infertile positions, where γ ≥ 0. We say that alignment a(m, l) has an infertility width of γ.

Representation of Alignments: Since all source positions that are not connected to any of the target positions 1, . . . , l are assumed to be connected to the null position (0), we can represent an alignment, without loss of generality, as a set of tuples {(j, aj) |aj ̸= 0}. Let m′ = m - φ0. Thus, a sequence representation of an alignment has m′ tuples. By sorting the tuples in ascending order using the second field as the key, a(m, l) can now be represented as a sequence (j1, a(m, l) j1 ) . . . (jm′ , a(m, l) jm′ ) where the a(m, l) jk s are nondecreasing with increasing k. Note that there are (l +1)m possible alignments for a given m, l > 0. Let a(m, l) ∣∣(v,u) be the alignment {1, . . . , v} → {0, . . . , u} where all the tuples (j, a(m, l) j ) such that j > v or a(m, l) j > u have been removed.

Definition 2 (Generator) A generator is a bijection g(m) : {1, . . . ,m} → {1, . . . ,m}.

Representation of Generators: A generator g(m) can be represented as a sequence of tuples (j1, 1) . . . (jm,m). Note that there are m! different possible generators for a given m > 0. The identity function g(m) (j) = j is denoted by g(m) 0 .

Definition 3 (g(m) -→ a(m, l) ) An alignment a(m, l) (with tuple sequence (j1, a(m, l) j1 ) . . . (jm′ , a(m, l) jm′ )) is said to be generated by a generator g(m) (with tuple sequence (k1, 1) . . . (km,m)) if j1 . . . jm′ is a subsequence of k1 . . . km.

Note that the above definition does not take into account the infertility width of the alignment. Hence, we refine the above definition.

Definition 4 (g(m) γ -→ a(m, l) ) An alignment a(m, l) is said to be γ-generated by g(m) , if g(m) -→ a(m, l) and the infertility width of a(m, l) is at most γ.

Definition 5 (Ag(m) γ, l )

Thus, for every generator g(m) and integer γ ≥ 0 there is an associated family of alignments Ag(m) γ, l for a given l ∈ ◆. Further, Ag(m) γ,⋆ = ∪l Ag(m) γ, l .

Swap Operation: Let g(m) be a generator and (j1, 1) . . . (jk, k) . . . (jk′ , k′ ) . . . (jm,m) be its tuple sequence. The result of a SWAP operation on the kth and k′ th tuples in the sequence is another tuple sequence (j1, 1) . . . (jk′ , k) . . . (jk, k′ ) . . . (jm,m). The new tuple sequence defines a generator g′(m) . The relationship between any two generators is given by:

Lemma 1 If g(m) and g′(m) are two generators then g′(m) can be obtained from g(m) by a series of swap operations.

Proof: Follows from the properties of permutations. We can apply a sequence of Swap operators to modify any given generator g(m) to g(m) 0 . The source position rv (1 ≤ v ≤ m) in g(m) corresponds to the source position v in g(m) 0 . For brevity, we denote a sequence vi vi+1 . . . vj by vj i . The source sentence is represented by f m 1 and the target sentence is represented by el1 .

3 Framework

We now describe the common framework for solving Viterbi Alignment and Decoding. The solution space for Viterbi Alignment can be written as ∪g(m) Ag(m) l, l , and the solution space of Decoding can be approximated by ∪g(m) Ag(m) γ,⋆ for a large enough γ. The key idea is to find the optimal solution in an exponentially large subspace A corresponding to a generator (A = Ag(m) l, l andA = Ag(m) γ,⋆ for Viterbi Alignment and Decoding respectively). Given an optimal search algorithm for A, we use Lemma 1 to augment the search space. Our framework is as follows

1. Choose any generator g(m) as the initial generator.
2. Find the best solution for the problem in A.
3. Pick a better generator g′(m) via a swap operation on g(m) .
4. Repeat steps 2 and 3 until the solution cannot be improved further.

3.1 Algorithms

Viterbi Alignment

The algorithm for finding a good approximate solution to Viterbi Alignment employs a subroutine Viterbi For Generator to find the best solution in the exponentially large subspace defined by Ag(m) γ, l . The implementation of this subroutine is discussed in Section 4.

Algorithm 1 Viterbi Alignment

• 1: g(m) ← g(m) 0 . 2: while (true) do 3: a∗(m, l) = Viterbi For Generator (g(m) , f m 1 , el1 ). 4: Find an alignment a′(m, l) with higher score by using swap operations on a∗(m, l) . 5: if (a′(m, l) = NIL) then 6: break. 7: end if 8: g(m) ←A generator of a′(m, l) . 9: end while
• 10: Output a∗(m, l)

Decoding

Our algorithm for Decoding employs a subroutine Decode For Generator to find the best solution in the exponentially large subspace defined by Ag(m) γ,⋆ . The implementation of this subroutine is discussed in Section 5.

Algorithm 2 Decoding

• 1 ).

1: g(m) ← g(m) 0 . 2: while (true) do 3: 〈e∗l 1 , a∗(m, l) 〉 = Decode For Generator (g(m) , f m 4: Find an alignment a′(m, l) with higher score by using swap operations on a∗(m, l) and e∗l 1 . 5: if (a′(m, l) = NIL) then 6: break. 7: end if 8: g(m) ←A generator of a′(m, l) . 9: end while 10: Output e∗l 1 .

3.2 Theory of Generators

In this section, we prove some important results on generators.

Structure Transformation Operations

We define a set of structure transformation operations on generators. The application of each of these operations on a generator modifies the structure of a generator and produces an alignment. Without loss of generality 1 , we assume that the generator is the identity generator g(m) 0 and define the structural transformation operations on it. The tuple sequence for g(m) 0 is (1, 1) . . . (m,m). Given an alignment a(j-1,i) ∈ Ag(j-1) 0 γ,i with φi > 0, we explain the modifications introduced by each of these operators to the jth tuple.

1. SHRINK: Extend a(j-1,i) ∈ Ag(j-1) 0 γ,i to a(j,i) ∈ Ag(j) 0 γ,i such that a(j,i) j = 0.

By removing the infertile positions at the end, we obtain the following result:

Lemma 2 a(m, l) ∈ Ag(m) 0 γ, l and has at least one fertile position iff there exists s such that 0 ≤ s ≤ γ, a(m, l) ∣∣(m, l-s) ∈

1 by permuting the given generator g(m) to the identity generator g(m) 0

Theorem 1 If a(m,l-s) ∈ Ag(m) γ, l-s such that φl-s > 0 then it can be obtained from g(m) 0 by a series of SHRINK, MERGE and (γ, k)-GROW operations.

Proof: WLOG we assume that the generator is g(m) 0 . We provide a construction that has m phases. In the vth step, we construct a(m, l-s) ∣∣(v,u) from g(v) 0 in the following manner:

• We construct a(m, l-s) ∣∣(v-1,u) fromg(v-1) 0 and employ a SHRINK operation on the tuple (v, v) if a(m, l-s) v = 0.
• We construct a(m, l-s) ∣∣(v-1,u) fromg(v-1) 0 and employ a MERGE operation on the tuple (v, v) if φu > 1.
• If φu = 1: Let a(m, l-s) ∣∣(v,u) define φt = 0 for u - k ≤ t ≤ u - 1 and φu-k-1 > 0, where 0 ≤ k ≤ γ. Construct a(m, l-s) ∣∣v-1,u-k-1 from g(v-1) 0 and apply (γ, k)-GROW to the (v, v) tuple. (Note: If (u-k-1) = 0, then consider the alignment where {1, . . . , v - 1} are all aligned to the null position)

As these are the only possibilities in the vth phase, at the end of the mth phase we get a(m,l-s) .

The dynamic programs for Viterbi Alignment and Decoding are based on ideas in Lemma 2 and Theorem 1.

Lemma 3 ∣∣∣Ag(m) γ, l ∣∣∣ is given by the coefficient of xl in

Proof: Refer [Udupa and Maji, 2005b]

Proof: Substitute x = 1 in Equation 1 Decode For Generator finds the optimal solution over all possible alignments in Ag(m) γ,⋆ in polynomial time.

Proof: Refer [Udupa and Maji, 2005b] Viterbi For Generator finds the optimal solution over all possible alignments in Ag(m) γ, l in polynomial time.

tors. Define span (S) = ∪Ni=1 Ag(m)

i γ=l, l . Let p(.) be a polynomial. If l ≥ 2 and N = O(p(m)), then there exists an alignment a(m, l) such that a(m, l) ̸∈ span (S).

Proof: Refer [Udupa and Maji, 2005b] This Lemma shows that by considering any polynomially large set of generators we can not obtain the optimal solutions to either Viterbi Alignment or Decoding.

4 Viterbi Alignment

We now develop the algorithm for the subroutine Viterbi For Generator for IBM Model 3. Recall that this subroutine solves the following problem:

Our algorithm has a time complexity polynomial in m and l. Without loss of generality, we assume that g(m) = g(m) 0 . Note that a∗(m, l) ∣∣(m, l-s) (where 0 ≤ s ≤ γ and φl-s > 0) can be obtained from g0 using the structure transformation operations described in Section 3.2. Therefore, we build the Viterbi alignment from left to right. We scan the tuple sequence from left to right in m phases and in any phase we determine the best structure transformation operation for that phase.

We consider all possible partial alignments between f v 1 and eu1 , such that φu = ϕ > 0 and φ0 = ϕ0. Let B (u, v, ϕ0, ϕ) be the best partial alignment between f v 1 and eu1 and A(u, v, ϕ0, ϕ) be its score 2 . Here, ϕ0 is the number of French words aligned to e0 in the partial alignment.

The key idea here is to compute A(u, v, ϕ0, ϕ) and B (u, v, ϕ0, ϕ) recursively using Dynamic Programming. In the vth phase (corresponding to the tuple (v, v)), we consider each of the structure transformation operation.

1. SHRINK: If ϕ0 > 0, the SHRINK operation extends B (u, v -1, ϕ0 -1, φ) and the score of the resulting partial alignment is

1. MERGE: If ϕ > 0, the MERGE operation extends B (u, v -1, ϕ0, ϕ-1) and the score of the resulting partial alignment is

1. (γ, k)-GROW: Let

(γ, k)-GROW extends B (u-k -1, v -1, ϕ0, ϕ′ ) if ϕ = 1. If u - k - 1 > 0, the score of the resulting partial alignment is

where

2 A naive implementation of the table B(∗, ∗, ∗, ∗) takes O (m) size for each element. It can instead be implemented as a table of decisions and a pointer to the alignment that was extended to obtain it. This makes the size of each entry O (1).

If u-k -1 = 0, then

We choose that operation which gives the best score. As a result, B (u, v, ϕ0, ϕ) now represents the best partial alignment so far and A (u, v, ϕ0, ϕ) represents its score. We have,

We determine A (u, v, ϕ0, ϕ) and B (u, v, ϕ0, ϕ), for all 0 ≤ u ≤ l, 0 ≤ v ≤ m, 0 < ϕ ≤ ϕmax and 0 ≤ ϕ0 ≤ m2 . To complete the scores of the alignments, we multiply each A (u, m, ϕ0, ϕ) by ∏lp=u+1 n (0|ep) for l - γ ≤ u ≤ l. Let

The Viterbi Alignment is, therefore, B (ˆu,m, ˆ ϕ0, ˆ ϕ).

4.1 Time Complexity

The algorithm computes B (u, v, ϕ0, ϕ) and A (u, v, ϕ0, ϕ) and therefore, there are O (lm2ϕmax ) entries that need to be computed. Note that each of these entries is computed incrementally by a structure transformation operation.

• SHRINK operation requires O(1) time.
• MERGE operation requires O (1) time.
• (γ, k)-GROW (0 ≤ k ≤ γ) operation requires O (ϕmax) time for finding the best alignment and another O(1) time to update the score 3 .

Each iteration takes O(γϕmax) time. Computation of the tables A and B takes O (lm2γϕ2max ) time. The final step of finding the Viterbi alignment from the table entries takes O (mγϕmax) time 4 . Thus, the algorithm takes O (lm2γϕmax ) time. In practice, γ and ϕmax are constants. The time complexity of our algorithm is O (lm2 ).

4.2 Space Complexity

There are O (lm2ϕmax ) entries in each of the two tables. Assuming γ and ϕmax to be constants, the space complexity of Viterbi For Generator is O (lm2 ).

IBM Models 4 and 5 Extending this procedure for IBM Models 4 and 5 is easy and we leave it to the reader to figure out the modifications.

3 Note: The product ◗u-1 p=u-k n (0|ep) can be calculated incrementally for each k, so that at each iteration only one multiplication needs to be done. Similarly, the score ◗v-1 p=1 t (fp|NULL) can be calculated incrementally over the loop on v.

4 The factor ◗lu+1 n (0|ep) can be calculated incrementally over the loop of u. So, it takes O(1) time in each iteration.

5 Decoding

The algorithm for the subroutine Decode For Generator is similar in spirit to the algorithm for Viterbi For Generator. We provide the details for IBMModel 4 as it is the most popular choice for Decoding. We assume that the language model is a trigram model. VE is the target language vocabulary and IE ⊂ VE is the set of infertile words. Our algorithm employs Dynamic Programming and computes the following:

Let Hv1 (e′′ , e′ , ϕ0, ϕ, ρ) be the set of all partial hypotheses which are translations of f v 1 and have e′′ e′ as their last two words (ρ is the center of cept associated with e′ and ϕ > 0 is the fertility of e′ ). Observe that the scores of all partial hypothesis in Hv1 (e′′ , e′ , ϕ0, ϕ, ρ) are incremented by the same amount thereafter if the partial hypotheses are extended with the same sequence of operations. Therefore, for every Hv1 (v, e′′ , e′ , ϕ0, ϕ, ρ) it suffices to work only on the best partial hypothesis in it.

The initial partial hypothesis is h0 (., ., 0, 0, 0) with a score of p0m. Initially, the hypothesis set H has only one hypothesis, h0 (., ., 0, 0, 0). We scan the tuple sequence of g(m) 0 left to right in m phases and build the translation left to right. In the vth phase, we extend each partial hypothesis in H by employing the structure transformation operations. Let hv-1 1 (e′′ , e′ , ϕ0, ϕ, ρ) be the partial hypothesis which is being extended.

• SHRINK: We create a new partial hypothesis hv1 (e′′ , e′ , ϕ0 +1, ϕ, ρ) whose score is the score of hv-1 1 (e′′ , e′ , ϕ0, ϕ, ρ) times

in to Hv1 (e′′ , e′ , ϕ0 + 1, ϕ, ρ).

• MERGE: We create a new partial hypothesis hv1 (e′′ , e′ , ϕ0, ϕ+1, ρ) whose score is the score of hv-1 1 (e′′ , e′ , ϕ0, ϕ, ρ) times

Here, dold is the distortion probability score of the last tableau before expansion, dnew is the distortion probability of the expanded hypothesis after rv is inserted into the tableau and ρ′ is the new center of the cept associated with e′ . We put the new hypothesis into Hv1 (e′′ , e′ , ϕ0, ϕ + 1, ρ′ ).

• (γ, k)-GROW: We choose k words (e(1) , . . . , e(k) ) from IE and one word (e(k+1) ) from VE. We create a new partial hypothesis hv1 (e′ , e(1) , ϕ0, 1, rv ) if k = 0, hv1 (e(k) , e(k+1) , ϕ0, 1, rv ) otherwise. The score of this hypothesis is the score of hv-1 1 (e′′ , e′ , ϕ0, ϕ, ρ) times

At the end of the phase, we retain only the best hypothesis for each Hv1 (e′′ , e′ , ϕ0, ϕ, ρ). After m phases, we append at most γ infertile words to all hypotheses in H. The hypothesis with the best score in H is the output of the algorithm.

5.1 Time Complexity

At the beginning of vth phase, there are at most O (|VE|2 v2ϕmax) distinct partial hypotheses. It takes O(1) + O(ϕmax) + O(|IE|γ |VE| ϕmax) time to extend a hypothesis. Therefore, the algorithm takes totally O (|VE|3 |IE|γ m3ϕ2max) time. Now, since |VE|, |IE|, ϕmax and γ are assumed to be constant, the time complexity of the algorithm is O (m3 ).

5.2 Space Complexity

In each phase, we need O (|VE|2 m2ϕmax) space. Assuming |VE| and ϕmax to be constant, the space complexity is O (m2 ).

Extending this procedure for IBMModels 3 and 5 is easy.

6 Experiments and Results

6.1 Decoding

We trained the models using the GIZA++ tool [Och, 2001] for the translation direction French to English. For the current set of experiments, we set γ = 1 and ϕmax = 10. To compare our results with those of a state of the art decoder, we used the Greedy decoder [Marcu and Och, 2004]. Our test data consisted of a corpus of French sentences with sentence length in the range 06-10, 11-15, . . . , 56-60. Each sentence class had 100 French sentences. In Table 1, we compare the mean logscores (negative logarithm of the probability) of each of the length classes. Lower logscore indicates better probability score. We observe that the scores for our algorithm are (20%) better than the scores for Greedy algorithm. In the same table, we report the average time required for decoding for each sentence class. Our algorithm is much faster than the Greedy algorithm for most length classes. This demonstrates the power of our algorithm to search an exponentially large subspace in polynomial time.

We compare the NIST and BLEU scores of our solutions with the Greedy solutions. Our NIST scores are 14% better while our BLEU scores are 16% better than those of the Greedy solutions.

6.2 Viterbi Alignment

We compare our results with those of local search algorithm of GIZA++ [Och, 2001]. We set γ = 4 and ϕmax = 10. The initial generator for our algorithm is obtained from the solution of the local search algorithm.

In Table 3, we report the mean logscores of the alignments (for each length class) found by our algorithm and the local search algorithm. Our scores are about 5% better than those of the local search algorithm.

7 Conclusions

It would be interesting to see if the theory of alignment generators can be applied successfully for other problems in NLP.