Using Perfect Sampling in Parameter Estimation of a Whole Sentence Maximum Entropy Language Model

In: Proceedings of CoNLL-2000 and LLL-2000, pages 79-82, Lisbon, Portugal, 2000. Using Perfect Sampling in Parameter Estimation of a Whole Sentence Maximum Entropy Language Model* F. Amaya t and J. M. Benedf Departamento de Sistemas Inform£ticos y Computacidn Universidad Polit6cnica de Valencia Camino de vera s/n, 46022-Valencia (Spain) {famaya, jbenedi}@dsic.upv.es Abstract The Maximum Entropy principle (ME) is an ap- propriate framework for combining information of a diverse nature from several sources into the same language model. In order to incorporate long-distance information into the ME frame- work in a language model, a Whole Sentence Maximum Entropy Language Model (WSME) could be used. Until now MonteCarlo Markov Chains (MCMC) sampling techniques has been used to estimate the paramenters of the WSME model. In this paper, we propose the applica- tion of another sampling technique: the Perfect Sampling (PS). The experiment has shown a re- duction of 30% in the perplexity of the WSME model over the trigram model and a reduc- tion of 2% over the WSME model trained with MCMC. 1 Introduction The language modeling problem may be defined as the problem of calculating the probability of a string, p(w) = p(wl,..., Wn). The probability p(w) is usually calculated via conditional prob- abilities. The n-gram model is one of the most widely used language models. The power of the n-gram model resides in its simple formulation and the ease of training. On the other hand, n- grams only take into account local information, and important long-distance information con- tained in the string wl ... wn cannot be modeled by it. In an attempt to supplement the local in- formation with long-distance information, hy- brid models have been proposed such us (Belle- * This work has been partially supported by the Spanish CYCIT under contract (TIC98/0423-C06). t Granted by Universidad del Cauca, Popay~n (Colom- bia) garda, 1998; Chelba, 1998; Benedl and Sanchez, 2000). The Maximum Entropy principle is an ap- propriate framework for combining information of a diverse nature from several sources into the same model: the Maximum Entropy model (ME) (Rosenfeld, 1996). The information is in- corporated as features which are submitted to constraints. The conditional form of the ME model is: 1 (1) p(ulx) = z(x) where Ai are the parameters to be learned (one for each feature), the fi are usually characteris- tic functions which are associated to the fea- tures and Z(x) = ~y exp{~i~l Aifi(x,y)} is the normalization constant. The main advan- tages of ME are its flexibility (local and global information can be included in the model) and its simplicity. The drawbacks are that the para- menter's estimation is computationally expen- sive, specially the evaluation of the normaliza- tion constant Z(x) andthat the grammatical information contained in the sentence is poorly encoded in the conditional framework. This is due to the assumption of independence in the conditional events: in the events in the state space, only a part of the information contained in the sentence influences de calculation of the probability (Ristad, 1998). 2 Whole …

Content truncated to 500 words