Performance Prediction for Exponential Language Models

Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the ACL, pages 450–458, Boulder, Colorado, June 2009. c⃝2009 Association for Computational Linguistics Performance Prediction for Exponential Language Models Stanley F. Chen IBM T.J. Watson Research Center P.O. Box 218, Yorktown Heights, NY 10598 stanchen@watson.ibm.com Abstract We investigate the task of performance pre- diction for language models belonging to the exponential family. First, we attempt to em- pirically discover a formula for predicting test set cross-entropy for n-gram language mod- els. We build models over varying domains, data set sizes, and n-gram orders, and perform linear regression to see whether we can model test set performance as a simple function of training set performance and various model statistics. Remarkably, we find a simple rela- tionship that predicts test set performance with a correlation of 0.9997. We analyze why this relationship holds and show that it holds for other exponential language models as well, in- cluding class-based models and minimum dis- crimination information models. Finally, we discuss how this relationship can be applied to improve language model performance. 1 Introduction In this paper, we investigate the following question for language models belonging to the exponential family: given some training data and test data drawn from the same distribution, can we accurately pre- dict the test set performance of a model estimated from the training data? This problem is known as performance prediction and is relevant for model se- lection, the task of selecting the best model from a set of candidate models given data.1 Let us first define some notation. Events have the form (x, y), where we attempt to predict the cur- rent word y given previous words x. We denote the training data as D = (x1, y1), . . . , (xD, yD) and de- fine ˜p(x, y) = countD(x, y)/D to be the empirical distribution of the training data. Similarly, we have 1A long version of this paper can be found at (Chen, 2008). a test set D∗ and an associated empirical distribu- tion p∗(x, y). We take the performance of a condi- tional language model p(y|x) to be the cross-entropy H(p∗, p) between the empirical test distribution p∗ and the model p(y|x): H(p∗, p) = − � x,y p∗(x, y) log p(y|x) (1) This is equivalent to the negative mean log- likelihood per event, as well as to log perplexity. We only consider models in the exponential fam- ily. An exponential model pΛ(y|x) is a model with a set of features {f1(x, y), . . . , fF (x, y)} and equal number of parameters Λ = {λ1, . . . , λF } where pΛ(y|x) = exp(�F i=1 λifi(x, y)) ZΛ(x) (2) and where ZΛ(x) is a normalization factor. One of the seminal methods for performance pre- diction is the Akaike Information Criterion (AIC) (Akaike, 1973). For a model, let ˆΛ be the maxi- mum likelihood estimate of Λ on some training data. Akaike derived the following estimate for the ex- pected …

Content truncated to 500 words