Machine translation

Using the VitalSource® ebook

Access to the VitalBookTM ebook accompanying this book is

via VitalSource® Bookshelf – an ebook reader which allows

you to make and share notes and highlights on your ebooks

and search across all of the ebooks that you hold on your

VitalSource Bookshelf. You can access the ebook online or

offline on your smartphone, tablet or PC/Mac and your notes

and highlights will automatically stay in sync no matter where

you make them.

1. Create a VitalSource Bookshelf account at

https://online.vitalsource.com/user/new or log into

your existing account if you already have one.

2. Redeem the code provided in the panel below

to get online access to the ebook. Log in to

Bookshelf and click the Account menu at the top right

of the screen. Select Redeem and enter the redemption

code shown on the scratch-off panel below in the Code

To Redeem box. Press Redeem. Once the code has

been redeemed your ebook will download and appear in

your library.

DOWNLOAD AND READ OFFLINE

To use your ebook offline, download BookShelf to your PC,

Mac, iOS device, Android device or Kindle Fire, and log in to

your Bookshelf account to access your ebook:

On your PC/Mac

Go to http://bookshelf.vitalsource.com/ and follow the

instructions to download the free VitalSource Bookshelf

app to your PC or Mac and log into your Bookshelf account.

On your iPhone/iPod Touch/iPad

Download the free VitalSource Bookshelf App available

via the iTunes App Store and log into your Bookshelf

account. You can find more information at https://support.

vitalsource.com/hc/en-us/categories/200134217-

Bookshelf-for-iOS

On your Android™ smartphone or tablet

Download the free VitalSource Bookshelf App available

via Google Play and log into your Bookshelf account. You can

find more information at https://support.vitalsource.com/

hc/en-us/categories/200139976-Bookshelf-for-Android￾and-Kindle-Fire

On your Kindle Fire

Download the free VitalSource Bookshelf App available

from Amazon and log into your Bookshelf account. You can

find more information at https://support.vitalsource.com/

hc/en-us/categories/200139976-Bookshelf-for-Android￾and-Kindle-Fire

N.B. The code in the scratch-off panel can only be used once.

When you have created a Bookshelf account and redeemed

the code you will be able to access the ebook online or offline

on your smartphone, tablet or PC/Mac.

SUPPORT

If you have any questions about downloading Bookshelf,

creating your account, or accessing and using your ebook

edition, please visit http://support.vitalsource.com/

Accessing the E-book edition

Machine

Translation

Pushpak Bhattacharyya

Indian Institute of Technology Bombay

Mumbai, India

CRC Press

Taylor & Francis Group

6000 Broken Sound Parkway NW, Suite 300

Boca Raton, FL 33487-2742

© 2015 by Taylor & Francis Group, LLC

CRC Press is an imprint of Taylor & Francis Group, an Informa business

No claim to original U.S. Government works

Version Date: 20141121

International Standard Book Number-13: 978-1-4398-9719-5 (eBook - PDF)

This book contains information obtained from authentic and highly regarded sources. Reasonable efforts

have been made to publish reliable data and information, but the author and publisher cannot assume

responsibility for the validity of all materials or the consequences of their use. The authors and publishers

have attempted to trace the copyright holders of all material reproduced in this publication and apologize to

copyright holders if permission to publish in this form has not been obtained. If any copyright material has

not been acknowledged please write and let us know so we may rectify in any future reprint.

Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmit￾ted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented,

including photocopying, microfilming, and recording, or in any information storage or retrieval system,

without written permission from the publishers.

For permission to photocopy or use material electronically from this work, please access www.copyright.

com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood

Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and

registration for a variety of users. For organizations that have been granted a photocopy license by the CCC,

a separate system of payment has been arranged.

Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used

only for identification and explanation without intent to infringe.

Visit the Taylor & Francis Web site at

http://www.taylorandfrancis.com

and the CRC Press Web site at

http://www.crcpress.com

To My Mother

This page intentionally left blank

v

Contents

List of Figures .........................................................................................................xi

List of Tables ..........................................................................................................xv

Preface................................................................................................................... xix

Acknowledgments ............................................................................................xxiii

About the Author............................................................................................... xxv

1. Introduction.....................................................................................................1

1.1 A Feel for a Modern Approach to Machine Translation:

Data-Driven MT ....................................................................................2

1.2 MT Approaches: Vauquois Triangle...................................................4

1.2.1 Understanding Transfer over the Vauquois Triangle .........9

1.2.2 Understanding Ascending and Descending Transfer...... 14

1.2.2.1 Descending Transfer.............................................. 14

1.2.2.2 Ascending Transfer................................................ 16

1.2.2.3 Ascending Transfer due to Tool and

Resource Disparity................................................. 17

1.3 Language Divergence with Illustration between Hindi

and English .......................................................................................... 19

1.3.1 Syntactic Divergence ............................................................. 19

1.3.1.1 Constituent Order Divergence ............................. 19

1.3.1.2 Adjunction Divergence..........................................20

1.3.1.3 Preposition-Stranding Divergence ...................... 21

1.3.1.4 Null Subject Divergence........................................ 21

1.3.1.5 Pleonastic Divergence............................................22

1.3.2 Lexical-Semantic Divergence ...............................................22

1.3.2.1 Conflational Divergence........................................22

1.3.2.2 Categorial Divergence ...........................................23

1.3.2.3 Head-Swapping Divergence .................................23

1.3.2.4 Lexical Divergence ................................................. 24

1.4 Three Major Paradigms of Machine Translation............................25

1.5 MT Evaluation .....................................................................................29

1.5.1 Adequacy and Fluency .........................................................30

1.5.2 Automatic Evaluation of MT Output.................................. 32

1.6 Summary..............................................................................................33

Further Reading.............................................................................................34

2. Learning Bilingual Word Mappings ........................................................ 37

2.1 A Combinatorial Argument..............................................................39

2.1.1 Necessary and Sufficient Conditions for Deterministic

Alignment in Case of One-to-One Word Mapping............. 39

vi Contents

2.1.2 A Naïve Estimate for Corpora Requirement......................40

2.1.2.1 One-Changed-Rest-Same ...................................... 41

2.1.2.2 One-Same-Rest-Changed......................................42

2.2 Deeper Look at One-to-One Alignment..........................................46

2.2.1 Drawing Parallels with Part of Speech Tagging ...............46

2.3 Heuristics-Based Computation of the VE × VF Table .....................50

2.4 Iterative (EM-Based) Computation of the VE × VF Table ............... 51

2.4.1 Initialization and Iteration 1 of EM..................................... 52

2.4.2 Iteration 2 ................................................................................53

2.4.3 Iteration 3 ................................................................................54

2.5 Mathematics of Alignment................................................................56

2.5.1 A Few Illustrative Problems to Clarify

Application of EM..................................................................57

2.5.1.1 Situation 1: Throw of a Single Coin .....................57

2.5.1.2 Throw of Two Coins............................................... 57

2.5.1.3 Generalization: Throw of More Than One

“Something,” Where That “Something”

Has More Than One Outcome .............................59

2.5.2 Derivation of Alignment Probabilities ............................... 62

2.5.2.1 Key Notations ......................................................... 62

2.5.2.2 Hidden Variables (a; the alignment variables)...... 63

2.5.2.3 Parameters (θ) .........................................................63

2.5.2.4 Data Likelihood......................................................64

2.5.2.5 Data Likelihood L(D;θ), Marginalized over A..... 64

2.5.2.6 Marginalized Data Log-Likelihood LL(D, A;θ).... 64

2.5.2.7 Expectation of Data Log-Likelihood E(LL(D; Θ))... 64

2.5.3 Expressing the E- and M-Steps in Count Form................. 67

2.6 Complexity Considerations ...............................................................68

2.6.1 Storage .....................................................................................68

2.6.2 Time ......................................................................................... 70

2.7 EM: Study of Progress in Parameter Values.................................... 70

2.7.1 Necessity of at Least Two Sentences ...................................71

2.7.2 One-Same-Rest-Changed Situation.....................................71

2.7.3 One-Changed-Rest-Same Situation.....................................72

2.8 Summary..............................................................................................73

Further Reading............................................................................................. 76

3. IBM Model of Alignment ...........................................................................79

3.1 Factors Influencing P(f|e)................................................................... 81

3.1.1 Alignment Factor a ................................................................ 81

3.1.2 Length Factor m......................................................................82

3.2 IBM Model 1.........................................................................................86

3.2.1 The Problem of Summation over Product in

IBM Model 1 ...........................................................................86

Contents vii

3.2.2 EM for Computing P(f|e)......................................................88

3.2.3 Alignment in a New Input Sentence Pair .......................... 91

3.2.4 Translating a New Sentence in IBM Model 1:

Decoding ............................................................................91

3.3 IBM Model 2.........................................................................................93

3.3.1 EM for Computing P(f|e) in IBM Model 2..........................94

3.3.2 Justification for and Linguistic Viability of P(i|j,l,m)........96

3.4 IBM Model 3.........................................................................................98

3.5 Summary............................................................................................ 102

Further Reading........................................................................................... 103

4. Phrase-Based Machine Translation ........................................................ 105

4.1 Need for Phrase Alignment............................................................. 106

4.1.1 Case of Promotional/Demotional Divergence ................ 106

4.1.2 Case of Multiword (Includes Idioms) ............................... 107

4.1.3 Phrases Are Not Necessarily Linguistic Phrases............ 108

4.2 An Example to Illustrate Phrase Alignment Technique ............. 108

4.2.1 Two-Way Alignments.......................................................... 109

4.2.2 Symmetrization.................................................................... 110

4.2.3 Expansion of Aligned Words to Phrases.......................... 111

4.2.3.1 Principles of Phrase Construction ..................... 111

4.3 Phrase Table ....................................................................................... 115

4.4 Mathematics of Phrase-Based SMT................................................ 116

4.4.1 Understanding Phrase-Based Translation through

an Example............................................................................ 117

4.4.2 Deriving Translation Model and Calculating

Translation and Distortion Probabilities .......................... 119

4.4.3 Giving Different Weights to Model Parameters.............. 120

4.4.4 Fixing λ Values: Tuning ...................................................... 121

4.5 Decoding ............................................................................................122

4.5.1 Example to Illustrate Decoding .........................................125

4.6 Moses .................................................................................................. 128

4.6.1 Installing Moses................................................................... 128

4.6.2 Workflow for Building a Phrase-Based SMT System ..... 129

4.6.3 Preprocessing for Moses ..................................................... 129

4.6.4 Training Language Model.................................................. 131

4.6.5 Training Phrase Model........................................................ 131

4.6.6 Tuning.................................................................................... 132

4.6.6.1 MERT Tuning........................................................ 132

4.6.7 Decoding Test Data.............................................................. 133

4.6.8 Evaluation Metric................................................................. 133

4.6.9 More on Moses ..................................................................... 133

4.7 Summary............................................................................................ 134

Further Reading........................................................................................... 135

viii Contents

5. Rule-Based Machine Translation (RBMT)............................................ 139

5.1 Two Kinds of RBMT: Interlingua and Transfer ............................ 141

5.1.1 What Exactly Is Interlingua? .............................................. 141

5.1.2 Illustration of Different Levels of Transfer ...................... 142

5.2 Universal Networking Language (UNL)....................................... 146

5.2.1 Illustration of UNL .............................................................. 146

5.3 UNL Expressions as Binary Predicates ......................................... 148

5.3.1 Why UNL? ............................................................................ 150

5.4 Interlingua and Word Knowledge.................................................. 151

5.4.1 How Universal Are UWs?................................................... 152

5.4.2 UWs and Multilinguality ................................................... 154

5.4.3 UWs and Multiwords .......................................................... 155

5.4.3.1 How to Represent Multiwords in the UW

Dictionary.............................................................. 157

5.4.4 UW Dictionary and Wordnet............................................. 158

5.4.5 Comparing and Contrasting UW Dictionary and

Wordnet................................................................................. 159

5.5 Translation Using Interlingua ......................................................... 161

5.5.1 Illustration of Analysis and Generation ........................... 162

5.6 Details of English-to-UNL Conversion: With Illustration .......... 163

5.6.1 Illustrated UNL Generation ............................................... 164

5.7 UNL-to-Hindi Conversion: With Illustration ............................... 172

5.7.1 Function Word Insertion .................................................... 173

5.7.2 Case Identification and Morphology Generation............ 174

5.7.3 Representative Rules for Function Words Insertion....... 174

5.7.4 Syntax Planning................................................................... 175

5.7.4.1 Parent-Child Positioning..................................... 175

5.7.4.2 Prioritizing the Relations .................................... 176

5.8 Transfer-Based MT............................................................................ 177

5.8.1 What Exactly Are Transfer Rules?..................................... 177

5.9 Case Study of Marathi-Hindi Transfer-Based MT ....................... 179

5.9.1 Krudant: The Crux of the Matter in M-H MT ................. 180

5.9.1.1 Finite State Machine (FSM) Rules

for Krudanta.......................................................... 182

5.9.2 M-H MT System................................................................... 183

5.10 Summary............................................................................................ 186

Further Reading........................................................................................... 187

6. Example-Based Machine Translation..................................................... 193

6.1 Illustration of Essential Steps of EBMT.......................................... 196

6.2 Deeper Look at EBMT’s Working ................................................... 197

6.2.1 Word Matching .................................................................... 197

6.2.2 Matching of Have ................................................................. 199

6.3 EBMT and Case-Based Reasoning..................................................200

Contents ix

6.4 Text Similarity Computation........................................................... 202

6.4.1 Word Based Similarity........................................................ 202

6.4.2 Tree and Graph Based Similarity ......................................204

6.4.3 CBR’s Similarity Computation Adapted to EBMT..........205

6.5 Recombination: Adaptation on Retrieved Examples................... 207

6.5.1 Based on Sentence Parts...................................................... 207

6.5.2 Based on Properties of Sentence Parts..............................208

6.5.3 Recombination Using Parts of Semantic Graph .............. 210

6.6 EBMT and Translation Memory ..................................................... 212

6.7 EBMT and SMT ................................................................................. 212

6.8 Summary............................................................................................ 212

Further Reading........................................................................................... 213

Index ..................................................................................................................... 217

This page intentionally left blank

xi

List of Figures

Figure 1.1 Vauquois triangle expressing approaches to machine

translation ..........................................................................................5

Figure 1.2 NLP layer ...........................................................................................6

Figure 1.3 Illustration of transfer: svo → sov....................................................7

Figure 1.4 Family tree of Indo-European languages......................................... 8

Figure 1.5 Subject, verb, and object in 1.4.E ................................................... 11

Figure 1.6 Subject, verb, and object in 1.4.H .................................................. 11

Figure 1.7 Dependency representation of 1.1.H; the relations are

shown in italics................................................................................ 13

Figure 1.8 Simplified Vauquois triangle......................................................... 14

Figure 1.9 Descending transfer........................................................................ 16

Figure 1.10 Ascending transfer........................................................................ 17

Figure 1.11 Semantic role graphs of sentences 1.12.H, 1.13.H,

and 1.14.H................................................................................... 18

Figure 1.12 RBMT-EBMT-SMT spectrum: knowledge (rules)

intensive to data (learning) intensive.........................................25

Figure 1.13 Perspectivizing EBMT. EBMT is data driven like SMT,

but is closer to RBMT in its deeper analysis of the source

sentence ..........................................................................................26

Figure 1.14 Precision and recall computation ...............................................33

Figure 2.1 Partial tree: resolving correspondences with one-same￾rest-changed method......................................................................43

Figure 2.2 Trellis of POS tags...........................................................................47

Figure 2.3 Trellis of English words for the Hindi sentence “piitar

jaldii soya” .......................................................................................48

Figure 2.4 Adjacency list representation of VE × VF matrix ........................69

Figure 2.5 X-axis, number of iterations; Y-axis, average entropy;

average entropy decreases monotonically ..................................71

Figure 2.6 X-axis, number of iterations; Y-axis, P(x|rabbit),

where x = trois/lapins/de/grenoble .................................................72

xii List of Figures

Figure 2.7 Decrease in average entropy for one-changed-rest-same

situation............................................................................................73

Figure 2.8 X-axis, number of iterations; Y-axis, P(x|rabbits),

where x = trois/blancs/lapins/cygnes.............................................73

Figure 3.1 Alignment between an example e ←→ f pair............................. 81

Figure 3.2 Search space for best e for input f. e^ has the highest

probability value per length, alignment, and translation.........84

Figure 4.1 Tuning process ..............................................................................123

Figure 4.2 Partial hypotheses; prefixes of length 0 to 3 of final

translation...................................................................................... 126

Figure 4.3 Partial hypotheses; prefixes of length 4 to 6 of final

translation...................................................................................... 126

Figure 4.4 Partial hypotheses; prefixes of length 7 to 9 of final

translation ...................................................................................... 127

Figure 4.5 Moses control flow........................................................................ 129

Figure 4.6 Moses workflow............................................................................ 130

Figure 5.1 Simplified Vauquois triangle....................................................... 140

Figure 5.2 English parse tree for “Give obeisance to the king”................ 144

Figure 5.3 UNL graph for the sentence “On Sunday in Kolkata,

Sachin donated to the cricket museum the bat with which

he scored his hundredth century at Bangladesh”.................... 147

Figure 5.4 Concepts and their expressions in different languages.......... 152

Figure 5.5 Flow diagram for simple sentence to UNL analyzer............... 164

Figure 5.6 UNL generation for compound/complex sentences................ 165

Figure 5.7 The architecture of the generation system................................ 173

Figure 5.8 Transfer system ............................................................................. 178

Figure 5.9 Krudanta processing example .................................................... 182

Figure 5.10 FSM expressing the morphotactics of verbs: VERBS—

transition for majority of verbs; VERB_le—transition for

only those verbs that can take the ‘le’ suffix; VERBS1,

VERBS2 etc., verbs that can take particular derivational

suffixes (obvious from the diagram); DF—direct form;

OF—oblique form; and SSY—suffix stripping transition ..... 183

Figure 5.11 Marathi-Hindi transfer-based MT............................................ 184