ST340 Fundamentals of Machine Learning

Comprehensive practice flashcards defining foundational concepts, models, architectures, and algorithms in ST340 Fundamentals of Machine Learning.

Supervised Learning

A machine learning setting where an algorithm is provided with labelled training data comprising input vectors and corresponding output labels, $(x^{(i)}, y^{(i)})_{i=1}^n$, with the objective of predicting the labels of unseen future inputs.

Unsupervised Learning

A machine learning setting where an algorithm is provided with unlabelled data, $(x^{(i)})_{i=1}^n$, with the objective of discovering underlying patterns, clustering data points, or performing dimension reduction without target labels.

Empirical Risk (Training Error)

The average loss evaluated across the training dataset $D_n$, defined for a prediction function $f$ and loss function $\ell$ as $\hat{R}(f) = \frac{1}{n} \sum_{i=1}^n \ell(f(x^{(i)}), y^{(i)})$.

Curse of Dimensionality

The phenomenon in high-dimensional spaces ($d \gg 1$) where geometric intuitions fail; data points become exceedingly sparse, nearest neighbours are located far away, and the vast majority of volume concentrates near the outer boundary.

Underfitting

A condition occurring when a model family is too simple (possessing too few parameters or high bias) to capture the true underlying data-generating relationship, leading to high training error and high generalization error.

Overfitting

A condition occurring when a model is excessively flexible (possessing too many parameters or high variance) and fits the random noise of the training data rather than the true signal, resulting in low training error but poor generalization to new data.

Mean Squared Error (MSE) Decomposition

The identity decomposing the expected squared error of an estimator $\hat{\theta}$ for a parameter $\theta$ into variance and squared bias: $\mathbb{E}[(\hat{\theta} - \theta)^2] = \text{Var}(\hat{\theta}) + \text{Bias}^2(\hat{\theta})$.

Bayesian Occam's Razor

The property of Bayesian marginal likelihood maximization wherein overly complex models are automatically penalized because diffuse prior distributions over large parameter spaces place less probability mass on the specific parameter regions that explain the observed data well.

Laplace's Approximation

A method approximating an intractable posterior distribution $p(\theta \mid D)$ by a multivariate normal distribution $N_d(\hat{\theta}, [H(\hat{\theta})]^{-1})$ centered at the posterior mode $\hat{\theta}$, where $H(\hat{\theta})$ is the Hessian matrix of second derivatives of the negative log posterior.

Bayesian Information Criterion (BIC)

A penalized model selection criterion defined for a dataset of size $n$ and a model with parameter dimension $d_m$ as $\ell_{\text{BIC}}(m) = -2 \log p_m(D \mid \hat{\theta}_{\text{MLE}}) + d_m \log(n)$, which selects the model with the minimum score.

Akaike Information Criterion (AIC)

A frequentist-derived model selection criterion defined as $\ell_{\text{AIC}}(m) = -2 \log p_m(D \mid \hat{\theta}_{\text{MLE}}) + 2d_m$, penalizing parameter dimension by a constant factor of $2$ rather than $\log(n)$.

Validation Data

A sequestered dataset, separate from both the training data and the final test data, used to estimate generalization error in order to compare and select among multiple candidate models.

Interpolation Threshold

The model capacity threshold at which a model possesses just enough parameters to fit the training data perfectly (achieving zero training error), which is frequently accompanied by a sharp spike in validation and test error.

Double Descent

The phenomenon observed in overparametrised machine learning models where, after peaking at the interpolation threshold, validation or generalization error decreases a second time as model capacity increases further into the overparametrised regime.

k-Fold Cross-Validation

A model selection procedure where the training set is partitioned into $k$ equally sized subsets, iteratively training on $k-1$ subsets and evaluating validation error on the remaining subset, then selecting the model that minimizes the average error across all $k$ folds.

Leave-One-Out Cross-Validation (LOOCV)

The special case of $k$-fold cross-validation where $k = n$, meaning each model is trained $n$ separate times on $n - 1$ data points and evaluated on the single held-out observation.

Expected Risk

The theoretical expected loss of a prediction function $f$ under the true joint probability distribution $p$ of inputs and outputs: $R(f) = \mathbb{E}[\ell(f(X), Y)]$.

Conditional Risk

The expected loss of predicting a label value $z$ given a specific fixed input location $x$, defined as $r(z \mid x) = \mathbb{E}[\ell(z, Y) \mid X = x]$.

Bayes Predictor

A theoretical prediction function $f^*: \mathcal{X} \to \mathcal{Y}$ that achieves the global minimum expected risk by choosing, for each input $x$, the value $f^*(x) \in \arg\min_{z \in \mathcal{Y}} r(z \mid x)$.

Bayes Risk

The minimal attainable expected risk under the true distribution $p$, defined as the risk $R(f^*)$ associated with a Bayes predictor.

Excess Risk

The difference between the expected risk of a given prediction function $f$ and the Bayes risk, expressed as $R(f) - R(f^*)$.

No Free Lunch Theorem

A theorem stating that for binary classification with $0$-$1$ loss over an infinite domain $\mathcal{X}$, for any training sample size $n$ and any learning algorithm $A$, the worst-case expected excess risk across all possible probability distributions is at least $1/2$.

Discriminant Function

A non-probabilistic mapping $f: \mathbb{R}^d \to \{1, \dots, K\}$ that partitions the input space into $K$ decision regions separated by decision boundaries.

One-Hot Encoding

A binary vector representation of a categorical class label $y \in \{1, \dots, K\}$ where the $k$th component is $1$ if the instance belongs to class $k$, and $0$ for all other coordinates.

Generative Model

A statistical learning model that fully specifies the joint probability distribution $p(X, Y)$ over both inputs and labels, enabling synthetic data points to be generated.

Discriminative Model

A statistical learning model that specifies only the conditional distribution of labels given the inputs, $p(Y \mid X)$, without modelling the distribution of the inputs $X$.

Standard Logistic Function

The sigmoidal mapping $\phi: \mathbb{R} \to [0, 1]$ defined by $\phi(a) = \frac{1}{1 + e^{-a}}$, used in logistic regression to map a real-valued linear predictor to a probability.

Cross-Entropy Loss (Negative Log-Likelihood Loss)

The loss function used in logistic regression and neural classification, defined for binary labels $y \in \{0, 1\}$ as $\ell(f(x), y) = -y \log \phi(x^\top w) - (1 - y) \log(1 - \phi(x^\top w))$.

Iteratively Reweighted Least Squares (IRLS)

A numerical optimization method applying the Newton-Raphson algorithm to solve the maximum likelihood estimation problem for logistic regression.

Softmax Function

The normalized exponential vector mapping $\varphi: \mathbb{R}^K \to \Delta_K$ defined coordinate-wise by $\varphi_k(a) = \frac{e^{a_k}}{\sum_{l=1}^K e^{a_l}}$, serving as a smooth, differentiable multi-class generalization of the logistic function.

Feature Mapping

A collection of basis functions $\phi: \mathcal{X} \to \mathcal{H}$ that projects data points from the original input space into a higher-dimensional feature space $\mathcal{H}$ to allow linear hyperplanes to form non-linear decision boundaries in $\mathcal{X}$.

k-Nearest Neighbours (kNN)

A non-parametric supervised learning algorithm that assigns the label of an input query point by taking a majority vote (for classification) or the arithmetic mean (for regression) of its $k$ closest data points according to a chosen distance metric.

Mahalanobis Distance

A distance metric defined by $d(x, z) = \sqrt{(x - z)^\top S^{-1} (x - z)}$, where $S$ is the empirical covariance matrix of the data, weighting individual axes according to their sample variability and correlations.

Maximum Margin Hyperplane (MMH)

The unique separating hyperplane $x \cdot \beta + \alpha = 0$ that classifies linearly separable binary data while maximizing the geometric margin, found by minimizing $\frac{1}{2}\|\beta\|^2$ subject to $y^{(i)}(x^{(i)} \cdot \beta + \alpha) \ge 1$.

Margin (SVM)

The total perpendicular distance separating the parallel boundary hyperplanes of opposite classes in a support vector machine, equal to $\frac{2}{\|\beta\|}$.

Support Vectors

The specific training observations in a support vector machine that lie directly on or inside the margin boundaries, satisfying $y^{(i)}(x^{(i)} \cdot \beta + \alpha) = 1 - \xi_i$, which uniquely define the optimal separating hyperplane.

Slack Variables (\xi_i)

Non-negative variables $\xi_i \ge 0$ introduced in soft-margin SVM formulations to permit misclassifications and margin violations, adding a linear penalty $C \sum_{i=1}^n \xi_i$ to the objective function.

Hinge Loss

The continuous piecewise-linear loss function defined as $\ell(z, y) = \max(0, 1 - yz)$, punishing predictions that fall on the incorrect side of the margin in support vector machines.

Kernel Function

A symmetric function $K: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ that directly evaluates the inner product between two points in a feature space, $K(x, x') = \langle \phi(x), \phi(x') \rangle$, without explicitly computing the feature mapping $\phi$.

Kernel Trick

The principle of replacing inner products of explicit feature vectors with evaluations of a kernel function $K(x, x')$, enabling algorithms to operate in high- or infinite-dimensional feature spaces with computational cost depending only on the number of data points.

Radial Basis Function (RBF) Kernel

A widely used kernel function defined as $K(x, x') = \exp(-\gamma \|x - x'\|^2)$ for $\gamma \ge 0$, which corresponds to an infinite-dimensional feature space.

Gaussian Process (GP)

A collection of random variables $(Y_x)_{x \in \mathcal{X}}$ such that any finite subcollection has a joint multivariate Gaussian distribution, fully determined by a mean function $m(x)$ and a covariance kernel $K(x, x')$.

Positive Semidefinite Kernel

A symmetric kernel function $K$ that produces a positive semidefinite Gram matrix $K_{ij} = K(x^{(i)}, x^{(j)})$ satisfying $\sum_{i=1}^n \sum_{j=1}^n c_i c_j K(x^{(i)}, x^{(j)}) \ge 0$ for all finite point collections and real coefficients.

Stationary Kernel

A covariance kernel that depends solely on the difference between two inputs, $K(x, x') = k(x - x')$, making its covariance properties translation-invariant across the input domain.

Isotropic Kernel

A stationary covariance kernel that depends solely on the Euclidean distance between two inputs, $K(x, x') = k(\|x - x'\|)$, ensuring invariance to both translation and rotation.

Matérn Kernel

A family of covariance kernels parameterized by length-scale $\ell$ and order $\nu$, where sample paths of the resulting Gaussian process are precisely $\lceil \nu \rceil - 1$ times differentiable.

Ornstein–Uhlenbeck Process

The Gaussian process defined on $\mathbb{R}$ by a Matérn kernel with $\nu = 1/2$, $K(x, x') = \exp(-\|x - x'\| / \ell)$, which exhibits the Markov property but produces trajectories that are nowhere differentiable.

Automatic Relevance Determination (ARD) Kernel

A generalization of the squared exponential kernel that assigns a distinct length-scale parameter $\ell_j$ to each input coordinate, allowing the relative predictive importance of each covariate to be inferred from data.

Kriging

A Bayesian non-parametric regression method that models an unknown real-valued function using a Gaussian process prior combined with a Gaussian observation likelihood, yielding an analytical Gaussian process posterior.

Perceptron

An early single-layer artificial neural network architecture proposed by Frank Rosenblatt in 1957 that uses fixed basis functions and a step threshold activation function to perform non-probabilistic binary classification.

Perceptron Criterion

The objective function minimized in perceptron training, defined as $\ell_n(w; D_n) = -\sum_{i \in \mathcal{M}(w)} w \cdot \phi(x^{(i)}) y^{(i)}$, where $\mathcal{M}(w)$ denotes the set of data points currently misclassified by weight vector $w$.

Universal Approximation Theorem for Continuous Functions

A theorem establishing that any continuous function on a compact subset of $\mathbb{R}^d$ can be approximated uniformly by a two-layer feedforward network equipped with linear output units and Heaviside or sigmoidal hidden activations.

Kolmogorov–Arnold Representation Theorem

A theorem stating that every continuous function on $[0, 1]^d$ can be written exactly as a finite superposition and composition of continuous univariate functions and addition operations: $f_k(x) = \sum_{j=1}^{2d+1} \Phi_k(\sum_{i=1}^d \lambda_i g_j(x_i))$.

Gradient Descent (GD)

A first-order optimization algorithm that iteratively updates a parameter vector in the direction of steepest loss decrease evaluated across the full training dataset: $w^{(t+1)} = w^{(t)} - \eta \nabla \ell_n(w^{(t)}; D_n)$.

Stochastic Gradient Descent (SGD)

An on-line variant of gradient descent that updates parameters using the gradient evaluated on a single data point (or mini-batch) at each iteration: $w^{(t+1)} = w^{(t)} - \eta \nabla \ell(w^{(t)}; x^{(i)}, y^{(i)})$.

Backpropagation

A dynamic programming implementation of the multivariable chain rule that propagates errors backward from the output layer to compute the partial derivatives of the loss with respect to all network weights in linear time.

Activation Function Saturation

The condition where an activation function's derivative becomes near zero ($|g'(a)| \approx 0$) across extreme input values, preventing gradients from flowing through the network and halting learning via gradient descent.

Momentum (SGD)

A technique in gradient descent that incorporates an exponentially decaying velocity vector of previous weight updates, $v^{(t+1)} = \alpha v^{(t)} - \eta \nabla \ell$, helping the algorithm push through flat plateaus and dampening oscillations.

Batch Normalization

A training technique that standardizes the inputs to hidden units across each mini-batch to have zero mean and unit variance, followed by a learnable affine transformation with scale $\gamma$ and shift $\beta$.

Residual Connection (Skip Connection)

A network connection that adds the activation of an earlier layer directly to the output of a later layer, $z^{(i+k)} = z^{(i)} + G(z^{(i)})$, creating shortcut pathways for gradients to backpropagate directly without vanishing.

Vanishing Gradient Problem

An issue during backpropagation in deep neural networks where error gradients shrink exponentially as they propagate backward through many layers with small derivative values, preventing earlier layers from updating effectively.

Regularization

Any modification made to a machine learning algorithm or objective function designed specifically to reduce generalization error on unseen data without necessarily reducing training error.

Weight Decay (L2 Regularization)

A regularization method that adds an $L_2$ norm penalty $\frac{\lambda}{2}\|w\|_2^2$ to the objective function, shrinking weights toward zero at each gradient step by a multiplicative factor of $(1 - \eta\lambda)$.

Early Stopping

A regularization technique where iterative training is halted once validation error fails to improve after a specified patience threshold of iterations, preventing the network from overfitting to the training set.

Weight Sharing

A regularization approach that restricts subsets of network parameters, either by forcing them to take identical values (hard weight sharing) or by tying them to a common prior distribution (soft weight sharing).

Convolutional Neural Network (CNN)

A neural network architecture specialized for grid-structured data that replaces general dense matrix multiplication with discrete convolution (or cross-correlation) operations, enforcing sparse local connectivity and translation-invariant parameter sharing.

Toeplitz Matrix

A structured matrix with constant values along each descending diagonal from left to right, which corresponds to the linear operator representation of a discrete convolution.

Pooling

A non-linear spatial downsampling operation in CNNs (such as max pooling or average pooling) that summarizes local neighborhoods of neurons, reducing feature map dimensions and providing local translational invariance.

Transformer

A neural network architecture designed for sequence data that processes tokens in parallel using stacked multi-head self-attention mechanisms and feedforward layers, eschewing recurrence and convolution.

Self-Attention

A mechanism mapping an input sequence of tokens $X \in \mathbb{R}^{d \times M}$ to a transformed sequence by computing attention weights from dot products of token queries $q_m = U_q x_m$ and keys $k_m = U_k x_m$ via the softmax function.

Multi-Head Self-Attention (MHSA)

An attention architecture that applies $H$ distinct self-attention mechanisms in parallel using separate projection matrices, linearly combining their outputs through projection matrix $V_h$ to capture diverse contextual dependencies simultaneously.

Masked Self-Attention

A constrained variant of self-attention where the attention matrix $A$ is forced to be upper triangular ($A_{m'm} = 0$ for $m' > m$), ensuring that each token attends only to preceding tokens in autoregressive language models.

Singular Value Decomposition (SVD)

The matrix factorization of any real $m \times n$ matrix $A$ into $A = U\Sigma V^\top$, where $U$ and $V$ are orthogonal matrices of left- and right-singular vectors, and $\Sigma$ contains the ordered, non-negative singular values $\sigma_i$.

Frobenius Norm

A matrix norm defined for an $m \times n$ matrix $M$ as the square root of the sum of squared elements, $\ travel \|M\|_F = \sqrt{\sum_{i=1}^m \sum_{j=1}^n m_{ij}^2} = \sqrt{\text{tr}(M^\top M)}$, which is invariant under orthogonal rotations.

Schmidt Low-Rank Matrix Approximation Theorem

A theorem stating that the optimal rank-$k$ approximation of a matrix $A$ under both the Frobenius and spectral norms is given by its truncated SVD, $\tilde{A}_k = \sum_{i=1}^k \sigma_i u_i v_i^\top$.

Spectral Norm

The induced operator norm of a matrix defined by $\ travel \|M\|_2 = \sup_{x \ne 0} \frac{\|Mx\|_2}{\|x\|_2}$, which evaluates exactly to the largest singular value $\sigma_1$ of $M$.

Principal Component Analysis (PCA)

An unsupervised orthogonal linear transformation that projects centered data onto an orthonormal basis composed of the eigenvectors of the sample covariance matrix, arranged in descending order of explained variance.

Coordinate Descent

An iterative optimization algorithm that minimizes a multivariate objective function by successively solving exact one-dimensional minimization problems along single coordinate directions while keeping all other variables fixed.

K-Means Algorithm

A centroid-based clustering algorithm that uses coordinate descent to minimize the sum of squared Euclidean distances between observations and their assigned centroids, alternating between assigning points to the closest centroid and updating centroids to cluster means.

Gaussian Mixture Model (GMM)

A probabilistic latent variable model expressing the distribution of an observation as a convex combination of $K$ Gaussian component distributions: $p(x) = \sum_{k=1}^K w_k N(x; \mu_k, \Sigma_k)$.

Expectation-Maximization (EM) Algorithm

An iterative coordinate ascent algorithm for finding maximum likelihood parameter estimates in models with latent variables, alternating between calculating posterior distributions of latent assignments (E-step) and maximizing expected complete-data log-likelihood (M-step).

Responsibility (\gamma_{ik})

In a mixture model, the posterior probability that observation $x^{(i)}$ was generated by mixture component $k$, computed in the E-step as $\gamma_{ik} = \frac{w_k p(x^{(i)} \mid \psi_k)}{\sum_{j=1}^K w_j p(x^{(i)} \mid \psi_j)}$.