Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

As I understand the KL Divergence, it measures how different two probability distributions $P$ and $Q$ are.

However, say the two distributions are:

P = [0.2 0.2 0.2 0.4];
Q = [0 0.5 0.1 0.4];

Then the KL-divergence is infinity. What is the justification for these distributions being infinitely different?

share|improve this question
    
In general $D(P||Q) \neq D(Q||P)$ for the example you have given, $D(P||Q) = \infty$, whereas $D(Q||P)$ is finite. –  svenkatr Feb 9 '11 at 15:44
    
Right. But I suppose D(P||Q) gives a measure of how different P is to Q? So why is that infinite? –  Bill Cheatham Feb 9 '11 at 15:52
    
The same question was asked recently here: math.stackexchange.com/questions/20961/… –  Dinesh Feb 9 '11 at 17:04

1 Answer 1

up vote 3 down vote accepted

One interpretation of the Kullback-Leibler divergence $D_{KL}(P \Vert Q)$ is that it measures the extra message length per character needed to send a message drawn from distribution $P$ using an encoding scheme optimized for distribution $Q$. If one character is assigned a very small probability by $Q$, then the encoding scheme will use a very large number of bits to encode that character, since it is expected to occur so rarely. (By Kraft's inequality, the number of bits should be $-\log_2(q_i)$, where $q_i$ is the probability of the unlikely character.) If in fact it occurs frequently in distribution $P$, then a message drawn from $P$ will take a large number of bits to encode (specifically, $-p_i \log_2(q_i)$ per character on average). Therefore, if the $i$-th component of $Q$ goes to zero while the corresponding component of $P$ remains fixed and positive, the KL divergence $D_{KL}(P \Vert Q)$ should (and does) diverge logarithmically as $-p_i \log_2(q_i)$.

share|improve this answer
    
I see, thanks. So if a character is assigned zero probability by Q, then it will not be assigned a 'symbol' in the encoding table, thus will effectively not be able to be represented when P comes along? –  Bill Cheatham Feb 9 '11 at 16:51
1  
@Bill: That's right... I think strictly the KL divergence is undefined if $q_i=0$ and $p_i>0$, but that's the intuition for what happens as $q_i \rightarrow 0$: the encoding table is "unprepared" to represent the offending character without a large overhead. –  mjqxxxx Feb 9 '11 at 16:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.