Dependency Language Models for Sentence Completion

Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1405–1410, Seattle, Washington, USA, 18-21 October 2013. c⃝2013 Association for Computational Linguistics Dependency language models for sentence completion Joseph Gubbins Computer Laboratory University of Cambridge jsg52@cam.ac.uk Andreas Vlachos Computer Laboratory University of Cambridge av308@cam.ac.uk Abstract Sentence completion is a challenging seman- tic modeling task in which models must choose the most appropriate word from a given set to complete a sentence. Although a variety of language models have been ap- plied to this task in previous work, none of the existing approaches incorporate syntactic in- formation. In this paper we propose to tackle this task using a pair of simple language mod- els in which the probability of a sentence is estimated as the probability of the lexicalisa- tion of a given syntactic dependency tree. We apply our approach to the Microsoft Research Sentence Completion Challenge and show that it improves on n-gram language models by 8.7 percentage points, achieving the highest accu- racy reported to date apart from neural lan- guage models that are more complex and ex- pensive to train. 1 Introduction The verbal reasoning sections of standardised tests such as the Scholastic Aptitude Test (SAT) fea- ture problems where a partially complete sentence is given and the candidate must choose the word or phrase from a list of options which completes the sentence in a logically consistent way. Sen- tence completion is a challenging semantic mod- elling problem. Systematic approaches for solving such problems require models that can judge the global coherence of sentences. Such measures of global coherence may prove to be useful in various applications, including machine translation and nat- ural language generation (Zweig and Burges, 2012). Most approaches to sentence completion employ language models which use a window of immedi- ate context around the missing word and choose the word that results in the completed sentence with the highest probability (Zweig and Burges, 2012; Mnih and Teh, 2012). However, such language models may fail to identify sentences that are locally co- herent but are improbable due to long-range syntac- tic/semantic dependencies. Consider, for example, completing the sentence I saw a tiger which was really very ... with either fierce or talkative. A language model relying on up to five words of immediate context would ignore the crucial dependency between the missing word and the noun tiger. In this paper we tackle sentence completion us- ing language models based on dependency gram- mar. These models are similar to standard n-gram language models, but instead of using the linear or- dering of the words in the sentence, they generate words along paths in the dependency tree of the sen- tence. Unlike other approaches incorporating syntax into language models (e.g., Chelba et al., 1997), our models are relatively easy to train and estimate, and can exploit standard smoothing methods. We apply them to the Microsoft Research Sentence Comple- tion Challenge (Zweig and Burges, 2012) and show an improvement of 8.7 points in accuracy over …

Content truncated to 500 words