# What is perplexity?

I came across term perplexity which refers to the log-averaged inverse probability on unseen data. Wikipedia article on perplexity does not give an intuitive meaning for the same.

This perplexity measure was used in pLSA paper.

Can anyone explain the need and intuitive meaning of perplexity measure?

• How do i calculate perplexity for pLSA. I have datamatrix $X$ which has the count and by TEM algorithm $p(d)$ and $p(w|d)$ are calculated. – Learner May 4 '11 at 11:44
• I've checked the indices of 5 data mining / machine learning / predictive analytics books by Nisbett, Larose, Witten, Torgo, and Shemueli (plus coauthors) and this term doesn't occur in any of them. I'm perplexed :) – zbicyclist May 6 '17 at 2:35
• Perplexity is another fancy name for uncertainty. It can be considered as an intrinsic evaluation against extrinsic evaluation. Jan Jurafsky explains it elegantly with examples in accordance with language modeling here at youtube.com/watch?v=BAN3NB_SNHY – bicepjai Jul 5 '17 at 22:27
• @zbicyclist, If you're looking for examples in the wild, it's particularly common in NLP, and specifically for the evaluation of things like language models. – Matt Krause Dec 18 '17 at 18:03

You have looked at the Wikipedia article on perplexity. It gives the perplexity of a discrete distribution as

$$2^{-\sum_x p(x)\log_2 p(x)}$$

which could also be written as

$$\exp\left({\sum_x p(x)\log_e \frac{1}{p(x)}}\right)$$

i.e. as a weighted geometric average of the inverses of the probabilities. For a continuous distribution, the sum would turn into a integral.

The article also gives a way of estimating perplexity for a model using $N$ pieces of test data

$$2^{-\sum_{i=1}^N \frac{1}{N} \log_2 q(x_i)}$$

which could also be written

$$\exp\left(\frac{{\sum_{i=1}^N \log_e \left(\dfrac{1}{q(x_i)}\right)}}{N}\right) \text{ or } \sqrt[N]{\prod_{i=1}^N \frac{1}{q(x_i)}}$$

or in a variety of other ways, and this should make it even clearer where "log-average inverse probability" comes from.

• Is there any particular distinction between when e is used as the exponent rather than 2? – Henry E May 11 '17 at 12:23
• @HenryE: no, and common logarithms base $10$ would work too - logarithms in different bases are proportional to each other and clearly $a^{\log_a x} = b^{\log_b x}$ – Henry May 11 '17 at 13:32
• I figured as much. I came across this answer when I was trying to understand why a piece of code was using e to calculate perplexity when all the other formulations I'd previously seen had been using 2. I realise now how important it is to know what value a framework uses as a base for the log loss calculation – Henry E May 11 '17 at 15:12

I found this rather intuitive:

The perplexity of whatever you're evaluating, on the data you're evaluating it on, sort of tells you "this thing is right about as often as an x-sided die would be."

http://planspace.org/2013/09/23/perplexity-what-it-is-and-what-yours-is/

I've wondered this too. The first explanation isn't bad, but here are my 2 nats for whatever that's worth.

First of all, perplexity has nothing to do with characterizing how often you guess something right. It has more to do with characterizing the complexity of a stochastic sequence.

We're looking at a quantity, $$2^{-\sum_x p(x)\log_2 p(x)}$$

Let's first cancel out the log and the exponentiation.

$$2^{-\sum_{x} p(x)\log_2 p(x)}=\frac{1}{\prod_{x} p(x)^{p(x)}}$$

I think it's worth pointing out that perplexity is invariant with the base you use to define entropy. So in this sense, perplexity is infinitely more unique/less arbitrary than entropy as a measurement.

# Relationship to Dice

Let's play with this a bit. Let's say you're just looking at a coin. When the coin is fair, entropy is at a maximum, and perplexity is at a maximum of $$\frac{1}{\frac{1}{2}^\frac{1}{2}\times\frac{1}{2}^\frac{1}{2}}=2$$

Now what happens when we look at an $$N$$ sided dice? Perplexity is $$\frac{1}{\left(\frac{1}{N}^\frac{1}{N}\right)^N}=N$$

So perplexity represents the number of sides of a fair die that when rolled, produces a sequence with the same entropy as your given probability distribution.

# Number of States

OK, so now that we have an intuitive definition of perplexity, let's take a quick look at how it is affected by the number of states in a model. Let's start with a probability distribution over $$N$$ states, and create a new probability distribution over $$N+1$$ states such that the likelihood ratio of the original $$N$$ states remain the same and the new state has probability $$\epsilon$$. In the case of starting with a fair $$N$$ sided die, we might imagine creating a new $$N + 1$$ sided die such that the new side gets rolled with probability $$\epsilon$$ and the original $$N$$ sides are rolled with equal likelihood. So in the case of an arbitrary original probability distribution, if the probability of each state $$x$$ is given by $$p_x$$, the new distribution of the original $$N$$ states given the new state will be $$p^\prime_x=p_x\left(1-\epsilon\right)$$, and the new perplexity will be given by:

$$\frac{1}{\epsilon^\epsilon\prod_x^N {p^\prime_x}^{p^\prime_x}}=\frac{1}{\epsilon^\epsilon\prod_x^N {\left(p_x\left(1-\epsilon\right)\right)}^{p_x\left(1-\epsilon\right)}} = \frac{1}{\epsilon^\epsilon\prod_x^N p_x^{p_x\left(1-\epsilon\right)} {\left(1-\epsilon\right)}^{p_x\left(1-\epsilon\right)}} = \frac{1}{\epsilon^\epsilon{\left(1-\epsilon\right)}^{\left(1-\epsilon\right)}\prod_x^N p_x^{p_x\left(1-\epsilon\right)}}$$

In the limit as $$\epsilon\rightarrow 0$$, this quantity approaches $$\frac{1}{\prod_x^N {p_x}^{p_x}}$$

So as you make make rolling one side of the die increasingly unlikely, the perplexity ends up looking as though the side doesn't exist.

• Surely that's only ~1.39 nats worth? – Matt Krause Feb 5 '18 at 22:48
• Can you elaborate how you get $$\prod_x^N {p^\prime_x}^{p^\prime_x} = (1-\epsilon)^{1-\epsilon}\prod_x^N {p_x}^{p_x(1-\epsilon)}$$? I can only do $$\prod_x^N {p^\prime_x}^{p^\prime_x} = \prod_x^N {(p_x (1-\epsilon)) }^{p_x(1-\epsilon)} = \prod_x^N {(1-\epsilon) }^{p_x(1-\epsilon)} \prod_x^N {p_x }^{p_x(1-\epsilon)}$$ – user2740 Oct 20 '18 at 21:19
• $$\prod_x^N\left{(1-\epsilon\right)}^{p_x\left(1-\epsilon\right)}={\left(1-\epsilon\right)}^{\sum_x^N p_x \left(1-\epsilon\right)}={\left(1-\epsilon\right)}^{\left(1-\epsilon\right)\sum_x^N p_x}={\left(1-\epsilon\right)}^{\left(1-\epsilon\right)}$$ – Alex Eftimiades Oct 22 '18 at 0:27

There is actually a clear connection between perplexity and the odds of correctly guessing a value from a distribution, given by Cover's Elements of Information Theory 2ed (2.146): If $X$ and $X'$ are iid variables, then

$P(X=X') >= 2^{-H(X)} = \frac{1}{2^{H(X)}} = \frac{1}{perplexity}$ (1)

To explain, perplexity of a uniform distribution X is just |X|, the number of elements. If we try to guess the values that iid samples from a uniform distribution X will take by simply making iid guesses from X, we will be correct 1/|X|=1/perplexity of the time. Since the uniform distribution is the hardest to guess values from, we can use 1/perplexity as a lower bound / heuristic approximation for how often our guesses will be right.