Robust Bilingual Word Alignmentfor Machine Aided Translation
Ido Dagan

K e n n e t h W. Church

W i l l i a m A. Gale

AT&T Bell Laboratories
600 Mountain Avenue
Murray Hill, NJ 07974

Abstract
We have developed a new program called
word_align for aligning parallel text, text suchas the Canadian Hansards that are available intwo or more languages. The program takes theoutput of char_align (Church, 1993), a robust
alternative to sentence-based alignment programs, and applies word-level constraints using a version of Brown el al.'s Model 2 (Brown
et al., 1993), modified and extended to deal
with robustness issues. Word_align was tested
on a subset of Canadian Hansards supplied by
Simard (Simard et al., 1992). The combination of word_align plus char_align reduces thevariance (average square error) by a factor of
5 over char_align alone. More importantly, because word_align and char_align were designed
to work robustly on texts that are smaller andmore noisy than the Hansards, it has been possible to successfully deploy the programs at
AT&T Language Line Services, a commercial
translation service, to help them with difficult
terminology.

1Introduction

Aligning parallel texts has recently received considerable attention (Warwick et al., 1990; Brown et al.,1991a; Gale and Church, 1991b; Gale and Church,
1991a; Kay and Rosenschein, 1993; Simard et al.,
1992; Church, 1993; Kupiec, 1993; Matsumoto etal., 1993). These methods have been used in machine translation (Brown et al., 1990; Sadler, 1989),
terminology research and translation aids (Isabelle,
1992; Ogden and Gonzales, 1993), bilingual lexicography (Klavans and Tzoukermann, 1990), collocation studies (Smadja, 1992), word-sense disambiguation (Brown et al., 1991b; Gale et al., 1992)
and information retrieval in a multilingual environment (Landauer and Littman, 1990).
The information retrieval application may beof particular relevance to this audience. It would
be highly desirable for users to be able to express

queries in whatever language they chose and retrieve documents that may or may not have been
written in the same language as the query. Landauer and Littman used SVD analysis (or Latent
Semantic Indexing) on the Canadian Hansards,
parliamentary debates that are published in both
English and French, in order to estimate a kind ofsoft thesaurus. They then showed that these estimates could be used to retrieve documents appropriately in the bilingual condition where the queryand the document were written in different languages.
We have been most interested in the terminology application. How does Microsoft, or some othersoftware vendor, want "dialog box," "text box,"and "menu box" to be translated in their manuals? Considerable time is spent on terminology
questions, many of which have already been solved
by other translators working on similar texts. It
ought to be possible for a translator to point at
an instance of "dialog box" in the English versionof the Microsoft Windows manual and see how it
was translated in the French version of the same
manual. Alternatively, the translator can ask for abilingual concordance as shown in Figure 1. A PCbased terminology reuse tool is being developed to
do just exactly this. The tool depends cruciallyon the results of an alignment program to determine which parts of the source text correspond withwhich parts of the target text.
In working with the translators at AT&T Language Line Services, a commercial translation service, we discovered that we needed to completely
redesign our alignment programs in order to deal
more effectively with texts supplied by Language
Line's customers. All too often the texts are notavailable in electronic form, and may need to bescanned in and processed by an OCR (optical character recognition) device. Even if the texts areavailable in electronic form, it may not be worth
the effort to clean them up by hand. Real texts are
not like the bIansards; real texts are much smaller
and not nearly as clean as the ideal texts that havedisplayed . In
the SaveAs
affichaDana
Enregistrer Enregistrer
ainsi que son e x t e n s i o n . Dana la boite dedialogbox, thisarea is called Savedialogue boite
cette zone est
Enregistr
dialogue Enregistrer s o u s , cette zone eat appele

x Whenyou choose a command
button , theLorsquecommande b o u t o nsissez un b o u t o n de commande , la boite dedialogbox
closes and the commandis
dialogue boite
fermecommande execute
dialogue se ferme et le programme execute la tom, o .

buttonr boutonouvez. Dr doubl- lick the Control
cliquerlois
Systemeaussi
cliquer d e u x l o i ssurla c a s e

dumenu box. Or press ESC . If a dialog
box
menu caseSi
dialogue boite
menu Systeme . II eat egalement p o s s i b l e d ' a

d
p

o , .

o o .

' aa , ' Whenyou moveto an empty
Lorsqueplacezde Lorsque vous vous placez darts une zone de
ee

text
box
texte zone
texte vide

iiisertion point( flastung ve
insertion (, u n point d ' insertion ( barre vertic,

anFigure 1: A small sample of a bilingual concordance, based on the output of word_align. Four concordances
for the word "box" are shown, identifying three different translations for the word: boite, case, zone. The
concordances are selected from English and French versions of the Microsoft Windows manual (with someerrors introduced by OCR). There are three lines of text for each instance of "box": (1) English, (2) glosses,and (3) French. The glosses are selected from the French text (the third line), and are written underneaththe corresponding English words, as identified by word_align.
2.1.1

been used in previous studies.
To deal with these robustness issues, Church(1993) developed a character-based alignment
method called char_align. The method was intended as a replacement for sentence-based methods (e.g., (Brown et al., 1991a; Gale and Church,
1991b; Kay and Rosenschein, 1993)), which arevery sensitive to noise. This paper describes a
new program, called word_align, that starts withan initial "rough" alignment (e.g., the output ofchar_align or a sentence-based alignment method),and produces improved alignments by exploiting
constraints at the word-level. The alignment algorithm consists of two steps: (1) estimate translation probabilities, and (2) use these probabilities
to search for most probable alignment path. The
two steps are described in the following section.

2
2.1

The alignment

B r o w n et al.'s M o d e l

In the context of their statistical machine translation project (Brown et al., 1990), Brown et al.
estimate Pr(f[e), the probability that f, a sentence
in one language (say French), is the translation ofe, a sentence in the other language (say English).
Pr(fle ) is computed using the concept of alignment,
denoted by a, which is a set of connections between
each French word in f and the corresponding English word in e. A connection, which we will writea s c o B jf,e
, i , specifies that position j in f is connected
to position i in e. If a French word in f does notcorrespond to any English word in e, then it isconnected to the special word n~ll (position 0 ine). Notice that this model is directional, as eachFrench position is connected to exactly one position in the English sentence (which might be thenull word), and accordingly the number of connections in an alignment is equal to the length of theFrench sentence. However, an English word may beconnected to several words in the French sentence,or not connected at all.
Using alignments, the translation probability
for a pair of sentences is expressed as

Algorithm

Estimation of translation
probabilities

The translation probabilities are estimated using amethod based on Brown et al.'s Model 2 (1993),
which is summarized in the following subsection,
2.1.1. Then, in subsection 2.1.2, we describe
modifications that achieve three goals: (1) enable word_align to accept input which may not bealigned by sentence (e.g. char_align's output), (2)reduce the number of parameters that need to be
estimated, and (3) prepare the ground for the second step, the search for the best alignment (described in section 2.2).

Pr(fJe)-- Z

Pr(f, ale)

(1)

aE.A

where .A is the set of all combinatorially possiblealignments for the sentences f and e (calligraphic
font will be used to denote sets).
In their paper, Brown et al. present a series of
5 models of Pr(f[e). The firsttwo of these 5 models
are summarized here.

2Model1

It follows from the definition of Model 1 thatthe probability of a connection satisfies:

Model 1 assumes that Pr(f, ale) depends primarily on t(f[e), the probability that an occurrenceof the English word e is translated as the French
word f. That is,Pr(conf~e) =t• Ck=o t(filek)

Recall that fj refers to the French word in position
j of the French sentence f of length rn, and thatei refers to the English word in position i of the
English sentence e of length I. Also, rememberthat position 0 is reserved for the null word.
Equations 3 and 4.are used iteratively to estimate t(f[e). That is, we start with an initialguess
for t(fle). W e then evaluation the right hand sideof equation 4, and compute the probability of theconnections in the training set. Then we evaluate
equation 3, obtain new estimates for the translation probabilities, and repeat the process, until it
converges. This iterative process is known as theE M algorithm and has been shown to converge toa stationary point (Baum, 1972; Dempster et al.,1977). Moreover, Brown et aL show that ModelI has a unique maximum, and therefore, in thisspecial case, the E M algorithm is guaranteed toconverge to the m a x i m u m likelihood solution, anddoes not depend on the initial guess.

m

Pr(fle) = E Pr(f'ale) = E Cf.e I'I t(fjie*,)
ae.4

ae.4

j=l

(2)
where Cf,e, an irrelevant constant, accounts forcertain dependencies on sentence lengths, which
are not important for our purposes here. Except
for Cf.e, most of the notation is borrowed from
Brown ctal.. The variable, j, is used to refer to a
position in a French sentence, and the variable, i,
is used to refer to a position in an English sentence.
The expression, fj, is used to refer to the French
word in position j of a French sentence, and ei isused to refer to the English word in position i ofan English sentence. An alignment, a, is a set ofpairs (j, i), each of which connects a position in a
French sentence with a corresponding position in
an English sentence. The expression, aj, is used
to refer to the English position that is connectedto the French position j, and the expression, eoj,
is used to refer to the English word in position aj.
The variable, m, is used to denote the length of
the French sentence and the variable, 1, is used todenote the length of the English sentence.

Model 2Model 2 improves upon model 1 by making useof the positions within an alignment. For instance,
it is much more likely that the first word of an English sentence will be connected to a word near the
beginning of the corresponding French sentence,
than to some word near the end of the French sentence. Model 2 enhances Model 1 with the assuml>fe ,tion that the probability of a connection, conj,'~
depends also on j and i (the positions in f ande), as well as on m and I (the lengths of the twosentences). This dependence is expressed throughthe term a(ilj,m,l), which denotes the probability of connecting position j in a French sentence oflength m with position i in an English sentenceof length I. Since each French position is connected to exactly one English position, the constraint ~"~ti=0 a(i[j,m, I) = 1 should hold for all j,m and I. In place of equation 2, we now have:

There are quite a number of constraints that
could be used to estimate Pr(f, ale ). Model 1 depends primarily on the translation probabilities,t(f[e), and does not make use of constraints involving the positions within an alignment. These
constraints will be exploited in Model 2.
Brown e~ al. estimate t(f[e) on the basis of a
training set, a set of English and French sentencesthat have been aligned at the sentence level. Thosevalues of t(f[e) that maximize the probability ofthe training set are called the maximum likelihood
estimates. Brown et al. show that the m a x i m u mlikelihood estimates satisfy
Pr(con1,~e)(.fle) =)-~',o"f'eecoW'..,Pr(conf:e)

(4)

(3)

Pr(f[e)where CO.A/'t,e and CO./V'.e denote sets of connections: the set CO.A/'l,e contains all connectionsin the training data between f and e, and theset CO.N'. e contains all connections between some
French word and e. The probability of a connection, con~,~e, is the sum of the probabilities of allalignments that contain it. Notice that equation
3 satisfies the constraint: ~'~.!t(fle ) = 1, for eachEnglish word e.

=:EPr(f,
aEA

E
aE.4

ale)

(5)

i=l

where Of. e is an irrelevant constant.
As in Model 1, equation 3 holds for the maxi m u m likelihood estimates of the translation probabilities. The corresponding equation for the max-3

imum likelihood estimates of a(iIj, m, l) is:
E c o , f,eecoA,,-,, Pr(con f,'ie)a(ilj, m,l) ='"'"2 ¢ ° " f ; e e c ° X r :' Pr(conf,~)(6)

where CO.N'~S denotes the set of connections in the
training data between positions j and i in French
and English sentences of lengths m and 1, respectively. Similarly, CO.N'~. 'l denotes the set of connections between position j and some English position, in sentences of these lengths.
Instead of equation 4, we obtain the following
equation for the probability of a connection:f.e,t( fj [el)" a( ilj, rn, l)~"~k=0 t(fj [ek)-a(klj, rn, l)

Notice that Model 1 is a special case of Model 2,
where a(ilj , m, l) is held fixed at 1 + 1 "As before, the EM algorithm is used to compute maximum likelihood estimates for t(fle) anda(ilj, m, i) (using first equation 7, and then equations 3 and 6). However, in this case, Model 2does not have a unique maximum, and therefore
the results depend on the initial guesses. Brown
et al. therefore use Model 1 to obtain estimates fort(fle ) which do not depend on the initial guesses.
These values are then used as the initial guesses oft(fle ) in Model 2.
2.1.2

Our model

As mentioned in the introduction, we are interested
in aligning corpora that are smaller and noisierthan the Hansards. This implies severe practicalconstraints on the word alignment algorithm. As
mentioned earlier, we chose to start with the output of char_align because it is more robust than alternative sentence-based methods. This choice, ofcourse, requires certain modifications to the modelof Brown et al. to accommodate as input an initialrough alignment (such as produced by char_align)instead of pairs of aligned sentences.
It is also
useful to reduce the number of parameters that weare trying to estimate, because we have much lessdata and much more noise. The paragraphs below
describe our modifications which are intended tomeet these somewhat different requirements. The
two major modifications are: (a) replacing thesentence-by-sentence alignment with a single globalalignment for the entire corpus, and (b) replacing
the set of probabilities a(ilj, m, l) with a small setof offset probabilities.
Word_align starts with an initial rough alignment, I, which maps French positions to English
positions (if the mapping is partial, we use linear
extrapolation to make it complete). Our goal is tofind a global alignment, A, which is more accurate
than I. To achieve this goal, we first use I to determine which connections will be considered for A.
Let conj,i denote a connection between position jin the French corpus and position i in the English
corpus (the super-scripts in eon~,~ are omitted, as
there is no notion of sentences). We assume that
eonj,i is a possible connection only if i falls within alimited window which is centered around I(j), suchthat:
I ( j ) - w < i < I(j) + w(8)where w is a predetermined parameter specifying
the size of the window (we typically set w to 20
words). Connections that fall outside this window
are assumed to have a zero probability. This assumption replaces the assumption of Brown et al.
that connections which cross boundaries of aligned
sentences have a zero probability. In this newframework, equation 3 becomes:~-:~con,.,~co az ,., Pr( conj.i )t(fle) = ~ o , , . , e c o J ¢ . , Pr(conj,i)(9)where CO.h/'j,e and COA/'.,e are taken from the setof possible connections, as defined by (8).
Turning to Model 2, the parameters of the forma(ilj , rn, l) are somewhat more problematic. First,
since there are no sentence boundaries, there are no
direct equivalents for i, j, m and 1. Secondly, there
are too many parameters to be estimated, given thelimited size of our corpora Cone parameter for eachcombination of i , j , m and l). Fortunately, theseparameters are highly redundant. For example, it
is likely that a(i[j, m, l) will be very close to a(i +l l j + 1,re, l) and a(itj, rn+ 1,1+ 1).
In order to deal with these concerns, we replace probabilities of the form a(ilj, m, 1) with asmall set of offset probabilities. We use k to denotethe offset between i, an English position which corresponds to the French position j, and the English
position which the input alignment I connects to
j: k = i - I(j). An offset probability, o(k), is theprobability of having an offset k for some arbitrary
connection. According to (8), k ranges between- w and w. Thus, instead of equation 6, we haveo(k) = Y:~,,.,~coJ¢~ Pr(conj,i)(10)~---,¢~,.,~.CO.W Pr( e°ni,i )where COAl is the set of all connections and CO.hfk
is the set of all connections with offset k. Insteadof equation 7, we havePr(conj.i) =t(fl [el)" o(i - I ( j ) )X"I(#)+~ ~rr.[en). o(hI(j))
z..,h=i(j)_w -~a~(11)
The last three equations are used in the EM
algorithm in an iterative fashion as before to estimate the translation probabilities and the offset

probabilities. Table 1 and Figure 2 show some values that were estimated in this way. The input
consisted of a pair of Microsoft Windows manuals in English (125,000 words) and its equivalent in
French (143,000 words). Table 1 shows four Frenchwords and the four most likely translations, sortedby t(e]f) 1. Note that the correct translation(s) areusually near the front of the list, though there is atendency for the program to be confused by collocates such as "information about". Figure 2 shows
the probability estimates for offsets from the initial alignment I. Note that smaller offsets are more
likely than larger ones, as we would expect. Moreover, the distribution is reasonably close to normal,
as indicated by the dotted line, which was generated by a Gaussian with a mean of 0 and standard
deviation of 10 2 .

model, it is necessary to select the alignment A
that maximizes:I] t(file')'°(i-X(J))

Unfortunately, this method does not model the dependence between connections for French words
that are near one another. For example, the factthat the French position j was connected to theEnglish position i will not increase the probability
that j + 1 will be connected to an English position
near i. The absence of such dependence can easily
confuse the program, mainly in aligning adjacentoccurrences of the same word, which are common
in technical texts. Brown et al. introduce such dependence in their Model 4. We have selected asimpler alternative defined in terms of offset probabilities.

We have found it useful to make use of three filters to deal with robustness issues. Empirically, we
found that both high frequency and low frequency
words caused difficulties and therefore connections
involving these words are filtered out. The thresholds are set to exclude the most frequent function
words and punctuations, as well as words with lessthan 3 occurrences. In addition, following a similarfilter by Brown et al., small values of t(f[e) are set
to 0 after each iteration of the EM algorithm because these small values often correspond to inappropriate translations. Finally, connections to nullare ignored. Such connections model French words
that are often omitted in the English translation.
However, because of OCR errors and other sourcesof noise, it was decided that this phenomenon was
too difficult to model.

2.2.1

D e t e r m i n i n g t h e set o f r e l e v a n tconnections

The first step in finding the most probable alignment is to determine the relevant connections foreach French position. Relevant connections are required to be reasonably likely, that is, their translation probability (t(f[e)) should exceed some minimal threshold. Moreover, they are required to fallwithin a window between I(j) - w and I(j) + w in
the English corpus, as in the previous step (parameter estimation). We call a French position relevant
if it has at least one relevant connection. Eachalignment A then consists of exactly one connection for each relevant French position (the irrelevant positions are ignored).

Some words will not be aligned because of theseheuristics. It may not be necessary, however, toalign all words in order to meet the goal of helping translators (and lexicographers) with difficult
terminology.

2.2

(12)

con:.,eA

2.2.2

D e t e r m i n i n g the m o s t probablealignment

To model the dependency between connections in
an alignment, we assume that the offset of a connection is determined relative to the preceding connection in A, instead of relative to the initial alignment, I. For this purpose, we define A' (j) as a linear extrapolation from the preceding connection inA:

Finding the most probablealignment

The EM algorithm produces two sets of maximum likelihood probability estimates: translation
probabilities, t(fle), and offset probabilities, o(k).
Brown et al. select their preferred alignment simply
by choosing the most probable alignment according
to the maximum likelihood probabilities, relative tothe given sentence alignment. In the terms of ourNE

A ' ( j ) = A(jpre~) + (j - jp,e~) IVF(13)

where Jv,¢~ is the last French position before jwhich is aligned by A and NE and NF are thelengths of the English and French corpora. A ' ( j )thus predicts the connection of j , knowing the connection of jp,¢~ and assuming that the two languages have the same word order, instead of (12),the most probable alignment maximizes

l ln this example, French is used as the source language a~ad English as the taxget.
2The center of the estimated distribution seems
more fiat than in a normal distribution. This might
be explained by a higher tendency for local changes
of word order within phrases than for order changes
among phrases. This is merely a hypothesis, though,which requires further testing.

Heona,.~A

5t(fjlei), o ( i - A ' ( j ) ) .

(14)

French wordzone
fermerin formations
insertion

English translations (with probabilities)
box (0.58) area (0.28) want (0.04) In (0.02)
close (0.44) when (0.08) Close (0.07) selected (0.06)
information (0.66) about (0.15) For (0.12) see (0.04)
insertion (0.61) point (0.23) Edit (0.06) To (0.05)
Table 1: Estimated translation probabilities

o

o
0

0
0

c~
o
a.
0

0
0

-20

-10

0

10

20

OffsetFigure 2: Estimated offset probabilities (solid line) along with a Gaussian (dashed line) for comparison.
W e approximate the offset probabilities,0(k), relative to A', using the m a x i m u m likelihood estimates
which were computed relative to I (as described in
Section 2.1.2).
W e use a dynamic programming algorithm tofind the most probable alignment. This enables
us to know the value A(jp,e~) when dealing withposition j. To avoid connections with very low
probability (due to a large offset) we require thatt(fj [el). o(i-- A'(j)) exceeds a pre-specified threshold T s. If the threshold is not exceeded, theconnection is dropped from the alignment, andt(fjJei), o(i - A'(j)) for that connection is set to
T when computing (14). T can therefore be interpreted as a global setting of the probability thata random position will be connected to the null
3In fact, the threshold on t(f, le,), which is used todetermine the relevant connections (described in theprevious subsection), is used just as an efficient early
application of the threshold T. This early applicationis possible when t(f~le~)" o(k,,~==) < T, where k,~== isthe value of k with maximal o(k).

English word 4. A similar dynamic programming
approach was used by Gale and Church for wordalignment (Gale and Church, 1991a), to handle dependency between connections.

3

Evaluation

Word_align was first evaluated on a representative
sample of Canadian Hansards (160,000 words in
English and French). The sample was kindly provided by Simard et al., along with alignments ofsentence boundaries as determined by their panelof 8 judges (Simard et al., 1992).
Ten iterations of the EM algorithm were computed to estimate the parameters of the model.
The window size was set to 20 words in each direction, and the minimal threshold for t(fJe) was
set to 0.005.
We considered connections whose
source and target words had frequencies between 3
and 1700 (1700 is the highest frequency of a content word in the corpus. We thus excluded as many
4As mentioned earlier, we do not estimate directlytranslation probabilities for the null English word.

function words as possible, but no content words).
In this experiment, we used French as the source
language and English as the target language.
Figure 3 presents the alignment error rate ofword_align. It is compared with the error rate ofword_align's input, i.e. the initialrough alignment
which is produced by char_align. The errors are
sampled at sentence boundaries, and are measured
as the relative distance between the output of thealignment program and the "true" alignment, as
defined by the human judges 5. The histograms
present errors in the range of-20-20, which covers about 95% of the data s. It can be seen that
word_align decreases the error rate significantly(notice the different scales of the vertical axes). In
55% of the cases, there is no error in word_align's
output (distance of 0), in 73% the distance fromthe correct alignment is at most i, and in 84% the
distance is at most 3.
A second evaluation of word_align was performed on noisy technical documents, of the typetypically available for A T & T Language Line Services. W e used the English and French versions ofa manual of monitoring equipment (about 65,000
words), both scanned by an O C R device. W e sampled the English vocabulary with frequency between three and 450 occurrences, the same vocabulary that was used for alignment. W e sampled 100
types from the top fifthby frequency of the vocabulary (quintile),80 types from the second quintile,60
from the third, 40 from the fourth, and 20 from thebottom quintile. W e used this stratified sampling
because we wanted to make more accurate statements about our error rate by tokens than we would
have obtained from random sampling, or even fromequal weighting of the quintiles. After choosing the
300 types from the vocabulary list, one token foreach type was chosen at random from the corpus.
By hand, the best corresponding position in the
French version was chosen, to be compared with
word_align 's output.
Table 2 summarizes the results of the second
experiment. The figures indicate the expected relative frequency of each offset from the correct alignment. This relative frequency was computed according to the word frequencies in the stratified
sample. As shown in the table, for 60.5% of the tokens the alignment is accurate, and in 84% the offset from the correct alingment is at most 3. Thesefigures demonstrate the usefulness of word_align for
constructing bilingual lexicons, and its impact on

-20

-10

0

10

20

10

20

char_align errors (in wor(~s). . . . .

o
-20

-I0

nR Hno. . . .

0~t~cl_align errors (in wor~s)

Figure 3: Word_align reduces the variance (averagesquare error) by a factor of 5 over char_align alone(notice the vertical scales).
the quality of bilingual concordances (as in Figure 1). Indeed, using bilingual concordances which
are based on word_align's output, the translators at
AT&T Language Line Services are now producing
bilingual terminology lexicons at a rate of 60-100
terms per hour! This is compared with the previous
rate of about 30 terms per hour using char_align's
output, and an extremely lower rate before alignment tools were available.

4

Conclusions

Compared with other word alignment algorithms(Brown et al., 1993; Gale and Church, 1991a),word_align does not require sentence alignment as
input, and was shown to produce useful alignments for small and noisy corpora. Its robustness was achieved by modifying Brown et al.'s
Model 2 to handle an initial "rough" alignment,
reducing the number of parameters and introducing a dependency between alignments of adjacent
words. Taking the output of char_align as input, word_align produces significantly better, word-

5As explained eaxlier, word_align produces a partial
Mignment. For the purpose of the evaluation, we used
linear interpolation to get Mignments for all the positions in the sample.

6Recall that the window size we used is 20 words
in each direction, which means that word_align cannot
recover from larger errors in char_align.

7Offset fromcorrect alignment
0
1
2
3
4

Percentage
60.5%
10.8%

7.5%
5.2%
1.6%

Proc. of the DARPA Workshop on Speech andNatural Language.
William Gale and Kenneth Church. 1991b. A program for aligning sentences in bilingual corpora. In Proc. of the Annual Meeting of the
ACL.
William Gale, Kenneth Church, and David
Yarowsky. 1992. Using bilingual materials
to develop word sense disambiguation methods. In Proc. of the International Conferenceon Theoretical and Methodolgical Issues in Machine Translation.
P. Isabelle. 1992. Bi-textual aids for translators.
In Proc. of the Annual Conference of the UWCenter for the New OED and Text Research.
M. Kay and M. Rosenschein.
1 9 9 3 . Texttranslation alignment. Computational Linguistics. to appear.
J. Klavans and E. Tzoukermann. 1990. The bicord
system. In Proc. of COLING.
Julian Kupiec. 1993. An algorithm for finding
noun phrase correspondences in bilingual corpora. In Proc. of the Annual Meeting of the
ACL.
Thomas K. Landauer and Michael L. Littman.
1990. Fully automatic cross-language document retrieval using latent semantic indexing.
In Proc. of the Annual Conference of the UWCenter for the New OED and Text Research.
Yuji Matsumoto, Hiroyuki Ishimoto, Takehito Utsuro, and Makoto Nagao. 1993. Structural
matching of parallel texts. In Prac. of the Annual Meeting of the ACL.
William Ogden and Margarita Gonzaies. 1993.
Norm - a system for translators. Demonstration at ARPA Workshop on Human Language
Technology.
V. Sadler. 1989. Working with analogical semantics: Disambiguation techniques in DLT. Foris
Publications.
M. Simard, G. Foster, and P. Isabelle. 1992. Using cognates to align sentences in bilingual corpora. In Proc. of the International Conferenceon Theoretical and Methodolgical lssues in Machine Translation.
Frank Smadja. 1992. How to compile a bilingual
collocational lexicon automatically. In A A A I
Workshop on Statistically-based Natural Language Processing Techniques, July.
S. Warwick, J. Hajic, and G. Russell. 1990. Searching on tagged corpora: linguistically motivatedconcordance analysis. In Proc. of the Annual
Conference of the UW Center for the New
OED and Text Research.

Accumulative
percentage
60.5%
71.3%
78.8%
84%
85.6%

Table 2: Word_align's precision on noisy input,
scanned by an OCR device.
level, alignments on the kind of corpora that are
typically available to translators. This improvement increased the rate of constructing bilingual
terminology lexicons at AT&T Language Line Services by a factor of 2-3. In addition, the alignments may also be helpful to developers of lexicons
for machine translation systems. Word_align thus
provides an example how a model such as Brown
et al.'s Model 2, that was originally designed forresearch in statistical machine translation, can be
modified to achieve practical, though less ambitious, goals in the near term.

REFERENCES
L. E. Bantu. 1972. An inequality and an associated maximization technique in statistical estimation of probabilistic functions of a markov
process. Inequalities, 3:1-8.
P.

Brown,
J. Cooke,S. Della Pietra,
V. Della Pietra, F. Jelinek, R.L. Mercer, andRoossin P.S. 1990. A statistical approach tolanguage translation. Computational Linguistics, 16(2):79-85.

P. Brown, J. Lai, and R. Mercer. 1991a. Aligningsentences in parallel corpora. In Proc. of theAnnual Meeting of the ACL.
P. Brown, S. Della Pietra, V. Della Pietra, and
R. Mercer. 1991b. Word sense disambiguation
using statistical methods. In Proc. of the Annual Meeting of the A CL.
Peter Brown, Stephen Della Pietra, Vincent Della
Pietra, and Robert Mercer. 1993. The mathematics of machine translation: parameter estimation. Computational Linguistics. to appear.
Kenneth W. Church. 1993. Char_align: A programfor aligning parallel texts at character level. In
Proc. of the Annual Meeting of the ACL.
A. P. Dempster, N. M. Laird, and D. B. Rubin.
1977. Maximum liklihood from incomplete
data via the EM algorithm. Journal of theRoyal Statistical Society, 39(B):1-38.
William Gale and Kenneth Church. 1991a. Identifying word correspondence in parallel text. In

8