| # | date | topic | description |
|---|---|---|---|
| 1 | 24-Aug-2026 | Introduction | |
| 2 | 26-Aug-2026 | Foundations of learning | Drop/Add |
| 3 | 31-Aug-2026 | PAC learnability | HW1 |
| 4 | 02-Sep-2026 | Linear learning models | |
| 5 | 07-Sep-2026 | Labor Day Holiday | Holiday |
| 6 | 09-Sep-2026 | Principal Component Analysis | Project ideas |
| 7 | 14-Sep-2026 | Curse of Dimensionality | HW2, HW1 due |
| 8 | 16-Sep-2026 | Bayesian Decision Theory | |
| 9 | 21-Sep-2026 | Parameter estimation: MLE | |
| 10 | 23-Sep-2026 | Parameter estimation: MAP & NB | finalize teams |
| 11 | 28-Sep-2026 | Logistic Regression | HW3, HW2 due |
| 12 | 30-Sep-2026 | Kernel Density Estimation | |
| 13 | 05-Oct-2026 | Support Vector Machines | |
| 14 | 07-Oct-2026 | Matrix Factorization | |
| 15 | 12-Oct-2026 | * Midterm | Exam, HW3 due |
| 16 | 14-Oct-2026 | k-means clustering | |
| 17 | 19-Oct-2026 | Invited: Intro to Causal Learning I |
| # | date | topic | description |
|---|---|---|---|
| 18 | 21-Oct-2026 | Invited: Intro to Causal Learning II | |
| 19 | 26-Oct-2026 | * Mid-point projects checkpoint | HW4, P |
| 20 | 28-Oct-2026 | Expectation Maximization | |
| 21 | 02-Nov-2026 | Stochastic Gradient Descent | |
| 22 | 04-Nov-2026 | Automatic Differentiation | |
| 23 | 09-Nov-2026 | Nonlinear embedding approaches | HW5, HW4 due |
| 24 | 11-Nov-2026 | Model comparison | |
| 25 | 16-Nov-2026 | Model Calibration | |
| 26 | 18-Nov-2026 | Convolutional Neural Networks | |
| 27 | 23-Nov-2026 | Thanksgiving Break | Holiday |
| 28 | 25-Nov-2026 | Thanksgiving Break | Holiday |
| 29 | 30-Nov-2026 | Word Embedding | |
| 30 | 02-Dec-2026 | Project Final Presentations | HW5 due, P |
| 31 | 07-Dec-2026 | Presentation spillover / Exam prep | Classes End |
| 32 | 09-Dec-2026 | * Final Exam | Exam |
| 33 | 16-Dec-2026 | Project Reports | due |
| 34 | 17-Dec-2026 | Grades due 5 p.m. | PAWS |
| # | date | topic |
|---|---|---|
| 2–4 | Aug–Sep | ERM, PAC & Linear Models |
| 6–7 | 09–14 Sep | PCA & Curse of Dimensionality |
| 8 | 16-Sep-2026 | Bayesian Decision Theory |
| 9–10 | 21–23 Sep | Parameter Estimation: MLE, MAP & NB |
| 11 | 28-Sep-2026 | Logistic Regression |
| 12 | 30-Sep-2026 | Kernel Density Estimation |
| 13 | 05-Oct-2026 | Support Vector Machines |
| 14 | 07-Oct-2026 | Matrix Factorization |
| 16 | 14-Oct-2026 | k-means clustering |
| 17–18 | 19–21 Oct | Intro to Causal Learning I & II |
| 19 | 26-Oct-2026 | Mid-point projects checkpoint |
| 20 | 28-Oct-2026 | Expectation Maximization |
Likelihood: $\prob{p}{\vec{x}} = \sum_{k=1}^K \pi_k\prob{N}{\vec{x}|\vec{\mu}_k, \bm{\Sigma}_k}$
$$\begin{aligned} \mbox{for simplicity }\bm{\Sigma}_k & = \sigma^2 \bm{I}\\ \prob{p}{\vec{x}|y=k} & = \prob{N}{\vec{\mu}_k, \sigma^2 \bm{I}}\\ \prob{p}{y=k} & = \pi_k\\ \mbox{parameters: } & \vec{\mu}_1, \dots, \vec{\mu}_K, \; \sigma^2, \; \pi_1, \dots, \pi_K \end{aligned}$$
$$\ln \prob{p}{\bm{X}|\{\vec{\mu}_k\}, \{\bm{\Sigma}_k\}, \{\pi_k\}} = \sum_{n=1}^N \ln\left\{\sum_{k=1}^K \pi_k \prob{N}{\vec{x}_n|\vec{\mu}_k, \sigma_k^2\bm{I}} \right\}$$
$${\cal N}(x_i \mid \mu_k = x_i, \sigma_k^2) = \frac{1}{\sqrt{2\pi}\,\sigma_k} \to \infty \quad \text{as} \quad \sigma_k \to 0$$
recall logistic regression and softmax!
Using the good old Newton-Raphson update: $\mu_k \leftarrow \mu_k - \frac{\partial {\cal L}}{\partial \mu_k}\Big/\frac{\partial^2 {\cal L}}{\partial \mu_k^2}$
Yields the weighted average update: $$\mu_k = \frac{\sum_n \prob{P}{k|x_n,\vec{\theta}} x_n}{\sum_n \prob{P}{k|x_n,\vec{\theta}} }$$
Update
- Responsibilities $r_k^n = \prob{P}{k|\vec{x}_n,\vec{\theta}}$ are posteriors over latent cluster assignments
- Update is maximization of the likelihood holding responsibilities fixed
Both "hacky" approaches to solve a latent variable problem are instances of a rigorous general principle:
Expectation Maximization (EM): a meta-algorithm
Convex
Strictly convex
Strongly convex
Theorem:
If $f(x)$ is twice differentiable on $[a,b]$ and $f^{\prime \prime}(x) \ge 0$ on $[a,b]$ then $f(x)$ is convex on $[a,b]$.
Theorem:
$-\ln(x)$ is strictly convex on $(0, \infty)$ $\left(\text{since } \frac{d^2}{dx^2}[-\ln x] = \frac{1}{x^2} > 0\right)$
Theorem:
Let $f$ be a convex function on an interval $I$. If $x_1, x_2, \dots, x_n \in I$ with $\lambda_1, \lambda_2, \dots, \lambda_n \ge 0$ and $\sum_{i=1}^n\lambda_i=1$: $$f\left(\sum_{i=1}^n\lambda_ix_i\right) \le \sum_{i=1}^n \lambda_i f(x_i)$$
Since $-\ln(x)$ is strictly convex, $\ln(x)$ is strictly concave, which reverses the inequality: $$\ln\left(\sum_{i=1}^n\lambda_ix_i\right) \ge \sum_{i=1}^n \lambda_i \ln{(x_i)}$$In expectation notation (for $\lambda_i = q(z_i)$): $\ln \EE_{q}[X] \ge \EE_{q}[\ln X]$, with equality iff $x_1 = x_2 = \dots = x_n$.
Jensen's inequality $\ln\left(\sum_{\vec{z}} \lambda_{\vec{z}} x_{\vec{z}}\right) \ge \sum_{\vec{z}} \lambda_{\vec{z}} \ln(x_{\vec{z}})$ needs weights $\lambda_{\vec{z}} \ge 0$ with $\sum_{\vec{z}} \lambda_{\vec{z}} = 1$.
$$\lambda_{\vec{z}} = \prob{P}{\vec{z}|\bm{X}, \vth_n} \qquad \left(\text{since } \sum_{\vec{z}} \prob{P}{\vec{z}|\bm{X}, \vth_n} = 1\right)$$
Use $\ln(A/B) = \ln A - \ln B$ and $\prob{P}{\bm{X}|\vec{z},\vth}\prob{P}{\vec{z}|\vth} = \prob{P}{\bm{X},\vec{z}|\vth}$ to split the $\ln$:
$\displaystyle \Delta(\vth|\vth_n) = \sum_{\vec{z}} \underbrace{\color{#268bd2}{\prob{P}{\vec{z}|\bm{X}, \vth_n}}}_{\substack{\text{fixed weights}\\ \text{(only old }\vth_n\text{!)}}} \ln \underbrace{\color{#859900}{\prob{P}{\bm{X}, \vec{z}|\vth}}}_{\substack{\text{complete-data likelihood}\\ \text{(no sum inside }\ln\text{!)}}} \;-\; \underbrace{\sum_{\vec{z}} \prob{P}{\vec{z}|\bm{X}, \vth_n} \ln \big(\prob{P}{\vec{z}|\bm{X}, \vth_n}\prob{P}{\bm{X}|\vth_n}\big)}_{\text{constant w.r.t. }\vth\text{!}}$
$\displaystyle \underbrace{\prob{L}{\vth} - \prob{L}{\vth_n}}_{\text{True improvement}} \;\ge\; \underbrace{\Delta(\vth|\vth_n)}_{\text{Guaranteed improvement}}$
$\displaystyle \prob{L}{\vth} \;\ge\; \underbrace{\prob{L}{\vth_n} + \Delta(\vth|\vth_n)}_{\def\; {\cal L}(\vth|\vth_n)}$
$\displaystyle \prob{L}{\vth_{n+1}} \;\ge\; {\cal L}(\vth_{n+1}|\vth_n) \;\ge\; {\cal L}(\vth_n|\vth_n) \;=\; \prob{L}{\vth_n}$
$\displaystyle \vth_{n+1} = \underset{\vth}{\argmax} \; \underbrace{\EE_{\vec{z}|\bm{X}, \vth_n}\!\left[ \ln \prob{P}{\bm{X}, \vec{z}|\vth} \right]}_{\def\; Q(\vth|\vth_n)}$
1. Expectation Step (E-Step): Build the analytical objective $Q(\vth|\vth_n)$
Requires a known analytical form for the complete-data log-likelihood $\ln \prob{P}{\bm{X}, \vec{z}|\vth}$!
Evaluate posterior $\prob{P}{\vec{z}|\bm{X}, \vth_n}$ at fixed $\vth_n$, keeping $\vth$ as a free symbolic variable:$\displaystyle Q(\vth|\vth_n) = \EE_{\vec{z}|\bm{X},\vth_n}\!\left[\ln \prob{P}{\bm{X}, \vec{z}|\vth}\right] = \sum_{\vec{z}} \underbrace{\prob{P}{\vec{z}|\bm{X}, \vth_n}}_{\text{numbers (at }\vth_n\text{)}} \;\cdot\; \underbrace{\ln \prob{P}{\bm{X}, \vec{z}|\vth}}_{\text{analytical formula in }\vth}$
2. Maximization Step (M-Step): Maximize $Q(\vth|\vth_n)$ over $\vth$
$\displaystyle \vth_{n+1} = \underset{\vth}{\argmax} \; Q(\vth|\vth_n) \qquad \Big(\text{solve } \nabla_{\vth} Q(\vth|\vth_n) = \vec{0}\Big)$
This gap between two distributions $q(\vec{z})$ and $p(\vec{z})$ is the Kullback-Leibler (KL) Divergence!
How different is distribution $q$ from target distribution $p$?
$$D_{\text{KL}}(q \parallel p) \;\def\; \sum_{\vec{z}} q(\vec{z}) \ln \frac{q(\vec{z})}{p(\vec{z})} \;=\; \EE_{q}\!\left[\ln \frac{q(\vec{z})}{p(\vec{z})}\right]$$
Left: $\argmin_q D_{\text{KL}}(p \parallel q)$ spreads over all modes | Right: $\argmin_q D_{\text{KL}}(q \parallel p)$ locks onto one mode (used in EM!)
For any probability distribution $q(\vec{z})$ over the hidden variables:
$\displaystyle \underbrace{\ln \prob{P}{\bm{X}|\vth}}_{\text{True Log-Likelihood } L(\vth)} \;=\; \underbrace{\sum_{\vec{z}} q(\vec{z}) \ln \frac{\prob{P}{\bm{X}, \vec{z}|\vth}}{q(\vec{z})}}_{\text{Evidence Lower Bound } \text{ELBO}(q, \vth)} \;+\; \underbrace{D_{\text{KL}}\!\left(q(\vec{z}) \;\middle\|\; \prob{P}{\vec{z}|\bm{X}, \vth}\right)}_{\text{Gap } \ge\, 0}$
If true $\prob{P}{\vec{z}|\bm{X}, \vth}$ is intractable, pick the closest tractable $q(\vec{z})$ $\implies$ Variational Inference & VAEs!
$\displaystyle \ln \prob{P}{\bm{X}|\vth} = \sum_{n=1}^N \ln \left\{ \sum_{k=1}^K \pi_k \prob{N}{\vec{x}_n|\vec{\mu}_k, \bm{\Sigma}_k} \right\}$
$\displaystyle \prob{P}{\vec{z}_n|\vth} = \prod_{k=1}^K \pi_k^{z_{nk}}, \qquad \prob{P}{\vec{x}_n|\vec{z}_n, \vth} = \prod_{k=1}^K \prob{N}{\vec{x}_n|\vec{\mu}_k, \bm{\Sigma}_k}^{z_{nk}}$
$\displaystyle \implies \prob{P}{\bm{X}, \bm{Z}|\vth} = \prod_{n=1}^N \prod_{k=1}^K \Big[ \pi_k \prob{N}{\vec{x}_n|\vec{\mu}_k, \bm{\Sigma}_k} \Big]^{z_{nk}}$
Now take $\ln$ of the product $\prob{P}{\bm{X}, \bm{Z}|\vth}$ — the exponent $z_{nk}$ comes down in front!
$\displaystyle \ln \prob{P}{\bm{X}, \bm{Z} | \vth} = \ln \prod_{n=1}^N \prod_{k=1}^K \Big[ \pi_k \prob{N}{\vec{x}_n|\vec{\mu}_k, \bm{\Sigma}_k} \Big]^{z_{nk}} = \sum_{n=1}^N \sum_{k=1}^K z_{nk} \Big[ \ln \pi_k + \ln \prob{N}{\vec{x}_n | \vec{\mu}_k, \bm{\Sigma}_k} \Big]$
$\displaystyle Q(\vth|\vth_n) = \sum_{n=1}^N \sum_{k=1}^K \gamma_{nk} \Big[ \ln \pi_k + \ln \prob{N}{\vec{x}_n | \vec{\mu}_k, \bm{\Sigma}_k} \Big]$
$\displaystyle \text{where } \gamma_{nk} \;\def\; \EE[z_{nk} | \vec{x}_n, \vth_n] = \prob{P}{z_{nk} = 1 | \vec{x}_n, \vth_n}$
1. E-Step: Soft responsibilities $\gamma_{nk}$ and effective cluster size $N_k$
$$\gamma_{nk} = \frac{\pi_k \prob{N}{\vec{x}_n \mid \vec{\mu}_k, \bm{\Sigma}_k}}{\sum_{j=1}^K \pi_j \prob{N}{\vec{x}_n \mid \vec{\mu}_j, \bm{\Sigma}_j}}, \qquad N_k = \sum_{n=1}^N \gamma_{nk}$$
2. M-Step: Update means, covariances, and mixing weights
$$\begin{aligned} \vec{\mu}_k^{\text{new}} &= \frac{1}{N_k} \sum_{n=1}^N \gamma_{nk} \vec{x}_n, \qquad \pi_k^{\text{new}} = \frac{N_k}{N} \\ \bm{\Sigma}_k^{\text{new}} &= \frac{1}{N_k} \sum_{n=1}^N \gamma_{nk} (\vec{x}_n - \vec{\mu}_k^{\text{new}})(\vec{x}_n - \vec{\mu}_k^{\text{new}})^T \end{aligned}$$
Fix spherical covariance $\bm{\Sigma}_k = \sigma^2 \bm{I}$ and equal weights $\pi_k = 1/K$:
$\displaystyle \gamma_{nk} = \frac{\exp\!\left(-\frac{\|\vec{x}_n - \vec{\mu}_k\|^2}{2\sigma^2}\right)}{\sum_{j=1}^K \exp\!\left(-\frac{\|\vec{x}_n - \vec{\mu}_j\|^2}{2\sigma^2}\right)} \;\xrightarrow{\;\sigma^2 \to 0\;}\; \begin{cases} 1 & \text{if } k = \argmin_j \|\vec{x}_n - \vec{\mu}_j\|^2 \\ 0 & \text{otherwise} \end{cases}$