Aller au boulot

Entropy

Definition

For a discrete probability distribution $p$ on the finite set $\{x_1,x_2,\dots ,x_N\}$ with $p_i=p(x_i)$, the entropy of $p$ is defined as

$$h(p)=-\sum _{i=1}^N{p}_i\log p_i.$$

For a continuous probability density function $p$ on an interval $[a,b]$, the entropy of $p$ is defined as

$$h(p)=-{\int }_a^{b}p(x)\log p(x)dx.$$

Theorem

For a probability density function $p$ on a finite set $\{x_1,x_2,\dots ,x_N\}$, then

$$h(p)\le \log n,$$

with equality iff. $p$ is uniform, i.e. $\forall i\le N,p(x_i)=1/n$.

Uniform probability yields maximum uncertainty and therefore maximum entropy.

Theorem

For a continuous probability density function $p$ on $\mathbb{R}$ with variance ${\sigma }^2$, then

$$h(p)\le \frac{1}{2}(1+\log (2\pi {\sigma }^2))$$

with equality iff. $p$ if Gaussian with variance ${\sigma }^2$, i.e. for some $\mu$ we have

$$p(x)=\frac{1}{\sqrt{2\pi }\sigma }{e}^{-\frac{(x-\mu {)}^2}{2{\sigma }^2}}.$$

Theorem

For a continuous probability density function $p$ on $(0,\infty )$ with mean $\lambda$, then

$$h(p)\le 1+\lambda ,$$

with equality iff. $p$ is exponential with mean $\lambda$, i.e.

$$p(x)=\frac{1}{\lambda }{e}^{-\frac{1}{\lambda }x}.$$

Cross entropy

The cross entropy of the distribution $q$ relative to a distribution $p$ over a given set is defined as follows:

$$H(p,q)=-E_p[\log q]=-\sum p\log q=H(p)+D_{\mathrm{K}\mathrm{L}}(p\Vert q)$$

Kullback-Leibler divergence

The Kullback-Leibler divergence (relative entropy) was introduced as the directed divergence between two distributions

$$D_{\text{KL}}(P\parallel Q)=-\sum _{x\in \mathcal{X}}P(x)\log \left(\frac{Q(x)}{P(x)}\right)$$

The Kullback-Leibler divergence is then interpreted as the average difference of the number of bits required for encoding samples of $P$ using a code optimized for $Q$ rather than one optimized for $P$.

Jensen-Shannon divergence

$$D_{\text{JS}}(P\parallel Q)=\frac{1}{2}{D}_{\text{KL}}(P\parallel M)+\frac{1}{2}{D}_{\text{KL}}(Q\parallel M)$$

where $M=\frac{1}{2}(P+Q)$

Mutual Information

Let $(X,Y)$ be a pair of random variables with values over the space $\mathcal{X}\times \mathcal{Y}$. If their joint distribution is $P_{(X,Y)}$ and the marginal distributions are $P_X$ and $P_Y$, the mutual information is defined as

$$I(X;Y)=D_{\mathrm{K}\mathrm{L}}(P_{(X,Y)}\Vert P_X\otimes P_Y)$$

where $D_{\mathrm{K}\mathrm{L}}$ is the Kullback–Leibler divergence.

PMFs for discrete distributions

The mutual information of two jointly discrete random variables $X$ and $Y$ is calculated as a double sum:

$$I(X;Y)=\sum _{y\in \mathcal{Y}}\sum _{x\in \mathcal{X}}{P}_{(X,Y)}(x,y)\log \left(\frac{P_{(X,Y)}(x,y)}{P_X(x)P_Y(y)}\right),$$

where $P_{(X,Y)}$ is the joint probability mass function of $X$ and $Y$, and $P_X$ and $P_Y$ are the marginal probability mass functions of $X$ and $Y$ respectively.

PDFs for continuous distributions

In the case of jointly continuous random variables, the double sum is replaced by a double integral:

$$I(X;Y)={\int }_{\mathcal{Y}}{\int }_{\mathcal{X}}{P}_{(X,Y)}(x,y)\log \left(\frac{P_{(X,Y)}(x,y)}{P_X(x)P_Y(y)}\right)dxdy,$$

where $P_{(X,Y)}$ is now the joint probability density function of $X$ and $Y$, and $P_X$ and $P_Y$ are the marginal probability density functions of $X$ and $Y$ respectively.

Mutual information and Kullback–Leibler divergence

Mutual information is the Kullback–Leibler divergence from the product of the marginal distributions

$$I(X;Y)=D_{\text{KL}}\left(p_{(X,Y)}\parallel p_X{p}_Y\right)$$

$$I(X;Y)={\mathbb{E}}_Y\left[D_{\text{KL}}\left(p_{X\mid Y}\parallel p_X\right)\right]$$