Machine Learning for Engineers:

Chapter 3. Inference, or Model-Based Prediction

CME 465 Lecture Slides

University of Saskatchewan

Fall 2024

Book: Machine Learning for Engineers, by Osvaldo Simeone, CUP, 2022

Fall 2024 1 / 108

This Chapter

Learning is needed when a “model” for the data is not available.

This chapter discusses the ideal case in which learning is not
necessary since a model for the data is known.
Inference includes the problems of:
▶ detection, i.e., prediction of discrete-valued quantities;
▶ and estimation, i.e., prediction of continuous-valued quantities.
This chapter will introduce key concepts such as loss function,
population loss, optimal hard/ soft predictors, log-loss, cross-entropy
loss and cross entropy, entropy and conditional entropy, KL
divergence, and mutual information.

Fall 2024 2 / 108

Overview

Defining inference
Optimal soft prediction, or Bayesian inference
Loss function and optimal hard prediction
KL divergence
Optimal soft prediction revisited
Mutual information
Summary

Fall 2024 3 / 108

 Defining Inference

Fall 2024 4 / 108

Defining Inference

In inference problems, we have two types of variables:

▶ input variables x,
▶ and output, or target, variables t.
The general problem in inference is to obtain a predictor of target t
given input x based on a probabilistic model of the relationship
between these two variables.
A model for these variables is given by their joint distribution p(x, t).
In learning problems, this joint distribution is not known, while in
inference problems it is available to design the predictor.

Fall 2024 5 / 108

Defining Inference

In inference problems, we have two types of variables:

▶ input variables x,
▶ and output, or target, variables t.
The general problem in inference is to obtain a predictor of target t
given input x based on a probabilistic model of the relationship
between these two variables.
A model for these variables is given by their joint distribution p(x, t).
In learning problems, this joint distribution is not known, while in
inference problems it is available to design the predictor.

Fall 2024 5 / 108

Defining Inference

Inference can be classified into:

▶ detection problems, in which the target t takes values in a discrete and
finite set,
⋆ e.g., predicting rain vs shine weather;
▶ and estimation problems, in which the target t is continuous,
⋆ e.g., predicting temperature.

Fall 2024 6 / 108

Example: Detection Problem

x = today’s weather (rainy: x = 0; or sunny: x = 1)

t = tomorrow’s weather (rainy: t = 0; or sunny: t = 1)
Suppose that we have a joint distribution p(x, t), which may be
obtained from textbooks, experts, or measurements:

x\t 0 1
0 0.45 0.05
1 0.1 0.4

Using a frequentist interpretation, according to this model, for any

two consecutive days, we have a probability of 45% that they are both
rainy; 40% that they are both sunny; 5% that a rainy day is followed
by a sunny day; and 10% that a sunny day followed by a rainy day.

Fall 2024 7 / 108

Example: Detection Problem

x = today’s weather (rainy: x = 0; or sunny: x = 1)

t = tomorrow’s weather (rainy: t = 0; or sunny: t = 1)
Suppose that we have a joint distribution p(x, t), which may be
obtained from textbooks, experts, or measurements:

x\t 0 1
0 0.45 0.05
1 0.1 0.4

Using a frequentist interpretation, according to this model, for any

two consecutive days, we have a probability of 45% that they are both
rainy; 40% that they are both sunny; 5% that a rainy day is followed
by a sunny day; and 10% that a sunny day followed by a rainy day.

Fall 2024 7 / 108

Defining Inference

The predictor of the target, for both detection and estimation

problems, may be of one of two different types:
▶ a “hard” predictor specifies a single predicted value t̂ of t for every
value of x = x:
⋆ we write t̂(x) for the predictive function mapping input x to predicted
value t;
▶ and a “soft” predictor specifies a “score” for each possible value of t
given x = x,
⋆ we write q(t|x) for the function returning the score of value t for a
given value x.
We will refer to hard predictors also as point predictors; and to the
problem of optimizing a soft predictor also as Bayesian inference.

Fall 2024 8 / 108

Defining Inference

The predictor of the target, for both detection and estimation

problems, may be of one of two different types:
▶ a “hard” predictor specifies a single predicted value t̂ of t for every
value of x = x:
⋆ we write t̂(x) for the predictive function mapping input x to predicted
value t;
▶ and a “soft” predictor specifies a “score” for each possible value of t
given x = x,
⋆ we write q(t|x) for the function returning the score of value t for a
given value x.
We will refer to hard predictors also as point predictors; and to the
problem of optimizing a soft predictor also as Bayesian inference.

Fall 2024 8 / 108

Example

For the weather prediction (detection) example:

▶ A possible hard predictor is:
⋆ when x = 0, predict t̂ = 0;
⋆ and when x = 1 predict t̂ = 1.
⋆ This corresponds to the hard predictive function t̂(x) defined as
t̂(0) = 0 and t̂(1) = 1.
▶ A possible soft predictor is:
⋆ when x = 0, output the distribution (|{z}
0.8 , |{z}
0.2 );
t=0 t=1
⋆ and when x = 1, output the distribution (|{z}
0.3 , |{z}
0.7 ).
t=0 t=1
⋆ This corresponds to the soft predictive function q(t|x) defined as
q(1|0) = 0.2 and q(1|1) = 0.7.

Fall 2024 9 / 108

Example

For the weather prediction (detection) example:

▶ A possible hard predictor is:
⋆ when x = 0, predict t̂ = 0;
⋆ and when x = 1 predict t̂ = 1.
⋆ This corresponds to the hard predictive function t̂(x) defined as
t̂(0) = 0 and t̂(1) = 1.
▶ A possible soft predictor is:
⋆ when x = 0, output the distribution (|{z}
0.8 , |{z}
0.2 );
t=0 t=1
⋆ and when x = 1, output the distribution (|{z}
0.3 , |{z}
0.7 ).
t=0 t=1
⋆ This corresponds to the soft predictive function q(t|x) defined as
q(1|0) = 0.2 and q(1|1) = 0.7.

Fall 2024 9 / 108

Hard vs Soft Prediction

A soft predictor provides more information than a hard predictor:

▶ One can always turn a soft predictor q(t|x) into a hard predictor t̂(x),
e.g., by choosing the value t that has the largest score according to the
soft predictor, i.e., t̂(x) = arg maxt q(t|x).
▶ The scores q(t|x) of all possible values t given input x quantify the
uncertainty associated with any prediction. For instance, if we have
q(1|1) = 0.7 as in the example, the soft predictor assigns a 30%
chance that the prediction t̂ = 1 for x = 1 is incorrect.

Fall 2024 10 / 108

Hard vs Soft Prediction

A soft predictor provides more information than a hard predictor:

▶ One can always turn a soft predictor q(t|x) into a hard predictor t̂(x),
e.g., by choosing the value t that has the largest score according to the
soft predictor, i.e., t̂(x) = arg maxt q(t|x).
▶ The scores q(t|x) of all possible values t given input x quantify the
uncertainty associated with any prediction. For instance, if we have
q(1|1) = 0.7 as in the example, the soft predictor assigns a 30%
chance that the prediction t̂ = 1 for x = 1 is incorrect.

Fall 2024 10 / 108

Optimal Soft Prediction, or Bayesian
Inference

Fall 2024 11 / 108

Optimal Soft Prediction, or Bayesian Inference

A natural choice for the soft predictor q(t|x) of t given x = x is the

posterior distribution p(t|x).
With this choice, the “score” q(t|x) assigned to each value of t is its
posterior probability given x = x.
We will indeed see later that setting q(t|x) = p(t|x) is optimal in a
specific mathematical sense.

Fall 2024 12 / 108

Example

We are given the joint pmf p(x, t)

x\t 0 1
0 0.45 0.05
1 0.1 0.4

The posterior p(t|x) is obtained as

x\t 0 1
0 0.9 0.05/(0.45 + 0.05) = 0.1
1 0.2 0.4/(0.1 + 0.4) = 0.8

Fall 2024 13 / 108

Example

The optimal (Bayesian) soft predictor is hence given as

(t|x = 0) ∼ q(t|0) = p(t|0) = Bern(t|0.1)

and (t|x = 1) ∼ q(t|1) = p(t|1) =Bern(t|0.8)

This can be used to provide the following conclusions:
▶ If x = 0, we can offer the hard prediction t̂(0) = 0 with associated
probability of error of 0.1;
▶ if x = 1, we can offer the hard prediction t̂(1) = 1 with associated
probability of error of 0.2.
In this example, we have chosen the hard predictions that maximize
the posterior probability. How do we formalize and generalize the
optimal design of hard predictors?

Fall 2024 14 / 108

Example

The optimal (Bayesian) soft predictor is hence given as

(t|x = 0) ∼ q(t|0) = p(t|0) = Bern(t|0.1)

and (t|x = 1) ∼ q(t|1) = p(t|1) =Bern(t|0.8)

This can be used to provide the following conclusions:
▶ If x = 0, we can offer the hard prediction t̂(0) = 0 with associated
probability of error of 0.1;
▶ if x = 1, we can offer the hard prediction t̂(1) = 1 with associated
probability of error of 0.2.
In this example, we have chosen the hard predictions that maximize
the posterior probability. How do we formalize and generalize the
optimal design of hard predictors?

Fall 2024 14 / 108

Loss Function and Optimal Hard
Prediction

Fall 2024 15 / 108

Loss Function
To measure the quality of a hard prediction t̂ when the correct value
for the target variable is t, we introduce a loss function

ℓ(t, t̂).

We will assume without loss of generality that the loss function

satisfies the conditions

ℓ(t, t̂) = 0 if t = t̂
and ℓ(t, t̂) ≥ 0

For estimation, we often use the ℓk loss for some integer k ≥ 1, which
is defined as
ℓ(t, t̂) = ℓk (t, t̂) = |t − t̂|k
A typical choice is k = 2, which yields the quadratic error.
Note that the loss function is fixed and not subject to optimization.
Fall 2024 16 / 108
Loss Function
To measure the quality of a hard prediction t̂ when the correct value
for the target variable is t, we introduce a loss function

ℓ(t, t̂).

We will assume without loss of generality that the loss function

satisfies the conditions

ℓ(t, t̂) = 0 if t = t̂
and ℓ(t, t̂) ≥ 0

For estimation, we often use the ℓk loss for some integer k ≥ 1, which
is defined as
ℓ(t, t̂) = ℓk (t, t̂) = |t − t̂|k
A typical choice is k = 2, which yields the quadratic error.
Note that the loss function is fixed and not subject to optimization.
Fall 2024 16 / 108
Loss Function
For detection, a typical choice is the 0-1 loss, also known as detection-error
loss, which is defined as
ℓ(t, t̂) = 1(t ̸= t̂),
where we have introduced the indicator function

1(a) = 01 ifif aa == false
true

One can more generally give different weights to errors {t ̸= t̂}. For
instance, for the weather detection problem, we may set the loss function
ℓ(t, t̂) as

t\t̂ 0 1

0 0 1
1 0.1 0

This indicates that, if it is actually sunny, we don’t care as much that rain
was predicted as we would have on a rainy day if the weather had been
predicted to be sunny.
Fall 2024 17 / 108
Loss Function
For detection, a typical choice is the 0-1 loss, also known as detection-error
loss, which is defined as
ℓ(t, t̂) = 1(t ̸= t̂),
where we have introduced the indicator function

1(a) = 01 ifif aa == false
true

One can more generally give different weights to errors {t ̸= t̂}. For
instance, for the weather detection problem, we may set the loss function
ℓ(t, t̂) as

t\t̂ 0 1

0 0 1
1 0.1 0

This indicates that, if it is actually sunny, we don’t care as much that rain
was predicted as we would have on a rainy day if the weather had been
predicted to be sunny.
Fall 2024 17 / 108
Population Loss

For a given predictor t̂(·), we define the population loss as

Lp (t̂(·)) := E(x,t)∼p(x,t) [ℓ(t, t̂(x))].

The population loss is the average loss over the joint distribution
p(x, t) of input and target, that is, over the “population” of possible
inputs and targets.
Note that we have used the notation t̂(·) to emphasize that the
population loss depends on the entire function t̂(x) obtained by
varying x.
Note also that the subscript “p” stands for “population”.

Fall 2024 18 / 108

Example
For the detection-error loss, under the assumption of discrete rvs x
and t, we have the general formulas

Lp (t̂(·)) := E(x,t)∼p(x,t) [1(t̂(x) ̸= t)]

p(x, t)1(t̂(x) ̸= t)
X
=
x,t
X
= p(x, t)
x,t̸=t̂(x)
X
=1− p(x, t̂(x)).
x
P
In the last expression, the term x p(x, t̂(x)) can be interpreted as
the probability P
of correct detection for predictor t̂(x), and hence
Lp (t̂(·)) = 1 − x p(x, t̂(x)) represents the probability of a detection
error.

Fall 2024 19 / 108

Optimal Hard Predictor

For a given loss function, an optimal hard predictor minimizes the

population loss.
This is expressed as

t̂ ∗ (·) := arg min Lp (t̂(·)) = E(x,t)∼p(x,t) [ℓ(t, t̂(x))] .


t̂(·)

The notation indicates the “argument” that minimizes the function in

the brackets, that is, the minimizer of this function.
Note that there may be multiple optimal hard predictors, in which
case the above notation is meant to indicate one of the optimal
solutions.

Fall 2024 20 / 108

Example
We are given the joint distribution p(x, t):

x\t 0 1
0 0.45 0.05
1 0.1 0.4

Adopting the detection-error loss, compute the population loss for the
hard predictor t̂(0) = 1 and t̂(1) = 1.
We have

Lp (t̂(·)) = 0.45 × 1(t̂(0) ̸= 0) +0.05 × 1(t̂(0) ̸= 1)

| {z } | {z }
=1 =0
+ 0.1 × 1(t̂(1) ̸= 0) +0.4 × 1(t̂(1) ̸= 1) = 0.55
| {z } | {z }
=1 =0

Fall 2024 21 / 108

Example
We are given the joint distribution p(x, t):

x\t 0 1
0 0.45 0.05
1 0.1 0.4

Adopting the detection-error loss, compute the population loss for the
hard predictor t̂(0) = 1 and t̂(1) = 1.
We have

Lp (t̂(·)) = 0.45 × 1(t̂(0) ̸= 0) +0.05 × 1(t̂(0) ̸= 1)

| {z } | {z }
=1 =0
+ 0.1 × 1(t̂(1) ̸= 0) +0.4 × 1(t̂(1) ̸= 1) = 0.55
| {z } | {z }
=1 =0

Fall 2024 21 / 108

Example
What is the optimal hard predictor?
For any predictor t̂(x), we can write

Lp (t̂(·)) = 0.45 × 1(t̂(0) = 1) + 0.05 × 1(t̂(0) = 0)

+ 0.1 × 1(t̂(1) = 1) + 0.4 × 1(t̂(1) = 0)

which we need to optimize over t̂(0) and t̂(1).

To obtain the optimal prediction t̂ ∗ (0), we need to minimize the first
two terms in the population loss, namely
0.45 × 1(t̂(0) = 1) + 0.05 × 1(t̂(0) = 0):
▶ this is obtained for t̂ ∗ (0) = 0 since
p(x = 0, t = 0) = 0.45 > p(x = 0, t = 1) = 0.05.
To obtain the optimal prediction t̂ ∗ (0), we need to minimize the last
two terms, which yields t̂ ∗ (1) = 1 since
p(x = 1, t = 1) = 0.4 > p(x = 1, t = 0) = 0.1.

Fall 2024 22 / 108

Example
What is the optimal hard predictor?
For any predictor t̂(x), we can write

Lp (t̂(·)) = 0.45 × 1(t̂(0) = 1) + 0.05 × 1(t̂(0) = 0)

+ 0.1 × 1(t̂(1) = 1) + 0.4 × 1(t̂(1) = 0)

which we need to optimize over t̂(0) and t̂(1).

To obtain the optimal prediction t̂ ∗ (0), we need to minimize the first
two terms in the population loss, namely
0.45 × 1(t̂(0) = 1) + 0.05 × 1(t̂(0) = 0):
▶ this is obtained for t̂ ∗ (0) = 0 since
p(x = 0, t = 0) = 0.45 > p(x = 0, t = 1) = 0.05.
To obtain the optimal prediction t̂ ∗ (0), we need to minimize the last
two terms, which yields t̂ ∗ (1) = 1 since
p(x = 1, t = 1) = 0.4 > p(x = 1, t = 0) = 0.1.

Fall 2024 22 / 108

Example
What is the optimal hard predictor?
For any predictor t̂(x), we can write

Lp (t̂(·)) = 0.45 × 1(t̂(0) = 1) + 0.05 × 1(t̂(0) = 0)

+ 0.1 × 1(t̂(1) = 1) + 0.4 × 1(t̂(1) = 0)

which we need to optimize over t̂(0) and t̂(1).

To obtain the optimal prediction t̂ ∗ (0), we need to minimize the first
two terms in the population loss, namely
0.45 × 1(t̂(0) = 1) + 0.05 × 1(t̂(0) = 0):
▶ this is obtained for t̂ ∗ (0) = 0 since
p(x = 0, t = 0) = 0.45 > p(x = 0, t = 1) = 0.05.
To obtain the optimal prediction t̂ ∗ (0), we need to minimize the last
two terms, which yields t̂ ∗ (1) = 1 since
p(x = 1, t = 1) = 0.4 > p(x = 1, t = 0) = 0.1.

Fall 2024 22 / 108

Example
What is the optimal hard predictor?
For any predictor t̂(x), we can write

Lp (t̂(·)) = 0.45 × 1(t̂(0) = 1) + 0.05 × 1(t̂(0) = 0)

+ 0.1 × 1(t̂(1) = 1) + 0.4 × 1(t̂(1) = 0)

which we need to optimize over t̂(0) and t̂(1).

To obtain the optimal prediction t̂ ∗ (0), we need to minimize the first
two terms in the population loss, namely
0.45 × 1(t̂(0) = 1) + 0.05 × 1(t̂(0) = 0):
▶ this is obtained for t̂ ∗ (0) = 0 since
p(x = 0, t = 0) = 0.45 > p(x = 0, t = 1) = 0.05.
To obtain the optimal prediction t̂ ∗ (0), we need to minimize the last
two terms, which yields t̂ ∗ (1) = 1 since
p(x = 1, t = 1) = 0.4 > p(x = 1, t = 0) = 0.1.

Fall 2024 22 / 108

Example

The corresponding minimum population loss is

Lp (t̂ ∗ (·)) = 0.05 + 0.1 = 0.15

Fall 2024 23 / 108

Optimal Hard Prediction

Generalizing the example, how do we compute the optimal hard

predictor given a loss function ℓ?
We will see now that, for any given loss function ℓ, the optimal
predictor can be directly computed from the posterior distribution

p(x, t)
p(t|x) =
p(x)

that is, from the optimal soft predictor.

So, knowing the optimal soft predictor p(t|x) allows to obtain the
optimal hard predictor for any loss function.

Fall 2024 24 / 108

Optimal Hard Prediction

Using the law of iterated expectations, the population loss can be

written as
Lp (t̂(·)) = Ex∼p(x) [Et∼p(t|x) [ℓ(t, t̂(x))]].
It follows that the optimal hard prediction t̂ ∗ (x) for any given value x
can be obtained by minimizing the inner expectation as

t̂ ∗ (x) = arg min Et∼p(t|x) [ℓ(t, t̂)].

t̂

So, the optimal hard prediction can be computed separately for each
value x and it is a function of the corresponding optimal soft
predictor p(t|x).

Fall 2024 25 / 108

Example
Let’s apply this general formula to the example seen above for which
the posterior distribution p(t|x) is
x\t 0 1
0 0.9 0.1
1 0.2 0.8
Under the detection-error loss, the optimal prediction t̂ ∗ (0) is hence
given as t̂ ∗ (0) = arg mint̂ Et∼p(t|0) [1(t ̸= t̂)], where we have
Et∼p(t|0) [1(t ̸= t̂)] = 0.9 × 1(t̂ ̸= 0) + 0.1 × 1(t̂ ̸= 1).
Therefore, the optimal prediction is t̂ ∗ (0) = 0, which yields
Et∼p(t|0) [1(t ̸= 0)] = 0.1.
Note that the conditional average detection-error loss is the
probability of error conditioned on x = 0.
In a similar way, we have t̂ ∗ (1) = 1, which yields
Et∼p(t|1) [1(t ̸= 1)] = 0.2.
Fall 2024 26 / 108
Example
Let’s apply this general formula to the example seen above for which
the posterior distribution p(t|x) is
x\t 0 1
0 0.9 0.1
1 0.2 0.8
Under the detection-error loss, the optimal prediction t̂ ∗ (0) is hence
given as t̂ ∗ (0) = arg mint̂ Et∼p(t|0) [1(t ̸= t̂)], where we have
Et∼p(t|0) [1(t ̸= t̂)] = 0.9 × 1(t̂ ̸= 0) + 0.1 × 1(t̂ ̸= 1).
Therefore, the optimal prediction is t̂ ∗ (0) = 0, which yields
Et∼p(t|0) [1(t ̸= 0)] = 0.1.
Note that the conditional average detection-error loss is the
probability of error conditioned on x = 0.
In a similar way, we have t̂ ∗ (1) = 1, which yields
Et∼p(t|1) [1(t ̸= 1)] = 0.2.
Fall 2024 26 / 108
When x And t Are Independent

As a special case, suppose that x and t are independent, i.e.,

p(x, t) = p(x)p(t). What is the optimal predictor of t given x?
In this case, using x to predict t is not useful since the posterior
distribution equals the marginal, that is,

p(x, t) p(x)p(t)
p(t|x) = = = p(t),
p(x) p(x)

and the only information we have about t is its distribution p(t).

Therefore, the optimal predictor is a constant t̂ ∗ that does not
depend on the value of x, i.e.,

t̂ ∗ = arg min Lp (t̂) = Et∼p(t) [ℓ(t, t̂)] .


t̂

Fall 2024 27 / 108

When x And t Are Independent

As a special case, suppose that x and t are independent, i.e.,

p(x, t) = p(x)p(t). What is the optimal predictor of t given x?
In this case, using x to predict t is not useful since the posterior
distribution equals the marginal, that is,

p(x, t) p(x)p(t)
p(t|x) = = = p(t),
p(x) p(x)

and the only information we have about t is its distribution p(t).

Therefore, the optimal predictor is a constant t̂ ∗ that does not
depend on the value of x, i.e.,

t̂ ∗ = arg min Lp (t̂) = Et∼p(t) [ℓ(t, t̂)] .


t̂

Fall 2024 27 / 108

Example: Optimal Hard Prediction Under ℓ2 Loss

Under the ℓ2 (quadratic) loss, when x and t are independent, we

have:
▶ the optimal hard predictor is the mean

t̂ ∗ = arg min Lp (t̂) = Et∼p(t) [(t − t̂)2 ] = Et∼p(t) [t];


t̂

▶ and the minimum population loss is the variance

Lp (t̂ ∗ ) = Et∼p(t) [(t − t̂ ∗ )2 ]

= Et∼p(t) [(t − Et∼p(t) [t])2 ]
= Var(t).

Proof: Take the derivative of the population loss and equate it to

zero.

Fall 2024 28 / 108

Example: Optimal Hard Prediction Under ℓ2 Loss
Under the ℓ2 (quadratic) loss, in the more general case in which x
and t are dependent, we have
▶ the optimal hard predictor is the posterior mean, that is, the mean of
the posterior distribution

t̂ ∗ (x) = Et∼p(t|x) [t];

▶ and the minimum population loss is the average posterior variance

Lp (t̂ ∗ (·)) = E(x,t)∼p(x,t) [(t − t̂ ∗ (x))2 ]

= E(x,t)∼p(x,t) [(t − Et∼p(t|x) [t])2 ]
= Ex∼p(x) [Et∼p(t|x) [(t − Et∼p(t|x) [t])2 ]]
| {z }
:=Var(t|x)

= Ex∼p(x) [Var(t|x)],

where we have used the law of iterated expectations

Proof: Take the derivative of the population loss and equate it to
zero.
Fall 2024 29 / 108
Example: Optimal Hard Prediction Under Detection-Error
Loss
Under the detection-error loss, we have:
▶ the optimal predictor is the maximum of the posterior distribution, i.e.,
the posterior mode
t̂ ∗ (x) = arg max p(t|x),
t

which is also referred to as maximum a posterior (MAP) predictor;

▶ and the minimum population loss is the minimum probability of error

Lp (t̂ ∗ (·)) = E(x,t)∼p(x,t) [1(t ̸= t̂ ∗ (x))]

= Ex∼p(x) [Et∼p(t|x) [1(t ̸= t̂ ∗ (x))]]
 
X
= Ex∼p(x)  p(t|x)
t̸=t̂ ∗ (x)

= 1 − Ex∼p(x) p(t̂ ∗ (x)|x)

 
h i
= 1 − Ex∼p(x) max p(t|x)
t

Fall 2024 30 / 108

Example
With the posterior distribution p(t|x) below, compute the optimal
hard predictor t̂(0) under the ℓ2 and the detection-error losses.

x\t 0 1
0 0.9 0.1
1 0.2 0.8

Under the quadratic loss, we need to compute the posterior mean

t̂ ∗ (0) = 0.9 × 0 + 0.1 × 1 = 0.1

While, under the detection-error loss, we need to compute the MAP

predictor
t̂ ∗ (0) = 0
Repeat for x = 1 and compute the minimum average loss.
Fall 2024 31 / 108
Example
With the posterior distribution p(t|x) below, compute the optimal
hard predictor t̂(0) under the ℓ2 and the detection-error losses.

x\t 0 1
0 0.9 0.1
1 0.2 0.8

Under the quadratic loss, we need to compute the posterior mean

t̂ ∗ (0) = 0.9 × 0 + 0.1 × 1 = 0.1

While, under the detection-error loss, we need to compute the MAP

predictor
t̂ ∗ (0) = 0
Repeat for x = 1 and compute the minimum average loss.
Fall 2024 31 / 108
Example: Optimal Prediction With Jointly Gaussian
Variables

We now consider an estimation problem in which we observe a noisy

version x of a Gaussian variable t, and we would like to estimate t
using a soft or a hard predictor.
Accordingly, we assume a joint distribution p(x, t) = p(t)p(x|t) that
is defined by
▶ prior t ∼ N (ν, α−1 ), where α represents the “precision” of the prior
knowledge on t;
▶ and likelihood of the noisy observation (x|t = t) ∼ N (t, β −1 ), which
can be equivalently described as

x = t + z, with z ∼ N (0, β −1 ),

where the noise z is independent of t, and β is the precision of the

observation.

Fall 2024 32 / 108

Example: Optimal Prediction With Jointly Gaussian
Variables

We now consider an estimation problem in which we observe a noisy

version x of a Gaussian variable t, and we would like to estimate t
using a soft or a hard predictor.
Accordingly, we assume a joint distribution p(x, t) = p(t)p(x|t) that
is defined by
▶ prior t ∼ N (ν, α−1 ), where α represents the “precision” of the prior
knowledge on t;
▶ and likelihood of the noisy observation (x|t = t) ∼ N (t, β −1 ), which
can be equivalently described as

x = t + z, with z ∼ N (0, β −1 ),

where the noise z is independent of t, and β is the precision of the

observation.

Fall 2024 32 / 108

Example: Optimal Prediction With Jointly Gaussian
Variables

We now consider an estimation problem in which we observe a noisy

version x of a Gaussian variable t, and we would like to estimate t
using a soft or a hard predictor.
Accordingly, we assume a joint distribution p(x, t) = p(t)p(x|t) that
is defined by
▶ prior t ∼ N (ν, α−1 ), where α represents the “precision” of the prior
knowledge on t;
▶ and likelihood of the noisy observation (x|t = t) ∼ N (t, β −1 ), which
can be equivalently described as

x = t + z, with z ∼ N (0, β −1 ),

where the noise z is independent of t, and β is the precision of the

observation.

Fall 2024 32 / 108

Example: Optimal Prediction With Jointly Gaussian
Variables
In a manner similar to computation seen in the previous chapter, the
optimal soft predictor, that is, the posterior distribution for these
jointly Gaussian variables is given as
 
αν + βx 1
p(t|x) = N t ,
α+β α+β
Note that the precision of the posterior is the sum of the precisions of
prior and likelihood.
Note also that, if α is much larger than β, i.e., if the precision of the
prior is much larger than that of the observation, we have
p(t|x) ≃ N (t|ν, α−1 ) = p(t), and hence the observation x is
discarded.
Vice versa, if β is much larger than α, i.e., if the precision of the
observation is much larger than that of the prior, we have
p(t|x) ≃ N (t|x, β −1 ), and hence the prior is discarded.
Fall 2024 33 / 108
Example: Optimal Prediction With Jointly Gaussian
Variables
In a manner similar to computation seen in the previous chapter, the
optimal soft predictor, that is, the posterior distribution for these
jointly Gaussian variables is given as
 
αν + βx 1
p(t|x) = N t ,
α+β α+β
Note that the precision of the posterior is the sum of the precisions of
prior and likelihood.
Note also that, if α is much larger than β, i.e., if the precision of the
prior is much larger than that of the observation, we have
p(t|x) ≃ N (t|ν, α−1 ) = p(t), and hence the observation x is
discarded.
Vice versa, if β is much larger than α, i.e., if the precision of the
observation is much larger than that of the prior, we have
p(t|x) ≃ N (t|x, β −1 ), and hence the prior is discarded.
Fall 2024 33 / 108
Example: Optimal Prediction With Jointly Gaussian
Variables
In a manner similar to computation seen in the previous chapter, the
optimal soft predictor, that is, the posterior distribution for these
jointly Gaussian variables is given as
 
αν + βx 1
p(t|x) = N t ,
α+β α+β
Note that the precision of the posterior is the sum of the precisions of
prior and likelihood.
Note also that, if α is much larger than β, i.e., if the precision of the
prior is much larger than that of the observation, we have
p(t|x) ≃ N (t|ν, α−1 ) = p(t), and hence the observation x is
discarded.
Vice versa, if β is much larger than α, i.e., if the precision of the
observation is much larger than that of the prior, we have
p(t|x) ≃ N (t|x, β −1 ), and hence the prior is discarded.
Fall 2024 33 / 108
Example: Optimal Prediction With Jointly Gaussian
Variables

0
0 1 2 3 4 5 6

Fall 2024 34 / 108

Example: Optimal Prediction With Jointly Gaussian
Variables

0
0 1 2 3 4 5 6

Fall 2024 35 / 108

Example: Optimal Prediction With Jointly Gaussian
Variables

star: x = 4, dashed line: prior, solid line: posterior

0
1.5 2 2.5 3 3.5 4 4.5

0
1.5 2 2.5 3 3.5 4 4.5

0
1.5 2 2.5 3 3.5 4 4.5

Fall 2024 36 / 108

Example: Optimal Prediction With Jointly Gaussian
Variables

Under the ℓ2 loss, the optimal hard predictor is given by the posterior
mean
αν + βx
t̂ ∗ (x) = .
α+β
And the minimum population loss is given by the average conditional
variance
1
Ex∼p(x) [Var(t|x)] = Var(t|x) = .
α+β
Note that, for this example, the conditional variance is the same for
every value x, which is not the case in general.

Fall 2024 37 / 108

Example: Optimal Prediction With Jointly Gaussian
Vectors
We now consider an estimation problem in which we observe an
M × 1 vector x, that provides a noisy measure of an L × 1 jointly
Gaussian vector t, and we would like to estimate t using a soft or a
hard predictor.
Accordingly, we assume a joint distribution p(x, t) = p(t)p(x|t) that
is defined by
▶ prior t ∼ N (ν, α−1 IL ), where α represents the precision of the prior
knowledge on t. Note that this choice assumes that the entries of the
target vector t are a prior independent;
▶ and likelihood of the noisy observation (x|t = t) ∼ N (At, β −1 IM ),
which can be equivalently described as
x = At + z, with z ∼ N (0, β −1 IM ),
where the noise z is independent of t, A is an M × L matrix, and β is
the precision of the observation.
This model accounts for many real-world applications, such as the
cocktail party problem, equalization of a communication system, ...
Fall 2024 38 / 108
Example: Optimal Prediction With Jointly Gaussian
Vectors
We now consider an estimation problem in which we observe an
M × 1 vector x, that provides a noisy measure of an L × 1 jointly
Gaussian vector t, and we would like to estimate t using a soft or a
hard predictor.
Accordingly, we assume a joint distribution p(x, t) = p(t)p(x|t) that
is defined by
▶ prior t ∼ N (ν, α−1 IL ), where α represents the precision of the prior
knowledge on t. Note that this choice assumes that the entries of the
target vector t are a prior independent;
▶ and likelihood of the noisy observation (x|t = t) ∼ N (At, β −1 IM ),
which can be equivalently described as
x = At + z, with z ∼ N (0, β −1 IM ),
where the noise z is independent of t, A is an M × L matrix, and β is
the precision of the observation.
This model accounts for many real-world applications, such as the
cocktail party problem, equalization of a communication system, ...
Fall 2024 38 / 108
Example: Optimal Prediction With Jointly Gaussian
Variables

Generalizing the previous example, the optimal soft predictor, that is,
the posterior distribution can be computed as

p(t|x) = N (Θ−1 (αν + βAT x), Θ−1 ),

where
Θ = αIL + βAT A
is the precision matrix of the posterior.
Note that this reduces to the posterior seen in the previous example if
all quantities are scalar. Therefore, the same general considerations
apply.

Fall 2024 39 / 108

Example: Optimal Prediction With Jointly Gaussian
Variables

     
1 10 0 25
Set ν = , α = 1, A = , β = 2, and x = , and
1 0 1 2
compute optimal soft predictor, as well as the optimal hard predictors
under the ℓ2 loss.

Fall 2024 40 / 108

Example
 
100 0
We compute AT A = and
0 1
 
25
▶ posterior t x = ∼
2
 
 
 
       
 1/201 0 1 500 1/201 0
 
N + ,

0 1/3 1 4 0 1/3 


| {z } 
   


501/201 = 2.5  
5/3 = 1.7
   
25 2.5
▶ optimal hard predictor: posterior mean t̂ =
2 1.7

Fall 2024 41 / 108

Example
 
100 0
We compute AT A = and
0 1
 
25
▶ posterior t x = ∼
2
 
 
 
       
 1/201 0 1 500 1/201 0
 
N + ,

0 1/3 1 4 0 1/3 


| {z } 
   


501/201 = 2.5  
5/3 = 1.7
   
25 2.5
▶ optimal hard predictor: posterior mean t̂ =
2 1.7

Fall 2024 41 / 108

 KL Divergence

Fall 2024 42 / 108

Log-Likelihood Ratio

Consider two distributions p(t) and q(t). How different are they?
Define the Log-Likelihood Ratio (LLR)
 
p(t)
log
q(t)

▶ The LLR is large in magnitude for values of t at which the two

distributions differ more significantly.
▶ The LLR equals zero only for values of t at which the two distributions
are equal.

Fall 2024 43 / 108

Log-Likelihood Ratio

Consider two distributions p(t) and q(t). How different are they?
Define the Log-Likelihood Ratio (LLR)
 
p(t)
log
q(t)

▶ The LLR is large in magnitude for values of t at which the two

distributions differ more significantly.
▶ The LLR equals zero only for values of t at which the two distributions
are equal.

Fall 2024 43 / 108

Example

For p(t) = N (t| − 1, 1) and q(t) = N (t|1, 1), the distributions and
the LLR are illustrated in the figure.

0.5

0.4

0.3

0.2

0.1

-0.1

-0.2
-4 -3 -2 -1 0 1 2 3 4

Fall 2024 44 / 108

KL Divergence
The KL divergence between two distributions p and q is defined as
the average value of the LLR with respect to distribution p, i.e.,
  
p(t)
KL(p∥q) = Et∼p(t) log .
q(t)

If the LLR is small on average, then the KL divergence is small, and

vice versa.
The KL divergence is measured in natural units of information (nats).
If we substituted the natural log with the log in base 2, the KL
divergence would be measured in bits. We can compute the KL
divergence in bits from the KL divergence in nats as

KL(p∥q) [bits] = log2 (e) · (KL(p∥q) [nats])

=1.44 · (KL(p∥q) [nats]).

Fall 2024 45 / 108

KL Divergence
The KL divergence between two distributions p and q is defined as
the average value of the LLR with respect to distribution p, i.e.,
  
p(t)
KL(p∥q) = Et∼p(t) log .
q(t)

If the LLR is small on average, then the KL divergence is small, and

vice versa.
The KL divergence is measured in natural units of information (nats).
If we substituted the natural log with the log in base 2, the KL
divergence would be measured in bits. We can compute the KL
divergence in bits from the KL divergence in nats as

KL(p∥q) [bits] = log2 (e) · (KL(p∥q) [nats])

=1.44 · (KL(p∥q) [nats]).

Fall 2024 45 / 108

KL Divergence

The KL divergence is generally asymmetric, i.e., we have the

inequality KL(p∥q) ̸= KL(q∥p).
Furthermore, as suggested by the figure, since we are averaging over
p(t), we expect KL(p∥q) to be non-negative (to be proved rigorously
later).
As a technical, but important, notes, we first observe
 that, when
p(t)
p(t) = 0, we take the corresponding term p(t) log q(t) that appears
in the KL to be also zero. This follows by taking the limit p(t) → 0.
Furthermore, the KL divergence is well defined only when, for all
values of t for which q(t) = 0, we also have
 p(t) = 0. In this case,
p(t)
we take the corresponding term p(t) log q(t) to equal zero.

Fall 2024 46 / 108

Example
For the distributions p(t) = Bern(t|p) and q(t) = Bern(t|q), the KL
divergence is
   
p 1−p
KL(p||q) = p log + (1 − p) log
q 1−q

2.5

1.5

0.5

0
0 0.2 0.4 0.6 0.8 1

Fall 2024 47 / 108

Example

For p(t) = N (t|µ1 , σ12 ) and q(t) = N (t|µ2 , σ22 ), the KL divergence is

1 σ12 (µ1 − µ2 )2
  2 
σ2
KL(p∥q) = + − 1 + log .
2 σ22 σ22 σ12

It hence depends on differences in both means and variances.

In the special case σ12 = σ22 = σ 2 , we have

1 (µ1 − µ2 )2
KL(p∥q) = .
2 σ2

Fall 2024 48 / 108

Example

The figure shows the two KL divergences KL(N (µ, 1)||N (µ, σ 2 )) and
KL(N (µ, σ 2 )||N (µ, 1)) for any mean µ as a function of the variance
σ2.

1.8

1.6

1.4

1.2

0.8

0.6

0.4

0.2

0
0 0.5 1 1.5 2 2.5 3

Fall 2024 49 / 108

Example

Thinking of distribution N (µ, 1) as being fixed and as distribution

N (µ, σ 2 ) as being an approximation of N (µ, 1), we can make the
following observations:
▶ The KL divergence KL(N (µ, 1)||N (µ, σ 2 )) penalizes more significantly
approximations N (µ, σ 2 ) that do not cover the given distribution
N (µ, 1), i.e., approximations N (µ, σ 2 ) with small values of σ 2 ;
▶ In contrast, the KL divergence KL(N (µ, σ 2 )||N (µ, 1)) “prefers”
approximations N (µ, σ 2 ) that capture the main peak of the given
distribution N (µ, 1), while not being too spread out.
This suggests that using either divergence in machine learning
problems leads to trained models with different properties in terms of
their capacity to match the data distribution.

Fall 2024 50 / 108

Example

Thinking of distribution N (µ, 1) as being fixed and as distribution

N (µ, σ 2 ) as being an approximation of N (µ, 1), we can make the
following observations:
▶ The KL divergence KL(N (µ, 1)||N (µ, σ 2 )) penalizes more significantly
approximations N (µ, σ 2 ) that do not cover the given distribution
N (µ, 1), i.e., approximations N (µ, σ 2 ) with small values of σ 2 ;
▶ In contrast, the KL divergence KL(N (µ, σ 2 )||N (µ, 1)) “prefers”
approximations N (µ, σ 2 ) that capture the main peak of the given
distribution N (µ, 1), while not being too spread out.
This suggests that using either divergence in machine learning
problems leads to trained models with different properties in terms of
their capacity to match the data distribution.

Fall 2024 50 / 108

Gibbs Inequality

The KL divergence can be taken as a measure of distance between

two distributions.
To this end, we need to prove that the KL divergence is positive for
any pair of non-identical p and q and that it is zero if the two
distributions are identical.
This is stated by Gibbs inequality

KL(p∥q) ≥ 0,

where KL(p∥q) = 0 if and only if the two distributions p and q are

identical.
Proof: See Appendix.

Fall 2024 51 / 108

Gibbs Inequality

The KL divergence can be taken as a measure of distance between

two distributions.
To this end, we need to prove that the KL divergence is positive for
any pair of non-identical p and q and that it is zero if the two
distributions are identical.
This is stated by Gibbs inequality

KL(p∥q) ≥ 0,

where KL(p∥q) = 0 if and only if the two distributions p and q are

identical.
Proof: See Appendix.

Fall 2024 51 / 108

Cross Entropy

Finally, the KL divergence can be expressed as a function of an

important quantity, the cross entropy between distributions p and q

H(p, q) := Et∼p(t) [− log q(t)].

In fact, we have the equality

KL(p∥q) = Et∼p(t) [− log q(t)] − Et∼p(t) [− log p(t)]

= H(p, q) − H(p, p).

We will see next that the cross entropy is an information-theoretic

measure of how well q(t) serves as a soft predictor for an rv t ∼ p(t).

Fall 2024 52 / 108

Optimal Soft Prediction Revisited

Fall 2024 53 / 108

Optimal Soft Prediction?

We said that the posterior distribution p(t|x) is the optimal soft

predictor q(t|x) – but what does this mean exactly?
We know that optimal hard predictor for any loss function can be
directly computed from p(t|x). So, in this sense, the posterior is a
“universal” optimal predictor.
But can we obtain the posterior directly as the minimizer of a
population loss as we did for hard predictors?

Fall 2024 54 / 108

Optimal Soft Prediction?

We said that the posterior distribution p(t|x) is the optimal soft

predictor q(t|x) – but what does this mean exactly?
We know that optimal hard predictor for any loss function can be
directly computed from p(t|x). So, in this sense, the posterior is a
“universal” optimal predictor.
But can we obtain the posterior directly as the minimizer of a
population loss as we did for hard predictors?

Fall 2024 54 / 108

Log-Loss, or Cross-Entropy Loss

To address this question, consider the use of a generic predictive

distribution q(t|x) – not necessarily the posterior p(t|x).
Can we optimize over q(t|x) to define an optimal soft predictor?
To this end, we need to measure the loss of the soft predictor q(t|x)
on a pair (x, t).
This can be done by using the log-loss, also known as cross-entropy
loss — a key concept in machine learning:
▶ the log-loss, or cross-entropy loss, for a soft predictor q(t|x) on a pair
(x, t) is defined as
−logq(t|x)

Fall 2024 55 / 108

Log-Loss, or Cross-Entropy Loss

To address this question, consider the use of a generic predictive

distribution q(t|x) – not necessarily the posterior p(t|x).
Can we optimize over q(t|x) to define an optimal soft predictor?
To this end, we need to measure the loss of the soft predictor q(t|x)
on a pair (x, t).
This can be done by using the log-loss, also known as cross-entropy
loss — a key concept in machine learning:
▶ the log-loss, or cross-entropy loss, for a soft predictor q(t|x) on a pair
(x, t) is defined as
−logq(t|x)

Fall 2024 55 / 108

Log-Loss, or Cross-Entropy Loss
The plot refers to a discrete rv t, i.e., to a detection problem, for
which the score q(t|x) is in the interval [0, 1].

4.5

3.5

2.5

1.5

0.5

0
0 0.2 0.4 0.6 0.8 1

Fall 2024 56 / 108

Log-Loss, or Cross-Entropy Loss
The log-loss − log q(t|x)
▶ is large if the predictor gives low probability to the correct output t
given x;
▶ and is small if the predictor gives high probability to the correct output
t given x.
In information theory, the log-loss − log q(t|x) measures the
“surprise” experienced by the predictor when observing t = t given
x=x
▶ the suprise is higher if the output is less expected (i.e., predicted with
lower probability).
It can also be interpreted from an operational perspective as the
minimum number of bits – when the logarithm is in base 2 – needed
to compress the label t when x is known.
There are other, less used, measures of loss for a soft predictor, which
are collectively known as scoring rules.

Fall 2024 57 / 108

Log-Loss, or Cross-Entropy Loss
The log-loss − log q(t|x)
▶ is large if the predictor gives low probability to the correct output t
given x;
▶ and is small if the predictor gives high probability to the correct output
t given x.
In information theory, the log-loss − log q(t|x) measures the
“surprise” experienced by the predictor when observing t = t given
x=x
▶ the suprise is higher if the output is less expected (i.e., predicted with
lower probability).
It can also be interpreted from an operational perspective as the
minimum number of bits – when the logarithm is in base 2 – needed
to compress the label t when x is known.
There are other, less used, measures of loss for a soft predictor, which
are collectively known as scoring rules.

Fall 2024 57 / 108

Log-Loss, or Cross-Entropy Loss
The log-loss − log q(t|x)
▶ is large if the predictor gives low probability to the correct output t
given x;
▶ and is small if the predictor gives high probability to the correct output
t given x.
In information theory, the log-loss − log q(t|x) measures the
“surprise” experienced by the predictor when observing t = t given
x=x
▶ the suprise is higher if the output is less expected (i.e., predicted with
lower probability).
It can also be interpreted from an operational perspective as the
minimum number of bits – when the logarithm is in base 2 – needed
to compress the label t when x is known.
There are other, less used, measures of loss for a soft predictor, which
are collectively known as scoring rules.

Fall 2024 57 / 108

Log-Loss, or Cross-Entropy Loss
The log-loss − log q(t|x)
▶ is large if the predictor gives low probability to the correct output t
given x;
▶ and is small if the predictor gives high probability to the correct output
t given x.
In information theory, the log-loss − log q(t|x) measures the
“surprise” experienced by the predictor when observing t = t given
x=x
▶ the suprise is higher if the output is less expected (i.e., predicted with
lower probability).
It can also be interpreted from an operational perspective as the
minimum number of bits – when the logarithm is in base 2 – needed
to compress the label t when x is known.
There are other, less used, measures of loss for a soft predictor, which
are collectively known as scoring rules.

Fall 2024 57 / 108

Log-Loss, or Cross-Entropy Loss

If t is a discrete rv, i.e., if we have a detection problem, the score q(t|x) is

constrained in the interval [0, 1].
Therefore, the log-loss − log q(t|x) is always non-negative: we have the
inequality − log q(t|x) ≥ 0 with equality − log q(t|x) = 0 if and only if
q(t|x) = 1.
Moreover, we have a zero log-loss only for values of t that are assigned the
maximum score q(t|x) = 1.
For a continuous rv t, i.e., for an estimation problem, the score q(t|x) is
non-negative, and it can be larger than 1. Think for instance of a Gaussian
soft predictor – the Gaussian pdf can take values larger than 1.
Therefore, the log-loss − log q(t|x) can be negative when t is continuous.
Note that this is not an issue, since the log-loss is used to compare different
predictors, and hence what matters is the difference between log-losses.

Fall 2024 58 / 108

Log-Loss, or Cross-Entropy Loss

If t is a discrete rv, i.e., if we have a detection problem, the score q(t|x) is

constrained in the interval [0, 1].
Therefore, the log-loss − log q(t|x) is always non-negative: we have the
inequality − log q(t|x) ≥ 0 with equality − log q(t|x) = 0 if and only if
q(t|x) = 1.
Moreover, we have a zero log-loss only for values of t that are assigned the
maximum score q(t|x) = 1.
For a continuous rv t, i.e., for an estimation problem, the score q(t|x) is
non-negative, and it can be larger than 1. Think for instance of a Gaussian
soft predictor – the Gaussian pdf can take values larger than 1.
Therefore, the log-loss − log q(t|x) can be negative when t is continuous.
Note that this is not an issue, since the log-loss is used to compare different
predictors, and hence what matters is the difference between log-losses.

Fall 2024 58 / 108

Population Log-Loss

Following the approach taken to define optimal hard predictors, an

optimal soft predictor can then be obtained by minimizing the
population log-loss, or population cross-entropy loss

min Lp (q(·|·)) = E(x,t)∼p(x,t) [− log q(t|x)] .
q(·|·)

Note that we are using the notation q(·|·) to indicate that the
population loss depends on the entire soft predictor q(t|x) obtained
by considering all values of x and t.

Fall 2024 59 / 108

Optimal Soft Prediction

What is the soft predictor that minimizes the population

cross-entropy loss?
To proceed, let us first consider the simpler case in which x and t are
independent, and hence the only information we have about t is its
distribution p(t):
▶ in this case, we are interested in determining a soft predictor q(t);
▶ and it will be easy to extend the results to the case in which the soft
predictor q(t|x) depends on x.

Fall 2024 60 / 108

Optimal Soft Prediction
The problem we are interested in is the minimization of the
population log-loss

min Lp (q(·)) = Et∼p(t) [− log q(t)] .
q(·)

Using the definition seen above, the population log-loss is also known
as the cross entropy between p(t) and q(t), i.e.,

Lp (q(·)) = H(p, q).

By Gibbs inequality, we have

KL(p∥q) = H(p, q) − H(p, p) ≥ 0

or H(p, q) ≥ H(p, p) with equality if p = q.

This demonstrates that the minimum population log-loss is attained
when q = p, and hence q ∗ (t) = p(t) is the optimal soft predictor.
Fall 2024 61 / 108
Optimal Soft Prediction
The problem we are interested in is the minimization of the
population log-loss

min Lp (q(·)) = Et∼p(t) [− log q(t)] .
q(·)

Using the definition seen above, the population log-loss is also known
as the cross entropy between p(t) and q(t), i.e.,

Lp (q(·)) = H(p, q).

By Gibbs inequality, we have

KL(p∥q) = H(p, q) − H(p, p) ≥ 0

or H(p, q) ≥ H(p, p) with equality if p = q.

This demonstrates that the minimum population log-loss is attained
when q = p, and hence q ∗ (t) = p(t) is the optimal soft predictor.
Fall 2024 61 / 108
Example

Consider the distribution t∼p(t) = Bern(t|0.7) and assume that the soft
predictor q(t) = Bern(t|0.5) is used. Compute the population log-loss
Lp (q(·)), i.e., the cross entropy H(p(t), q(t)).
The cross entropy is given as

H(p, q) = 0.7 · (− log(0.5)) + 0.3 · (− log(0.5)) = 0.69 (nats)

Fall 2024 62 / 108

Example

Consider the distribution t∼p(t) = Bern(t|0.7) and assume that the soft
predictor q(t) = Bern(t|0.5) is used. Compute the population log-loss
Lp (q(·)), i.e., the cross entropy H(p(t), q(t)).
The cross entropy is given as

H(p, q) = 0.7 · (− log(0.5)) + 0.3 · (− log(0.5)) = 0.69 (nats)

Fall 2024 62 / 108

Example

What would be the cross entropy if we used the optimal soft predictor
q(t) = p(t)?
We have

H(p, p) = 0.7 · (− log(0.7)) + 0.3 · (− log(0.3)) = 0.61 (nats)

Fall 2024 63 / 108

Example

What would be the cross entropy if we used the optimal soft predictor
q(t) = p(t)?
We have

H(p, p) = 0.7 · (− log(0.7)) + 0.3 · (− log(0.3)) = 0.61 (nats)

Fall 2024 63 / 108

Entropy

The minimum cross entropy is

min H(p, q) = H(p, p) =: H(p),

q(·)

which is known as the entropy of rv t ∼ p(t).

The entropy

H(p) = H(t) = Et∼p(t) [− log p(t)]

measures the population log-loss that we obtain when we use the

optimal soft predictor, and is hence a measure of irreducible
uncertainty for rv t ∼ p(t).
Note that the entropy is also written as H(t) if the distribution of t is
clear from the context.

Fall 2024 64 / 108

KL Divergence, Cross-Entropy, and Entropy

Finally, note that the KL divergence can be expressed as

KL(p∥q) = H(p, q) − H(p)

and hence it measures the excess population log-loss we incur if we

use the generally suboptimal soft predictor q as compared to the
optimal predictor p:
▶ it is a measure not of loss but of “regret”, or excess loss.

Fall 2024 65 / 108

Differential Entropy

As a remark, for continuous rvs, one should more correctly talk about
differential entropy, but we won’t use this distinct terminology here in
order to allow a unified presentation (see Appendix for some key
difference between entropy and differential entropy).
It is useful to know that the (differential) entropy for a Gaussian rv
t ∼ N (µ, σ 2 ) is

1
H(t) = H(N (µ, σ 2 )) = log(2πeσ 2 ),
2
and hence the entropy of a Gaussian rv is independent of the mean
and increases with the variance α−1 .

Fall 2024 66 / 108

To Recap

To summarize the discussion so far, for the special case in which we

only know the distribution p(t), we have seen that:
▶ the soft optimal predictor q(t) that minimizes the population log-loss,
also known as cross entropy H(p, q), is given by q ∗ (t) = p(t);
▶ the minimum cross entropy is given by the entropy H(p) = H(p, p);
▶ the difference between cross entropy and entropy is the KL divergence

KL(p∥q) = H(p, q) − H(p) ≥ 0,

which is an asymmetric measure of distance between p and q.

Fall 2024 67 / 108

Optimal Soft Predictor

Let’s now go back to our original problem of evaluating the optimal

soft predictor by solving the problem of minimizing the population
log-loss

min Lp (q(·|·)) = E(x,t)∼p(x,t) [− log q(t|x)] .
q(·|·)

In a manner similar to what we have done for hard predictors, using

the law of iterated expectations, we can write the population log-loss
as
Lp (q(·|·)) = Ex∼p(x) [ Et∼p(t|x) [− log q(t|x)] ].
| {z }
=H(p(t|x),q(t|x)) cross entropy

Note that the cross entropy H(p(t|x), q(t|x)) is between distributions

p(t|x) and q(t|x) for a fixed value of x.

Fall 2024 68 / 108

Optimal Soft Predictor

Let’s now go back to our original problem of evaluating the optimal

soft predictor by solving the problem of minimizing the population
log-loss

min Lp (q(·|·)) = E(x,t)∼p(x,t) [− log q(t|x)] .
q(·|·)

In a manner similar to what we have done for hard predictors, using

the law of iterated expectations, we can write the population log-loss
as
Lp (q(·|·)) = Ex∼p(x) [ Et∼p(t|x) [− log q(t|x)] ].
| {z }
=H(p(t|x),q(t|x)) cross entropy

Note that the cross entropy H(p(t|x), q(t|x)) is between distributions

p(t|x) and q(t|x) for a fixed value of x.

Fall 2024 68 / 108

Optimal Soft Predictor

The optimal soft predictor can be hence obtained for each value of x
by minimizing the cross entropy

q ∗ (·|x) = arg min H(p(t|x), q(t|x)).

q(·|x)

And we know from the analysis above that this yields the optimal soft
predictor
q ∗ (t|x) = p(t|x).
We conclude that indeed the posterior distribution is the optimal soft
predictor under the log-loss.

Fall 2024 69 / 108

Conditional Entropy

Furthermore, the minimum population log-loss is given as

Lp (p(·|·)) = Ex∼p(x) [Et∼p(t|x) [− log p(t|x)]]

| {z }
entropy H(p(t|x))

The quantity Lp (p(·|·)) is known as conditional entropy of t given x.

When the joint distribution p(x, t) is clear from the context, we can
write the conditional entropy as

H(t|x) = E(x,t)∼p(x,t) [− log p(t|x)].

Since it measures the minimum cross entropy for any possible soft
predictor, the conditional entropy measures how difficult – in terms of
log-loss – it is to predict t from x. Equivalently, it provides a measure
of uncertainty about t when x is known.

Fall 2024 70 / 108

Example
Consider again the joint distribution p(x, t)

x\t 0 1
0 0.45 0.05
1 0.1 0.4

Assume the soft predictor q(t|x) given by the table

x\t 0 1
0 0.6 0.4
1 0.6 0.4

Compute the cross entropies H(p(t|x = 0), q(t|x = 0)) and

H(p(t|x = 1), q(t|x = 1)), and then evaluate the population log-loss.

Fall 2024 71 / 108

Example
Let’s first compute the conditional distribution p(t|x)

x\t 0 1
0 0.9 0.1
1 0.2 0.8

Then, the cross entropies are given as

H(p(t|x = 0), q(t|x = 0)) = 0.9·(− log(0.6))+0.1·(− log(0.4)) = 0.55

H(p(t|x = 1), q(t|x = 1)) = 0.2·(− log(0.6))+0.8·(− log(0.4)) = 0.83

Therefore, the population log-loss is

Ex∼p(x) [H(p(t|x), q(t|x))] = 0.5 · 0.55 + 0.5 · 0.83 = 0.69

Fall 2024 72 / 108

Example

Compute now the minimum cross entropy, i.e., the conditional

entropy.
The conditional entropy H(t|x) is

E(x,t)∼p(x,t) [− log p(t|x)] = 0.45 · (− log(0.9)) + 0.05 · (− log(0.1))

+ 0.1 · (− log(0.2)) + 0.4 · (− log(0.8))
= 0.41.

Fall 2024 73 / 108

Example

Compute now the minimum cross entropy, i.e., the conditional

entropy.
The conditional entropy H(t|x) is

E(x,t)∼p(x,t) [− log p(t|x)] = 0.45 · (− log(0.9)) + 0.05 · (− log(0.1))

+ 0.1 · (− log(0.2)) + 0.4 · (− log(0.8))
= 0.41.

Fall 2024 73 / 108

Conditional Entropy

It may be at first glance surprising that, even when choosing the

optimal soft predictor that matches the true conditional distribution,
the population log-loss is not zero.
After all, if one chooses a hard predictor t̂ that always produces the
correct value t, the population loss is zero (under the mentioned
assumption that the loss function satisfies the equality ℓ(t, t) = 0).
This points to a conceptual difference between soft and hard
prediction. To elaborate on this aspect, let us consider a discrete rv t.
A soft predictor must assign a score q(t|x) to every value of rv t.
Given a realization t = t, for x = x, the incurred log-loss is
− log q(t|x). This loss is only zero if the score assigned to t is
maximum, i.e., if q(t|x) = 1.

Fall 2024 74 / 108

Conditional Entropy

But if this is the case, all other values t ′ ̸= t would incur an infinite
log-loss − ′
Plog q(t′ |x) = − log(0) = ∞, since we must have the
equality t ′ q(t |x) = 1 for every x.
Therefore, the only situation in which we can guarantee a zero
population log-loss is if the distribution p(t|x) assigns probability 1 to
a single value t for every value of x.
As a result, the minimum population log-loss, i.e., the conditional
entropy, is typically positive, and it can only be equal to zero if the
relationship between x and t under the model p(x, t) is deterministic,
i.e., if p(x, t) = 1 only for one value of t given x.

Fall 2024 75 / 108

Conditional Entropy

For continous rvs t, i.e., for estimation problems, as discussed, the

log-loss can be negative.
In fact, if the relationship between x and t under the model p(x, t)
tends to a deterministic model, i.e., if p(x, t) > 0 only for one value
of t given value x, the conditional entropy tends to −∞.
To see this, consider the limit of the entropy of a Gaussian
distribution as the variance goes to zero.
In this sense, informally speaking, “−∞” in estimation problerms
plays the role of “0” in detection problems in terms of the log-loss.

Fall 2024 76 / 108

Soft Predictors Minimize the Average KL Divergence

As seen, we have the equality KL(p∥q) = H(p, q) − H(p) that

relates KL divergence, cross entropy, and entropy. We will now derive
a similar equality involving the conditional entropy.
This equality will allow us to draw the important conclusion that, by
minimizing the population cross-entropy loss, the soft predictors also
minimize the average KL divergence between true posterior p(t|x)
and soft predictor q(t|x).
First, by using the mentioned equality we can write

KL(p(t|x)||q(t|x)) = H(p(t|x), q(t|x)) − H(p(t|x))

for every fixed value x.

Fall 2024 77 / 108

Soft Predictors Minimize the Average KL Divergence

As seen, we have the equality KL(p∥q) = H(p, q) − H(p) that

relates KL divergence, cross entropy, and entropy. We will now derive
a similar equality involving the conditional entropy.
This equality will allow us to draw the important conclusion that, by
minimizing the population cross-entropy loss, the soft predictors also
minimize the average KL divergence between true posterior p(t|x)
and soft predictor q(t|x).
First, by using the mentioned equality we can write

KL(p(t|x)||q(t|x)) = H(p(t|x), q(t|x)) − H(p(t|x))

for every fixed value x.

Fall 2024 77 / 108

Soft Predictors Minimize the Average KL Divergence

Therefore, by averaging over x ∼ p(x), we obtain

Ex∼p(x) [KL(p(t|x)||q(t|x))] =Ex∼p(x) [H(p(t|x), q(t|x))]

− Ex∼p(x) [H(p(t|x))]
=Lp (q(·|·)) − Ex∼p(x) [H(p(t|x))]
=Lp (q(·|·)) − H(t|x).

Since H(t|x) does not depend on the soft predictor q(t|x), the optimal soft
predictor, which minimizes Lp (q(·|·)), also minimizes the average KL
divergence Ex∼p(x) [KL(p(t|x)||q(t|x))].

Fall 2024 78 / 108

 Mutual Information

Fall 2024 79 / 108

Mutual Information

Consider again two random variables (x, t) ∼ p(x, t)

We have seen that:
▶ the entropy H(t) represents the minimum population log-loss when the
only information available is the distribution p(t);
▶ the conditional entropy H(t|x) represents the minimum population
log-loss when we also have access to x to predict t.
The mutual information is defined as

I(x; t) := H(t) − H(t|x)

and measures by how much we can decrease the population log-loss

when we have access to x:
▶ it is a measure of statistical dependence between x and t.

Fall 2024 80 / 108

Mutual Information and KL Divergence

The mutual information can be written in terms of the KL divergence

as

I(x; t) = H(t) − H(t|x)

  
p(t|x)
= E(x,t)∼p(x,t) log
p(t)
  
p(x, t)
= E(x,t)∼p(x,t) log
p(x)p(t)
= KL(p(x, t)∥p(x)p(t)).

Hence, it can also be interpreted as measuring by how much the joint

distribution p(x, t) differs from the product distribution p(x)p(t)
under which x and t are independent:
▶ this is another way of thinking of I(x; t) as a measure of the
dependence of x and t.

Fall 2024 81 / 108

Mutual Information and “Explained Uncertainty”
Finally, we can interpret mutual information in terms of “explained
uncertainty”.
To see this, rewrite the definition of mutual information as
H(t) = H(t|x) + I(x; t) .
|{z} | {z } | {z }
total uncertainty residual, i.e., unexplained, uncertainty explained uncertainty

In the identity above, we have decomposed the total a priori

uncertainty about t into the sum of the residual uncertainty that
remains even after observing x and of the part of the entropy that is
explained by the observation of x. The latter is measured by the
mutual information.
We note that this decomposition is related, but distinct, from the
decomposition of variance, also known as law of total variance
Var(t) = Ex∼p(x) [Var(t|x)] + Var(Et∼p(t|x) [t|x]) .
| {z } | {z } | {z }
total variance residual, i.e., unexplained, variance explained variance
.
Fall 2024 82 / 108
Mutual Information and “Explained Uncertainty”
Finally, we can interpret mutual information in terms of “explained
uncertainty”.
To see this, rewrite the definition of mutual information as
H(t) = H(t|x) + I(x; t) .
|{z} | {z } | {z }
total uncertainty residual, i.e., unexplained, uncertainty explained uncertainty

In the identity above, we have decomposed the total a priori

uncertainty about t into the sum of the residual uncertainty that
remains even after observing x and of the part of the entropy that is
explained by the observation of x. The latter is measured by the
mutual information.
We note that this decomposition is related, but distinct, from the
decomposition of variance, also known as law of total variance
Var(t) = Ex∼p(x) [Var(t|x)] + Var(Et∼p(t|x) [t|x]) .
| {z } | {z } | {z }
total variance residual, i.e., unexplained, variance explained variance
.
Fall 2024 82 / 108
Mutual Information: Some Properties

Since we have KL(p(x, t)∥p(x)p(t)),

▶ the mutual information is symmetric:

I(x; t) = I(t; x) = H(x) − H(x|t);

▶ the mutual information is non-negative

I(x; t) ≥ 0,

and we have I(x; t) = 0 only if x and t are independent.

It is important to note that, for continuous rvs both H(t) and H(t|x)
can be negative, but their different must be non-negative.

Fall 2024 83 / 108

Mutual Information: Some Properties

Two useful bounds on the mutual information that follow directly

from Gibbs inequality are as follows (see proofs in Appendix):
▶ upper bound: for any distribution q(t), we have the inequality
  
p(t|x)
I(x; t) ≤ H(p, q) − H(t|x) = E(x,t)∼p(x,t) log
q(t)
▶ lower bound: for any conditional distribution q(t|x), we have the
inequality

I(x; t) ≥ H(t) − Ex∼p(x) [H(p(t|x), q(t|x))]

  
q(t|x)
= E(x,t)∼p(x,t) log
p(t)

Fall 2024 84 / 108

Mutual Information and Cross Entropy

From the lower bound, we have the following relationship between

mutual information and average cross entropy
  
q(t|x)
I(x; t) ≥ E(x,t)∼p(x,t) log
p(t)
 

= Ex∼p(x) Et∼p(t|x) [log (q(t|x))]+H(t)

 
| {z }
−H(p(t|x),q(t|x))

Therefore, the optimal soft predictor q(t|x) that minimizes the cross
entropy, also maximizes a lower bound on the mutual information.

Fall 2024 85 / 108

Example

Consider again the joint distribution p(x, t) = p(t)p(x|t) with

▶ t ∼ N (ν, α−1 ), and
▶ (x|t = t) ∼ N (t, β −1 ), i.e., x = t + z, with independent noise
z ∼ N (0, β −1 ).
What is the mutual information I(x; t)?

Fall 2024 86 / 108

Example
We can directly calculate the (differential) entropy

1
H(t) = H(N (ν, α−1 )) = log(2πeα−1 ).
2
Recalling
 that we have  the soft predictor p(t|x)
αν+βx 1
= N t α+β , α+β , we can then also compute the conditional
entropy
1
H(t|x) = log(2πe(α + β)−1 ).
2
Therefore, the mutual information is
 
1 β
I(x; t) = H(t) − H(t|x) = log 1 + .
2 α

The mutual information increases with the ratio αβ between the

precision of the observation and the precision of the prior.

Fall 2024 87 / 108

Log-Loss as a Universal Loss Function
Concered as it is with the performance of a soft predictor q(t|x), the
log-loss − log q(t|x) appears to be rather different from the loss
ℓ(t, t̂) of a hard prediction t̂.
In fact, the difference is not as stark as it may seem, and the log-loss,
in a fairly broad sense, includes as a special case most practical loss
functions ℓ(t, t̂).
To see this, let us consider the log-loss for a Gaussian soft predictor
q(t|x) = N (t|f (x), σ 2 ), where f (·) is some function of input x. This
can be written as
1
− log q(t|x) = 2 (t − f (x))2 + const
2σ
1
= 2 ℓ(t, f (x)) + const
2σ
where the constant term does not depend on input x.
Therefore, apart from inessential multiplicating and additive
constants, the log-loss is equivalent to the ℓ2 loss when the hard
predictor is given by the mean f (x) of the soft predictor.
Fall 2024 88 / 108
Log-Loss as a Universal Loss Function

Equivalently, we have that the ℓ2 loss for a hard predictor t̂(x) can be
expressed as the log-loss for a soft predictor of the form

q(t|x) = exp(−a · ℓ(t, t̂(x)) + b),

where a > 0 and b > 0 are constants, with b being a normalizing

constant that ensures that q(t|x) is a conditional pdf.
More generally, if the score output by a soft predictor depends on the
loss of a hard predictor – as is the case for the soft predictor
q(t|x) = N (t|f (x), σ 2 ) – then the log-loss subsumes as a special case
the loss of the hard predictor.

Fall 2024 89 / 108

 Summary

Fall 2024 90 / 108

Summary
Inference refers to optimal prediction of a target variable t from an
input variable x in the presence of model information, i.e., when the
joint distribution p(x, t) is known.
We can distinguish:
▶ detection problems, in which the target t is discrete (e.g., predicting
rain vs shine)
▶ estimation problems, in which the target t is continuous (e.g.,
predicting temperature)
The optimal hard predictor minimizes the population loss

t̂ ∗ (·) = arg min Lp (t̂(·)) = E(x,t)∼p(x,t) [ℓ(t, t̂(x))] ,


t̂(·)

or equivalently, by optimizing separately for each input x, we have

t̂ ∗ (x) = arg min Et∼p(t|x) [ℓ(t, t̂)] ,


t̂

which depends on the posterior distribution p(t|x).

Fall 2024 91 / 108
Summary
Inference refers to optimal prediction of a target variable t from an
input variable x in the presence of model information, i.e., when the
joint distribution p(x, t) is known.
We can distinguish:
▶ detection problems, in which the target t is discrete (e.g., predicting
rain vs shine)
▶ estimation problems, in which the target t is continuous (e.g.,
predicting temperature)
The optimal hard predictor minimizes the population loss

t̂ ∗ (·) = arg min Lp (t̂(·)) = E(x,t)∼p(x,t) [ℓ(t, t̂(x))] ,


t̂(·)

or equivalently, by optimizing separately for each input x, we have

t̂ ∗ (x) = arg min Et∼p(t|x) [ℓ(t, t̂)] ,


t̂

which depends on the posterior distribution p(t|x).

Fall 2024 91 / 108
Summary
Bayesian inference: A soft predictor q(t|x) assigns a score in the form
of a probability for each value of t given x. The optimal soft predictor
solves the problem of minimizing the population log-loss, or
cross-entropy loss, as
 

 

∗
q (·|·) = arg min Lp (q(·|·)) = E(x,t)∼p(x,t) [− log q(t|x)] ,
q(·|·) 
 | {z }

log-loss

or equivalently, by optimizing separately for each input x, we have

 

 


 


 

 
∗
q (·|x) = arg min Lp (q(·|x)) = Et∼p(t|x) [− log q(t|x)] .
q(·|x) 
 | {z } 


 log-loss 



 | {z } 

cross entropy H(p(t|x), q(t|x))

The optimal soft predictor is given by the posterior distribution

q ∗ (t|x) = p(t|x).
Fall 2024 92 / 108
Summary

The minimun population log-loss is known as conditional entropy of t

given x
H(t|x) = E(x,t)∼p(x,t) [− log p(t|x)].
The conditional entropy is a measure of uncertainty about variable t
when variable x is known.
When the only information available about t is its distribution, the
minimum population log-loss is given by the entropy

H(t) = Et∼p(t) [− log p(t)].

The entropy is a measure of uncertainty about variable t when no

additional information is available apart from its distribution.

Fall 2024 93 / 108

Summary
The KL divergence between distributions p and q is defined as

KL(p∥q) = H(p, q) − H(p) ≥ 0

with equality if and only if q is identical to p. The inequality above is

known as Gibbs inequality.
The KL divergence is an asymmetric measure of distance between two
distributions, while the cross entropy is a measure of “regret” or
excess loss.
Since H(p(·|x)) does not depen on q(·|x), the optimal soft predictor
can also be formulated as
 

 

∗
q (·|x) = arg min KL(p(·|x)∥q(·|x))
q(·|x) 
| {z }

KL divergence

Fall 2024 94 / 108

Summary

The mutual information

I(x; t) = H(t) − H(t|x)

measures by how much we can decrease the population log-loss when

we have access to x, and is accordingly a measure of statistical
dependence between x and t.
The mutual information can be written in terms of the KL divergence
as

I(x; t) = KL(p(x, t)∥p(x)p(t)).

Fall 2024 95 / 108

 Appendix

Fall 2024 96 / 108

Generalized Entropy and Generalized Conditional Entropy

The concepts of entropy and conditional entropy can be generalized

to include any loss function.
We have seen that the entropy is the minimum population log-loss
when one only knows the distribution p(t) of the target variable t;
and that the conditional entropy is the minimum population log-loss
when we have access to an input variable x.
Generalizing these concepts to hard predictors, we can define as
generalized entropy the minimum population loss when one only
knows the distribution p(t) of the target variable t

Hℓ (t) = Lp (t̂ ∗ ) = Et∼p(t) [ℓ(t, t̂ ∗ )].

The generalized entropy measures how much uncertainty there is

about t, when the uncertainty is measured by the loss function ℓ.

Fall 2024 97 / 108

Relating Generalized Entropy and Generalized Conditional
Entropy

And we can define as generalized conditional entropy the minimum

population loss when we have access to an input variable x

Hℓ (t|x) = Lp (t̂ ∗ (·)) = E(x,t)∼p(x,t) [ℓ(t, t̂ ∗ (x))].

The generalized conditional entropy hence measures how much

uncertainty there is about t given x on average over x, when the
uncertainty is measured by the loss function ℓ.
Note that these definitions are loss dependent.
The generalized mutual information can be analogously defined as

Iℓ (x; t) = Hℓ (t) − Hℓ (t|x).

Fall 2024 98 / 108

Entropy vs Differential Entropy

If rv t ∼ p(t) is discrete-valued, then the entropy

H(t) = Ex∼p(x) [− log p(x)] satisfies

0 ≤ H(t) ≤ log |T |,

where |T | denotes the cardinality of the alphabet of rv t.

Accordingly, the entropy is non-negative; is minimized when the rv is
deterministic, i.e., it takes a single value with probability 1, i.e.,
p(t) = 1(t = t0 ) for some t0 ∈ T ; and is maximized when the
distribution is uniform, i.e., when p(t) = 1/|T |.
One can think of the entropy as the logarithm of the “effective”
alphabet size.

Fall 2024 99 / 108

Entropy vs Differential Entropy
If rv t ∼ p(t) is continuous-valued, the (differential) entropy does not
satisfy these properties and we have

−∞ ≤ H(t) ≤ +∞.

The differential entropy can be thought of as the logarithm of the

“effective” support of the distribution.
As an example, for a Gaussian rv, the differential entropy is
1
H(t) = H(N (ν, α−1 )) = log(2πeα−1 ),
2
which tends to −∞ as the precision goes to infinity, and hence the
variance goes to zero; and to +∞as the precision goes to zero, and
hence the variance goes to infinity.
Note that a continuous rv with zero entropy is not a deterministic
variable. For instance, a Gaussian rv with precision α = 2πe has
differential entropy H(N (ν, α−1 )) = 0.
Fall 2024 100 / 108
Proof of Gibbs Inequality

We use Jensen’s inequality:

d 2 f (x)
▶ Given a convex function f (x), that is a function with dx 2 ≥ 0, we
have the inequality


Ex∼p(x) [f (x)] ≥ f Ex∼p(x) [x]

with equality if and only if f (x) is constant for all x with p(x) > 0.

Fall 2024 101 / 108

Proof of Gibbs Inequality

Since f (x) = − log(x) is convex, we have

 
q(t)
KL(p||q) = Et∼p(t) − log
p(t)
  
q(t)
≥ − log Et∼p(t)
p(t)
!
X q(t)
= − log p(t)
t
p(t)
!
X
= − log q(t)
t
= − log (1) = 0,

with equality if and only if p(t) = q(t).

Fall 2024 102 / 108

Jensen-Shannon (JS) Divergence

Recall that the KL divergence is asymmetric. A symmetric version of

the KL divergence is known as JS divergence:
▶ the JS divergence for any two distributions p and q is defined as

JS(p, q) = JS(q, p)
   
1 p+q 1 p+q
= KL p + KL q ;
2 2 2 2
▶ we have JS(p, q) ≥ 0, with equality if and only if p and q are indentical;
▶ it can also be proved that, unlike the KL divergence, the JS divergence
is upper bounded as JS(p, q) ≤ log(2).

Fall 2024 103 / 108

Conditional Entropy and JS Divergence

The JS divergence can be related to the conditional entropy for a

binary detection problem, and hence to the corresponding minimal
population log-loss.
To see this, consider the following joint distribution

t∼Bern(1/2)
(x|t = 1) ∼ p(x|t = 1)
(x|t = 0) ∼ p(x|t = 0)

p(x|t=1)+p(x|t=0)
Note that the marginal of x is given as p(x) = 2 .
We will specifically show that we have

H(t|x) = log(2) + JS(p(x|t = 0), p(x|t = 1)).

Fall 2024 104 / 108

Conditional Entropy and JS Divergence

Proof:

H(t|x) = E(x,t)∼p(x,t) [− log p(t|x)]

1
LIE 1X
= Ex∼p(x|t=t) [− log p(t|x)]
2 t=0
1  
1X 0.5p(x|t)
= Ex∼p(x|t=t) − log
2 t=0 p(x)
1  
1X p(x|t)
= log(2) + Ex∼p(x|t) − log
2 t=0 p(x)
|  {z }
p(x|t=0)+p(x|t=1)
=KL p(x|t) 2

= log(2) + JS(p(x|t = 0), p(x|t = 1))

where we used the Law of Iterated Expectation (LIE).

Fall 2024 105 / 108

Data Processing Inequality

The mutual information satisfies the intuitive property that

post-processing of data cannot create information.
To elaborate, consider an input x and a target variable t.
Assume now that the input x is processed via a random
transformation p(y |x) producing y ∼ p(y |x) for x = x.
It can be proven that the mutual information I(y; t) cannot be larger
than the mutual information I(x; t), i.e., I(y; t) ≤ I(x; t). This is
known as data processing inequality.
When equality holds, we say that y is a sufficient statistic of x for the
prediction of t.

Fall 2024 106 / 108

Bounds on the Mutual Information

In this section, we derive two useful bounds on the mutual

information that follow directly from Gibbs inequality

H(p, q) ≥ H(p)

with equality if and only if p(z) = q(z).

Recall that the mutual information is defined as
  
p(t|x)
I(x; t) = E(x,t)∼p(x,t) log
p(t)
= H(t) − H(t|x)
= H(p(t)) − Ex∼p(x) [H(p(t|x))]

Fall 2024 107 / 108

Bounds on the Mutual Information

So, upper bounding the entropy with the cross entropy, we have the
following upper bound for any q(t)

I(x; t) ≤ H(p(t), q(t)) − H(t|x)

  
p(t|x)
= E(x,t)∼p(x,t) log
q(t)

And upper bounding the conditional entropy with the cross entropy,
we have the lower bound for any q(t|x)

I(x; t) ≥ H(t) − Ex∼p(x) [H(p(t|x), q(t|x))]

  
q(t|x)
= E(x,t)∼p(x,t) log .
p(t)

Fall 2024 108 / 108