24
$\begingroup$

Why do some definitions of the Kullback-Leibler divergence include extra terms $-p_i + q_i$? For example, kl_div() (in the Python scipy.special module) defines the Kullback-Leibler divergence as $$ \sum_i p_i \ln\frac{p_i}{q_i} - p_i + q_i. $$

The documentation says:

The origin of this function is in convex programming; see [1] for details. This is why the function contains the extra terms over what might be expected from the Kullback-Leibler divergence.

I don't have the referenced book at hand. What is the justification or motivation for the additional $-p_i + q_i$ terms?

Anti-closing note: This is not a question about software, but about the concept behind it.

$\endgroup$
5
  • $\begingroup$ @Firebug I'm unsure whether I understand what you mean. The software is obviously meant to work on discrete distributions. A different function, rel_entr() (relative entropy), linked from the above one, relies on the common definition of the KL-divergence for discrete distributions. I'd like to know how and why the additional terms appear. $\endgroup$
    – Igor F.
    Commented Apr 14, 2023 at 11:39
  • 1
    $\begingroup$ The function does not integrate anything, ergo, it does not compute the Kullback-Leibler Divergence. $\endgroup$
    – Firebug
    Commented Apr 14, 2023 at 11:41
  • 1
    $\begingroup$ @JohnMadden I believe you are talking about the OP question, while I'm talking about scipy $\endgroup$
    – Firebug
    Commented Apr 14, 2023 at 13:45
  • 3
    $\begingroup$ @Firebug Oh, I see what you mean, yes that's confusing that they define an "elementwise" KL divergence. $\endgroup$ Commented Apr 14, 2023 at 14:36
  • 3
    $\begingroup$ I have edited the question so the plea not to be closed goes at the end and a very brief summary of the question (in particular, what the extra terms are) goes at the very start - this is to try and make the question appear more meaningful in search engine snippet results for future readers. (I've also phrased it to make clear that scipy isn't the only place you'll see this definition, eg the cited reference uses it too, so this Q will be useful to non-scipy users as well.) Feel free to revert my changes or make further ones if you think it will be useful! $\endgroup$
    – Silverfish
    Commented Apr 14, 2023 at 18:39

2 Answers 2

28
$\begingroup$

The other answer tells us why we don't usually see the $-p_i+q_i$ term: $p$ and $q$ are usually residents of the simplex and so sum to one, so this leads to $\sum - [p_i - q_i] = \sum - p_i + \sum q_i = -1 + 1 = 0$.

In this answer, I want to show why those terms are there in the first place, by viewing KL divergence as the Bregman divergence induced by the (negative) Entropy function.

Given some differentiable function $\psi$, the Bregman divergence induced by it is a binary function on the domain of $\psi$:

$$ B_\psi(p,q) = \psi(p)-\psi(q)-\langle\nabla\psi(q),p-q\rangle $$

Intuitively, the Bregman divergence measures the difference between $\psi$ evaluated at $p$ and the linear approximation to $\psi$ (about $q$) evaluated at $p$. When $\psi$ is convex, this is guaranteed to be nonnegative, and thus so is the Bregman divergence.

Noting that if $\psi(p) = \sum_i p_i \log p_i$, $\nabla\psi(p) = [\log p_i + 1]$, the entropic Bregman divergence is thus:

$$ B_e(p,q) = \sum_i p_i \log p_i - \sum_i q_i \log q_i - \sum_i [\log q_i + 1][p_i-q_i]\\ = \sum_i p_i \log p_i - \sum_i q_i \log q_i - \sum_i [\log q_i (p_i-q_i) + p_i-q_i]\\ = \sum_i p_i \log p_i - \sum_i q_i \log q_i - \sum_i p_i \log q_i + \sum_i q_i\log q_i - \sum_i[p_i-q_i]\\ = \sum_i p_i \log p_i - \sum_i p_i \log q_i - \sum_i[p_i-q_i]\\ = \sum_i p_i \log \frac{p_i}{q_i} + \sum_i[-p_i+q_i] $$

which we recognize as the KL divergence you mentioned.

$\endgroup$
0
22
$\begingroup$

The referenced book has a free pdf on Boyd's site: https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

On page 90, formula 3.17 gives this definition. I suspect the reason for the added terms is that in convex optimization, the two vectors needn't be probability distributions; the authors say

Note that the relative entropy and the Kullback-Leibler divergence are the same when $u$ and $v$ are probability vectors

When they are, in the sum the extra terms cancel. But when they aren't, the added terms ensure that the total is nonnegative.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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