Lecture 9 · November 11, 2026

Information Theory, Sampling and Density

How should a robot compare uncertain predictions?

Two safe routes can have different probabilities. A useful model must represent both, and we need evidence that it does.

Mathematics for Robotics · ROB-GY 6013
NYU Tandon · Jing Zhang · Fall 2026

Goodfellow et al., Deep Learning (2016), §3.13

Concept map

The reasoning path

One robot problem, several different questions

A distribution describes uncertainty. A score compares predictions. Samples estimate quantities. A density model reveals structure.

Goodfellow et al., Deep Learning (2016), §3.13

Recall

Probability recall

The distribution and its samples are different objects

Assume a finite outcome set. The probabilities are fixed; the observed outcomes vary.

$$\mathbb E_p[g(X)]=\sum_xp(x)g(x)$$
X,x
random outcome and possible value
p,g
probability mass function and measured quantity

Goodfellow et al., Deep Learning (2016), §3.8; original example

Definition

Surprisal

A confident mistake should cost more

A predicted probability of 0.01 makes an observed event more surprising than a prediction of 0.5.

$$I_q(x)=-\log_2q(x)$$
q(x)
predicted probability of the observed event
I_q(x)
surprisal, measured in bits

Goodfellow et al., Deep Learning (2016), §3.13

Derivation

Surprisal

Independent evidence adds in log space

For independent events, their joint probability is the product.

$$-\log_2(q_1q_2)=-\log_2q_1-\log_2q_2$$
q_1,q_2
probabilities of independent events

Derivation 1 / 1

Factor the independent joint probability

q₁ and q₂ are positive probabilities of independent events.

  1. $q(x_1,x_2)=q_1q_2$ by independence.
  2. $I_q(x_1,x_2)=-\log_2(q_1q_2)$ by the definition of surprise.
  3. $-\log_2(q_1q_2)=-\log_2q_1-\log_2q_2$ by the log-product rule.

Goodfellow et al., Deep Learning (2016), §3.13

Definition

Entropy

Average surprise under the true distribution

Use the same distribution to generate and score the outcome.

$$H(p)=-\sum_xp(x)\log_2p(x)$$
p(x)
probability of outcome x
H(p)
entropy in bits; use 0 log 0 = 0

Goodfellow et al., Deep Learning (2016), §3.13

Worked example

Entropy

A concrete prefix code makes the units visible

Course-created worked example

Four symbols have probabilities 1/2, 1/4, 1/8, 1/8. Use codewords 0, 10, 110, 111.

$$L=\tfrac 12(1)+\tfrac 14(2)+\tfrac 18(3)+\tfrac 18(3)$$
L
expected codeword length in bits

Shannon (1948), §§6,9–12; original course examples

Worked example

Entropy

The code length equals entropy in this example

Course-created worked example

The same four probabilities give ideal lengths 1, 2, 3, 3.

$$H(p)=\tfrac 12\log_22+\tfrac 14\log_24+\tfrac 14\log_28=1.75$$
p
(1/2, 1/4, 1/8, 1/8)
H(p)
average surprise in bits

Shannon (1948), §§6,9–12; original course examples

Your turn

Entropy

Which binary source is hardest to predict?

Compare A: p=(1,0), B: p=(3/4,1/4), C: p=(1/2,1/2).

  1. AA has the largest entropy
  2. BB has the largest entropy
  3. CC has the largest entropy✓

Solution 1 / 2

Compute each expected surprise

H is entropy in bits. A, B, C are the given binary distributions.

  1. $H(A)=0$. A single certain outcome has no surprise.
  2. $H(B)=-(3/4)\log_2(3/4)-(1/4)\log_2(1/4)\approx 0.811$.
  3. $H(C)=-(1/2)(-1)-(1/2)(-1)=1$.

Solution 2 / 2

Compare the distributions

The entropy values are 0, 0.811, and 1 bit.

  1. Choose C. Its two outcomes are equally plausible.
  2. A is fully predictable. B retains a more likely outcome.
  3. Maximum binary entropy occurs at equal probabilities, not certainty.

Goodfellow et al., Deep Learning (2016), §3.13

Definition

Cross entropy

The source and the prediction can differ

Outcomes follow p. The model scores them with q. Require q(x)>0 whenever p(x)>0.

$$H(p,q)=-\sum_xp(x)\log_2q(x)$$
p
data-generating probabilities
q
model probabilities
H(p,q)
cross entropy in bits

Goodfellow et al., Deep Learning (2016), §3.13

Definition

KL divergence

The excess cost of using the wrong probabilities

Subtract the irreducible entropy of the source from its cross entropy.

$$D_{\mathrm{KL}}(p\Vert q)=\sum_xp(x)\log_2\frac{p(x)}{q(x)}$$
p,q
source and model on the same outcomes
D_KL
Kullback–Leibler divergence in bits

Goodfellow et al., Deep Learning (2016), §3.13

Derivation

KL divergence

The cross-entropy identity follows by expansion

Separate the logarithm of a ratio into a difference.

$$H(p,q)=H(p)+D_{\mathrm{KL}}(p\Vert q)$$
H(p)
source uncertainty
D_KL
extra cost of q
H(p,q)
total average log penalty

Derivation 1 / 2

Expand the log ratio

p is the fixed source; q is positive wherever p is positive.

  1. $D_{\rm KL}(p\Vert q)=\sum_xp(x)\log_2[p(x)/q(x)]$.
  2. $=\sum_xp(x)\log_2p(x)-\sum_xp(x)\log_2q(x)$ by the log-ratio rule.

Derivation 2 / 2

Identify the two entropy terms

H(p) is source entropy; H(p,q) is cross entropy.

  1. $\sum_xp(x)\log_2p(x)=-H(p)$.
  2. $-\sum_xp(x)\log_2q(x)=H(p,q)$.
  3. Hence $D_{\rm KL}(p\Vert q)=H(p,q)-H(p)$, or $H(p,q)=H(p)+D_{\rm KL}(p\Vert q)$.

Goodfellow et al., Deep Learning (2016), §3.13

Worked example

KL divergence

A two-route model has a measurable penalty

Course-created worked example

Source p=(3/4,1/4). Model q=(1/2,1/2).

$$H(p,q)=1,\quad H(p)\approx 0.811,\quad D_{\rm KL}\approx 0.189$$
p,q
route probabilities in left/right order
values
bits per observed route

Goodfellow et al., Deep Learning (2016), §3.13

Your turn

KL divergence

What changes when source and model swap?

Now p=(1/2,1/2), q=(3/4,1/4). Find KL in bits.

  1. AAbout 0.189
  2. BAbout 0.208✓
  3. CExactly zero

Solution 1 / 2

Average the model log penalties

p=(1/2,1/2) generates data; q=(3/4,1/4) scores it.

  1. $H(p,q)=-(1/2)\log_2(3/4)-(1/2)\log_2(1/4)$.
  2. $H(p,q)=0.207519+1=1.207519$ bits.
  3. $H(p)=1$ bit because the source is fair.

Solution 2 / 2

Subtract source entropy

KL is the excess cross entropy for the given order.

  1. $D_{\rm KL}(p\Vert q)=1.207519-1=0.207519$ bits.
  2. Choose B. A is the value for the reversed source/model roles.
  3. C would require the two distributions to agree.

Goodfellow et al., Deep Learning (2016), §3.13

Derivation

Cross entropy

Maximum likelihood uses the same average penalty

Assume independent observations x₁,…,xₙ from one model qθ.

$$-\tfrac 1n\log\prod_{i=1}^nq_\theta(x_i)=-\tfrac 1n\sum_{i=1}^n\log q_\theta(x_i)$$
θ
adjustable model parameters
n,x_i
fixed sample count and observed values

Derivation 1 / 2

Turn a likelihood product into a sum

x₁,…,xₙ are observed iid data; θ is adjustable; log is natural.

  1. $L(\theta)=\prod_{i=1}^nq_\theta(x_i)$ by the iid model.
  2. $-n^{-1}\log L(\theta)=-n^{-1}\sum_i\log q_\theta(x_i)$ by the log-product rule.

Derivation 2 / 2

Group repeated outcomes

N_x is the count of outcome x; empirical frequency is p̂ₙ(x)=N_x/n.

  1. $-n^{-1}\sum_i\log q_\theta(x_i)=-\sum_x(N_x/n)\log q_\theta(x)$.
  2. $=-\sum_x\hat p_n(x)\log q_\theta(x)$, the empirical cross entropy.
  3. The minus sign converts maximization to minimization; fixed 1/n does not change the optimizer.

Goodfellow et al., Deep Learning (2016), §5.5

Your turn

KL divergence

Can a model forbid an event that occurs?

p=(0.9,0.1), q=(1,0). The second outcome is possible under p.

  1. AKL(p||q) is infinite✓
  2. BKL(p||q) is zero
  3. CThe zero-probability term is ignored

Solution 1 / 2

Check the support condition

p assigns probability 0.1 to outcome 2; q assigns it zero.

  1. The second term is $0.1\log(0.1/0)=+\infty$.
  2. It has positive source weight, so it cannot be omitted.
  3. The convention $0\log 0=0$ applies to zero source weight, not zero model probability.

Solution 2 / 2

Interpret the failure

The data source can produce an event that the model declares impossible.

  1. Choose A. The average log penalty is infinite.
  2. B would require matching distributions. C confuses source and model zeros.
  3. For finite KL, q must be positive wherever p is positive.

Goodfellow et al., Deep Learning (2016), §3.13

Derivation

KL divergence

Why the total cannot be negative

For positive u, −log u ≥ 1−u. Apply it where p(x)>0.

$$D_{\rm KL}(p\Vert q)\ge\sum_{p(x)>0}[p(x)-q(x)]\ge 0$$
u
q(x)/p(x)
log
natural logarithm here; base changes only scale

Derivation 1 / 2

Apply the tangent inequality

Use natural logs; u=q(x)/p(x)>0 on the support of p.

  1. $-\log u\ge 1-u$, with equality only at u=1.
  2. $p(x)\log[p(x)/q(x)]\ge p(x)-q(x)$ after multiplying by p(x)>0.

Derivation 2 / 2

Sum over source support

S={x:p(x)>0}; both p and q have total mass 1.

  1. $D_{\rm KL}(p\Vert q)\ge\sum_{x\in S}(p(x)-q(x))$.
  2. $=1-\sum_{x\in S}q(x)\ge 0$.
  3. Equality requires q=p on S and no q mass outside S. A log-base change preserves the sign.

Goodfellow et al., Deep Learning (2016), §3.13

Counterexample

KL divergence

Nonnegative does not make it a distance

Course-created worked example

KL can be asymmetric and violate the triangle inequality.

$$\begin{aligned}D(p\Vert r)&\approx1.758\\D(p\Vert q)+D(q\Vert r)&\approx0.368+0.511<1.758\end{aligned}$$
p,q,r
(0.9,0.1), (0.5,0.5), (0.1,0.9)
D
KL in nats for this example

Goodfellow et al., Deep Learning (2016), §3.13

Interpretation

KL fitting

The direction changes what the model averages

p is fixed. qθ is restricted to a chosen model family.

$$\min_\theta D(p\Vert q_\theta)\quad\text{or}\quad\min_\theta D(q_\theta\Vert p)$$
θ
adjustable model parameters
p,q_theta
target distribution and approximation

Goodfellow et al., Deep Learning (2016), §3.13

Derivation

KL fitting

Forward KL within a Gaussian family

Continuous density p on R: finite second moment, finite differential entropy, variance v>0. Fit q=N(m,s²), s²>0.

$$-\mathbb E_p[\log q(X)]=\tfrac 12\log(2\pi s^2)+\frac{\mathbb E_p[(X-m)^2]}{2s^2}$$
m,s²
adjustable Gaussian mean and variance
mu,v
fixed target mean and variance

Derivation 1 / 2

Insert the Gaussian model density

p is the fixed target density. q=N(m,s²), with adjustable m and s²>0.

  1. $q(x)=(2\pi s^2)^{-1/2}\exp[-(x-m)^2/(2s^2)]$.
  2. $-\log q(x)=\tfrac 12\log(2\pi s^2)+(x-m)^2/(2s^2)$.

Derivation 2 / 2

Average under the continuous target

μ=Eₚ[X], v=Varₚ(X)>0; differential entropy h(p)=−∫p(x)log p(x) dx is finite.

  1. $C(m,s^2)=-\mathbb E_p[\log q(X)]=\tfrac 12\log(2\pi s^2)+\mathbb E_p[(X-m)^2]/(2s^2)$.
  2. $D_{\rm KL}(p\Vert q)=\int p(x)\log[p(x)/q(x)]\,dx=C(m,s^2)-h(p)$.
  3. Finite fixed h(p) makes minimizing KL equivalent to minimizing C.

Goodfellow et al., Deep Learning (2016), §§3.8,3.9.3,3.13; course derivation

Derivation

KL fitting

The best Gaussian center is the target mean

Expand around μ=Eₚ[X]. The centered residual has zero expectation.

$$\mathbb E_p[(X-m)^2]=v+(\mu-m)^2$$
v
target variance E[(X−μ)²]
m
candidate Gaussian mean

Derivation 1 / 2

Expand the square around the target mean

μ=Eₚ[X], v=Varₚ(X), m is the adjustable Gaussian mean.

  1. $X-m=(X-\mu)+(\mu-m)$.
  2. $(X-m)^2=(X-\mu)^2+2(X-\mu)(\mu-m)+(\mu-m)^2$.

Derivation 2 / 2

Average and minimize

μ−m is fixed when taking expectation over X.

  1. $\mathbb E[X-\mu]=0$, so the cross term vanishes.
  2. $\mathbb E[(X-m)^2]=v+(\mu-m)^2$.
  3. For fixed s²>0, the nonnegative square is minimized at m=μ.

Goodfellow et al., Deep Learning (2016), §§3.8,3.9.3,3.13; course derivation

Derivation

KL fitting

The best Gaussian variance matches the spread

At m=μ, set r=s²>0 and minimize C(r).

$$C(r)=\tfrac 12\log(2\pi r)+\frac{v}{2r},\qquad C\prime(r)=\frac{r-v}{2r^2}$$
r
candidate Gaussian variance
v
positive target variance

Derivation 1 / 2

Differentiate with respect to the variance

r=s²>0 is adjustable; v>0 is the target variance.

  1. $C(r)=\tfrac 12\log(2\pi r)+v/(2r)$.
  2. $C\prime(r)=1/(2r)-v/(2r^2)=(r-v)/(2r^2)$.

Derivation 2 / 2

Verify the minimum, not just stationarity

The denominator 2r² is positive for r>0.

  1. For r<v, C′(r)<0. For r>v, C′(r)>0.
  2. C decreases toward v and increases after v, so r=v is the global minimum.
  3. The optimal Gaussian has mean μ and variance v.

Goodfellow et al., Deep Learning (2016), §§3.8,3.9.3,3.13; course derivation

Integrated example

KL fitting

One Gaussian can place its mean between two peaks

Course-created worked example

Let p be an equal mixture of N(−2,1) and N(2,1).

$$\mu=0,\qquad v=1+4=5,\qquad q^*=\mathcal N(0,5)$$
p
two-component target density
q*
best single Gaussian for forward KL

Goodfellow et al., Deep Learning (2016), §§3.8,3.9.3,3.13; course derivation

Your turn

KL fitting

An uneven mixture shifts both fitted moments

p=0.75 N(−2,1)+0.25 N(2,1). Fit one Gaussian by forward KL.

  1. AMean −1, variance 1
  2. BMean −1, variance 4✓
  3. CMean 0, variance 5

Solution 1 / 2

Compute moments of the target

Component means are −2 and 2; each component variance is 1.

  1. $\mu=0.75(-2)+0.25(2)=-1$.
  2. $\mathbb E[X^2]=0.75(1+4)+0.25(1+4)=5$.
  3. $v=\mathbb E[X^2]-\mu^2=5-1=4$.

Solution 2 / 2

Use the Gaussian-family result

The fitted Gaussian has adjustable mean m and variance s².

  1. Forward-KL minimization gives $m=\mu=-1$ and $s^2=v=4$. Choose B.
  2. A omits between-component spread. C ignores the unequal weights.
  3. The standard deviation is 2, distinct from variance 4.

Goodfellow et al., Deep Learning (2016), §§3.8,3.9.3,3.13; course derivation

Interpretation

KL fitting

Reverse KL penalizes probability in a forbidden gap

If q(x)>0 where p(x)=0 on a region of positive q mass, reverse KL is infinite.

$$D(q\Vert p)=\mathbb E_q[\log q(X)-\log p(X)]$$
p
fixed target density
q
candidate model density

Goodfellow et al., Deep Learning (2016), §3.13

Your turn

KL fitting

Does reverse KL always select one mode?

The candidate family contains the exact bimodal target p.

  1. AYes, one mode is always optimal
  2. BNo, q=p minimizes both directions✓
  3. CNeither direction can reach zero

Solution 1 / 2

Apply nonnegativity and equality

The exact target p is available as a candidate q.

  1. $D(p\Vert p)=0$ in either optimization.
  2. Every KL divergence is nonnegative, so zero is a global minimum.
  3. The exact bimodal target keeps both modes.

Solution 2 / 2

State the scope of the heuristic

A model family may or may not be able to represent the target.

  1. Choose B. Mode selection can arise from a restricted family and target geometry.
  2. A turns a tendency into a universal rule. C overlooks the exact target candidate.
  3. Always name the family before predicting the fitted shape.

Goodfellow et al., Deep Learning (2016), §3.13

Motivation

Mutual information

A sensor is useful when it changes our uncertainty

Let X be a hidden state and Y a sensor report. Does knowing Y help us predict X?

Shannon (1948), §§6,9–12; original course examples

Worked example

Mutual information

The marginals come from summing the joint table

Course-created worked example

A fair binary state is reported correctly with probability 0.9.

$$p_{XY}=\begin{bmatrix}0.45&0.05\\0.05&0.45\end{bmatrix}$$
rows
X=0,1
columns
Y=0,1
p_X,p_Y
row and column sums, each (1/2,1/2)

Shannon (1948), §§6,9–12; original course examples

Definition

Mutual information

Compare dependence with the independent baseline

The joint and product-of-marginals distributions live on the same pairs (x,y).

$$I(X;Y)=\sum_{x,y}p(x,y)\log_2\frac{p(x,y)}{p_X(x)p_Y(y)}$$
I(X;Y)
mutual information in bits
p_X,p_Y
marginal distributions

Shannon (1948), §§6,9–12; original course examples

Derivation

Mutual information

Information is expected uncertainty reduction

Use p(x,y)=p(y)p(x|y) inside the log ratio.

$$I(X;Y)=H(X)-H(X\mid Y)$$
H(X|Y)
average entropy of X after observing Y
H(X)
entropy before observing Y

Derivation 1 / 2

Cancel the report probability

p(x,y)=p_Y(y)p(x|y) on positive joint-probability pairs.

  1. $\log_2\frac{p(x,y)}{p_X(x)p_Y(y)}=\log_2\frac{p(x\mid y)}{p_X(x)}$.
  2. $=\log_2p(x\mid y)-\log_2p_X(x)$.

Derivation 2 / 2

Average over the joint distribution

H(X|Y)=−Σₓ,ᵧp(x,y)log₂p(x|y) is conditional entropy.

  1. $I(X;Y)=\sum_{x,y}p(x,y)\log_2p(x\mid y)-\sum_{x,y}p(x,y)\log_2p_X(x)$.
  2. The first sum is −H(X|Y). Summing over y makes the second sum −H(X).
  3. Therefore I(X;Y)=H(X)−H(X|Y), an expected reduction.

Shannon (1948), §§6,9–12; original course examples

Integrated example

Mutual information

A noisy binary sensor supplies part of a bit

Course-created worked example

X is fair. The sensor flips the state independently with probability e=0.1.

$$I(X;Y)=1-h_2(e)\approx 0.531$$
h_2(e)
−e log₂e−(1−e) log₂(1−e)
e
independent binary flip probability

Shannon (1948), §§6,9–12; original course examples

Your turn

Mutual information

A noisier sensor leaves more uncertainty

X is fair. Y flips X independently with probability e=0.25. Find I(X;Y).

  1. AAbout 0.811 bits
  2. BAbout 0.189 bits✓
  3. CExactly 0.75 bits

Solution 1 / 2

Compute remaining uncertainty

The binary state is fair, with independent flip probability e=0.25.

  1. $H(X)=1$ bit.
  2. $H(X\mid Y)=h_2(0.25)=-(1/4)\log_2(1/4)-(3/4)\log_2(3/4)$.
  3. $H(X\mid Y)\approx 0.811278$ bits.

Solution 2 / 2

Subtract from prior entropy

Mutual information is the expected reduction in entropy.

  1. $I(X;Y)=1-0.811278\approx 0.188722$ bits. Choose B.
  2. A is remaining uncertainty. C is the accuracy, not information.
  3. More flips move the report toward independence when e approaches 0.5.

Shannon (1948), §§6,9–12; original course examples

Worked example

Mutual information

Zero covariance can hide a nonlinear dependence

Course-created worked example

X is uniform on {−1,0,1}. Set Y=X².

$$\operatorname{Cov}(X,Y)=\mathbb E[X^3]-\mathbb E[X]\mathbb E[X^2]=0$$
X,Y
random input and its square
Cov
covariance; both variances are positive

Goodfellow et al., Deep Learning (2016), §3.8; original example

Your turn

Mutual information

How much does the square reveal?

X is uniform on {−1,0,1}; Y=X². H(Y|X)=0.

  1. AI(X;Y)=0 because covariance is zero
  2. BI(X;Y)=log₂3
  3. CI(X;Y)=h₂(1/3)≈0.918 bits✓

Solution 1 / 2

Find the distribution of the output

Y=0 when X=0; Y=1 when X=−1 or 1.

  1. $P(Y=0)=1/3$, $P(Y=1)=2/3$.
  2. $H(Y)=-(1/3)\log_2(1/3)-(2/3)\log_2(2/3)\approx 0.918296$.
  3. $H(Y\mid X)=0$ because Y is determined by X.

Solution 2 / 2

Use the information identity

Mutual information is symmetric, so use the simpler output entropy.

  1. $I(X;Y)=H(Y)-H(Y\mid X)=H(Y)$. Choose C.
  2. A confuses zero correlation with independence.
  3. B is H(X); observing the square does not reveal the sign when Y=1.

Shannon (1948), §§6,9–12; original course examples

Your turn

Mutual information

Compare a direct and an inverted sensor

X is a fair binary state. Sensor A gives Y=X. Sensor B gives Y=1−X.

  1. AA has more mutual information
  2. BBoth provide 1 bit✓
  3. CB provides zero information

Solution 1 / 2

Determine each conditional uncertainty

X is binary and both sensor mappings are deterministic and invertible.

  1. A reveals X directly; for B, recover $X=1-Y$.
  2. For either report, $H(X\mid Y)=0$.
  3. With fair X, $H(X)=1$, so $I(X;Y)=1$ bit.

Solution 2 / 2

Separate information from an uncorrected decision

A known inverted report can be decoded before choosing an action.

  1. Choose B. Mutual information measures dependence, not raw classification accuracy.
  2. A and C treat inversion as missing information, though it is reversible.
  3. Calibration tells the robot how to interpret the report.

Shannon (1948), §§6,9–12; original course examples

Synthesis

From distributions to data

The formulas need evidence from observations

Entropy compares uncertainty. KL compares models. Mutual information compares dependence. Samples estimate all three.

Goodfellow et al., Deep Learning (2016), §3.13

Definition

Monte Carlo estimation

An average estimates a chosen expectation

Collect n independent and identically distributed draws from p, with n chosen in advance.

$$\hat\mu_n=\frac 1n\sum_{i=1}^ng(X_i),\qquad\mu=\mathbb E_p[g(X)]$$
X_i
independent draws from the same distribution
g,mu
measured quantity and its true mean

UC Berkeley CS70 (2017), Note18: mean, variance, concentration

Derivation

Monte Carlo estimation

Linearity explains unbiasedness

Assume E|g(X)| is finite and fixed n.

$$\mathbb E[\hat\mu_n]=\frac 1n\sum_{i=1}^n\mathbb E[g(X_i)]=\mu$$
μ̂
random sample average
μ
common expectation of each sample value

Derivation 1 / 1

Use linearity of expectation

n is fixed; every measured value g(Xᵢ) has the same finite expectation μ.

  1. $\mathbb E[\hat\mu_n]=\mathbb E[n^{-1}\sum_i g(X_i)]$.
  2. $=n^{-1}\sum_i\mathbb E[g(X_i)]$ by linearity.
  3. $=n^{-1}(n\mu)=\mu$ by the common sample expectation.

UC Berkeley CS70 (2017), Note18: mean, variance, concentration

Derivation

Monte Carlo estimation

Independence makes the variance shrink

Assume Var(g(X))=σ²<∞ and independent samples.

$$\operatorname{Var}(\hat\mu_n)=\frac{\sigma^2}{n},\qquad\operatorname{SE}(\hat\mu_n)=\frac{\sigma}{\sqrt n}$$
σ²
variance of one measured value
SE
standard deviation of the estimator

Derivation 1 / 2

Expand the variance of the average

Zᵢ=g(Xᵢ) are independent with common finite variance σ².

  1. $\operatorname{Var}(\hat\mu_n)=n^{-2}\operatorname{Var}(\sum_i Z_i)$.
  2. $=n^{-2}\sum_i\operatorname{Var}(Z_i)$ because all cross covariances vanish.
  3. $=n^{-2}(n\sigma^2)=\sigma^2/n$.

Derivation 2 / 2

Convert variance to standard error

Standard error is the standard deviation of the estimator.

  1. $\operatorname{SE}(\hat\mu_n)=\sqrt{\operatorname{Var}(\hat\mu_n)}=\sigma/\sqrt n$.
  2. Four times as many independent samples gives half the standard error.
  3. This describes the average, not the spread of one observation.

UC Berkeley CS70 (2017), Note18: mean, variance, concentration

Your turn

Monte Carlo estimation

What does four times as much data buy?

Independent draws have the same finite variance. Increase n from 100 to 400.

  1. AStandard error becomes one quarter
  2. BStandard error becomes one half✓
  3. CEvery realized estimate is closer

Solution 1 / 2

Use the square-root law

The one-sample standard deviation σ is unchanged.

  1. $\operatorname{SE}_{100}=\sigma/10$.
  2. $\operatorname{SE}_{400}=\sigma/20$.
  3. $\operatorname{SE}_{400}/\operatorname{SE}_{100}=1/2$.

Solution 2 / 2

Interpret the guarantee

Standard error describes the distribution of estimates over repeated datasets.

  1. Choose B. Variance becomes one quarter, but standard error becomes one half.
  2. C is not guaranteed: an individual larger dataset can give a worse error.
  3. The sampling uncertainty shrinks in distribution, not monotonically on every path.

UC Berkeley CS70 (2017), Note18: mean, variance, concentration

Derivation

Monte Carlo estimation

A variance bound gives a probability statement

For fixed n and ε>0, the squared error is at least ε² on the large-error event.

$$P(|\hat\mu_n-\mu|\ge\varepsilon)\le\frac{\sigma^2}{n\varepsilon^2}$$
epsilon
chosen error tolerance
σ²
finite variance of g(X)

Derivation 1 / 2

Bound squared error on the bad event

E=|μ̂ₙ−μ|, ε>0, and A={E≥ε}.

  1. On A, E²≥ε²; outside A, E²≥0.
  2. Therefore $\mathbb E[E^2]\ge\varepsilon^2P(A)$.

Derivation 2 / 2

Insert the estimator variance

The fixed-n iid average is unbiased and has variance σ²/n.

  1. $\mathbb E[E^2]=\operatorname{Var}(\hat\mu_n)=\sigma^2/n$.
  2. Dividing gives $P(|\hat\mu_n-\mu|\ge\varepsilon)\le\sigma^2/(n\varepsilon^2)$.
  3. The result is an upper bound, not an equality or a guarantee for each dataset.

UC Berkeley CS70 (2017), Note18: mean, variance, concentration

Integrated example

Monte Carlo estimation

A conservative trial count for a success rate

Course-created worked example

Bernoulli success has variance p(1−p)≤1/4. Target error 0.1 with failure probability ≤0.05.

$$\frac{1}{4n(0.1)^2}\le 0.05\quad\Longrightarrow\quad n\ge 500$$
p
unknown success probability
n
fixed number of independent trials

UC Berkeley CS70 (2017), Note18: mean, variance, concentration

Your turn

Monte Carlo estimation

A tighter tolerance changes sample cost

Use p(1−p)≤1/4 and the variance bound. Keep failure probability ≤0.05; reduce error tolerance from 0.1 to 0.05.

  1. A250 trials suffice by this bound
  2. B1000 trials suffice by this bound
  3. C2000 trials suffice by this bound✓

Solution 1 / 2

Substitute the new tolerance

n is fixed; ε=0.05 and failure bound δ=0.05.

  1. $P(|\hat p-p|\ge\varepsilon)\le 1/(4n\varepsilon^2)$.
  2. $n\ge 1/[4(0.05)^2(0.05)]=2000$.
  3. Halving ε multiplies the sufficient n by four.

Solution 2 / 2

Read the statement precisely

This is a conservative sufficient count under independent Bernoulli trials.

  1. Choose C. A moves in the wrong direction; B ignores the square on ε.
  2. The result controls probability of error at least 0.05.
  3. It does not assert that each estimate is exactly within tolerance.

UC Berkeley CS70 (2017), Note18: mean, variance, concentration

Result

Monte Carlo estimation

The law of large numbers is not a monotone path

For every fixed ε>0, the variance bound tends to zero as n grows.

$$P(|\hat\mu_n-\mu|\ge\varepsilon)\longrightarrow 0$$
μ̂n
average of n iid measurements
μ
finite-variance population mean

UC Berkeley CS70 (2017), Note18: mean, variance, concentration

Boundary case

Monte Carlo estimation

Correlated repetitions are not fresh evidence

For general samples, the covariance terms remain.

$$\operatorname{Var}(\bar Z)=\frac{1}{n^2}\left[\sum_i\operatorname{Var}(Z_i)+2\sum_{i<j}\operatorname{Cov}(Z_i,Z_j)\right]$$
Z_i
measured values g(X_i)
Z-bar
sample average

UC Berkeley CS70 (2017), Note18: mean, variance, concentration

Definition

Stopping rules

The data can determine when collection ends

A stopping time T decides whether to stop using observations available so far.

$$T=\begin{cases}1,&X_1=1\\2,&X_1=0\end{cases}$$
X_i
independent fair Bernoulli trials
T
random sample count chosen by the rule

Sheffield, MIT 18.175 (2016), Lecture 14, pp.34–35; original example

Worked example

Stopping rules

Enumerating paths exposes the selection effect

Course-created worked example

Stop after first success, but take at most two trials. Each trial succeeds with probability 1/2.

$$(T,\hat p_T)=(1,1),(2,1/2),(2,0)$$
path probabilities
1/2, 1/4, 1/4 respectively
p̂T
success fraction at the stopping time

Sheffield, MIT 18.175 (2016), Lecture 14, pp.34–35; original example

Your turn

Stopping rules

Is the stopped success fraction unbiased?

Completed paths: 1, 01, 00. Their probabilities are 1/2,1/4,1/4 and estimates 1,1/2,0.

  1. AIts expectation is 1/2
  2. BIts expectation is 5/8✓
  3. CIts expectation is 1

Solution 1 / 2

Average over completed experiments

The true success probability is p=1/2.

  1. $\mathbb E[\hat p_T]=(1/2)(1)+(1/4)(1/2)+(1/4)(0)$.
  2. $\mathbb E[\hat p_T]=1/2+1/8=5/8$.
  3. The bias is $5/8-1/2=1/8$.

Solution 2 / 2

Locate the broken fixed-n argument

The stopping rule favors a short experiment when success occurs early.

  1. Choose B. The rule is fixed, but T depends on outcomes.
  2. A incorrectly imports the fixed-n unbiasedness proof. C ignores failed first trials.
  3. A random denominator correlated with data cannot be pulled outside expectation.

Sheffield, MIT 18.175 (2016), Lecture 14, pp.34–35; original example

Your turn

Stopping rules

Reverse the stopping preference

Stop after the first failure; otherwise take a second fair trial. Report success fraction.

  1. AExpected estimate 3/8✓
  2. BExpected estimate 1/2
  3. CExpected estimate 5/8

Solution 1 / 2

List the completed paths

Each trial is independent Bernoulli(1/2); stop after failure or after two trials.

  1. Path 0: probability 1/2, estimate 0.
  2. Path 10: probability 1/4, estimate 1/2.
  3. Path 11: probability 1/4, estimate 1.

Solution 2 / 2

Compute the reported average

Weight each stopped estimate by its completed-path probability.

  1. $\mathbb E[\hat p_T]=(1/2)0+(1/4)(1/2)+(1/4)1=3/8$.
  2. Choose A. The downward bias is $3/8-1/2=-1/8$.
  3. B assumes fixed n. C belongs to stopping after first success.

Sheffield, MIT 18.175 (2016), Lecture 14, pp.34–35; original example

Robotics payoff

Stopping rules

Match the guarantee to the collection rule

Fixed-n estimates need fixed-n evaluation. Adaptive collection needs an analysis designed for its stopping rule.

Howard et al. (2020), Introduction: time-uniform bounds

Integrated example

Monte Carlo estimation

A rollout result needs an uncertainty statement

Course-created worked example

An independent fixed evaluation has 80 successes in 100 trials. Use a Bernoulli model.

$$\hat p=0.8,\qquad\widehat{\operatorname{SE}}=\sqrt{\frac{0.8(0.2)}{100}}=0.04$$
p̂
observed success fraction
estimated SE
plug-in standard error, not exact coverage

UC Berkeley CS70 (2017), Note18: mean, variance, concentration

Your turn

Monte Carlo estimation

How many draws to see a rare route at least once?

A route has probability 0.1 in each independent draw. Find the smallest fixed integer n with detection probability at least 0.95.

$$P(\text{no rare route})=(0.9)^n$$
n
fixed independent sample count
  1. AAt least 10 draws
  2. BAt least 29 draws✓
  3. CAt least 95 draws

Solution 1 / 2

Turn detection into its complement

Each independent draw misses the rare route with probability 0.9.

  1. $P(\text{seen at least once})=1-0.9^n$.
  2. $1-0.9^n\ge 0.95$ means $0.9^n\le 0.05$.
  3. $n\log 0.9\le\log 0.05$.

Solution 2 / 2

Solve and round in the correct direction

log 0.9 is negative, so dividing reverses the inequality.

  1. $n\ge\log 0.05/\log 0.9\approx 28.433$. Thus n≥29. Choose B.
  2. A mistakes expected waiting count for a 95% detection guarantee.
  3. C is sufficient but is not the minimum among fixed integer counts.

UC Berkeley CS70 (2017), Note18: mean, variance, concentration

Motivation

Density and modes

A mean can hide the choices a robot actually makes

Observed actions: −2.2, −2.0, −1.8, 1.8, 2.0, 2.2. Their mean is zero.

$$\bar x=0,\qquad\text{dense groups lie near }-2\text{ and }2$$
x_i
six observed scalar actions
x̄
arithmetic mean

Wasserman, 36-708 Density Estimation, §§1,3–4

Definition

Density and modes

A discrete mode maximizes probability mass

For discrete outcomes, estimate each probability by its observed frequency.

$$\hat p_n(x)=\frac{N_x}{n},\qquad\hat m\in\arg\max_x\hat p_n(x)$$
N_x
number of observations equal to x
m̂
one empirical mode; ties are possible

Wasserman, 36-708 Density Estimation, §§1,3–4

Your turn

Density and modes

Does the largest observed count prove the true mode?

Three categories have counts 5,3,2 in ten independent observations.

  1. AThe first category is the empirical mode✓
  2. BThe first category is certainly the population mode
  3. CThe sample mean defines the mode

Solution 1 / 2

Distinguish observed and population quantities

Counts are 5,3,2 and sample size n=10.

  1. Empirical probabilities are $(0.5,0.3,0.2)$.
  2. The largest observed frequency belongs to the first category.
  3. Finite sampling error can change the rank of the observed frequencies.

Solution 2 / 2

Choose only what the data establish

A population mode maximizes true probabilities, not necessarily sample frequencies.

  1. Choose A. B makes a certainty claim that ten observations do not support.
  2. C confuses an average of labels with the most frequent outcome.
  3. Repeat the experiment to see how the empirical mode can vary.

Wasserman, 36-708 Density Estimation, §§1,3–4

Recall

Density and modes

Continuous data rarely repeat exactly

For an absolutely continuous model, each exact value has probability zero, while intervals can have positive probability.

$$P(X=x)=0,\qquad P(a\le X\le b)=\int_a^bp(u)\,du$$
p(u)
density, not point probability
a,b
interval endpoints

Goodfellow et al., Deep Learning (2016), §3.3.2

Definition

Histograms

Counts become density after dividing by width

Choose non-overlapping bins with common width h. Count Nⱼ observations in bin j.

$$\hat p(x)=\frac{N_j}{nh}\quad(x\text{ in bin }j)$$
n,N_j
total count and bin count
h
bin width in action units

Wasserman, 36-708 Density Estimation, §3; original example

Worked example

Histograms

The area check catches normalization mistakes

Course-created worked example

Eight samples give counts 2,4,2 in three bins of width 1.

$$\hat p=(0.25,0.5,0.25),\qquad\sum_jh\hat p_j=1$$
h
common bin width 1
p-hat_j
constant density in bin j

Wasserman, 36-708 Density Estimation, §3; original example

Your turn

Histograms

Compare bins with different widths

n=7. Bin A: count 4,width 2. Bin B: count 3,width 1. Which has higher histogram density?

  1. ABin A
  2. BBin B✓
  3. CThey have equal density

Solution 1 / 2

Normalize each count by its own width

n=7, N_A=4, h_A=2, N_B=3, h_B=1.

  1. $\hat p_A=4/(7\cdot 2)=2/7$.
  2. $\hat p_B=3/(7\cdot 1)=3/7$.
  3. Although A has more total mass, B concentrates mass into less width.

Solution 2 / 2

Check the areas

Each density times its bin width returns its probability mass.

  1. $2(2/7)+1(3/7)=1$.
  2. Choose B. A compares counts rather than density; C ignores widths.
  3. Density and probability mass answer different questions.

Wasserman, 36-708 Density Estimation, §3; original example

Interpretation

Histograms

The apparent peak depends on the binning

Bin width controls averaging. Bin origin controls which observations share a bin.

Wasserman, 36-708 Density Estimation, §3; original example

Definition

Kernel density estimation

Each sample contributes a small smooth bump

Use a nonnegative kernel K with total integral 1 and a bandwidth h>0.

$$\hat p_h(x)=\frac 1{nh}\sum_{i=1}^nK\!\left(\frac{x-x_i}{h}\right)$$
x_i,x
observed samples and query location
h,K
bandwidth and unit-integral kernel

Wasserman, 36-708 Density Estimation, §4; original example

Derivation

Kernel density estimation

The normalization survives a change of scale

Substitute u=(x−xᵢ)/h, so dx=h du.

$$\int\frac 1hK\!\left(\frac{x-x_i}{h}\right)dx=\int K(u)\,du=1$$
h
positive bandwidth
x_i
fixed sample center
u
rescaled integration variable

Derivation 1 / 2

Change the integration variable

K has integral 1, h>0, and xᵢ is a fixed sample center.

  1. Set $u=(x-x_i)/h$, so $dx=h\,du$.
  2. $\int h^{-1}K((x-x_i)/h)\,dx=\int h^{-1}K(u)h\,du=1$.

Derivation 2 / 2

Average the unit-area bumps

There are n kernel bumps and the estimator divides their sum by n.

  1. $\int\hat p_h(x)\,dx=n^{-1}\sum_{i=1}^n1=1$.
  2. Without the 1/h factor, each bump would instead have area h.
  3. Bandwidth changes width and height together, preserving total probability.

Wasserman, 36-708 Density Estimation, §4; original example

Your turn

Kernel density estimation

What does a larger bandwidth change?

Use the same samples and a normalized Gaussian kernel. Increase h.

  1. AWider bumps, same total area✓
  2. BMore total probability mass
  3. CNarrower bumps and more sharp peaks

Solution 1 / 2

Follow the scale factors

The bump is K((x−x_i)/h)/h with h>0.

  1. Increasing h spreads the bump horizontally.
  2. The factor 1/h lowers its height so its area stays 1.
  3. The mean of n such bumps remains a normalized density.

Solution 2 / 2

Interpret the estimator change

A larger bandwidth averages over a wider neighborhood.

  1. Choose A. Nearby peaks may merge through more smoothing.
  2. B violates normalization. C describes smaller rather than larger h.
  3. More smoothing can conceal genuine structure.

Wasserman, 36-708 Density Estimation, §4; original example

Integrated example

Kernel density estimation

The same actions support different apparent shapes

Course-created worked example

Data: −2.2, −2.0, −1.8, 1.8, 2.0, 2.2. Compare Gaussian-kernel bandwidths 0.25 and 2.

$$\hat m_h\in\arg\max_x\hat p_h(x)$$
m̂h
estimated density mode, dependent on h
h
bandwidth, in action units

Wasserman, 36-708 Density Estimation, §4; original example

Your turn

Density and modes

Choose an action from two observed groups

Actions form two separated groups around−2 and 2. A robot needs one plausible action.

  1. AAlways execute the mean 0
  2. BModel the distribution and check the sampled action✓
  3. CDeclare every observed value a true mode

Solution 1 / 2

Match the method to the goal

The goal is a plausible action, not a minimum squared-error summary.

  1. The mean 0 summarizes symmetric data but can fall between the groups.
  2. A distribution model can represent both groups and generate alternatives.
  3. Generated actions still need task-specific feasibility checks.

Solution 2 / 2

Keep the statistical limits visible

A finite sample and a chosen smoothing level do not reveal exact population modes.

  1. Choose B. A can average incompatible behaviors.
  2. C treats sampling noise as exact density structure.
  3. Diffusion and flow models will represent action distributions in later lectures.

Wasserman, 36-708 Density Estimation, §§1,3–4

Definition

Stable probability computation

Exponentials turn scores into probabilities

A model produces finite real logits z₁,…,z_K. Normalize positive exponentials.

$$q_i=\frac{e^{z_i}}{\sum_{j=1}^Ke^{z_j}}$$
z_i
unconstrained model score, called a logit
q_i
normalized probability of class i

Blanchard, Higham & Higham (2021), §§1,4

Derivation

Stable probability computation

A shared shift leaves softmax unchanged

Multiply numerator and denominator by e⁻ᶜ. Choose c=maxⱼzⱼ.

$$q_i=\frac{e^{z_i-c}}{\sum_je^{z_j-c}}$$
c
largest finite logit
z_i−c
nonpositive shifted logit

Derivation 1 / 2

Cancel a common exponential factor

zᵢ are finite logits; c is any finite shared constant.

  1. $q_i=\frac{e^{z_i}e^{-c}}{\sum_je^{z_j}e^{-c}}$.
  2. $=\frac{e^{z_i-c}}{\sum_je^{z_j-c}}$ by exponential multiplication.

Derivation 2 / 2

Choose the shift for numerical safety

Set c=maxⱼzⱼ.

  1. Every shifted score satisfies zᵢ−c≤0.
  2. Therefore 0<exp(zᵢ−c)≤1 in exact arithmetic; at least one equals 1.
  3. This avoids exponential overflow. Tiny terms can still underflow in finite precision.

Blanchard, Higham & Higham (2021), §§1,4

Worked example

Stable probability computation

Large logits can encode ordinary probabilities

Course-created worked example

Given z=(1000,1001,1002), subtract c=1002.

$$q=\frac{(e^{-2},e^{-1},1)}{e^{-2}+e^{-1}+1}\approx(0.090,0.245,0.665)$$
z,q
logit vector and probability vector
c
maximum logit 1002

Blanchard, Higham & Higham (2021), §§1,4

Your turn

Stable probability computation

Which change preserves the distribution?

For finite logits z, compare two transformations before softmax.

  1. Az→z+1000·1✓
  2. Bz→2z
  3. Cz→−z

Solution 1 / 2

Factor the shared exponential

1 is the all-ones vector. Every logit receives the same added constant.

  1. $e^{z_i+1000}=e^{1000}e^{z_i}$.
  2. The common factor cancels between numerator and denominator.
  3. Therefore softmax(z+1000·1)=softmax(z) in exact arithmetic.

Solution 2 / 2

Compare the other transformations

Changing score differences changes the distribution in general.

  1. Choose A. Multiplying by 2 magnifies differences and usually sharpens probabilities.
  2. Negating reverses score order.
  3. Use a stable shifted evaluation rather than directly forming e¹⁰⁰⁰.

Blanchard, Higham & Higham (2021), §§1,4

Derivation

Stable probability computation

Log-sum-exp keeps the normalization in log space

Factor the largest exponential before taking the logarithm.

$$\operatorname{LSE}(z)=c+\log\sum_je^{z_j-c},\quad c=\max_jz_j$$
LSE(z)
log of the sum of exponentials
c
maximum finite logit

Derivation 1 / 2

Factor before taking the logarithm

c=maxⱼzⱼ for finite logits z.

  1. $\sum_je^{z_j}=e^c\sum_je^{z_j-c}$.
  2. $\log\sum_je^{z_j}=\log e^c+\log\sum_je^{z_j-c}$.
  3. $\operatorname{LSE}(z)=c+\log\sum_je^{z_j-c}$.

Derivation 2 / 2

Track the constant

LSE is a log normalization value, not a probability ratio.

  1. Adding c to every logit adds c to LSE.
  2. The shift term cancels in softmax ratios but must be restored in LSE.
  3. For z=(1000,1000), LSE=1000+log 2.

Blanchard, Higham & Higham (2021), §§1,4

Derivation

Stable probability computation

Compute log probabilities before exponentiating

For a known class y, use the log probability directly in cross entropy.

$$\log q_i=z_i-\operatorname{LSE}(z),\qquad\ell=-\log q_y$$
y
observed class index
ℓ
single-example negative log loss in nats

Derivation 1 / 2

Take the log of the softmax ratio

qᵢ is the class probability and LSE(z)=logΣⱼexp(zⱼ).

  1. $\log q_i=\log e^{z_i}-\log\sum_je^{z_j}=z_i-\operatorname{LSE}(z)$.
  2. For the observed class y, $\ell=-\log q_y$.

Derivation 2 / 2

Keep the computation in shifted form

c=maxⱼzⱼ and y is the observed class index.

  1. $\log q_i=(z_i-c)-\log\sum_je^{z_j-c}$.
  2. $\ell=\log\sum_je^{z_j-c}-(z_y-c)$.
  3. Average ℓ across observations to obtain empirical cross entropy in nats.

Blanchard, Higham & Higham (2021), §§1,4

Your turn

Stable probability computation

Compute the observed-class log loss

z=(1000,999). The observed class is the second. Compute loss in nats.

  1. AAbout 0.313
  2. BAbout 1.313✓
  3. CInfinite because e¹⁰⁰⁰ overflows

Solution 1 / 2

Shift before computing the log probability

c=1000, shifted logits are(0,−1), true index y=2.

  1. $\ell=\log(1+e^{-1})-(-1)$.
  2. $\log(1+e^{-1})\approx 0.313262$.
  3. $\ell\approx 1.313262$ nats.

Solution 2 / 2

Interpret the result

The true class has lower logit and receives probability about 0.268941.

  1. Choose B. A is the loss if the first class had occurred.
  2. C describes an avoidable overflow in a naive computation, not the mathematical loss.
  3. The model probability is positive, so the exact loss is finite.

Blanchard, Higham & Higham (2021), §§1,4

Derivation

Stable probability computation

The gradient of log-sum-exp is softmax

Differentiate the scalar normalizer with respect to each score.

$$\frac{\partial}{\partial z_i}\log\sum_je^{z_j}=\frac{e^{z_i}}{\sum_je^{z_j}}=q_i$$
z
column vector of logits
gradient
column probability vector q

Derivation 1 / 2

Differentiate the scalar normalizer

S=Σⱼexp(zⱼ), and the logits are independent coordinates.

  1. $\partial S/\partial z_i=e^{z_i}$.
  2. $\partial\log S/\partial z_i=S^{-1}\partial S/\partial z_i=e^{z_i}/S=q_i$.

Derivation 2 / 2

Differentiate the observed-class loss

ℓ=LSE(z)−z_y; e_y is the one-hot column target.

  1. $\nabla_z\operatorname{LSE}(z)=q$.
  2. $\nabla_z z_y=e_y$, so $\nabla_z\ell=q-e_y$.
  3. The gradient components sum to 1−1=0, consistent with shared-shift invariance.

Blanchard, Higham & Higham (2021), §§1,4

Your turn

Stable probability computation

The loss gradient changes the right scores

q=(0.7,0.2,0.1). The true class is 2. Use gradient descent on logits.

$$\nabla_z\ell=q-e_2$$
e_2
one-hot target (0,1,0)
z
adjustable logits
  1. AIncrease all logits equally
  2. BIncrease class 2, decrease classes 1 and 3✓
  3. CDecrease class 2, increase classes 1 and 3

Solution 1 / 2

Subtract the target

q=(0.7,0.2,0.1) and e₂=(0,1,0).

  1. $\nabla_z\ell=(0.7,-0.8,0.1)$.
  2. Gradient descent uses $z_{new}=z-\eta\nabla_z\ell$ with η>0.
  3. The class 2 component increases because its gradient is negative.

Solution 2 / 2

Read all score changes

Classes 1 and 3 have positive gradients, so their logits decrease.

  1. Choose B. C follows ascent instead of descent.
  2. A is a shared shift and would leave probabilities unchanged.
  3. The gradient components sum tozero:0.7−0.8+0.1=0.

Blanchard, Higham & Higham (2021), §§1,4

Integrated setup

Robot synthesis

Choose the quantities before calculating them

Routes follow p=(0.8,0.2); model q=(0.6,0.4). Evaluate 100 independent preplanned trials.

Goodfellow et al., Deep Learning (2016), §3.13

Integrated solution

Robot synthesis

Information and sampling answer different parts

Course-created worked example

p=(0.8,0.2), q=(0.6,0.4), n=100 independent trials.

$$H(p)\approx 0.722,\quad H(p,q)\approx 0.854,\quad D_{\rm KL}\approx 0.132$$
values
bits per route; exact source probabilities given
SE
sqrt(0.8·0.2/100)=0.04 for route frequency

Goodfellow et al., Deep Learning (2016), §3.13

Your turn

Robot synthesis

Evaluate a changed route frequency

Source changes to p=(0.2,0.8); model stays q=(0.6,0.4). Collect a fresh fixed evaluation.

  1. AEntropy stays the same; cross entropy rises✓
  2. BBoth quantities stay the same
  3. CEntropy must increase

Solution 1 / 2

Preserve the source/model roles

p=(0.2,0.8) generates routes; q=(0.6,0.4) is unchanged.

  1. Swapping source labels leaves $H(p)\approx 0.721928$ bits.
  2. $H(p,q)=-0.2\log_20.6-0.8\log_20.4\approx 1.204936$.
  3. $D_{\rm KL}\approx 1.204936-0.721928=0.483008$ bits.

Solution 2 / 2

Interpret the change

The model now assigns its smaller probability to the more common route.

  1. Choose A. Source uncertainty is unchanged, but prediction quality worsens.
  2. B ignores which route the model favors. C confuses uncertainty with mismatch.
  3. Fresh fixed trials estimate the new source without mixing old and new regimes.

Goodfellow et al., Deep Learning (2016), §3.13

Synthesis

The reasoning path

From scoring predictions to generating actions

Probabilities support log losses. Samples support estimates. Structured density models support multiple action choices.

Goodfellow et al., Deep Learning (2016), §3.13

Sources

References

Probability and information

  1. Goodfellow, Bengio & Courville. Deep Learning. MIT Press, 2016. §§3.3,3.8,3.9,3.13,5.5.
  2. Shannon. A Mathematical Theory of Communication. Bell System Technical Journal, 1948. §§6,9–12.
  3. UC Berkeley. CS70 Note18: Chebyshev inequality and large numbers. 2017.

Original course examples and redraws. No source figures reproduced. Course materials: CC BY-NC 4.0.

Sources

References

Sampling, density and numerical methods

  1. Sheffield. MIT 18.175, Lecture 14, 2016. pp.34–35.
  2. Wasserman. Density Estimation. CMU 36-708. §§1,3–4.
  3. Blanchard, Higham & Higham. Log-Sum-Exp and Softmax. IMA J. Numer. Anal., 2021. §§1,4.
  4. Howard et al. Time-uniform Chernoff bounds. Probability Surveys 17, 2020.

Original course examples and redraws. No source figures reproduced. Course materials: CC BY-NC 4.0.

← → · o overview · p print