Exploring Asymmetric Clustering for Statistical Language Modeling

Exploring Asymmetric Clustering for Statistical Language Modeling Jianfeng Gao Microsoft Research, Asia Beijing, 100080, P.R.C jfgao@microsoft.com Joshua T. Goodman Microsoft Research, Redmond Washington 98052, USA joshuago@microsoft.com Guihong Cao1 Department of Computer Science and Engineering of Tianjin University, China Hang Li Microsoft Research, Asia Beijing, 100080, P.R.C hangli@microsoft.com 1 This work was done while Cao was visiting Microsoft Research Asia. Abstract The n-gram model is a stochastic model, which predicts the next word (predicted word) given the previous words (conditional words) in a word sequence. The cluster n-gram model is a variant of the n-gram model in which similar words are classified in the same cluster. It has been demonstrated that using different clusters for predicted and conditional words leads to cluster models that are superior to classical cluster models which use the same clusters for both words. This is the basis of the asymmetric cluster model (ACM) discussed in our study. In this paper, we first present a formal definition of the ACM. We then describe in detail the methodology of constructing the ACM. The effectiveness of the ACM is evaluated on a realistic application, namely Japanese Kana-Kanji conversion. Experimental results show substantial improvements of the ACM in comparison with classical cluster models and word n-gram models at the same model size. Our analysis shows that the high-performance of the ACM lies in the asymmetry of the model. 1 Introduction The n-gram model has been widely applied in many applications such as speech recognition, machine translation, and Asian language text input [Jelinek, 1990; Brown et al., 1990; Gao et al., 2002]. It is a stochastic model, which predicts the next word (predicted word) given the previous n-1 words (conditional words) in a word sequence. The cluster n-gram model is a variant of the word n-gram model in which similar words are classified in the same cluster. This has been demonstrated as an effective way to deal with the data sparseness problem and to reduce the memory sizes for realistic applications. Recent research [Yamamoto et al., 2001] shows that using different clusters for predicted and conditional words can lead to cluster models that are superior to classical cluster models, which use the same clusters for both words [Brown et al., 1992]. This is the basis of the asymmetric cluster model (ACM), which will be formally defined and empirically studied in this paper. Although similar models have been used in previous studies [Goodman and Gao, 2000; Yamamoto et al., 2001], several issues have not been completely investigated. These include: (1) an effective methodology for constructing the ACM, (2) a thorough comparative study of the ACM with classical cluster models and word models when they are applied to a realistic application, and (3) an analysis of the reason why the ACM is superior. The goal of this study is to address the above three issues. We first present a formal definition of the ACM; then we describe in detail the methodology of constructing the ACM including (1) an asymmetric clustering algorithm in which …

Content truncated to 500 words