A discriminative language model with pseudo-negative samples

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 73–80, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics A Discriminative Language Model with Pseudo-Negative Samples Daisuke Okanohara� Jun’ichi Tsujii��� �Department of Computer Science, University of Tokyo Hongo 7-3-1, Bunkyo-ku, Tokyo, Japan �School of Informatics, University of Manchester �NaCTeM (National Center for Text Mining) �hillbig,tsujii �@is.s.u-tokyo.ac.jp Abstract In this paper, we propose a novel discrim- inative language model, which can be ap- plied quite generally. Compared to the well known N-gram language models, dis- criminative language models can achieve more accurate discrimination because they can employ overlapping features and non- local information. However, discriminative language models have been used only for re-ranking in specific applications because negative examples are not available. We propose sampling pseudo-negative examples taken from probabilistic language models. However, this approach requires prohibitive computational cost if we are dealing with quite a few features and training samples. We tackle the problem by estimating the la- tent information in sentences using a semi- Markov class model, and then extracting features from them. We also use an on- line margin-based algorithm with efficient kernel computation. Experimental results show that pseudo-negative examples can be treated as real negative examples and our model can classify these sentences correctly. 1 Introduction Language models (LMs) are fundamental tools for many applications, such as speech recognition, ma- chine translation and spelling correction. The goal of LMs is to determine whether a sentence is correct or incorrect in terms of grammars and pragmatics. The most widely used LM is a probabilistic lan- guage model (PLM), which assigns a probability to a sentence or a word sequence. In particular, N- grams with maximum likelihood estimation (NLMs) are often used. Although NLMs are simple, they are effective for many applications. However, NLMs cannot determine correctness of a sentence independently because the probabil- ity depends on the length of the sentence and the global frequencies of each word in it. For exam- ple, ��� � � � ��� � �, where ��� � is the probability of a sentence � given by an NLM, does not always mean that � � is more correct, but instead could occur when � � is shorter than � �, or if � � has more com- mon words than � �. Another problem is that NLMs cannot handle overlapping information or non-local information easily, which is important for more ac- curate sentence classification. For example, a NLM could assign a high probability to a sentence even if it does not have a verb. Discriminative language models (DLMs) have been proposed to classify sentences directly as cor- rect or incorrect (Gao et al., 2005; Roark et al., 2007), and these models can handle both non-local and overlapping information. However DLMs in previous studies have been restricted to specific ap- plications. Therefore the model cannot be used for other applications. If we had negative examples available, the models could be trained directly by discriminating between correct and incorrect …

Content truncated to 500 words