Lecture 9 min.
In information theory, perplexity is a measure of how well a probability distribution or probability model predicts a sample. It can be used to compare probability models. A low perplexity indicates that the probability distribution predicts the sample well.
Given two probability models, the better model is the one that fits the test data better, that is, the one that assigns a higher probability to the test data; the better model will assign a higher probability to the test data.
The most common internal criterion is perplexity, used for evaluating language models in computational linguistics. It is a measure of the mismatch, or "surprise," of the model p(w | d) with respect to the tokens w observed in the documents d of the collection D.
It is defined through the log-likelihood (2.18), separately for each modality:
where 
is the length of the collection in the m-th modality.
The smaller the perplexity, the better the model p predicts the occurrence of tokens w in the documents d of the collection D.
Perplexity has the following interpretation. If the terms w are generated from a uniform distribution p(w) = 1/V over a vocabulary of size V, then the perplexity of the model p(w) on such a text converges to V as its length grows. The more the distribution p(w) differs from uniform, the smaller the perplexity. The more the model p(w) differs from the generating distribution, the larger the perplexity. For conditional probabilities p(w | d) the interpretation is slightly different: if each document is generated from V equiprobable terms (possibly different in different documents), then the perplexity converges to V.
Denote by pD(w | d) the model built from the training collection of documents D. The training-sample perplexity 
is an optimistically biased (underestimated) measure of model quality because of the overfitting effect. The generalization ability of topic models is usually evaluated by the hold-out perplexity 
the collection is randomly split into a training and a hold-out sample in a 9 : 1 proportion [17].
The perplexity PP of a discrete probability distribution p is defined as
where H ( p ) is the entropy (in bits) of the distribution, and x ranges over the events. (The base need not be 2: perplexity is independent of the base, provided that the entropy and the exponentiation use one and the same base.) In some fields this measure is also known as the diversity (of true order 1) .
The perplexity of a random variable X may be defined as the perplexity of the distribution of its possible values x .
In the special case where p models a fair k- sided die (a uniform distribution over k discrete events), its perplexity is k . A random variable with perplexity k has the same uncertainty as a fair k -sided die, and one is said to be " k -ways perplexed" about the value of the random variable. (If it is not a fair k- sided die, there will be more than k possible values, but the overall uncertainty is no greater, because some of these values will have a probability greater than 1 / k , decreasing the overall value when summed.)
Perplexity is sometimes used as a measure of how hard a prediction problem is. This is not always accurate. If you have two choices, one with probability 0.9, then your chance of a correct guess is 90 percent using the optimal strategy. The perplexity is 2 −0.9 log 2 0.9 - 0.1 log 2 0.1 = 1.38. The inverse of the perplexity (which, in the case of a fair k-sided die, represents the probability of guessing correctly) is 1 / 1.38 = 0.72, not 0.9.
Perplexity is the exponentiation of the entropy, which is a more fundamental quantity. Entropy is a measure of the expected, or "average," number of bits required to encode the outcome of a random variable, using a theoretical optimal variable-length code, cf. It can also be regarded as the expected information gain from learning the outcome of the random variable.
A model of an unknown probability distribution p may be proposed based on a training sample drawn from p . Given a proposed probability model q , one may evaluate q by asking how well it predicts a separate test sample x 1 , x 2 , ..., x N, also drawn from p . The perplexity of the model q is defined as
where 
is usually 2. Better models q of the unknown distribution p will tend to assign higher probabilities q ( x i ) to the test events. Thus, they have lower perplexity: they are less surprised by the test sample.
The exponent above may be regarded as the average number of bits needed to represent a test event x i, if an optimal code based on q is used. Low-perplexity models compress the test sample better, requiring few bits per test element on average, because q ( x i ) tends to be high.
The exponent may also be regarded as a cross-entropy ,
where 
denotes the empirical distribution of the test sample (i.e.,
if x appeared n times in a test sample of size N ).
In natural language processing, perplexity is a way of evaluating language models . A language model is a probability distribution over entire sentences or texts.
Using the definition of perplexity for a probability model, one might find, for example, that the average sentence x i in the test sample could be coded in 190 bits (i.e., the test sentences had an average log-probability of -190). This would give an enormous model perplexity of 2 190 per sentence. However, it is more common to normalize for sentence length and consider only the number of bits per word. Thus, if the test sample's sentences comprise a total of 1000 words, and could be coded using a total of 7.95 bits per word, one could report a model perplexity of 2 7.95 = 247 per word. In other words, the model is as confused on the test data as if it had to choose uniformly and independently among 247 possibilities for each word.
The lowest perplexity that had been published on the Brown Corpus (1 million words of American English of varying topics and genres) as of 1992 is indeed about 247 per word, corresponding to a cross-entropy of log 2 247 = 7.95 bits per word or 1.75 bits per letter using a trigram model . Lower perplexity can often be achieved on more specialized corpora , as they are more predictable.
Again, simply guessing that the next word in the Brown Corpus is "the" would have an accuracy of 7 percent, not 1/247 = 0.4 percent, as a naive use of perplexity as a measure of predictability might lead one to think. This guess is based on the unigram statistics of the Brown Corpus, not on the trigram statistics, which yielded the word perplexity of 247. Using trigram statistics would further improve the chance of a correct guess.
A drawback of perplexity is that its numerical values are not intuitive, and that it depends not only on the quality of the model but also on a number of extraneous factors: document length, and the size and sparsity of the vocabulary. In particular, it is incorrect to use perplexity to compare topic models of the same collection built on different vocabularies.
A drawback of hold-out perplexity is its high sensitivity to rare and new words, which are practically useless for topic models. Early experiments showed that LDA substantially outperforms PLSA in perplexity, from which it was concluded that LDA overfits less [17]. In [2, 5, 3], robust topic models were proposed that describe rare words with a special "background" distribution. The perplexity of robust variants of PLSA and LDA turned out to be substantially lower and practically identical
Perplexity is a very well-known measure of language model quality in computational linguistics. In linguistics, the quality of a language model is assessed by perplexity, a measure of how well the model predicts the details of a test collection (the lower the perplexity, the better the model). There are several ways to evaluate the quality of topic models; the most common criterion is perplexity, which depends on the vocabulary size and the distribution of word frequencies in the document collection
.
Vorontsov K. V. Additive regularization of topic models of text document collections // Doklady Mathematics. — 2014. — Vol. 456, No. 3. — Pp. 268–271.
Vorontsov K. V., Potapenko A. A. Regularization, robustness and sparsity of probabilistic
topic models // Computer Research and Modeling. — 2012. — Vol. 4, No. 4. —
Pp. 693–706.
Vorontsov K. V., Potapenko A. A. Modifications of the EM algorithm for probabilistic topic modeling // Machine Learning and Data Analysis. — 2013. — Vol. 1, No. 6. — Pp. 657–686.
Vorontsov K. V., Potapenko A. A. Regularization of probabilistic topic models to
improve interpretability and determine the number of topics // Computational Linguistics and Intellectual Technologies: Proceedings of the annual international conference "Dialogue" (Bekasovo, June 4–8, 2014). — Issue 13 (20). — Moscow: RGGU Publishing, 2014. — Pp. 676–687.
Potapenko A. A., Vorontsov K. V. Robust PLSA performs better than LDA // 35th European Conference on Information Retrieval, ECIR-2013, Moscow, Russia, 24-27 March 2013. — Lecture Notes in Computer Science (LNCS), Springer Verlag-Germany, 2013. — Pp. 784–787
Comments