2
$\begingroup$

I am wondering that how one can calculate KL-divergence on two probability distributions. For example, if we have

t1 = 0.4, 0.2, 0.3, 0.05, 0.05
t2 = 0.23, 0, 0.14, 0.17

The formula is bit complicated for me :(

$\endgroup$
  • $\begingroup$ t2 does not add up to one and is thus no valid probability. If you don't fix that, you will get weird results. $\endgroup$ – bayerj Mar 26 '11 at 12:51
  • $\begingroup$ @bayer: I had read these as equally probable values in my answer below. I now see they might be probabilities: before the question was changed, they did add up to 1. That would make a difference. $\endgroup$ – Henry Mar 28 '11 at 7:17
3
$\begingroup$

Using brute force and the first formula here based on the first formula for the Kullback-Leibler divergence, you are starting from two multisets each with 5 values, 3 of which are shared between them. So the combination of them is the multiset $$M={0, 0.05, 0.05, 0.1, 0.2, 0.2, 0.3, 0.3, 0.4, 0.4}$$

so using $D_{\mathrm{KL}}(P\|Q) = \sum_i P(i) \log \frac{P(i)}{Q(i)}$

$$JSD(t_1 \parallel t_2)= \frac{1}{2}D_{\mathrm{KL}}(t_1 \parallel M)+\frac{1}{2}D_{\mathrm{KL}}(t_2 \parallel M)$$ $$=\frac{1}{2}\left(1\cdot\frac{2}{5} \log\left(\frac{2/5}{2/10}\right) +3\cdot\frac{1}{5} \log\left(\frac{1/5}{2/10}\right)\right) $$ $$+\frac{1}{2}\left(2\cdot\frac{1}{5} \log\left(\frac{1/5}{1/10}\right) +3\cdot\frac{1}{5} \log\left(\frac{1/5}{2/10}\right)\right) $$ $$= \dfrac{2}{5}\log(2) \approx 0.277$$

though you may want to check this. Other calculations, such as using Shannon entropy should produce the same result.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the detailed answer. Is it the standard formula for JS? and why did you mention 3 are same between two distributions? Is it important? Do I need to calculate this as well when I perform JS? How did you get 2/5? 1/5? $\endgroup$ – user3900 Mar 26 '11 at 1:39
  • $\begingroup$ OP wanted to find $D_{\mathrm{KL}}$, right? Why do you find JSD? Sorry if I'm mistaken. $\endgroup$ – Ashok Mar 26 '11 at 5:44
  • 1
    $\begingroup$ @Ashok: I asked the question as it was at the time. It has since changed. $\endgroup$ – Henry Mar 26 '11 at 7:17
  • $\begingroup$ Thanks for the explanation but I really don't understand how you obtained M. The wiki page for JSD says $M=0.5*(P+Q)$? $\endgroup$ – Legend Jan 16 '13 at 22:22
  • $\begingroup$ @Legend The original question was for $t1 = 0.4, 0.2, 0.3, 0.05, 0.05$ and $t2 = 0.3, 0, 0.4, 0.1, 0.2$ so $M$ was simply the two them combined as a multiset. $\endgroup$ – Henry Jan 16 '13 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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