¿Por qué la divergencia KL no es negativa?

Desde la perspectiva de la teoría de la información, tengo una comprensión tan intuitiva:

Digamos que hay dos conjuntos y que se componen del mismo conjunto de elementos etiquetados por . y son diferentes distribuciones de probabilidad sobre el conjunto y respectivamente. $A$ $B$ $x$ $p(x)$ $q(x)$ $A$ $B$

Desde la perspectiva de teoría de la información, es la menor cantidad de bits que requiere para la grabación de un elemento para conjunto . Para que la expectativa pueda interpretarse como al menos cuántos bits necesitamos para registrar un elemento en en promedio. $\log_{2}(P(x))$ $x$ $A$

\sum_{x \in e n s e m b l e} - p (x) \ln (p (x))

$\sum_{x \in ensemble}-p(x)\ln(p(x))$

A

$A$

Dado que esta fórmula pone un límite inferior en los bits que necesitamos en promedio, de modo que para un conjunto diferente que produce una distribución de probabilidad diferente , el límite que proporciona para cada elemento seguramente no será un bit que sea dado por , lo que significa tomar la expectativa, esta longitud promedio seguramente será mayor que la anterior, lo que lleva a no pongo aquí, ya que y son diferentes. $B$ $q(x)$ $x$ $p(x)$

\sum_{x \in e n s e m b l e} - p (x) \ln (q (x))

$\sum_{x\in ensemble}-p(x)\ln(q(x))$

\sum_{x \in e n s e m b l e} p (x) \frac{\ln (p (x))}{\ln (q (x))} > 0

$\sum_{x\in ensemble }p(x)\frac{\ln(p(x))}{\ln(q(x))} > 0$

\geq

$\ge$

p (x)

$p(x)$

q (x)

$q(x)$

Esta es mi comprensión intuitiva, ¿existe una forma puramente matemática de probar que la divergencia de KL no es negativa? El problema se puede expresar como:

Dado que y son positivos sobre la línea real, y , . Probar no es negativo. $p(x)$ $q(x)$ $\int_{-\infty}^{+\infty}p(x)dx = 1$ $\int_{-\infty}^{+\infty}q(x)dx = 1$

\int_{- \infty}^{+ \infty} p (x) \ln \frac{p (x)}{q (x)}

$\int_{-\infty}^{+\infty}p(x)\ln\frac{p(x)}{q(x)}$

¿Cómo se puede probar esto? ¿O puede probarse esto sin condiciones adicionales?

information-theory kullback-leibler meTchaikovsky
fuente

Si comprende la prueba de la desigualdad de Fano, es fácil deducir la no negatividad de la entropía relativa.

Lerner Zhang

Respuestas:

Prueba 1:

Primero tenga en cuenta que para todo . $\ln a \leq a-1$ $a \gt 0$

Ahora mostraremos que que significa que $-D_{KL}(p||q) \leq 0$ $D_{KL}(p||q) \geq 0$

\begin{aligned} - D (p | | q) & = - \sum_{x} p (x) \ln \frac{p (x)}{q (x)} \\ = \sum_{x} p (x) \ln \frac{q (x)}{p (x)} \\ \overset{(a)}{\leq} \sum_{x} p (x) (\frac{q (x)}{p (x)} - 1) \\ = \sum_{x} q (x) - \sum_{x} p (x) \\ = 1 - 1 \\ = 0 \end{aligned}

$\begin{align} -D(p||q)&=-\sum_x p(x)\ln \frac{p(x)}{q(x)}\\ &= \sum_x p(x)\ln \frac{q(x)}{p(x)}\\ &\stackrel{\text{(a)}}{\leq} \sum_x p(x)\left(\frac{q(x)}{p(x)}-1\right)\\ &=\sum_x q(x) - \sum_x p(x)\\ &= 1 - 1\\ &= 0 \end{align}$

Para la desigualdad (a) utilizamos la desigualdad explicada al principio. $\ln$

Alternativamente, puede comenzar con la desigualdad de Gibbs que establece:

- \sum_{x} p (x) \log_{2} p (x) \leq - \sum_{x} p (x) \log_{2} q (x)

$-\sum_x p(x) \log_2 p(x) \leq -\sum_x p(x)\log_2 q(x)$

Entonces, si llevamos el término izquierdo a la derecha, obtenemos:

\sum_{x} p (x) \log_{2} p (x) - \sum_{x} p (x) \log_{2} q (x) \geq 0 \sum_{x} p (x) \log_{2} \frac{p (x)}{q (x)} \geq 0

$\sum_x p(x) \log_2 p(x) - \sum_x p(x)\log_2 q(x)\geq 0 \\ \sum_x p(x)\log_2 \frac{p(x)}{q(x)}\geq 0$

La razón por la que no incluyo esto como una prueba separada es porque si me pidiera que probara la desigualdad de Gibbs, tendría que comenzar desde la no negatividad de la divergencia KL y hacer la misma prueba desde arriba.

Prueba 2: Usamos la desigualdad de Log log sum :

\sum_{i = 1}^{n} a_{i} \log_{2} \frac{a_{i}}{b_{i}} \geq (\sum_{i = 1}^{n} a_{i}) \log_{2} \frac{\sum_{i = 1}^{n} a_{i}}{\sum_{i = 1}^{n} b_{i}}

$\sum_{i=1}^{n} a_i \log_2 \frac{a_i}{b_i} \geq \left(\sum_{i=1}^{n} a_i\right)\log_2\frac{\sum_{i=1}^{n} a_i}{\sum_{i=1}^{n} b_i}$

Entonces podemos mostrar que : $D_{KL}(p||q) \geq 0$

\begin{aligned} D (p | | q) & = \sum_{x} p (x) \log_{2} \frac{p (x)}{q (x)} \\ \overset{(b)}{\geq} (\sum_{x} p (x)) \log_{2} \frac{\sum_{x} p (x)}{\sum_{x} q (x)} \\ = 1 \cdot \log_{2} \frac{1}{1} \\ = 0 \end{aligned}

$\begin{align} D(p||q)&=\sum_x p(x)\log_2 \frac{p(x)}{q(x)}\\ &\stackrel{\text{(b)}}{\geq} \left(\sum_x p(x)\right)\log_2\frac{\sum_x p(x)}{\sum_x q(x)}\\ &=1 \cdot \log_2 \frac{1}{1}\\ &=0 \end{align}$

donde hemos usado el Log sum desigualdad en (b).

Prueba 3:

(Tomado del libro "Elementos de la teoría de la información" de Thomas M. Cover y Joy A. Thomas)

\begin{aligned} - D (p | | q) & = - \sum_{x} p (x) \log_{2} \frac{p (x)}{q (x)} \\ = \sum_{x} p (x) \log_{2} \frac{q (x)}{p (x)} \\ \overset{(c)}{\leq} \log_{2} \sum_{x} p (x) \frac{q (x)}{p (x)} \\ = \log_{2} 1 \\ = 0 \end{aligned}

$\begin{align} -D(p||q)&=-\sum_x p(x)\log_2 \frac{p(x)}{q(x)}\\ &= \sum_x p(x)\log_2 \frac{q(x)}{p(x)}\\ &\stackrel{\text{(c)}}{\leq} \log_2 \sum_x p(x)\frac{q(x)}{p(x)}\\ &=\log_2 1\\ &=0 \end{align}$

donde en (c) hemos utilizado la desigualdad de Jensen y el hecho de que es una función cóncava. $\log$

Andreas G.
fuente