Information

Information is tied to the field of probabilities, and it can be seen as a measure of uncertainty or surprise. To avoid extrapolation and misuse of this concept, you need to remember that it only makes sense to talk about information (in the mathematical sense) when you are studying a probabilistic event.

Information relates to probabilities in that the realization of an event with low probability brings a lot of information, and the realization of an event with high probability brings little information.

So the information gained by knowing an event has realized relates to probability of the event realization. Therefore it has to be a function of the form [begin-latex-inline]I(p)[end-latex-inline], but what is it exactly?

Let's explore the properties we would like such a mapping to have:

1. Low probability [begin-latex-inline]\implies[end-latex-inline] high information

2. High probability [begin-latex-inline]\implies[end-latex-inline] low information

3. [begin-latex-inline]p=1 \implies I=0[end-latex-inline] (if an event is certain to be realized, then knowing about it doesn't bring about any information)

4. [begin-latex-inline] p \to 0 \implies I \to \inf[end-latex-inline] (the opposite of 3 must be true)

5. Information should be additive for independent events, i.e. learning about two independent events should give you the amount of information equal to the sum of the information gained from each event separately:

[begin-latex]p(E_1 \cap E_2) = p(E_1) * p(E_2) \implies I(p(E_1 \cap E_2)) = I(p(E_1)) + I(p(E_2))[end-latex]

If we need this mapping function to be continuous, which we do since probabilities themselves are continuous and that information should not jump suddenly, then there's only one family of functions that meets those requirements: logarithms.

More precisely, the negative logarithms:

We define information mathematically as:

[begin-latex]I(x) = -log(p(x)) \\ \text{or} \\ I(p) = -log(p)[end-latex]
I might use either notation depending on the context to make the equations lighter.

We said the family of functions — indeed, logarithms of all bases meet the requirements listed above. Any base is valid, the difference will be in the unit of the information:

All of those are valid ways of expressing information. In practice, we often use the base 2 logarithm.

Bit: represents the amount of information content gained with a binary choice.

Example 1

I flip a fair coin [begin-latex-inline]p(\text{heads}) = p(\text{tails}) = \frac{1}{2}[end-latex-inline] and tell you the result. I have just given you: [begin-latex-inline]-log_2(\frac{1}{2}) = log_2(2) = 1[end-latex-inline] bit of information! In other words, I have given you the information content gained with 1 binary choice, i.e. one yes/no question.

Recall that [begin-latex-inline]log(\frac{1}{x}) = -log(x)[end-latex-inline].

Logarithm in base 2 answers the question: "how many times do I have to divide x by 2 to get 1 (or less) ?". In other words, how many binary choices do I have to make on my input space to be left with 1 element (or less). Each of these binary choices (divisions) represent one bit of information.

Example 2

I have to pick one fruit amongst 8 different fruits (assume each is equally likely to be picked). I pick one and tell you which: I have just given you [begin-latex-inline]-log_2(\frac{1}{8}) = log_2(8) = 3[end-latex-inline] bits of information. In other words, I have given you the information content gained with 3 binary choices (divide 8 by two 3 times).

I could have measured information in dits instead. It is equally correct to say that I would have given you [begin-latex-inline]-log_{10}(\frac{1}{8}) = log_{10}(8) = 0.9[end-latex-inline] dits of information.

[begin-latex-inline]3 \text{ bits} = 0.9 \text{ dits}[end-latex-inline]

Entropy

In the previous examples, you'll notice that I used uniform probability distributions. The probability of each outcome was equally likely ([begin-latex-inline]p=\frac{1}{2}[end-latex-inline] for the coin toss, and [begin-latex-inline]p=\frac{1}{8}[end-latex-inline] for the fruit pick). Then I asked:

What is the information gained for observing one of those events?

Since the probability was the same for all events, then the answer to that question would be the same regardless of the outcome of the random experiment.

What if each outcome had a different probability of realization?

What if I had to pick between 3 fruits, each with a different probability according to my preferences:

A natural question is: on average, what is the information gained for observing an event from that random experiment? We are asking the same question as before, but of course since each outcome has a different probability, and since the information depends on the probability, the result will change for different outcomes. Therefore we ask about the average outcome.

One way is to sum the information gained by each event weighted by the probability of realization.

[begin-latex]\begin{align*} \mathbb{E}[I] &= p(M) * I(M) + p(A) * I(A) + p(O) * I(O) \\ &= -p(M)*log(p(M)) -p(A)*log(p(A)) -p(O)*log(p(O)) \\ &= -0.7*log(0.7) -0.2*log(0.2) -0.1*log(0.1) \\ &= 0.35 \end{align*}[end-latex]
That is exactly what entropy is!

We call entropy the expected amount of information gained for observing an event from a random variable. In other words, this answers the question: "If I sample an event from a variable [begin-latex-inline]X[end-latex-inline]; On average, what is the information gained for observing one of [begin-latex-inline]x_1[end-latex-inline], [begin-latex-inline]x_2[end-latex-inline], ..., or [begin-latex-inline]x_n[end-latex-inline] given the probability distribution of those events?".

We usually denote the entropy of a random variable [begin-latex-inline]X[end-latex-inline] as [begin-latex-inline]H(X)[end-latex-inline]:

[begin-latex]\begin{align*} H(X) &= \sum_x p(x) * I(x) \\ &= - \sum_x p(x) * log(p(x)) \end{align*}[end-latex]
An interesting follow up question is: when is the entropy minimal/maximal ?

We can try to intuitively answer. Give it a thought!

Minimal Entropy

Since entropy is the expected information to be gained from observing a random variable, and since information is minimal when events are certain to be realized, the absolute minimum would be reached if a random variable could be predictable every time, i.e. if it had an event with probability [begin-latex-inline]p=1[end-latex-inline] and the rest [begin-latex-inline]p=0[end-latex-inline] (in which case [begin-latex-inline]H(X)=0[end-latex-inline]). Any other probability distribution would yield some amount of information.

Maximum Entropy

Entropy is maximized if the average information is maximal. We know information is highest for most improbable events ([begin-latex-inline]p \to 0[end-latex-inline]). If we have multiple events, each with a certain probability, and we want those probabilities to be as low as possible, then the lowest we can go on average is when we spread the probability space over all events equally, that is [begin-latex-inline]p=\frac{1}{n}[end-latex-inline] with [begin-latex-inline]n[end-latex-inline] the number of events. In other words: a uniform probability distribution.

You can see the uniform distribution as the most "unpredictable" — the one for which each event brings the maximum amount of information content upon realization.

I highly advise checking out 3B1B video on how to solve the game Wordle using the concept of entropy.

Solving Wordle using information theory An excuse to teach a lesson on information theory and entropy.These lessons are funded by viewers: https://www.patreon.com/3blue1brownSpecial thanks to these... www.youtube.com

There's also another way to interpret entropy, and it's going to be useful for the rest of the article, so before going further with Cross Entropy and Relative Entropy, we're making a little stop at encoders.

Encoders

An encoder is a machine/routine/code that assigns a code to each event of a probability distribution (let's say in bits, but we could use another base).

An encoder is optimal, if on average, it uses the theoretical minimum number of bits possible to represent an event drawn from the distribution.

Example 1

Say we have three events [begin-latex-inline]\{A,B,C\}[end-latex-inline], with [begin-latex-inline]p(A)=p(B)=p(C)=\frac{1}{3}[end-latex-inline].

We could create a coding (a mapping) that uses 2 bits to encode each outcome:

If I then give you a list of bits, e.g. 011000, you are able to decode it (by splitting every 2 bits and using the mapping above): 011000 → BCA. This works out fine, but we are waisting the 11 state of our 2 bits, which accounts for 25% of all possible states! This is not very optimal.

What if we assigned less bits to some events ?

Example 2

Consider the following encoder:

Here, we use a total of 5 bits to encode 3 states (instead of 6 bits in the previous coding), that is [begin-latex-inline]\frac{5}{3} = 1.7[end-latex-inline] bits on average, which is less than 2 bits like previously.

With this new encoder, suppose we read the first 2 bits of a message [begin-latex-inline]b_1, b_2[end-latex-inline]:

And we can keep reading and decoding a long string of bits that way.

Why not use even less bits?

Example 3 ❌

Consider this final encoder:

This uses less bits than the previous too, but it is also ambiguous!

The bit string [begin-latex-inline]00[end-latex-inline] could be either [begin-latex-inline]AA[end-latex-inline] or [begin-latex-inline]C[end-latex-inline], and there's no way to go around this.

An encoder must be unambiguous, i.e. decodable in a single way.

Encoders & Entropy

How does that relate to entropy?

Think about the optimal encoder: that will be the encoder that assigns, on average, the least amount of bits possible to an event of your distribution.

In example 2 above, we considered [begin-latex-inline]\{A,B,C\}[end-latex-inline] to be equally likely; but what if [begin-latex-inline]C[end-latex-inline] was more probable than [begin-latex-inline]A[end-latex-inline] and [begin-latex-inline]B[end-latex-inline]? Wouldn't it be better then to assign the single bit to [begin-latex-inline]C[end-latex-inline] and two bits to [begin-latex-inline]A[end-latex-inline] and [begin-latex-inline]B[end-latex-inline]?

To achieve optimality, we need to assign less bits to more probable outcomes, and more bits to less probable outcomes.

A natural question is then:

What is the minimum number of bits we can use to encode events drawn from a given probability distribution?

The answer is... entropy!

Shannon's source coding theorem - Wikipedia en.wikipedia.org

To clarify: the entropy is the theoretical minimum, but in practice you may not come up with an encoder that uses [begin-latex-inline]H(X)[end-latex-inline] number of bits on average.

Now that we're equipped with this new insight, let's tackle the next concepts!

Cross Entropy

Let's say I have a machine that produces random letters (a-z) according to a certain unknown probability distribution [begin-latex-inline]P = \{p(a), p(b), ..., p(z)\}[end-latex-inline].

Your task is to create an optimal encoder for [begin-latex-inline]P[end-latex-inline], i.e. an encoder that uses, on average, the least amount of bits possible to encode events from this distribution.

We know from earlier that the optimal encoder uses, on average, a number of bits equal to the entropy of the distribution [begin-latex-inline]H(P)[end-latex-inline]. But for this you need to know the exact distribution, and here you don't!

Therefore, you will have to guess what the true distribution is and produce an encoder based on your guess. Let's call your guessed distribution [begin-latex-inline]Q = \{q(a), q(b), ..., q(z)\}[end-latex-inline]. By definition, the average number of bits used by your encoder for [begin-latex-inline]Q[end-latex-inline] will be higher or equal to [begin-latex-inline]H(P)[end-latex-inline]... and the actual amount is called the cross entropy between [begin-latex-inline]P[end-latex-inline] and [begin-latex-inline]Q[end-latex-inline].

The cross entropy between [begin-latex-inline]P[end-latex-inline] and [begin-latex-inline]Q[end-latex-inline] is the average number of bits needed to encode events from [begin-latex-inline]P[end-latex-inline] using an optimal encoder for [begin-latex-inline]Q[end-latex-inline]. We denote that number [begin-latex-inline]H(P, Q)[end-latex-inline].

Said differently, it means that you were expecting data from a probability distribution [begin-latex-inline]Q[end-latex-inline], but in reality the data belonged to a probability distribution [begin-latex-inline]P[end-latex-inline]. And the average number of bits used to encode those events from [begin-latex-inline]P[end-latex-inline] (while expecting they were drawn from [begin-latex-inline]Q[end-latex-inline]) is what we call the cross entropy.

Can you guess the formula?
[begin-latex]\begin{align*} H(P, Q) &= p(x_1) * I(q(x_1)) + p(x_2) * I(q(x_2)) + \ldots \\ &= \sum_x p(x) * I(q(x)) \\ &= - \sum_x p(x) * log(q(x)) \\ \end{align*}[end-latex]

This looks very much like [begin-latex-inline]H(Q)[end-latex-inline], but the information is weighted by the probabilities coming from [begin-latex-inline]P[end-latex-inline]. This makes sense:

You will be using [begin-latex-inline]Q[end-latex-inline] to encode events coming from the machine, therefore the information content will be calculated using [begin-latex-inline]q(x)[end-latex-inline]. However, the actual weighting of the information for each event comes from [begin-latex-inline]P[end-latex-inline] since that is the true frequency of the events.

Notice that [begin-latex-inline]H(P, Q) \neq H(Q, P)[end-latex-inline].

Also, notice that if you had guessed [begin-latex-inline]P[end-latex-inline] perfectly well ([begin-latex-inline]Q=P[end-latex-inline]), then the result should be the theoretical minimum number of bits possible to encode events from [begin-latex-inline]P[end-latex-inline], which is the entropy:

[begin-latex]\begin{align*} H(P, P) &= - \sum_x p(x) * log(p(x)) \\ &= H(P) \end{align*}[end-latex]

Relative Entropy

Lastly, the relative entropy, also known as the KL divergence.

If you've understood the cross entropy, then this should be a piece of cake!

The cross entropy is the average number of bits used if you encode events drawn from a distribution [begin-latex-inline]P[end-latex-inline] while expecting the events to come from a distribution [begin-latex-inline]Q[end-latex-inline]. We said this number must be higher or equal to [begin-latex-inline]H(P)[end-latex-inline] since that would be the number of bits used by a perfect encoder for [begin-latex-inline]P[end-latex-inline]. [begin-latex-inline]H(P)[end-latex-inline] is a lower bound for [begin-latex-inline]H(P, Q)[end-latex-inline].

The number of extra bits used relative to [begin-latex-inline]H(P)[end-latex-inline] is what we call the relative entropy and we denote it [begin-latex-inline]KL(P||Q)[end-latex-inline]! That is, not the entire entropy but just the extra you used due to the error in guessing [begin-latex-inline]P[end-latex-inline].

The relative entropy is the difference in information used by a suboptimal encoder and an optimal encoder: [begin-latex-inline]H(P, Q) - H(P)[end-latex-inline].
[begin-latex]\begin{align*} KL(P || Q) &= H(P, Q) - H(P) \\ &= -\sum_x p(x) * log(q(x)) + \sum_x p(x) log(p(x)) \\ &= \sum_x p(x) * (log(p(x)) - log(q(x))) \\ &= \sum_x p(x) * log\left(\frac{p(x)}{q(x)}\right) \\ \end{align*}[end-latex]

Like the cross entropy, the relative entropy is not commutative: [begin-latex-inline]KL(P||Q) \neq KL(Q||P)[end-latex-inline]. You can understand it as a measure of relative difference between two probability distributions, the minimum being [begin-latex-inline]0[end-latex-inline] when [begin-latex-inline]Q=P[end-latex-inline].

Last Note

In machine learning, we try to minimize the cross entropy:

[begin-latex]H(P, Q) = KL(P || Q) + H(P)[end-latex]

Where [begin-latex-inline]P[end-latex-inline] is the distribution of the data, and [begin-latex-inline]Q[end-latex-inline] is the distribution of the model. Since the data doesn't change during the training, [begin-latex-inline]H(P)[end-latex-inline] is a constant, we are essentially minimizing the relative entropy, i.e. the difference between [begin-latex-inline]P[end-latex-inline] and [begin-latex-inline]Q[end-latex-inline].

Interestingly, in the context of LLMs (Large Language Models), when we minimize the cross entropy and therefore minimize the relative entropy, the loss we end up with after training is an approximation (as KL goes to 0) of the entropy of the data distribution, that is, the entropy of language.