20050421-smoothing-tutorial

NLP Lunch Tutorial: SmoothingBill MacCartney21 April 2005Preface Everything is from this great paper by Stanley F. Chen and JoshuaGoodman (1998), “An Empirical Study of Smoothing Techniquesfor Language Modeling”, which I read yesterday. Everything is presented in the context of n-gram language models,but smoothing is needed in many problem contexts, and most ofthe smo methods we’ll look at generalize without difficulty.1The Plan Motivation– the problem– an example All the smoothing methods– formula after formula– intuitions for each So which one is the best?– (answer: modified Kneser-Ney) Excel “demo” for absolute discounting and Good-Turing?2Probabilistic modeling You have some kind of probabilistic model, which is a distributionp(e) over an event space E. You want to estimate the parameters of your model distribution pfrom data. In principle, you might to like to use maximum likelihood (ML)estimates, so that your model isc(x)p (x)=PMLc(e)eBut...3Problem: data sparsity But, you have insufficient data: there are many events x such thatc(x)=0, so that the ML estimate is p (x)=0.ML In problem settings where the event space E is unbounded (e.g.most NLP problems), this is generally undesirable. Ex: a language model which gives probability 0 to unseen words. Just because an event has never been observed in training data doesnot mean it cannot occur in test data. So if c(x)=0, what should p(x) be? If data sparsity isn’t a ...