Adron 2.6x serial key or number

Transcription

1

2 Accessing the E-book edition Using the VitalSource ebook Access to the VitalBook TM 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.. Create a VitalSource Bookshelf account at 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 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 vitalsource.com/hc/en-us/categories/ 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 hc/en-us/categories/ bookshelf-for-androidand-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 hc/en-us/categories/ bookshelf-for-androidand-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

3 Machine Translation

4 Pushpak Bhattacharyya Indian Institute of Technology Bombay Mumbai, India

5 CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 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: 2042 International Standard Book Number-3: (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, transmitted, 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 com ( or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 0923, 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 and the CRC Press Web site at

6 To My Mother

7 This page intentionally left blank

8 Contents List of Figures...xi List of Tables...xv Preface... xix Acknowledgments...xxiii About the Author... xxv. Introduction.... A Feel for a Modern Approach to Machine Translation: Data-Driven MT MT Approaches: Vauquois Triangle Understanding Transfer over the Vauquois Triangle Understanding Ascending and Descending Transfer Descending Transfer Ascending Transfer Ascending Transfer due to Tool and Resource Disparity Language Divergence with Illustration between Hindi and English Syntactic Divergence Constituent Order Divergence Adjunction Divergence Preposition-Stranding Divergence Null Subject Divergence Pleonastic Divergence Lexical-Semantic Divergence Conflational Divergence Categorial Divergence Head-Swapping Divergence Lexical Divergence Three Major Paradigms of Machine Translation MT Evaluation Adequacy and Fluency Automatic Evaluation of MT Output Summary...33 Further Reading Learning Bilingual Word Mappings A Combinatorial Argument Necessary and Sufficient Conditions for Deterministic Alignment in Case of One-to-One Word Mapping v

9 vi Contents 2..73 Further Reading IBM Model of Alignment Factors Influencing P(f e) Alignment Factor a Length Factor m IBM Model The Problem of Summation over Product in IBM Model...86

1035

11 viii Contents 5. Rule-Based Machine Translation (RBMT) Two Kinds of RBMT: Interlingua and Transfer What Exactly Is Interlingua? Illustration of Different Levels of Transfer Universal Networking Language (UNL) Illustration of UNL UNL Expressions as Binary Predicates Why UNL? Interlingua and Word Knowledge How Universal Are UWs? UWs and Multilinguality UWs and Multiwords How to Represent Multiwords in the UW Dictionary UW Dictionary and Wordnet Comparing and Contrasting UW Dictionary and Wordnet Translation Using Interlingua Illustration of Analysis and Generation Details of English-to-UNL Conversion: With Illustration Illustrated UNL Generation UNL-to-Hindi Conversion: With Illustration Function Word Insertion Case Identification and Morphology Generation Representative Rules for Function Words Insertion Syntax Planning Parent-Child Positioning Prioritizing the Relations Transfer-Based MT What Exactly Are Transfer Rules? Case Study of Marathi-Hindi Transfer-Based MT Krudant: The Crux of the Matter in M-H MT Finite State Machine (FSM) Rules for Krudanta M-H MT System Summary Further Reading Example-Based Machine Translation Illustration of Essential Steps of EBMT Deeper Look at EBMT s Working Word Matching Matching of Have EBMT and Case-Based Reasoning...200

12 Contents ix 6.4 Text Similarity Computation Word Based Similarity Tree and Graph Based Similarity CBR s Similarity Computation Adapted to EBMT Recombination: Adaptation on Retrieved Examples Based on Sentence Parts Based on Properties of Sentence Parts Recombination Using Parts of Semantic Graph EBMT and Translation Memory EBMT and SMT Summary Further Reading Index... 27

13 This page intentionally left blank

14 List of Figures Figure. Vauquois triangle expressing approaches to machine translation...5 Figure.2 NLP layer...6 Figure.3 Illustration of transfer: svo sov...7 Figure.4 Family tree of Indo-European languages... 8 Figure.5 Subject, verb, and object in.4.e... Figure.6 Subject, verb, and object in.4.h... Figure.7 Dependency representation of..h; the relations are shown in italics... 3 Figure.8 Simplified Vauquois triangle... 4 Figure.9 Descending transfer... 6 Figure.0 Ascending transfer... 7 Figure. Semantic role graphs of sentences.2.h,.3.h, and.4.h... 8 Figure.2 RBMT-EBMT-SMT spectrum: knowledge (rules) intensive to data (learning) intensive...25 Figure.3 Perspectivizing EBMT. EBMT is data driven like SMT, but is closer to RBMT in its deeper analysis of the source sentence...26 Figure.4 Precision and recall computation...33 Figure 2. Partial tree: resolving correspondences with one-samerest-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 V E V F matrix...69 Figure 2.5 X-axis, number of iterations; Y-axis, average entropy; average entropy decreases monotonically...7 Figure 2.6 X-axis, number of iterations; Y-axis, P(x rabbit), where x = trois/lapins/de/grenoble...72 xi

15 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. Alignment between an example e f pair... 8 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. Tuning process...23 Figure 4.2 Partial hypotheses; prefixes of length 0 to 3 of final translation Figure 4.3 Partial hypotheses; prefixes of length 4 to 6 of final translation Figure 4.4 Partial hypotheses; prefixes of length 7 to 9 of final translation Figure 4.5 Moses control flow Figure 4.6 Moses workflow Figure 5. Simplified Vauquois triangle Figure 5.2 English parse tree for Give obeisance to the king 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 Figure 5.4 Concepts and their expressions in different languages Figure 5.5 Flow diagram for simple sentence to UNL analyzer Figure 5.6 UNL generation for compound/complex sentences Figure 5.7 The architecture of the generation system Figure 5.8 Transfer system Figure 5.9 Krudanta processing example Figure 5.0 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; VERBS, VERBS2 etc., verbs that can take particular derivational suffixes (obvious from the diagram); DF direct form; OF oblique form; and SSY suffix stripping transition Figure 5. Marathi-Hindi transfer-based MT... 84

16 List of Figures xiii Figure 6. Perspectivizing EBMT; EBMT is data driven like SMT, but is closer to RBMT in its deeper analysis of the source sentence Figure 6.2 Vauquois triangle adapted for EBMT Figure 6.3 CBR schematic Figure 6.4 Semantic graph of example sentence and its translation... 2 Figure 6.5 Semantic graph of new input sentence... 2

17 This page intentionally left blank

18 List of Tables Table. Parallel Sentences in Czech and English...2 Table.2 Alignments Learned from the Czech-English Data in Table...3 Table.3 English-Hindi Data Corresponding to the Czech-English Example...4 Table.4 English-Bengali Data Corresponding to the Czech-English Example...4 Table.5 Subject, Verb, and Object in Sentences.4.E and.4.h... 0 Table.6 Adjuncts in Sentences.4.E and.4.h... 0 Table.7 Five-Point Scales for Fluency and Adequacy Rating... 3 Table 2. Bengali-English Parallel Sentence...38 Table 2.2 Word Lists of Languages L and L 2 (we need to compute mapping probability between e i and f j )...40 Table 2.3 Formulae for Number of Sentence Pairs and Number of Correspondences for One-Same-Rest-Changed Situation...44 Table 2.4 Lexical Probability Table in POS Tagging...48 Table 2.5 V E V F Matrix...49 Table 2.6 Two English-French Parallel Sentence Pairs...50 Table 2.7 Alignment Probabilities Found by Simple Counting Heuristic; Average Entropy = Table 2.8 Initial Alignment Probabilities; Average Entropy = Table 2.9 Expected Counts of Mappings in Three Rabbits Trois Lapins Table 2.0 Expected Counts of Mappings in Rabbits of Grenoble Lapins de Grenoble...53 Table 2. Revised Alignment Probabilities after Iteration ; Average Entropy = Table 2.2 Revised Expected Counts of Mappings in Three Rabbits Trois Lapins xv

19 xvi List of Tables Table 2.3 Revised Expected Counts of Mappings in Rabbits of Grenoble Lapins de Grenoble...54 Table 2.4 Revised Alignment Probabilities after Iteration 2; Average Entropy = Table 2.5 Parallel Sentence with No Common Words...7 Table 2.6 Alignment Probabilities Frozen at 0.5; Average Entropy = Table 2.7 Parallel Corpora of Type One-Changed-Rest-Same...72 Table 3. Word Alignment in a Long Noun Phrase Translation...80 Table 3.2 Alignment Values for piitar jaldii soyaa...82 Table 3.3 Alignments in piitar jaldii soyaa Peter slept early...87 Table 3.4 Alignment Values in a-cells...87 Table 3.5 Mapping between Vocabulary of e and f...90 Table 3.6 Different Alignment Possibilities of Trois Lapins (there are nine of them and three rabbits (marked bold) is the desired one)...92 Table 3.7 Different Cases of Positional Alignment for the Main Verb...97 Table 4. Linguistic and Nonlinguistic Phrases Table 4.2 Example of Alignment of Phrases with Nonequivalent Meanings Table 4.3 Example of Alignment of Phrases, Both Linguistic and Nonlinguistic Table 4.4 Alignment from English to Marathi... 0 Table 4.5 Alignment from Marathi to English... 0 Table 4.6 A Few of the Possible Phrases from Alignments in Tables 4.4 and Table 4.7 Bigger Phrases Consistent with the Intersection of Tables 4.4 and Table 4.8 First Few Alignments from Moses...25 Table 5. Illustration of Transfer among Different Language Families...43 Table 5.2 Wordnet Lexical Matrix Table 5.3 POS and NER of Simple Sentence ()... 66

20 List of Tables xvii Table 5.4 POS and NER of Simple Sentence (2) Table 5.5 WSD of Simple Sentence () Table 5.6 WSD of Simple Sentence (2) Table 5.7 UWs in Simple Sentence () Table 5.8 UWs in Simple Sentence (2) Table 5.9 Relations in Simple Sentence () Table 5.0 Relations in Simple Sentence (2) Table 5. Attributes in Simple Sentence () Table 5.2 Attributes in Simple Sentence (2) Table 5.3 Sample Noun Morphology Rules Table 5.4 Sample Verb Morphology Rules Table 5.5 A Subsection of the Priority Matrix Table 5.6 Stages of Generation and Corresponding Output Table 5.7 Krudanta Types... 8 Table 6. Translation of a New Input by Analogy in EBMT Table 6.2 EBMT Using Word Classes Table 6.3 Sentence Features and Their Similarities Table 6.4 Correspondences from the Semantic Graph... 20

21 This page intentionally left blank

22 Preface The field of machine translation (MT) is as old as computer science itself starting in the days of the Cold War. Because of globalization, tourism, commerce, governance, education, etc., the need for translation has become all pervading, and the sheer volume of translation has made automation inevitable. Computers entry into translation was natural, like into many other human activities, such as accounting. Language ability defines humans, and languages define nations. MT has ingrained in it linguistics, natural language processing (NLP), and multilingual computation, besides programming, software engineering, lexical resource building, etc. Like all human activities requiring intelligence, translation too has repetitive components and creative components. In translating from one language to another, do humans first understand the source text completely and then produce the target text representing that understanding, or do they reuse patterns of pre-existing translations? Such questions and their attempted answers have given rise to paradigms of machine translation. Three paradigms have dominated MT. In temporal order, they are rule-based machine translation (RBMT), example-based machine translation (EBMT), and statistical machine translation (SMT). They differ in the way they handle the three fundamental processes in machine translation: analysis, transfer, and generation (ATG). In its pure form, RBMT uses rules, while SMT uses data, i.e., examples of parallel translations. EBMT tries a combination: Data supplies translation parts that rules recombine to produce translation. This book is meant to be a textbook for advanced undergraduate and graduate-level courses in machine translation and natural language processing. It grew out of about 0 years of teaching machine translation and natural language processing in the Department of Computer Science and Engineering, IIT Bombay. Stressing intuition and imparting clear concepts have been the guiding principles in writing this book. Different batches of students learning MT and NLP have found this teaching methodology, viz., exposition of language phenomena followed by modeling and experimentation (as lab assignments), useful. In using this book the reader will do well to keep this pedagogical framework in mind. The primary aim of this book is to teach MT through MT s three major paradigms: rule-based machine translation, example-based machine translation, and statistical machine translation. These paradigms are introduced as follows: SMT in Chapters 2 to 4, RBMT in Chapter 5, and EBMT in Chapter 6. Being the dominant paradigm in recent times, teeming with activity, SMT naturally xix

23 xx Preface takes a larger number of chapters. Now if somebody asks, Why cover anything else, if SMT is the ruling paradigm? then the answer is: RBMT and EBMT give the real feel for MT as to what exactly MT is. SMT no doubt shows how to climb a tree, but RBMT and EBMT show which tree to climb. Therefore, in this book we cover salient principles and practices of the three MT paradigms, perspectivizing, comparing, and contrasting them. Throughout, key points that help form and link fundamental concepts are stressed and restressed. For example, it is the conviction of the author that expectation maximization (EM)-based word alignment was a turning point in the history of MT, birthing SMT. No other paradigm of MT had in its arsenal such a concrete first step to arrange transfer in the A-T-G process. This point is brought up multiple times in different chapters. In Chapter, we introduce machine translation. The main aim of this chapter is to situate MT against the backdrop of language divergence and the Vauquois triangle. Translation is solving language divergence, which, in other words, is the expression of the reality that languages express meaning differently. The basic process of analysis-transfer-generation is also discussed in terms of levels in the Vauquois triangle. RBMT, EBMT, and SMT are introduced with an illuminating example to contrast them. As already mentioned, Chapters 2 to 4 are on data-driven or statistical machine translation (SMT). The goal of Chapter 2 is to explain the most important element of SMT bilingual word alignment from pairs of parallel translations. A student of MT cannot but appreciate the fundamental role word alignment has played in SMT. Compared to all paradigms, SMT probably had the most concrete scheme of transfer, once plenty of data became available. Word alignment is the starting point for all forms of alignment in different kinds of SMT word based, phrase based, tree based, and hybrid. As a buildup to the expectation maximization-based word alignment, we specify the very obvious, but hitherto unstressed, requirement of the one-same-rest-changed and one-changed-rest-same properties of parallel corpora. The mathematical machinery of EM algorithms is elaborated through many helpful examples. The deduction of E and M steps of the EM-based alignment algorithm, once understood, is empowering. An insightful part of discussions is combinatorics of the corpora requirement and the size of the phrase table, both of which run into millions of entries for any nontrivial translation situation. The goal of Chapter 3 is to explain the celebrated IBM models of machine translation. SMT takes birth in these models. Though unrealistic in its assumption of uniform probability of all alignments, IBM model remains the model of thinking for any form of word alignment modeling. We go up the model chain to IBM model 3, showing en route how making assumptions of alignment increasingly realistic increases the complexity of modeling. The number of parameters to be found by the EM algorithm increases rapidly. Two important things covered in this chapter are () finding the best alignment given a translation pair and (2) finding the best translation given a new

24 Preface xxi input sentence, the so-called decoding process. These are representative of SMT processes, besides alignment. The goal of Chapter 4 is to present phrase-based SMT, the ruling framework of SMT. Chapter 3 shows how messy and artificial the task of modeling can become, if alignment starts and stops with words. A simple enhancement, permitting many-many mapping of words, rids the task of modeling of many nonintuitive assumptions. Of course, the notion of nonlinguistic phrases is jarring, but it is inevitable in the kind of translation we are discussing. Probably the most instructive lesson of Chapter 4 is the way phrase alignments are built out of word alignments through bidirectional word alignment (L L 2 and L 2 L ), symmetrization, and phrase expansion. The mathematics of phrase-based SMT, phrase-based decoding, and the Moses SMT environment are the other important subjects covered. A complete decoding example is worked out. In Chapter 5 we go back to the very early days of MT, viz., rule-based MT. The aim of this chapter is to elaborate two types of RBMT: interlingua based and transfer based. Interlingua by its very nature is an ambitious proposition; it demands complete disambiguation on its way to generating the meaning graph of text. But once available, the meaning graph can produce the target translation through the process of natural language generation. Transfer, on the other hand, can pitch its level of analysis and generation on the proximity or distance between the two languages involved. It is instructive to note how the level of transfer differs from one pair of languages to another. The chapter also gives complete walk-throughs on the working of interlingua-based and transfer-based MT. Chapter 6 the final chapter is on EBMT, a development of the 980s through early EBMT was a breakaway from RBMT in that it asked for translation reuse. Translation memory had by then made its appearance, but had left disambiguation to human intervention. Chapter 6 aims to show how translation parts can be extracted and recombined to translate a new input, all automatically. Comparison with SMT is inevitable, which exposes the then inherent weakness of EBMT; viz., there is no concrete scheme for extraction of translation parts from examples. Throughout the book, an attempt has been made to provide insightful examples that help elucidate concepts. The examples are mainly from Indian languages. India is a country whose language diversity is any MT researcher s delight and whose need for MT technology, like Europe s, is critical. That said, the examples illustrate universal translation phenomena through the usage of specific languages. It is hoped that this book will accord a holistic understanding of MT, rather than coverage of a single paradigm. Some important discussions have been left out either because they are not essential for exposition of principles or because they will be covered in a next-level treatise. MT evaluation is important, but has not been dealt with. Like language modeling, it is mainly an exercise in n-gram computation with associated concerns

25 xxii Preface of smoothing. Advancements on phrase-based SMT, factor-based SMT, hybrid SMT, tree-based or so-called hierarchical SMT, and pivot-based SMT have been left out. On the cognitive side, eye tracking of human translators reveals many interesting facts. This is an advanced-level treatise. MT of Indian languages is a large and challenging enterprise. I hope to explore these advanced topics in a future book. Additional material is available from the CRC website: crcpress.com/product/isbn/

26 Acknowledgments As mentioned before, this book is the result of experiences gained in teaching NLP, MT, and AI to batches of students for the last 0 years. Students undergoing these courses, writing quizzes and examinations, doing assignments, interacting in the class, and giving valuable feedback have provided the inspiration, plan of coverage, and exercises in this book; they therefore deserve my first and foremost gratitude. Next, my thanks go to generations of associated faculty members, researchers, students, and administrators of CFILT lab ( The stimulating and inspiring environment of CFILT is a rarity anywhere in the world. The names of the individuals are too numerous to enumerate, but they adorn the web page of the lab (as above) and on my home page ( The SMT part of the book took shape when three students of mine Anoop, Piyush, and Shubham and I decided to offer a tutorial on SMT at the International Conference on NLP, 203 in Noida, India. Not everything in the tutorial has been covered in this book because of time and space limitations. Anoop deserves special mention for a great exposition of phrasebased SMT and Moses, from which the material in this book draws heavily. Discussions with Philip Koehn, Kevin Knight, and other researchers at conferences like ACL, COLING, EMNLP, and NAACL helped set the perspective and scope of this book. The part on interlingua-based MT is based on the vast experience and deep insight gained in not only MT, but also the whole of NLP through the UNL project and UNL meetings across the world since 996. Interactions with Dr. Hiroshi Uchida, Prof. Christian Boitet, Prof. Igor Boguslavsky, Prof. Jesus Cardenosa, Prof. Irina Prodanoff, Prof. Della Senta, Prof. M.G.K Menon, Dr. Ronaldo Martins, Ms. Meiying Zhu, and many others have been invaluable. The United Nations University, Tokyo, the UNDL Foundation, Geneva, and the U++ Consortium, Madrid, deserve everybody s thanks for making these interactions possible. Fortuitously, parallel with UNL, interactions were going on with the Global Wordnet Community Prof. Christiane Fellbaum, Prof. Piek Vossen, Adam Pease, Prof. Key Sun Choi, Dr. Virach Sommervich, Tony Veale, and many others. Next come the members of the IndoWordnet group: Prof. Jyoti Pawar, Prof. Malhar Kulkarni, Prof. Shikhar Sharma, Prof. Arulmozi, Prof. Rajendran, Prof. Soman, Prof. Baskaran, Prof. Bipul Shyam Purkayastha, Prof. Kishorjit, Prof. Hemananda, and many others. These interactions established and refined my thinking on knowledge-based NLP, MT included. The part on transfer-based MT owes its content and insights to the Department of Electronics and Information Technology (DEIty), Ministry of IT, xxiii

27 xxiv Acknowledgments India, which sponsored large consortia projects on machine translation, search, and lexical knowledge networks. Prof. Balakrishnan, Prof. Rajeev Sangal, Mr. F.C. Kohli, Dr. Hemant Darbari, Prof. G. Sivakumar, Prof. C.N. Krishnan, Mrs. Swaran Lata, Dr. Somnath Chandra, Mr. Manoj Jain, and Mr. Vijay Kumar have been instrumental in providing a platform for Indian NLP researchers to be on and to collaborate. Principal investigators of these projects and researchers have provided valuable insights into MT and NLP. With advance apologies for inadvertent omissions, I mention Prof. Dipti Mishra Sharma, Dr. Anuradha Lele, Prof. Sudeshna Sarkar, Prof. Sivaji Bandyopadhyaya, Prof. Sobha Lalitha Devi, Prof. Umamaheswar Rao, Prof. Amba Kulkarni, Prof. Ranjani ParthaSarathy, Prof. T.V. Geetha, Prof. Vasudev Varma, Prof. Mandar Mitra, Prof. Prasenjit Majumdar, Prof. Rakash Balabanta Rai, Mr. Karunesh Arora, Mr. Ajai Kumar, Swati Mehta, Priyanka Jain, Siva Karthik, and Vivek Koul. Many figures in this book and walk-throughs have been provided by Rajen, Ratish, Piyush, Rahul, Rucha, Sreelekha, Ankur, Kritika, and Raj. I am really thankful for their help. Teachers shape our lives. Dr. Vineet Chaitanya and Prof. Rajeev Sangal introduced me to MT through the Anusarak Project during my master s. Mr. Atul Chandra Pal of my high school taught me what flow and lucidity mean. Prof. S.N. Pal, Prof. Shekhar Datta, and many others in college taught me the wonders of natural sciences, with which NLP bears striking similarity. I am grateful to the Department of Computer Science and Engineering Department, IIT Bombay, for the stimulating intellectual environment and freedom they have provided. Working with department chairs and colleagues like Prof. S.S.S.P. Rao, Prof. D.B. Phatak, Prof. Krithi Ramamritham, Prof. S. Sudarshan, Prof. Saketh Nath, Prof. Ganesh Ramakrishnan and many others has, in itself, been an educative experience. Without the background and support of family, nothing is possible. My mother has always emphasized original thinking, and my father, scholarship. My wife, Aparna, and son, Raunak, constitute the loving family and have always urged me to complete the book. Finally, the book would not have seen the light of the day without the persuasion of Aastha Sharma of CRC Press, who is the acquiring editor. I have dreaded her phone calls and s and have labored continuously on the book. I know that behind every great book there is a great project coordinator. Laurie Schlaggs of CRC has provided all kinds of publishing support. Finally, Judith Simon s editing has been invaluable for ensuring quality. My heartfelt thanks to them.

28 About the Author Dr. Pushpak Bhattacharyya is Vijay and Sita Vashee Chair Professor of computer science and engineering at the Indian Institute of Technology Bombay (IITB), where he has been teaching and researching for the last 25 years. Dr. Bhattacharyya was educated at IIT Kharagpur (B.Tech), IIT Kanpur (M.Tech), and IIT Bombay (PhD). While earning his PhD, he was a visiting scholar at MIT, Cambridge, Massachusetts. Subsequently, he has been a visiting professor at Stanford University, University of Grenoble, and a distinguished lecturer at the University of Houston, Texas. Professor Bhattacharyya s research interests lie in natural language processing, machine learning, machine translation, information extraction, sentiment analysis, and cross-lingual search, in which he has published extensively. Currently he is the Associate Editor of ACM Transactions on Asian Language Information Processing. His personal home page URL is xxv

29 This page intentionally left blank

30 Introduction Translation from one language to another is both an art and science (Bell, 99). This book presents the art, science, and technology of machine translation (MT). MT has been in existence since the 940s and has flourished in recent times due to the proliferation of the web. MT was the first computer-based application in natural language processing (NLP), and its history is old (Hutchins and Somers, 992). The field is said to have served as the forcing function for computer science (CS) itself, when the search for automatic means of translation between English and Russian assumed importance in the 960s due to the Cold War. Prior to this translation effort in the background of the Cold War, Alan Turing, working on Enigma to decipher the secret code of war messages during WWII, can be said to have been solving an automatic translation problem though the task is more popularly known as cryptography (Hodges, 992). Indeed in the early days of MT, Warren Weaver, a noted computer scientist, wrote: When I look at an article in Russian, I say: This is really written in English, but has been coded in some strange symbols; I will now proceed to decode. (A letter written in 955) War and commerce have been the two drivers of translation technology. Since ancient times, the bold and adventurous have explored the world. Coming in their wake, men of commerce have carried out trade with nations far removed from their own land. Translation naturally became a necessity in such circumstances. In today s world, navigations through physical landscape have been augmented at a much larger scale with explorations in the virtual world. People are much better connected. But language barriers remain, and pose a challenge to communication. A reality that cannot be wished away is terrorism that has always spurred interest in automatic translation, with the aim of intercepting and interpreting foreign language communication. Deciphering cross- border cell phone messages is looked upon as security critical by governments across nations.

31 2 Machine Translation. A Feel for a Modern Approach to Machine Translation: Data-Driven MT Statistical machine translation (SMT) is the ruling paradigm of machine translation today. Prior to this, example-based machine translation (EBMT) was introduced in the early 980s. Both these paradigms rely on availability of examples of translation, the so-called parallel corpora. To get a feel for what is involved, refer to Table.. In the two columns of the table we have parallel sentences in the Czech language and in English. Following this table is a set of new English sentences, different from those in the parallel corpus, whose translation is required. In other words, one would like to learn the word, syntax, and meaning correspondences between the two languages from the given data and use this gained knowledge to translate new sentences. We have to use the table to translate: I will carry. They drive. He swims. They will drive. The translations respectively are: PONESU. YEDOU. PLAVE. POYEDOU. The reasoning is as follows:. From I carry NESU and I drive YEDU, deduce the verb stem mappings carry NES. 2. Similarly, drive YED; swim PLAV. Table. Parallel Sentences in Czech and English a Czech English NESU I carry PONESE He will carry NESE He carries NESOU They carry YEDU I drive PLAVOU They swim a morphpractice4.pdf

32 Introduction 3 3. Get the pronoun mappings: I U; they OU; he E. 4. Get the tense mappings: will PO. Use is made of the similarity and the differences in the data. For example, the correspondences NESU I carry and YEDU I drive yield the mappings I U, because what is common between the pair of sentences on the English side is I and what is common on the Czech side is U. After dispensing with this mapping, what is left is the two substrings NES and YED, which should map to carry and drive, respectively, since the sentences themselves are in correspondence. At this point we know from the correspondence PONESE He will carry that PO and E align with he and will, but do not know which to which. Use is made at this stage of the correspondence NESE He carries. PONESE and NESE show that E he. Therefore, PO will. The rest of the mappings can be similarly argued out. At this point we are ready to introduce perhaps the most fundamental concept of machine translation, viz., alignment. We have learned the alignments from the data, as shown in Table.2. These learned alignments are used to produce the translation of the new English sentence I will carry. We put the learned pieces together to get PONESU. This step is called decoding. Why we produce PO + NES + U and not NES + PO + U or any other sequence is a matter of what is called the syntax order in the target language. Though the above example captures the essence of data-driven MT, there are complexities that push the framework, especially in the direction of introduction of probability. Let us take the English-Hindi data shown in Table.3. Arguing as in the case of Czech and English, the correspondences Dhotaa hum I carry and chalaataa hum I drive yield the mappings I A hum, and then the mappings Dho carry and chalaa drive. Now ega carries the mapping of He will. Using Dhoegaa He will carry and DhotA he He carries, we propose A he. So eg will. The translation of I will carry is Dhoegaa hum, which we know is wrong. Table.2 Alignments Learned from the Czech-English Data in Table. Czech U E OU PO NES YED PLAV English I He They Will Carry Drive Swim

33 4 Machine Translation Table.3 English-Hindi Data Corresponding to the Czech-English Example Hindi Hindi English ढ त ह Dhotaa hum I carry ढ एग Dhoegaa He will carry ढ त ह Dhotaa he He carries ढ त ह Dhote hem They carry चल त ह chalaataa hum I drive त रत ह terte he They swim Table.4 English-Bengali Data Corresponding to the Czech-English Example Bengali Bengali English বই bai I carry বইব baibe He will carry বয় bay He carries বয় bay They carry চ ল ই chaalaai I drive স তর য় saamtraai They swim Of course, we will not know that Dhoegaa hum I will carry is wrong and will carry on, until we meet evidence to the contrary. This is the main point about statistical MT or, for that matter, anything based on machine learning. Data dictate. The limits to what we can do and how well, are set by the data, and since new data can always overthrow hypothesis, we can at best make probabilistic statements. Difficulties similar to the Hindi-English situation arise for Bengali-English too (Table.4). The reader is invited to work with the data in Table.4 and see the problems. Insight into why such problems arise will be given in later chapters. This has to do with overloading of morpheme functions and syncretism in languages..2 MT Approaches: Vauquois Triangle MT approaches have been grouped into a number of categories in the famous Vauquois triangle, also called the Vauquois pyramid (Vauquois, 968, 988), shown in Figure.. Prof. Bernard Vauquois was a translation theorist. Originally trained as a physicist, he got interested in automatic translation when the problem of translation between English and Russian assumed importance during the Cold War days.

34 Introduction 5 Deep understanding level Ontological interlingua Interlingual level Conceptual transfer Semantico-linguistic interlingua Logico-semantic level Mixing levels Semantic transfer Ascending transfer Multilevel transfer SPA-structures (semantic & predicate-argument) Multilevel description Syntactico-functional level Syntactic transfer (deep) F-structures (functional) Syntagmatic level Syntactic transfer (surface) C-structures (constituent) Morpho-syntactic level Semi-direct translation Descending transfers Tagged text Graphemic level Direct translation Text Figure. Vauquois triangle expressing approaches to machine translation. What the diagram depicts is that translation requires operating at many levels. The left side of the triangle is the ascending side and the right side is the descending side. The left corner mentions the source language and the right corner the target language. When we ascend up the left-hand side, we perform analysis of various kinds on the source input sentence. This processing on the input sentence could involve one or more or all of the following:. Morphology analysis 2. Part of speech (POS) tagging 3. Noun and verb group identification (also called shallow parsing or chunking) 4. Parsing, followed by semantics extraction 5. Discourse resolution in the form of co-references 6. Pragmatics In other words, ascending the left-hand side of the Vauquois triangle until the apex amounts to traversing the NLP layers (Figure.2). After the analysis, the representation of the input sentence is taken through the stage of transfer. This means the representation is brought on the side of the target sentence. For example, the parse tree of John eats bread undergoes

35 6 Machine Translation Discourse and Co-reference Increased Complexity of Processing Semantics Parsing Chunking POS tagging Morphology Figure.2 NLP layer. (From Bhattacharyya, 202.) transfer to produce the parse tree for John bread eats, which conforms to the word order of the target language that follows the subject-object-verb (SOV) order (e.g., in Japanese or Indian languages) (see Figure.3). Interesting elements in the Vauquois triangle are ascending transfers and descending transfers. It is important to remember that in the Vauquois triangle, the higher one goes toward the apex, the higher is the information richness of the representation. Thus, the morphosyntactic level is richer in information than the graphemic level, the syntagmatic level is richer than the morphosyntactic level, and so on (refer to Figure.). We give an example below : Graphemic level: The government levied new taxes. Morphosyntactic level: The/DT government/nn levied/vbd new/jj taxes/nns./. Syntagmatic level: (S (NP (DT The) (NN Government)) (VP (VBD levied) (NP (JJ new) (NNS taxes))) (..))) The parse tree of the sentence (syntagmatic level) reveals the constituent phrases of the sentence and their domination (Carnie, 2006), which is more The annotations on the text are obtained by running the Stanford Parser on the sentence The government levied new taxes (

36 Introduction 7 S S N V N V N V N (transfer svo sov) N N V John eats N John N eats bread bread Figure.3 Illustration of transfer: svo sov. information-rich than the morphosyntactic level, where the raw sentence is tagged with parts of speech. POS-tagged text is in turn more informationrich than the raw input sentence at the graphemic level. What do we gain by taking the level of representation progressively higher? The answer is the universality hypothesis. Universality hypothesis: At the level of deep meaning, all texts are the same, whatever the language. The quoted expressions are quoted because the notions of deep meaning and sameness are by nature imprecise and informal. The consequence of the hypothesis is that the smaller the distance between the source language and the target language, the easier it is for the machine translation system to transfer between the two languages. The distance of transfer decreases with the height at which the transfer takes place in the Vauquois triangle. At the tip of the pyramid, the distance between the two languages is zero, as per the universality hypothesis. This is not to say, however, translation becomes easier as the depth of representation increases. The analysis-transfer-generation paradigm that the Vauquois triangle expostulates has to negotiate the challenges of () ambiguity on the analysis side and (2) lexical and syntactic choices on the generation side. The former appears as lexical, structural, and co-reference ambiguity (Bhattacharyya, 202). For example consider the following sentence:..e: "I went with my friend Washington to the bank to withdraw some money, but was disappointed to find it closed."

37 8 Machine Translation Various ambiguities obtaining in this sentence are: Is bank a noun or verb? Part of speech ambiguity. Is Washington a place or person? Named entity ambiguity. Is bank a place for financial transaction or the borders of a water body? Sense ambiguity. What does it refer to? Co-reference/discourse ambiguity. Who was disappointed to find the bank closed? Pro-drop ambiguity. One might be tempted to think that translation is impossible without first resolving these ambiguities. However, this is not true, since ambiguity need not be resolved, especially in case of translation between a familialy close pair of languages. We show below a part of the language typology tree (Figure.4). Consider the following two sentences in Hindi and Bengali (two familialy close languages as per the tree in Figure.4), which are translations of each other..2.h: म झ आपक म ठ ई ख ल न पड़ ग.2.HT: mujhe aapko mithaaii khilaanii padegii.2.hg: to/by_me to/by_you sweets feed must THE INDO-EUROPEAN FAMILY OF LANGUAGES INDO-EUROPEAN Indian Armenian Iranian Germanic Balto-Slavic Albanian Celtic Hellenic Italic c B.C. c. 000 B.C. Sanskrit Middle Indian Old Persian Persian Avestan Baltic Old Slavic Irish Welsh Gaelic Breton Lithuanian, Russian, Polish, Lettish Czech, Bulgarian, Greek Serbo-Croation, etc. Latin A.D. (Anno Domini) c. 500 A.D. Hindustani, Bengali, and other modern Indian languages N. Germanic E. Germanic Gothic W. Germanic E. Norse W. Norse High German French Provençal Italian Spanish Portuguese Catalan Romanian c A.D. Low German Swedish, Norwegian, Danish, Icelandic, Gothlandic Faroese German Yiddish c. 300 A.D. Old Frisian Frisian Anglo-Saxon (Old English) Middle English Old Saxon Middle Low German Low Franconian Middle Dutch Modern English Plattdeutsch Dutch, Flemish c A.D. Figure.4 Family tree of Indo-European languages. (Courtesy The numbering convention followed for non-english sentences will be C.N.L for the non- English sentence, C.N.LT for the transliterated sentence, C.N.LG for glosses (word-to-word English translations), and finally C.N.E for the English translation. Here C is the chapter no., N is the sentence no., and L is the language tag.

38 Introduction 9.2.E: I/you must feed you/me sweets.3.b: আম ক ত ম য় ম খ ওয় ত হব.3.BT: aamaake tomaay mishti khaaoyaate habe.3.bg: to/by_me to/by_you sweets feed must.3.e: I/you must feed you/me sweets The Hindi sentence has what is called semantic role ambiguity. For the give sweets action, it is not clear who the agent (I/you) and the beneficiary (you/i) are. So is the case with the corresponding Bengali sentence. This is an illustration of the point that not all ambiguities need be resolved before translation. The same situation is obtained if the translation is into Marathi or Gujarati. The reader is invited to translate the Hindi sentence into English and be convinced that unique translation cannot be produced without first resolving the ambiguity. So is the case if the target language is from the Dravidian family. The work on the analysis side increases as the distance between the two languages increases. The complexity of target language generation manifests in the challenge of choosing the correct register, topicalization, focus, etc., none of which are easy problems. For example, to express the thought that John s mother will visit him in Christmas, we have the option of choosing from among the words mother, mom, mummy, amma, and so on. Only the first option is permissible in a formal discourse like writing a leave application. The linguistic term for making such a choice is register. Topicalization and focus refer to the process of departing from the canonical (i.e., the most common) order for the purpose of emphasizing a component of the meaning. For example, to emphasize in Christmas, we might want to move the phrase to the beginning of the sentence, i.e., In Christmas, John s mother will visit him, since the start of a sentence is the most attention-catching location. Note that some languages do not allow the adjunct in Christmas to be placed at the end of the sentence. In such cases the emphasis is introduced using particles. Hindi, for example, may use the particle ह (hii) after the translation of Christmas. Generation of such particles in the translation necessitates using additional machinery..2. Understanding Transfer over the Vauquois Triangle The Vauquois triangle expresses the analysis-transfer-generation (ATG) process as the foundation of machine translation. To concretize our understanding of the ATG process, we take the example of translation from a free word order language to a language with a relatively fixed word order. Consider the following Hindi-English example:.4.h: सरक र_न च न व _क _ब द म बई म कर _क _म ध यम_स अपन र जसव_क बढ़ य.4.HT: sarkaar ne chunaawo ke baad Mumbai me karom ke maadhyam se apne raajaswa ko badhaayaa

39 0 Machine Translation.4.HG: Government_(ergative) elections_after Mumbai_in taxes_ through its revenue_(accusative) increased.4.e: The government increased its revenue after the elections through taxes in Mumbai The number of possible variations in these example sentences can be found as follows. The canonical order of words in English is subject-verb-object (SOV). Table.5 shows the subject, object, and verb in.4.e. The government, increase, and its revenue are the core elements (arguments of increase ) of.4.e. The other elements in the sentence are the adjuncts (Table.6). The locations before the subject (P 0 ), between the subject and the verb (P ), between the verb and the object (P 2 ), and after the verb (P 3 ) are available for placing the instrumental adjunct through taxes in Mumbai and the temporal adjunct after the elections, as shown in Figure.5. Though the two adjuncts can occupy any of the four positions P 0, P, P 2, and P 3, idiomaticity would allow only P 0 or P 3 for the temporal adjunct (after the elections) and P 3 for the instrumental adjunct (through taxes in Mumbai). Thus, only two additional variations are possible on.4.e..5.e: After the elections, the government increased its revenue through taxes in Mumbai.6.E: The government increased its revenue through taxes in Mumbai after the elections Hindi, however, allows many more variations. First, the Hindi canonical order is subject-verb sequence. The object position is relatively flexible. Table.5 Subject, Verb, and Object in Sentences.4.E and.4.h Entity English Hindi Subject The government सरक र (sarkaar) Verb Increased बढ़ य (badhaayaa) Object Its revenue अपन र जसव (apne raajaswa) Table.6 Adjuncts in Sentences.4.E and.4.h Adjunct English Hindi Instrumental Through taxes in Mumbai म बई_म कर _क _म ध यम_स (mumbai me karo ke maadhyam se) Temporal After the elections च न व _क _ब द (chunaawo ke baad)

40 Introduction The Government increased its revenue P 0 P P 2 P 3 Figure.5 Subject, verb, and object in.4.e. sarkaar_ne badhaayaa P 0 P P 2 Figure.6 Subject, verb, and object in.4.h. Refer to Figure.6. There are three positions, and two adjuncts and one object (apne rajaswa_ko). Idiomaticity restrictions do not allow the object or the adjuncts to be placed after the verb, thus ruling out P 2. Now the object can occupy either P 0 or P. Two positions open up around the object. Then three positions can be filled by the two adjuncts (chunaava_ ke_baad and mumbai_me karom_ke_maadhyam_se) in six ways. Thus, the allowable number of variations in Hindi for the given sentence is 2 6 = 2, some of which are shown in.7.h through.0.h..7.h: च न व _क _ब द सरक र_न म बई_म कर _क _म ध यम_स अपन र जसव_क बढ़ य.7.HT: Elections_after government_(erg) Mumbai_in taxes_through its revenue increased..8.h: च न व _क _ब द म बई_म कर _क _म ध यम_स सरक र_न अपन र जसव_क बढ़ य.8.HT: Elections_after Mumbai_in taxes_through government_(erg) its revenue increased..9.h: च न व _क _ब द म बई_म कर _क _म ध यम_स अपन र जसव_क सरक र_न बढ़ य.9.HT: Elections_after Mumbai_in taxes_through its revenue government_(erg) increased..0.h: म बई_म कर _क _म ध यम_स च न व _क _ब द सरक र_न अपन र जसव_क बढ़ य.0.HT: Mumbai_in taxes_through elections_after government_(erg) its revenue increased. ne is the ergative marker.

41 2 Machine Translation What has all this got to do with the ATG process? If the word order can vary considerably in source language sentences, syntactic functional representation (refer to Figure.) is the most appropriate one for such sentences for the purpose of translation. This level of representation consists of the words and dependencies. For example, for the sentence.4.7. Root is a generic node that starts the dependency tree. The main verb is just below the root node. Arguments and adjuncts in the sentence link to the main verb through dependency relations (Figure.7). The generation of the dependency tree DT from the input sentence is a fairly involved analysis step, going up the left side of the Vauquois triangle. After this analysis step, from the DT, the target language sentence is produced directly through word substitution and syntax generation. The target language is fixed order, and so very little choice is available for word order. We take up another example of transfer. We discuss a case where the translation has to commit to a meaning, because the translation of the function words have to be committed to. Some parsers produce multiple parse trees, leading to multiple translation outputs ( nlp.stanford.edu/software/parser-faq.shtml#h).

42 Introduction 3 root badhaayaa sarkaar_ne nsubj dobj prep prep ke_maadhyam_se raajasva_ko ke_baad obj karom poss obj pobj apane chunaavom me obj mumbai Figure.7 Dependency representation of..h; the relations are shown in italics. Consider the well-known ambiguous sentence in English I saw the boy with a telescope. The ambiguity is that of structure, more specifically that of preposition phrase (PP) attachment: Should with a telescope be attached to the boy or to saw? The meaning changes according to the attachment. Now when translating from English to German, nothing special is required. German can afford to retain the ambiguity in the translated sentence Ich sah den Jungen mit einem Teleskop. The German function word mit is as noncommittal as the English counterpart with. However when we translate this to Hindi, we have to decide between se (meaning with ) and ke_saath (meaning carrying in the given context) before producing the translation. I saw the boy with a telescope maine us ladke ko ek durbin se dekha maine us ladke ko ek durbin ke saath dekha Here arises an interesting case of transfer. After the analysis stage produces the parse tree(s) of the English sentence, context has to be consulted to disambiguate among the options. Some parsers produce multiple parse trees, leading to multiple translation outputs ( nlp.stanford.edu/software/parser-faq.shtml#h).

43 4 Machine Translation.2.2 Understanding Ascending and Descending Transfer Transfer over the Vauquois triangle is not always horizontal, i.e., level preserving in terms of representation over the transfer. Consider the simplified Vauquois triangle in Figure.8. It is possible that the generation process has to start from a representation that is at a lower level than the output of the analysis. This is called descending transfer. For example, we obtain the semantic structure from the source sentence and convert the structure to a syntax structure or word structure. The opposite case is that of ascending transfer, where the generation process starts from a representation at a higher level than the output of the analysis stage. We illustrate descending and ascending transfers through two examples Descending Transfer Nominal verbs, which are derived from nouns, are common in Sanskrit. A subtype of Sanskrit nominal verbs is what may be called behave-like verbs. For example, see the following sentence:..s: स ह सन स न व नर न प यत was there before!..st: simhaasanaasiino vaanaro nripaayate..sg: Sitting-on-throne monkey behaves-like-king..e: A monkey sitting on (king s) throne behaves like the king Interlingua Semantic Structure Semantic Structure Syntactic Structure Syntactic Structure Word Structure Word Structure Figure.8 Simplified Vauquois triangle.

44 Introduction 5 How will the translation of English to Sanskrit take place in such a situation? Can we lexicalize the translation of the phrase behaves like a king? That is, can we store in the lexicon the mapping Behaves like a king न प यत and plug it in the translation? The answer, in general, is no. An arbitrary amount of text can appear within the structure as follows: Behaves, it seems, like a king Behaves, to my mind, like a king Behaves very much like a king Behaves like a majestic king and so on. Here dependency parsing comes to the rescue. Whatever the text inserted in the structure, the core phrase behaves like a king can be retrieved from the dependency tree of the source sentence and replaced with nripaayate. This is explained through the dependency expressions below: det(monkey-2, A-) nsubj(behaves-0, monkey-2) partmod(monkey-2, sitting-3) prep(sitting-3, on-4) det(throne-6, the-5) pobj(on-4, throne-6) prep(throne-6, of-7) det(king-9, a-8) pobj(of-7, king-9) root(root-0, behaves-0) advmod(much-2, very-) acomp(behaves-0, much-2) prep(behaves-0, like-3) pobj(like-3, king-5) det(king-5, the-4) These dependency relations can be obtained by passing the sentence through the dependency analyzer (going up the left side of the Vauquois triangle). The application of the transfer rule prep (behaves-0, like-3) pobj(like-3, x-5) (A) Xaayate det (X-5, a-4) at one shot produces the target word in Sanskrit. X is any noun (see Figure.9).

45 6 Machine Translation prep(behaves 0, like 3) pobj (like 3, x 5) det(x 5, a 4) descending Xaayate Figure.9 Descending transfer Ascending Transfer For illustration of ascending transfer, we choose an example of Finnish- English translation. Finnish is morphologically a highly complex language (Karlsson, 999), with a great deal of agglutination. istahtaisinkohan: I wonder if I should sit down for a while ist: sit, verb stem ahta: verb derivation morpheme, to do something for a while isi: conditional affix n: first-person singular suffix ko: question particle han: a particle for things like reminder (with declaratives) or softening (with questions and imperatives) We first isolate the morphemes, which amounts to going some distance up the left side of the Vauquois triangle (analysis). Then we substitute the morphemes with their English equivalent as shown above (transfer). What do we do after that? It is important to note that at this stage we have a bag of words and phrases of English and speech acts, viz., {sit, to do something for a while, if, I, <speech act of question + speech act of softening equivalent to wonder if combination in English >} It is impossible for the generation algorithm to directly synthesize an English sentence from these entities. In the least, the algorithm needs to know who the subject of sit is. Do something in do something for a while needs to bind to sit through co-reference. Then for a while should set up a dependency I am thankful to Prof. Aarne Ranta of Gothenberg University for providing this example of Finnish Agglutination.

46 Introduction 7 relation with sit. The verb wonder has to have the same subject as that of sit the so-called pro-drop problem. All this and more suggest creating through actual representation or notionally through steps in a procedure a structure, which is nothing but the dependency tree of the target sentence. This is ascending transfer (see Figure.0) Ascending Transfer due to Tool and Resource Disparity More often than not, ascending and descending transfers are caused by the asymmetry in the repository of tools and resources available for the two languages involved in translation. Consider the case of generating Hindi translation of the English sentences:.2.e: Jill broke the window.3.e: The window broke.4.e: The stone broke the window The translations of these three sentences are:.2.h: ज ल न ख डक त ड़_द.2.HT: jil ne khidkii tod_dii.2.hg: jill <ergative> window broke.3.h: ख डक ट ट_ग य.3.HT: khidkii tut_gayii.3.hg: window broke.4.h: पत थर स ख डक ट ट_ग य.4.HT: patthar se khidkii tut_gayii.4.hg: stone <instrumental case maker> window broke Though John, window, and the stone are in subject positions in these three sentences, semantic roles played by them are very different. This manifests in the three different case markers for the three subjects, viz., ne, null, and se. Dependency tree of I wonder if I should sit for a while ist+ahta+isi+n+ko+han I wonder if I should sit for a while Figure.0 Ascending transfer.

47 8 Machine Translation Suppose, for argument s sake English did not have a semantic role labeler and in Hindi had. Then the transfer will do lexical substitution of English lexemes into Hindi and create a semantic role labeled graph for the sentence as shown in Figure.. From these semantic graphs it will be easy to produce the Hindi sentences. However, we note the crucial role played by ascending transfer in this translation. Tools disparity between the source language and the target language is at the heart of this transfer. tod_dii agent object jil khidkii tut_gayii object khidkii tut_gayii instrument object patthar khidkii Figure. Semantic role graphs of sentences.2.h,.3.h, and.4.h.

48 Introduction 9.3 Language Divergence with Illustration between Hindi and English At the root of all the challenges of MT lies language divergence (LD). LD is the phenomenon of languages expressing meaning in divergent ways. The further two languages are from each other in the typology tree (Figure.4), the greater is the divergence likely to be between them. Thus, the divergence between English and Russian is more than that between English and German; the divergence between Hindi and English is much more than that between Hindi and Marathi. In fact, language pairs like Spanish and Catalan, Hindi and Urdu, and Bengali and Assamese are almost isomorphic to each other in the sense that word-to-word substitution at each position produces the translation on one language from the other, in most cases. The importance of this point will be brought home when we discuss word alignment in Chapters 2 and 3. In this section, we discuss language divergence in a formal setting proposed by Dorr (993)..3. Syntactic Divergence Dorr gives the following divergences arising from structural and syntactic aspects of German, Spanish, and English languages: Constituent order divergence Adjunction divergence Preposition-stranding divergence Movement divergence Null subject divergence Dative divergence Pleonastic divergence.3.. Constituent Order Divergence Constituent order divergence relates to the divergence of word order between two languages. Essentially, the constituent order describes where the specifier and the complements 2 of a phrase are positioned. For example, in English the complement of a verb is placed after the verb and the specifier of the verb is placed before. Thus, English is an SVO language. Hindi, on the other hand, is an SOV language. Sentence.8 shows the constituent order divergence between English and Hindi..8.E: Jim (S) is playing (V) tennis (O).8.H: ज म (S) ट न स (O) ख ल रह ह (V) The material in this section is mostly from Dave, Parikh, Bhattacharyya, Specifier, complement, and such other formal linguistic concepts come from the well-known X-bar theory introduced and developed by Noam Chomsky in the 960s.

49 20 Machine Translation.8.HT: jeem (S) tenis (O) khel rahaa hai (V).8.HG: Jim tennis playing is Jim is the subject (S), is playing the verb (V) and tennis the object (O). Also, in Hindi, the qualifier of the complement succeeds the verb, whereas in English, it succeeds the complement:.9.e: He saw (V) a girl (C) whose eyes were blue (Q).9.H: उस न एक लड़क (C) क द ख (V) ज सक आ ख न ल थ (Q)..9.HT: usne ek ladakee (C) ko dekhaa (V) jisakee aankhen neelee thee (Q).9.HG: He_subj girl_to saw whose eyes blue were Here girl is the complement (C) and whose eyes were blue is the qualifier (Q) Adjunction Divergence Syntactic divergences associated with different types of adjunct structures are classified as adjunction divergence. Hindi and English differ in the positioning of the adjective phrase, which is a type of adjunct. In the former, this phrase can be placed to the left of the head noun. This is not allowed in English..20.E: *the [living in Delhi] boy.20.h: [द लल म रहन व ल ] (AP) लड़क.20.HT: [dillii mein rahanevaalaa] (AP) ladakaa.20.hg: [delhi in living] boy AP is the adjective phrase. The suffix vaalaa added to rahanaa ( live ) makes it an adjective phrase. This construction, in general, applies only to habitual actions. Consider:.2.H: ज म न [प टर क पस द आन व ल ] त हफ भ ज.2.HT: jeem ne [peetar ko pasand aanevaalaa] tohafaa bhejaa.2.hg: Jim <subj-marker> Peter to like <habitual-action-marker> gift sent.22.h: ज म न वह त हफ भ ज ज प टर क पस द आ य.22.HT: jeem ne vah tohafaa bhejaa jo peetar ko pasand aayaa.22.hg: Jim <subj-maker> that gift sent which Peter to like came.23.h: ज म न वह त हफ भ ज ज प टर क पस द ह.23.HT: jeem ne vah tohafaa bheejaa jo peetar ko pasand hai.23.hg: Jim <subj-marker> that gift sent which Peter to like is Sentences.22 and.23 are equivalent. Sentence.22 cannot use vaalaa. Ungrammatical sentences are marked with *, as per standard practice in linguistics.

50 Introduction 2 Another divergence in this category is PP adjunction with respect to a verb phrase. In Hindi a PP can be placed between a verb and its object or before the object, while in English it can only be at the maximal level (i.e., not between the verb and its object)..24.e: He called me [to his house] (PP) He called [to his house] me H: उसन म झ [अपन घर] (PP) ब ल य (ko of ghar_ko dropped).24.ht: usne mujhe [apne ghar] (PP) bulaayaa.24.hg: He me his house called.3..3 Preposition-Stranding Divergence This divergence is accounted for by the choice of proper governors..25.e: Which shop did John go to?.25.h: क स द क न ज न ग य म? 2.25.HT: kis dukaan john gayaa mein.25.hg: Which shop John went in Sentence.25.H, which is a literal translation of.25.e, is syntactically incorrect, as the case marker mein ( to ) cannot be a proper governor for the noun phrase. In English, the preposition to is a proper governor for the trace. 3 The case marker mein is required to follow the noun, which in this case is dukaan ( shop ) Null Subject Divergence In Hindi, unlike in English, the subject of the sentence can be left implicit..26.e: Long ago, there was a king.26.h: बह त पहल एक र ज थ.26.HT: bahut pahale ek raajaa thaa.26.hg: Long ago one king was A semantically vacuous subject like there is required in the sentence.26.e, but not so in Hindi. Hindi allows dropping of the subject where the subject is obvious, as in.27.h..27.h: ज रह ह.27.HT: jaa rahaa hum.27.e: going am In Hindi, PP is the postposition phrase. 2 Am going. 3 Concepts of governor and trace come from the X-bar theory.

51 22 Machine Translation The subject I is absent. Such omissions are permitted only in two situations. The first is that a pleonastic is eliminated, and the second is when a valid subject is omitted, as its implicit presence is reflected through the morphology of the predicate Pleonastic Divergence A special kind of null subject divergence is the pleonastic divergence. A pleonastic is a syntactic constituent that has no semantic content, as in:.28.e: It is raining. It has no semantic role. Similarly in sentence.26.e, there does not have any semantic role. Frequently, pleonastics are linked to another constituent that carries the appropriate semantic content..28.h: * यह ब र श ह रह ह.28.HT: yah baareesh ho rahee hai.28.hg: This rain happen -ing is The correct translation of.28.e is.29.h:.29.h: ब र श ह रह ह.29. HT: baareesh ho rahee hai.29.hg: This rain happen -ing is.3.2 lexical-semantic Divergence While syntactic divergences result from structural differences, i.e., in the difference in the positioning of sentence constituents, lexical-semantic divergences arise from lexico-semantic properties of items in the lexicons of the two languages. Following are the types of lexical-semantic divergences: Conflational divergence Categorial divergence Head-swapping divergence Lexical divergence.3.2. Conflational Divergence Conflation is the lexical incorporation of necessary components of meaning (or arguments) of a given action. This divergence arises from a variation in the selection of the word between the source language and the target language:

52 Introduction E: Jim stabbed John.30.H: ज म न ज न क छ र स म र.30.HT: jeem ne john ko chhoore se maaraa.30.hg: Jim-subj John-to knife-with hit Here, stab does not have a single-word equivalent in Hindi. We require the phrase छ र स म र chhoore se maaraa ( hit with a knife ). The opposite case of Hindi words being conflational is seen for both noun (devar, husband s younger brother ) and verb (ausaanaa, to cause to ripen ). Here is another example:.3.e: Jim entered the house.3.h: ज म न घर म प रव श दक य.3.HT: Jeem ne ghar mein pravesha kiyaa.3.hg: Jim <subj marker> house into entry did The Hindi sentence diverges from the English sentence, since the verbal object is realized as a noun phrase (house) in English and as a prepositional phrase (ghar mein, into the house ) in Hindi. In English, both enter and enter into will be allowed, whereas in Hindi the prepositional phrase should strictly be used Categorial Divergence Categorial divergence arises if the lexical category of a word changes during the translation process. Consider:.32.E: They are competing.32.h: व म क बल कर रह ह.32: HT: ve muqaabalaa kar rahe hain.32.hg: They competition doing <present tense, progressing aspect, plural> Here, competing is expressed as a verb in English and as a noun-verb combination ( do competition ) in Hindi. This divergence is very common in English-to-Hindi MT, and in general in English to an Indian language MT. Hindi, like most Indian languages, forms conjunct verbs in which a noun is followed by a form of kar ( do ) or ho ( be ) to express the action suggested by the noun Head-Swapping Divergence Head-swapping divergence is divided into two further subcategories of demotional and promotional divergences. Demotional divergence is characterized by the demotion (placement into a position lower down in the X-bar

53 24 Machine Translation tree) of a logical head. In such a situation, the logical head is associated with the syntactic adjunct position, and then the logical argument is associated with a syntactic head position. For example, in.33.e, the word suffice is realized as the main verb in English but as an adjectival modifier kaafee hai in Hindi:.33.E: It suffices.33.h: यह क फ ह.33.HT: yaha kaafee hai.33.hg: It sufficient is Promotional divergence is the promotion (placement into a higher position) of a logical modifier. The logical modifier is associated with the syntactic head position, and then the logical head is associated with an internal argument position, as exemplified in e: The play is on.34.h: ख ल चल रह ह.34.HT: khel chal rahaa hai.34.hg: play go -ing is Here the modifier is on is realized as an adverbial phrase in English, but as the main verb chal rahaa hai ( is going on ) in Hindi Lexical Divergence Lexical divergence means that the choice of a target language word is not a literal translation of the source language word. However, lexical divergence arises only in the context of other divergence types. In particular, lexical divergence generally co-occurs with conflational, structural, and categorial divergences. An example is shown in.35:.35.h: ज न जबरदसत घर म घ स ग य.35.HT: john jabardasti ghar mein ghus gayaa.35.hg: John forcefully house-in enter went.35.e: John broke into the house Here the divergence is lexical in the sense that the target language word is not a literal translation of the source language word. It is important to carefully study language divergences as they give a theoretical framework in which to understand the complexity of translation. Many divergences can be tackled by rules in the translation process, while other divergences have to be simply memorized, i.e., pattern substituted.

54 Introduction 25 In general, structural divergences are tackled by rules, while lexical-semantic divergences are tackled by machine learning. What rule can one give for the divergence of conflation, for example? What rule does stab obey when it conflates to chhoore se maaranaa in getting translated to Hindi? And what rule does sit obey when it does not conflate and translates to baithanaa in Hindi?.4 Three Major Paradigms of Machine Translation In this book we will study three large paradigms of machine translation: rule-based (RBMT), statistical (SMT), and example based (EBMT). In their pure forms, the first is rule governed or knowledge based, the second is data driven, and the third is intermediately placed (Figure.2). It is useful to taxonomize the three paradigms of MT (Figure.3). We know analysis-transfer-generation (ATG) is the process by which MT generates translations of source sentences into the target language. The Vauquois triangle places these operations pictorially as ascendance up the left arm, movement to the right side, and descent down the right arm. In this whole ATG chain, if human-created rules exchange are only applied, then we have the so-called rule-based MT system (RBMT). There are rules for analyzing the source sentence, rules for transferring the representation resulting from the analysis stage, and finally, there are rules for generating the target sentence from the transferred representation. All these rules are limited by the knowledge and expertise of the rule makers as per their understanding of the properties of the two languages involved and the domain of discourse. Rule-based systems are high precision and low recall; when they apply they almost always get it right (high precision), but it is not often that they apply (low recall). Also, rules conflict; i.e., more than one rule becomes applicable to a situation. Therefore, rules have to be ordered carefully. RBMT EBMT SMT Figure.2 RBMT-EBMT-SMT spectrum: knowledge (rules) intensive to data (learning) intensive.

55 26 Machine Translation Machine Translation Direct MT Rule-Based MT Data-Driven MT Transfer Interlingua EBMT SMT Figure.3 Perspectivizing EBMT. EBMT is data driven like SMT, but is closer to RBMT in its deeper analysis of the source sentence. A more specific rule coming later in the textual order will never apply, in case the rules are tried in the order of their appearance. That said, rules have the great advantage of being able to supply explanation. We know exactly what is going on in the system when the output is required to be analyzed. We therefore conclude that in RBMT, the onus of empowering the MT system lies with the human expert. Let us now consider the other end of the spectrum in Figure.2, i.e., statistical MT (SMT). In pure SMT, there are no manually created ATG rules. There are parallel corpora, i.e., collection of translation pairs. Translation patterns are learned from these data. These patterns are mappings of words and phrases from the source language to the target language along with probabilities; because these mappings are many to many, probabilities are a result of inherent ambiguity in languages and redundancy in how they express meaning. After the mappings are learned from the parallel corpus, in a new translation situation, parts of the input sentence are matched in the mapping table (called phrase table in SMT parlance), their translations picked up along with probability values, and these translations stitched together (called decoding) along with a probability score. The highest probability output string is provided as the translation. In SMT, the onus of empowering the MT system lies on the data and machine learning. Human knowledge and parallel data are two ends of the spectrum discussed so far. These opposing trends of human knowledge-driven and data-driven processing are the story of whole artificial intelligence (AI) too, are they not? In his very illuminating paper A Pendulum Swung Too Far, Ken Church (20) makes the interesting observation that every 20 years the

56 Introduction 27 rationalist (knowledge-based, theory-driven) and empiricist (data-driven, empirical) approaches alternate in their domination of providing methodologies and philosophical vantage points for artificial intelligence. Natural language processing and its subfield machine translation are no exceptions. EBMT is shown to be positioned intermediate between RBMT and SMT. This is because humans (rules) and data (ML) synergistically create translation in this paradigm. The translation patterns come from the data, but identifying these patterns is heavily rule driven. One reason behind the stupendous success of SMT as the reigning paradigm of machine translation is the discovery of the expectation maximization-based word alignment algorithm for SMT. SMT had a very principled way based on probability of detecting the most likely word correspondences between parallel sentences. Word alignment led to phrase alignment, tree alignment, factor alignment, and so on. We study SMT in Chapters 2, 3, and 4. EBMT is discussed in Chapter 6 after the topic of RBMT in Chapter 5. To get a feel for the essential difference among these three paradigms of MT, consider a tricky translation situation the translation of the English word have. We take three sentences:..36.e: Peter has a house E: Peter has a brother E: This hotel has a museum Though the English sentences have very similar structures, their translations are very different in many languages. We take English-Marathi examples:. a..36.e: Peter has a house (ownership) b..36.m: प टरकड एक घर आह c..36.mt: piitar kade ek ghar aahe d..36.mg: Peter with a house is 2. a..37.e: Peter has a brother (kinship) b..37.m: प टरल एक भ ऊ आह c..37.mt: piitar laa ek bhaauu aahe d..37.mg: Peter with a brother is 3. a..38.e: This hotel has a museum (situatedness) b..38.m: ह य ह ट लमध य एक स ग रह ल य आह c..38.mt: hyaa hotel madhye ek samgrahaalay aahe d..38.mg: this hotel in museum is

57 28 Machine Translation The syntactic subjects and objects in these sentences determine the translation of has, which are, respectively, kade aahe, laa aahe, and madhye aahe. In RBMT, we will have to construct rules like:. If the syntactic subject is animate and the syntactic object is owned by the subject, then have should translate to kade aahe. 2. If the syntactic subject is animate and the syntactic object denotes kinship with the subject, then have should translate to laa aahe. 3. If the syntactic subject is inanimate, then have should translate to madhye aahe. One can immediately see the severe challenge and open-endedness of the enterprise of construction of such rules. How do we encode animacy, ownership, situatedness, and such other classically intricate semantic attributes? Linguistics, philosophy, and cognitive science have spent millennia grappling with the problem of defining, describing, encoding, and annotating these semantic properties for humans, to say nothing of the challenge of describing them to a computing machine! EBMT would instead use portions of example sentences, thus bypassing the complication of representing and using semantic attributes. It would work with templates that are learned from the data, i.e., pairs of parallel translations: X have Y Xkade Y aahe Xlaa Y aahe X madhye Y aahe Then textual separation within the structures kade-aahe, laaa-ahe, and madhye-aahe can be dealt with effectively. We will see later these rules are like transfer rules. In the context of syntactic objects like house, car, racket, etc. (which have similar properties like inanimacy, ownability, etc.), have will have one translation; in the context of objects with other properties, it will have another translation. Ontological positions of these context words play a crucial role, because these ontological positions correspond to the specific properties of the objects denoted by these words. Lastly, we will see how SMT could deal with the translation of have. SMT will memorize translation strings like: has a house kade ek ghar aahe has a car kade ek gaadii aahe has a brother laa ek bhaau aahe has a sister laa ek bahiin aahe

58