Stochastic inversion transduction grammars with application to segmentation, bracketing, and alignment of parallel corpora
Published 20 August 1995
Dekai Wu
Citations75
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 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.
Abstract
We introduce (1) a novel stochastic inversion transduction grammar formalism for bilingual language modeling of sentence-pairs, and (2) the concept of bilingual parsing with potential application to a variety of parallel corpus analysis problems. The formalism combines three tactics against the constraints that render finite-state transducers less useful: it skips directly to a context-free rather than finite-state base, it permits a minimal extra degree of ordering flexibility, and its probabilistic formulation admits an efficient maximum-likelihood bilingual parsing algorithm. A convenient normal form is shown to exist, and we discuss a number of examples of how stochastic inversion transduction grammars bring bilingual constraints to bear upon problematic corpus analysis tasks.
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.
A program for aligning sentences in bilingual corpora
956 Citations1993William A. Gale, Kenneth Church
This paper will describe a method and a program for aligning sentences based on a simple statistical model of character lengths, which uses the fact that longer sentences in one language tend to be translated into longer sentence in the other language, and that shorter sentences tend to been translated into shorter sentences.
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.
Journal of the ACMSyntax-Directed Transduction
340 Citations1968Philip Lewis, Richard E. Stearns
Some special conditions are investigated under which syntax-directed translations can be performed on (deterministic) pushdown machines and some time bounds for translations on Turing machines are derived.
Inside-outside reestimation from partially bracketed corpora
289 Citations1992Fernando Pereira, Yves Schabes
The inside-outside algorithm for inferring the parameters of a stochastic context-free grammar is extended to take advantage of constituent information in a partially parsed corpus to achieve faster convergence and better modelling of hierarchical structure than the original one.
<i>Termight</i>
223 Citations1994Ido Dagan, Kenneth Church
A semi-automatic tool that helps professional translators and terminologists identify technical terms and their translations using part-of-speech tagging and word-alignment programs in an interface designed to minimize keystrokes is proposed.
Char_align
191 Citations1993Kenneth Church
This paper describes a new program, char_align, that aligns texts at the character level rather than at the sentence/paragraph level, based on the cognate approach proposed by Simard et al.
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.
K-vec
137 Citations1994Pascale Fung, Kenneth Church
An alternative alignment strategy which is presented, which is called K-vec, that starts by estimating the lexicon, that discovers that the English word fisheries is similar to the French peches by noting that the distribution of fisheries in the English text isSimilar to the Distribution of pê'ches in the French.
Parsing a natural language using mutual information statistics
127 Citations1990David M. Magerman, Mitchell P. Marcus
The generalized mutual information statistic is derived, the parsing algorithm is described, and results and sample output from the parser are presented.
Journal of the American Society for Information ScienceChinese text segmentation for text retrieval: Achievements and problems
121 Citations1993Zimin Wu, Gwyneth Tseng
A review of the various different approaches to Chinese text segmentation has been classified in order to provide a general picture of the research activity in this area and demonstrate thatText segmentation remains one of the most challenging and interesting areas for Chinese text retrieval.
Learning an English-Chinese Lexicon from a Parallel Corpus.
95 Citations1994Dekai Wu, Xuanyin Xia
To the authors' knowledge, these are the first empirical results of the kind between an Indo-European and non-Indo-European language for any significant corpus size with a non-toy vocabulary.
Rodopi eBooksStatistically-driven computer grammars of English : the IBM/LANCASTER approach
73 Citations1993Ezra Black, Roger Garside +2 more
This book is about building computer programs that parse (analyze, or diagram) sentences of a real-world English, which might be a corpus of everyday, naturally-occurring prose, such as the entire text of this morning's newspaper.
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.
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.
Aligning Noisy Parallel Corpora Across Language Groups : Word Pair Feature Matching by Dynamic Time Warping
42 Citations1994Pascale Fung, Kathleen McKeown
Meeting of the Association for Computational LinguisticsHMM-Based Part-of-Speech Tagging for Chinese Corpora
35 Citations1993Chao-Huang Chang, Cheng-Der Chen
This work presents work on Chinese part-of-speech tagging based on a first-order, fully-connected hsdden Markov model that adopts Kupiec's concept of word equivalence classes in the tagger and is able to correctly tag approzimately 96~ of all words in the testing data.
Trainable Coarse Bilingual Grammars for Parallel Text Bracketing
33 Citations1995Dekai Wu