14

Symbolic MT 4: Tree-based MT

In this chapter, we will cover one final symbolic method for translation: tree-based machinetranslation.

14.1

Motivation for Tree-based Methods

Translation Examples
josei wa ringo wo tabeta

A Generalized Rule
NP1 wa NP2 wo tabeta

the woman ate an apple

NP1 ate NP2

sutekina aoi mafura wo maita josei wa ie kara motte kita sukoshi ureta ringo wo tabeta
the woman wearing a fetching blue scarf ate a slightly over-ripe apple that she brought from home

Figure 46: An example of translations with varying complexity that can nonetheless be expressed using a general translation rule with embedded variables NP1 and NP2 .
In the previous two chapters, we covered word-based methods and phrase-based methods,
which memorize correspondences between words and contiguous phrases, respectively. However, there are still several very useful correspondences between the languages that are beyond
the reach of these models.
Specifically, language has a hierarchical structure, where phrases can be arbitrarily simple,
or complex. An example of this is shown in Figure 46. Here, we can see that there are twosentence pairs, the first one simple and the second one complex. However, both have the sameunderlying structure of “noun phrase ate noun phrase” in English, which is the translationequivalent of “noun phrase wa noun phrase wo tabeta” in Japanese.
If we can capture this structure in the rules that our model uses, then we can expect that
it will be able to more accurately generalize to sentences with more complicated forms andimprove the ability of the model to capture the reordering between phrases in complex sentences. One way to express this is through the generalized translation rule shown in the upper
right corner of the Figure 46. This rule has words in each language, but also two variables
NP1 and NP2 , corresponding to the first and second verb phrase respectively, and we will
discuss models that capture these types of rules throughout the remainder of this chapter.
Before doing so, however, it is important to note that these rules cannot be captured in standard phrase-based translation models, as these models are restricted to handling contiguous
phrases, with no capacity to model embedded variables.

14.2

Probabilistic Context-Free Grammars and Parsing

Before taking the step to using these types of rules in translation, we first need to take a stepback and focus on the task of syntactic parsing, capturing the underlying syntactic structureof a sentence. While parsing is an extremely rich field in natural language processing, it is
not the focus of this course, so we’ll just cover a few points that are relevant to understandingtree-based models of translation here.
First, the goal of parsing is to go from a sentence, let’s say an English sentence E, into aparse tree T . As explained in Section 7.3, parse trees describe the structure of the sentence,
104

Tree

Generation Rules R
r1: S → NP VP
r8: VBD → chased
r2: NP → DET NP' r9: NP → DET NP'
r3: DET → ther10: DET → ther4: NP' → JJ NN
r11: NP' → JJ NN
r5: JJ → red
r12: JJ → little
r6: NN → cat
r13: NN → birdr7: VP → VBD NP

S
VP

NP

NP
NP'

DET JJNN

the red cat

NP'
VBD

DET JJ

NN

chased the little bird

Figure 47: A parse tree and the rules used in its derivation.
as in the example which is reproduced here in Figure 47 for convenience. Like other tasks
that we have handeled so far, we will define a probability P (T | E), and calculate the treethat maximizes this probabilityT̂ = argmax P (T | E).

(139)

T

There are a number of models to do so, including both discriminative models that model
the conditional probability P (T | E) directly [2] and generative models that model the joint
probability P (T, E) [4]. Here, we will discuss a very simple type of generative model: probabilistic context free grammars (PCFGs), which will help build up to models of translationthat use similar concepts.
The way a PCFG works is by breaking down the generation of the tree into a step-by-stepprocess consisting of applications of production rules R. These rules fully specify and are
fully specified by T and E. As shown in the right-hand side of Figure 47, the rules used inthis derivation take the form of:(r) (r)(r)s(l) ! s1 s2 . . . sN

(140)

(r)

where s(l) is the label of the parent, while sn are the labels of the right-hand side nodes. Morespecifically, there are two types of labels: non-terminals and terminals. Non-terminals
label internal nodes of the tree, usually represent phrase labels or part-of-speech tags, andare expressed with upper-case letters in diagrams (e.g. “NP” or “VP”). Terminals label leaf
nodes of the tree, usually represent the words themselves, and are expressed with lowercase
letters.
The probability is usually specified as the product of the conditional probabilities of theright hand side s(r) given the left hand side symbol s(l) :P (T, E) =

|R|
Y
i=1

(r)

(l)

P (si |si ).

(141)

The reason why we can use the conditional probability here is because at each time step, weknow the identity of parent node of the next rule to be generated, because it has alreadybeen generated in one of the previous steps.42 For example, taking a look at Figure 47, at
42
At time step 1, we assume that the identity of the root node is the same for all sentences, for example,“S” in the example.

105

the second time step, in r1 we just generated “S ! NP VP”, which indicates that at the(l)next time step we should be generating a rule for which s2 = NP. In general, we follow aleft-to-right, depth-first traversal of the tree when deciding the next node to expand, whichallows us to uniquely identify the next non-terminal to expand.
(r) (l)The next thing we need to consider is how to calculate probabilities P (si |si ). In mostcases, these probabilities are calculated from annotated data, where we already know thetree T . In this case, it is simple to calculate these probabilities using maximum likelihood
estimation:43(l) (r)c(si , si )(r) (l)P (si |si ) =
.
(142)
(l)
c(si )

14.3

Hypergraphs and Hypergraph Search

Now that we have a grammar that specifies rules and assigns each of them a probability, thenext question is, given a sentence E, how can we obtain its parse tree? The answer is thatthe algorithms we use to search for these parse trees are very similar to the Viterbi algorithm,
with one big change.
Specifically, the big change is that while the Viterbi algorithm as described before is analgorithm that attempts to find the shortest path through a graph, the algorithm for parsing
has to find a path through a hyper-graph. If we recall from Section 12.3, a graph edge in a
WFSA was defined as a previous node, next node, symbol, and score:g = hgp , gn , gx , gs i.

(143)

The only di↵erence between this edge in a graph and a hyper-edge in a hyper-graph is thata hyper-edge allows each edge to have multiple “previous” nodes, re-defining gp as a vectorof these nodes:
g = hgp , gn , gx , gs i.
(144)
To make this example more concrete, Figure 48 shows an example of two parse trees forthe famously ambiguous sentence “I saw a girl with a telescope”.44 In this example, each setof arrows joined together at the head is a hyper-edge. To give a few examples, the edge going
into the root “S1,8 ” node would be
g = h{NP1,2 , VP2,8 }, S1,8 , “S ! NP VP”,

log P (NP VP | S)i,(145)

and the edge from “i” to “PRP1,2 ” would be
g = h{i1,2 }, PRP1,2 , “PRP ! i”,

log P (i | PRP)i.

(146)

As can be seen in the bottom of Figure 48, hypergraphs can also be used to express
uncertainty. In this case, there are two nodes going into VP2,8 , and depending on which one
we choose, our interpretation of the sentence will change. Thus, like we performed search
43

It is also possible to estimate these probabilities in a semi-supervised or unsupervised manner [14] using
an algorithm called the “inside-outside algorithm”, but this is beyond the scope of these materials.
44
In the first example, “with a telescope” is part of the verb phrase, indicating that I used a telescope to see
a girl, while the second example has “a girl with a telescope” as a noun phrase, indicating that the girl is inpossession of a telescope.

106

Two Parse Trees
S
1,8

S
1,8
VP
2,8

VP
2,8

NP
3,8

PP
5,8
NP
1,2

NP
3,5

PRP VBD DT
1,2 2,3 3,4

NP
6,8
NN
4,5

IN
5,6

DT
6,7

NP
1,2
NN
7,8

NP
3,5

PRP VBD DT
1,2 2,3 3,4i saw a girl with a telescope

PP
5,8
NP
6,8

NN
4,5

IN
5,6

DT
6,7

NN
7,8

i saw a girl with a telescope

A Hypergraph Expressing Both Trees
S
1,8
VP
2,8

Two choices!
Choose red, get the first tree
Choose blue, get the second tree

NP
3,8

PP
5,8
NP
1,2
PRP VBD1,2 2,3

i saw

NP
6,8

NP
3,5
DT
3,4

NN
4,5

IN
5,6

DT
6,7

NN
7,8

a girl with a telescope

Figure 48: An example of two parse trees, and how they can be combined together into asingle hypergraph.
over graphs with the Viterbi algorithm in Section 12, we would like to perform search overhyper-graphs to find the best scoring parse. Luckily, we can do so with only minimal changes
to the overall algorithm. Recall that the forward score calculation in the Viterbi algorithm(Equation 116, reproduced here for convenience), calculated the score as follows:aiming2{g̃;g̃n =i}

a gp + g s .

(147)

The one change that we make to apply this to hyper-graphs that instead of adding the score
for a single predecessor, we sum over all predecessors in the hyper-edge:Xaiminaj + g s .
(148)
g2{g̃;g̃n =i}

j2gp

Putting this in the context of the trees in the figure, this means that we will calculate ai in abottom-up fashion, and every time we calculate the score for a node in the hyper-graph, wewill add its edge score to the sum of the scores for its child nodes. The following back-pointers
step of the Viterbi algorithm is also similar. In the standard Viterbi algorithm over graphs, if
we had a back-pointer bi = g, we would follow its previous node gp to read o↵ the best-scoring107

string in reverse order. In hyper-graphs, we instead read o↵ all the previous nodes in gp ,traversing in depth-first left-to-right order, which allows us to read o↵ the rules used in thebest-scoring tree in a similar fashion to the right side of Figure 47.
Now that we have the algorithm to perform search over hyper-graphs, the only questionis how to create a hyper-graph that allows us to perform the task that we want to do. One
example of a parsing algorithm, which we can also frame as a hyper-graph creation algorithm,
is the CKY algorithm [9, 15]. Interested readers can refer to [8] for precise details, but here
we give a brief sketch to demonstrate the process of creating a hyper-graph from a probabilistic
model and input sentence E.
The CKY algorithm can be used to parse grammars in Chomsky normal form (CNF),
which means that the right-hand side of all non-terminals consists of either a single nonterminal (word), or two non-terminals. 45 This indicates that all rules will either take theform P (x | A) for the former type, or P (BC | A) for the latter type. Algorithm 7 demonstrates
how we use E and the probabilities of rules in the grammar to build hyper-graph that expresses
the probabilities of all the possible trees. Briefly, Lines 2-6 step through all rules of the first
type, and Lines 7-19 step through all rules of the second type, adding edges that result in
non-zero paths through the hyper-graph, resulting in something like the bottom of Figure 48(although the hyper-graph in the figure is not in Chomsky normal form). We could thenrun the Viterbi-like algorithm described above to find the highest-scoring path through this
hyper-graph. This would tell us, for example, which of the two trees in the top of Figure 48
is the highest-scoring, and we could return this as our parse.

14.4

Synchronous Context-free Grammars

The PCFGs from the previous section allowed us to find a parse tree T from a sentence E, butthey are not a sequence-to-sequence model that can transform one sentence F into anothersentence E. However, one simple change to the PCFGs explained above can change them into
a form that makes it possible to perform translation. This new, expanded version of PCFGs
is called synchronous context-free grammars (SCFGs) [15, 3], which are very much likea standard PCFG, with the di↵erence that they specify rules that simultaneously generate
trees and sentences in two languages at a time.
The top section of Figure 49 shows an example of SCFG rules in Chomsky normal form.
In contrast to the standard PCFG rules from Equation 140, we now have left- and right-handside symbols for both the source and target languages:hs(F,l) , s(E,l) i ! hs(F,r) , s(E,r) i(149)

In addition, each symbol on the right-hand side is subscripted by a mapping between thesymbols indicating which corresponds to which, as shown in the figure.
These rules can capture a number of interesting phenomena. For example, they cancapture the fact that certain words translate into others (e.g. hthis, korei in the figure), as
well as systematic grammatical similarities or di↵erences between languages (e.g. hVP, VPi !
hVBZ1 NP2 , NP2 VP1 i in the figure indicates that the verb and object of a verb phrase arereordered between English and Japanese, capturing the di↵erence between the SVO word
order of English and SOV word order of Japanese).
45
It can be shown that all context-free grammars can be converted into equivalent ones in CNF, so this is
not a restriction on the expressivity of the model.

108

Algorithm 7 An example of how we can perform parsing using the CKY algorithm to createa hyper-graph|E|

1: procedure CKYHyperGraph(E = e1)

for i from 1 to |E|. Expand P (ei | Ai,i+1 ) do
for A 2 {Ã; P (ei | Ã) 6= 0} do
4:Add edge h{}, Ai,i+1 , “s ! ei ”, log P (ei | A)i5:
end for6:
end for7:
for k from 3 to |E| + 1. Expand P (Bi,j Cj,k | Ai,k ) do
8:for i from k 2 to 1 do
9:for j from i + 1 to k 1 do
10:
for All Bi,j existing in graph do
11:
for All Cj,k existing in graph do
12:
for Ai,k 2 {Ã; P (Bi,j Cj,k | Ã) 6= 0} do
13:
Add h{Bi,j , Cj,k }, Ai,k , “Ai,k ! Bi,j Cj,k ”, log P (Bi,j Cj,k | Ai,k )i14:
end for15:
end for16:
end for17:
end for18:
end for19:
end for
20: end procedure2:
3:

In addition, generating translations with this grammar is an extremely straight-forward
application of the CKY algorithm described in the previous section. Basically all we need to
do is parse the input sentence F using only the source side of the SCFG ruless(F,l) ! s(F,r) ,(150)

but keep track of which target-side symbols participated in the parse. We can then re-assemble
these target-side rules into a target-side tree, and read o↵ the leaves of the tree, which gives
us our translation.
However, the translations generated by this method are still stilted (“kore aru pen desu”
feels about as natural as “this is it pen” in English). The reason for this, as noted in the previous section on phrase-based translation, is because there are di↵erences between languages
that cannot be easily fit into simple word-to-word translations, and trying to generate translations. In order to resolve this problem, in synchronous grammars, it is common to use rulesthat move beyond CNF by using multi-word strings, or by mixing non-terminal and terminal
symbols, as shown in the bottom of Figure 49. This allows for much more natural handlingof various phenomena such as the insertion of function words (the grammatical marker “wa”
in Japanese, or determiner “a” in English) and the memorization of the types of phrases withempty variables, like the one mentioned at the beginning of this chapter in Figure Figure 46.
While the addition of the rules that are not in CNF precludes the use of the standard CKY
algorithm, there are other algorithms that can create the appropriate hyper-graphs with only
slightly more complexity: the CKY+ algorithm [1].
109A Synchronous Context-free Grammar in CNF
GrammarEnglish Tree

Japanese TreeS

S<S,S> → <NP1 VP2, NP1 VP2>
VP
VP
NP
NP
<NP,NP> → <PRN1, PRN1><NP,NP> → <DET1 NN2, DET1 NN2> PRN VBZ NP
PRN
NP
VB
<VP,VP> → <VBZ1 NP2, NP2 VB1>
DET NN
DET NN<PRN,PRN> → <this, kore>
thisis a pen kore aru pen desu
<PRN,PRN> → <he, kare><DET,DET> → <a, aru>
S
S
<DET,DET> → <the, sono>
VP<DET,DET> → <that, sono>
NP
VP
NP<NN,NN> → <pen, pen>
PRN VBZ NP
PRN
NP
VB
<NN,NN> → <pencil, enpitsu><VBZ,VB> → <is, desu>
DET NN
DET NN<VBZ,VB> → <eats, tabemasu>
heeats that pencil kare sono enpitsu tabemasu

Some More Flexible Synchronous Rules
S

S
VP

NP

<S,S> → <NP1 VP2, NP1 wa VP2>
<NN,NN> → <a pen, pen>
PRN
<S,S> → <NP1 eats NP2,
NP1 wa NP2 wo tabemasu>
this

VBZ

NP
NP

PRN
NN

is

a

pen

VP
NP

VB

NN
kore wa pen desu

Figure 49: An example of an SCFG in Chomsky normal form, which can generate translations
in two languages (top), along with some additional SCFG rules that are not in Chomsky
normal form, but are helpful in generating more fluent translations.
Of course, like phrase-based translation, it is necessary to extract these phrases from
data, which is possible to do with a minimal modification from the standard phrase-extract
method (Algorithm 6).
1. First, we run phrase-extract to find all contiguous phrases in F and E given alignments
A. In the case where we are using syntactic annotations such as NP or VP, these will belimited to only phrases that correspond to a syntactic phrase in the source and target
sentences (more on relaxing this assumption next section).
2. Next, for each extracted phrase pair hf , ei, we enumerate all sets of non-overlapping
sub-phrases that are contained within the bounds of hf , ei, replace these sub-phrases
with placeholders such such as NP1 or VP2 .
The exact algorithm can be found in more detail in [3].

14.5

Syntax or Not?

One important thing to note here is that up until now we have assumed that there is aconstraint that non-terminals correspond to well-defined grammatical categories such as “nounphrase (NP)” or “verb phrase (VP)” in one or both of the languages. In the ideal case, this110

has advantages; it makes it possible to ensure that the syntactic structures in the source
and target sentences are well-formed and align to each other. However, it also has several
disadvantages:• This constraint also has the side e↵ect of making it more difficult to produce correcttranslations in the case when syntax diverges between the two languages. This is truein the case of non-literal translations.
• In many cases, it is hard to get a good syntactic parser in one or both of the languages under consideration, and syntactic parsing errors can cause failure in extractionof translation rules.
• Even if we are able to obtain appropriate trees for both languages, syntax-based methods
still tend to be more brittle to alignment errors [12] due to the strict requirement thatboth the source and target side of the phrase pair must correspond exactly to a syntacticphrase.
Tree-to-tree:<S,S> → <he VB1 NP2, kare wa NP2 wo VB1>
String-to-tree: <X,S> → <he X1 X2, kare wa NP2 wo VB1>
Tree-to-string: <S,X> → <he VB1 NP , kare wa X wo X1>
2
2
String-to-string: <X,X> → <he X1 X , kare wa X wo X1>
2

2

Figure 50: Examples of various ways to use syntax in translation.
Thus, it is also common to remove this syntactic constraint to improve robustness of treebased translation models. As shown in Figure 50, this is done by replacing “NP” or “VP”
with a generic symbol “X” that can be any grammatical phrase, or can even correspond toa string that has no grammatical category at all. This leads to four combinations of source
and target syntax:
Tree-to-tree translation uses syntax on both sides, providing the strongest syntactic
constraint. While some works have found this method useful [16], they generally require more
complicated methods of absorbing brittleness in training through the consideration of multiple
parsing hypotheses.
String-to-tree translation uses syntax on only the target side [6], simultaneously performing translation and parsing on the target side. This has the advantage of relaxing the strong
constraints imposed by tree-to-tree translation, while still helping to ensure that the generated translation has some degree of grammatical constraint to ensure that it is well-formed.
The disadvantage of these methods is that because they consider a cubic combination of nonterminals (e.g. the loops in Lines 10-12 of Algorithm 7), translation time can be quite slow
compared to other methods.
Tree-to-string translation uses syntax on only the source side. This is generally done in
one of three ways:
Simultaneous parsing and translation , like string-to-tree translation, simultaneously
generates a syntactic parse tree (on the source side) and a translation. However, thismethod has the disadvantages of string-to-tree (slow computation time) without the111

advantages (imposing a constraint on the generated hypotheses to ensure better grammaticality) and is not widely used.
Pre-parsing followed by translation , in contrast, first parses the input sentence with ahigh-accuracy syntactic parser, then performs translation using only translation rulesthat match with this tree [10]. This has a strong advantage in that it greatly restricts
the space of hypotheses that the translator has to explore, greatly improving translation
speed, and if the parsing result is correct, accuracy. However, it is quite common for
syntactic parsers to make mistakes, degrading translation accuracy. As a remedy to thisproblem, forest-to-string translation encodes many parsing hypotheses in a hypergraph, and performs translation over these hypotheses [11].
Pre-ordering is one final method that is not exactly tree-based translation but shares its
motivation of incorporating syntax into translation. Specifically, this method works byfirst parsing the input sentence, re-ordering the constituents into an order closer to thatof the target language, then translating these re-ordered constituents using a standard
phrase-based MT system [5]. The advantage of this method is that it can help phrasebased systems overcome their problems with handling long-distance reordering while
making minimal changes to the translation engine itself. Disadvantages of error propagation are similar to those experienced in tree-to-string translation, and it is possible
to overcome these to some extent by considering multiple pre-ordering candidates when
performing translation [13].
String-to-string tree-based translation, also often called hierarchical phrase-basedtranslation or Hiero, takes the removal of syntax to the extreme: it uses no formal syntax
at all [3]. As a result, creation of Hiero models is as simple as that of phrase-based, being
possible in cases where no syntactic parser is available at all. However, it does lose thebenefit of constraining the hypothesis space using syntax, and the accuracy often lags behind
well-trained systems that use some sort of syntax on the source or target side.

14.6

Integration with Language Models

One detail that was glossed over up until this point is how we incorporate a language model
into translation. While the exact details are beyond the scope of this chapter (see [3] fordetails), the basic idea is that the language model probabilities are added to the graph as|E|soon as we know which words will be combined together consecutively in the output e1 .
An example of this is shown in Figure 51, where we calculate both the PCFG probability
similar to the hypergraph in Section 14.3, but also additionally calculate the probabilityof a 2-gram language model between the words. At each edge, we have both the PCFG
probability for the edge, and the probabilities for the boundaries between the children of eachnode For example, at VP2,8 , we will have the PCFG probability P (VBD NP PP | VP), as
well as P (a | saw) which calculates the probability of the words at the boundary between thefirst two child nodes, and P (with | girl) which calculates the probability of the words at theboundary between the second two child nodes. The reader can confirm that by combining
together the probabilities assigned to each edge, we can calculate the full PCFG and 2-gram
LM probability for the entire sentence accurately. While this is not exactly a translation

112

PT(NP VP | S) *PL(i|
) *PL(saw|i) *PL(
|telescope)S
1,8i * telescopeVP
2,8saw * telescope

PT(VBD NP PP | VP) *PL(a|saw) *PL(with|girl)NP
1,2i
PT(PRP | NP)

NP
PT(IN NP | PP) *3,5
PL(a|with)a, girl
PT(DT NN | NP) *PL(girl|a) DT
NN
IN
3,4
4,5
5,6
a
girl
with

VBD
PRP
2,3
1,2
saw
i
PT(i | PRP) PT(saw | VBD)

i

saw

PP
5,8
with * telescope

PT(a | DT)a

PT(girl | NN) PT(with | IN)

girl

with

NP
6,8
a, telescope PT(DT NN | NP) *PL(telescope|a)
DT
6,7
a

NN
7,8
telescopePT(a | DT)aPT(telescope | NN)

telescope

Figure 51: An example of calculating PCFG probabilities (red) and 2-gram language model
probabilities (blue) in the same hyper-graph.
model, the general principle would be the same in an SCFG, or any tree-based generation
model with the additional n-gram language model integrated.
One thing to note here is that in order to calculate the 2-gram model accurately, we needto keep track of the words on the furthest-most left and furthest-most right side of each
subtree as part of the information available to the node. This is because a 2-gram language
model needs one word of context et 1 (from the left node), to calculate the probability of thenext word et (from the right node). While incorporating a language model is essential for
improving translation accuracy, this has the unfortunate side e↵ect of expanding the search
space for the translation system, making translation less efficient. This is exacerbated evenmore when using higher order n-gram language models, when we must keep track of n 1
words of context on either side of each node. Luckily, there are relatively efficient approximate
search algorithms such as cube pruning [3] and hierarchical LM search [7], which allow us
to search even this complex search space more e↵ectively.

14.7

Tree Substitution Grammars

Finally, it is worth mentioning one more variety of grammar that is often used in translationin addition to SCFGs. This grammar, called a tree substitution grammar, focuses on thereplacement of full sub-trees that remember the inner structure of the tree being replaced, as
opposed to just flat SCFG rules. An example, contrasting to standard SCFG rules, can befound in Figure 52. As shown in this example, there are some cases in which remembering
the whole sub-tree can be useful. In the case in the figure, the PCFG rule “VBD1 NP2 with
NP3 ” does not allow us to disambiguate between the two translations corresponding to theambiguous “saw a girl with a telescope” in Figure 48. However, the TSG rule that explicitly
makes the distinction between the inner structure does allow us to make this distinction, andwill rule out one of the two translations based on the source-side parsing result.

113

SCFG

TSG

TargetNP →the white houseNP
DET NN NN
the white househowaito hausu

VP
VB1 NP2

X2 wo X1VP →VB1 NP2

VP
VBD1 NP2 PPVP →VBD1 NP2 with NP3
IN NP
with

VP →
VBD1 NP2 with NP3

X3 de X2 wo X1
3

VP
VBD1 NP
X3 no aru X2 wo X1NP2 PP
IN NP3
withFigure 52: A contrast between SCFG and tree substitution grammar rules.

14.8

Exercise

The exercise this time will be to create a translation system based on Hiero. This will include:• Modifying phrase extraction code from the previous chapter to make it possible to add
open spaces for variables.
• Write code to match these phrases to the input sentence.
• Write the CKY algorithm to find the best result.
Expansions to the model could include integrating an n-gram language model into search.
It might also be useful to incorporate syntax in some form, either through tree-to-string,
string-to-tree, or tree substitution grammar models.

References[1] Jean-Cédric Chappelier, Martin Rajman, et al. A generalized CYK algorithm for parsing stochastic CFG. In TAPD, pages 133–137, 1998.
[2] Eugene Charniak and Mark Johnson. Coarse-to-fine n-best parsing and maxent discriminative
reranking. In Proceedings of the 43rd Annual Meeting of the Association for Computational
Linguistics (ACL), pages 173–180, 2005.
[3] David Chiang. Hierarchical phrase-based translation. Computational Linguistics, 33(2):201–228,
2007.
[4] Michael Collins. Three generative, lexicalised models for statistical parsing. In Proceedings ofthe 35th Annual Meeting of the Association for Computational Linguistics (ACL), pages 16–23.
Association for Computational Linguistics, 1997.

114

[5] Michael Collins, Philipp Koehn, and Ivona Kucerova. Clause restructuring for statistical machinetranslation. In Proceedings of the 43rd Annual Meeting of the Association for Computational
Linguistics (ACL), pages 531–540, 2005.
[6] Michel Galley, Mark Hopkins, Kevin Knight, and Daniel Marcu. What’s in a translation rule? In
Proceedings of the 2004 Human Language Technology Conference of the North American Chapterof the Association for Computational Linguistics (HLT-NAACL), pages 273–280, 2004.
[7] Kenneth Heafield, Philipp Koehn, and Alon Lavie. Grouping language model boundary words
to speed k–best extraction from hypergraphs. In Proceedings of the 2013 Conference of theNorth American Chapter of the Association for Computational Linguistics: Human Language
Technologies (NAACL-HLT), pages 958–968, 2013.
[8] Daniel Jurafsky and James H. Martin. Speech and Language Processing. Pearson Education, 2
edition, 2008.
[9] Tadao Kasami. An efficient recognition and syntax analysis algorithm for context-free languages.
Technical report, DTIC Document, 1965.
[10] Yang Liu, Qun Liu, and Shouxun Lin. Tree-to-string alignment template for statistical machinetranslation. In Proceedings of the 44th Annual Meeting of the Association for Computational
Linguistics (ACL), pages 609–616, 2006.
[11] Haitao Mi, Liang Huang, and Qun Liu. Forest-based translation. In Proceedings of the 46th
Annual Meeting of the Association for Computational Linguistics (ACL), pages 192–199, 2008.
[12] Graham Neubig and Kevin Duh. On the elements of an accurate tree-to-string machine translation system. In Proceedings of the 52nd Annual Meeting of the Association for Computational
Linguistics (ACL), pages 143–149, 2014.
[13] Yusuke Oda, Taku Kudo, Tetsuji Nakagawa, and Taro Watanabe. Phrase-based machine translation using multiple preordering candidates. In Proceedings of the 26th International Conference
on Computational Linguistics (COLING), pages 1419–1428, 2016.
[14] Fernando Pereira and Yves Schabes. Inside-outside reestimation from partially bracketed corpora. In Proceedings of the 30th Annual Meeting of the Association for Computational Linguistics(ACL), pages 128–135, 1992.
[15] Daniel H Younger. Recognition and parsing of context-free languages in time n3. Informationand control, 10(2):189–208, 1967.
[16] Min Zhang, Hongfei Jiang, Aiti Aw, Haizhou Li, Chew Lim Tan, and Sheng Li. A tree sequencealignment-based tree-to-tree translation model. In Proceedings of the 46th Annual Meeting of the
Association for Computational Linguistics (ACL), pages 559–567, 2008.

115