Pourquoi la divergence KL n'est pas négative?

Pourquoi la divergence KL n'est-elle pas négative?

Du point de vue de la théorie de l'information, j'ai une telle compréhension intuitive:

Disons qu'il y a deux ensembles $A$ et $B$ qui sont composés du même ensemble d'éléments étiquetés par $x$ . $p(x)$ et $q(x)$ sont des distributions de probabilité différentes sur l'ensemble $A$ et $B$ respectivement.

Du point de vue de la théorie de l' information, $\log_{2}(P(x))$ est la plus petite quantité de bits nécessaires pour enregistrer un élément $x$ pour ensemble $A$ . Pour que l'attente puisse être interprétée comme au moins le nombre de bits dont nous avons besoin pour enregistrer un élément dans en moyenne.

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

Étant donné que cette formule met une borne inférieure sur les bits dont nous avons besoin en moyenne, de sorte que pour un ensemble différent qui entraîne une distribution de probabilité différente , la borne qu'elle donne pour chaque élément ne sera certainement pas le bit qui est donné par , ce qui signifie prendre l'espérance, cette longueur moyenne sera sûrement supérieure à la précédente, ce qui conduit à Je ne mets pas ici puisque et sont différents. $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)$

Ceci est ma compréhension intuitive, existe-t-il un moyen purement mathématique de prouver que la divergence KL est non négative? Le problème peut être déclaré comme suit:

Étant donné que et sont tous deux positifs sur la ligne réelle, et , . Prouver n'est pas négatif. $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)}$

Comment cela peut-il être prouvé? Ou cela peut-il être prouvé sans conditions supplémentaires?

information-theory kullback-leibler meTchaikovsky
la source

Si vous comprenez la preuve de l' inégalité de Fano, il est facile de déduire la non négativité de l'entropie relative.

Lerner Zhang

Réponses:

Preuve 1:

Notons tout d'abord que pour tout . $\ln a \leq a-1$ $a \gt 0$

$-D_{KL}(p||q) \leq 0$ $D_{KL}(p||q) \geq 0$

\begin{aligned} - ré (p | | q) & = - \sum_{X} p (X) \ln \frac{p (X)}{q (X)} \\ = \sum_{X} p (X) \ln \frac{q (X)}{p (X)} \\ \overset{(une)}{\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}$

$\ln$

- \sum_{X} p (X) {Journal}_{2} p (X) \leq - \sum_{X} p (X) {Journal}_{2} q (X)

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

\sum_{X} p (X) {Journal}_{2} p (X) - \sum_{X} p (X) {Journal}_{2} q (X) \geq 0 \sum_{X} p (X) {Journal}_{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 raison pour laquelle je n'inclus pas cela en tant que preuve distincte est que si vous me demandiez de prouver l'inégalité de Gibbs, je devrais partir de la non-négativité de la divergence KL et faire la même preuve par le haut.

\sum_{je = 1}^{n} {une}_{je} {Journal}_{2} \frac{{une}_{je}}{b_{je}} \geq (\sum_{je = 1}^{n} {une}_{je}) {Journal}_{2} \frac{\sum_{je = 1}^{n} {une}_{je}}{\sum_{je = 1}^{n} b_{je}}

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

$D_{KL}(p||q) \geq 0$

\begin{aligned} ré (p | | q) & = \sum_{X} p (X) {Journal}_{2} \frac{p (X)}{q (X)} \\ \overset{b)}{\geq} (\sum_{X} p (X)) {Journal}_{2} \frac{\sum_{X} p (X)}{\sum_{X} q (X)} \\ = 1 \cdot {Journal}_{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}$

où nous avons utilisé l'inégalité de la somme Log en (b).

Preuve 3:

(Tiré du livre "Elements of Information Theory" de Thomas M. Cover et Joy A. Thomas)

\begin{aligned} - ré (p | | q) & = - \sum_{X} p (X) {Journal}_{2} \frac{p (X)}{q (X)} \\ = \sum_{X} p (X) {Journal}_{2} \frac{q (X)}{p (X)} \\ \overset{(c)}{\leq} {Journal}_{2} \sum_{X} p (X) \frac{q (X)}{p (X)} \\ = {Journal}_{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}$

où en (c) nous avons utilisé l'inégalité de Jensen et le fait que $\log$ est une fonction concave.

Andreas G.
la source