4
$\begingroup$

Is it possible to compute the Jensen-Shannon divergence between a discrete and a continuous probability distribution, e.g. between a standard normal distribution and a distribution taking the values 1,2,3 each with probability 1/3? Or are there any other divergences which can be used as a similarity measure of discrete and continuous distributions.

$\endgroup$
6
  • $\begingroup$ related question: stats.stackexchange.com/questions/69125/… $\endgroup$
    – Pat
    Sep 4, 2013 at 11:11
  • 1
    $\begingroup$ I have to ask why you'd want to measure the divergence a continuous and discrete distribution. It doesn't feel like a very natural thing to do at all. If you give us some more details as to what you're wanting to apply it to, people may be able to steer you towards a solution. $\endgroup$
    – Pat
    Sep 4, 2013 at 11:12
  • $\begingroup$ @Pat: This is not uncommon in dynamic state estimation, e.g. the Unscented Kalman Filter (UKF) approximates (using Moment Matching) a d-dimensional Normal distribution by a discrete probability distribution (consisting of 2*d+1 components) with same mean and covariance. Sometimes, the quality can be improved by approximating the original distribution with a more complex discrete distribution. I am interested in a good distance Measure which can be used to perform this kind of optimization. $\endgroup$
    – Igor
    Sep 4, 2013 at 11:36
  • $\begingroup$ Okay. I'm not familiar with the UKF. From what I can read online you take a set of points with the same mean and covariance as your normal distribution, pass them through the system's non-linear transform, and use the transformed points to re-estimate the normal distribution in the new space by moment matching? In that case wouldn't it be best to measure the divergence of the re-estimated normal from the 'ideal' normal (probably what you would get if you used an infinite number of sigma points)? Then you're comparing two continuous distributions to one another, and avoid the problem entirely. $\endgroup$
    – Pat
    Sep 4, 2013 at 12:03
  • $\begingroup$ Yes, this would be the best strategy. Unfortunately, this approach is often computationally burdensome (this obviously depends on the system function), which motivates the use of approximations of continuous probability distributions by discrete distributions. $\endgroup$
    – Igor
    Sep 4, 2013 at 12:51

1 Answer 1

4
$\begingroup$

I'm going to answer a more general question, generalizing your question as well as my answer here about KL:$\DeclareMathOperator{\supp}{supp}\newcommand{\R}{\mathbb R}$

Suppose that $P$ and $Q$ are probability measures such that $P(\supp Q) = 0$. Consider an $f$-divergence $D_f(P \| Q)$; what values can it take?

If $P$ is continuous (in the usual sense: absolutely continuous w.r.t. Lebesgue measure on a domain $\mathcal X$) and $Q$ is discrete (with support $\supp Q \subset \mathcal X$ at most countable), then $P(\supp Q) = 0$. Also, the Jensen-Shannon is an $f$-divergence.

The usual definition of an $f$-divergence is something like $$ D_f(P \| Q) = \int_{\mathcal X} q(x) f\left( \frac{p(x)}{q(x)} \right) \mathrm dx ,$$ but this definition has (at least) two problems for our purposes: it assumes both $p$ and $q$ have (standard) density functions, and it's not clear what to do if there are $x$ where $q(x) = 0$, or (for many choices of $f$, which diverge at $0$) where $p(x) = 0$.

To address these problems: let $\mu$ be any reference measure such that $P$ and $Q$ are each absolutely continuous w.r.t. $\mu$, i.e. for any measurable set $A \subset \mathcal X$ with $\mu(A) = 0$, we have $P(A) = 0 = Q(A)$. Let the Radon-Nikodym derivatives of $P$ and $Q$ with respect to $\mu$ be $p$ and $q$. Then we can define the $f$-divergence as (see Definition 7.1 of Polyanskiy and Wu, Information Theory) $$D_f(P \| Q) = \int_{\supp Q} q(x) f\left( \frac{p(x)}{q(x)} \right) \mathrm d\mu + f'(\infty) P(\mathcal X \setminus \supp Q).$$ The $f'(\infty)$ term handles situations when $q(x) = 0$ but $p(x) > 0$: in those cases the integrand becomes $0 \times f(\infty)$, and this term acounts for that with integration by parts. What's a derivative at infinity? It's defined here as $\lim_{t \searrow 0} t f(1/t)$; we'll evaluate this for specific $f$ divergences in a moment.

Now, since $P(\supp Q) = 0$ and $P(\mathcal X) = 1$, we must have $P(\mathcal X \setminus \supp Q) = 1$.

This leaves the integral; to evaluate this we'll need to choose a measure $\mu$, but luckily this definition is invariant to the choice of $\mu$ (see e.g. Remark 7.2 of Polyanskiy and Wu). We'll choose a $\mu$ below such that for any point $x \in \supp Q$, $q(x) > 0$ but $p(x) = 0$. That leaves the integral as $$\int_{\supp Q} q(x) f(0) \,\mathrm d \mu = f(0) \, Q(\supp Q) = f(0),$$ so that $$D_f(P \| Q) = f(0) + f'(\infty).$$

Thus, as long as $P(\supp Q) = 0$, the value of $D_f(P \| Q)$ is simply a constant depending only on $f$ – it doesn't matter what the particular distributions are.

It's also worth noting that for any $f$, we have $D_f(P \| Q) = D_{g}(Q \| P)$ for $g(t) = t f(1/t)$, and that we have $g(0) = f'(\infty)$, $g'(\infty) = f(0)$; thus if $P(\supp Q) = 0$, $D_f(P \| Q) = D_f(Q \| P)$.


For the Jensen-Shannon, $f(t) = - (t+1) \log \frac{t+1}{2} + t \log t$: \begin{align*} f(0) &= \lim_{t \searrow 0} - (t+1) \log \frac{t+1}{2} + t \log t \\&= - \log \frac12 + \lim_{t \searrow 0} t \log t = \log 2 \\ f'(\infty) &= \lim_{t \searrow 0} t f(1/t) = \lim_{t \searrow 0} - t \left( \frac1t + 1 \right) \log \frac{\frac1t + 1}{2} + t \frac1t \log \frac1t \\&= \lim_{t \searrow 0} - (t+1) \log \frac{t + 1}{2t} + \log \frac1t \\&= \lim_{t \searrow 0} - \underbrace{t \log (t+1)}_{\to 0} + \underbrace{t \log 2}_{\to 0} + \underbrace{t \log t}_{\to 0} - \underbrace{\log(t+1)}_{\to 0} + \log 2 + \underbrace{\log t - \log t}_0 \\&= \log 2 ,\end{align*} so that under these assumptions $$ \operatorname{JS}(P, Q) = 2 \log 2 .$$


For the KL divergence, \begin{align*} f(t) &= t \log t \\ f(0) &= \lim_{t \searrow 0} t \log t = 0 \\ f'(\infty) &= \lim_{t \searrow 0} t \frac1t \log \frac1t = \infty .\end{align*}

So both $\operatorname{KL}(P \| Q)$ and $\operatorname{KL}(Q \| P)$ are infinite if $P(\supp Q) = 0$.


Just out of interest, the total variation distance has \begin{align*} f(t) &= \frac12 \lvert t - 1 \rvert \\ f(0) &= \frac12 \\ f'(\infty) &= \lim_{t \searrow 0} t \frac12 \lvert \frac1t - 1\rvert = \lim_{t \searrow 0} \frac12 \left(1 - t \right) = \frac12 \end{align*} confirming (as you could see immediately from other forms of TV) that the TV becomes 1 if $P(\supp Q) = 0$.


Choosing $\mu$, that we deferred earlier:

We want a $\mu$ that dominates both $P$ and $Q$, where the derivative of $P$ wrt $\mu$ has $p(x) = 0$ on $\supp Q$.

Let $\lambda_Q$ be a $\sigma$-finite measure that dominates $Q$. For a discrete distribution, this could be $\lambda_Q(A) = \lvert A \cap \supp Q \rvert$.

Let $\lambda_P$ be a $\sigma$-finite measure that dominates $P$ while also satisfying $\lambda_P(\supp Q) = 0$. For a continuous $P$ and discrete $Q$, this could be the Lebesgue measure. This is possible in any case, though, because we know that $P(\supp Q) = 0$.

We'll choose $\mu = \lambda_P + \lambda_Q$. Now, a Radon-Nikodym derivative of $P$ wrt $\mu$ is any measurable function $p$ such that for all measurable sets $A$, $$P(A) = \int_A p(x) \,\mathrm d \mu(x) = \int_A p(x) \,\mathrm d \lambda_P(x) + \int_A p(x) \,\mathrm d \lambda_Q(x).$$ Let's choose $$ p(x) = \begin{cases} \frac{\mathrm d P}{\mathrm d \lambda_P}(x) & x \notin \supp Q \\ 0 & x \in \supp Q ,\end{cases} $$ which is measurable since $\supp Q$ is measurable, and means that $$ \int_A p(x) \,\mathrm d \mu(x) = \int_{A \setminus \supp Q} \frac{\mathrm d P}{\mathrm d \lambda_P}(x) \, \mathrm d \lambda_P(x) + 0 = P(A \setminus \supp Q) = P(A) .$$ Likewise, choosing $$ q(x) = \begin{cases} \frac{\mathrm d Q}{\mathrm d \lambda_Q}(x) & x \in \supp Q \\ 0 & x \notin \supp Q ,\end{cases} $$ gives $$ \int_A q(x) \,\mathrm d \mu(x) = \int_A q(x) \,\mathrm d \lambda_P(x) + \int_A q(x) \,\mathrm d \lambda_Q(x) = 0 + Q(A) .$$

Thus $p$ and $q$ are valid Radon-Nikodym derivatives wrt $\mu$. They satisfy that if $x \in \supp Q$, $q(x) > 0$, but $p(x) = 0$, as desired.

$\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.