Relationship between KL divergence, cross entropy and encoding

The relationship between KL divergence and cross entropy

Information amount: $-log(p)$, (the log here is based on e).

And entropy is the expectation of information amount: $\sum_{i = 1}^n p(x_i)log(\frac{1}{p(x_i)})$

For two different probability distributions, KL divergence can be used to measure the difference between the two probability distributions:

$$D_{KL}(p||q) = \sum_{i = 1}^n p(x_i) log\left( \frac{p(x_i)}{q(x_i)} \right)\\ = \sum_{i = 1}^n p(x_i) log(p(x_i)) - \sum_{i = 1}^n p(x_i) log(q(x_i))\\ = \left[ \sum_{i = 1}^n p(x_i) log(\frac{1}{q(x_i)}) \right] -\sum_{i = 1}^n p(x_i) log(\frac{1}{p(x_i)})$$

That is, KL divergence = cross entropy - information entropy. Information entropy is a constant after the distribution is determined, so optimizing cross entropy is equivalent to optimizing KL divergence

Note that the asymmetry of KL divergence cannot be regarded as a measure of distance between different distributions, because it can be seen from the calculation formula of KL divergence that it does not comply with symmetry (the distance measure should satisfy symmetry), that is, $D_{KL}(P||Q) \neq D_{KL}(Q||P)$

The TD-IDF algorithm can be understood as the application of relative entropy: the difference between the distribution of word frequency in the entire corpus and the distribution of word frequency in specific documents.

Therefore, if you want to derive the cross-entropy loss function, a common explanation on the Internet is to derive the cross-entropy loss function from logarithmic probability regression, but it can also be derived from KL divergence

The relationship between information entropy and encoding

Let’s talk about the conclusion first: Information entropy is the expectation of the amount of information, which can reflect the amount of bits required to be encoded.

For example: a random variable X has only four states (a, b, c, d), and the probability of each state is the same ($\frac{1}{4}$), then the information entropy is 2, In order to transmit the value of X to the receiver, a 2-bit message needs to be transmitted

If the above four states are not evenly distributed, for example $(\frac{1}{2}, \frac{1}{4},\frac{1}{8}, \frac{1}{8})$ , then the required information entropy is 1.75, In order to transmit the value of X to the receiver, we need to transmit a 1.75-bit message

There is a mathematical rule hidden: uniformly distributed information entropy requires more encoding digits and more bits than non-uniformly distributed information entropy;

Then, For non-uniform distribution, shorter codewords can be used to express high probability events, and longer codewords can be used to express low probability events

(Same as Huffman coding)

Shannon Coding Theorem: Entropy is the lower bound on the number of bits required to transmit the state value of a random variable (the shortest average code length)

In other words, given the probabilities of each category of a set of information, the entropy can be easily calculated, and the shortest average coding length can be directly obtained.

The above explanation can lead to another understanding of cross entropy as a loss function:

The so-called optimization of the loss function is to use the distribution of the function q (computable) to fit the true distribution p (unknown) as much as possible.

The so-called cross entropy $\sum_{i = 1}^n p log(\frac{1}{q})$ refers to using distribution $q$ to represent the average coding length of distribution $p$.

Optimizing cross entropy is equivalent to letting the function fit the true distribution

KL divergence is relative entropy

Assume $p(x) and q(x)$ are two probability distributions of values in discrete random variable $X$, then the relative entropy of $p$ to $q$ is:

$$D_{KL}(p||q)=∑_xp(x) log \frac{p(x)}{q(x)}=E \{p(x)log \frac{p(x)}{q(x)} \}$$

Properties:

1. If the two distributions $p(x)$ and $q(x)$ are the same, then the relative entropy is equal to 0

2. $D_{KL}(p||q)≠D_{KL}(q||p)$, the relative entropy has asymmetry. You can give a simple example to calculate it.

3. $D_{KL}(p||q)≥0$ is proved as follows (using Jensen’s inequality) (non-negativity)

Relative entropy refers to the extra encoding length required to represent distribution $p$ (real distribution) using $q$ (non-real distribution).

KL divergence is a measure of the average number of extra bits required to encode samples from “p” using “q-based encoding”

Conditional entropy

Conditional entropy $H(Y|X)$ represents the uncertainty of a random variable $Y$ given a known random variable $X$.

Conditional entropy $H(Y|X)$ is defined as the mathematical expectation of the entropy of the conditional probability distribution of $Y$ with respect to $X$ under the given conditions of $X$:

Maximum likelihood estimation angle

Of course, there is another way to derive cross entropy from the perspective of log probability regression, which shows that cross entropy loss is equivalent to the maximum likelihood estimate of log probability regression.

Then, the numerator and denominator in the logarithmic probability are just artificially added as probabilities.

For specific derivation, see Simple cross-entropy loss function, do you really understand it? - Zhihu

References

Loss function: Detailed explanation of cross entropy