16--28 Active Final Sheet

16. Continuous Information Measures

Trigger: continuous variables / Gaussian information formulas / reparameterization.

Differential entropy

• Can be negative.
• Not invariant to coordinate transformations.
• For \(x=g(s)\),

  \[ h(x)=h(s)+\mathbb E[\log |g'(s)|]. \]

• Multivariate:

  \[ h(\mathbf x)=h(\mathbf s)+\mathbb E[\log|\det J_g(\mathbf s)|]. \]

Mutual information and KL

• \(I(x;y)\ge0\), \(D(p\|q)\ge0\).
• \(I,D\) are coordinate-free / invariant to invertible reparameterization.
• Conditioning still does not increase differential entropy on average:

  \[ h(x|y)\le h(x). \]

Gaussian formulas

Scalar:

Vector:

Scalar jointly Gaussian:

Vector jointly Gaussian:

If \(\rho_k\) are the singular values of \(B_{xy}\), then

Equal covariance Gaussian KL:

General Gaussian KL:

17. Maximum Entropy Distributions

Trigger: “least biased distribution” subject to constraints.

For finite \(\mathcal Y\),

Thus

If constraints are linear:

then the maximum entropy solution has exponential-family form:

with \(x\) chosen so the constraints hold.

Templates:

• No constraints on finite alphabet:

  \[ p^*=U(\mathcal Y). \]

• Given marginals \(p_{y_1},p_{y_2}\):

  \[ p^*(y_1,y_2)=p_{y_1}(y_1)p_{y_2}(y_2). \]

• Given overlapping pairwise marginals \(p_{12},p_{23}\):

  \[ y_1\leftrightarrow y_2\leftrightarrow y_3, \qquad p^*(y_1,y_2,y_3)=\frac{p_{12}(y_1,y_2)p_{23}(y_2,y_3)}{p_2(y_2)}. \]

• Fixed mean on \(\mathbb R_+\): exponential distribution.
• Fixed mean and variance on \(\mathbb R\): Gaussian.
• Fixed covariance on \(\mathbb R^K\): multivariate Gaussian.

18. Conjugate Priors

Trigger: repeated Bayesian updates / posterior family stays same.

Bayes update:

Beta-Bernoulli

After \(N\) observations:

Predictive:

• \(\alpha=\beta=1\): Laplace estimate.
• \(\alpha=\beta=1/2\): Krichevsky-Trofimov estimate.
• \(\alpha,\beta\to0\): ML-like estimate.

Exponential family conjugacy

If

then natural conjugate prior:

After data \(y_1,\ldots,y_N\):

19. Information Geometry of ML and EM

Trigger: empirical distribution / latent variables / exponential-family ML.

ML as reverse I-projection

For iid finite data,

Therefore

Exponential-family ML

If

then ML satisfies

EM

Complete data \(z\), observed data \(y=g(z)\).

Algorithm:

1. E-step: compute \(p_{z|y}(\cdot|y;\hat x^{(l-1)})\).
2. M-step:

   \[ \hat x^{(l)} = \arg\max_x U(x;\hat x^{(l-1)}). \]

Geometry:

20. Stochastic Approximation

Trigger: partition functions / expectations / samples are hard.

Monte Carlo

Importance sampling

Suppose

Weights:

Estimator:

Why:

Failure mode: \(q\) tiny where \(p|f|\) large \(\Rightarrow\) huge weights \(\Rightarrow\) bad effective sample size.

Rejection sampling

Need

Exact but often awful in high dimension because \(c\) is global.

Metropolis-Hastings

Proposal \(v(x'|x)\). Acceptance:

Symmetric proposal:

Detailed balance:

Detailed balance implies \(p\) is stationary.

21. Typical Sequences and Large Deviations

Trigger: iid sequence / typical set / compression / rare sample average.

AEP

For \(y^N\sim p^N\),

Since

Typical set:

AEP:

Divergence typicality

If samples are generated by \(q\), then probability of looking \(p\)-typical:

So independent \(x^N,y^N\) are jointly typical wrt \(p_{x,y}\) with probability

Cramer's theorem

For \(y_i\sim q\), statistic \(t\), and \(\gamma>\mu=E_q[t]\):

Dominant tilted distribution:

where \(x>0\) is chosen so that

Rate:

22. Method of Types and Sanov

Trigger: finite alphabet + empirical distribution/type event.

Type:

Type class:

Facts:

Sanov

For event

The minimizer

is the I-projection of \(q\) onto \(S\).

Template:

1. Convert event into \(S\subset\mathcal P^\mathcal Y\).
2. Find \(p^*=\arg\min_{p\in S}D(p\|q)\).
3. Probability exponent is \(D(p^*\|q)\).

23. Asymptotics of Hypothesis Testing

Trigger: iid binary hypothesis test.

Normalized LLR:

Under \(H_0\):

Under \(H_1\):

LRT:

For

define

where

Then

Stein / Neyman-Pearson

Fixed \(P_F\le\alpha\), \(0<\alpha<1\):

Bayesian

For positive priors/costs:

Optimal exponent balances:

Equivalently:

24. Sequence Convergence

Trigger: proving asymptotic estimator results.

Modes

Convergence in divergence:

Almost sure means sample path eventually stays close:

Convergence in probability means one late sample is probably close.

Useful theorems

Continuous mapping:

for continuous \(g\), preserving the same convergence mode.

Slutsky:

CLT:

ULLN:

25. Asymptotics of Parameter Estimation

Trigger: ML consistency / efficiency / posterior normality.

Definitions

Consistency:

Asymptotic normality:

Asymptotic efficiency:

ML empirical divergence

ML minimizes \(\hat D_N(a)\). For fixed \(a\):

If convergence is uniform and model identifiable, ML is consistent.

Exponential-family ML efficiency

Scalar exponential family:

ML satisfies:

CLT:

Taylor:

Slutsky:

Mismatched ML

If true distribution \(q\) is outside model class:

Posterior asymptotics

Laplace:

Posterior:

Local coordinate:

26. Asymptotics of Inference and Universality

Trigger: sequential prediction with unknown true model.

Average prediction loss:

Universal:

Universal prediction theorem:

Capacity asymptotics

Finite family:

Regular \(d\)-parameter family:

Jeffreys prior:

Since \(C_N=O(\log N)\),

Misspecification

If true \(q\) is outside the class:

so prediction loss cannot vanish.

Universality over classes

For mixtures over model classes,

If truth lies in class \(\mathcal P_m\), then

So the hyper-prior class penalty vanishes for fixed \(m\).

27. Model Order Selection

Trigger: choose one model class/order, hard decision.

Nested classes:

Naive generalized ML:

overfits because richer classes fit at least as well.

Evidence:

Laplace gives BIC.

Maximize:

Equivalently minimize:

AIC:

Comparison:

• BIC: model-identification flavored; assumes truth is in one class.
• AIC: prediction/approximation flavored; allows misspecification.

28. Variational Inference

Trigger: partition function/evidence/posterior too hard.

If

then

Proof identity:

Restrict \(q\in Q\):

The variational optimizer solves:

Mean-field

Common tractable family:

This can underrepresent dependence / uncertainty because \(D(q\|p)\) is mode-seeking.

ELBO

Latent variable model:

For any \(q(s)\),

Thus

Equivalent:

EM relation

Exact EM:

makes the bound tight, then M-step maximizes it over \(x\).

Variational EM: restrict \(q\in Q\), so E-step chooses the best approximate posterior.

I. Motivation / Decision Tree

Decision Tree

Problem Pattern Map for Lectures 16--28

How to Use This

For each problem, first classify the problem type. Then apply the corresponding template.

Pattern 1: Continuous / Gaussian Information

Trigger: problem gives Gaussian variables and asks for \(h\), \(I\), or \(D\).

Template:

1. Identify scalar vs vector.
2. Identify covariance / conditional covariance.
3. Plug into Gaussian formula.

Scalar jointly Gaussian:

Vector jointly Gaussian:

Gaussian KL:

Common mistake: forgetting unequal-covariance trace/log-det terms.

Pattern 2: Max Entropy Under Constraints

Trigger: “maximum entropy distribution subject to constraints.”

Template:

1. Write constraints as \(E_p[t_k(y)]=\bar t_k\).
2. State max entropy solution:

   \[ p^*(y)=\exp\left\{\sum_k x_kt_k(y)-\alpha(x)\right\}. \]

3. Solve \(x_k\)'s from the constraints if needed.

Special cases:

Common mistake: max entropy under moment constraints is not “choose uniform” unless no constraints exist.

Pattern 3: Conjugate Prior Update

Trigger: Bayesian repeated updates / Beta prior / exponential-family prior.

Template for Beta-Bernoulli:

Then

Predictive:

Template for exponential family:

Natural conjugate prior:

Update:

Common mistake: treating \(\alpha,\beta\) as ordinary parameters rather than pseudo-counts / hyperparameters.

Pattern 4: ML as KL Projection

Trigger: iid finite data + ML estimate / empirical distribution.

Template:

1. Compute empirical distribution:

   \[ \hat p_y(b)=\frac1N\sum_i1_{y_i=b}. \]

2. Rewrite normalized likelihood:

   \[ \frac1N\log p(y^N;x) = -D(\hat p_y\|p_y(\cdot;x))-H(\hat p_y). \]

3. Therefore:

   \[ \hat x_{\mathrm{ML}} = \arg\min_xD(\hat p_y\|p_y(\cdot;x)). \]

Common mistake: wrong KL direction. ML uses

not

Pattern 5: Exponential-Family ML Moment Matching

Trigger: ML in exponential family.

Template:

1. Write log-likelihood:

   \[ \ell(x)=x^T\sum_i t(y_i)-N\alpha(x)+\text{const}. \]

2. Differentiate:

   \[ 0=\frac1N\sum_i t(y_i)-\nabla\alpha(x). \]

3. Use

   \[ \nabla\alpha(x)=E_x[t(Y)]. \]

4. Conclude:

   \[ \frac1N\sum_i t(y_i)=E_{\hat x}[t(Y)]. \]

Common mistake: forgetting \(\beta(y)\) disappears for ML because it does not depend on \(x\).

Pattern 6: EM / Latent Variable Problem

Trigger: hidden/missing variables \(s\), complete data \(z=(y,s)\), EM-MAP/EM-ML.

Template:

EM-ML:

EM-MAP:

Common steps:

1. Define complete data \(z=(y,s)\).
2. Compute posterior responsibility \(p(s|y;x')\).
3. Take expectation of complete-data log-likelihood.
4. Maximize wrt \(x\).

Common mistake: using \(p(s|y;x)\) inside the E-step. E-step uses old parameter \(x'\).

Pattern 7: Importance Sampling / Rejection / MH

Trigger: approximate \(E_p[f]\), sample from hard \(p\), partition function unknown.

Importance sampling template:

Check:

MH template:

If symmetric:

Common mistake: MH only needs \(p^\circ\), not \(Z_p\).

Pattern 8: AEP / Typical Set

Trigger: typical sequence, compression, number of likely sequences.

Template:

Then:

Compression:

Common mistake: confusing total number of sequences \(2^{N\log|\mathcal Y|}\) with typical number \(2^{NH(p)}\).

Pattern 9: Joint Typicality / Classification

Trigger: jointly typical pairs \((x^N,y^N)\), random codebook/features, distinguish many classes.

Template: If \(\tilde x^N\sim p_x^N\) and \(\tilde y^N\sim p_y^N\) independently, then

If there are \(M\) wrong classes:

If

and