Paper: Efficient Extraction of Oracle-best Translations from Hypergraphs

ACL ID N09-2003
Title Efficient Extraction of Oracle-best Translations from Hypergraphs
Venue Human Language Technologies
Session Short Paper
Year 2009
Authors

Hypergraphs are used in several syntax- inspired methods of machine translation to compactly encode exponentially many trans- lation hypotheses. The hypotheses closest to given reference translations therefore cannot be found via brute force, particularly for pop- ular measures of closeness such as BLEU. We develop a dynamic program for extracting the so called oracle-best hypothesis from a hyper- graph by viewing it as the problem of finding the most likely hypothesis under an n-gram language model trained from only the refer- ence translations. We further identify and re- move massive redundancies in the dynamic program state due to the sparsity of n-grams present in the reference translations, resulting in a very efficient program. We present run- time statistics for this program, and d...