How to ensure the non-negativity of Kullback-Leibler Divergence KLD Metric (Relative Entropy)? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T13:38:01Z http://mathoverflow.net/feeds/question/43849 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/43849/how-to-ensure-the-non-negativity-of-kullback-leibler-divergence-kld-metric-relat How to ensure the non-negativity of Kullback-Leibler Divergence KLD Metric (Relative Entropy)? Mike 2010-10-27T18:48:00Z 2010-10-27T19:07:24Z <p>Hello,</p> <p>I’m having some problems in ensuring the non-negativity of <strong>KLD</strong>! </p> <p>I know that <strong>KLD</strong> is always positive and I went over the proof. However, it doesn’t seem to work for me. In some cases I’m getting negative results. Here is how I’m using <strong>KLD</strong>:</p> <p>KLD( P(x) || Q(x) ) = Sum[ (P(x) . Log[P(x)/Q(x)] ]; Log is base 2. P(x) and Q(x) are two different distributions for all x belongs to X.</p> <p>For example, P(x) = (Frequency(x)/Total_Size); just normal PMF! The same thing for Q(x). Note that the Total_Size for P might be different from Q distribution.</p> <p>Could you please let me know if I’m missing something? Are there any special conditions that I have to take into consideration to avoid having negative results?</p> <p>Thanks in advance.</p> http://mathoverflow.net/questions/43849/how-to-ensure-the-non-negativity-of-kullback-leibler-divergence-kld-metric-relat/43851#43851 Answer by ohai for How to ensure the non-negativity of Kullback-Leibler Divergence KLD Metric (Relative Entropy)? ohai 2010-10-27T19:00:21Z 2010-10-27T19:00:21Z <p>"The K-L divergence is only defined if P and Q both sum to 1 and if Q(i) > 0 for any i such that P(i) > 0."</p> <p>I suspect that the second condition is your problem. Say that you have x which appears in P but not Q -- in this case you're probably adding zero contribution to the sum in your code so that you don't have to divide by zero or take the logarithm of zero, but this is effectively throwing out mass from P and you get a negative number for the divergence.</p> <p><a href="http://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence" rel="nofollow">http://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence</a></p> http://mathoverflow.net/questions/43849/how-to-ensure-the-non-negativity-of-kullback-leibler-divergence-kld-metric-relat/43852#43852 Answer by S. Sra for How to ensure the non-negativity of Kullback-Leibler Divergence KLD Metric (Relative Entropy)? S. Sra 2010-10-27T19:02:22Z 2010-10-27T19:07:24Z <p>Here is a simple proof, which also shows non-negativity for several other related functions.</p> <p>Let $\varphi : \mathbb{R}^n \to \mathbb{R}$ be a <em>strictly convex</em> and continuously differentiable function. Then we can use $\varphi$ to "generate" a divergence function $D$ defined as follows: $$D(x,y) = \phi(x) - \phi(y) - \langle \nabla\varphi(y), x - y\rangle$$</p> <p>The above divergence function is known as a <em>Bregman divergence</em>.</p> <p>The fact that $D(x,y) \ge 0$ (equalling $0$, iff $x=y$) is an immediate consequence of the strict convexity of $\varphi$.</p> <p>Now, if you choose $\varphi(x) = \sum_i x_i \log x_i$, you obtain the KL-Divergence (upto normalization) --- Note here that usually one takes $0\log 0 = 0$ (by continuity), and that the arguments to KL should satisfy the conditions mentioned by Ohai.</p>