CSCI 5832 Natural Language Processing Jim Martin Lecture 26 01 15 19 1 Today 4 29 More MT 2 01 15 19 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 P e x P s e 01 15 19 3 Three Sub Problems of Statistical MT Language model Given an English string e assigns P e by formula good English string high P e random word sequence low P e Translation model Given a pair of strings f e assigns P f e by formula f e look like translations high P f e f e don t look like translations low P f e Decoding algorithm Given a language model a translation model and a new sentence f find translation e maximizing P e P f e 4 01 15 19 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 01 15 19 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 6 01 15 19 Word Alignment la maison la maison bleue la fleur the house the blue house the flower Inherent hidden structure revealed by EM training 7 01 15 19 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 for each of these sentence pairs 8 01 15 19 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 9 01 15 19 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 la blue m house m blue b house b blue la flower f flower 10 01 15 19 Reminder P la the is P la aligned with the P the Which is Count la aligned with the Count the in a word aligned corpus Which we don t have 11 01 15 19 EM Step 1 Make up some numbers for the parameters of interest In this case just the translation probs la the 1 4 m the 1 4 b the 1 4 f the 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 la flower 1 2 f flower 1 2 12 01 15 19 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 la maison bleue the blue house 1 3 1 3 1 36 13 01 15 19 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 1 12 2 12 1 2 1 6 For each 14 01 15 19 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 15 01 15 19 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 16 01 15 19 EM Step 3 Evidence for la the la maison la maison bleue la fleur the house the blue house the flower 1 2 1 17 01 15 19 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 18 01 15 19 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 19 01 15 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 la the 8 6 18 6 m the 5 6 18 6 b the 2 6 18 6 f the 3 6 18 6 la the 44 m the 27 b the 11 f the 16 20 01 15 19 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 21 01 15 19 EM Alignment Ok I know this seems weird 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 22 01 15 19 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 possibilities 23 01 15 19 Break I will try to cover a subset of the material in Chapter 23 next week 24 01 15 19 Intuition of phrase based translation Koehn et al 2003 Generative story has three steps 1 Group words into phrases 2 Translate each phrase 3 Move the phrases around 25 01 15 19 Generative story again 1 Group English source words into phrases e1 e2 en 2 Translate each English phrase ei into a Spanish …
View Full Document
Unlocking...