Phrase-based Model - Revision history

Tamchyna at 13:29, 29 April 2015

2015-04-29T13:29:51Z

← Older revision		Revision as of 13:29, 29 April 2015
Line 1:		Line 1:
	{{Infobox		{{Infobox
	\|title = Lecture 8: Phrase-based model		\|title = Lecture 9: Phrase-based model
	\|image = [[File:computer-copies.png\|200px]]		\|image = [[File:computer-copies.png\|200px]]
	\|label1 = Lecture video:		\|label1 = Lecture video:

Tamchyna at 07:26, 9 April 2015

2015-04-09T07:26:08Z

← Older revision		Revision as of 07:26, 9 April 2015
Line 85:		Line 85:
	There is one more caveat -- not all input words (or spans -- phrases) are created equal. Some are difficult to translate and some only have one or a few possible translations. To account for this discrepancy, phrase-based decoders estimate the '''future cost''' of translating the remainder of the input sentence. This estimation is based on the score of the most probable translation of the remaining spans and can be efficiently pre-computed using dynamic programming. Without accounting for future cost, hypotheses which translate the easiest words first would dominate the stacks and the search would lead to heavily suboptimal solutions.		There is one more caveat -- not all input words (or spans -- phrases) are created equal. Some are difficult to translate and some only have one or a few possible translations. To account for this discrepancy, phrase-based decoders estimate the '''future cost''' of translating the remainder of the input sentence. This estimation is based on the score of the most probable translation of the remaining spans and can be efficiently pre-computed using dynamic programming. Without accounting for future cost, hypotheses which translate the easiest words first would dominate the stacks and the search would lead to heavily suboptimal solutions.

	== A Real Example ==		=== A Real Example ===

	The following search graphs were exported from Moses when translating the sentence:		The following search graphs were exported from Moses when translating the sentence:

Tamchyna at 07:25, 9 April 2015

2015-04-09T07:25:20Z

← Older revision		Revision as of 07:25, 9 April 2015
Line 97:		Line 97:
	: ''the meeting of the House of the upper law . fell''		: ''the meeting of the House of the upper law . fell''

	[[File:merged-0001.png\|800px]] [[File:merged-0030.png\|800px]] [[File:merged-0050.png\|800px]]		[[File:merged-0001.png\|800px]]

			This is not a good translation and systems with higher stack limits do not even consider it. Because they can keep more than one-best candidate on each stack, they are able to find better-scoring combinations of translation options and this partial translation is pruned away before covering the whole input sentence. See the search graphs for stack limit 30 and 50 for comparison:

			[[File:merged-0030.png\|800px]] [[File:merged-0050.png\|800px]]

	== See Also ==		== See Also ==

Tamchyna at 07:22, 9 April 2015

2015-04-09T07:22:16Z

← Older revision		Revision as of 07:22, 9 April 2015
Line 86:		Line 86:

	== A Real Example ==		== A Real Example ==

			The following search graphs were exported from Moses when translating the sentence:

			: ''Ze schůze sněmovny vypadl horní zákon.'' (The mining law was dropped from the meeting of the House.)

			The graphs differ in stack limits (1, 30, 50) -- the maximum number of partial hypotheses on each stack. For clarity, we show the union of all translations considered by any of the systems in dotted lines. Full lines represent the translations considered by that particular system.

			For example, the first system (stack limit 1) proposes just a single translation:

			: ''the meeting of the House of the upper law . fell''

	[[File:merged-0001.png\|800px]] [[File:merged-0030.png\|800px]] [[File:merged-0050.png\|800px]]		[[File:merged-0001.png\|800px]] [[File:merged-0030.png\|800px]] [[File:merged-0050.png\|800px]]

Tamchyna at 07:15, 9 April 2015

2015-04-09T07:15:19Z

← Older revision		Revision as of 07:15, 9 April 2015
Line 87:		Line 87:
	== A Real Example ==		== A Real Example ==

	[[File:merged-0001.png]] [[File:merged-0030.png]] [[File:merged-0050.png]]		[[File:merged-0001.png\|800px]] [[File:merged-0030.png\|800px]] [[File:merged-0050.png\|800px]]

	== See Also ==		== See Also ==

Tamchyna at 07:12, 9 April 2015

2015-04-09T07:12:45Z

← Older revision		Revision as of 07:12, 9 April 2015
Line 84:		Line 84:

	There is one more caveat -- not all input words (or spans -- phrases) are created equal. Some are difficult to translate and some only have one or a few possible translations. To account for this discrepancy, phrase-based decoders estimate the '''future cost''' of translating the remainder of the input sentence. This estimation is based on the score of the most probable translation of the remaining spans and can be efficiently pre-computed using dynamic programming. Without accounting for future cost, hypotheses which translate the easiest words first would dominate the stacks and the search would lead to heavily suboptimal solutions.		There is one more caveat -- not all input words (or spans -- phrases) are created equal. Some are difficult to translate and some only have one or a few possible translations. To account for this discrepancy, phrase-based decoders estimate the '''future cost''' of translating the remainder of the input sentence. This estimation is based on the score of the most probable translation of the remaining spans and can be efficiently pre-computed using dynamic programming. Without accounting for future cost, hypotheses which translate the easiest words first would dominate the stacks and the search would lead to heavily suboptimal solutions.

			== A Real Example ==

			[[File:merged-0001.png]] [[File:merged-0030.png]] [[File:merged-0050.png]]

	== See Also ==		== See Also ==

Tamchyna at 21:25, 7 April 2015

2015-04-07T21:25:19Z

← Older revision		Revision as of 21:25, 7 April 2015
Line 75:		Line 75:
	It is obvious that with realistic sentence lengths and translation dictionaries, the search space very quickly explodes and it becomes impossible to go through all the possible combinations of span translations and their orderings.		It is obvious that with realistic sentence lengths and translation dictionaries, the search space very quickly explodes and it becomes impossible to go through all the possible combinations of span translations and their orderings.

	First, we need to impose a limit on reordering (how far we can jump in the input), otherwise the search would be intractable. In practice, the limit is set to roughly 6 words.		First, we need to impose a limit on reordering (how far we can jump in the input), otherwise the search would be hopelessly intractable. In practice, the limit is set to roughly 6 words.

	Furthermore, we need to prune our partial hypotheses as there are still too many combinations. Our model assigns a score to each of them (more on that in later lectures) so we can sort our translations according to it and only keep several most promising candidates.		Furthermore, we need to prune our partial hypotheses as there are still too many combinations. Our model assigns a score to each of them (more on that in later lectures) so we can sort our translations according to it and only keep several most promising candidates.
Line 83:		Line 83:
	The algorithm can then proceed from stack "0" (which contains the empty hypothesis) to the final stack where full hypotheses compete for the best score. Each stack has a limited size which keeps the search tractable.		The algorithm can then proceed from stack "0" (which contains the empty hypothesis) to the final stack where full hypotheses compete for the best score. Each stack has a limited size which keeps the search tractable.

	There is one more caveat -- not all input words (or spans -- phrases) are created equal. Some are difficult to translate and some only have one or a few possible translations. To account for this discrepancy, phrase-based decoders estimate the '''future cost''' of translating the remainder of the input sentence. This estimation is on the score of the most probable translation of the remaining spans and can be efficiently pre-computed using dynamic programming. Without accounting for future cost, hypotheses which translate the easiest words first would dominate the stacks and the search would lead to heavily suboptimal solutions.		There is one more caveat -- not all input words (or spans -- phrases) are created equal. Some are difficult to translate and some only have one or a few possible translations. To account for this discrepancy, phrase-based decoders estimate the '''future cost''' of translating the remainder of the input sentence. This estimation is based on the score of the most probable translation of the remaining spans and can be efficiently pre-computed using dynamic programming. Without accounting for future cost, hypotheses which translate the easiest words first would dominate the stacks and the search would lead to heavily suboptimal solutions.

	== See Also ==		== See Also ==

Bojar: /* Phrase Scoring */ drobnost

2015-04-07T21:24:14Z

Phrase Scoring: drobnost

← Older revision		Revision as of 21:24, 7 April 2015
Line 38:		Line 38:
	The formula tells us to simply count how many times we saw <math>f</math> translated as <math>e</math> in our training data and divide that by the number of times we saw <math>f</math> in total.		The formula tells us to simply count how many times we saw <math>f</math> translated as <math>e</math> in our training data and divide that by the number of times we saw <math>f</math> in total.

	In practice, other scores are also computed (~~e.g.~~ <math>P(f\|e)</math>) but that's a topic for another lecture.		In practice, several other scores are also computed (including the reverse phrase translation probability <math>P(f\|e)</math>) but that's a topic for another lecture.

	== Decoding ==		== Decoding ==

Tamchyna at 21:24, 7 April 2015

2015-04-07T21:24:10Z

← Older revision		Revision as of 21:24, 7 April 2015
Line 67:		Line 67:
	This is an excerpt of the space where the decoder searches for the best translation. One (the most reasonable) full translation is illustrated but the decoder theoretically needs to evaluate all possible combinations.		This is an excerpt of the space where the decoder searches for the best translation. One (the most reasonable) full translation is illustrated but the decoder theoretically needs to evaluate all possible combinations.

	[[File:beam-search.png\|~~300px~~]]		[[File:beam-search.png\|350px]]

			Note that we keep track of covered input spans in a Boolean array (1 for covered words, 0 for untranslated ones) -- we know that we have a full translation once the '''coverage vector''' has no more zeroes.

	=== Stacks, Pruning ===		=== Stacks, Pruning ===

	It is obvious that with realistic sentence lengths and translation dictionaries, the search space very quickly explodes and it becomes impossible to go through all possible combinations of span translations and their orderings.		It is obvious that with realistic sentence lengths and translation dictionaries, the search space very quickly explodes and it becomes impossible to go through all the possible combinations of span translations and their orderings.

			First, we need to impose a limit on reordering (how far we can jump in the input), otherwise the search would be intractable. In practice, the limit is set to roughly 6 words.

			Furthermore, we need to prune our partial hypotheses as there are still too many combinations. Our model assigns a score to each of them (more on that in later lectures) so we can sort our translations according to it and only keep several most promising candidates.

			However, it would be unfair to compare a score of a full translation with a partial hypothesis that e.g. only had to translate one phrase. The full hypothesis contains more decisions => more uncertainty => almost surely, the full translation has a lower score. For this reason, partial hypotheses are organized into '''stacks''' according to the number of covered input words. For each number, we have a separate stack. That way, only hypotheses which cover the same "amount" of input are compared.

			The algorithm can then proceed from stack "0" (which contains the empty hypothesis) to the final stack where full hypotheses compete for the best score. Each stack has a limited size which keeps the search tractable.

			There is one more caveat -- not all input words (or spans -- phrases) are created equal. Some are difficult to translate and some only have one or a few possible translations. To account for this discrepancy, phrase-based decoders estimate the '''future cost''' of translating the remainder of the input sentence. This estimation is on the score of the most probable translation of the remaining spans and can be efficiently pre-computed using dynamic programming. Without accounting for future cost, hypotheses which translate the easiest words first would dominate the stacks and the search would lead to heavily suboptimal solutions.

	== See Also ==		== See Also ==

Tamchyna at 21:02, 7 April 2015

2015-04-07T21:02:48Z

← Older revision		Revision as of 21:02, 7 April 2015
Line 67:		Line 67:
	This is an excerpt of the space where the decoder searches for the best translation. One (the most reasonable) full translation is illustrated but the decoder theoretically needs to evaluate all possible combinations.		This is an excerpt of the space where the decoder searches for the best translation. One (the most reasonable) full translation is illustrated but the decoder theoretically needs to evaluate all possible combinations.

	[[File:beam-search.png\|~~600px~~]]		[[File:beam-search.png\|300px]]

	=== Stacks, Pruning ===		=== Stacks, Pruning ===