14
$\begingroup$

Is it possible to use Fisher Information at p to get a useful upper bound on KL(q,p)?

KL(q,p) is known as Kullback-Liebler divergence and is defined for discrete distributions over k outcomes as follows:

$$KL(q,p)=\sum_i^k q_i \log \frac{q_i}{p_i}$$

The most obvious approach is to use the fact that 1/2 x' I x is the second order Taylor expansion of KL(p+x,p) where I is Fisher Information Matrix evaluated at p and try to use that as an upper bound (derivation of expansion from Kullback's book, pages 26, 27, 28).

If $p(x,t)$ gives probability of observation $x$ in a discrete distribution parameterized by parameter vector $t$, Fisher Information Matrix is defined as follows

$$I_{ij}(t)=\sum_x p(x,t) (\frac{\partial}{\partial t_i} \log p(x,t)) ( \frac{\partial}{\partial t_j} \log p(x,t)) $$

where sum is taken over all possible observations.

Below is a visualization of sets of $k=3$ multinomial distributions for some random $p$'s (marked as black dots) where this bound holds. From plots it seems that this bound works for sets of distributions that are "between" $p$ and the "furthermost" 0 entropy distribution.

(source)

Motivation: Sanov's theorem bounds probability of some event in terms of KL-divergence of the most likely outcome...but KL-divergence is unwieldy and it would be nicer to have a simpler bound, especially if it can be easily expressed in terms of parameters of the distribution we are working with

$\endgroup$
  • 2
    $\begingroup$ Here's Mathematica notebook to generate figure above, I always welcome coding suggestions yaroslavvb.com/research/qr/mo-multinomials/mo-fisher-bound.nb $\endgroup$ – Yaroslav Bulatov Aug 19 '10 at 21:53
  • $\begingroup$ Any chance you could either define or give a reference for what you mean by Fisher information and KL(q,p)? $\endgroup$ – Deane Yang Aug 19 '10 at 21:55
  • 2
    $\begingroup$ what does it mean to relate the two ? they are of different "type" - the fisher information is a metric tensor, and the kl-divergence is a distance measure. $\endgroup$ – Suresh Venkat Aug 20 '10 at 2:50
  • $\begingroup$ Second order Taylor expansion of KL uses Fisher information matrix and "relates" to KL. I'm trying to see if that expansion relates to KL in any interesting way outside of neighborhood of the expansion point $\endgroup$ – Yaroslav Bulatov Aug 20 '10 at 3:38
  • 1
    $\begingroup$ i think, it might be easier to work with the Jensen-Shannon divergence instead of KL. $\endgroup$ – Suvrit Nov 10 '10 at 14:04
2
$\begingroup$

I'm not sure if this is still of interest to you, but I think it is possible to get some reasonable bounds if you are okay with dropping the factor of $\frac{1}{2}$. Here's my work, which can be strengthened and refined.

We start by taking two probability mass functions $p$ and $q$ which we denote as $p_i$ and $q_i$. We define the function $f$ as $f_i= q_i-p_i$. Instead of doing anything fancy, we consider the line segment $p_i(t) = p_i +tf_i$. Since $f$ has total mass zero, the $p_i(t)$ are well defined probability distributions that form a straight line in the probability simplex. We can see that $p_i(0) = p_i$ and $p_i(1) = q_i$

Now we take the Taylor series for the Kullback-Liebler divergence, expanded at $t=0$. This will involve the Fisher metric, but we should expand it out further to get better results.

When we expand out $(p_i + t f_i)\log\left( \frac{p_i + t f_i}{p_i} \right)$, we get the following:

$$f_i t+\frac{f_i^2 t^2}{2 p_i}-\frac{f_i^3 t^3}{6 p_i^2}+\frac{f_i^4 t^4}{12 p_i^3}-\frac{f_i^5 t^5}{20 p_i^4}+\frac{f_i^6 t^6}{30 p_i^5}+O\left(t^7\right)$$

When we sum over $i$, the first term will vanish, and we can factor out a Fisher metric term from all of the others. I will use an integral sign to sum over $i$, as it is suggestive of what should happen in the continuous case.

$$\int f_i t+\frac{f_i^2 t^2}{2 p_i}-\frac{f_i^3 t^3}{6 p_i^2}+\frac{f_i^4 t^4}{12 p_i^3} \ldots \,di = \int \frac{f_i^2 t^2}{ p_i} \left( \frac{1}{2} - \frac{f_i t}{6 p_i} + \frac{f_i^2 t^2}{12 p_i^2} \ldots \right) di $$

We find that the terms in the parenthesis on the right hand side can be simplified. We set $x_i = \frac{f_i t}{p_i}$ and can derive the following:

$$\left( \frac{1}{2} - \frac{x_i}{6} + \frac{x_i}{12} \ldots \right) = \sum_{k=0}^\infty \frac{(-1)^k x_i^k}{(k+1)(k+2)} = \frac{(x_i +1)\log(x_i+1)-x_i}{x_i^2}$$

This should not be surprising; it's very closely related to the original formula for the Kullbeck-Liebler divergence. In fact, we didn't need Taylor series except to know to subtract off the pesky $t f_i$ term. Therefore, we don't need to worry about the convergence, this manipulation is valid without the series. Therefore,

$$KL(p(t), p) = \int \frac{f_i^2 t^2}{ p_i} \left( \frac{( x_i +1)\log(x_i+1)-x_i}{x_i^2} \right) di $$

In order for this to make sense, we need to make sure that $x_i= \frac{f_i t}{p_i} \geq -1$. However, $\frac{f_i}{p_i} = \frac{q_i}{p_i} - 1 \geq -1$. Even better, it turns out that $ \frac{( x_i +1)\log(x_i+1)-x_i}{x_i^2} \leq 1$ on its domain. With this, we are done, because this implies $$KL(q,p)< I_p(f,f).$$

This implies that we can bound the Kullback-Liebler divergence by the Fisher information metric evaluated on a particular vector $f$. Since the KL-divergence can blow up, it's worthwhile to see what happens in this case. Whenever this happens, the tangent vector $f$ at $p$ is large in the Fisher metric.

$\endgroup$

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.