A polynomial-time algorithm for statistical machine translation
Published 1 January 1996Open access
Dekai Wu
Citations155
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A polynomial-time algorithm for statistical machine translation that employs the stochastic bracketing transduction grammar (SBTG) model to replace earlier word alignment channel models, while retaining a bigram language model.
Abstract
We introduce a polynomial-time algorithm for statistical machine translation. This algorithm can be used in place of the expensive, slow best-first search strategies in current statistical translation architectures. The approach employs the stochastic bracketing transduction grammar (SBTG) model we recently introduced to replace earlier word alignment channel models, while retaining a bigram language model. The new algorithm in our experience yields major speed improvement with no significant loss of accuracy.
Keywords
Computer Science
IEEE Transactions on Information TheoryError bounds for convolutional codes and an asymptotically optimum decoding algorithm
6,705 Citations1967Andrew J. Viterbi
The upper bound is obtained for a specific probabilistic nonsequential decoding algorithm which is shown to be asymptotically optimum for rates above R_{0} and whose performance bears certain similarities to that of sequential decoding algorithms.
The mathematics of statistical machine translation: parameter estimation
4,125 Citations1993Peter F. Brown, Vincent J. Della Pietra +2 more
It is reasonable to argue that word-by-word alignments are inherent in any sufficiently large bilingual corpus, given a set of pairs of sentences that are translations of one another.
A statistical approach to machine translation
1,699 Citations1990Peter F. Brown, John Cocke +6 more
The application of the statistical approach to translation from French to English and preliminary results are described and the results are given.
Communications of the ACMAn efficient context-free parsing algorithm
817 Citations1970Jay Earley
A parsing algorithm which seems to be the most efficient general context-free algorithm known is described and appears to be superior to the top-down and bottom-up algorithms studied by Griffiths and Petrick.
Computational complexity and natural language
273 Citations1987Geoff Barton, Robert C. Berwick +1 more
A unified and coherent account emerges of how complexity theory can probe the information-processing structure of grammars, discovering why a grammar is easy or difficult to process and suggesting where to look for additional grammatical constraints.
Aligning a parallel English-Chinese corpus statistically with lexical criteria
185 Citations1994Dekai Wu
This report concerns three related topics: progress on the HKUST English-Chinese Parallel Bilingual Corpus; experiments addressing the applicability of Gale & Church's length-based statistical method to the task of alignment involving a non-Indo-European language; and an improved statistical method that also incorporates domain-specific lexical cues.
Text, speech and language technologyRobust Bilingual Word Alignment for Machine Aided Translation
162 Citations1999Ido Dagan, Kenneth Church +1 more
Because word_align and char_align were designed to work robustly on texts that are smaller and more 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.
Linguistics and PhilosophyDirect parsing of ID/LP grammars
76 Citations1984Stuart M. Shieber
This work develops a parsing algorithm, based on the algorithm of Earley, for parsing ID/LP grammars directly, circumventing the initial expansion phase, and discusses some aspects of the time complexity of the algorithm and some formal properties associated with 1D/LPgrammars and their relationship to context-free Grammars.
Stochastic inversion transduction grammars with application to segmentation, bracketing, and alignment of parallel corpora
75 Citations1995Dekai Wu
A novel stochastic inversion transduction grammar formalism for bilingual language modeling of sentence-pairs and the concept of bilingual parsing with potential application to a variety of parallel corpus analysis problems is introduced.
An algorithm for simultaneously bracketing parallel texts by aligning words
65 Citations1995Dekai Wu
Focusing on transduction grammars for bracketing, this work forms a normal form, and a stochastic version amenable to a maximum-likelihood bracketing algorithm.
Machine TranslationLarge-scale automatic extraction of an English-Chinese translation lexicon
63 Citations1995Dekai Wu, Xuanyin Xia
This work introduces a fully automatic two-stage statistical methodology that is able to learn translations for collocations and reports experimental results on automatic extraction of an English-Chinese translation lexicon, by statistical analysis of a large parallel corpus.
Improving Chinese tokenization with linguistic filters on statistical lexical acquisition
62 Citations1994Dekai Wu, Pascale Fung
Empirical evidence is presented for four points concerning tokenization of Chinese text: more rigorous "blind" evaluation methodology is needed to avoid inflated accuracy measurements, the extent of the unknown-word problem is far more serious than generally thought, and the nk-blind method is introduced.
Grammarless extraction of phrasal translation examples from parallel texts
45 Citations1995Dekai Wu
A generic, language-independent constituent-matching ITG with inherent expressiveness properties that correspond to a desirable level of matching flexibility is devised.
Trainable Coarse Bilingual Grammars for Parallel Text Bracketing
33 Citations1995Dekai Wu
Text, speech and language technologyStatistical Augmentation of a Chinese Machine-Readable Dictionary
22 Citations1999Pascale Fung, Dekai Wu
Results show that the method outputs legitimate words, acronymic constructions, idioms, names and titles, as well as technical compounds, many of which were lacking from the original dictionary.
National Conference on Artificial IntelligenceWord-order variation in natural language generation
21 Citations1987Aravind K. Joshi
The tree adjoining grammar (TAG) formalism has been investigated from the point of view of its ability to handle word-order variation in the context of generation.
Using Brackets to Improve Search for Statistical Machine Translation
3 Citations1995Dekai Wu, Cindy K.Y. Ng
A method to improve search time and space complexity in statistical machine translation architectures, by employing linguistic bracketing information on the source language sentence is proposed.