Results 1 to 4 of 4

Math Help - Calculations give me a negative relative entropy

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    31

    Post Calculations give me a negative relative entropy

    The Kullback-Leibler Divergence, also known as Relative Entropy in Information Theory, measures the "distance" between two distributions. Usually, one of the distributions is the theoretical, and the other is the empirical. Now, based on Gibbs' Inequality, relative entropy is nonnegative; it is zero only when the two distributions are similar. Below is the general formula for discrete distributions:

    D(P\|Q) = \sum_i P(i) \log \frac{P(i)}{Q(i)}. \!

    So, we take the logarithm of p relative to q and multiply it by p, summing over all the values.

    My problem is the following. I have two empirical distributions, each having 8 values:

    P(i)
    =====
    0.0152
    0.1108
    0.0297
    0.0405
    0.0757
    0.0054
    0.6405
    0.0541

    and

    Q(i)
    =====
    0.0000
    0.0375
    0.0500
    0.0625
    0.0625
    0.0000
    0.7875
    0.0000

    Now, when I calculate the relative entropy D(P||Q), I get a negative value equal to -0.0444. This violates Gibbs' Inequality. Could you think of any possible reason why?

    It seems to me that, the terms with indexes 3, 4, 7 yield negative logarithms (to base 2) in the summation, and the result is negative. What am I doing wrong here?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by EmpSci View Post
    The Kullback-Leibler Divergence, also known as Relative Entropy in Information Theory, measures the "distance" between two distributions. Usually, one of the distributions is the theoretical, and the other is the empirical. Now, based on Gibbs' Inequality, relative entropy is nonnegative; it is zero only when the two distributions are similar. Below is the general formula for discrete distributions:

    D(P\|Q) = \sum_i P(i) \log \frac{P(i)}{Q(i)}. \!

    So, we take the logarithm of p relative to q and multiply it by p, summing over all the values.

    My problem is the following. I have two empirical distributions, each having 8 values:

    P(i)
    =====
    0.0152
    0.1108
    0.0297
    0.0405
    0.0757
    0.0054
    0.6405
    0.0541

    and

    Q(i)
    =====
    0.0000
    0.0375
    0.0500
    0.0625
    0.0625
    0.0000
    0.7875
    0.0000

    Now, when I calculate the relative entropy D(P||Q), I get a negative value equal to -0.0444. This violates Gibbs' Inequality. Could you think of any possible reason why?

    It seems to me that, the terms with indexes 3, 4, 7 yield negative logarithms (to base 2) in the summation, and the result is negative. What am I doing wrong here?
    I don't know anything about K-L divergence, but your P's do not sum to 1. Could that be it?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2009
    Posts
    31
    Thanks for the input, awkward. I fixed the problem for P, now the new values are as follows:

    P
    =====
    0.0432
    0.1108
    0.0297
    0.0405
    0.0757
    0.0054
    0.6405
    0.0541

    and

    Q
    =====
    0.0000
    0.0375
    0.0500
    0.0625
    0.0625
    0.0000
    0.7875
    0.0000

    Apparently, in the overall summation, three logarithms are negative, and their sum is larger than the sum of the rest, so the relative entropy results in a negative value, which violates Gibbs' Inequality.

    If I find out what the problem is, I'll post the solution here, unless somebody may have some other input on what the problem is.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Mar 2009
    Posts
    31
    OK, I fixed the problem, which was computational anyways.

    As per the K-L Divergence definition, if a q_{i} is 0, then the result of the logarithmic term is infinity, and so is supposed to be the sum (i.e. the relative entropy. Therefore, the result should be infinity wherever the computation gives a negative (for whatever reason), while I assumed (after my third glass of black label JD) that the term would be zero.

    In the two distributions I gave above, I set the 0 values to 0.1 x 10^-10 for my own purposes. That gave me positive values.

    So, in general, the definition of K-L Divergence is the following:

    <br /> <br />
D(P\|Q) = \sum_i P(i) \log \frac{P(i)}{Q(i)}. \!<br />

    where  0 \log 0 = 0, for P(i)=0 and P(i) \log \frac{P(i)}{0} = inf, the latter implying that the pseudo-distance between the two distributions is practically huge.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: October 28th 2010, 08:40 AM
  2. Replies: 0
    Last Post: August 3rd 2010, 07:02 PM
  3. Replies: 2
    Last Post: April 7th 2009, 08:12 AM
  4. Entropy
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 6th 2008, 10:48 AM
  5. Entropy
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: December 27th 2007, 04:58 AM

Search Tags


/mathhelpforum @mathhelpforum