Clustering Words with the MDL Principle

Clustering Words with the MDL Principle Hang Li and Naoki Abe Theory NEC Laboratory, RWCP* c/o C&C Research Labora.tories, NEC 4-1-1 Miya~zaki Miyamae-ku, Ke~wasa.ki, 216 Japan {lihang,abe} (@sbl.cl.nee.co.jp Abstract We address the probhml of automaticMly constructing a thesaurus by clustering words based on corpus data. We view this problem as that of estimating a joint distribution over the (:artesian product of a partition of a set of nouns and a partition of a set of verbs, and propose a learning a.lgorithm based on the Min- inmm Description Length (MDL) Prin- ciple for such estimation. We empiri- cally compared the performance of our method based on the MDL Principle against the Maximum Likelihood Esti- mator in word clustering, and found that the former outperforms the latter. ~¢Ve also evaluated the method by conduct- ing pp-attachment disambiguation ex- periments using an automaticMly con- structed thesaurus. Our experimental results indicate that such a thesaurus can be used to improve accuracy in disam- biguation. 1 Introduction Recently various methods for automatically con- structing a thesaurus (hierarchically clustering words) based on corpus data. have been proposed (Hindle, 1990; Brown et al., 1992; Pereira et al., 1993; Tokunaga et al., 1995). The realization of such an automatic construction method would make it possible to a) save the cost of constructing a thesaurus by hand, b) do away with subjectivity inherent in a hand made thesaurus, and c) make it easier to adapt a natural language processing system to a new domain. In this paper, we pro- pose a new method for automatic construction of thesauri. Specifically, we view the problem of au- tomatically clustering words as that of estimating a joint distributiofl over the Cartesian product of a partition of a set of nouns (in general, any set of words) and a partition of a set of w:rbs (in gen- eral, any set of words), and propose an est.imation *Real World Computing Partership algorithm using simulated annealing with an en- ergy function based on the blinimum Description Length (MDL) Principle. The MDL Principle is a well-motivated and theoretically sound principle for data compression and estimation in informa- tion theory and statistics. As a method of sta- tisticM estimation MDL is guaranteed to be near optimal. We empiricMly evMuated the effectiveness of our method. In particular, we compared the per- formance of an MDL-based sinm]ated anuealilag Mgorithm in hierarchical word clustering against. that of one based on the Maximum Likelihood Estimator (MLE, for short). We found that the MDL-based method performs better than the MLE-based method. We also evaluated our method by conducting pp-attachment disam- biguation experiments using a thesaurus automat- ically constructed by it and found that disam- biguation results can be improved. Since some words never occur in a corpus, and thus cannot be reliably classified by a method solely based on corpus data, we propose to com- bine the use of an automatically constructed the- saurus and a hand made thesaurus in disambigua- tion. We conducted some experiments in order to test the effectiveness …

Content truncated to 500 words