An efficient clustering algorithm for class-based language models

An Efficient Clustering Algorithm for Class-based Language Models Takuya Matsuzaki� Yusuke Miyao� �Department of Computer Science, University of Tokyo Hongo 7-3-1, Bunkyo-ku, Tokyo 113-0033 JAPAN �CREST, JST (Japan Science and Technology Corporation) Honcho 4-1-8, Kawaguchi-shi, Saitama 332-0012 JAPAN �matuzaki,yusuke,tsujii �@is.s.u-tokyo.ac.jp Jun’ichi Tsujii�� Abstract This paper defines a general form for class- based probabilistic language models and pro- poses an efficient algorithm for clustering based on this. Our evaluation experiments re- vealed that our method decreased computation time drastically, while retaining accuracy. 1 Introduction Clustering algorithms have been extensively studied in the research area of natural language processing because many researchers have proved that “classes” obtained by clustering can improve the performance of various NLP tasks. Examples have been class-based �-gram models (Brown et al., 1992; Kneser and Ney, 1993), smooth- ing techniques for structural disambiguation (Li and Abe, 1998) and word sense disambiguation (Sh¨utze, 1998). In this paper, we define a general form for class-based probabilistic language models, and propose an efficient and model-theoretic algorithm for clustering based on this. The algorithm involves three operations, CLAS- SIFY, MERGE, and SPLIT, all of which decreases the optimization function based on the MDL principle (Ris- sanen, 1984), and can efficiently find a point near the lo- cal optimum. The algorithm is applicable to more general tasks than existing studies (Li and Abe, 1998; Berkhin and Becher, 2002), and computational costs are signifi- cantly small, which allows its application to very large corpora. Clustering algorithms may be classified into three types. The first is a type that uses various heuristic mea- sure of similarity between the elements to be clustered and has no interpretation as a probability model (Widdow, 2002). The resulting clusters from this type of method are not guaranteed to work effectively as a component of a statistical language model, because the similarity used in clustering is not derived from the criterion in the learning process of the statistical model, e.g. likelihood. The second type has clear interpretation as a probability model, but no criteria to determine the number of clusters (Brown et al., 1992; Kneser and Ney, 1993). The perfor- mance of methods of this type depend on the number of clusters that must be specified before the clustering pro- cess. It may prove rather troublesome to determine the proper number of clusters in this type of method. The third has interpretation as a probability model and uses some statistically motivated model selection criteria to determine the proper number of clusters. This type has a clear advantage compared to the second. AutoClass (Cheeseman and Stutz, 1996), the Bayesian model merg- ing method (Stolcke and Omohundro, 1996) and Li’s method (Li, 2002) are examples of this type. AutoClass and the Bayesian model merging are based on soft clus- tering models and Li’s method is based on a hard clus- tering model. In general, computational costs for hard clustering models are lower than that for soft clustering models. However, the time complexity of Li’s method is of cubic order in the size …

Content truncated to 500 words