Collocation Map for Overcoming Data Sparseness

Collocation Map for Overcoming Data Sparseness Moonjoo Kim, Young S. Han, and Key-Sun Choi Department of Computer Science Korea Advanced Institute of Science and Technology Taejon, 305-701, Korea mj0712~eve.kaist.ac.kr, yshan~csking.kaist.ac.kr, kschoi~csking.kai~t.ac.k~ Abstract Statistical language models are useful because they can provide probabilis- tic information upon uncertain decision making. The most common statistic is n-grams measuring word cooccurrences in texts. The method suffers from data shortage problem, however. In this pa- per, we suggest Bayesian networks be used in approximating the statistics of insufficient occurrences and of those that do not occur in the sample texts with graceful degradation. Collocation map is a sigmoid belief network that can be constructed from bigrams. We compared the conditional probabilities and mutual information computed from bigrams and Collocation map. The results show that the variance of the values from Colloca- tion map is smaller than that from fre- quency measure for the infrequent pairs by 48%. The predictive power of Col- location map for arbitrary associations not observed from sample texts is also demonstrated. 1 Introduction In statistical language processing, n-grams are bar sic to many probabilistic models including Hidden Markov models that work on the limited depen- dency of linguistic events. In this regard, Bayesian models (Bayesian network, Belief network, Infer- ence diagram to name a few) are not very different from ItMMs. Bayesian models capture the con- ditional independence among probabilistic vari- ables, and can compute the conditional distribu- tion of the variables, which is known as a prob- abilistic inferencing. The pure n-gram statistic, however, is somewhat crude in that it cannot do anything about unobserved events and its approx- imation on infrequent events can be unreliable. In this paper we show by way of extensive ex- periments that the Bayesian method that also can be composed from bigrams can overcome the data sparseness problem that is inherent in frequency counting methods. According to the empirical re- sults, Collocation map that is a Bayesian model for lexical variables induced graceful approxima- tion over unobserved and infrequent events. There are two known methods to deal with the data sparseness problem. They are smoothing and class based methods (Dagan 1992). Smoothing methods (Church and Gale 1991) readjust the dis- tribution of frequencies of word occurrences ob- tained from sample texts, and verify the distri- bution through held-out texts. As Dagan (1992) pointed out, however, the values from the smooth- ing methods closely agree with the probability of a bigram consisting of two independent words. Class based methods (Pereira et al. 1993) approximate the likelihood of unobserved words based on similar words. Dagan and et al. (1992) proposed a non-hierarchical class based method. The two approaches report limited successes of purely experimental nature. This is so because they are based on strong assumptions. In the case of smoothing methods, frequency readjustment is somewhat arbitrary and will not be good for heav- ily dependent bigrams. As to the class based methods, the notion of similar words differs across different methods, and the association of proba- …

Content truncated to 500 words