Word Re Ordering and Dynamic Programming based Search

Word Re Ordering And Dynamic Programming Based Search-Free PDF

  • Date:12 Sep 2020
  • Views:1
  • Downloads:0
  • Pages:153
  • Size:806.72 KB

Share Pdf : Word Re Ordering And Dynamic Programming Based Search

Download and Preview : Word Re Ordering And Dynamic Programming Based Search


Report CopyRight/DMCA Form For : Word Re Ordering And Dynamic Programming Based Search


Transcription:

Acknowledgements, I would like to thank my scientific advisor Prof Hermann Ney for his. adamant criticism of all my scientific pursuits I would like to thank the. members of my committee Prof Francisco Casacuberta who gave valuable. advice on this work as well as Prof Klaus Indermark and Prof Gerhard. My work has been influenced in a multitude of ways by my group members. in Aachen Sonja Niessen Franz Josef Och Hassan Sawaf Nicola Ueffing. and Stefan Vogel The first version of the dynamic programming decoder. was joint work with Stefan Vogel Hassan Sawaf and Alex Zubiaga The. concept of inverted alignments is due to Sonja Niessen Franz Josef Och. provided the training software for the IBM 4 model Nicola Ueffing carried. out some of the experiments on the French to English translation task Ag. niezska Muhr worked on preparing the test data for the German to English. translation experiments For all administrative matters concerning my work. and my thesis I would like to thank Christiane Beumers Ingeborg Jen. nessen and Gisela Gillmann, Thanks a lot to my beloved wife and she might reply to my thankfulness. with a cheeky wry smile of her own My son is growing up while I am. working And now that I might never again want to be a doctor I could. finally explain to him that computers are only the second most interesting. things in the world I would like to thank my mother my father and my. sister for their support Still while being at home I don t feel like touching. upon any topic related to my work, In this work a new search procedure for statistical machine translation. SMT is proposed that is based on dynamic programming DP The start. ing point is a DP solution to the traveling salesman problem that works. by jointly processing tours that visit the same subset of cities For SMT. the cities correspond to source sentence positions to be translated Impos. ing restrictions on the order in which the source positions are translated. yields a DP algorithm for carrying out the word re ordering in SMT effi. ciently A simple data driven search organization allows the algorithm to. prune unlikely translation hypotheses Search restrictions especially useful. for the translation directions German to English and English to German are. presented A generalization of these re ordering restrictions is given that is. applicable to several different translation directions Translation results are. reported with a widely used SMT model,Zusammenfassung. In dieser Arbeit wird ein neuer Suchalgorithmus fu r die Statistische. Maschinelle U bersetzung vorgestellt Der Algorithmus beruht auf dem. Prinzip der Dynamischen Programmierung DP Ausgangspunkt ist eine. DP Lo sung fu r das Traveling Salesman Problem die darauf beruht da. Untermengen von Sta dten gemeinsamen bearbeitet werden ko nnen ohne. die Reihenfolge in der die Sta dte besucht wurden zu beachten In. der Statistischen Maschinellen U bersetzung entsprechen den Sta dten Po. sition in dem zu u bersetzenden Satz Unter der Verwendung von. geeigneten Einschra nkungen der erlaubten Wortumordnungen erha lt man. einen effizienten DP basierten Suchalgorithmus Eine daten abha ngige. Suchorganization erlaubt es unwahrscheinliche U bersetzungshypothesen. zu prunen Sucheinschra nkungen die besonderes nu tzlich fu r die. U bersetzungsrichtungen Deutsch Englisch und Englisch Deutsch sind wer. den vorgestellt Die Umordnungseinschra nkungen werden verallgemeinert. wodurch sie auf mehrere unterschiedliche U bersetzungsrichtungen anwend. bar sind U bersetzungsergebnisse werden fu r ein allgemein verwendetes. U bersetzungsmodell und verschiedene U bersetzungsrichtungen vorgestellt. 1 Introduction 1,1 1 Introduction to Machine Translation 1.
1 2 Introduction to Statistical Machine Translation 2. 1 3 Baseline Alignment Models 4,1 3 1 HMM Model Training 6. 1 3 2 IBM Model Training 7,1 4 State of the Art in Statistical MT 8. 2 Objectives 12,3 Translation Model Extensions 15,3 1 Monotone Alignment Model 15. 3 2 Extended Language Model 18,3 2 1 Trigger Pairs in Language Modeling 18. 3 2 2 Selection of High Level Triggers 20,3 2 3 Selection of Unigram Level Triggers 22.
3 2 4 Selection of Low Level Triggers 22,3 2 5 Multi Trigger Model 23. 3 3 Extended Lexicon Model 25,3 3 1 Word Joining Viterbi Path Criterion 25. 3 3 2 Word Joining Likelihood Criterion 27,3 3 3 Selection of Target Word Joinings 33. 3 3 4 Selection of Multi Word Extensions 35,4 Search Algorithm for Translation 37. 4 1 Introduction into Dynamic Programming 37, 4 2 Dynamic Programming for Machine Translation 39.
4 3 DP Algorithm Using Monotone Alignments 40,4 4 DP Algorithm Using Inverted Alignments 43. 4 5 Held Karp Algorithm for Traveling Salesman Problem 45. 4 6 DP Algorithm for Statistical Machine Translation 47. 4 6 1 Verb Group Re ordering German to English 48,4 6 2 Word Re ordering Generalization 51. 4 6 3 Word Re ordering IBM Style Restrictions 56,4 6 4 Empirical Complexity Calculations 56. ii CONTENTS,4 7 Beam Search Pruning Techniques 58,4 8 Accelerated Recombination 60. 4 9 Details for IBM 4 Model 60,4 10 Beam Search Implementation 62.
5 Experimental Results 71,5 1 Extended Language Model Trigger Pairs 71. 5 1 1 Trigger Pair Examples 72,5 1 2 Trigger Pair Perplexity Results 75. 5 1 3 Conclusions on the Use of Word Trigger Pairs 76. 5 2 Extended Lexicon Model Target Word Joining 77,5 3 Details on the IBM Model Training 80. 5 4 Details on the Translation Procedure 80,5 5 Performance Measures for Evaluation 82. 5 6 Experiments on the German English Verbmobil Corpus 84. 5 7 Experiments on the Italian English FUB Corpus 100. 5 8 Experiments on the French English Hansard Corpus 103. 6 Discussion and Future Work 106,7 Summary 110, A Appendix Quantification of Re ordering Restrictions 112.
B Complexity of Different Re ordering Schemata 114. B 1 Pseudo Translation Task 114,B 2 Word Re ordering Complexity 115. C Formal Description for the GE Re ordering Constraint 121. D Search Parameter File 123,E Mathematical Symbols 124. E 1 Translation Model Symbols 124,E 2 Trigger Language Model Symbols 125. E 3 Extended Lexicon Model Symbols 125,E 4 Translation Search Symbols 126. List of Figures,1 1 Transfer and Interlingua pyramid diagram 1.
1 2 Architecture of the statistical translation approach based on Bayes decision. 1 3 Example of word alignment for two German to English sentence pairs taken. from the Verbmobil corpus 4,3 1 Illustration of monotone HMM alignments 16. 3 2 Illustration of two level monotone HMM alignment 17. 3 3 Example of word trigger pairs 19, 3 4 Example of the word joining carried out for the translation direction German. to English The training procedure is carried out subsequently for two dif. ferent translation directions Stage II and Stage III 26. 3 5 German to English alignment examples where a single source word is aligned. to several target language words The source word zum is mapped to the. target words to the The German compound nouns Hauptbahnhof und. Mittwochnachmittag are mapped to the English words main station and. Wednesday afternoon 28, 3 6 Illustration of the possible target word extensions f e for the single word. dependency f e0 The extension shown does not involve additional source. language words 29, 3 7 Example for the selection restriction for target language extensions e aligned. to a single source word f The alignment path of the regular translation di. rection is shown as filled dots The alignment path of the inverse translation. direction is shown as unfilled dots The following extensions are considered. morgens in the morning and Zahnarzttermin dentist s appoint. 3 8 Target language word extension selection for the two German compound. nouns Arbeitskreis work group meeting and Personalsitzung staff. council meeting Here the single German word in the center should be. properly aligned to three English words a part of the surrounding alignment. is shown as well no aligned words are shown for this part 33. iv LIST OF FIGURES, 3 9 Multi word lexicon extension involving both target and source sentence.
words The English phrase of two consecutive words how about is mapped. to the German phrase wie sieht es aus where there is a gap of two words. between the phrase wie sieht es and the German particle aus The gap. may be filled by different German phrases like am Freitag am Donner. stag or etwas spa ter The unfilled circles indicate additional alignment. positions that may be learned as part of a multi word lexicon extension 36. 4 1 Regular alignment example for the translation direction German to English. For each German source word there is exactly one English target word on. the alignment path 43, 4 2 Illustration of the transitions in the inverted alignment model The target. sentence is generated from bottom to top 45, 4 3 Illustration of the algorithm by Held Karp for a traveling salesman problem. with J 5 cities Not all permutations of cities have to be considered For. a given subset of cities the order in which the cities have been visited can be. ignored 47, 4 4 Word re ordering for the translation direction German to English the re. ordering is restricted to the German verb group 49. 4 5 Order in which the German source positions are covered for the German to. English re ordering example given in Figure 4 4 50. 4 6 Word re ordering for the translation direction English to German the re. ordering is restricted to the English verb group 52. 4 7 Order in which the English source positions are covered for the English to. German re ordering example given in Figure 4 6 53, 4 8 Illustration of the IBM style re ordering constraint 56. 4 9 Illustration of the traceback procedure for the beam search strategy 65. 6 1 Illustration of the computation of the upper bound calculation for the partial. hypothesis extension involving the uncovered positions j j and j 108. List of Tables, 3 1 Algorithm for computing a set E of candidate extensions f e A likelihood.
threshold is used to restrict the extensions selected 31. 3 2 Algorithm for computing a modified target language corpus and a corre. sponding list of selected extensions 34, 4 1 DP based search algorithm for the monotone translation model 42. 4 2 DP based algorithm for solving the traveling salesman problem due to Held. and Karp The outer most loop is over the cardinality of subsets of already. visited cities 46, 4 3 DP based algorithm for statistical MT which consecutively processes subsets. C of source sentence positions of increasing cardinality 48. 4 4 Procedural description to compute the set Succ of successor hypotheses by. which to extend a partial hypothesis S C j 55, 4 5 Number or processed arcs for the pseudo translation task as a function of. the input sentence length J y axis is given in log scale The complexity. for the four different re ordering constraints MON GE EG and S3 is given. The complexity of the S3 constraint is close to J 4 57. 4 6 Two list implementation of a DP based search algorithm 63. 4 7 Two list implementation of a DP based search algorithm for statistical MT 64. 4 8 Implementation of dynamic programing core of the DP beam search procedure 67. 4 9 Implementation of dynamic programing program code lines description for. Table 4 8 68, 4 10 Implementation of the dynamic programming the baseline class 69. 4 11 Implementation of dynamic programming struct representing a partial hy. pothesis for the IBM 4 model search 70, 5 1 Best word trigger pairs along with perplexity improvement P P for the.
three selection criteria A B and C self triggers and same root triggers ex. 5 2 List of best triggered words b for some triggering words a for the selection. criteria A B and C 74, 5 3 Perplexity results for the extension of a unigram language model 5 million. training words with three different components low level triggers unigram. triggers and cache 76, 5 4 Perplexity results for the combination of trigger pairs with a trigram cache. language model 1 5 and 39 million training words 77. vi LIST OF TABLES, 5 5 List of best target word joinings sorted by the log likelihood improvement. F f e Fe 0 as obtained on the aligned Verbmobil training corpus using the. word joining algorithm shown in Table 3 2 78, 5 6 List of best target word joinings where the predicted source word f starts. with an upper case letter The extensions are sorted by the log likelihood. improvement F f e Fe 0 as obtained on the aligned Verbmobil training corpus. using algorithm 3 2 The German word Nachmittag is abbreviated nach. in compound nouns 79, 5 7 Number of training iterations for the IBM model training as is described.
in Brown et al 1993 Och et al 2000a The IBM 2 training step of the. original IBM model training is replaced by an hidden Markov model training. 5 8 Complete list of IBM model parameters that are automatically trained on. the training corpora 81, 5 9 Parameters for the search procedure to control the re ordering restrictions 81. 5 10 Complete list of pruning parameters to control the beam width within the. beam search concept 82, 5 11 Training and test conditions on the German English Verbmobil corpus. number of words without punctuation 84, 5 12 Target language vocabulary size word error rate WER and multi reference. word error rate m WER for two cases 1 Without word joining applied. Word Re Ordering and Dynamic Programming based Search Algorithm for Statistical Machine Translation Von der Fakult at fur Mathematik Informatik und Naturwissenschaften der Rheinisch Westf alischen Technischen Hochschule Aachen zur Erlangung des akademischen Grades eines Doktors der Naturwissenschaften genehmigte Dissertation vorgelegt von Diplom Informatiker Christoph Tillmann aus Julic

Related Books