Word Ordering with Phrase-Based Grammars

Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics, pages 259–268, Gothenburg, Sweden, April 26-30 2014. c⃝2014 Association for Computational Linguistics Word Ordering with Phrase-Based Grammars Adri`a de Gispert, Marcus Tomalin, William Byrne Department of Engineering, University of Cambridge, UK ad465@cam.ac.uk, mt126@cam.ac.uk, wjb31@cam.ac.uk Abstract We describe an approach to word ordering using modelling techniques from statisti- cal machine translation. The system in- corporates a phrase-based model of string generation that aims to take unordered bags of words and produce fluent, gram- matical sentences. We describe the gen- eration grammars and introduce parsing procedures that address the computational complexity of generation under permuta- tion of phrases. Against the best previous results reported on this task, obtained us- ing syntax driven models, we report huge quality improvements, with BLEU score gains of 20+ which we confirm with hu- man fluency judgements. Our system in- corporates dependency language models, large n-gram language models, and mini- mum Bayes risk decoding. 1 Introduction Word ordering is a fundamental problem in NLP and has been shown to be NP-complete in dis- course ordering (Althaus et al., 2004) and in SMT with arbitrary word reordering (Knight, 1999). Typical solutions involve constraints on the space of permutations, as in multi-document summari- sation (Barzilay and Elhadad, 2011) and preorder- ing in SMT (Tromble and Eisner, 2009; Genzel, 2010). Some recent work attempts to address the fun- damental word ordering task directly, using syn- tactic models and heuristic search. Wan et al. (2009) use a dependency grammar to address word ordering, while Zhang and Clark (2011; 2012) use CCG and large-scale n-gram language models. These techniques are applied to the unconstrained problem of generating a sentence from a multi-set of input words. We describe GYRO (Get Your Order Right), a phrase-based approach to word ordering. Given a bag of words, the system first scans a large, trusted text collection and extracts phrases consisting of words from the bag. Strings are then generated by concatenating these phrases in any order, sub- ject to the constraint that every string is a valid reordering of the words in the bag, and the re- sults are scored under an n-gram language model (LM). The motivation is that it is easier to make fluent sentences from phrases (snippets of fluent text) than from words in isolation. GYRO builds on approaches developed for syn- tactic SMT (Chiang, 2007; de Gispert et al., 2010; Iglesias et al., 2011). The system generates strings in the form of weighted automata which can be rescored using higher-order n-gram LMs, depen- dency LMs (Shen et al., 2010), and Minimum Bayes Risk decoding, either using posterior prob- abilities obtained from GYRO or SMT systems. We report extensive experiments using BLEU and conclude with human assessments. We show that despite its relatively simple formulation, GYRO gives BLEU scores over 20 points higher than the best previously reported results, gener- ated by a syntax-based ordering system. Human fluency assessments confirm these substantial im- provements. 2 Phrase-based Word Ordering …

Content truncated to 500 words