Predicting Sentences using N-Gram Language Models

Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 193–200, Vancouver, October 2005. c⃝2005 Association for Computational Linguistics Predicting Sentences using N-Gram Language Models Steffen Bickel, Peter Haider, and Tobias Scheffer Humboldt-Universit¨at zu Berlin Department of Computer Science Unter den Linden 6, 10099 Berlin, Germany {bickel, haider, scheffer}@informatik.hu-berlin.de Abstract We explore the benefit that users in sev- eral application areas can experience from a “tab-complete” editing assistance func- tion. We develop an evaluation metric and adapt N-gram language models to the problem of predicting the subsequent words, given an initial text fragment. Us- ing an instance-based method as base- line, we empirically study the predictabil- ity of call-center emails, personal emails, weather reports, and cooking recipes. 1 Introduction Prediction of user behavior is a basis for the con- struction of assistance systems; it has therefore been investigated in diverse application areas. Previous studies have shed light on the predictability of the next unix command that a user will enter (Motoda and Yoshida, 1997; Davison and Hirsch, 1998), the next keystrokes on a small input device such as a PDA (Darragh and Witten, 1992), and of the trans- lation that a human translator will choose for a given foreign sentence (Nepveu et al., 2004). We address the problem of predicting the subse- quent words, given an initial fragment of text. This problem is motivated by the perspective of assis- tance systems for repetitive tasks such as answer- ing emails in call centers or letters in an adminis- trative environment. Both instance-based learning and N-gram models can conjecture completions of sentences. The use of N-gram models requires the application of the Viterbi principle to this particular decoding problem. Quantifying the benefit of editing assistance to a user is challenging because it depends not only on an observed distribution over documents, but also on the reading and writing speed, personal prefer- ence, and training status of the user. We develop an evaluation metric and protocol that is practical, intuitive, and independent of the user-specific trade- off between keystroke savings and time lost due to distractions. We experiment on corpora of service- center emails, personal emails of an Enron execu- tive, weather reports, and cooking recipes. The rest of this paper is organized as follows. We review related work in Section 2. In Section 3, we discuss the problem setting and derive appropri- ate performance metrics. We develop the N-gram- based completion method in Section 4. In Section 5, we discuss empirical results. Section 6 concludes. 2 Related Work Shannon (1951) analyzed the predictability of se- quences of letters. He found that written English has a high degree of redundancy. Based on this find- ing, it is natural to ask whether users can be sup- ported in the process of writing text by systems that predict the intended next keystrokes, words, or sen- tences. Darragh and Witten (1992) have developed an interactive keyboard that uses the sequence of past keystrokes to predict the most likely succeed- …

Content truncated to 500 words