CSCI 5832 Natural Language Processing Lecture 26 Jim Martin 5 1 07 CSCI 5832 Spring 2007 1 Today 4 26 Review Machine translation framework Word based models Worked out EM alignment example Phrase based translation Syntax based 5 1 07 CSCI 5832 Spring 2007 2 1 Sample from Today s Al Jazeera 5 1 07 CSCI 5832 Spring 2007 3 MT Pyramid interlingua semantics semantics syntax syntax phrases phrases words words 5 1 07 SOURCE CSCI 5832 Spring 2007 TARGET 4 2 Bayes Rule Noisy Channel Garbled English Spanish Translation Model P s e Que hambre tengo yo English Language Model P e Decoding algorithm argmax P e P s e e I am so hungry Given a source sentence s the decoder should consider many possible translations and return the target string e that maximizes P e s By Bayes Rule we can also write this as P e x P s e P s and maximize that instead P s never changes while we compare different e s so we can equivalently maximize this 5 1 07 CSCI 5832 Spring 2007 5 P e x P s e Parts List We need probabilities for n x y The probability that word y will yield x outputs in the translation fertility p The probability of a null insertion t The actual word translation probability table d j i the probability that a word at position i will make an appearance at position j in the translation 5 1 07 CSCI 5832 Spring 2007 6 3 Parts List Every one of these can be learned from a sentence aligned corpus Ie A corpus where sentences are paired but nothing else is specified And the EM algorithm 5 1 07 CSCI 5832 Spring 2007 7 Word Alignment la maison la maison bleue la fleur the house the blue house the flower Inherent hidden structure revealed by EM training 5 1 07 CSCI 5832 Spring 2007 8 4 EM Worked out example Focus only on the word translation probs la maison la maison bleue la fleur the house the blue house the flower How many alignments are there 5 1 07 CSCI 5832 Spring 2007 9 EM Worked out Knight example Focus only on the word translation probs la maison la maison bleue la fleur the house the blue house the flower 2 6 2 How many alignments are there 5 1 07 CSCI 5832 Spring 2007 10 5 EM Step 1 Make up some numbers for the parameters of interest In this case just the word translation probabilities la the m the b the f the la house m house b house 5 1 07 la blue m blue b blue la flower f flower CSCI 5832 Spring 2007 11 EM Step 1 Make up some numbers for the parameters of interest In this case just the translation probs word translation probs la the m the b the f the 5 1 07 1 4 1 4 1 4 1 4 la house 1 3 m house 1 3 b house 1 3 la blue 1 3 m blue 1 3 b blue 1 3 CSCI 5832 Spring 2007 la flower 1 2 f flower 1 2 12 6 EM Step 2 Make some simple assumptions and produce some normalized alignment probabilities la maison la maison the house the house 1 3 1 12 1 3 1 12 5 1 07 la maison bleue the blue house 1 3 1 3 1 36 CSCI 5832 Spring 2007 13 EM Step 2 normalize Make some simple assumptions and produce some normalized alignment probabilities la maison la maison la maison bleue the house the house the blue house 1 3 1 12 1 3 1 3 1 36 1 3 1 12 1 12 2 12 1 2 5 1 07 1 12 2 12 1 2 CSCI 5832 Spring 2007 1 6 For each 14 7 EM Step 3 Now that we have the probability of each alignment we can go back and count the evidence in the alignments for each translation pair and prorate them based on the alignments they come from 5 1 07 CSCI 5832 Spring 2007 15 EM Step 3 Now that we have the probability of each alignment we can go back and count the evidence in the alignments for each translation pair and prorate them based on the alignments they come from Huh Let s just look at la the What evidence do we have 5 1 07 CSCI 5832 Spring 2007 16 8 EM Step 3 Evidence for la the la maison la maison bleue la fleur the house the blue house the flower 2 1 5 1 07 1 CSCI 5832 Spring 2007 17 EM Step 3 Evidence for la the la maison la maison bleue la fleur the house the blue house the flower 1 1 5 1 07 2 2 1 6 CSCI 5832 Spring 2007 1 1 18 9 EM Step 3 Evidence for la the la maison la maison bleue la fleur the house the blue house the flower 1 1 2 2 1 6 1 1 8 6 Discounted count for la the 5 1 07 CSCI 5832 Spring 2007 19 EM Step 3 Do that for the other the and normalize la the 8 6 m the 5 6 b the 2 6 f the 3 6 5 1 07 la the 8 6 18 6 m the 5 6 18 6 b the 2 6 18 6 f the 3 6 18 6 CSCI 5832 Spring 2007 la the 44 m the 27 b the 11 f the 16 20 10 EM Step 4 Do that for all the words in the table Recompute the alignment probabilities using the new word translation probabilities Recompute the fractional counts Normalize to get new word translation probs Iterate until done When you re done you can use the numbers to get the most probable alignment From which you can read off all the parameters you need 5 1 07 CSCI 5832 Spring 2007 21 EM Alignment This is totally weird voodoo science We need some parameters which we don t have We can get them from a word aligned corpus which we don t have So we make up some parameters to get the alignment and then use that alignment to get the right numbers 5 1 07 CSCI 5832 Spring 2007 22 11 Parts List Given a sentence alignment we can induce a word alignment Given that word alignment we can get the p t d and n parameters we need for the model Ie We can argmax P e f by max over P f e P e and we can do that by iterating over some large space of f possibilities 5 1 07 CSCI 5832 Spring 2007 23 Break Quiz Coverage Semantics Compositional and IE Chapter 16 Pages 1 29 Chapter 19 Sections 19 1 19 4 Review Bioinformatics Slides Discourse Chapter 21 MT Pages 1 31 skip 20 6 2 Chapter 24 Pages 1 41 skip 24 2 5 1 07 CSCI 5832 Spring 2007 24 12 Decoding Remember Viterbi Just a fancier Viterbi Given …
View Full Document
Unlocking...