Statistical machine translation : textbook

The dream of automatic language translation is now closer thanks to recent advances in the techniques that underpin statistical machine translation. This class-tested textbook from an active researcher in the field, provides a clear and careful introduction to the latest methods and explains how to build machine translation systems for any two languages. It introduces the subject's building blocks from linguistics and probability, then covers the major models for machine translation: word-based, phrase-based, and tree-based, as well as machine translation evaluation, language modeling, discriminative training and advanced methods to integrate linguistic annotation. The book also reports the latest research, presents the major outstanding challenges, and enables novices as well as experienced researchers to make novel contributions to this exciting area. Ideal for students at undergraduate and graduate level, or for anyone interested in the latest developments in machine translation. Half-title 3 Title 5 Copyright 6 Dedication 7 Contents 9 Preface 13 Part I Foundations 15 Chapter 1 Introduction 17 1.1 Overview 18 1.1.1 Chapter 1: Introduction 18 1.1.2 Chapter 2: Word, Sentences, Corpora 19 1.1.3 Chapter 3: Probability Theory 20 1.1.4 Chapter 4: Word-Based Models 20 1.1.5 Chapter 5: Phrase-Based Models 22 1.1.6 Chapter 6: Decoding 23 1.1.7 Chapter 7: Language Models 23 1.1.8 Chapter 8: Evaluation 24 1.1.9 Chapter 9: Discriminative Training 25 1.1.10 Chapter 10: Integrating Linguistic Information 26 1.1.11 Chapter 11: Tree-Based Models 27 1.2 History of Machine Translation 28 1.2.1 The Beginning 28 1.2.2 The ALPAC Report and Its Consequences 29 1.2.3 First Commercial Systems 30 1.2.4 Research in Interlingua-Based Systems 30 1.2.5 Data-Driven Methods 31 1.2.6 Current Developers 32 1.2.7 State of the Art 32 1.3 Applications 34 1.3.1 Fully-Automatic High-Quality Machine Translation 34 1.3.2 Gisting 35 1.3.3 Integration with Speech Technologies 35 1.3.4 Translation on Hand-Held Devices 36 1.3.5 Post-Editing 37 1.3.6 Tools for Translators 37 1.4 Available Resources 37 1.4.1 Tools 38 1.4.2 Corpora 39 1.4.3 Evaluation Campaigns 39 1.5 Summary 40 1.5.1 Core Concepts 40 1.5.2 Further Reading 41 1.5.3 Exercises 44 Chapter 2 Words, Sentences, Corpora 47 2.1 Words 47 2.1.1 Tokenization 48 2.1.2 Distribution of Words 49 2.1.3 Parts of Speech 52 2.1.4 Morphology 54 2.1.5 Lexical Semantics 57 2.2 Sentences 59 2.2.1 Sentence Structure 59 2.2.2 Theories of Grammar 61 2.2.3 Translation of Sentence Structure 65 2.2.4 Discourse 66 2.3 Corpora 67 2.3.1 Types of Text 67 2.3.2 Acquiring Parallel Corpora 68 2.3.3 Sentence Alignment 69 2.4 Summary 71 2.4.1 Core Concepts 71 2.4.2 Further Reading 73 2.4.3 Exercises 76 Chapter 3 Probability Theory 77 3.1 Estimating Probability Distributions 77 3.1.1 Estimation by Analysis 78 3.1.2 Common Probability Distributions 78 3.1.3 Estimation from Statistics 80 3.2 Calculating Probability Distributions 81 3.2.1 Formal Definitions 81 3.2.2 Joint Probability Distributions 82 3.2.3 Conditional Probability Distributions 83 3.2.4 Bayes Rule 83 3.2.5 Interpolation 84 3.3 Properties of Probability Distributions 85 3.3.1 Mean and Variance 85 3.3.2 Expectation and Variance 86 3.3.3 Entropy 86 3.3.4 Mutual Information 88 3.4 Summary 89 3.4.1 Core Concepts 89 3.4.2 Further Reading 90 3.4.3 Exercises 90 Part II Core Methods 93 Chapter 4 Word-Based Models 95 4.1 Machine Translation by Translating Words 95 4.1.1 Lexical Translation 95 4.1.2 Collecting a Statistic 96 4.1.3 Estimating a Probability Distribution 96 4.1.4 Alignment 97 4.1.5 IBM Model 1 100 4.2 Learning Lexical Translation Models 101 4.2.1 The Problem of Incomplete Data 102 4.2.2 The Expectation Maximization Algorithm 102 4.2.3 EM for IBM Model 1 103 4.2.4 Perplexity 106 4.3 Ensuring Fluent Output 108 4.3.1 Empirical Evidence for Fluent Output 108 4.3.2 Language Model 109 4.3.3 Noisy-Channel Model 109 4.4 Higher IBM Models 110 4.4.1 IBM Model 2 111 4.4.2 IBM Model 3 114 4.4.3 Training for Model 3: Sampling the Alignment Space 117 4.4.4 IBM Model 4 119 4.4.5 IBM Model 5 124 4.5 Word Alignment 127 4.5.1 The Task of Word Alignment 127 4.5.2 Measuring Word Alignment Quality 129 4.5.3 Word Alignment Based on IBM Models 130 4.6 Summary 132 4.6.1 Core Concepts 132 4.6.2 Further Reading 133 4.6.3 Exercises 138 Chapter 5 Phrase-Based Models 141 5.1 Standard Model 141 5.1.1 Motivation for Phrase-Based Models 141 5.1.2 Mathematical Definition 143 5.2 Learning a Phrase Translation Table 144 5.2.1 Extracting Phrases from a Word Alignment 144 5.2.2 Definition of Consistency 145 5.2.3 Phrase Extraction Algorithm 146 5.2.4 Example 147 5.2.5 Estimating Phrase Translation Probabilities 149 5.3 Extensions to the Translation Model 150 5.3.1 Log-Linear Models 150 5.3.2 Bidirectional Translation Probabilities 152 5.3.3 Lexical Weighting 153 5.3.4 Word Penalty 154 5.3.5 Phrase Penalty 154 5.3.6 Phrase Translation as a Classification Problem 155 5.4 Extensions to the Reordering Model 156 5.4.1 Reordering Limits 156 5.4.2 Lexicalized Reordering 157 5.5 EM Training of Phrase-Based Models 159 5.5.1 A Joint Model for Phrasal Alignment 159 5.5.2 Complexity of the Alignment Space 160 5.5.3 Training the Model 161 5.6 Summary 162 5.6.1 Core Concepts 162 5.6.2 Further Reading 163 5.6.3 Exercises 167 Chapter 6 Decoding 169 6.1 Translation Process 170 6.1.1 Translating a Sentence 170 6.1.2 Computing the Sentence Translation Probability 171 6.2 Beam Search 172 6.2.1 Translation Options 173 6.2.2 Decoding by Hypothesis Expansion 173 6.2.3 Computational Complexity 175 6.2.4 Hypothesis Recombination 175 6.2.5 Stack Decoding 177 6.2.6 Histogram Pruning and Threshold Pruning 179 6.2.7 Reordering Limits 180 6.3 Future Cost Estimation 181 6.3.1 Varying Translation Difficulty 181 6.3.2 Estimating Future Cost for Translation Options 183 6.3.3 Estimating Future Cost for Any Input Span 184 6.3.4 Using Future Cost in the Search 185 6.4 Other Decoding Algorithms 186 6.4.1 Beam Search Based on Coverage Stacks 186 6.4.2 A* Search 187 6.4.3 Greedy Hill-Climbing Decoding 188 6.4.4 Finite State Transducer Decoding 189 6.5 Summary 190 6.5.1 Core Concepts 190 6.5.2 Further Reading 191 6.5.3 Exercises 192 Chapter 7 Language Models 195 7.1 N-Gram Language Models 196 7.1.1 Markov Chain 196 7.1.2 Estimation 197 7.1.3 Perplexity 198 7.2 Count Smoothing 202 7.2.1 Add-One Smoothing 203 7.2.2 Deleted Estimation 204 7.2.3 Good–Turing Smoothing 206 7.2.4 Evaluation 209 7.3 Interpolation and Back-off 210 7.3.1 Interpolation 211 7.3.2 Recursive Interpolation 211 7.3.3 Back-off 212 7.3.4 Diversity of Predicted Words 213 7.3.5 Diversity of Histories 214 7.3.6 Modified Kneser–Ney Smoothing 215 7.3.7 Evaluation 217 7.4 Managing the Size of the Model 218 7.4.1 Number of Unique N-Grams 218 7.4.2 Estimation on Disk 219 7.4.3 Efficient Data Structures 220 7.4.4 Reducing Vocabulary Size 222 7.4.5 Extracting Relevant n-Grams 223 7.4.6 Loading N-Grams on Demand 225 7.5 Summary 226 7.5.1 Core Concepts 226 7.5.2 Further Reading 228 7.5.3 Exercises 229 Chapter 8 Evaluation 231 8.1 Manual Evaluation 232 8.1.1 Fluency and Adequacy 232 8.1.2 Goals for Evaluation 234 8.1.3 Other Evaluation Criteria 235 8.2 Automatic Evaluation 236 8.2.1 Precision and Recall 236 8.2.2 Word Error Rate 238 8.2.3 BLEU: A Bilingual Evaluation Understudy 240 8.2.4 METEOR 242 8.2.5 The Evaluation Debate 242 8.2.6 Evaluation of Evaluation Metrics 243 8.2.7 Evidence of Shortcomings of Automatic Metrics 245 8.3 Hypothesis Testing 246 8.3.1 Computing Confidence Intervals 247 8.3.2 Pairwise Comparison 248 8.3.3 Bootstrap Resampling 250 8.4 Task-Oriented Evaluation 251 8.4.1 Cost of Post-Editing 251 8.4.2 Content Understanding Tests 253 8.5 Summary 254 8.5.1 Core Concepts 254 8.5.2 Further Reading 255 8.5.3 Exercises 259 Part III Advanced Topics 261 Chapter 9 Discriminative Training 263 9.1 Finding Candidate Translations 264 9.1.1 Search Graph 264 9.1.2 Word Lattice 265 9.1.3 N-Best List 267 9.2 Principles of Discriminative Methods 269 9.2.1 Representing Translations with Features 269 9.2.2 Labeling Correctness of Translations 271 9.2.3 Supervised Learning 272 9.2.4 Maximum Entropy 274 9.3 Parameter Tuning 277 9.3.1 Experimental Setup 278 9.3.2 Powell Search 279 9.3.3 Simplex Algorithm 284 9.4 Large-Scale Discriminative Training 286 9.4.1 Training Issues 287 9.4.2 Objective Function 288 9.4.3 Gradient Descent 289 9.4.4 Perceptron 290 9.4.5 Regularization 291 9.5 Posterior Methods and System Combination 292 9.5.1 Minimum Bayes Risk 292 9.5.2 Confidence Estimation 294 9.5.3 System Combination 295 9.6 Summary 297 9.6.1 Core Concepts 297 9.6.2 Further Reading 298 9.6.3 Exercises 301 Chapter 10 Integrating Linguistic Information 303 10.1 Transliteration 305 10.1.1 Numbers and Names 305 10.1.2 Name Translation 306 10.1.3 A Finite State Approach to Transliteration 306 10.1.4 Resources 309 10.1.5 Back-Transliteration and Translation 310 10.2 Morphology 310 10.2.1 Morphemes 311 10.2.2 Simplifying Rich Morphology 312 10.2.3 Translating Rich Morphology 314 10.2.4 Word Splitting 315 10.3 Syntactic Restructuring 316 10.3.1 Reordering Based on Input-Language Syntax 317 10.3.2 Learning Reordering Rules 318 10.3.3 Reordering Based on Part-of-Speech Tags 319 10.3.4 Reordering Based on Syntactic Trees 321 10.3.5 Preserving Choices 323 10.4 Syntactic Features 324 10.4.1 Methodology 325 10.4.2 Count Coherence 325 10.4.3 Agreement 326 10.4.4 Syntactic Parse Probability 327 10.5 Factored Translation Models 328 10.5.1 Decomposition of Factored Translation 330 10.5.2 Training Factored Models 332 10.5.3 Combination of Components 333 10.5.4 Efficient Decoding 334 10.6 Summary 334 10.6.1 Core Concepts 334 10.6.2 Further Reading 336 10.6.3 Exercises 341 Chapter 11 Tree-Based Models 345 11.1 Synchronous Grammars 345 11.1.1 Phrase Structure Grammars 346 11.1.2 Synchronous Phrase Structure Grammars 347 11.1.3 Synchronous Tree-Substitution Grammars 348 11.2 Learning Synchronous Grammars 351 11.2.1 Learning Hierarchical Phrase Models 351 11.2.2 Learning Syntactic Translation Rules 354 11.2.3 Simpler Rules 358 11.2.4 Scoring Grammar Rules 359 11.3 Decoding by Parsing 360 11.3.1 Chart Parsing 360 11.3.2 Core Algorithm 362 11.3.3 Chart Organization 363 11.3.4 Recombination 364 11.3.5 Stack Pruning 365 11.3.6 Accessing Grammar Rules 366 11.3.7 Cube Pruning 371 11.3.8 Binarizing the Grammar 373 11.3.9 Outside Cost Estimation 375 11.4 Summary 377 11.4.1 Core Concepts 377 11.4.2 Further Reading 378 11.4.3 Exercises 383 Bibliography 385 Author Index 430 Index 441 0521874157,9780521874151 Cambridge University Press The Field Of Machine Translation Has Recently Been Energized By The Emergence Of Statistical Techniques, Which Have Brought The Dream Of Automatic Language Translation Closer To Reality. This Class-tested Textbook, Authored By An Active Researcher In The Field, Provides A Gentle And Accessible Introduction To The Latest Methods And Enables The Reader To Build Machine Translation Systems For Any Language Pair. It Provides The Necessary Grounding In Linguistics And Probabilities, And Covers The Major Models For Machine Translation: Word-based, Phrase-based, And Tree-based, As Well As Machine Translation Evaluation, Language Modeling, Discriminative Training, And Advanced Methods To Integrate Linguistic Annotation. The Book Reports On The Latest Research And Outstanding Challenges, And Enables Novices As Well As Experienced Researchers To Make Contributions To The Field. It Is Ideal For Students At Undergraduate And Graduate Level, Or For Any Reader Interested In The Latest Developments In Machine Translation.--jacket. Preface -- Part I. Foundations -- 1. Introduction -- 2. Words, Sentences, Corpora -- 3. Probability Theory -- Part Ii. Core Methods -- 4. Word-based Models -- 5. Phrase-based Models -- 6. Decoding -- 7. Language Models -- 8. Evaluation -- Part Iii. Advanced Topics -- 9. Discriminative Training -- 10. Integrating Linguistic Information -- 11. Tree-based Models -- Bibliography -- Author Index -- Index. By Philipp Koehn. Includes Bibliographical References (p. 371-415) And Index. "The field of machine translation has recently been energized by the emergence of statistical techniques, which have brought the dream of automatic language translation closer to reality. This class-tested textbook, authored by an active researcher in the field, provides a gentle and accessible introduction to the latest methods and enables the reader to build machine translation systems for any language pair." "It provides the necessary grounding in linguistics and probabilities, and covers the major models for machine translation: word-based, phrase-based, and tree-based, as well as machine translation evaluation, language modeling, discriminative training, and advanced methods to integrate linguistic annotation. The book reports on the latest research and outstanding challenges, and enables novices as well as experienced researchers to make contributions to the field. It is ideal for students at undergraduate and graduate level, or for any reader interested in the latest developments in machine translation."--Page [4] de la couv This introductory text to statistical machine translation (SMT) provides all of the theories and methods needed to build a statistical machine translator, such as Google Language Tools and Babelfish. In general, statistical techniques allow automatic translation systems to be built quickly for any language-pair using only translated texts and generic software. With increasing globalization, statistical machine translation will be central to communication and commerce. Based on courses and tutorials, and classroom-tested globally, it is ideal for instruction or self-study, for advanced undergraduates and graduate students in computer science and/or computational linguistics, and researchers in natural language processing. The companion website provides open-source corpora and tool-kits.