Information Theory Basics

An overview of the concept “Entropy”, “Mutual Information”, “KL Divergence”, and “F-Divergence”. In this work, we discuss important concepts to information theory, often useful for intuition, and proofs.

Entropy

The entropy of a probability distribution ( $x$ ) is denoted with the symbol $\mathcal{H}(x)$ , such that $\mathcal{H}(x) = -\sum p \log p$ . Furthermore, we can prove that this entropy is bounded above using Jensen’s Inequality as follows:

$\begin{align*} H(X) &= \mathbb{E}\left(\log_2 \frac{1}{\mathbb{P}_X(X)}\right)\\ &\le \log_2 \mathbb{E} \left(\frac{1}{\mathbb{P}_X(X)}\right)\hspace{2cm}(\textrm{Jensen's inequality})\\ & = \log_2 |\mathcal{X}|. \end{align*}$

Mutual Information

In probability theory and information theory, the mutual information (MI) of two random variables is a measure of the mutual dependence between the two variables. More specifically, it quantifies the “amount of information” (in units such as shannons (bits), nats or hartleys) obtained about one random variable by observing the other random variable. The concept of mutual information is intimately linked to that of entropy of a random variable, a fundamental notion in information theory that quantifies the expected “amount of information” held in a random variable. The Mutual information is basically the KL divergence between the joint probability function $P(X,Y)$ , and the marginal probability distributions $P(X)$ , and $P(Y)$ .

KL Divergence

In mathematical statistics, Kullback-Leibler divergence, denoted by $D_{\text{KL}}(P||Q)$ , is a type of statistical distance: a measure of how one probability distribution $P$ is different from the second reference probability distribution $Q$ . A simple interpretation of KL divergence of $P$ from $Q$ is the expected excess surprise from using $Q$ as a model when the actual distribution is $P$ . The exact definition of KL divergence is explained below.

$D_{\text{KL}}(P||Q) = \sum _{x\in\mathcal{X}} P(x)\log \begin{pmatrix} \frac{P(x)}{Q(x)} \end{pmatrix}$

F Divergence

In probability theory, an f-divergence is a function $D_f(P||Q)$ that measures the difference between two probability distributions $P$ and $Q$ . Many common divergences, such as KL-divergence, Hellinger distance, and total variational distance, are special cases of f-divergence.

$D_{f}(P||Q) = \int _{\Omega } f \begin{pmatrix} \frac{dP}{dQ} \end{pmatrix}dQ$

Here, f is called the generator of $D_{f}$ . In concrete applications, there is usally a reference distribution $\mu$ on $\Omega$ , such that $P, Q \ll \mu$ , then we can use Radon-Nikodym theorem to take their probability densities p and q giving:

$D_{f}(P||Q) = \int _{\Omega } f \begin{pmatrix} \frac{p(x)}{q(x)} \end{pmatrix}q(x) d\mu(x)$

When the generator function is x\log x, we get the KL-Divegence.

Written on June 17, 2022