12

Symbolic MT 2: Weighted Finite State Transducers

The previous section introduced a number of word-based translation models, and introduced
their parameter estimation methods and application to alignment. However, it intentionally
glossed over an important question: how to generate translations from them. This section
introduces a general framework for expressing our models graphs: weighted finite-statetransducers. It explains how to encode a simple translation model within this framework,and how this allows us to perform search.

12.1

Graphs and the Viterbi Algorithm

Before getting into the details of expressing our actual models, let’s look a little bit in the
abstract about an algorithm to do search over a graph. Without getting into the details about
how we obtained the graph, let’s say we have a graph such as the one in Figure 33. Eachedge of the graph represents a single word, with a weight representing whether the word is
likely to participate in a good translation candidate or not. Actually, in these sorts of graphs,
it is common to assume that higher weights are worse, and to search for the path through thegraph that has the lowest overall score. Thus, of the hypotheses encoded in this graph “thetax is” is the best, with the lowest score of 2.5.
taxes:taxes/3
the:the/1
01

that:that/2

tax:tax/1
axe:axe/1

2

3

is:is/0.5

4axes:axes/2

Figure 33: An example of a graph.
So how do we perform this search? While there are a number of ways, the most simple
and widely used is called the Viterbi algorithm [9]. This algorithm works in two steps, aforward calculation step, where we calculate the best path to each node in the graph, andthen a backtracking step, in which we follow back-pointers from one state to another.
In the forward calculation step, we step through the graph in topological order, visiting
each node in an order so that when visiting a node, all preceding nodes have already been
visited. For the initial node (“0” in the graph), we set its path score a0
0. Next, we define
all edges g as a tuple hgp , gn , gx , gs i, where gp is the previous node, gn is the next node, gx isthe word, and gs is its score (weight). When processing a single node, we step through all its
incoming edges, and calculate the minimum of the sum of the edge score and the path scoreof the preceding node,ai
min agp + gs .
(116)
g2{g̃;g̃n =i}

We also calculate a “back pointer” to the edge that resulted in this minimum score, which we
use to re-construct the highest scoring hypothesis at the end of the algorithm:biargmin agp + gs

g2{g̃;g̃n =i}

83

(117)

In the example above, the calculation would be equal to:a1 = a0 + gthe,s=0+1=1b1 = gthe
a2 = a0 + gthat,s=0+2=2b2 = gthat
a3 = min (a1 + gtax,s , a2 + gaxe,s )= min (1 + 1, 2 + 1) = 2
b3 = gtax
a4 = min (a1 + gtaxes,s , a2 + gaxes,s , a3 + gis,s )= min (1 + 3, 2 + 3, 2 + 0.5) = 2.5
b4 = gis
The next step is the back-pointer following step. In this step, we start at the final state(“4”) in the example, and iterate over the back-pointers gp of each edge, one by one. First,
we observe b4 , note the word gis,x is “is”, then step to gis,p = 3. We continue to follow b3 ,note the word “tax”, step to b1 , note the word “the”, step to b0 and terminate because we’vereached the beginning of the sentence. This leaves us with the words “is tax the”, which wethen reverse to obtain “the tax is”, our highest scoring hypothesis.

12.2

Weighted Finite State Automata and A Language Model

This sort of graph where g = hgp , gn , gx , gs i is also called a weighted finite state automaton(WFSA). These WFSAs can be used to express a wide variety of strings and their weightings
over them,35 and being able to think about various tasks in this way opens up possibilities fordoing a wide variety of processing in a single framework. The following explanation describes
some basic properties of WFSAs, and interested readers can reference [7] for a comprehensive
explanation.
One example of something that can be expressed as an WFSA is the smoothed n-gram
languages models described in Section 3. Let’s say that we have a 2-gram language modelinterpolated according to Equation 9 over the set of words “she”, “i”, “ate”, “an”, “a”,
“apple”, “peach”, “apricot” calculated from the following corpus:
she ate an apple
she ate a peachi ate an apricot(118)

We also assume that the interpolation coefficient is ↵ = 0.1.
35Specifically, they are able to express all regular languages, with a weight assigned to each string contained
therein.

84Given this, we will have two classes of probabilities, one where the bigram count is nonzero, such as P (apple | an), which (sparing the details) becomes the probability:
P (et = apple | et 1 = an) = (1↵)PM L (et = apple | et 1 = an) + ↵PM L (et = apple)
1
1= 0.9 + 0.1
2
15= 0.456.

We also have probabilities where where the bigram count is zero, these are essentially equal
to the unigram probability discounted by ↵. For example:
P (et = apple | et 1 = a) = (1↵)PM L (et = apple | et 1 = a) + ↵PM L (et = apple)
1= 0 + 0.1
15
= 0.006
/1.6094
apricot/2.7081<eps>/2.3026
apricot
apricot/0.7838<eps>/2.3026
anan/2.0149
apple/2.7081
/0.0834

apple/0.7838

NULL<eps>/2.3026
i/2.7081

i
/0apple

an/0.4888
/0.0834<eps>/2.3026<eps>/2.3026
/0.0834

ate/0.0834

ate/1.6094
i/1.182<eps>/2.3026
she/2.0149
she/0.4888<eps>/2.3026

ate

ate/0.0834

a/1.182

she<eps>/2.3026
peach/0.098

peach

a

<eps>/2.3026
a/2.7081
peach/2.7081

Figure 34: A 2-gram language model as a WFSA. Edge labels are “word/score”, where thescore is represented as a negative log probability. States are labeled with the context et 1
that the represent, where “NULL” represents unigrams. “hepsi” represents an ✏ edge, which
can be used to fall back from the unigram state to the bigram state.
The way we express this in a WFSA is shown in Figure 34. Each state label indicatesthe bigram context, so the state labeled “an” will represent probabilities P (et | et 1 = an).
Edges outgoing from a labeled state (with an edge label that is not “hepsi”, which we will getto later), represent negative log bigram probabilities. So for example, P (et = apple | et 1 =an) = 0.456, which indicates that the edge outgoing from the state “an” that is labeled with85

“apple” will have an edge weight of log P (et = apple | et 1 = an) ⇡ 0.7838. We also have astate labeled “NULL”, which represents all unigram probabilities P (et ). All outgoing edges
here represent a unigram probability.
Now, to the hepsi edges, which are called ✏ edges or ✏ transitions. ✏ edges are basicallyedges that we can follow at any time, without consuming a token in the input sequence. In
the case of language models, these transitions are used to express the fact that sometimes wewon’t have a transition that we can match for a particular context, and will instead want tofall back to a more general context using interpolation. For example, after “an” we may see
the word “peach” and want to calculate its probability. In this case, we would fall back fromthe “an” state to the “NULL” state using the ✏ edge, which incurs a score of log ↵ = 2.3026,
then follow the edge from the “NULL” state to the “peach” state, resulting in a probability oflog P (et = peach) = 2.7081. Of course, we could also create an edge directly from “an” to“peach” with a probability log ↵P (et = peach), but by using the ✏ edges we are able to avoid
explicitly enumerating all pairs of words, improving our memory efficiency while obtaining
the exact same results.

12.3

Weighted Finite State Transducers and a Translation Model

As could be seen from the previous section, WFSAs are able to express sets of strings withcorresponding scores over them. This is enough for when we want to express something
like a language model, but what if we want to express a translation model, that takes ina string and translates it into another string. This sort of string transduction can be donewith another formalism called weighted finite state transducers (WFSTs). WFSTs are
essentially similar to WFSAs with an addition symbol gy , leading to g = hgp , gn , gx , gy , gs i.
Thus, each edge takes in a symbol, outputs another symbol, and gives a score to this particulartransduction.
To give a very simple example, let’s assume a translation model that is even simpler than
IBM Model 1: one that calculates P (F | E) by taking one et at a time and independently
calculates the translation probability of the corresponding word ft
P (F | E) =

|E|
Y
t=1

P (ft | et ).

(119)

Assume that we have the following Spanish corpus equivalent to our English corpus in Equation 118:36
ella comió una manzana
ella comió un melocotónyo comi un albaricoque(120)

In this case, we can learn translation probabilities for each word, for example:
P (f = ella | e = she) = 1
36

(121)

Spanish allows dropping of the pronoun “yo” – equivalent to “i” – and a natural translation would probably
do so. But for the sake of simplicity, let’s leave it in to maintain the one-to-one relationship with the English
words, and we’ll deal with the problem of translations that are not one-to-one in a bit.

86

or
P (f = comió | e = ate) = 0.666(122)

P (f = comi | e = ate) = 0.333.

(123)
:
/0
un:a/0
comió:ate/0.4055
ella:she/0
comi:ate/1.0986
una:an/0.6931
melocotón:peach/0
yo:i/0manzana:apple/0
un:an/0.6931
albaricoque:apricot/0
0/0

Figure 35: A graph of a word-to-word translation model where P (F |E) =Q|E|

t=1 P (ft | et ).

To express these translation probabilities as a WFST, we define a WFST where the input
symbol gx is the word f , the output symbol gy is the word e, and the weight gs is the negativelog probability log P (f | e). Because translation probability is independent of the others,
we do not need to maintain the “state” of the translation model, and thus the we can justuse a single input and output state for every edge. Figure 35 shows an example of a WFST
representing this translation model.

12.4

Composing Multiple WFSTs

OK, so now we have a WFSTs calculating our language model probability P (E) as shown in
Figure 34, and translation model probability P (F | E) as shown in Figure 35. But, as in all
statistical translation models, what we really want to do is find the best translation:Ê = argmax P (E | F )E= argmax P (F | E)P (E).

(124)

E

This requires combining together the scores P (F | E) and P (E), which are each expressed as
separate WFSTs, so how do we do so?
Luckily, one of the benefits of the WFST framework is that it has general purpose algorithms that allow us to perform a number of common operations, independent of the underlying semantics of the WFSTs themselves. One of these operations is composition, which
combines together two consecutive operations into a single one. In other words, if we have two
WFSTs representing functions T1 (X), and T2 (x), if we perform composition we can create a
new WFST
T3 (X) = T2 (T1 (X)).
(125)
87

a:i/0.5
a:j/1.5
0

1

c:k/1
c:k

b:i/2
b:j/3

i:x/0.1

30

1

k:z/0.6

j:y/0.2

2

k:z/0.4
3

2
1,1
a:x/0.6

a:y/1.70,0

c:z/1.4
1,2

b:x/2.1
b:y/3.2

c:z/1.6
c:z/0.4

2,1

3,3

c:z/0.6

2,2

Figure 36: An example two simple transducers (top) composed into one (bottom).
This composition operation over transducers is generally expressed as T3 = T1 T2 .
The full detail of the composition algorithm is beyond the scope of this chapter (andinterested readers can reference [7]), but the general procedure is basically as follows:
1. Add a pair of initial nodes h0, 0i to a stack S.
2. For each pair of nodes hn1 , n2 i in S that has not already been processed, in topologicalorder:(a) Step over each pair of edges e1 and e2 where e1,p = n1 and e2,p = n2 respectively.
(b) If e1,y = e2,x , add hn1 , n2 i to the stack S, and create a new edge in T3 which
has a previous state e3,p = he1,p , e2,p i, next state e3,n = he1,n , e2,n i, input symbol
e3,x = e1,x , output symbol e3,y = e2,y , and score e3,s = e1,s + e2,s .
Figure 36 shows an example of the composition of two simple transducers. As an example
of combining two edges in the two transducers into a single edge in the output transducer,
we can see the edges e1 = h0, 1, a, j, 1.5i and e2 = h0, 2, j, y, 0.2i get composed into e3 =
hh0, 0i, h1, 2i, a, y, 1.7i.
Next, as a more concrete example, I’ll show an example from the translation model thatwe’ve been talking about so far. The WFST in Figure 35 can be viewed as a function
TP (F |E) (F ) that takes an input F , and outputs a graph encoding all possible E along with
their negative log probabilities P (F | E). The WFST in Figure 34 is a function TP (E) (E) thattakes in E and returns the same E but with the addition of a score representing the negativelog probability according to the bigram model. The composition of these two TP (F |E) TP (E) ,gives us a function that takes an input F and outputs candidate Es with scores that reflect
log P (F | E) log P (E), which we will call our TP (E|F ) . An example of this composedtransducer is shown in Figure 37. As we can see, the general structure of the WFST basically88
:
/1.6094<eps>:<eps>/2.3026

albaricoque:apricot/2.7081
una:an/2.708
albaricoque:apricot/0.7838

4
:
/0.0834<eps>:<eps>/2.3026<eps>:<eps>/2.3026
comi:ate/2.708
yo:i/1.182
yo:i/2.7081<eps>:<eps>/2.3026
03

un:an/1.1819

comió:ate/0.4889
comi:ate/1.182

5
manzana:apple/0.7838

una:an/1.1819

10

9/0

comió:ate/2.0149<eps>:<eps>/2.3026
:
/0.0834

1
comi:ate/1.182

ella:she/2.0149
ella:she/0.4888<eps>:<eps>/2.3026

2

comió:ate/0.4889
:
/0.0834

6
un:a/1.182

un:an/2.708
manzana:apple/2.7081<eps>:<eps>/2.3026

melocotón:peach/2.7081
melocotón:peach/0.098<eps>:<eps>/2.3026

7

8

un:a/2.7081<eps>:<eps>/2.3026

Figure 37: A WFST representing the negative log probability of E given F (TP (E|F ) ), createdby composing Figure 35 (TP (F |E) ) with Figure 34 (TP (E) ).
follows that in Figure 34, but with the addition of input representing Spanish words, anddi↵erent arcs when di↵erent Spanish words can translate into a single English word.
0

yo

1

comi

2

un

3

melocotón

4




5

Figure 38: A WFST representing the input TF .
Now, we can use this model to actually perform translations. The way we do so is bycreating another WFSA to represent the input TF ; the WFSA in Figure 38 is an example for“yo comi un melocotón”. This WFSA is then composed with TP (E|F ) to obtain a search graph,as shown in Figure 39, which encodes all of our possible translations, and paths through thelanguage model WFST. The actual graph we acquire through the composition process, on
the top of the figure, includes many ✏ transitions for every time we might fall back to theunigram context in the bigram language model. To make it easier to read and more compact,
we can also run an ✏ removal algorithms ([6]), which collapses the ✏ transitions to leave only
the best-scoring path, and giving us the easy-to-read graph at the bottom of the figure. From
this graph, we can see that we have two candidate translations “i ate a peach” and “i ate
an peach”. We can then run the Viterbi algorithm from Section 12.1 to obtain the bestscoring translation, which in this case will be “i ate a peach”, which was given much higher
probability by the language model than its counterpart using “an peach”.

89<eps>:<eps>/2.3026

1<eps>:<eps>/2.3026

yo:i/2.7081

yo:i/1.182

0

2

3

un:an/1.1819
comi:ate/2.708

comi:ate/1.182

un:an/2.708
4<eps>:<eps>/2.3026

5

un:a/1.182
01

comi:ate/1.182

2

4

un:an/1.1819<eps>:<eps>/2.3026<eps>:<eps>/2.3026

7

un:a/1.182

yo:i/1.182

6

un:a/2.7081

8<eps>:<eps>/2.3026

melocotón:peach/2.7081

melocotón:peach/0.098

910
:
/1.6094
:
/0.0834

11

melocotón:peach/0.098
melocotón:peach/5.0107

5
:
/0.0834

6

3

Figure 39: A WFST representing all of the candidate translations for input “yo comi un
melocotón”, with epsilon transitions (on top) and after these epsilon transitions have been
removed (on the bottom).

12.5

Other WFST Models

One thing that we should stress at this point is that the only problem-specific knowledge
encoded in the process above was used in the construction of our model transducers TP (E|F )and TP (E) . The other pieces of the previous section, specifically the Viterbi search algorithm
and the WFST composition algorithm, were both entirely general and equally applicable toother tasks.
Because of the elegant and extensible framework for processing symbol sequences provided
by WFSTs, they have seen wide use in a number of sequence-to-sequence processing tasks. We
will cover some examples from machine translation in the following chapter, and the following
is a far-from-comprehensive list of some examples from other areas:
Speech processing: WFSTs are behind many standard speech recognizers [7]. In this case,
it is common to create transducers such as an acoustic model TA that converts speechfeatures into phonemes, a pronunciation dictionary TD that converts phonemes intowords, and a language model TL . The whole speech recognition process is represented
as the composition of the input speech features TX with the composed model TA TD TL .
Down-stream tasks for speech: Because speech recognizers often are based on WFSTs, it
is also common to express down-stream tasks that consume speech as input as WFSTs
as well. Some examples include dialog management [4], which manages the flow of a
dialog system, and transcript cleaning [8], which converts a transcript with colloquial
expressions into a more clean and readable version for archival purposes.
Models of words: It is also common to use transducers to create models of the charactersin words for various purposes. For example, it is possible to do pronunciation estimation [3], estimating the pronunciation of words from their spelling, or processing of themorphology of words in morphologically rich languages [2].
One thing that the observant reader will note is that we have not discussed any more complicated model for machine translation than the simple word substitution model introducedin Section 12.3. The reason for this is that, despite their desirable properties, WFSTs do have
one relatively major weak point: it is not trivial to model problems that require reorderingof the elements in the input and output. As machine translation problems do require thisreordering, they will require slightly more involved methods for creating graphs, which wewill cover in the next chapter.

90

12.6

Other Properties of WFSTs

While this chapter touched on a variety of interesting properties of WFSTs and demonstrated
how they can be used to formalize models and search problems that we are interested in,
it just scratched the surface of this very elegant and extensible formalism. For example,
there is an interesting concept of semi-rings, which can be used to change the semanticsof the weights in the WFST, allowing us to perform a number of operations using the sameunderlying formalism and algorithms. For example, we can perform Viterbi search (using the“tropical” semi-ring [7]), marginalization over all of the paths in the graph (using the “log” or“probability semi-rings” [7]), calculation of expectations of feature weights for discriminative
training (usign the “expectation” semi-ring [5]), and calculation of edit distance between
strings (using the “edit-distance” semi-ring [1]). There are also other algorithms over WFSTs
in addition to the search, composition, and epsilon removal algorithms noted above. These
can allow us to perform unions or intersections over the languages expressed by WFSTs, or
efficiently compress complicated models consisting of the composition of multiple component
WFSTs into the most efficient form possible, greatly improving processing speed [7].

12.7

Exercise

The exercise this time will be to combine the simple word-to-word translation model introduced in Section 12.3 with the 2-gram language model that was introduced in Section 3. The
probabilities of the word-to-word translation model can be estimated with IBM Model 1, or
whatever variant you implemented in the exercise Section 11. This whole implementation
exercise will involve:• Creating WFSTs to represent the translation model and the 2-gram language model,
compiling them, and composing them together.
• Creating one WFSA for each input, composing it with the model WFST, and performing
shortest path to find the best answer.
Models can be implemented in OpenFST (http://openfst.org) which should makethings easier. OpenFST allows you to specify models in text format, compile them into binary,compose together WFSTs, perform shortest path search, and print the resulting output. Thiscan be done either through a command line interface, C++ code, or Python bindings.

References[1] Corinna Cortes, Patrick Ha↵ner, and Mehryar Mohri. Rational kernels. In Proceedings of the 15th
International Conference on Neural Information Processing Systems, pages 617–624. MIT Press,
2002.
[2] Markus Dreyer, Jason Smith, and Jason Eisner. Latent-variable modeling of string transductions
with finite-state methods. In Proceedings of the 2008 Conference on Empirical Methods in Natural
Language Processing (EMNLP), pages 1080–1089, 2008.
[3] Timothy J Hazen, I Lee Hetherington, Han Shu, and Karen Livescu. Pronunciation modeling using
a finite-state transducer representation. Speech Communication, 46(2):189–203, 2005.
[4] Chiori Hori, Kiyonori Ohtake, Teruhisa Misu, Hideki Kashioka, and Satoshi Nakamura. Weighted
finite state transducer based statistical dialog management. In Automatic Speech Recognition &Understanding, 2009. ASRU 2009. IEEE Workshop on, pages 490–495. IEEE, 2009.

91

[5] Zhifei Li and Jason Eisner. First- and second-order expectation semirings with applications tominimum-risk training on translation forests. In Proceedings of the 2009 Conference on Empirical
Methods in Natural Language Processing (EMNLP), pages 40–51, 2009.
[6] Mehryar Mohri. Generic epsilon-removal and input epsilon-normalization algorithms for weighted
transducers. International Journal of Foundations of Computer Science, 13(01):129–143, 2002.
[7] Mehryar Mohri, Fernando Pereira, and Michael Riley. Speech recognition with weighted finite-statetransducers. Handbook on speech processing and speech communication, Part E: Speech recognition,
2008.
[8] Graham Neubig, Shinsuke Mori, and Tatsuya Kawahara. A WFST-based log-linear framework for
speaking-style transformation. In Proceedings of the 10th Annual Conference of the International
Speech Communication Association (InterSpeech), pages 1495–1498, 2009.
[9] Andrew Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding
algorithm. IEEE transactions on Information Theory, 13(2):260–269, 1967.

92