1. 2/3/26: Introduction

Humans are bad at random selection. Bell Labs made a machine, Shannon's Outguessing Machine, that was able to exploit any human's inherent bias.

We want to be able to extrapolate a low-dimension feature from data, similar to machine learning.

2. 2/5/26: Bayesian Hypothesis Testing

2.1. Semantics

• $H$ (or $X$): underlying phenomenon / state of the world we care about (can be deterministic or random).
• $Y$: observed data (random).
• $\hat{H} = f(Y)$: a decision rule (a.k.a. estimator / classifier) mapping data to a hypothesis.

Core issues in inference:

• model the phenomenon,
• model the observation mechanism,
• design processors (decision rules),
• analyze performance.

Today: $H$ is binary-valued. Focus on hypothesis testing / binary classification / decision theory.

2.2. Notation

Let the hypothesis set be $\mathcal{H} = \{H_0, H_1\}$. We refer to $\mathcal{H}$ as the model family. (Often $H_0$ is called the null hypothesis.)

We refer to the realized observation $y$ as test data. (Data alphabet: $y \in \mathcal{Y}$; $Y$ may be continuous or discrete.)

2.3. Bayesian Binary Hypothesis Testing Model

A Bayesian binary testing problem is specified by:

• a priori information:

  \[ P_0 \triangleq \mathbb{P}(H = H_0), \qquad P_1 \triangleq \mathbb{P}(H = H_1) = 1 - P_0. \]

• observation model under each hypothesis (likelihoods):

  \[ p_{y|H}(y \mid H_0), \qquad p_{y|H}(y \mid H_1). \]

Two equivalent “directions” to describe the model:

• Forward: $p_{y|H}$ and $p_H$ (equivalently the joint $p_{y,H}$).
• Backward: $p_{H|y}$ and $p_y$.

2.4. Bayesian Performance Criterion (Bayes Risk)

Let $C(H, f(y))$ be the cost of deciding $\hat{H}=f(y)$ when the truth is $H$. For shorthand, $C(H_i, H_j) \triangleq C_{ij}$ (truth $H_i$, decision $H_j$).

The optimal decision rule minimizes expected cost:

where $\varphi(f)$ is the Bayes risk.

Derivation (pointwise minimization)
Using iterated expectation,

Since $p_y(y)\ge 0$, minimizing $\varphi(f)$ is achieved by minimizing the conditional risk for each fixed $y$.

Fix an observation $y_*$. If we decide $\hat{H}(y_*) = H_0$, the conditional risk is

and if we decide $\hat{H}(y_*) = H_1$,

Choose the decision with smaller conditional risk. Rearranging yields an equivalent test in terms of posterib odds:

(Assume a valid cost assignment so denominators are positive.)

2.5. Posterior (Bayes' Rule)

The a posteriori probabilities are

2.6. Likelihood Ratio Test (LRT)

Substituting the posterior into the odds test gives the Likelihood Ratio Test:

• The optimal processor is deterministic (threshold test).
• $\mathcal{L}(y)$ is scalar-valued even if $y$ is high-dimensional.
• Often easier to implement than reasoning directly in the $y$-space.

Implementation / “intractability” intuition:

• The induced decision regions in the original observation space $\mathcal{Y}$ can be geometrically messy (even disconnected), but the LRT maps $y \mapsto \mathcal{L}(y)\in\mathbb{R}$ so the decision is just “left vs. right of a threshold”.
• Any strictly increasing transform of $\mathcal{L}(y)$ is equivalent (same decisions). In particular, using the log-likelihood ratio \[ \ell(y) \triangleq \log \mathcal{L}(y) \]

  is common because it improves numerical stability and often simplifies algebra.

• Practical “NN / modern ML” angle: the exact likelihoods $p_{y|H}(y\mid H_i)$ are often unknown or too hard to compute, so we learn a scoring function $s_\theta(y)$ that acts like a learned log-likelihood ratio and then threshold it.

2.7. Special Case: Minimum Probability of Error (0--1 Loss)

If

then $\varphi(f) = \mathbb{P}(\hat{H}(Y)\neq H)$, i.e. minimizing Bayes risk is minimizing error probability (max accuracy).

2.8. MAP and ML Rules

Maximum a Posteriori (MAP) rule (general priors):

Maximum Likelihood (ML) rule (equal priors $P_0=P_1$):

• ML note: ML optimizes $p(y\mid \theta)$ directly, so it avoids Bayesian normalization; a posterior $p(\theta\mid y)$ is not defined without choosing a prior, and MAP reduces to ML only under a constant prior in that parameterization.

2.9. Literature Note: “Features” and “Embeddings”

A real-valued function of the data (e.g. $\mathcal{L}(y)$ or $\ell(y)$) is a statistic. In ML language, such functions are often called features (especially for continuous data); when the data are discrete, people sometimes say embeddings. In Bayesian binary testing, $\mathcal{L}(y)$ (or any invertible transform) is a sufficient statistic for optimal decision-making.

For binary labels $Y\in\{0,1\}$ and observation $x$,

where $\sigma(t)=\frac{1}{1+e^{-t}}$.

Discriminative view (sigmoid + cross-entropy):

• Model form:

  \[ q_\theta(x)=\sigma(g_\theta(x)). \]

• Training with binary cross-entropy pushes
  \[ q_\theta(x)\approx p(Y=1\mid x), \]

  so the learned score satisfies

  \[ g_\theta(x)\approx \log\frac{p(Y=1\mid x)}{p(Y=0\mid x)} \]

• If a correct generative model exists, then
  \[ \log\frac{p(Y=1\mid x)}{p(Y=0\mid x)} = \log\frac{p(x\mid Y=1)}{p(x\mid Y=0)} + \log\frac{p(Y=1)}{p(Y=0)}. \]

  So: posterior log-odds = log-likelihood ratio + prior log-odds.

• Geometry: this score is affine in $x$ only under extra assumptions (e.g. Gaussian class-conditionals with equal covariance). With unequal covariances, the Bayes-optimal score is typically quadratic in $x$.
  Proof. For reference, a Gaussian density with covariance form is \[ p(x\mid y=c)=\frac{1}{\sqrt{(2\pi)^d\det\Sigma_c}}\, \exp\!\left( -\frac{1}{2}(x-\mu_c)^\top\Sigma_c^{-1}(x-\mu_c) \right). \]

  When \(\Sigma_0=\Sigma_1=\Sigma\), the shared \(x^\top\Sigma^{-1}x\) terms cancel:

  \[ \log\frac{p(x\mid 1)}{p(x\mid 0)} = \frac{1}{2}(x-\mu_0)^\top\Sigma^{-1}(x-\mu_0) - \frac{1}{2}(x-\mu_1)^\top\Sigma^{-1}(x-\mu_1) + \text{const}, \]

  leaving \(x^\top\Sigma^{-1}(\mu_1-\mu_0)\) plus constants, hence linear log-odds.

3. 2/10/26: Non-Bayesian Decision Theory & Hypothesis Testing

3.1. Classification Performance Measures

Problem with Bayesian: priors/costs may be difficult to assign, e.g. medical diagnostics and detecting extraterrestrial life. We will see later from Neyman--Pearson that any good test comes in the form of an LRT:

The performance of any decision rule $\hat{H}(\cdot)$ may be fully specified in terms of the detection and false-alarm probabilities (in statistics, the “power” and “size” of the test):

3.2. Operating Characteristic of the LRT

A good decision rule has large $P_{\mathrm{D}}$ and low $P_{\mathrm{F}}$, but decreasing the threshold $\eta$ to increase $P_{\mathrm{D}}$ comes at the expense of increasing $P_{\mathrm{F}}$. To visualize the trade-off, consider the operating characteristic (OC) curve: plot $(P_{\mathrm{F}}(\eta),\, P_{\mathrm{D}}(\eta))$ while varying $\eta$ from $0$ to $\infty$.

The Bayesian hypothesis test corresponds to a point on this curve. In general, the Bayes risk looks like

where $\eta_B$ is set as

Setting the risk to a constant yields lines of fixed slope $\eta_B$. Hence we want the highest such line that still intersects the OC-LRT:

Properties of the OC-LRT:

• The OC-LRT is monotonically nondecreasing

3.3. Neyman--Pearson Hypothesis Testing

A popular alternative formulation to BHT, used when difficult to choose costs for a decision problem:

Note that $\alpha$ is not treated as a random variable.

Proof sketch (greedy/intuitive justification). We want to include as many $y$ values in the $H_1$ region as possible while respecting the false-alarm constraint. Among all $y$ with a given contribution to $P_{\mathrm{F}}$, those with the largest $\mathcal{L}(y)$ give the biggest boost to $P_{\mathrm{D}}$, so a threshold test on $\mathcal{L}$ is optimal. $\square$

3.4. (Extra) Relation to Significance Tests

Since p-values are monotone transforms of LRT, we can reparametrize the LRT using $g(\cdot) = P_F(\cdot)$ and define

Since $P_{\mathrm{F}}$ and $P_{\mathrm{D}}$ are strictly decreasing functions of $\eta$, we can let $p = P_{\mathrm{F}}(\mathcal{L}(y))$, flip the direction of the inequality, and recover a p-value and significance test.

3.5. Performance Limits: LRs with Discrete Components

When $\mathcal{L}(y)$ has discrete components, the OC-LRT may consist of isolated points rather than a smooth curve.

Example. [Example 4.1] Consider binary-valued data $y \in \mathcal{Y} = \{0,1\}$, where the probability mass functions are \[ p_{y|H}(y \mid H_0) = \begin{cases} 1/2 & y=0, \\ 1/2 & y=1, \end{cases} \qquad p_{y|H}(y \mid H_1) = \begin{cases} 2/3 & y=0, \\ 1/3 & y=1. \end{cases} \]

Then the likelihood ratio is

\[ \mathcal{L}(y) = \begin{cases} 4/3 & y=0, \\ 2/3 & y=1. \end{cases} \]

The LRT with threshold $\eta$ yields the false-alarm and detection probabilities

\[ P_{\mathrm{F}}(\eta) = \begin{cases} 0 & 4/3 < \eta, \\ 1/2 & 2/3 < \eta \le 4/3, \\ 1 & \eta \le 2/3, \end{cases} \qquad P_{\mathrm{D}}(\eta) = \begin{cases} 0 & 4/3 < \eta, \\ 2/3 & 2/3 < \eta \le 4/3, \\ 1 & \eta \le 2/3. \end{cases} \]

The operating characteristic consists of exactly three $(P_{\mathrm{F}}, P_{\mathrm{D}})$ points: $(0,0)$, $(1/2, 2/3)$, and $(1,1)$.

4. 2/10/26: Performance Limits of Hypothesis Testing

Effect on Bayesian LRT. When the likelihood ratio has point masses, equality $\mathcal{L}(y) = \eta$ may occur with nonzero probability. The Bayes risk is the same for either decision at equality, meaning there may be multiple operating points on the OC-LRT corresponding to the optimum Bayesian rule. When equality occurs with probability zero, there is a unique operating point.

Effect on Neyman--Pearson LRT. There may not exist a threshold $\eta$ that yields $P_{\mathrm{F}}(\eta) = \alpha$ exactly. Then the NP problem corresponds to the OC-LRT point whose $P_{\mathrm{F}}$ is the largest value smaller than $\alpha$. However, the resulting curve can't lie below the line $P_{\mathrm{D}} = P_{\mathrm{F}}$ (random guessing):

4.1. Improving Via Randomization

We can improve the test via randomization. Consider the test:

where $\hat{H}_1, \hat{H}_2$ are NP-LRTs with thresholds $\eta'$ and $\eta''$ respectively. Then $P_{\mathrm{F}} = \gamma\, P_{\mathrm{F}}(\eta') + (1-\gamma)\, P_{\mathrm{F}}(\eta'')$ (and same for $P_{\mathrm{D}}$). Hence we can linearly interpolate between any two points on the OC-LRT to obtain the convex hull.

We can write the prediction $\hat{H}$ as a conditional distribution:

By taking $\eta'' - \eta'$ sufficiently small, we get the point-mass splitting form of the randomized LRT:

For example, if $P_{\mathrm{F}}$ jumps from $\alpha_1$ to $\alpha_2$ at $\eta'$, there must exist a point mass at $\mathcal{L}(y)=\eta'$ with mass $\alpha_2 - \alpha_1$. Applying point-mass splitting with randomization probability $p$ lets us hit any $P_{\mathrm{F}} \in [\alpha_1, \alpha_2]$.

4.2. Randomized Tests

We chose a randomized test that picks one of two thresholds. Is there some other type of randomized test that has better performance? We have the Markov chain

which is to say that $\hat{H}$ depends only on $Y$ and not directly on $H$.

We refer to the dependence of the best achievable $P_{\mathrm{D}}$ on $\alpha$ as the Neyman--Pearson function: $P_{\mathrm{D}}^{\mathrm{NP}}(\alpha)$ or $\zeta_{\mathrm{NP}}(\alpha)$.

4.3. Efficient Frontier of Operation

Since $P_{\mathrm{D}}^{\mathrm{NP}}(\alpha)$ is nondecreasing, the efficient frontier is at best the convex hull of the OC-LRT points.

Some facts from optimality:

• The Neyman--Pearson function lies above the line $P_{\mathrm{D}} = P_{\mathrm{F}}$ since it is better than the randomized decision rule $\hat{H}(y) = H_1$ with probability $\alpha$.
• The Neyman--Pearson function is concave. Otherwise we could create a new rule using interpolation and get a better rule.
• IMPORTANT: The slope of the Neyman--Pearson function equals the threshold of the corresponding LRT:
  \[ \frac{dP_{\mathrm{D}}^{\mathrm{NP}}}{d\alpha}\bigg|_{\alpha = P_{\mathrm{F}}(\eta)} = \eta. \]

  Proof sketch. Let $\mathcal{Y}_1(\eta) = \{y : \mathcal{L}(y) \ge \eta\}$. Writing $P_D$ and $P_F$ as integrals over the likelihood ratio distribution under $H_0$:

  \[ P_D(\eta) = \int_\eta^\infty L\, p_{L|H}(L|H_0)\,dL, \qquad P_F(\eta) = \int_\eta^\infty p_{L|H}(L|H_0)\,dL. \]

  Differentiating with respect to $\eta$ (Leibniz rule):

  \[ \dot{P}_D(\eta) = -\eta\, p_{L|H}(\eta|H_0), \qquad \dot{P}_F(\eta) = -p_{L|H}(\eta|H_0). \]

  By the chain rule $\dot{\zeta}_{\mathrm{NP}}(P_F(\eta))\cdot\dot{P}_F(\eta) = \dot{P}_D(\eta)$, so:

  \[ \dot{\zeta}_{\mathrm{NP}}(P_F(\eta)) = \frac{\dot{P}_D(\eta)}{\dot{P}_F(\eta)} = \frac{-\eta\,p_{L|H}(\eta|H_0)}{-p_{L|H}(\eta|H_0)} = \eta. \qquad\square \]

4.4. Region of Achievable Operating Points

Having characterized the efficient frontier $\mathcal{F}_{P|H}$ via the Neyman-Pearson function $\zeta_{\mathrm{NP}}(\cdot)$, we now describe the full region of $(P_F, P_D)$ pairs achievable by some decision rule.

If decision rule $\tilde{H}_*(y)$ achieves $(P_F^*, P_D^*)$ on the efficient frontier, then the reversed rule $\tilde{H}_{**}$ (flip 0/1 outputs) achieves:

This gives the reflected frontier:

the mirror image of $\mathcal{F}_{P|H}$ across $P_F = P_D = 1/2$, which provides a lower bound on achievable $P_D$ for a given $P_F$.

Any point between $\mathcal{F}_{P|H}$ and $\bar{\mathcal{F}}_{P|H}$ is achievable via a randomized decision rule that randomly selects between one rule on each frontier. Therefore the achievable region is the convex hull of the OC-LRT and its reflection:

4.5. Bayesian Tests Revisited

A deterministic rule (LRT) is always sufficient for the Bayesian criterion. The achievable region gives geometric intuition for why:

• The Bayesian operating point is where an equi-Bayes-risk line (slope determined by priors and costs) is tangent to the efficient frontier. Typically this is a unique point, and the optimal rule is a single LRT.
• However, if the equi-Bayes-risk line is parallel to a segment of the efficient frontier, any point on that segment is optimal — including the endpoints, which are two different LRTs. All rules achieving those points share the same Bayes risk, and randomizing between them is also optimal.
• When the OC-LRT is discontinuous (jumps over a segment), there can be randomized tests that hit interior points of the achievable region that no single LRT can reach, and these may also be Bayes-optimal.

So while deterministic rules always suffice, non-uniqueness arises geometrically whenever the risk line aligns with a flat part of the frontier.

5. 2/12/26: Minimax Hypothesis Testing

5.1. Motivation

With both Bayes and Neyman--Pearson testing, we are able to justify costs, but it is often difficult to justify priors. The minimax criterion applies when we are able to meaningfully assign (valid) costs $C_{ij} = C(H_i, \hat{H}_j)$ for $i, j \in \{0, 1\}$, but not a prior.

5.2. Minimax Criterion

We allow nature to pick the most detrimental prior regardless of our decision rule, even if it is randomized.

A randomized decision rule can be written as a function $r:\mathcal{Y}\to[0,1]$ where $r(y)=\mathbb{P}(\hat{H}=H_1\mid Y=y)$. Define the conditional risks

Then the Bayes risk under prior $p=\mathbb{P}(H=H_1)$ is

Our solution $r_M(\cdot)$ (the optimum randomized decision rule $\hat{H}_M$) is the solution to the minimax problem:

Equalizer rule is a decision rule $r$ for which $\varphi_0(r)$ and $\varphi_1(r)$ are equal. (Then $\varphi(p,r)$ does not depend on $p$.)

Example. [Example 5.1 (0--1 loss picture)] Consider the likelihood ratio test and set threshold to $\eta(p)=\frac{1-p}{p}$ (this corresponds to $0$--$1$ loss). The probability of error is \[ P_{\mathrm{E}}(p) = (1-p)\,P_{\mathrm{F}}\!\Big(\tfrac{1-p}{p}\Big) + p\Big(1-P_{\mathrm{D}}\!\Big(\tfrac{1-p}{p}\Big)\Big). \]

The blue curve denotes how our error probability varies with the prior $p$. The minimax decision rule is the black horizontal line.

When mismatched (we tune the threshold as if the prior were $q$), our error probability is

\[ P_{\mathrm{E}}(p;q) = (1-p)\,P_{\mathrm{F}}\!\Big(\tfrac{1-q}{q}\Big) + p\Big(1-P_{\mathrm{D}}\!\Big(\tfrac{1-q}{q}\Big)\Big). \]

Each mismatched rule gives a straight line in $p$. The Bayes-optimal curve is the concave lower hull of those lines.

Theorem. [Minimax Theorem (0--1 loss)] The minimax decision rule is the equalizer rule. In the ROC picture under $0$--$1$ loss, the equalizer condition is \[ \varphi_0=\varphi_1 \quad \Longleftrightarrow \quad P_D = 1 - P_F, \]

so the optimum operating point is the intersection of the OC-LRT (efficient frontier) and the line $P_D=1-P_F$.

Preliminaries. Let $\mathcal{L}(y)=\frac{p_{Y|H}(y\mid H_1)}{p_{Y|H}(y\mid H_0)}$. The Bayes LRT threshold for prior $p$ is

and we may randomize on the boundary (needed only when $\mathbb{P}(\mathcal{L}(Y)=\eta(p)\mid H_i)>0$):

Mismatched Bayes Risk Let the true prior be $p$, but we use the Bayes rule tuned to $q$ (and $\lambda$ on the boundary):

Writing in terms of $P_F(q,\lambda)$ and $P_D(q,\lambda)$,

5.3. Properties of $\varphi_B(p,q,\lambda)$ and $\varphi_B^*(p)$

Define the Bayes envelope

• $\varphi_B(p,q,\lambda)$ is a linear function of $p$ (for fixed $(q,\lambda)$).
  Proof. For fixed $(q,\lambda)$, define \[ A(q,\lambda) \triangleq C_{00}(1-P_F(q,\lambda)) + C_{10}P_F(q,\lambda), \quad B(q,\lambda) \triangleq C_{01}(1-P_D(q,\lambda)) + C_{11}P_D(q,\lambda). \]

  Then

  \[ \varphi_B(p,q,\lambda)=(1-p)A(q,\lambda)+pB(q,\lambda) = A(q,\lambda)+p\big(B(q,\lambda)-A(q,\lambda)\big), \]

  so it is affine in $p$.

• For all $p$ and all $(q,\lambda)$, $\varphi_B(p,q,\lambda)\ge \varphi_B^*(p)$. Moreover, when matched ($q=p$), $\varphi_B(p,p,\lambda)=\varphi_B^*(p)$.
• $\varphi_B^*(\cdot)$ is concave and continuous on $[0,1]$ (lower envelope of affine functions).
  
• $\varphi_B^*(0)=C_{00}$ and $\varphi_B^*(1)=C_{11}$. (At $p=0$, the Bayes rule always picks $H_0$ so $P_F^B(0,\lambda)=0$; at $p=1$, it always picks $H_1$ so $P_D^B(1,\lambda)=1$.)

5.4. Minimax Inequality

Intuition. Think of a zero-sum game: player A minimizes $g$ by choosing $a$, player B maximizes by choosing $b$. The left side is the outcome when B moves last (better for B); the right side is when A moves last (better for A). It is always preferable to move last, so $\min\max \ge \max\min$.

Note: Every point on the NP efficient frontier is achievable by some Bayes LRT for an appropriate $(p, \lambda)$.

5.5. Minimax Decision Rule

This exhibits a saddle point:

6. 2/19/26: Bayesian Parameter Estimation

6.1. Motivation

Up to hypothesis testing, the unknown was essentially a discrete label (“which world are we in?”). Lecture 6 reframes that: many real problems aren’t “H0 vs H1,” they’re “what is the parameter/value?”. They are often high dimensional, and possibly continuous.

Applications of Poisson model:

• Rate of asteroid impact on launch
• Rate of climate change
• Rate of goals in hockey, soccer, etc.
• Transportation: air and ground

Recall, in the Bayesian framework, there is an a priori distribution $p_x(·)$ for the unknown parameter. This represents our belief about $x$ prior to any observation of the measurement $y$. In addition, the data model $p_{y|x}(·|·)$ fully specifies the way in which $y$ contains information about $x$.

So far we considered $x = H = \{H_0, H_1\}$. This could be extended for $x$ to include $\infty$ alphabet (e.g. $\mathbb{Z}^+$ or $\mathbb{R}^L$) for continuous parameters.

6.2. Bayesian Parameter Estimation

As in hypothesis tesing, $x$ is modeled as random. Given model $p_{y|x}(·|·)$ for our data $y$ and prior $p_x(·)$ for parameters, this gives a complete statistical characterization of the problem.

6.3. Bayes Risk Criteria for Estimation

One might have to make a decision (observation) about the parameter $x$ given the data $y$.

We choose our estimator to be the function $f(y)$ that minimizes the Bayes risk $E[C(x,f(y))]$.

which means we choose $\hat{x}$ to be

6.4. Minimum Absolute-Error Estimation

A possible choise for our cost function is

When the unknown parameter is a vector, the natural “absolute error” cost is the L1 distance.

6.5. Maximum A Posteriori Estimation

A possible choise for our cost function is

As $\epsilon \to 0$, this becomes the maximum a posteriori estimator (MAP), which is the mode of the posterior distribution.

When unknown parameter is a vector, the natural 0-1 cost is the L0 distance.

6.6. Minimum Mean-Square Error Estimation

The mott common cost function is the squared error, or Bayes least squares:

When unknown parameter is a vector, the natural “squared error” cost is the L2 distance.

6.7. Bayesian Decomposition of MSE

The error $e(x,y) = \hat{x}(y) - x$ can be expressed as $b+(e(x,y)-b)$, where

The MSE = $\mathbb{E}[e(x,y)^2] = \mathbb{E}[(e(x,y)-b)^2] + b^2$. We denote $\mathbb{E}[(e(x,y)-b)^2]=\Lambda_e$, the error covariance matrix.

• The BLS estimator is unbiased: $\mathbb{E}[\hat{x}_{\mathrm{BLS}}(y) - x] = 0$.

  \[ b_{\mathrm{BLS}} = \mathbb{E}[e(x,y)] = \mathbb{E}\!\left[\hat{x}_{\mathrm{BLS}}(y)-x\right] = \mathbb{E}\!\left[\mathbb{E}[x\mid y]\right]-\mathbb{E}[x] = 0. \]

• $\Lambda_{BLS}=\mathbb{E}[\Lambda_{x|y}(y)]$.
  \[ \Lambda_{\mathrm{BLS}} \triangleq \Lambda_e = \mathbb{E}\!\left[ ee^{\mathsf T} \right] = \mathbb{E}\!\left[ \bigl(x-\mathbb{E}[x\mid y]\bigr)\bigl(x-\mathbb{E}[x\mid y]\bigr)^{\mathsf T} \right]. \]

  Applying iterated expectation,

  \[ \Lambda_{\mathrm{BLS}} = \mathbb{E}\!\left[ \mathbb{E}\!\left[ \bigl(x-\mathbb{E}[x\mid y]\bigr)\bigl(x-\mathbb{E}[x\mid y]\bigr)^{\mathsf T} \;\middle|\; y \right] \right]. \]

  gives, $\Lambda_{\mathrm{BLS}}=\mathbb{E}[\Lambda_{x|y}(y)]$.

6.8. Orthogonality Characterization of BLS Estimators

6.9. Remarks

Robustness: BLS is sensitive to outliers. A common solution is using a robust estimator, that behaves like L2 estimator for small errors but L1 estimator for large errors.

Huber loss:

which is continuously differentiable in $|\hat{x}-x|$.

6.10. Implementation Architectures and Hypothesis Classes

The optimal Bayesian estimator is often intractable when $\mathbf{x}, \mathbf{y}$ are high-dimensional. Instead, restrict to a parametric class $\mathbf{f}_\theta(\cdot)$ and optimize over $\boldsymbol{\theta}$:

Common architecture choices:

• Linear: $\mathbf{f}_\theta(\mathbf{y}) = A\mathbf{y} + \mathbf{d}$
• Neural networks: layers of linear maps + nonlinear activations; $\boldsymbol{\theta}$ can be billions of parameters

6.11. Covariance Inequalities

7. 2/20/26: Linear Least-Squares Estimation

7.1. Motivation

In Bayesian least-squares (BLS), the optimal estimator for squared error is the conditional mean

but computing it typically requires the full posterior $p_{\mathbf{x}\mid \mathbf{y}}(\mathbf{x}\mid \mathbf{y})$, which in turn requires full knowledge of the joint model (prior + likelihood) and may be computationally intractable in high dimensions.

A common approximation is to restrict the estimator class to something implementable and learnable from limited statistics. Here: restrict to linear/affine estimators and minimize MSE within that class.

7.2. Problem Setup: Linear Least-Squares (LLS)

We seek an estimator of a (possibly vector) parameter $\mathbf{x}$ from data $\mathbf{y}$, minimizing squared error but constrained to be affine in $\mathbf{y}$:

Notation for moments:

7.3. Orthogonality Principle

The optimal linear estimate is a projection, so the error is orthogonal (in mean) to the data. Let the estimation error be

Then $\hat{\mathbf{x}}(\mathbf{y})$ is LLS iff:

Equivalently, the LLS error is orthogonal to every linear function of the data:

7.4. Closed Form for the LLS Estimator

Solving the orthogonality constraints for $\hat{\mathbf{x}}(\mathbf{y})=A\mathbf{y}+\mathbf{d}$ yields:

Interpretation:

• Center the data: $(\mathbf{y}-\mu_y)$.
• Apply the best linear map: $\Lambda_{xy}\Lambda_y^{-1}$.
• Add back the mean: $\mu_x$.

Sanity check: if $\Lambda_{xy}=0$ (uncorrelated), then $\hat{\mathbf{x}}_{\mathrm{LLS}}(\mathbf{y})=\mu_x$ (data provides no linear predictive value).

7.5. Performance: Error Covariance and MSE

Define the LLS error covariance

Then

The mean-square error (for vector $\mathbf{x}$) is $\mathbb{E}[\|\mathbf{x}-\hat{\mathbf{x}}_{\mathrm{LLS}}(\mathbf{y})\|_2^2]=\mathrm{tr}(\Lambda_{\mathrm{LLS}})$.

7.6. Example: Nonlinear BLS vs Linear LLS

Let $x$ and $w$ be independent and uniform on $[-1,1]$, and define

In this example, the posterior structure makes the BLS estimator nonlinear:

with conditional variance $\lambda_{x|y}(y)=\tfrac{1}{12}$, so $\lambda_{\mathrm{BLS}}=\tfrac{1}{12}$.

For LLS, symmetry gives $\mu_x=\mu_y=0$, and

Thus

So constraining to linear estimators increases MSE: $\frac{7}{48}>\frac{1}{12}$.

7.7. Jointly Gaussian Case: LLS = BLS

Proof idea: for jointly Gaussian variables, “uncorrelated” implies “independent.” The LLS error is uncorrelated with $\mathbf{y}$ by orthogonality, hence independent of $\mathbf{y}$, forcing $\mathbb{E}[\mathbf{x}\mid \mathbf{y}]$ to equal the linear form above.

7.8. Only Second-Order Information: A Minimax View

Suppose we do not know the full joint distribution of $(\mathbf{x},\mathbf{y})$, but we do know the means and covariances $(\mu_x,\mu_y,\Lambda_x,\Lambda_y,\Lambda_{xy})$. Consider a game: the estimator designer chooses $f(\cdot)$ to minimize MSE, while nature chooses any joint distribution consistent with those second-order moments to maximize MSE.

Result:

• The designer's optimal choice is the LLS estimator.
• Nature's worst-case distribution is jointly Gaussian with those moments.
• The resulting minimax MSE equals the LLS MSE:

  \[ \mathbb{E}\!\left[\|\mathbf{x}-\hat{\mathbf{x}}_{\mathrm{LLS}}(\mathbf{y})\|_2^2\right] = \mathrm{tr}\!\left(\Lambda_x-\Lambda_{xy}\Lambda_y^{-1}\Lambda_{xy}^\top\right). \]

7.9. BLS as LLS Over a Richer Function Space (Geometric View)

LLS can be generalized by first mapping $y$ through features $g(y)$ and then doing LLS on $z=g(y)$. As the feature class expands (more basis functions of $y$), the best linear estimator in that expanded space improves.

If we allow all (square-integrable) functions of $y$ as “features,” then the LLS projection becomes the full conditional expectation:

i.e., BLS is the LLS projection of $x$ onto the space of all functions of $y$. This is the clean geometric meaning of conditional expectation as an orthogonal projection in a (Hilbert) function space.

8. 2/24/26: NonBayesian Parameter Estimation

A lot of inference looked "Bayesian" up to now, where we treated unknown $x$ as a random, choose a prior $p_x(x)$, and computed estimators like MMSE/BLS, MAE, MAP. This is clean mathematically, but it relies on a prior that is not easily justifiable, and many real settings the unknown is better modeled as a fixed constant.

Non-Bayesian parameter estimation changes the modeling stance to:

• $x$ is deterministic, but unknown constant.
• $Y$ is random and distributed according to a model indexed by $x$: $p_Y(y;x)$.

We now can't minimize an average loss over $x$ since $x$ is not random. Instead, we must evaluate an estimator at each possible true $x$ using quantities like bias, variance, and MSE.

A natural non-Bayesian benchmark is the minimax estimator:

Hence, we are optimizing performance over randomness in $y$, but the estimator must not depend on $x$.

8.1. Bias and Covariance

Define the estimation error

• Bias: $b_{\hat{x}}(x)\triangleq \mathbb{E}[\hat{x}(Y)]-x=\mathbb{E}[e(Y;x)]$.
• Unbiased: $\mathbb{E}[\hat{x}(Y)]=x$ for all $x\in\mathcal{X}$.
• Variance: $\lambda_{\hat{x}}(x)\triangleq \mathrm{var}(\hat{x}(Y))=\mathbb{E}\!\left[(\hat{x}(Y)-\mathbb{E}[\hat{x}(Y)])^2\right]$.
• MSE: $\mathbb{E}\!\left[(\hat{x}(Y)-x)^2\right]=\lambda_{\hat{x}}(x)+b_{\hat{x}}(x)^2$.

For vector estimators, it is useful to define the error covariance and estimator covariance explicitly:

In the non-Bayesian case, we have $\hat{x}(y) = x + e(y)$, where the error and estimate are related by a constant. The estimate covariance and error covariance are the same for fixed $x$, though this isn't try in Bayesian case.

8.2. Minimum Variance Unbiased Estimators

The MVU may not exist when $\mathcal{A}$ is empty or no estimator in $\mathcal{A}$ is uniformly smaller in variance than all other for all values of $x$.

8.3. Cramer-Rao Bound and Efficiency

We can interpret the score as the best local direction in the data for learning $x$. If $S$ is large, then the observed data $y$ is pushing the likelihood towards larger $x$. If the distribution changes sharply with $x$, then the Fisher information is large and we can estimate $x$ more precisely.

• The $\hat{x}$ that saturates Cramer-Rao bound must be MVU. Note Cramer-Rao bound may not be tight and MVU might not saturate it.
• We can invoke conditions for Cauchy-Schwarz saturation, see 8.2
• [TODO] CRB can be constructed for biased estimates but is not useful in practice. There is analogous bound for random parameters, see Bayesian CRB.
• For problems where regularity condition of CRB is not satisfied, the Hammersley-Chapman-Robbin (HCR) bound applies.

We say an estimator is efficient if its saturates the CRB.

• A valid estimator satisfying 8.2 is guaranteed to be unbiased.
• The corollary implies that this efficient estimator is unique.
• When it exists, it must be the unique MVU estimator for a problem.

8.4. Maximum Likelihood Estimation

when the RHS exists and is unique. Common to refer to $p_y(y;x)$ as a likelihood function.

Bayesian estimators don’t commute with invertible transformations but maximum likelihood does. The properties don’t necessarily get preserved, e.g. Jensen’s inequality.

8.5. Generalization to Vector Estimation

For vector parameters, the scalar Cramer--Rao bound generalizes to a matrix inequality:

Here the score is now a vector and the Fisher information becomes a matrix:

8.6. Regularized and Constrained Estimation

ML estimation with a particular regularizer $\rho(\cdot)$ is given by

Note we replaced $p$ with $\log p$.

This corresponds to MAP estimate with a prior:

A Gaussian prior yields an $L_2$ penalty (ridge regression), while a Laplace prior yields an $L_1$ penalty.

8.7. Linear and Logistic Regression

Linear Regression

The maximum likelihood estimator is the least-squares estimator, and in fact is also MVU. Under a Gaussian noise model,

the ML estimator is

when $H^TH$ is invertible.

Logistic Regression

$p(u)$ tells you how common the input is. $p(v|u)$ tells you what class it belongs to. Classification only needs the second.

Training logistic regression only requires maximizing the conditional log-likelihood of the labels given the inputs. We ignore how the inputs are distributed.

9. 2/26/26: Exponential Families

Motivation: Efficient estimators are nice. For which families do they exist? We know that $p_y(y; \cdot)$ must have a unique stationary point if an efficient estimator exist.

When $\hat{x}_{eff}$ exists, solving for likelihood in equation 8.2 by integrating $x$ gives

Integrating gives

or

$\alpha(\cdot)$ is not specified as it serves as a normalization constant $\frac{1}{Z(x)} = \frac{1}{\exp(\alpha(x))}$ etermined by $\lambda$, $t$, and $\beta$. $Z(x)$ is called the partition function and $\alpha(x)$ is called the log-partition function.

Note:

• The support of $p_y(\cdot)$ (set of $y$ where $p_y(y;x) > 0$) cannot depend on $x$. Hence, $p_y(y;x) = \frac{1}{x}$ for $0 \le y \le x$ is not an OPEF.
• Such a specification is not unique as you can apply affine transformations to $\lambda, t, \beta$ and get a new $\alpha$ (renormalization). See Example 9.1.

Examples:

• Normal distribution.
• Bernoulli distribution with pmf $p_y(y;x) = x^y (1-x)^{1-y}$ for $\mathcal{Y} = \{0, 1\}$. More general binomial and multinomial distributions.
• A Markov Chain $x_1 \rightarrow x_2 \rightarrow x_3$. Distributions that have this are exponential. [TODO]

More definitions:

• A canonical OPEF is an exponential family with $\lambda(x) = x$. \[p_y(y;x) = \exp\{x t(y) - \alpha(x) + \beta(y)\}\]

  so that $Z(x) = e^{\alpha(x)} = \sum_{y} \{xt(y) + \beta(y)\}$.

  Any exponential family is canonical wrt to some $\lambda, t, \beta$. Just let $x' = \lambda(x)$ and $\alpha(x')$ is implicit by normalization ([TODO] $\lambda$ need not be injective?). May not be indentifiable.

• The natural parameter space $\mathcal{X}$ of a canonical exponential family is the collection of all possible $x$ such that the corresponding form of the distribution can be normalized: $\mathcal{X} = \{x \in \mathbb{R}: a(x) < \infty\}$. $\mathcal{X}$ is a convex set because $\alpha$ is convex (9.1). Hence
  \[\alpha(tx_1 + (1-t)x_2) \le t\alpha(x_1) + (1-t)\alpha(x_2)\]

  for any $t \in [0,1]$.

9.1. Log-Partition Function Properties

Implications:

• The mean of the score function is zero (recall this happens iff you can exchange differentiiation and integration from intepreting the regularity conditions).
• $\ddot{\alpha}$ is nonnegative as variance is nonnegative. Hence, $\dot{a}(x)$ is nondecreasing.

9.2. Constructions and Interpretations

9.2.1. Geometric Mean

Define the weighted geometric mean of two strictly positive probability distributions as

This describes a canonical exponential family parameterized in $\mathcal{X} = [0,1]$. Every canonical exponential family can be written as family constructed via weighted geometric mean of two suitably chosen distributions (see Theorem 9.1). [TODO]

9.2.2. Tilting Distributions

Given a base distribution $q(\cdot)$, define the tilted distribution

This describes a canonical exponential family. Any canonical exponential family having a finite alphabet $\mathcal{Y}$ can be expressed as a tilted distribution. [TODO]

9.3. Connection to Efficient Estimators

Theorems

Efficient unbiased estimators are rare, and when they exist, the model has a very rigid exponential-family structure and the estimator comes directly from the sufficient statistic.

\[\hat{x} = c t(y) + b\]

9.4. Multi-Parameter EFs

A canonical multi-parameter exponential family has $L=K$ and $\lambda(x) = x$.

Properties of log partition functions (check 9.5.2).

9.5. Categorizing and Reducing EFs

9.5.1. Identifiable Families

We only care about distributions where $p_y(\cdot; x)$ is associated with a unique value of $x$.

Example

9.5.2. Minimal Families

Minimality tells you you have the irreducible exponential-family representation, with no hidden linear redundancy in the natural parameters or statistics.

9.5.3. Full-Rank and Curved Families

Minimal exponential constraints satisfy no affine constraints but they may still satisfy nonlinear ones. In that case, the natural parameter space $\lambda(\mathcal{X})$ does not include an open subset of $\mathbb{R}^K$. One way to see this is to find a Jacobian with nonzero determinant.

examples

Minimal excludes linear redundancy in the statistics, but it does not exclude nonlinear relations among the natural parameters; the Jacobian test tells you whether the natural parameter image is locally full-dimensional.

Other wise we call it curved, or $\lambda(\mathcal{X})$ is a manifold in $\mathbb{R}^K$ of dimension less than $K$.

example of full-rank family

Shows that minimal does not imply nice parameterization.

9.6. Reparameterization

When we specify an exponential family, we specify the collection via $t(\cdot)$ and $\beta(\cdot)$, and a particular parameterization via $\lambda(\cdot)$. If we don't care about choice of $\lambda$, we can use the canonical one.

In generative modelling, the parameters are not identifiable, but this is not important.

9.7. EFs over Finite Alphabets

For a finite alphabet $\mathcal{Y}$, it is possible to construct a canonical exponential family that includes all positive distributions.

Let

where $t_i(y) = \mathbb{1}_{y=i}$. Then an arbitrary distribution $q(\cdot)$ over $\mathcal{Y}$ is a member of the family corresponding to the choice of $x$:

This is effectively a weighted mean of $M$ elementary distributions $p_i(y) \propto e^{\mathbb{1}_{y=i}}$.

For distributions over infinite alphabets, it is possible to show that under suitable constrains there exists a sequence of exponential families that are dense in the space of all suitably well-behaved distributions. We will revisit this after developing the notion of closeness of two distributions.

9.8. Markov Structure as an EF

Consider a Markov chain $y_1 \leftrightarrow y_2 \leftrightarrow y_3$ with a strictly positive joint distribution.

1. It factorizes as \[p_{y_1,y_2,y_3}(y_1,y_2,y_3) \propto \phi_{1,2}(y_1,y_2) \phi_{2,3}(y_2,y_3)\]

   for some strictly positive $\phi_{1,2}$ and $\phi_{2,3}$ that have $M_1M_2 - 1$ and $M_2M_3 - 1$ degrees of freedom respectively.

2. We can construct an exponential family in $y = (y_1, y_2, y_3)^\intercal$ in the following way:
   

9.9. Local Families of Distributions

In this section, we show that sufficiently well-behaved families of distributions are effectively “locally” exponential. This can essentially be seen as just a first-order Taylor expansion of the log-density in the parameter.

9.10. Computation for Inference with Exponential Families

When computing $p_y(y;x)$, the data $y$ only participates through natural statistics $t(y) \in \mathbb{R}^K$ and log base function $\beta(y)$. Once we compute these $K+1$ numbers, we can get rid of $y$.

In fact, we don't need to keep $\beta(y)$ to carry out ML estimation: For example, in a canonical exponential family,

We know that $\alpha(x)$ is convex as $J_y(x)$ is positive definite, and second term is linear. Hence if $\mathcal{X}$ is a convex set, we have a convex optimization problem that can be solved via gradient descent.

We can throw away $\beta(y)$ in general, and $t(y)$ is sufficient statistic.

[TODO] review pset 3 p3 where ML estimation can be turned into BLS estimation

10. 3/3/26: Sufficient Statistics

Data comes from very large alphabet (in discrete case) or has very high dimension (in continuous-valued case). When is extracting features lossless (sufficient statistic) and is there a notion of "compactness"? What about Bayesian vs Non-Bayesian?

10.1. NonBayesian Setting

In the nonBayesian setting, a model family is written as

Before, we modeled $(X,Y)$ as a joint distribution. Now, we fix $x$ and model $Y$ as a distribution.

Define a statistic $t(\cdot)$ to be a function of the data. The random variable $t = t(y)$ induces distributions $y\vert t;x$ and $t\vert x$.

Essentially, probability of $y$ given $x$ is the probability of $y$ given $t(y)$ times the probability of $t(y)$ given $x$.

The definition expresses that the given $t$, the remaining uncertainty about $y$ is not a function of $x$. We cannot infer additional information about $x$ by getting access to the value of $y$ from which this value of $t$ was computed. Because of (10.2), we get the form

Basically, for fixed $y$, the distribution of $y$ and $t$ are proportional when changing $x$. With a given observation, the relative variations in the likelihood $p_y(y;x)$ with $x$ are what we have available to exploit in making inferences about the true value of $x$. For example, then we get the same likelihood ratio and MLEs if we use $t$.

Proof of equivalence of the functional definition

Sufficiency means that after conditioning on $T$, whatever randomness remains in the full data is parameter-free, and therefore useless for improving inference about the parameter.

This is a practical way to check for sufficiency.

proof

examples

Examples 10.2 (exponential families) and 10.3 (finite alphabet).

10.2. Bayesian Setting

In the Bayesian view the conditional distribution $p_{y \vert x}(y \vert x)$ replaces $p_y(y;x)$ in specifying the model family, yielding

We shift the model from an indexed family to a conditional distribution.

proof

10.3. Markov Chain View

The Bayesian results imply this characterization:

10.4. Minimal Sufficient Statistics

Minimal dimension is not a good notion of minimality without some weird notion of smoothness.

Essentially, its minimal if any other sufficient statistic can be processed into it.

• It is nonunique up to invertible functions. So if the tuple $(y_1, y_2)$ is minimal, so is $y_1, y_2, y_1+y_2$.

For example, when $x$ comes from a finite alphabet, the vector of likelihood ratios is a minimal sufficient statistic (see pset 4 #1).

[TODO] t(y) is a minimal sufficient statistic for exponential family.

10.5. Partition View of Sufficiency

We are characterizing sufficiency and minimal sufficiency as partitions of the data into classes that have the same evidence about the parameter.

Denote the likelihood $\mathcal{L}_{y=y_1}(x)$.

The minimal statistic can be thought of the maximally coarse partition among sufficient statistic. Partition view quotients about invertible transformations.

Algorithm 10.1 to find minimal sufficient statistic for finite $\mathcal{Y}$: just try all possible partitions with some pruning. (merge observation points whenever they have the same likelihood shape as a function of the parameter).

visual

10.6. Complete Sufficient Statistic

For example, $t(y)$ is a complete sufficient statistic for the exponential family based on some Laplace transform theory.

There is a geometric interpretation.

11. 3/3/26: Inequalities

In the case where $f(x)=x\log x$, we have log-sum inequality

States that true distribution uniquely maximizes expected log-likelihood.

12. 3/5/26: EM Algorithm

Ideas start back to Fisher in 1925. Popularized by Dempster in 1977.

12.1. Motivation

Can we define a hill-climbing method that explicitly takes advantage of special structure of the distribution in interest?

Example. [Phenotype analysis]

Bin of R,G,B balls, prabilities are parameterized by

\[\mathbb{P}(R) = \frac{1}{2} + \frac{x}{4}, \quad \mathbb{P}(G) = \frac{x}{4}, \quad \mathbb{P}(B) = \frac{1}{2} - x\]

We observe $y_R, y_B, y_G$ of each ball. What is the ML estimator?

\[\log p_y(y;x) = y_R \log \Big(\frac{1}{2} + \frac{x}{4}\Big) + y_G \log \Big(\frac{x}{4}\Big) + y_B \log \Big(\frac{1}{2} - x\Big)+c\]

where $c= \log \frac{(y_R+y_G+y_B)!}{y_R!y_G!y_B!}$.

Differentiating yields a quadratic in $x$ that can be solved analytically.

Another strategy is divide R into two groups, $R_1$ and $R_2$ with $\mathbb{P}(R_1)=\frac{1}{2}$ and $\mathbb{P}(R_2) = \frac{x}{4}$. Solving for ML estimator now becomes a linear equation!

math

This does not change the marginal law of the observed data

\[\mathbb{P}(Y=R)=\mathbb{P}(Z=R_1) + \mathbb{P}(Z=R_2) = \frac{1}{2} + \frac{x}{4}\]

The goal is to exploit the structure by introducing ficticious variables that can turn a harad optimization into an easier one.

Model: Let $y$ be the observation. Define $z$ which we refer as a complete data that is generated by a probability distribution $p_z$ for some $\mathcal{Z}$ but is not fully observable.

WLOG, we decompose the complete data as $z = (y,s) \in \mathcal{Y} \times \mathcal{S}$ where $s$ is a latent variable comprising the unobserved part of $z$.

We can denote our observed data $y=g(z)$ for some function $g$, possibly many-to-one, so that

Then,

Taking expectation wrt to $q = p_{z \vert y}(\cdot \vert y;x')$ for variable $x'$ for both sides give

as LHS does not depend on $z$ at all.

Note that $V(x,x')$ is a expected log conditional density. Then, we know by Gibb's inequality that $V(x,x') \le V(x',x')$ so taht

Think of $U(x,x')$ as the expected complete-data log-likelihood under the current posterior of the latent variables.

Hence to maximize likelihood it suffices to find an $x$ that maximizes $\Delta U$ since $\Delta V$ is non-negative.

This motivates the EM algorithm.

Remarks:

• A variety of what are referred to as variational inference techniques are based on the use of optimizing lower bounds. In variational Bayes' methods, it is the evidence lower bound (ELBO) that is optimized. [TODO] review this
  elbo

  

  EM is a special case of variational/ELBO optimization where the E-step is exact posterior inference rather than an approximation.

• In practice, we can replace $M$-step with anything that increases $U$ (generalized EM).
• Under mild conditions (e.g. exponential family), we can show that EM converges to a stationary point of $\mathcal{L}_{y=y}(\cdot)$. This is not necessarily the ML estimator.
• Rate of convergence: it's exponential and depends on choice of $z$. As a general rule of thumb, for a given problem, the less predictable the complete data is from the observed data, the worse the exponent.
• There is often a natural choice for $z$ with some physical interpretation.
• There is a beautiful geometric interpretation we will develop later.
• Pset4 #4 goes over Bayesian version: EM-MAP instead of EM-ML. Uses relation:
  

  [TODO] review this

  • EM-ML is nonBayesian, where EM-MAP here adds a prior onto $x$.
  • ordinary EM-ML optimizes $\mathbb{E}_{p(s \vert x',y)}[\log p(y,s \vert x)]$ where EM-MAP optimizes $\mathbb{E}_{p(s \vert \hat{x}^{(l-1)},y)}[\log p(y,s \vert x) + \log p(x)]$.

12.2. EM in Exponential Families

We have an exponential family complete data when the complete data is from a canonical exponential family:

The specialization of the EM algorithm to this case:

Last term is independent of $x$, so we can ignore it.

So choose x such that $\nabla \alpha(x)= \mathbb{E}_{p_{z \vert y}(\cdot \vert y;x')}[t(z)]$.

In exponential-family EM, the E-step computes the expected complete-data sufficient statistic, and the M-step chooses the parameter whose exponential-family moment matches that expected statistic.

proof

The condition for a fixed point is that two expectations match. It turns out this is the same condition for stationary point in an EF.

[TODO] we essentially get $s \vert y$ written as an EF and solve for its stationary points.

The convergence rate analysis can also be derived elementarily.

12.3. Examples

Example. [Gaussian Mixture Model] The complete data augments $y$ with the latent component label indicating which Gaussian generated $y$. The likelihood for a single point is just the sum below.

multiple stationary point

Example. [Logistic Model Mixture]

Mixture of two logistic models, e.g. classify truck vs car while winter vs summer is confounding.. The likelihood with the component selector known is

$w$ follows a Bernoulli distribution which is exponential. Let $z=(u,v,w)$ where $v$ is the class label. Compute conditional probabilities and posteriors using Bayes.

Intuitively, the iterative approach is to guess a value for the $q, x_0, x_1$, and then update the posterior distribution for $w$ (E-step), and update $x_1$ and $x_2$ assuming posterior (M-step).

analysis

[TODO]

Mixture models are just the easiest place to see the mechanics, but EM is a general latent-variable maximum likelihood method. “Maximizing a surrogate objective where the latent variables are treated as soft labels distributed according to the current posterior”

[TODO] pset4.3 as well

13. 3/10/26: Revisiting Estimation (Bayesian)

13.1. Inferring Distributions

Let $x$ be the quantity of interest, with prior $p_x(\cdot)$ and observational model $p_{y \vert x}(\cdot)$.

Recall that with a cost function $C(x, \hat{x})$,

aka once $y$ is fixed, your decision is just some value $a=f(y)$.

1. We have an inference engine that takes in $p_x$ and $y$ and produces an estimate $\hat{x}$ on the posterior belief $p_{x \vert y}$. The prior and cost are known beforehand based on the application.
2. But suppose we don't know the application ahead of time, or there are multiple applications. This leads us to needing a general purpose "inference" box.

Generalization: Our model will output a distribution $q(\cdot)$ over $\mathcal{X}$ instead of a number $\hat{x}$. We will view "inference" itself as teh estimate. Clearly the best distribution is $q_a = \mathbb{1}_{x=a}$ (objective/posterior cost is linear in $q$).

Some examples of cost criterion:

1. $C(x,q) = A\sum_{\alpha \in \mathcal{X}} (q(a) - \mathbb{1}_{x=a})^2 + B(x)$ (quadratic cost)
2. $C(x,q) = -A \log q(x) + B(x)$ (negative log loss, make $q$ as peaky as possible)

Now, because expected cost relies on $q$, a non-degenerate $q$ could be optimal.

The expected cost is ove rthe true distribution $p_{x \vert y}(\cdot)$.

proof

Lemma. Suppose that for all positive $u,v,w$ such that $u + v+ w \le 1$, we have $f(u)=g(v)$. Then $f$ is a constant function.

13.2. Log-loss as Self-Information Cost Function

WLOG let $A=1$ and $B=0$. Then the expected cost when using the log cost is

Under truthful report $q(\cdot \vert y)=p_{x \vert y}(\cdot \vert y)$, the expected cost is

Suppose we have no data, so $p_{x \vert y}(\cdot \vert ∅)=p_x(\cdot)$. Then the prior cost is

We call $H(x)$ the self-information or entropy of $x$.

Properties:

1. Measure of hwo random $x$ is. [TODO] $0 \le H(x) \le \log \vert \mathcal{X} \vert$
2. Not sensitive to $\mathcal{X}$ or reparameterization, unlike variance. Depends only on distribution, not the labels.
3. If $X \sim p$, we write $H(p)$.
4. When $p$ is a Bernoulli distributiion with $p$, $H_B(p) = -p\log p - (1-p)\log(1-p)$. Symmetric concave function that peaks at $(\frac{1}{2}, 1)$, when $H$ is said to be measured in bits when log base is $2$.

13.3. Cost Update

Once we have data, we denote the conditional entropy as

Properties

1. We can compute the conditional entropy pointwise using the self-information formula on $H(x \vert y=y)$. Then

   \[H(x \vert y) = \sum_{y} p_y(y) H(x \vert y=y)\]

2. [TODO] $H(x \vert y) \ge 0$ with equality iff $x$ is a deterministic function of $y$.
3. [TODO] $H(x \vert y) \le H(x)$. Note that we can have $H(x \vert y = y) \ge H(x)$ for some point $y$, but on average, conditioning never increases uncertainty.
   proof

   
4. [TODO] We have the following decomposition of the joint entropy (chain rule of entropy) \[H(x \vert y) + H(y) = H(x,y)\]

   To undestand what $H(x,y)$ means, we can write $z=(x,y)$ as its own distribution over an alphabet.

We get a lot of additive results in the algebra of information because logs turn products into sums.

13.4. Cost Reduction

The cost reduction due to the data is called the mutual information.

visual

Properties:

1. $I(x;y)$ is a very fundamental quantity. It characterizes how much $y$ tells us about $x$ for purpose of inference. Larger $I$ is better.
2. $I(x;y) \ge 0$ from above.
3. $I(x;y) = 0$ iff $x \perp y$. [TODO]
4. $I(x;y) = I(y;x)$, implying $I(x;y) = H(y)-H(y\vert x)$.
5. The extension to conditional mutual information as \[I(x;y \vert z) \triangleq H(x \vert z) - H(x \vert y,z)\]

   [TODO] which equals 0 iff $x \perp y \vert z$ or $x \leftrightarrow z \leftrightarrow y$.

6. $I(x;y,z)=I(x;z) + I(x;y \vert z)$ (chain rule of mutual information). The LHS is the mutual information between $x$ and the joint variable $(y,z)$.

[TODO] in general just go through all the math here

13.5. Sufficient Statisitc Revisited

Recall $t$ is a statistic if $x \leftrightarrow y \leftrightarrow t$ ($t = g(y)$ is a special case). If $x \leftrightarrow t \leftrightarrow y$, then $t$ is a sufficient statistic.

Remarks

• Processing can only destroy information.
• As a special case, $I(x,y) \ge I(x,g(y))$

13.6. Imperfect Inference

We often can't implement the true belief

e.g. if $x$ is a language model the denominator is a huge sum. ([TODO] does this matter?) So we must approximate with some other $q(\cdot)$. How should we measure the approximation loss?

First focus on approximating the prior belief $p_x$ versus $q$.

This is called information of divergence or relative entropy. More commonly called Kullback-Leibler divergence or KL divergence.

Remarks:

1. $D(p \vert \vert q) \ge 0$ by Gibb's inequality.
2. $D(p \vert \vert q) \neq D(q \vert \vert p)$ in general.
3. $I(x;y) = D(p_{x,y} \vert \vert p_x p_y)$
4. Key measure in geometry of information. There is a nice relation between divergence and Fisher information:
   

   [TODO] understand this

5. [TODO] Chain rule for divergence
   
6. $D(p \vert \vert q)$ is continuous function of $p,q$ at al $p,q$ s.t. $q$ is positive.
   divergence example

   
7. Conventions from continuity: \[0 \log \frac{0}{0} = 0, \quad 0 \log \frac{0}{\lambda} = 0 \quad \lambda \log \frac{\lambda}{0} = \infty, \quad \lambda \in (0,1]\]

   Hence $D(p \vert \vert q)$ is bounded whenver $\text{supp}(p) \subset \text{supp}(q)$.

8. $D(p \vert \vert q)$ is the expectation of the log likelihood ratio under $p$. We usually think of $p$ as true distribution. Using the reverse, the behavior is mode-seeking: if $p$ is multimodal, the divergence will prefer orientations that place mass in one of the modes, rather than spreading out the mass between all of $p$'s modes. Check: https://andrewcharlesjones.github.io/journal/klqp.html
   visual

   

[TODO] get through all the identities

14. 3/12/26: Information Geometry

We've viewed inference in data (raw $y$) or feature (sufficient statistic) space as partitioning $\mathcal{Y}$. Now we'll look at distribution space.

We developed KL divergence as a meaningful way to measure how different two distributions are wrt to task of inference: $D(p \vert \vert q)$ is cost you get for using distribution $q$ instead of $p$ in with log cost.

Remarks:

• Continue with discrete, finite alphabet. Countably and uncountably infinite alphabets require extra care.
• Use $\log_2$ sometimes
• Define $0 \log 0 = 0$ for continuity
• $D(p \vert \vert q) \ge 0$ with equality iff $p = q$.
• $D(p \vert \vert q)$ is convex in $p$ as well as $(p,q)$:

  \[D(\lambda_1 p_1 + (1-\lambda_1)p_2 \vert \vert q) \le \lambda_1 D(p_1 \vert \vert q) + (1-\lambda_1) D(p_2 \vert \vert q)\]

14.1. Euclidean Geometry

A convex set satisfies $p_1, p_2 \in S \implies p_\lambda = \lambda p_1 + (1-\lambda)p_2 \in S \quad \forall \quad \lambda \in [0,1]$.

Define projection onto set as the nearest point in that set. If you have convex set $S$, the angle $\theta = \angle XPY$ where $X$ is any point in $S$, $Y$ is a point outside the set, and $P$ is $Y$ s projection is at least $\frac{\pi}{2}$. If $S$ is a hyperplane, then $\theta = \frac{\pi}{2}$. Pythagoras for convex sets then say

with equality iff $\theta = \frac{\pi}{2}$.

Supose we're in $\mathbb{R}^M$ and want to know how many points project onto $p$ in $(M-K)$-dimensional hyperplane $S$. This is the orthogonal complement of $S$ (shifted so with $p$ is the center) and is $K$-dimensional.

We'll show we get similar results using $D(\cdot \vert \vert \cdot)$.

Denote $\mathcal{P}^\mathcal{Y}$ as the collection of distributions over $\mathcal{Y}$. When $\mathcal{Y}$ is finite, this is a probability simplex. For example $\vert \mathcal{Y} \vert = 3$ corresponds to the plane $x + y + z = 1$ in first octant.

Examples

• The weighted geometric and arithmetic mean for a curve and a line respectively on the simplex.
• The expectation constraint $\mathcal{P} = \{p : \mathbb{E}_p[t(y)] = c \}$ is a linear constraint and yields a $M-2$ dimensional hyperplane (an existing constraint is the simplex constraint).

14.2. Projections of Distributions

Remark: Because KL is not symmetric, there's two different notions of projection. [TODO] We will get to the other one later. apparently a very beautiful duality

proof

Trivial if $q \in \mathcal{P}$. Assume otherwise. $p^*$ exists and is unique since $D(p,q)$ is (strictly?) convex in $p$.

Pick arbitrary $p$ and define $p_\lambda = (1- \lambda) p^* + \lambda p$ for $0 \le \lambda \le 1$. Since $\mathcal{P}$ is convex and closed, $p_\lambda \in \mathcal{P}$ and $\lim_{\lambda \rightarrow 0} p_\lambda = p^*$.

Since $D(p^*,q)$ is the minimum of $D(p_\lambda, q)$ along the path from $p^*$ to $q$ parameterized by $\lambda$ as it goes from $0$ to $1$, we must have

\[\frac{d}{d \lambda} D(p_\lambda, q) \text{ evaluate}_{\lambda = 0} \ge 0\]

Otherwise, for some sufficiently small $\epsilon$, we'd have $D(p_\epsilon, q) \le D(p^*,q)$.

Now let's evaluate the derivative and see what the constraint we get is:

\[ \begin{aligned} \frac{d}{d \lambda} D(p_\lambda, q) &= \frac{d}{d \lambda} \sum_{y} p_\lambda (y) \log \frac{p_\lambda (y)}{q(y)} \\ &= \sum_y [p(y) - p^*(y)]\log \frac{p_\lambda(y)}{q(y)} + \sum_y p_\lambda(y) \cdot \frac{1}{p_\lambda(y)} [p(y) - p^*(y)] \\ &= \sum_y [p(y)-p^*(y)] \log \frac{p_\lambda (y)}{q(y)}\\ \end{aligned} \]

Setting $\lambda = 0$,

• $p^*$ will be $0$ for some coordinate, so $D(p \vert \vert p^*)$ will blow up.

14.3. Linear Families

Definition. [Linear Family] A set of distributions $\mathcal{P} \subset \mathcal{P}^\mathcal{Y}$ is a linear family if it can be written as the set of distributions in a simplex satisfying $K$ expectation (linearity) constraints:

The representation ($t, \overline{t}$) of a linear family is minimal if the matrix $\tilde T$ has linearly independent rows.

The dimension of original simplex is $M-1$. By rank-nullity, $\text{dim} \mathcal{P} = M - \text{rank}(\tilde T)-1$.

Proposition. [Pythagorean Identity]

[TODO] try to figure out from euclidean version

14.4. Orthogonal Families

Given a linear family with a minimal representation corresponding to a particular choice of $t$. Then for any $p^* \in \mathcal{P}^\mathcal{Y}$, there is a unique choice of $\bar{t}$ such that $p^*$ is in this linear family: $\bar{t} = \mathbb{E}_{p^*}[t(y)]$.

What is the set of all distributions in the simplex (unrestricted) whose I-projection onto $\mathcal{L}_t(p^*)$ is $p^*$?

Theorem. [Orthogonality of Linear and Exponential Families]

Essentially think $\beta(y) = \log p^*(y)$.

14.5. [TODO] Canonical Exponential Family Identities

14.6. [TODO] Local Information Geometry

15. 3/17/26: Modeling as Inference

15.1. Introduction

This is a NonBayesian perspective of L13.

Suppose you don't have the correct model for potential data $y$ but you know it lies in a class parameterized by $x \in \mathcal{X}$.

Modeling goal: Want to make inferences about $y$. Don't care about $x$ per-se, only our ability to model $y$.

• Language modeling: Predict $p_{y_n \vert y_1, \ldots, y_{n-1}}$
• Image classification: $y_i = (u_i, v_i)$ where $u_i$ denotes image and $v_i$ denotes class label, and we want to compute

  \[p_{v_n \vert u_n, y_1, \ldots, y_{n-1}}\]

• We mesaure some iid Bernoulli variables for some bias $x \in [0,1]$, and we want to best characterize the uncertainty in $y_n$.
  • One approach is to construct the distribution according to MLE estimator for $x$ can be justified asymptotically but is not the best approach for any finite value of $n$.

$D(p_y(\cdot ; x) \vert \vert q)$ serves the natural measure of goodness of $q$.

We develop a fundamental approach for such modeling problems. Interestingly, we neither require nor benefit from explicitly estimating $x$.

15.2. Modeling via Mixture

The key to our approach is to model $y$ as a mixture of the class

where $w(x)$ are all nonnegative and sum to one. From Bayesian viewpoint, $w(x)$ would be interpreted as a prior over $x$, since $\sum_{x \in X} p(x) = 1$.

recall that $q(y)$ is our true distribution, but it might not lie in the model class. We want to find a mixture that is as close to $q$ as possible.

Plan: We will first discuss a framework to optimize $w$ and then show that is useful for inference

Check Example 15.2, which shows divergence between $B(0)$ and $B(1)$ vs their mixture

This is because distribution spaces preserve convex by construction, and averaging parameters can destroy multimodality.

15.3. Optimization Framework

Now we know it is sufficient to optimize a mixture. A natural means for choosing $q$ is according to a minimax criterion. We choose $q$ to try to make the divergence as small as possible, knowing that nature will subsequently choose $x \in \mathcal{X}$ to make divergence as large as possible. We define the minimax redundancy in $q$

So interpretation is that you first pick a distribution and nature picks some weights to maximize the divergence on your choice.

From this form, we apply the following saddle-point theorem, which establishes the equivalence between minimax and maximin redundancy. It turns out the maximin version is easier to perform directly!

[TODO] PROVE THIS USING VON NEUMANN THEOREM AND INFORMATION GEOMETRY

Let's consider the inner optimizations of $R^-$. Given a fixed set of weights that nature chooses, how does one minimize the summation? It is choosing exactly

so that

For the outer maximization, nature tries to maximuze:

More useful intuition is obtained by returning to a Bayesian view. Interpret $p_y(y;x) \leftrightarrow p_{y|x}(y|x)$ and $w(x) \leftrightarrow p_x(x)$ so that

Nature's outer optimization becomes:

which is just $I(x;y)$. So $R^-$ is choosing the prior that maximizes how much $y$ tells about $x$. This will maximize the reduction in uncertainty.

The quantities involved have names:

Remarks

• $0 \le C \le \log |X|$
• The model capacity expresses the richness of the model family (expressive power). There is a tradeoff: Larger classes of models are more expressive but come with larger values of $C$ (nature can force a larger loss because the family is harder to approximate uniformly).

  \[\text{capacity} \approx \text{how separated the models in the family are.}\]

• For $| \mathcal{X} | < \infty$, the optimum model satisfies the equidistnace property
  
• Recall $I(x;y) = H(x) - H(x \vert y)$.
  1. If $x$ can be determined uniquely from $y$, then the latter term is $0$. So $\max I = \log |X|$ (nature picks a uniform distribution)
  2. If no information about $x$ is determined from $y$, then $C=0$.
• (nontrivial) [TODO] Even when $x$ is continuous-valued, provided $y$ is discrete, the associated least informative prior is discrete with at most $| \mathcal{Y} |$ mass points.
• When we have a sequence of $N$ observations $y_1, \dots, y_N$ each from $\mathcal{Y}$, optimizing weights depend on $N$, which is sometimes referred to as the horizon of the problem.

15.4. Computation of Model Capacity

Recall KL divergence is convex.

proof

Note that we can alternatively denote mutual information as $I(p_x; p_{y \vert x})$.

Hence the optimization is concave, and so is the problem is well behaved.

15.5. Inference with Mixture Models

Okay so we know how to find the distribution that minimizes KL divergence within a model class. How can we do inference (i.e. infer new $y$ given old observed $y$)?

The strategy is to compute the minimax distribution $q(y)$ and apply conditional probability on it.

• How do we use $w$? In a general scenario, there are a set of variables $y_-$ that we observe and a set $y_+$ that we do not observe but about which we want to make inferences (think time series data)

We want to find some $q_{y_+ \vert y_-}(y_+ \vert y_-)$ that is true to the true conditional $p_{y_+ \vert y_- ; x}(y_+ \vert y_- ; x)$.

Essentially:

• mix the full model class using prior weights $w^*(x)$
• condition on observed $y_-$
• equivalently, update the weights to posterior weights $w^*(x \vert y_-)$
• average the conditioned component models with those revised weights

chatgpt

Note that we computed $q_y$ where $y = [y_-, y_+]$, but its marginal $q_{y_-}$ to substitute into 15.31.

Essentially mixture is a softversion of maximum likelihood, where inference doesn't commit to best $x$ but plausible according to observed data.

example

16. 3/19/26: Continuous Parameters

We previously developed entropy for random variables over finite alphabets $\mathcal{X}$. We now extend to infinite alphabets. Most notably, differential entropy is not as nice, but mutual information and information divergence remain nice.

So entropy could be finite even when mean or variance does not exist.

16.1. Uncountably Infinite Alphabets

We focus on continuous variables for which there exists a PDF.

16.1.1. Differential Entropy

Properties:

• DE has the same dimensions as $x$
• DE need not be nonnegative. $U[0, \Delta]$ has negative entropy if $\Delta < 1$.
• DE is not invariant to coordinate transformations. Let $x = g(s)$ where $g$ is some strictly increasing mapping. Then $p_x(x) = p_s(s)/g'(s)$ with $s=g^{-1}(s)$ where $g'$ is the Jacobian of the transformation, and

  \[\begin{align} h(x) & -\int p_x(x) \log p_x(x) dx \nonumber\\ &= -\int p_s(s) \frac{1}{g'(s)} \log \left( \frac{p_s(s)}{g'(s)}\right) g'(s) ds \nonumber\\ &= h(s) + \mathbb{E}[\log g'(s)] \nonumber\\ \end{align}\]

• The multivariate extension of this fact is
  \[h(x) = h(s) + \mathbb{E}[\log \vert \det J_g(s) \vert]\]

  where $(J_g(s))_{ij} = \frac{\partial_{g_i}}{\partial_{s_j}}$

Conditional differential entropy is defined in the same manner:

16.1.2. Mutual Information

Define mutual information in terms of differential entropies via

Properties:

• Remains nonnegative since divergence remains the same. Hence conditioning can still never increase differential entropy even though differential entropy may be positive or negative.
• Invariant to coordinate transformations. i.e. $h(x \vert y) = h(s \vert y)$
  proof

  Comes from Tower Law and the fact that $\mathbb{E}[\log g'(s)]$ terms appears in both $h(x)$ and $h(x \vert y)$.

  

16.1.3. Information Divergence

Properties:

• still holds for continouous variables.
• Divergence is coordinate free transformation:

  \[ \begin{align} D(p_x \vert \vert q_x) &= \int p_x(x) \log \frac{p_x(x)}{q_x(x)} dx \nonumber \\ &= \int \frac{p_s(s)}{g'(s)} \log \frac{p_s(s)/g'(s)}{q_s(s) g'(s)} g'(s) ds \nonumber \\ &= D(p_s \vert \vert q_s) \nonumber \end{align} \]

16.2. Inference and Modeling

Recall the capacity-redundancy theorem was used to turn the minimax problem into a maximin problem. The following fairly general theorem is an extension:

16.3. Information Measures for Gaussians

Gaussians are the one continuous family where the information measures collapse cleanly into second-order quantities. This is why covariance / correlation / Fisher information keep reappearing.

16.3.1. Differential Entropy

• Entropy depends only on covariance, not the mean.
• Larger variance/covariance volume means larger differential entropy.
• If \(\Lambda\) is singular, the density does not exist on full \(\mathbb R^K\), so the usual differential entropy formula breaks.

16.3.2. Conditional Gaussian Entropy

For jointly Gaussian scalar variables

we have

The conditional variance is

For vector Gaussians,

then

16.3.3. Gaussian Mutual Information

For scalar jointly Gaussian \(x,y\),

• If \(\rho_{xy}=0\), then \(I(x;y)=0\). For Gaussians, uncorrelated implies independent.
• As \(|\rho_{xy}|\to 1\), \(I(x;y)\to\infty\). Perfect continuous correlation makes the conditional variance collapse.

For vector jointly Gaussian variables,

where

If \(\rho_1,\ldots,\rho_K\) are the singular values of \(B_{xy}\), then

The \(\rho_k\)'s are canonical correlations.

16.3.4. Gaussian KL Divergence

If

then

This is basically signal-to-noise ratio measured in information units.

For multivariate Gaussians with the same covariance,

More generally, if

then

16.4. Approximating Distributions by Exponential Families

For continuous alphabets, sufficiently light-tailed distributions can be approximated arbitrarily well in KL by a sequence of exponential families.

Idea:

• approximate \(\log p(y)\) by a finite linear combination of basis functions \(t_k(y)\);
• exponentiate and renormalize;
• closeness is measured by information divergence.

17. 3/31/26: Maximum Entropy Distributions

From model capacity, the least informative prior is the minimax-optimal weighting over models, but it can be hard to compute. The notes now exploit the fact that performance is often not too sensitive to the exact prior, provided the prior is strictly positive / interior.

17.1. Maximally Ignorant Priors

Motivation: if we have no data but need a simple prior, choose the distribution with maximum entropy subject to whatever constraints we actually trust.

If there are no constraints on a finite alphabet \(\mathcal Y\), the max entropy distribution is uniform:

with equality iff \(p=U(\mathcal Y)\).

17.2. Finite Alphabet Case

For finite \(\mathcal Y\),

Thus maximizing entropy is equivalent to minimizing KL divergence to the uniform distribution:

Suppose constraints are linear:

Then

By information geometry, \(p^*\) is the I-projection of \(U\) onto the linear family \(\mathcal L_t\). Since the exponential family orthogonal to \(\mathcal L_t\) has base \(U\), the solution has exponential-family form:

with \(x_1,\ldots,x_K\) chosen so that

17.3. Infinite Alphabet Case

For continuous alphabets, uniform distribution may not exist, and differential entropy is coordinate-dependent. Still, the max entropy solution under linear constraints has the same exponential-family form when it exists:

Examples:

• No constraint on \(\mathbb R\): no maximum entropy distribution.
• Fixed mean on \(\mathbb R_+\): exponential distribution.
• Fixed mean and variance on \(\mathbb R\): Gaussian distribution.
• Fixed covariance matrix on \(\mathbb R^K\): multivariate Gaussian.

18. 4/2/26: Conjugate Priors

So far:

• Least informative prior is minimax-optimal but hard to compute.
• Maximally ignorant priors are easier but may not be easy to update.
• Conjugate priors are priors chosen for computational closure under Bayesian updating.

18.1. Permutation-Invariant Models

Conditionally i.i.d. implies permutation invariance:

for any permutation \((n_1,\ldots,n_N)\).

Any mixture of i.i.d. distributions is exchangeable:

18.2. Successive Belief Revision

For continuous \(x\), a Bayesian update is a map

If \(y_1,y_2\) are conditionally independent given \(x\), then updates can be done successively:

If observations are conditionally i.i.d., the same update rule \(T_y\) is reused each time.

18.3. Initial Example: Beta-Bernoulli

Let

If

then

So

For \(N\) observations and \(t_N(y)=\sum_{n=1}^N y_n\),

Predictive probability:

where \(n_1\) is the number of ones in \(y_1,\ldots,y_{n-1}\).

Special cases:

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

18.4. Conjugate Prior Families

Equivalently, there is an update map

such that

18.5. Why Exponential Families Appear

For continuous observations, conjugate prior families can only exist when the model has finite-dimensional sufficient statistics. The notes then connect this to exponential families.

Mental compression:

18.6. Natural Conjugate Priors for Exponential Families

Suppose

A natural conjugate prior has the form

Here \(\gamma(\bar t,N)\) is the normalization constant.

For data \(y_1,\ldots,y_N\),

So the hyperparameters update by

19. 4/7/26: Information Geometry of ML and EM

19.1. ML as a Reverse I-Projection

For i.i.d. discrete data \(y=(y_1,\ldots,y_N)\), the empirical distribution/type is

For any function \(f\),

The normalized log-likelihood is

Then

The entropy term does not depend on \(x\), so

19.2. EM as Alternating Projections

Let \(z=(z_1,\ldots,z_N)\) be complete data and \(y=g(z)\) be observed incomplete data. The observed model is

Define

This is the set of possible empirical distributions over complete data consistent with the observed empirical distribution.

The E-step distribution is

It satisfies

Then

Thus the M-step is

19.3. ML Estimation in Exponential Families

Suppose

For i.i.d. data,

Differentiate wrt \(x_k\):

But

So ML satisfies the moment matching equations

Equivalently,

Geometry:

• \(\hat p_y\) defines a linear family of all distributions with the same expected sufficient statistics.
• The exponential family is orthogonal to that linear family.
• The ML model is the intersection.

20. 4/9/26: Stochastic Approximation

Many inference tasks are exact but computationally infeasible:

• computing partition functions,
• computing marginals,
• computing conditional distributions/posteriors,
• computing expectations,
• sampling from a target distribution.

Stochastic approximation uses samples to approximate these objects.

20.1. Monte Carlo

If \(x_1,\ldots,x_N\sim p\) i.i.d., then

estimates

It is unbiased and

Problem: often we cannot sample from \(p\), and may only know

up to an unknown partition function.

20.2. Importance Sampling

Suppose \(x_n\sim q\), and

Define importance weights

Then

Why it works:

So numerator and denominator converge to the right quantities and the ratio converges to \(\mathbb E_p[f]\).

Failure mode:

• If \(q(x)\) is tiny where \(p(x)|f(x)|\) is large, weights explode.
• Effective sample size collapses.
• This is why \(q\) is often chosen heavier-tailed than \(p\).

20.3. Rejection Sampling

Assume

Algorithm:

1. sample \(x\sim q\);
2. sample \(u\sim U([0,cq^\circ(x)])\);
3. accept \(x\) if \(u\le p^\circ(x)\), otherwise reject.

The acceptance probability is proportional to

20.4. Markov Chain Monte Carlo

MCMC constructs a Markov chain whose stationary distribution is the target \(p\). Samples are correlated, but asymptotically drawn from \(p\).

Detailed balance implies stationarity by summing over \(x'\).

A finite-state homogeneous Markov chain that is fully communicating and aperiodic converges to its unique stationary distribution:

20.5. Metropolis-Hastings

Given proposal \(v(x'|x)\), define the acceptance probability

Then transition to \(x'\) with probability

and stay at \(x\) with the leftover probability.

If the proposal is symmetric:

then

20.6. Correlation Time / Burn-In

MCMC samples are correlated. If the correlation time is large, \(N\) samples behave like far fewer independent samples.

• burn-in: discard early samples before approximate stationarity;
• mixing time: how long the chain takes to approach \(p\);
• proposal quality controls the tradeoff between exploration and acceptance rate.

21. 4/14/26: Typical Sequences and Large Deviations

21.1. WLLN

With finite variance, Chebyshev gives an \(O(1/N)\) bound, but large deviations will show many probabilities decay exponentially.

21.2. Typical Sequences

For i.i.d. \(y=(y_1,\ldots,y_N)\sim p^N\), define normalized log-likelihood

Since

WLLN gives

AEP:

and for large \(N\),

21.3. Divergence Typicality

For reference distribution \(q\), define normalized log-likelihood ratio

Under \(p\),

So define the divergence-typical set:

If \(y\) is generated from \(q\), then landing in \(p\)'s typical set is exponentially unlikely:

Mutual information version:

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

21.4. Large Deviations of Sample Averages

Let \(y_1,\ldots,y_N\sim q\) and \(t:\mathcal Y\to\mathbb R\), with

For \(\gamma>\mu\),

The dominant atypical distribution is a tilted exponential family:

with \(x>0\) chosen so that

Then

Equivalently, since

depending on log convention:

22. 4/16/26: Method of Types

22.1. Types and Type Classes

Let \(\mathcal Y=\{1,\ldots,M\}\). The type / empirical distribution of \(y=(y_1,\ldots,y_N)\) is

The set of all possible types is \(\mathcal P_N^\mathcal Y\). The type class of \(p\in\mathcal P_N^\mathcal Y\) is

Useful identity:

Taking logs:

22.2. Exponential Rate Notation

Rules:

22.3. Properties of Types

Number of types is polynomial:

So types are subexponential, while sequences are exponential.

If \(y\) has type \(\hat p\), then

For \(y\in T_N^\mathcal Y(p)\),

In particular,

Type class size:

More precisely,

Therefore,

22.4. Sanov's Theorem

Let \(\mathcal S\subset \mathcal P^\mathcal Y\), and consider the event

Sanov:

where

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

22.5. Large Deviations via Types

For sample average event

write it as a type event:

Then

where \(p_*\) is the I-projection of \(q\) onto \(\mathcal S\).

The boundary \(\mathbb E_p[t]=\gamma\) is a linear family. The I-projection lies on the exponential family

This recovers Cramer's theorem.

22.6. Dominant Atypical Behavior

Conditional limit theorem: if a rare type event \(\hat p\in\mathcal S\) occurs, then with high probability the observed type is close to the I-projection \(p_*\):

Pinsker:

So convergence in divergence implies \(L^1\) convergence.

23. 4/21/26: Asymptotics of Hypothesis Testing

23.1. Setup

Binary i.i.d. hypothesis test:

Normalized log-likelihood ratio:

Under \(H_0\):

Under \(H_1\):

23.2. Error Exponents for LRT

LRT:

For

define

with \(x_*\) chosen so that

Then

23.3. Neyman-Pearson Asymptotics / Stein

If \(P_F\le\alpha\) for fixed \(\alpha\in(0,1)\), then \(P_F\) is not required to decay exponentially. The optimal miss exponent is

This is Stein's lemma.

23.4. Bayesian Asymptotics

For priors \(\pi_0,\pi_1>0\) and nondegenerate costs,

Since priors and costs are constants,

To maximize the decay exponent, choose \(p_*\) so that

Equivalently,

23.5. Extreme Thresholds

If

then even \(H_0\)-typical data falls in the \(H_1\) region:

If

then even \(H_1\)-typical data falls in the \(H_0\) region:

so

24. 4/23/26: Sequence Convergence

24.1. Modes of Convergence

Almost-sure convergence is stronger:

Alternative characterization:

Equivalent characterization:

for all bounded continuous \(g\).

Pinsker implies:

so convergence in divergence is stronger than convergence in distribution.

Hierarchy:

24.2. Continuous Mapping and Slutsky

24.3. Sample Averages

SLLN:

Uniform LLN: for \(g(w;\theta)\) and compact \(\Theta\),

CLT:

Equivalently, for large \(N\),

25. 4/28/26: Asymptotics of Parameter Estimation

25.1. NonBayesian Asymptotics

Model:

where \(x\) is fixed but unknown.

25.2. Empirical Divergence View of ML

Define

The ML estimate minimizes \(\hat D_N(a)\):

By LLN, for fixed \(a\),

The population divergence is minimized at \(a=x\), assuming identifiability.

25.3. Finite Families

If \(|\mathcal X|<\infty\), \(|\mathcal Y|<\infty\), all pmfs are positive, and the true parameter is identifiable, then the ML estimator is weakly consistent:

Reason:

• for each wrong \(a\), \(\hat D_N(a)\to D(x,a)>0\);
• probability that wrong \(a\) beats \(x\) goes to zero;
• union bound over finitely many wrong \(a\)'s.

25.4. Exponential Families

Suppose

Let

The ML estimate satisfies moment matching:

Thus

Consistency:

by continuous mapping.

Asymptotic efficiency:

Using Taylor / mean value:

So

by Slutsky.

25.5. Mismatched ML

If the true distribution \(q_y\) is outside the model family, the ML estimator converges to the reverse I-projection:

Then under regularity,

25.6. Limits of Asymptotic Efficiency

Asymptotic efficiency is pointwise in \(x\). It is not a universal finite-sample MSE guarantee.

Hodges estimator example:

• modifies an efficient estimator by shrinking to zero in a small neighborhood;
• becomes super-efficient at \(x=0\);
• pays by being worse in shrinking neighborhoods around zero.

25.7. Bayesian Posterior Asymptotics

We want posterior behavior:

The denominator is a partition function/evidence. Laplace's method approximates it.

Interpretation:

• approximate log-integrand by a quadratic around its maximum;
• integral behaves like Gaussian mass near the mode;
• tails vanish exponentially.

For large \(N\),

With local coordinate

26. 4/30/26: Asymptotics of Inference and Universality

26.1. Universal Inference

Universal inference asks: can we predict future samples as well as if we knew the true model, after seeing enough data?

A sequence of predictors \(q_n(\cdot;y^{n-1})\) has average prediction loss

Equivalently,

where

26.2. Universal Prediction Theorem

Let

be the model capacity / minimax redundancy for length \(N\).

Proof sketch:

• If \(C_N/N\to0\), use the minimax mixture distribution induced by the least informative prior; its per-symbol redundancy vanishes.
• If a universal predictor exists, its joint distribution \(q_{y^N}\) has small worst-case divergence per symbol, so the minimax redundancy must also be small.

26.3. Universal Mixture Predictors

The universal predictor is a mixture:

where

So we update weights by likelihood:

26.4. Asymptotics of Model Capacity: Finite Families

For finitely many distinct positive models:

The asymptotic least informative prior is uniform:

Thus

so universal prediction is possible.

Interpretation:

• finite model identity costs only \(O(1)\) bits;
• amortized over \(N\) samples, cost per sample vanishes.

26.5. Continuous Parameter Families and Jeffreys Prior

For a one-dimensional regular family,

This gives

Thus

where

This is Jeffreys prior.

So

For \(d\)-dimensional parameters:

and

26.6. Misspecified Families

If the true distribution is outside the model family, no mixture over the family can become the true predictor. The asymptotic loss is lower bounded by

So the average prediction loss cannot vanish.

26.7. Universality over Classes

Suppose nested model classes

A mixtures-over-mixtures predictor has

where \(q_m\) is universal for class \(\mathcal P_m\).

If the true distribution lies in \(\mathcal P_m\), then

The second term vanishes for fixed \(m\).

27. 5/5/26: Model Order Selection

This section is the hard-decision counterpart to universality over classes.

In Lecture 26, we used a soft mixture over model classes. Here we choose one model order:

The index \(m\) is the model order. Larger \(m\) means richer class.

27.1. Overfitting and Generalized ML

Naive generalized ML chooses

Problem: if classes are nested, richer classes can fit at least as well:

So generalized ML over-selects complex models.

27.2. Bayesian Evidence and Occam Factor

Treat model class \(H_m\) as a hypothesis. Under \(H_m\), parameters have prior \(p_{x|H}(\cdot|H_m)\), and evidence is

Bayesian model selection chooses the class with largest posterior:

For large \(N\), the prior over classes is lower order, so evidence dominates.

Use Laplace:

in scalar case.

Interpretation:

• likelihood term rewards fit;
• Occam factor rewards models whose good-fit region is broad, i.e. simpler / less finely tuned;
• richer models have more parameter volume to integrate over and get penalized.

27.3. Bayes Information Criterion

For \(K_m\)-dimensional parameter \(x\) and i.i.d. data \(y^N\), Laplace gives

Thus choose

Equivalently, minimizing the usual BIC score:

Mental model:

27.4. Relation to Universal Inference

Lecture 26:

with penalty \(\log(1/\lambda_m)/N\).

Lecture 27:

with Laplace/BIC penalty \((K_m/2)\log N\).

Both express the same tension:

27.5. MDL and AIC

MDL: choose the model class giving shortest description length:

This connects inference and compression. BIC can be interpreted as an asymptotic approximation to MDL.

AIC: aims to minimize predictive KL risk even if the true distribution is not in any class. For i.i.d. data, it leads to choosing \(m\) maximizing approximately

Equivalently, minimizing the usual AIC:

Comparison:

So BIC penalizes complexity more strongly for large \(N\).

28. 5/7/26: Variational Inference

We have three approximation families:

• stochastic approximation: approximate by sampling;
• asymptotic approximation: approximate large-\(N\) behavior;
• variational approximation: replace evaluation/inference by optimization over a tractable class.

28.1. Variational Characterization of Partition Function

Suppose

Then

Proof:

So

Since \(D(q\|p)\ge0\),

with equality iff \(q=p\).

Restrict to tractable \(Q\subset\mathcal P^\mathcal Y\):

This is the variational lower bound.

28.2. Variational Approximation in Exponential Families

Suppose

The hard part is

Using the variational identity,

Restrict to a tractable family \(Q\):

The best variational approximation is

Important direction:

not

Caution:

is generally not normalized, because \(\tilde\alpha(x)\) is only a lower bound on \(\alpha(x)\). The actual usable approximation is \(q^*(\cdot;x)\), not the unnormalized plug-in distribution.

28.3. Mean-Field Approximation

A common tractable class is independent/product distributions:

The optimizer is the mean-field approximation.

Mental model:

• true \(p\) may have complicated dependence;
• \(q\) is forced to factorize;
• optimize factors to best approximate \(p\) in \(D(q\|p)\).

Because \(D(q\|p)\) is mode-seeking, mean-field can underrepresent uncertainty / correlations.

28.4. Latent Variable Models and ELBO

For latent variable model

the evidence is

For any \(q(s)\),

where

Thus

This is the ELBO.

Equivalent form:

EM relation:

• Exact E-step sets \(q(s)=p_{s|y}(s|y;x^{(l-1)})\), making the bound tight.
• M-step maximizes the tight lower bound over \(x\).
• Variational EM restricts \(q\in Q\), so E-step chooses best approximate posterior.

28.5. Model Architecture Selection

For model class \(H_m\), evidence is

If exact evidence is hard, use variational lower bound:

Then choose the model with largest variational evidence lower bound.

28.6. Summary

• Partition function identity:

  \[ \log Z=\max_q\{H(q)+\mathbb E_q[\log\tilde p]\}. \]

• Restrict \(q\in Q\) to get lower bound.
• VI optimizes \(D(q\|p)\), not \(D(p\|q)\).
• Mean-field chooses \(Q\) as product distributions.
• ELBO:

  \[ \log p_y(y)=\mathrm{ELBO}(q)+D(q\|p_{s|y}). \]

• EM is exact variational inference for latent variables.