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?
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.
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.
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.
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.
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') \ge 2^{-H(X)} = \frac{1}{2^{H(X)}} = \frac{1}{\text{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.
