See discussions, stats, and author profiles for this publication at: [Link]

net/publication/240719852

Context-Based Machine Translation

Article · January 2006

CITATIONS READS
45 187

7 authors, including:

Jaime G. Carbonell
Carnegie Mellon University
439 PUBLICATIONS 19,576 CITATIONS

SEE PROFILE

Some of the authors of this publication are also working on these related projects:

Surface Construction Labeling View project

History of Computer Science at Carnegie Mellon University View project

All content following this page was uploaded by Jaime G. Carbonell on 01 December 2014.

The user has requested enhancement of the downloaded file.

 Context-Based Machine Translation

Jaime Carbonell, Steve Klein, David Miller, Michael Steinbaum,

Tomer Grassiany, Jochen Frey
Meaningful Machines, LLC
{jaime, steve, dave, mike, tomer, jochen}@[Link]

Abstract ing corpora. The former can take person-decades to

write, debug and perfect the set of rules for reason-
Context-Based Machine Translation™ able quality translation (e.g., at the SYSTRAN
(CBMT) is a new paradigm for corpus- level), and acquiring parallel text for Statistical MT
based translation that requires no parallel and Example-Based MT in sufficient quantity for
text. Instead, CBMT relies on a light- comparable or better quality MT proves to be a
weight translation model utilizing a full- daunting task even for major language pairs. For
form bilingual dictionary and a sophisti- less-translated language pairs, accessible parallel
cated decoder using long-range context text is simply non-existent in sufficient quantities.
via long n-grams and cascaded overlap- To address these serious challenges, CBMT is be-
ping. The translation process is enhanced ing developed as a corpus-based method that re-
via in-language substitution of tokens and quires neither rules nor parallel corpora. Instead,
phrases, both for source and target, when CBMT requires an extensive monolingual target-
top candidates cannot be confirmed or re- text corpus (from 50 gigabytes to 1 terabyte), a
solved in decoding. Substitution utilizes a full-form bilingual dictionary, and optionally (to
synonym and near-synonym generator im- further improve translation quality) a smaller
plemented as a corpus-based unsupervised monolingual source-text corpus. Monolingual text
learning process. Decoding requires a very can be acquired in quantities by crawling the Web,
large target-language-only corpus, and extracting pure text from HTML, and indexing
while substitution in target can be per- such text in the manner required by the CBMT
formed using that same corpus, substitu- methods. The most time-consuming resource to
tion in source requires a separate (and build or acquire is the large-scale full-form bilin-
smaller) source monolingual corpus. gual dictionary for each language pair.
Spanish-to-English CBMT was tested on CBMT exhibits two advantages over tradi-
Spanish newswire text, achieving a BLEU tional MT approaches: (1) higher accuracy due to
score of 0.6462 in June 2006, the highest the model’s ability to decode long n-grams (as evi-
BLEU reported for any language pair. denced by the performance of CBMT’s still-
Further testing also shows that quality in- incomplete prototype which achieved a higher
creases above the reported score as the BLEU score in initial testing than any other MT
target corpus size increases and as diction- system to date), and (2) the ability to extend fairly
ary coverage of source words and phrases rapidly to new language pairs, including those that
becomes more complete. 1 lack sufficient parallel text. This paper describes
the fundamental new techniques underlying
1 Introduction CBMT, and presents results from Spanish-to-
English MT.
Traditional MT paradigms require either extensive In our AMTA-2002 paper (Abir et al.,
transfer-rule writing by linguists and computer sci- 2002), we introduced some of the component con-
entists or very large parallel (pre-translated) train- cepts on a general level, but details were not pro-
1
vided. This paper addresses several of those
The authors offer special acknowledgement to Eli concepts as well as others, and provides methodo-
Abir, co-founder of Meaningful Machines, who origi-
nally conceived of and participated in the development
logical details. Furthermore, our 2002 paper stated
of the methods described in this paper. that we were experimenting with a corpus-based

19
Proceedings of the 7th Conference of the Association for Machine Translation in the Americas, pages 19-28,
Cambridge, August 2006. ©2006 The Association for Machine Translation in the Americas
approach that does not require parallel text, which content words. Then, the large number of candi-
we referred to as “AIMT.” That process, which is date translations are resolved against their overlap-
now called “flooding,” is a key aspect of CBMT, ping neighbors to select the long n-grams whose
and is described in sections 2.1 and 3.2 below. suffix is also the prefix of its right neighbor, and
whose prefix is also the suffix of its left neighbor.
2 Basic CBMT Architecture The highest scoring translation (best long n-grams
and maximal overlap) is selected by the decoder.
The CBMT method consists of several modules, Of course, the method requires substantial back-
architected as shown in Figure 1. The principle is end machinery to index and match efficiently bil-
to produce many long n-gram candidate transla- lions of target n-grams, and other such support
tions by finding – in a huge target corpus – those tasks, which are not depicted in the primary func-
long n-grams that contain as many as possible of tional architecture diagram.
the potential word and phrase translations from the
dictionary, and as few as possible (if any) other

Figure 1. CBMT Basic Run-Time Architecture

Source Language

N-gramParser
Segmenter

INDEXED
RESOURCES N-GRAM BUILDERS
(Translation Model)
Bilingual
Dictionary Flooder CACHE DATABASE
(non-parallel text method)

Target Corpora Cross-Language

Edge Locker N-gram Database

Source Corpora
Synonym Generator Stored
N-gram Approved
N-gram
Gazetteers Substitution
Pairs
Pairs
N-gram Candidates Request

N-GRAM CONNECTOR
Overlap-based Decoder

Target Language

The primary functional components of CBMT are sentence position k; we select n-grams [w1,wn],
described below. [w2, w(n+1)], [w3,w(n+2)], etc. if, for example, n-
grams are based on a fixed number of words. The
2.1 Cross-Language “Flooding” n-gram size can also be based on the number of
This method generates target translation candidates non-function words in the n-gram – and since the
for highly overlapping source language n-grams number of intervening function words is not con-
which are generally between 4 and 8 words in stant – source n-gram size will vary. Regardless,
length (although n-grams can extend outside this the criteria for generating source overlapping n-
range). The n-grams are highly overlapping in grams from source input is an optimization pa-
source; let [wk,w(k+n)] denote the n-gram starting in rameter. Once the source n-grams are created, the

20
n-gram translation candidates are generated using a 2.3 Word and Phrasal Synonymy
bilingual dictionary as a source of candidate trans-
lations on the word level (and phrase level) and we This process uses an unsupervised method for con-
search a very large, multi-indexed target corpus for textual clustering over a monolingual corpus to
potentially corresponding target n-grams, i.e., generate word and phrasal synonyms and near-
those containing the maximal number of lexical synonyms. If the overlap decoder fails to find co-
translation candidates in context and the minimal herent sequences of overlapping target n-grams,
number (preferably zero) of spurious content then it asks for more candidate translations. One
words. Word order in the target n-gram may differ way to obtain such is to attempt translating a syno-
slightly or greatly from word order in the corre- nym or near-synonym n-gram of the problematic
sponding source n-gram. The flooding process has source passage, in case such translation is more
the role of translation model in that it populates globally coherent (i.e., decodes by overlapping
lattices with candidate translations, thus serving a right and left contexts). Similarly, we can substi-
similar function to the candidate translation lattice- tute target candidate n-grams with synonyms and
building by SMT and EBMT systems. Each source near-synonyms and use them in flooding. In es-
n-gram may generate hundreds of target language sence, replacing words or phrases with their syno-
n-gram translation candidates of varying length. nyms or near-synonyms on an as-needed basis
enlarges the search space of possible translations.
2.2 Source and Target Lattice Overlap To our knowledge, no other translation engine util-
This method combines the target n-gram transla- izes dynamically-generated word or phrasal syn-
tion candidates by finding maximal left and right onymy to optimize translation results.
overlaps with the translation candidates of the pre-
vious and following n-grams. Thus, the retained 3 CBMT Under the Hood
target n-grams are those that are contextually an- This section provides functional details regarding
chored both left and right. In other words, only the processes in operation.
contextually confirmed translations are kept and
scored by the overlap decoder. This process allows 3.1 Preprocessing: Preparation of Monolin-
context well beyond the n words of the n-gram to gual Corpus and Bilingual Dictionary
affect the selected translation. Individual cross-
language n-gram correspondences that overlap in CBMT requires a full-form bilingual dictionary
source and target are cached in the cross-language and a long-n-gram indexed target language corpus.
database to be used when that source language n- The former is generated semi-automatically from a
gram appears in input in the future, thus improving stem (citation form) bilingual dictionary, such as
MT speed. This step is akin to the lattice decoding those available commercially, plus a set of inflec-
process of SMT but extends the segments from tion rules (conjugations, pluralizations, etc.) for
trigrams to arbitrarily long n-grams (n typically source and target languages, including a cross-
ranges from 4 to 8) for greater accuracy. Further- language inflection mapping table (e.g., “imper-
more, CBMT’s confirmation process of requiring fait” in French maps to past progressive, simple
content word overlap on both sides of each long n- past, and the form “used to <Vinf>” in English). In
gram with preceding and succeeding n-grams is far addition, multi-word entries, even non-lexicalized
stricter than other language-model decoding, which ones, are added to the dictionary as they too are
only requires abutting short n-grams from the used in flooding, and actually improve flooding
translation model, scored by the target language efficiency and overall quality when they are
model, which consists of transition probabilities matched, which is seldom at present because our
derived from short n-grams (typically trigrams). In phrasal coverage is minimal, but growing. Our
fact, CBMT’s symbolic long-n-gram decoding Spanish-English dictionary has approximately
outputs a fairly reliable confidence score on trans- 100,000 stems, which expands to 1.8M inflected
lated passages, which optimizes human post-editor forms, each with potentially multiple translations
utility by permitting him or her to focus on prob- generated automatically from their stems and the
lematic passages. cross-language inflection mapping table.

21
 The long-n-gram indexed target language disjunction of all possible translations for the cor-
corpus requires first acquiring a large target lan- responding source word or in-dictionary phrase.
guage corpus, 50GB to 1TB via Web crawling, The flooding process is one of matching the CNF
language identification, HTML stripping, sentence to the indexed target language corpus, taking the
finding (vs. isolated words as in menu selections or top matches (typically 300-1000), where “top” is
small entries in tables), and multi-layered inverted defined as the highest density target language n-
indexing so long n-grams are quickly identified gram matches. The above process is repeated in a
from the component words. The index search re- moving window left-to-right (for Spanish, English,
quires best-first behavior, where retrieved n-grams etc.). For instance, we could start flooding with the
are those that contain the most component words at CNF from source sentence positions 1-to-7, then 2-
maximal proximity (minimal number spurious to-8, 3-to-9, etc. until the end of the sentence. Each
words). Techniques such as parallel search/merge n-gram search is a complex proximity query, but
expedite this otherwise most time-consuming step. does not require pre-generation of permutations to
Moreover, the index also requires left and right- find compact target n-grams without regard to tar-
context search for word and phrasal synonym find- get language order within the n-gram.
ing, as described in section 3.4.
3.3 Process 2: Target Language Lattice
3.2 Process 1: Source-to-Target Flooding Overlap Maximization

The first phase of the translation process segments Flooding produces a lattice of n-gram translation
the source sentence into overlapping n-grams of candidates at each position within the source sen-
typically 4 to 8 words each by moving a sliding tence. Then, the lattice candidates that fully over-
window across the sentence, advancing the n-gram lap are selected over those that partially overlap or
starting position one word at a time. Then for each fail to overlap at all, as illustrated by the high-
n-gram, the system looks up all possible transla- lighted segments below. The final translation result
tions for every source word or known phrase in the is the lattice walk that globally maximizes over-
bilingual dictionary. Then, the indexed target cor- laps, and that is composed of the highest match
pus is searched for n-grams that contain the maxi- density (the most source word translation
mal number of different potential translations of matches), longest target language n-grams. We
the source words (i.e., long target n-grams that have not yet sought the optimal parameter combi-
contain one translation option from as many source nation, but expect to do so based on a regression
words/phrases as possible, in any order). Essen- model applied to a per-language validation set. We
tially, an n-long conjunctive normal form (CNF) would expect to obtain an additional modest boost
expression is generated where each conjunct is the in our BLEU score by so doing.
Figure 2. Lattice Overlap

Parsed Overlapping Target Lattice Candidates

Source Segments
largest rebel group signed
group signed the largest contract
signed in November by the largest rebel group
Flood 1
Source Segment 1 rebel group signed a peace deal
Flood 2 a deal for peace signed by the rebel group
Source Segment 2 peace marchers group signed a deal
Source Segment 3
Flood 3 group signed a peace deal in November
in November the group rejected a peace deal
a group peace accord signed in November

Final Target Lattice largest rebel group signed a peace deal in November

22
In this manner, each word in the middle of the tar- grams whose translations failed to resolve, thereby
get language sentence is confirmed by having ap- expanding the space of candidate translation gen-
peared in multiple overlapping n-grams. Moreover, eration in a new dimension. The challenge, of
the coherence of the target sentence is strongly course, is to mine the source (or target) corpus for
favored by the fact that all long overlapping n- synonyms and near-synonyms dynamically and
grams come directly from human composed text in automatically.
the target language, and the flow is at least locally The synonym (and near-synonym) creation
coherent throughout the target sentence being process starts with a word or phrase, i.e., a short or
composed, not just inside the flooded n-grams, but long n-gram. Then, the process operates as fol-
in the transitions between them, as otherwise there lows:
would not have been overlap. Strong overlap,
Step 1: Perform a key-phrase/word-in-context
hence, is an absolutely key process for CBMT.
index (a generalization of a KWIC index), generat-
(Note that Figure 2 is a simplified example of the
ing paired left and right contexts that contain the
potential target candidates, with candidates com-
desired word or phrase anywhere in the massive
prised of only one of many possible target lan-
monolingual indexed corpus. Anywhere from
guage translations per source word.)
1,000 to 100,000 paired contexts, which may be of
variable length, are typically generated.
3.4 Process 3: Word and Phrasal Synonym
Generation Step 2: Tabulate, sort, and unify paired con-
texts (e.g., a long paired context that occurs multi-
The CBMT system has a method for identifying ple times ranks above one without repeat
synonyms or near-synonyms on a word or phrasal occurrences).
level using a monolingual corpus. This approach Step 3: Search the same massive indexed cor-
differs from others in that it does not require paral- pus, but this time with the contexts and only the
lel resources (Barzilay and McKeown, 2001; Lin et contexts (not with the original phrase, a.k.a. the
al., 2003; Callison-Burch et al., 2006) nor does it “middle”) to find other words and phrases that fit
use pre-determined sets of manually coded patterns the same contextual framework. Typically thou-
(Lin et al., 2003). In addition, CBMT’s methods sands are found.
work on the word as well as phrasal level. If the n-
grams in the above described lattice fail to overlap Step 4: Rank the list of new middles according
fully (or at all) we could flood deeper by retrieving to several criteria, such as number of different con-
more than the top m flooding candidates from the text pairs in common with the original word or
target language corpus, but that would compromise phrase, ratio of common contexts to total ones,
computational tractability and degrade the quality frequency of common contexts, length of common
of the results as we get fewer and fewer complete contexts, and others. The top ranked items gener-
matches. As an alternative, the CBMT system’s ally consist of synonyms and near-synonyms of the
word and phrasal synonym (and near-synonym) original word or phrase.
generation method can identify synonyms and
near-synonyms in source (or target) for the n-

[See Figure 3 on the next page for an illustration of these steps.]

23
Figure 3. Synonym (and Near-Synonym) Generation

. . . of changes in stock market conditions based on . . . . . . of changes in _____ conditions based on . . .

. . . out of the stock market and putting it . . . . . . out of the _____ and putting it . . .

. . . stabilized as the stock market rebounded for most . . . . . . stabilized as the _____ rebounded for most . . .

. . . changes in stock market wealth have become . . . . . . changes in _____ wealth have become . . .

. . . from the NASDAQ stock market before the opening . . . . . . from the NASDAQ _____ before the opening . . .

. . . to exit troubled stock market and banking ventures . . . . . . to exit troubled _____ and banking ventures . . .

. . . out of the stock market and money going . . . . . . out of the _____ and money going . . .

Find left and right contexts for Drop out the candidate phrase, leaving only
candidate phrase the left and right contexts

. . . of changes in market conditions based on . . .

. . . of changes in industry conditions based on . . .

. . . out of the market and putting it . . . Results for stock market

. . . out of the stock exchange and putting it . . .
market
. . . stabilized as the economy rebounded for most . . . stock exchange
. . . stabilized as the national market rebounded for most . . . national market
national market system
. . . changes in market wealth have become . . . stock market ®
. . . changes in personal wealth have become . . . exchange
major stock market
. . . from the NASDAQ stock exchange before the opening . . .
. . . from the NASDAQ stock market® before the opening . . .
Results are tabulated
. . . to exit troubled major stock market and banking ventures . . . and ranked
. . . to exit troubled federal government and banking ventures . . .

. . . out of the national market system and money going . . .

. . . out of the market and money going . . .

Then search for “new middles” that fit the same contextual “signature”.
Thousands of new middles can be found, and of course, multiple new
middles can be found for each signature.

Table 1. Other examples of synonyms and near-synonyms found by this method

Term Result
terrorist organization terrorist network / terrorist group / militant group / terror network
conference meeting / symposium / convention / briefing / workshop
bin laden bin ladin / bin-laden / osama bin laden / usama bin laden
nation’s largest country’s largest / nation’s biggest / nation’s leading
watchful eye direct supervision / close watch / stewardship / able leadership
it is safe to say it’s fair to say / it is important to note / you will find / I can say
it is important to recognize / it is well known / it is obvious

24
Notes: (1) The scores reported in this paper do not somewhat newer internal R&D or other versions of
reflect the use of the process described above (i.e., their systems.)
supplementing source words and phrases with their
synonyms or near-synonyms); (2) other uses of ƒ CBMT scored 0.6462 in June 2006 on news-
synonyms or near-synonyms in either source or wire text on a Spanish-to-English system pro-
target are beyond the scope of this paper. totype using still incomplete resources (i.e.,
v1.0 of the dictionary and only 52GB of in-
3.5 Process 4: Edge Locking dexed target text). On the same test set, SDL
scored 0.5610 and SYSTRAN scored 0.5551.
The flooding plus overlap processes are most reli-
able in the interior of each sentence, as each part of ƒ In development testing: CBMT scored 0.6950
the target translation is confirmed by multiple on a development set when expanded language
overlapping n-grams. However, the first word(s) resources were simulated: (1) a larger target
and last word(s) in the sentence are confirmed by corpus by online Web crawls seeded by dic-
one or just a few overlapping n-grams. To obtain tionary translations of the source words, and
better confirmation, we find other source sentences (2) a dictionary that contains all source words
where the starting n-gram from the original source (not tailored to the development set, just add-
sentence occurs in the interior of the newly found ing out-of-vocabulary (OOV) words).
sentences. By performing flooding-style analysis
with the original n-gram plus additional context ƒ The best published results for Arabic-English
words, we can assess whether the selected transla- and Chinese-English MT on the same news-
tion is consistent with the context, either confirm- wire genre are Google’s 2005 NIST scores:
ing the top ranking candidate or potentially 0.5137 (Arabic-English) and 0.3531 (Chinese-
preferring an otherwise lower-ranking candidate if English).
it satisfies more criteria. The same process is ap-
plied to the n-grams at the end of sentences (the Of course, we are well aware that compar-
right edge) and can be applied to natural breaks ing Arabic or Chinese MT to Spanish, even for
within a sentence, i.e., n-grams surrounding com- texts in the same genre, is not an apples-to-apples
mas or other interior punctuation. In this way, we comparison. Translation from those languages into
achieve confirmation for “edges” that is close-to- English is more challenging than from another
comparable to that of the interior of the sentence. European language into English. Nevertheless,
CBMT, even in its current prototype form, outper-
4 CBMT Results on the BLEU Metric formed others: commercial Spanish-to-English,
and research Arabic- and Chinese-to-English,
CBMT was scored on newswire Spanish texts, us- which demonstrates the power of the new CBMT
ing the NIST BLEU scoring package, and follow- technology. An aspect of CBMT is that the more
ing the NIST procedure. Since NIST evaluations context-dependent and less syntax-dependent the
are for Arabic and Chinese, and the CBMT proto- language, the greater advantage CBMT has over
type is for Spanish, we ran our own test with held- other approaches, especially over Rule-Based MT.
out texts (different from development sets) and An interesting question is how much better
four reference translations for each sentence. 2 For can CBMT get? Can it reach human-quality trans-
comparison to other MT systems in Spanish-to- lation, at least with respect to the BLEU score?
English, we ran the exact same test for the Web- We can address that question partially by simulat-
available versions of SDL and SYSTRAN. (Ca- ing a complete dictionary and a larger target-
veat: It is possible that these companies have language corpus. For the former, we simply added
OOV words from the test corpus to the bilingual
2
The Spanish test set consists of 89 newswire sentences from dictionary, without letting the dictionary builders
diverse sources (shortest sentence: 8 words; average: 27 see the test corpus in order to avoid biasing for the
words; longest: 66 words). The Spanish sentences and their right translation in that context. For the latter, we
four English reference translations may be obtained gratis by
e-mailing: mike [-at-] [Link]. crawled the Web with the possible dictionary

25
translations of the source words in the text. This nificant positive impact. As for other language pair
simulates having a larger corpus (as the Web is testing, preliminary results on small-scale Arabic
exactly that), though it is not practical to do large and French development systems are positive.
numbers of targeted Web crawls for each new text How about algorithmic improvements? We
to translate in an operational setting. This resource- offer the figure below, showing how our BLEU
enhancement process raised our BLEU score to scores have been climbing during our R&D proc-
0.6950, demonstrating that there is room to im- ess. Of course, extrapolation is unreliable, but we
prove by resource accretion. Although this “non- are striving to reach the lower reaches of the hu-
blind” result did have the benefit of more complete man performance range as measured by BLEU.
resources, it did not simulate phrase inclusion in
the dictionary, which is anticipated to have a sig-

Figure 4. CBMT Scoring Over Time

0.85
0.8
Human Scoring Range
0.7 0.6950
BLEU SCORES

0.6456
0.6373 0.6462
0.6129
0.5979 0.6267
0.6 0.6144 0.6165
0.5670 0.5953

Blind
0.5
Non-Blind

0.4
0.3743

0.3
Jan 04 Apr 04 Jul 04 Oct 04 Jan 05 Apr 05 Jul 05 Oct 05 Jan 06 Apr 06 Jul 06

Figure 4 Notes: (1) Tests were run on newswire text. (2) Tests used four reference sentences. (3) Non-
Blind tests were run on a development set and under conditions as described in section 4. (4) Blind tests
were conducted under standard testing conditions. (5) Blind tests were run on an incomplete set of re-
sources, as described above. (6) The Blind test scoring 0.6462 used an indexed target corpus of 52GB;
the Blind test scoring 0.6373 used 42GB; other Blind tests used 30GB. The improvements from 0.6267
to 0.6462 in Blind tests were primarily due to corpus size increases, however, bug-fixing was also a fac-
tor. The earlier Blind test improvements from 0.5953 to 0.6267 were due to bug fixes/algorithmic im-
provements. (7) Non-Blind test improvements are largely due to algorithmic development. (8) We
scored each human reference set against the other 3 references plus an additional human set so that each
was scored against 4 references total. The human scores ranged from 0.7172 to 0.7941.

chins (1986) and Nagao (1989) give excellent

5 Related Work overviews. In contrast, interlingua-based systems
perform multi-phase analysis and synthesis, but
Traditional Rule-Based MT systems are comprised reduce or eliminate the need for a transfer compo-
of an analysis phase (typically a string-to-tree nent (Uchida and Zhu, 1993; Carbonell et al.,
parser), a transfer phase (typically a rule-based 1994; Mitamura et al., 1994). Both methods rely
tree-to-tree transformer), and a synthesis phase on extensive human knowledge engineering in all
(typically a tree-to-linear-string generator). Hut- phases. CBMT is radically different.

26
 Corpus-based systems, such as Example- Example 1 Input: Un coche bomba estalla junto a
Based MT (Nagao, 1984; Sumita and Iida, 1991; una comisaría de policía en Bagdad
Brown et al., 2003; Kim et al., 2005; Doi et al., ƒ CBMT: a car bomb explodes next to a police
2005) and Statistical MT (Brown et al., 1990; Ya- station in baghdad
mada and Knight, 2002; Och, 2005) are comprised
of a translation model and a target language model. ƒ SYSTRAN: A car pump explodes next to a
The two components are readily evident, for in- police station of police in Bagdad
stance, in the original IBM Candide system
(Brown et al., 1990), where the central equation is: Example 2 Input: Hamas anunció este jueves el
Topt = Arg max[P(S | Ti ) P(Ti )]
fin de su cese del fuego con Israel
Ti ∈LanguageT ƒ CBMT: hamas announced thursday the end of
In other words, the optimal target language sen- the cease fire with israel
tence is the one that maximizes the product of the ƒ SYSTRAN: Hamas announced east Thursday
translation model (the first probability) and the the aim of its cease-fire with Israel
target language model (the second probability).
The decoder is the process that estimates Topt. The Example 3 Input: Un soldado de Estados Unidos
translation model is typically trained from a large murió y otros dos resultaron heridos este lunes por
(e.g., 100MB) sentence-aligned parallel corpus of el estallido de un artefacto explosivo improvisado
professionally translated text. The target language en el centro de Bagdad, dijeron funcionarios
model is typically trained from a much larger militares estadounidenses
monolingual corpus. ƒ CBMT: a united states soldier died and two oth-
CBMT is also a corpus-based approach, ers were injured monday by the explosion of an
closest to EBMT, but radically different in terms of improvised explosive device in the heart of
requiring no parallel text whatsoever. In a sense, it baghdad, american military officials said
is reminiscent of the old “Shake and Bake” idea
(Whitelock, 1992), the newer EXERGE method in ƒ SYSTRAN: A soldier of the wounded United
generation-heavy MT (Habash, 2003) and also the States died and other two were east Monday by
METIS work (Dirix et al., 2005) at a very abstract the outbreak from an improvised explosive de-
level of letting the target language establish lexical vice in the center of Bagdad, said American mili-
order. It bears some commonality to the work of tary civil employees
Brown et al. (Brown et al., 2003) in that it permits
Acknowledgements
combination of lattice entries with overlap (al-
though the relevant CBMT components are cov- In addition to Eli Abir (previously mentioned), we
ered in patent applications filed in 2001). would also like to acknowledge Rick Lin, Nischala
However, it differs greatly from all previous sys- N. Nimmakayala, Aruna Kumar Pamulapati, and
tems in the maximal overlap principle for decoding Gary Sofizade for their dedication and hard work
and confirmation, in using consistently long n- on CBMT, and Kenneth Greif, Lawrence Horn,
grams, in near-synonym phrase substitutability, William Kohane, Jonathan Kolatch, and David
and in requiring no parallel text whatsoever to Tepper for their support.
translate.
References
Appendix A: Sample CBMT Translations
Eli Abir, Steve Klein, David Miller, and Michael Stein-
As is typical of all MT systems, CBMT produces baum (2002). Fluent Machines’ EliMT System. In
some good translations and some not-so-good. We Fifth Conference of the Association for Machine
illustrate a few good examples, which are not Translation in the Americas, AMTA-2002, Tiburon,
atypical (with Web-based SYSTRAN as contrast), California, USA, pp. 216-219.
drawn from newswire text relating to the Middle
East. CBMT does not yet generate true casing. Regina Barzilay and Kathleen McKeown (2001). Ex-
tracting Paraphrases from a Parallel Corpus. In Pro-
ceedings of the 39th Annual Meeting of the

27
 Association for Computational Linguistics, Toulouse, Dekang Lin, Shaojun Zhao, Lijuan Qin and Ming Zhou
France, pp. 50-57. (2003). Identifying Synonyms among Distributionally
Similar Words. In Proceedings of the Eighteenth In-
P. Brown, J. Cocke, S. Della Pietra, V. Della Pietra, F. ternational Joint Conference on Artificial Intelligence
Jelinek, J. Lafferty, R. Mercer, and P. Roossin (1990). (IJCAI-03), Acapulco, Mexico, pp.1492-1493.
A Statistical Approach to Machine Translation. Com-
putational Linguistics, 16(2), pp.79-85. Teruko Mitamura, Eric Nyberg, and Jaime Carbonell
(1994). KANT: Knowledge-Based, Accurate, Natural
Ralf D. Brown, Rebecca Hutchinson, Paul N. Bennett, Language Translation. Proceedings of the First Con-
Jaime G. Carbonell, and Peter Jansen (2003). Reduc- ference of the Association for Machine Translation in
ing Boundary Friction Using Translation-Fragment the Americas, Columbia, Maryland, USA, pp.232-
Overlap. In MT Summit IX, Proceedings of the Ninth 233.
Machine Translation Summit, New Orleans, USA,
pp.24-31. Makoto Nagao (1984). A Framework of a Mechanical
Translation between Japanese and English by Anal-
Chris Callison-Burch, Philipp Koehn and Miles Os- ogy Principle. In A. Elithorn and R. Banerji, editors,
borne (2006). Improved Statistical Machine Transla- Artificial and Human Intelligence. North-Holland: El-
tion Using Paraphrases. In Proceedings NAACL-2006, sevier Science Publishers, chap. 11, pp.173-180.
New York, USA.
Makoto Nagao (1989). Machine Translation: How Far
Jaime Carbonell, David Farwell, Robert Frederking, Can it Go? Oxford University Press, Oxford, U.K.
Steven Helmreich, Eduard Hovy, Kevin Knight, Lori Translated by Norman Cook.
Levin, and Sergei Nirenburg (1994). The Pangloss
MT System. Proceedings of the First Conference of Franz Josef Och (2005). Statistical Machine Transla-
the Association for Machine Translation in the tion: Foundations and Recent Advances. MT Summit
Americas, Columbia, Maryland, USA, pp.240-241. X, Phuket, Thailand, Tutorial Note.

Peter Dirix, Ineke Schuurman, and Vincent Vandeghin- E. Sumita and H. Iida (1991). Experiments and Pros-
ste (2005). METIS-II: Example-Based Machine pects of Example-Based Machine Translation. In
Translation Using Monolingual Corpora - System De- Proceedings of the 29th Annual Meeting of the Asso-
scription. In Proceedings of MT Summit X, Workshop ciation for Computational Linguistics. Berkeley, Cali-
on Example-Based Machine Translation, Phuket, fornia, USA, pp.185-192.
Thailand, pp.43-50.
Hiroshi Uchida and Meiying Zhu (1993). Interlingua for
Takao Doi, Hirofumi Yamamoto, and Eiichiro Sumita Multilingual Machine Translation. MT Summit IV.
(2005). Graph-Based Retrieval for Example-Based Kobe, Japan, pp.157-169.
Machine Translation Using Edit Distance. In Pro-
ceedings of MT Summit X, Workshop on Example- P. Whitelock (1992). Shake-and-Bake Translation. In
Based Machine Translation, Phuket, Thailand, pp.51- Proceedings of the 14th International Conference on
58. Computational Linguistics (COLING 92), Nantes,
France, Volume II, pp.784-791.
Nizar Habash (2003). Matador: A Large-Scale Spanish-
English GHMT System. In MT Summit IX, Proceed- Kenji Yamada and Kevin Knight (2002). A Decoder for
ings of the Ninth Machine Translation Summit, New Syntax-Based Statistical MT. In Proceedings of the
Orleans, USA, pp.149-156. 40th Annual Meeting of the Association for Computa-
tional Linguistics (ACL-2002), Philadelphia, USA,
W. John Hutchins (1986). Machine Translation: Past, pp.303-310.
Present and Future, Ellis Horwood Ltd., Chichester,
U.K., (Halsted Press, New York).

Jae Dong Kim, Ralf D. Brown, Peter J. Jansen, and

Jaime G. Carbonell (2005). Symmetric Probabilistic
Alignment for Example-Based Translation. In Pro-
ceedings of the 10th Workshop of the European Asso-
ciation for Machine Translation (EAMT-2005),
Budapest, Hungary, pp.153-159.

28

View publication stats