%!TEX program = xelatex
% miko:title: Machine Learning
% miko:summary: A concise guide to machine learning.
% miko:category: ml
% miko:type: complete
% miko:origin: ai
% miko:tags: ml
% miko:difficulty: undergrad
% miko:keywords: machine learning

\documentclass[a4paper,11pt]{article}
\usepackage{amsmath,amssymb,mathtools,bm}
\usepackage[margin=25mm]{geometry}
\usepackage{hyperref}
\usepackage{enumitem}

\title{Complete Machine Learning}
\author{Miko-pedia AI}
\date{\today}

\begin{document}
\maketitle
\tableofcontents

\textbf{Overview.} This complete note surveys the foundations and practice of machine learning at the undergraduate level. It moves from the conceptual framing of learning problems (data, loss, generalization) through mathematical foundations, classical methods, deep learning, generative models, and reinforcement learning, concluding with practical deployment and ethics. Each section contains definitions, algorithms, key equations, and review guidance. The note is designed as a comprehensive review resource: study it holistically or jump to individual sections for targeted revision.

\section{The Questions of ML: Data, Loss, Generalization, and Evaluation}
\subsection{Core ideas}

Machine learning (ML) constructs algorithms that improve on task $T$, with respect to performance metric $P$, based on experience $E$. In statistical ML, this is formalized as selecting a function from a hypothesis class to minimize expected error.

\textbf{Problem Setup:}
\begin{itemize}[nosep]
  \item \textbf{Data}: Drawn from an unknown joint distribution $\mathcal{D}$ over inputs $\mathbf{x} \in \mathcal{X}$ and targets $y \in \mathcal{Y}$. A training set $S = \{(\mathbf{x}^{(i)}, y^{(i)})\}_{i=1}^n$ is sampled i.i.d.\ from $\mathcal{D}$.
  \item \textbf{Hypothesis Class ($\mathcal{H}$)}: The set of all possible models $f_\theta : \mathcal{X} \to \mathcal{Y}$ the learning algorithm can consider (e.g., all linear functions, or neural networks of a fixed architecture).
  \item \textbf{Loss Function}: $\ell(f(\mathbf{x}), y) \in \mathbb{R}_{\ge 0}$ measures the cost of a prediction.
\end{itemize}

\textbf{Risk and Generalization:}
\begin{itemize}[nosep]
  \item \textbf{Expected Risk}: The true objective, $R(f) = \mathbb{E}_{(\mathbf{x},y)\sim \mathcal{D}}[\ell(f(\mathbf{x}), y)]$. Since $\mathcal{D}$ is unknown, we cannot directly minimize $R(f)$.
  \item \textbf{Empirical Risk Minimization (ERM)}: We approximate $R(f)$ using the training data: $\hat{R}_S(f) = \frac{1}{n}\sum_{i=1}^n \ell(f(\mathbf{x}^{(i)}), y^{(i)})$. ERM selects $\hat{f} = \arg\min_{f \in \mathcal{H}} \hat{R}_S(f)$.
  \item \textbf{Generalization Gap}: The difference $R(f) - \hat{R}_S(f)$. A large gap indicates \textbf{overfitting} (low empirical risk but high expected risk, often due to high capacity in $\mathcal{H}$). Conversely, \textbf{underfitting} occurs if $\mathcal{H}$ is too restrictive, leading to high training and test errors.
\end{itemize}

\textbf{Learning paradigms:}
\begin{itemize}[nosep]
  \item \textbf{Supervised}: Learn $f: \mathcal{X} \to \mathcal{Y}$ given fully labeled pairs.
  \item \textbf{Unsupervised}: Discover structure (clusters, manifolds, density) from unlabeled data $\{\mathbf{x}^{(i)}\}_{i=1}^n$.
  \item \textbf{Self-supervised}: Formulate supervised tasks from unlabeled data (e.g., predicting masked words or geometric transformations).
  \item \textbf{Reinforcement learning (RL)}: Learn a policy $\pi(\mathbf{a}|\mathbf{s})$ to maximize cumulative rewards in sequential environments.
\end{itemize}

\textbf{Evaluation Metrics:}
Held-out test sets estimate $R(f)$. Common empirical metrics include: Accuracy, Precision/Recall, and F1 for classification; Mean Squared Error (MSE) and Mean Absolute Error (MAE) for regression; and Area Under the ROC Curve (AUC-ROC) for binary confidence scores.

For review, be able to: define task, performance, and experience; contrast expected and empirical risk; explain the ERM principle and the role of the hypothesis class $\mathcal{H}$; and classify tasks into paradigms.

\paragraph{Section summary}
ML formalizes learning as optimization: we seek a hypothesis $f \in \mathcal{H}$ that minimizes empirical risk on training data while generalizing to the true distribution. Controlling the complexity of $\mathcal{H}$ to balance underfitting and overfitting is the central challenge.

\section{Mathematical Foundations: Linear Algebra, Calculus, Probability, and Optimization}
\subsection{Core ideas}

\textbf{Linear algebra} provides the language for representing data and models.
\begin{itemize}[nosep]
  \item A vector $\mathbf{x} \in \mathbb{R}^d$ is an ordered $d$-tuple; the inner product $\mathbf{w}^\top\mathbf{x} = \sum_{j=1}^d w_j x_j$ measures similarity.
  \item A matrix $\mathbf{X} \in \mathbb{R}^{n \times d}$ represents $n$ data points each with $d$ features.
  \item The transpose $(\mathbf{X}^\top)_{ij} = \mathbf{X}_{ji}$; the identity $\mathbf{I}_d$; the inverse $\mathbf{A}^{-1}$ satisfies $\mathbf{A}^{-1}\mathbf{A} = \mathbf{I}$.
  \item Eigendecomposition: $\mathbf{A}\mathbf{v} = \lambda \mathbf{v}$ for square $\mathbf{A}$. Symmetric positive-definite matrices have orthogonal eigenvectors and positive eigenvalues.
  \item Singular value decomposition (SVD): $\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^\top$ for any $\mathbf{A} \in \mathbb{R}^{m \times n}$, where $\mathbf{U},\mathbf{V}$ are orthogonal and $\boldsymbol{\Sigma}$ is diagonal with singular values $\sigma_1 \ge \cdots \ge \sigma_{\min(m,n)} \ge 0$.
  \item Norms: $L^2$ norm $\|\mathbf{x}\|_2 = \sqrt{\sum_j x_j^2}$; $L^1$ norm $\|\mathbf{x}\|_1 = \sum_j |x_j|$; Frobenius norm $\|\mathbf{A}\|_F = \sqrt{\sum_{ij} A_{ij}^2}$.
\end{itemize}

\textbf{Calculus} enables optimization.
\begin{itemize}[nosep]
  \item The gradient $\nabla_\mathbf{w} f(\mathbf{w})$ is the vector of partial derivatives; it points in the direction of steepest ascent.
  \item The chain rule: if $z = g(f(\mathbf{w}))$, then $\nabla_\mathbf{w} z = \frac{dg}{df} \cdot \nabla_\mathbf{w} f$.
  \item Hessian $\mathbf{H}_{ij} = \frac{\partial^2 f}{\partial w_i \partial w_j}$ encodes curvature; positive-definite Hessian $\implies$ local minimum.
  \item Taylor expansion: $f(\mathbf{w}+\boldsymbol{\delta}) \approx f(\mathbf{w}) + \nabla f(\mathbf{w})^\top\boldsymbol{\delta} + \frac12 \boldsymbol{\delta}^\top \mathbf{H} \boldsymbol{\delta}$.
\end{itemize}

\textbf{Probability} quantifies uncertainty.
\begin{itemize}[nosep]
  \item Random variable $X$ with distribution $P(X)$; expectation $\mathbb{E}[X] = \sum_x x P(x)$ (discrete) or $\int x p(x)\,dx$ (continuous).
  \item Conditional probability $P(Y|X) = P(X,Y)/P(X)$; Bayes' rule: $P(Y|X) = P(X|Y)P(Y)/P(X)$.
  \item Variance $\text{Var}(X) = \mathbb{E}[(X-\mathbb{E}[X])^2]$; covariance $\text{Cov}(X,Y) = \mathbb{E}[(X-\mathbb{E}[X])(Y-\mathbb{E}[Y])]$.
  \item Common distributions: Bernoulli$(\mu)$, Binomial$(n,\mu)$, Gaussian $\mathcal{N}(\mu,\sigma^2)$, Multinomial, Exponential.
  \item Law of large numbers: sample mean converges to expectation. Central limit theorem: sum of i.i.d.\ variables is approximately Gaussian.
\end{itemize}

\textbf{Optimization} finds parameters minimizing a loss.
\begin{itemize}[nosep]
  \item Convex functions: $f(\lambda\mathbf{w}_1+(1-\lambda)\mathbf{w}_2) \le \lambda f(\mathbf{w}_1) + (1-\lambda) f(\mathbf{w}_2)$. Convex problems have no local minima other than the global minimum.
  \item Gradient descent: $\mathbf{w}_{t+1} = \mathbf{w}_t - \eta\nabla f(\mathbf{w}_t)$ where $\eta$ is the learning rate.
  \item Stochastic gradient descent (SGD): uses a minibatch estimate of the gradient for efficiency.
  \item First-order methods (SGD, momentum, Adam) scale to high dimensions; second-order methods (Newton) use curvature but are costly.
\end{itemize}

For review, be able to: compute gradients via the chain rule; apply Bayes' rule; derive the normal equations; explain SVD; implement gradient descent; and recognize convex functions.

\paragraph{Section summary}
ML rests on linear algebra (representing data and models), calculus (optimizing via gradients), probability (modeling noise and uncertainty), and optimization (finding parameters). The normal equations solve linear regression analytically; for most models we use iterative gradient-based methods.

\section{Linear Models: Regression, Classification, and Regularization}
\subsection{Core ideas}

\textbf{Linear regression} models the target as a continuous function $f(\mathbf{x}) = \mathbf{w}^\top\mathbf{x} + b$. Under squared error loss, the empirical risk is:
\[
\mathcal{L}(\mathbf{w}, b) = \frac{1}{2n}\sum_{i=1}^n (\mathbf{w}^\top\mathbf{x}^{(i)} + b - y^{(i)})^2.
\]
By appending $1$ to each $\mathbf{x}^{(i)}$ to absorb $b$, the closed-form normal equations yield $\mathbf{w}^* = (\mathbf{X}^\top\mathbf{X})^{-1}\mathbf{X}^\top\mathbf{y}$. This requires $\mathbf{X}^\top\mathbf{X}$ to be invertible (full column rank).

\textbf{Logistic regression} is for binary classification, modeling the probability of the positive class using the logistic sigmoid function $\sigma(z) = 1/(1+e^{-z})$:
\[
P(y=1|\mathbf{x}) = \hat{y} = \sigma(\mathbf{w}^\top\mathbf{x} + b).
\]
\textit{Log-odds interpretation}: It models the log-odds as a linear function: $\log(\frac{\hat{y}}{1-\hat{y}}) = \mathbf{w}^\top\mathbf{x} + b$.
Optimized via gradient descent or Newton's method using the binary cross-entropy (log-loss):
\[
\mathcal{L}(\mathbf{w}) = -\frac{1}{n}\sum_{i=1}^n \bigl[y^{(i)}\log\hat{y}^{(i)} + (1-y^{(i)})\log(1-\hat{y}^{(i)})\bigr].
\]

\textbf{Softmax regression} (multinomial logistic regression) generalizes to $K$ classes:
\[
P(y=k|\mathbf{x}) = \hat{y}_k = \frac{\exp(\mathbf{w}_k^\top\mathbf{x})}{\sum_{j=1}^K \exp(\mathbf{w}_j^\top\mathbf{x})}.
\]
Loss is the categorical cross-entropy: $\mathcal{L}(\mathbf{W}) = -\frac{1}{n}\sum_{i=1}^n \sum_{k=1}^K \mathbb{1}[y^{(i)}=k] \log\hat{y}^{(i)}_k$.

\textbf{Generalized Linear Models (GLMs)} unify these approaches by assuming the target $y$ follows a distribution from the Exponential Family (e.g., Gaussian for linear regression, Bernoulli for logistic, Poisson for counts) and modeling the natural parameter as a linear combination of features $\eta = \mathbf{w}^\top\mathbf{x}$.

\textbf{Regularization} prevents overfitting by penalizing large weights:
\begin{itemize}[nosep]
  \item $L^2$ \textbf{(Ridge)}: Penalty $\lambda\|\mathbf{w}\|_2^2$. Closed-form: $\mathbf{w}^* = (\mathbf{X}^\top\mathbf{X} + \lambda\mathbf{I})^{-1}\mathbf{X}^\top\mathbf{y}$. Shrinks all weights.
  \item $L^1$ \textbf{(Lasso)}: Penalty $\lambda\|\mathbf{w}\|_1$. Induces sparsity (some weights become exactly zero), acting as feature selection.
  \item \textbf{Elastic Net}: Combines $L^1$ and $L^2$ penalties $\alpha\|\mathbf{w}\|_1 + (1-\alpha)\|\mathbf{w}\|_2^2/2$.
\end{itemize}

\textbf{Assumptions}: Ordinary least squares assumes $\mathbb{E}[y|\mathbf{x}]$ is linear, errors are i.i.d.\ homoscedastic (constant variance) and normally distributed, and no perfect multicollinearity.

For review, be able to: derive the normal equations; explain the log-odds interpretation of logistic regression; formulate linear and logistic regression as GLMs; compare $L^1$ vs $L^2$ regularization geometrically; and diagnose multicollinearity.

\paragraph{Section summary}
Linear models are the simplest parametric models: regression via least squares, classification via logistic/softmax with cross-entropy. They can be unified under GLMs. Regularization controls overfitting by penalizing weight magnitudes. These models are strictly convex and serve as fundamental baselines.

\section{Evaluation: Cross-Validation, Overfitting, and Bias-Variance Tradeoff}
\subsection{Core ideas}

\textbf{Overfitting} occurs when a model learns noise in the training data, achieving low training error but high test error. It happens with:
\begin{itemize}[nosep]
  \item Too many parameters relative to sample size ($d \gg n$).
  \item Training too long (over-optimization).
  \item No regularization or too much capacity.
\end{itemize}
\textbf{Underfitting} occurs when the model is too simple to capture the underlying pattern.

\textbf{Bias--variance decomposition} (for squared error):
\[
\mathbb{E}[(\hat{f}(\mathbf{x}) - y)^2] = \underbrace{(\mathbb{E}[\hat{f}(\mathbf{x})] - f^*(\mathbf{x}))^2}_{\text{Bias}^2} + \underbrace{\mathbb{E}[(\hat{f}(\mathbf{x}) - \mathbb{E}[\hat{f}(\mathbf{x})])^2]}_{\text{Variance}} + \underbrace{\mathbb{E}[(y - f^*(\mathbf{x}))^2]}_{\text{Irreducible error}}.
\]
Bias measures how much the model's average prediction deviates from the truth. Variance measures how much predictions fluctuate across different training sets. Simple models have high bias, low variance; complex models have low bias, high variance. The tradeoff guides model selection.

\textbf{Cross-validation} estimates generalization without wasting data:
\begin{itemize}[nosep]
  \item $k$-fold CV: split data into $k$ folds, train on $k-1$, test on the held-out fold, repeat $k$ times, average metrics. Typical $k = 5$ or $10$.
  \item Leave-one-out CV (LOOCV): $k = n$, expensive but nearly unbiased.
  \item Stratified CV: preserves class proportions in each fold.
  \item Train/validation/test split: hold out a test set at the very end, use validation set(s) for model selection.
\end{itemize}

\textbf{Hyperparameter tuning}: model capacity (degree of polynomial, $k$ in $k$-NN, $\lambda$ in ridge), learning rate, network architecture. Use validation performance (not test performance) for selection.

\textbf{Learning curves}: plot training and validation error vs.\ dataset size or training epochs. Gaps indicate overfitting; convergence to high error indicates underfitting.

\textbf{Diagnostics}:
\begin{itemize}[nosep]
  \item Training error $\ll$ validation error $\implies$ overfitting (increase regularization, get more data, reduce capacity).
  \item Both errors high $\implies$ underfitting (increase capacity, reduce regularization, add features).
\end{itemize}

For review, be able to: derive the bias--variance decomposition; explain why cross-validation is needed; choose $k$ in $k$-fold CV; interpret learning curves; and design a model selection pipeline.

\paragraph{Section summary}
Generalization is the central concern of ML. The bias--variance tradeoff explains why we need regularized, capacity-controlled models. Cross-validation provides a reliable estimate of test performance for model selection. Always keep a separate test set for final evaluation.

\section{Classical ML: Trees, SVMs, PCA, Clustering, and Ensembles}
\subsection{Core ideas}

\textbf{Decision trees} recursively partition the feature space into hyper-rectangles:
\begin{itemize}[nosep]
  \item \textbf{Splitting criterion}: At each node, select a feature $j$ and threshold $t$ to maximize information gain (decrease in impurity): $IG = H(\text{parent}) - \sum_{v} \frac{|D_v|}{|D|} H(D_v)$.
  \item \textbf{Impurity measures ($H$)}: Entropy $-\sum_k p_k \log p_k$ or Gini impurity $1 - \sum_k p_k^2$ for classification; Mean Squared Error (MSE) for regression.
  \item \textbf{Regularization}: Trees easily overfit. Mitigated by setting max depth, minimum samples per leaf, or cost-complexity pruning.
\end{itemize}

\textbf{Support vector machines (SVMs)} find the maximum-margin separating hyperplane.
\begin{itemize}[nosep]
  \item \textbf{Primal formulation}: $\min_{\mathbf{w},b} \frac12\|\mathbf{w}\|_2^2 + C \sum_{i=1}^n \xi_i$ subject to $y^{(i)}(\mathbf{w}^\top\mathbf{x}^{(i)} + b) \ge 1 - \xi_i$, where $\xi_i \ge 0$ are slack variables for non-separable data (soft-margin). $C$ controls the margin vs.\ misclassification penalty.
  \item \textbf{Dual formulation}: $\max_{\boldsymbol{\alpha}} \sum_i \alpha_i - \frac12 \sum_{i,j} \alpha_i\alpha_j y^{(i)}y^{(j)}\mathbf{x}^{(i)\top}\mathbf{x}^{(j)}$, with $0 \le \alpha_i \le C$. The solution depends only on support vectors (points where $\alpha_i > 0$).
  \item \textbf{Kernel trick}: By the Representer Theorem, the optimal weights lie in the span of the data: $\mathbf{w} = \sum_i \alpha_i y^{(i)} \phi(\mathbf{x}^{(i)})$. We can replace inner products with a kernel function $k(\mathbf{x}, \mathbf{x}') = \langle\phi(\mathbf{x}),\phi(\mathbf{x}')\rangle$. Common kernels: Polynomial $(\mathbf{x}^\top\mathbf{x}' + c)^d$, RBF $\exp(-\gamma\|\mathbf{x}-\mathbf{x}'\|_2^2)$.
\end{itemize}

\textbf{PCA} (principal component analysis) finds an orthogonal projection of data onto a lower dimensional linear space that maximizes variance.
\begin{itemize}[nosep]
  \item Center the data: $\mathbf{X}_c = \mathbf{X} - \boldsymbol{\mu}$.
  \item Compute SVD: $\mathbf{X}_c = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^\top$; columns of $\mathbf{V}$ are the principal components (eigenvectors of the covariance matrix $\mathbf{X}_c^\top\mathbf{X}_c$).
  \item Projection: $\mathbf{Z} = \mathbf{X}_c\mathbf{V}_k$ maps into $\mathbb{R}^k$.
  \item Often used as an unsupervised preprocessing step to reduce dimensionality and mitigate the curse of dimensionality.
\end{itemize}

\textbf{Clustering} partitions data into distinct groups:
\begin{itemize}[nosep]
  \item \textbf{$k$-means}: Minimizes within-cluster variance $\sum_{i=1}^n \sum_{k=1}^K \mathbb{1}[z_i = k] \|\mathbf{x}^{(i)} - \boldsymbol{\mu}_k\|_2^2$. Alternates between assigning points to the nearest centroid and recomputing centroids (Lloyd's algorithm). Highly sensitive to initialization; use $k$-means++.
  \item \textbf{DBSCAN}: Density-based, groups points closely packed together, robust to noise/outliers, automatically determines $K$.
\end{itemize}

\textbf{Ensemble methods} combine multiple base models to improve generalization:
\begin{itemize}[nosep]
  \item \textbf{Bagging} (Bootstrap Aggregating): Train independent high-variance models (e.g., deep decision trees) on bootstrap samples and average them. It significantly reduces \textit{variance} without increasing \textit{bias}. \textbf{Random Forest} improves this by also using random feature subsets at each split to de-correlate trees.
  \item \textbf{Boosting}: Sequentially train high-bias models (e.g., shallow trees/stumps), where each new model corrects the errors of the ensemble so far. It primarily reduces \textit{bias}. \textbf{Gradient Boosting Machines} (XGBoost, LightGBM) fit new trees to the negative gradient of the loss function.
\end{itemize}

For review, be able to: compute information gain for a split; derive the SVM dual; explain the kernel trick and Representer Theorem; perform PCA via SVD; run $k$-means; and analytically compare how bagging and boosting affect bias and variance.

\paragraph{Section summary}
Classical ML offers a mathematically grounded toolkit: decision trees (interpretable non-linear splits), SVMs (maximum-margin with kernels for infinite-dimensional feature spaces), PCA (unsupervised dimensionality reduction), and clustering. Ensembles (Random Forests, Gradient Boosting) dominate tabular data by systematically trading off bias and variance.

\section{Statistical Learning: Estimation, Bayes, Causality, and Uncertainty}
\subsection{Core ideas}

\textbf{Statistical estimation}: we observe data $\mathcal{D} = \{(x^{(i)}, y^{(i)})\}_{i=1}^n$ i.i.d.\ from $P(X,Y)$. We estimate parameters $\boldsymbol{\theta}$ of a model $p(y|\mathbf{x};\boldsymbol{\theta})$.

\textbf{Maximum likelihood estimation (MLE)}:
\[
\hat{\boldsymbol{\theta}}_{\text{MLE}} = \operatorname*{argmax}_{\boldsymbol{\theta}} \sum_{i=1}^n \log p(y^{(i)}|\mathbf{x}^{(i)}; \boldsymbol{\theta}).
\]
MLE is consistent (converges to true $\boldsymbol{\theta}^*$ as $n\to\infty$) and asymptotically efficient (achieves Cram\'{e}r--Rao lower bound).

\textbf{Maximum a posteriori (MAP)} adds a prior $p(\boldsymbol{\theta})$:
\[
\hat{\boldsymbol{\theta}}_{\text{MAP}} = \operatorname*{argmax}_{\boldsymbol{\theta}} \sum_{i=1}^n \log p(y^{(i)}|\mathbf{x}^{(i)}; \boldsymbol{\theta}) + \log p(\boldsymbol{\theta}).
\]
$L^2$ regularization on weights corresponds to a Gaussian prior; $L^1$ corresponds to a Laplace prior.

\textbf{Bayesian inference} computes the full posterior:
\[
p(\boldsymbol{\theta}|\mathcal{D}) = \frac{p(\mathcal{D}|\boldsymbol{\theta})p(\boldsymbol{\theta})}{p(\mathcal{D})} \propto p(\mathcal{D}|\boldsymbol{\theta})p(\boldsymbol{\theta}).
\]
Prediction: $p(y^*|\mathbf{x}^*,\mathcal{D}) = \int p(y^*|\mathbf{x}^*,\boldsymbol{\theta}) p(\boldsymbol{\theta}|\mathcal{D}) d\boldsymbol{\theta}$ (posterior predictive). For most models the integral is intractable; approximation via MCMC (sampling) or variational inference (optimization).

\textbf{Causality} goes beyond correlation. Key concepts:
\begin{itemize}[nosep]
  \item Structural causal models (SCMs): $X_i = f_i(\mathbf{PA}_i, U_i)$ where $\mathbf{PA}_i$ are parents of $X_i$ and $U_i$ are exogenous noise.
  \item Interventions $do(X_j = x)$ vs.\ conditioning $P(Y|X_j=x)$. The do-operator removes incoming edges to $X_j$.
  \item Confounders: $Z$ affects both $X$ and $Y$; conditioning on $Z$ blocks the backdoor path.
  \item Randomized controlled trials (RCT) are the gold standard for causal inference.
  \item Methods: propensity score matching, instrumental variables, difference-in-differences.
\end{itemize}

\textbf{Uncertainty quantification}:
\begin{itemize}[nosep]
  \item Aleatoric uncertainty: irreducible noise in data (e.g., measurement error). Cannot be reduced with more data.
  \item Epistemic uncertainty: uncertainty about model parameters due to limited data. Decreases with more data.
  \item Calibration: a model is calibrated if among predictions with confidence $p$, the true fraction correct is $p$.
\end{itemize}

For review, be able to: derive MLE for Gaussian and Bernoulli; explain MAP as regularized MLE; describe Bayesian vs.\ frequentist approaches; define confounding; distinguish aleatoric and epistemic uncertainty.

\paragraph{Section summary}
Statistical learning provides the probabilistic foundation: MLE for point estimates, Bayesian inference for full uncertainty, and causal reasoning for interventional questions. Understanding estimation properties (bias, consistency, efficiency) is essential for diagnosing models.

\section{Probabilistic ML: Generative Models, Latent Variables, and Graphical Models}
\subsection{Core ideas}

\textbf{Generative vs.\ discriminative models}:
\begin{itemize}[nosep]
  \item Discriminative: $p(y|\mathbf{x})$, e.g., logistic regression, neural networks.
  \item Generative: $p(\mathbf{x}, y) = p(\mathbf{x}|y)p(y)$, e.g., naive Bayes, GMMs.
  \item Generative models can produce new samples $\mathbf{x} \sim p(\mathbf{x})$ and handle missing data naturally.
  \item Naive Bayes assumes conditional independence: $p(\mathbf{x}|y) = \prod_{j=1}^d p(x_j|y)$. Despite the strong assumption, it works well for text classification.
\end{itemize}

\textbf{Gaussian mixture models (GMMs)}:
\[
p(\mathbf{x}) = \sum_{k=1}^K \pi_k\,\mathcal{N}(\mathbf{x}|\boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k), \quad \sum_{k=1}^K \pi_k = 1,\ \pi_k \ge 0.
\]
Latent variable $z_i \in \{1,\dots,K\}$ indicates which component generated $\mathbf{x}^{(i)}$. The log-likelihood is non-convex; use expectation--maximization (EM):
\begin{enumerate}[nosep]
  \item E-step: compute responsibilities $\gamma_{ik} = P(z_i=k|\mathbf{x}^{(i)}, \boldsymbol{\theta}^{(t)})$.
  \item M-step: update $\pi_k = \frac{1}{n}\sum_i \gamma_{ik}$, $\boldsymbol{\mu}_k = \frac{\sum_i \gamma_{ik}\mathbf{x}^{(i)}}{\sum_i \gamma_{ik}}$, $\boldsymbol{\Sigma}_k = \frac{\sum_i \gamma_{ik}(\mathbf{x}^{(i)}-\boldsymbol{\mu}_k)(\mathbf{x}^{(i)}-\boldsymbol{\mu}_k)^\top}{\sum_i \gamma_{ik}}$.
\end{enumerate}
EM monotonically increases the marginal log-likelihood.

\textbf{Probabilistic graphical models} represent conditional independence:
\begin{itemize}[nosep]
  \item Bayesian networks (DAG): $p(\mathbf{x}) = \prod_{j=1}^d p(x_j|\mathbf{pa}(x_j))$. Factorization according to graph structure.
  \item Markov random fields (undirected): $p(\mathbf{x}) = \frac{1}{Z}\prod_{C \in \mathcal{C}} \psi_C(\mathbf{x}_C)$ where $Z$ is the partition function.
  \item Hidden Markov models (HMMs): latent states $z_t$ evolve as a Markov chain $p(z_t|z_{t-1})$, observations $x_t$ depend on $z_t$. Forward-backward algorithm computes $p(z_t|\mathbf{x}_{1:T})$; Viterbi finds the most likely sequence.
\end{itemize}

\textbf{Latent variable models (LVMs)} assume the observed data is generated from unobserved latent variables:
\begin{itemize}[nosep]
  \item Factor analysis, probabilistic PCA ($\mathbf{x} = \mathbf{W}\mathbf{z} + \boldsymbol{\epsilon}$, $\mathbf{z} \sim \mathcal{N}(0,\mathbf{I})$).
  \item Topic models (LDA): documents are mixtures of topics, topics are distributions over words.
\end{itemize}

\textbf{Variational inference}: approximate intractable posterior $p(\mathbf{z}|\mathbf{x})$ with a simpler $q(\mathbf{z})$ by minimizing KL divergence:
\[
\text{KL}(q\|p) = \mathbb{E}_q[\log q(\mathbf{z}) - \log p(\mathbf{z}|\mathbf{x})] = -\text{ELBO} + \log p(\mathbf{x}).
\]
Maximizing the evidence lower bound (ELBO) $\mathcal{L} = \mathbb{E}_q[\log p(\mathbf{x},\mathbf{z}) - \log q(\mathbf{z})]$ is equivalent to minimizing KL.

For review, be able to: derive EM for GMMs; explain the difference between generative and discriminative models; factorize a joint distribution from a DAG; derive the ELBO; and implement the forward-backward algorithm.

\paragraph{Section summary}
Probabilistic ML models the full data distribution. GMMs cluster with soft assignments via EM. Graphical models encode structure and enable efficient inference. Variational inference approximates intractable posteriors, forming the foundation for modern deep generative models.

\section{Fundamentals of Deep Learning: MLPs, Backpropagation, and Optimization}
\subsection{Core ideas}

\textbf{Multilayer perceptrons (MLPs)} (feedforward neural networks) stack affine transformations with elementwise nonlinearities to learn hierarchical representations. A network of depth $L$ computes:
\[
\mathbf{h}_1 = \sigma_1(\mathbf{W}_1\mathbf{x} + \mathbf{b}_1), \quad \dots \quad \mathbf{h}_{L-1} = \sigma_{L-1}(\mathbf{W}_{L-1}\mathbf{h}_{L-2} + \mathbf{b}_{L-1}), \quad \hat{\mathbf{y}} = \mathbf{W}_L\mathbf{h}_{L-1} + \mathbf{b}_L.
\]
Hidden units act as learned feature extractors, circumventing the need for manual feature engineering.

\textbf{Activation functions} inject essential nonlinearity (without them, the network collapses to a single affine transform):
\begin{itemize}[nosep]
  \item \textbf{ReLU} (Rectified Linear Unit): $\sigma(z) = \max(0, z)$. Piecewise linear, cheap to compute, mitigates vanishing gradients. Default choice for hidden layers.
  \item \textbf{Sigmoid}: $\sigma(z) = 1/(1+e^{-z})$. Maps to $(0,1)$. Prone to vanishing gradients in saturated regions; mostly used for binary classification outputs.
  \item \textbf{Tanh}: $\tanh(z) = (e^z - e^{-z})/(e^z + e^{-z})$. Maps to $(-1,1)$. Zero-centered, generally preferred over sigmoid for hidden units.
  \item \textbf{Leaky ReLU} / \textbf{GELU}: Address the "dying ReLU" problem and provide smooth gradients, common in modern architectures like Transformers.
\end{itemize}

\textbf{Backpropagation} efficiently computes gradients of the loss $\mathcal{L}$ with respect to all parameters using the chain rule. It is a specific application of reverse-mode automatic differentiation:
\begin{enumerate}[nosep]
  \item \textbf{Forward pass}: Compute and cache hidden activations $\mathbf{h}_\ell = f_\ell(\mathbf{h}_{\ell-1})$ for $\ell=1,\dots,L$, and the loss $\mathcal{L}$.
  \item \textbf{Backward pass}: Propagate the error signal backwards. Compute the gradient w.r.t.\ activations: $\frac{\partial\mathcal{L}}{\partial\mathbf{h}_\ell} = \frac{\partial\mathcal{L}}{\partial\mathbf{h}_{\ell+1}} \frac{\partial\mathbf{h}_{\ell+1}}{\partial\mathbf{h}_\ell}$.
  \item \textbf{Parameter gradients}: $\frac{\partial\mathcal{L}}{\partial\mathbf{W}_\ell} = \frac{\partial\mathcal{L}}{\partial\mathbf{h}_\ell} \frac{\partial\mathbf{h}_\ell}{\partial\mathbf{W}_\ell}$.
\end{enumerate}

\textbf{Optimization algorithms} train these highly non-convex objectives:
\begin{itemize}[nosep]
  \item \textbf{SGD (Stochastic Gradient Descent)}: $\mathbf{w}_{t+1} = \mathbf{w}_t - \eta_t \nabla_{\mathbf{w}} \mathcal{L}_B(\mathbf{w}_t)$, using a minibatch $B$ to estimate the true gradient.
  \item \textbf{Momentum}: Accumulates an exponentially decaying moving average of past gradients to dampen oscillations and accelerate convergence across flat regions.
  \item \textbf{Adam}: Adaptive learning rates per parameter, using running averages of the first moment (mean) and second moment (uncentered variance) of the gradients:
    \[
    m_t = \beta_1 m_{t-1} + (1-\beta_1)g_t, \quad v_t = \beta_2 v_{t-1} + (1-\beta_2)g_t^2, \quad \theta_{t+1} = \theta_t - \eta \frac{\hat{m}_t}{\sqrt{\hat{v}_t} + \epsilon},
    \]
    where $\hat{m}_t$ and $\hat{v}_t$ are bias-corrected estimates.
\end{itemize}

\textbf{Numerical considerations \& Regularization}:
\begin{itemize}[nosep]
  \item \textbf{Vanishing/exploding gradients}: Deep networks repeatedly multiply weight matrices, causing gradients to vanish or explode. Handled by careful initialization (Xavier/Glorot, He) and skip connections.
  \item \textbf{Batch Normalization}: Standardizes activations within a minibatch to zero mean and unit variance, smoothing the optimization landscape and allowing higher learning rates.
  \item \textbf{Dropout}: Randomly zeroes out neurons during training with probability $p$. Acts as a regularizer by preventing feature co-adaptation, implicitly training an ensemble.
\end{itemize}

\textbf{Universal Approximation Theorem}: A feedforward network with at least one hidden layer of sufficient width and a non-polynomial activation function can approximate any continuous function on a compact subset of $\mathbb{R}^n$ to arbitrary precision. However, it does not guarantee that the learning algorithm can find those weights, nor that the network will generalize well.

For review, be able to: derive backpropagation for a 2-layer MLP; explain why nonlinearities are necessary; implement SGD with momentum; diagnose vanishing gradients; and describe batch normalization.

\paragraph{Section summary}
Deep learning stacks differentiable nonlinear layers to learn representations. Backpropagation leverages the chain rule for exact gradient computation. Due to non-convexity and high dimensionality, specialized optimizers (Adam, SGD+Momentum), careful initialization, and techniques like Batch Normalization and Dropout are vital for successful training.

\section{Modern Deep Learning: CNNs, RNNs, Attention, and Transformers}
\subsection{Core ideas}

\textbf{Convolutional Neural Networks (CNNs)} exploit the inherent spatial structure of data (e.g., images) through localized filter operations.
\begin{itemize}[nosep]
  \item \textbf{Definition (2D Convolution):} Given an image $I$ and a filter (kernel) $K$, the discrete convolution is defined as $(I * K)(i,j) = \sum_{m}\sum_{n} I(i+m, j+n) K(m,n)$. This operation shares weights across all spatial locations, a property known as \textit{weight tying}.
  \item \textbf{Key Properties:} 
    \begin{itemize}[nosep]
      \item \textit{Translation Equivariance:} Shifting the input shifts the output by the same amount, i.e., $f(g(x)) = g(f(x))$ where $g$ is a translation operator.
      \item \textit{Local Connectivity:} Each neuron only connects to a small local region of the input, defining its \textit{receptive field}.
    \end{itemize}
  \item \textbf{Pooling:} Operations like max or average pooling aggregate local features, providing spatial downsampling and local \textit{translation invariance} (robustness to small shifts).
  \item \textbf{Canonical Architectures:} 
    \begin{itemize}[nosep]
      \item \textit{AlexNet:} Pioneered deep CNNs using ReLU activations, dropout, and extensive data augmentation.
      \item \textit{VGG:} Standardized architecture using deep stacks of small $3 \times 3$ convolutions.
      \item \textit{ResNet:} Introduced residual (skip) connections $y = \mathcal{F}(x) + x$ to mitigate vanishing gradients in extremely deep networks.
    \end{itemize}
\end{itemize}

\textbf{Recurrent Neural Networks (RNNs)} are designed to model sequential data by maintaining a hidden state across time steps:
\[
\mathbf{h}_t = \sigma(\mathbf{W}_{hh}\mathbf{h}_{t-1} + \mathbf{W}_{hx}\mathbf{x}_t + \mathbf{b}_h), \quad
\hat{\mathbf{y}}_t = \mathbf{W}_{hy}\mathbf{h}_t + \mathbf{b}_y.
\]
\begin{itemize}[nosep]
  \item \textbf{Backpropagation Through Time (BPTT):} Unrolls the RNN computation graph over time to compute gradients. A canonical failure mode of standard RNNs is the \textit{vanishing/exploding gradient problem} over long sequences due to repeated multiplication of the weight matrix $\mathbf{W}_{hh}$.
\end{itemize}

\textbf{Gated RNNs} address long-range dependencies by regulating information flow:
\begin{itemize}[nosep]
  \item \textbf{Long Short-Term Memory (LSTM):} Introduces a cell state $\mathbf{c}_t$ regulated by forget ($\mathbf{f}_t$), input ($\mathbf{i}_t$), and output ($\mathbf{o}_t$) gates:
    \[
    \mathbf{f}_t = \sigma(\mathbf{W}_f[\mathbf{h}_{t-1},\mathbf{x}_t] + \mathbf{b}_f),\quad
    \mathbf{i}_t = \sigma(\mathbf{W}_i[\mathbf{h}_{t-1},\mathbf{x}_t] + \mathbf{b}_i),\quad
    \tilde{\mathbf{c}}_t = \tanh(\mathbf{W}_c[\mathbf{h}_{t-1},\mathbf{x}_t] + \mathbf{b}_c),
    \]
    \[
    \mathbf{c}_t = \mathbf{f}_t \odot \mathbf{c}_{t-1} + \mathbf{i}_t \odot \tilde{\mathbf{c}}_t,\quad
    \mathbf{o}_t = \sigma(\mathbf{W}_o[\mathbf{h}_{t-1},\mathbf{x}_t] + \mathbf{b}_o),\quad
    \mathbf{h}_t = \mathbf{o}_t \odot \tanh(\mathbf{c}_t).
    \]
  \item \textbf{Gated Recurrent Unit (GRU):} A simplified gated architecture merging the forget and input gates into a single update gate.
\end{itemize}

\textbf{Attention Mechanisms} overcome the bottleneck of compressing entire sequences into a fixed-length vector by allowing models to dynamically weigh the importance of all input elements.
\begin{itemize}[nosep]
  \item \textbf{Definition (Scaled Dot-Product Attention):} For queries $\mathbf{Q}$, keys $\mathbf{K}$, and values $\mathbf{V}$, attention is computed as:
    \[
    \text{Attention}(\mathbf{Q},\mathbf{K},\mathbf{V}) = \text{softmax}\!\left(\frac{\mathbf{Q}\mathbf{K}^\top}{\sqrt{d_k}}\right)\mathbf{V}.
    \]
    Scaling by $1/\sqrt{d_k}$ prevents the dot products from growing excessively large, which would push the softmax function into regions with near-zero gradients.
\end{itemize}

\textbf{Transformers} (Vaswani et al., 2017) rely entirely on attention, dispensing with recurrence and convolutions.
\begin{itemize}[nosep]
  \item \textbf{Multi-Head Attention:} Projects $\mathbf{Q}$, $\mathbf{K}$, and $\mathbf{V}$ into $h$ different representation subspaces (heads) in parallel. The independent attention outputs are then concatenated and linearly transformed.
  \item \textbf{Positional Encoding:} Since attention is permutation-invariant, positional encodings (e.g., fixed sinusoidal functions or learned embeddings) are added to input embeddings to inject sequence order information.
  \item \textbf{Architecture Components:} Comprises layer normalization, residual connections, and position-wise feedforward networks. The encoder uses full self-attention, whereas the decoder uses \textit{masked} self-attention to prevent attending to future tokens (preserving the autoregressive property).
  \item \textbf{Complexity:} Standard attention has $O(n^2)$ time and space complexity with respect to sequence length $n$.
\end{itemize}

\textbf{Large-Scale Pretraining} leverages massive unannotated datasets to learn general representations:
\begin{itemize}[nosep]
  \item \textit{BERT:} Uses a bidirectional encoder pretrained via Masked Language Modeling (MLM).
  \item \textit{GPT:} Employs a causal, autoregressive decoder architecture.
  \item \textbf{Scaling Laws:} Empirical observations that model performance scales power-law predictably with parameter count, dataset size, and training compute.
\end{itemize}

For review, be able to: explain the receptive field of a CNN; derive gradient flow in an RNN via BPTT; implement scaled dot-product attention; draw the standard Transformer encoder/decoder blocks; and describe masked language modeling.

\paragraph{Section summary}
Modern deep learning is built upon specialized architectures for data modalities: CNNs utilize local connectivity and weight tying for spatial data; RNNs and LSTMs maintain hidden states for sequential data; and Transformers leverage self-attention for parallelizable, long-range sequence modeling. The paradigm has shifted strongly toward large-scale, self-supervised pretraining followed by task-specific fine-tuning.

\section{Generative AI: VAEs, GANs, Diffusion, and Self-Supervised Learning}
\subsection{Core ideas}

\textbf{Variational Autoencoders (VAEs)} combine deep learning with variational inference to learn continuous, structured latent spaces:
\begin{itemize}[nosep]
  \item \textbf{Definition:} An architecture consisting of a probabilistic \textit{encoder} $q_\phi(\mathbf{z}|\mathbf{x})$ mapping data to a latent distribution (typically Gaussian $\mathcal{N}(\boldsymbol{\mu}_\phi(\mathbf{x}), \boldsymbol{\sigma}_\phi^2(\mathbf{x})\mathbf{I})$), and a \textit{decoder} $p_\theta(\mathbf{x}|\mathbf{z})$ reconstructing the data.
  \item \textbf{ELBO Objective:} Because exact marginal likelihood is intractable, VAEs maximize the Evidence Lower Bound (ELBO):
    \[
    \log p(\mathbf{x}) \ge \mathcal{L}(\theta,\phi) = \mathbb{E}_{q_\phi(\mathbf{z}|\mathbf{x})}[\log p_\theta(\mathbf{x}|\mathbf{z})] - \text{KL}(q_\phi(\mathbf{z}|\mathbf{x}) \| p(\mathbf{z})).
    \]
    The first term minimizes reconstruction error, while the second acts as a regularizer, pulling the approximate posterior toward the prior $p(\mathbf{z}) = \mathcal{N}(0,\mathbf{I})$.
  \item \textbf{Reparameterization Trick:} To allow gradients to backpropagate through the stochastic sampling step, $\mathbf{z}$ is reparameterized: sample $\boldsymbol{\epsilon} \sim \mathcal{N}(0,\mathbf{I})$, then compute $\mathbf{z} = \boldsymbol{\mu}_\phi(\mathbf{x}) + \boldsymbol{\sigma}_\phi(\mathbf{x}) \odot \boldsymbol{\epsilon}$.
\end{itemize}

\textbf{Generative Adversarial Networks (GANs)} frame generation as a two-player, zero-sum game:
\begin{itemize}[nosep]
  \item \textbf{Definition:} A \textit{generator} network $G_\theta$ maps noise $\mathbf{z} \sim p(\mathbf{z})$ to fake data $\tilde{\mathbf{x}}$, while a \textit{discriminator} $D_\phi$ predicts whether a sample is real ($\mathbf{x}$) or fake ($\tilde{\mathbf{x}}$).
  \item \textbf{Minimax Objective:} 
    \[
    \min_\theta \max_\phi \mathbb{E}_{\mathbf{x} \sim p_{\text{data}}}[\log D_\phi(\mathbf{x})] + \mathbb{E}_{\mathbf{z} \sim p(\mathbf{z})}[\log(1 - D_\phi(G_\theta(\mathbf{z})))].
    \]
  \item \textbf{Training Pathologies:} GANs are notoriously difficult to train, frequently suffering from \textit{mode collapse} (the generator produces only a limited variety of outputs, ignoring parts of the data distribution) and vanishing gradients.
  \item \textbf{Improvements:} Wasserstein GAN (WGAN) addresses instability by minimizing the Earth Mover's distance using a 1-Lipschitz discriminator constrained via gradient penalty. StyleGAN introduces mapping networks and adaptive instance normalization for high-fidelity synthesis.
\end{itemize}

\textbf{Diffusion Models} (and Score-Based Generative Models) generate data by learning to reverse a gradual noising process:
\begin{itemize}[nosep]
  \item \textbf{Forward Process (Diffusion):} A Markov chain gradually corrupts data $\mathbf{x}_0$ by adding Gaussian noise over $T$ steps: $q(\mathbf{x}_t|\mathbf{x}_{t-1}) = \mathcal{N}(\sqrt{1-\beta_t}\mathbf{x}_{t-1}, \beta_t\mathbf{I})$.
  \item \textbf{Reverse Process (Denoising):} A neural network learns the reverse transitions $p_\theta(\mathbf{x}_{t-1}|\mathbf{x}_t) = \mathcal{N}(\boldsymbol{\mu}_\theta(\mathbf{x}_t,t), \boldsymbol{\Sigma}_\theta(\mathbf{x}_t,t))$ to synthesize data from pure noise $\mathbf{x}_T \sim \mathcal{N}(0,\mathbf{I})$.
  \item \textbf{Training Objective:} DDPM minimizes a reweighted variational bound, effectively training a U-Net to predict the injected noise $\boldsymbol{\epsilon}_\theta(\mathbf{x}_t, t)$:
    \[
    \mathcal{L} = \mathbb{E}_{t,\mathbf{x}_0,\boldsymbol{\epsilon}}[\|\boldsymbol{\epsilon} - \boldsymbol{\epsilon}_\theta(\sqrt{\bar{\alpha}_t}\mathbf{x}_0 + \sqrt{1-\bar{\alpha}_t}\boldsymbol{\epsilon}, t)\|^2].
    \]
  \item \textbf{Score Matching Connection:} The noise prediction objective is mathematically equivalent to \textit{score matching}, learning the gradient of the log data density: $\nabla_{\mathbf{x}_t} \log p(\mathbf{x}_t) \approx -\boldsymbol{\epsilon}_\theta(\mathbf{x}_t, t)/\sqrt{1-\bar{\alpha}_t}$. \textit{Latent Diffusion Models} (e.g., Stable Diffusion) perform this process efficiently inside a frozen VAE latent space.
\end{itemize}

\textbf{Self-Supervised Learning (SSL)} extracts powerful representations from unannotated data by inventing pretext tasks:
\begin{itemize}[nosep]
  \item \textbf{Contrastive Learning:} Pulls representations of positive pairs (e.g., augmented views of the same image) closer while pushing negative pairs apart. SimCLR uses the \textit{InfoNCE loss}:
    \[
    \mathcal{L} = -\log \frac{\exp(\text{sim}(\mathbf{z}_i,\mathbf{z}_j)/\tau)}{\sum_{k\neq i} \exp(\text{sim}(\mathbf{z}_i,\mathbf{z}_k)/\tau)},
    \]
    where $\tau$ is a temperature hyperparameter controlling the penalty strength on hard negatives.
  \item \textbf{Non-contrastive Methods:} Architectures like BYOL and SimSiam use momentum encoders and stop-gradient operations to prevent representation collapse without requiring negative pairs.
  \item \textbf{Masked Autoencoders:} Models like BERT (text) and MAE (vision) mask patches of input data and train a network to reconstruct the missing content, enforcing deep contextual understanding.
\end{itemize}

For review, be able to: mathematically derive the VAE ELBO from Jensen's inequality; explain the necessity of the reparameterization trick; describe the GAN minimax game and optimal discriminator; outline the diffusion forward/reverse Markov chain; and define the InfoNCE contrastive loss.

\paragraph{Section summary}
Generative AI models data distributions. VAEs provide stable training and smooth latent spaces via variational inference. GANs employ an adversarial minimax game to achieve high-fidelity generation. Diffusion models use iterative denoising equivalent to score matching, currently yielding state-of-the-art visual quality. Self-supervised learning (contrastive or masked) converts raw data into informative latent structures, serving as the backbone for modern foundation models.

\section{Reinforcement Learning: MDPs, TD Learning, Q-Learning, and Policy Gradients}
\subsection{Core ideas}

\textbf{Markov Decision Process (MDP)} formalizes sequential decision-making under uncertainty:
\begin{itemize}[nosep]
  \item \textbf{Definition:} A tuple $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$ where $\mathcal{S}$ is the state space, $\mathcal{A}$ is the action space, $P(\mathbf{s}'|\mathbf{s}, a)$ is the transition probability, $R(\mathbf{s}, a, \mathbf{s}')$ is the reward function, and $\gamma \in [0,1]$ is the discount factor.
  \item \textbf{Markov Property:} The future depends only on the present state, not on the sequence of events that preceded it: $P(\mathbf{s}_{t+1}|\mathbf{s}_t, \mathbf{a}_t, \ldots, \mathbf{s}_0, \mathbf{a}_0) = P(\mathbf{s}_{t+1}|\mathbf{s}_t, \mathbf{a}_t)$.
  \item \textbf{Return:} The cumulative discounted reward from time $t$: $G_t = \sum_{k=0}^\infty \gamma^k R_{t+k+1}$.
  \item \textbf{Policy $\pi(a|\mathbf{s})$:} A mapping from states to a probability distribution over actions.
  \item \textbf{Value Functions:} 
    \begin{itemize}[nosep]
      \item State-value: $V^\pi(\mathbf{s}) = \mathbb{E}_\pi[G_t | \mathbf{S}_t = \mathbf{s}]$.
      \item Action-value: $Q^\pi(\mathbf{s}, a) = \mathbb{E}_\pi[G_t | \mathbf{S}_t = \mathbf{s}, A_t = a]$.
    \end{itemize}
  \item \textbf{Bellman Equations:} Recursive relationships linking the value of a state to the values of its successors:
    \[
    V^\pi(\mathbf{s}) = \sum_a \pi(a|\mathbf{s}) \sum_{\mathbf{s}'} P(\mathbf{s}'|\mathbf{s}, a)[R(\mathbf{s},a,\mathbf{s}') + \gamma V^\pi(\mathbf{s}')].
    \]
  \item \textbf{Bellman Optimality:} The optimal policy $\pi^*$ satisfies $V^*(\mathbf{s}) = \max_a Q^*(\mathbf{s}, a)$.
\end{itemize}

\textbf{Dynamic Programming} solves known MDPs exactly:
\begin{itemize}[nosep]
  \item \textit{Policy Iteration:} Alternate between evaluating $V^\pi$ and greedily improving $\pi'(a|\mathbf{s}) = \mathbb{1}[a = \arg\max_a Q^\pi(\mathbf{s},a)]$.
  \item \textit{Value Iteration:} Iteratively apply the Bellman optimality operator until convergence.
\end{itemize}

\textbf{Model-Free RL} learns optimal policies from environmental interaction without known $P$ or $R$.

\textbf{Temporal Difference (TD) Learning} blends Monte Carlo methods and dynamic programming:
\begin{itemize}[nosep]
  \item \textbf{Mechanism:} Bootstraps updates using current value estimates instead of waiting for episode completion.
  \item \textbf{TD(0) Update:} $V(\mathbf{s}_t) \leftarrow V(\mathbf{s}_t) + \alpha\delta_t$, where $\delta_t = \underbrace{r_{t+1} + \gamma V(\mathbf{s}_{t+1})}_{\text{TD Target}} - V(\mathbf{s}_t)$ is the \textit{TD Error}.
\end{itemize}

\textbf{Q-Learning and SARSA} are canonical TD control algorithms:
\begin{itemize}[nosep]
  \item \textbf{SARSA (On-Policy):} Updates $Q$ using the action actually taken by the behavior policy:
    \[
    Q(\mathbf{s}_t, a_t) \leftarrow Q(\mathbf{s}_t, a_t) + \alpha[r_{t+1} + \gamma Q(\mathbf{s}_{t+1}, a_{t+1}) - Q(\mathbf{s}_t, a_t)].
    \]
  \item \textbf{Q-Learning (Off-Policy):} Updates $Q$ using the maximum possible value of the next state, uncoupling learning from the behavior policy:
    \[
    Q(\mathbf{s}_t, a_t) \leftarrow Q(\mathbf{s}_t, a_t) + \alpha[r_{t+1} + \gamma \max_{a'} Q(\mathbf{s}_{t+1}, a') - Q(\mathbf{s}_t, a_t)].
    \]
  \item \textbf{Deep Q-Network (DQN):} Stabilizes Q-learning with neural networks via \textit{experience replay} (breaking temporal correlations) and \textit{target networks} (providing fixed bootstrap targets).
\end{itemize}

\textbf{Policy Gradient Methods} directly parameterize and optimize the policy $\pi_\theta$:
\begin{itemize}[nosep]
  \item \textbf{Policy Gradient Theorem:} Provides an analytic gradient for the expected return:
    \[
    \nabla_\theta J(\theta) = \mathbb{E}_{\pi_\theta}[ \nabla_\theta \log \pi_\theta(a|\mathbf{s}) \cdot Q^{\pi_\theta}(\mathbf{s},a) ].
    \]
  \item \textbf{REINFORCE:} Uses sample returns $G_t$ as an unbiased (but high-variance) estimator of $Q$.
  \item \textbf{Actor-Critic:} Combines policy gradients (the \textit{actor}) with a learned value function (the \textit{critic}) serving as a baseline to reduce variance. Subtracting the state-value yields the \textit{advantage} function $A(\mathbf{s},a) = Q(\mathbf{s},a) - V(\mathbf{s})$.
  \item \textbf{PPO (Proximal Policy Optimization):} Clips the policy ratio $r_t(\theta) = \frac{\pi_\theta(a|s)}{\pi_{\text{old}}(a|s)}$ to prevent destructively large policy updates.
\end{itemize}

\textbf{Exploration vs. Exploitation Tradeoff}: Algorithms must balance exploiting known rewards with exploring undiscovered states using strategies like $\epsilon$-greedy, Boltzmann exploration, or Upper Confidence Bound (UCB).

For review, be able to: define the Markov Property; mathematically state the Bellman Optimality Equation; prove why Q-learning is off-policy while SARSA is on-policy; derive the REINFORCE update rule; and explain how Actor-Critic reduces variance.

\paragraph{Section summary}
Reinforcement learning solves sequential decision-making governed by MDPs. Value-based methods (Q-Learning) learn optimal action-values off-policy. Policy gradient methods directly optimize a parameterized policy, overcoming limitations in continuous action spaces. Deep RL merges these frameworks with neural network function approximators (e.g., DQN, PPO), relying heavily on mechanisms like advantage estimation to stabilize learning.

\section{Practice and Ethics: MLOps, Fairness, Explainability, and Safety}
\subsection{Core ideas}

\textbf{Machine Learning Operations (MLOps)} standardizes the transition from experimental models to reliable, production-grade systems:
\begin{itemize}[nosep]
  \item \textbf{Data Pipeline \& Versioning:} Tracks dataset lineage (e.g., DVC), standardizes feature engineering via feature stores, and automates data quality monitoring.
  \item \textbf{Experiment Tracking \& CI/CD:} Systematically logs hyperparameters, metrics, and artifacts (e.g., MLflow). Implements continuous integration for data validation and continuous deployment for model updates.
  \item \textbf{Monitoring in Production:} Detects degradation over time, primarily distinguishing between \textit{data drift} (covariate shift: $P(\mathbf{x})$ changes while $P(y|\mathbf{x})$ remains constant) and \textit{concept drift} (the underlying relationship $P(y|\mathbf{x})$ changes, requiring retraining).
\end{itemize}

\textbf{Fairness in ML} systematically measures and mitigates discriminatory algorithmic behaviors:
\begin{itemize}[nosep]
  \item \textbf{Sources of Bias:} Encompasses historical bias, representation bias (under-sampling minority groups), and measurement bias (using flawed proxies for target variables).
  \item \textbf{Group Fairness Notions:} For a sensitive attribute $A \in \{a,b\}$, target $y$, and prediction $\hat{y}$:
    \begin{itemize}[nosep]
      \item \textit{Demographic Parity:} The model's positive prediction rate is independent of the sensitive attribute: $P(\hat{y}=1|A=a) = P(\hat{y}=1|A=b)$.
      \item \textit{Equalized Odds:} Both the True Positive Rate (TPR) and False Positive Rate (FPR) are identical across groups: $P(\hat{y}=1|y=c, A=a) = P(\hat{y}=1|y=c, A=b)$ for $c \in \{0,1\}$.
      \item \textit{Equal Opportunity:} Requires equality only for the TPR ($y=1$).
    \end{itemize}
  \item \textbf{Impossibility Theorem (Chouldechova et al.):} It is mathematically impossible to simultaneously satisfy demographic parity and equalized odds unless the base rates of the groups are exactly equal or the predictor is perfectly accurate.
  \item \textbf{Mitigation:} Involves pre-processing (reweighing data), in-processing (adversarial debiasing, constrained optimization), or post-processing (group-specific thresholding).
\end{itemize}

\textbf{Explainability and Interpretability} open the "black box" of complex models:
\begin{itemize}[nosep]
  \item \textbf{Intrinsic Interpretability:} Using transparent model classes natively (e.g., shallow decision trees, sparse linear models).
  \item \textbf{Post-Hoc Feature Attribution:} 
    \begin{itemize}[nosep]
      \item \textit{SHAP (SHapley Additive exPlanations):} Grounded in cooperative game theory, it uniquely satisfies desirable axioms (local accuracy, missingness, consistency) to assign a marginal contribution to each feature.
      \item \textit{LIME (Local Interpretable Model-agnostic Explanations):} Fits a simple, interpretable surrogate model (e.g., linear regression) in the local neighborhood of a specific prediction.
    \end{itemize}
  \item \textbf{Saliency \& Counterfactuals:} Saliency maps visualize gradients w.r.t.\ input pixels (in vision). Counterfactual explanations highlight the minimal perturbation required to alter the model's decision.
\end{itemize}

\textbf{AI Safety, Robustness, and Privacy} ensure models perform reliably under stress and adversarial conditions:
\begin{itemize}[nosep]
  \item \textbf{Adversarial Examples:} Microscopic, carefully crafted perturbations $\delta$ that drastically flip model predictions.
    \begin{itemize}[nosep]
      \item \textit{Fast Gradient Sign Method (FGSM):} A single-step attack: $\delta = \epsilon \cdot \text{sign}(\nabla_{\mathbf{x}} \mathcal{L}(\theta, \mathbf{x}, y))$.
      \item \textit{Projected Gradient Descent (PGD):} An iterative, multi-step application of FGSM representing a strong first-order attack.
    \end{itemize}
  \item \textbf{AI Alignment:} The challenge of ensuring systems pursue intended human goals without exhibiting \textit{reward hacking} (gaming the objective) or negative side-effects.
  \item \textbf{Differential Privacy (DP):} Provides a mathematical guarantee that the inclusion or removal of a single data point does not significantly alter the output distribution of a randomized algorithm $\mathcal{M}$.
    \begin{itemize}[nosep]
      \item \textit{Formal Definition ($\epsilon$-DP):} $P(\mathcal{M}(D) \in S) \le e^\epsilon P(\mathcal{M}(D') \in S)$ for all neighboring datasets $D, D'$ differing by one record, bounding the privacy loss by $\epsilon$.
    \end{itemize}
  \item \textbf{Federated Learning:} Enables decentralized model training without aggregating raw data centrally, often combined with secure multi-party computation.
\end{itemize}

For review, be able to: describe the MLOps lifecycle; rigorously define demographic parity and equalized odds; compute SHAP values for a minimal cooperative game; derive adversarial examples via FGSM; and explain the formal bounds of differential privacy.

\paragraph{Section summary}
The deployment of machine learning is constrained by practical and ethical requirements. MLOps ensures rigorous, automated pipelines for continuous monitoring and deployment. Mathematical fairness guarantees audit and mitigate algorithmic bias. Explainability methods like SHAP and LIME provide interpretability for black-box models. AI Safety enforces robustness against adversarial attacks and distribution shifts, while Differential Privacy and Federated Learning protect sensitive data.

\end{document}
