Syntax-Based Grammaticality Improvement using CCG and Guided Search

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 1147–1157, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Syntax-Based Grammaticality Improvement using CCG and Guided Search Yue Zhang University of Cambridge Computer Laboratory yue.zhang@cl.cam.ac.uk Stephen Clark University of Cambridge Computer Laboratory stephen.clark@cl.cam.ac.uk Abstract Machine-produced text often lacks grammat- icality and fluency. This paper studies gram- maticality improvement using a syntax-based algorithm based on CCG. The goal of the search problem is to find an optimal parse tree among all that can be constructed through se- lection and ordering of the input words. The search problem, which is significantly harder than parsing, is solved by guided learning for best-first search. In a standard word order- ing task, our system gives a BLEU score of 40.1, higher than the previous result of 33.7 achieved by a dependency-based system. 1 Introduction Machine-produced text, such as SMT output, often lacks grammaticality and fluency, especially when using n-gram language modelling (Knight, 2007). Recent efforts have been made to improve grammat- icality using local language models (Blackwood et al., 2010) and global dependency structures (Wan et al., 2009). We study grammaticality improvement using a syntax-based system. The task is effectively a text-to-text generation problem where the goal is to produce a grammati- cal sentence from an ungrammatical and fragmen- tary input. The input can range from a bag-of- words (Wan et al., 2009) to a fully-ordered sentence (Blackwood et al., 2010). A general form of the problem is to construct a grammatical sentence from a set of un-ordered input words. However, in cases where the base system produces fluent subsequences within the sentence, constraints on the choice and order of certain words can be fed to the grammati- cality improvement system. The input may also in- clude words beyond the output of the base system, e.g. extra words from the SMT lattice, so that con- tent word insertion and deletion can be performed implicity via word selection. We study the above task using CCG (Steedman, 2000). The main challenge is the search problem, which is to find an optimal parse tree among all that can be constructed with any word choice and order from the set of input words. We use an approximate best-first algorithm, guided by learning, to tackle the more-than-factorial complexity. Beam-search is used to control the volume of accepted hypotheses, so that only a very small portion of the whole search space is explored. The search algorithm is guided by perceptron training, which ensures that the explored path in the search space consists of highly proba- ble hypotheses. This framework of best-first search guided by learning is a general contribution of the paper, which could be applied to problems outside grammaticality improvement. We evaluate our system using the generation task of word-order recovery, which is to recover the orig- inal word order of a fully scrambled input sentence (Bangalore et al., 2000; Wan et al., 2009). This problem is an instance of our general task formu- …

Content truncated to 500 words