Syntax-Based Word Ordering Incorporating a Large-Scale Language Model

Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 736–746, Avignon, France, April 23 - 27 2012. c⃝2012 Association for Computational Linguistics Syntax-Based Word Ordering Incorporating a Large-Scale Language Model Yue Zhang University of Cambridge Computer Laboratory yz360@cam.ac.uk Graeme Blackwood University of Cambridge Engineering Department gwb24@eng.cam.ac.uk Stephen Clark University of Cambridge Computer Laboratory sc609@cam.ac.uk Abstract A fundamental problem in text generation is word ordering. Word ordering is a com- putationally difficult problem, which can be constrained to some extent for particu- lar applications, for example by using syn- chronous grammars for statistical machine translation. There have been some recent attempts at the unconstrained problem of generating a sentence from a multi-set of input words (Wan et al., 2009; Zhang and Clark, 2011). By using CCG and learn- ing guided search, Zhang and Clark re- ported the highest scores on this task. One limitation of their system is the absence of an N-gram language model, which has been used by text generation systems to improve fluency. We take the Zhang and Clark system as the baseline, and incor- porate an N-gram model by applying on- line large-margin training. Our system sig- nificantly improved on the baseline by 3.7 BLEU points. 1 Introduction One fundamental problem in text generation is word ordering, which can be abstractly formu- lated as finding a grammatical order for a multi- set of words. The word ordering problem can also include word choice, where only a subset of the input words are used to produce the output. Word ordering is a difficult problem. Finding the best permutation for a set of words accord- ing to a bigram language model, for example, is NP-hard, which can be proved by linear reduction from the traveling salesman problem. In prac- tice, exploring the whole search space of permu- tations is often prevented by adding constraints. In phrase-based machine translation (Koehn et al., 2003; Koehn et al., 2007), a distortion limit is used to constrain the position of output phrases. In syntax-based machine translation systems such as Wu (1997) and Chiang (2007), synchronous grammars limit the search space so that poly- nomial time inference is feasible. In fluency improvement (Blackwood et al., 2010), parts of translation hypotheses identified as having high local confidence are held fixed, so that word or- dering elsewhere is strictly local. Some recent work attempts to address the fun- damental word ordering task directly, using syn- tactic models and heuristic search. Wan et al. (2009) uses a dependency grammar to solve word ordering, and Zhang and Clark (2011) uses CCG (Steedman, 2000) for word ordering and word choice. The use of syntax models makes their search problems harder than word permutation us- ing an N-gram language model only. Both meth- ods apply heuristic search. Zhang and Clark de- veloped a bottom-up best-first algorithm to build output syntax trees from input words, where search is guided by learning for both efficiency and accuracy. The framework is flexible in allow- ing a …

Content truncated to 500 words