Math Foundations

Everything below is math you will use directly when reading papers, implementing algorithms, and understanding why things work.

Table of contents

1. Linear algebra
2. Calculus and analysis
3. Probability theory
4. Statistics
5. Information theory

1. Linear algebra

1.1 Vectors

A column vector $\mathbf{x} \in \mathbb{R}^n$ is a list of $n$ real numbers. Row vector = $\mathbf{x}^\top$.

Inner product (dot product):

Euclidean (L2) norm:

L1 norm: $\|\mathbf{x}\|_1 = \sum |x_i|$. Induces sparsity in optimization.

L∞ norm: $\|\mathbf{x}\|_\infty = \max_i |x_i|$.

Cauchy–Schwarz inequality: $|\mathbf{x}^\top \mathbf{y}| \leq \|\mathbf{x}\|\,\|\mathbf{y}\|$. Equality iff $\mathbf{x} = c\mathbf{y}$. This is the foundation of cosine similarity.

Cosine similarity: $\cos\theta = \frac{\mathbf{x}^\top \mathbf{y}}{\|\mathbf{x}\|\,\|\mathbf{y}\|} \in [-1,1]$.

1.2 Matrices

A matrix $\mathbf{A} \in \mathbb{R}^{m \times n}$ has $m$ rows and $n$ columns.

Transpose: $(\mathbf{A}^\top)_{ij} = A_{ji}$. Matrix product: $(\mathbf{AB})_{ik} = \sum_j A_{ij} B_{jk}$ (row-times-column). Properties: $(\mathbf{AB})^\top = \mathbf{B}^\top \mathbf{A}^\top$, $\;(\mathbf{AB})\mathbf{C} = \mathbf{A}(\mathbf{BC})$.

Symmetric matrix: $\mathbf{A} = \mathbf{A}^\top$. Covariance matrices are always symmetric.

Trace: $\operatorname{tr}(\mathbf{A}) = \sum_i A_{ii}$. Cyclic: $\operatorname{tr}(\mathbf{ABC}) = \operatorname{tr}(\mathbf{CAB})$.

Determinant: scalar that captures volume scaling. $\det(\mathbf{AB}) = \det(\mathbf{A})\det(\mathbf{B})$.

Rank: dimension of column space (= row space). Full rank ⇒ invertible (for square matrices).

Frobenius norm: $\|\mathbf{A}\|_F = \sqrt{\sum_{ij} A_{ij}^2} = \sqrt{\operatorname{tr}(\mathbf{A}^\top\mathbf{A})}$.

1.3 Systems of linear equations

$\mathbf{Ax} = \mathbf{b}$: if $\mathbf{A}$ is square and invertible, unique solution $\mathbf{x} = \mathbf{A}^{-1}\mathbf{b}$. In practice, use Gaussian elimination or numpy.linalg.solve (never explicitly invert).

Overdetermined ($m > n$): no exact solution in general → least-squares $\min_\mathbf{x}\|\mathbf{Ax}-\mathbf{b}\|^2$ → normal equations $\mathbf{A}^\top\mathbf{Ax} = \mathbf{A}^\top\mathbf{b}$.

1.4 Eigendecomposition

For square $\mathbf{A} \in \mathbb{R}^{n\times n}$:

$\lambda$ is an eigenvalue and $\mathbf{v} \neq \mathbf{0}$ is its eigenvector.

Spectral theorem: a real symmetric matrix has all real eigenvalues and an orthonormal basis of eigenvectors:

where $\boldsymbol{\Lambda} = \operatorname{diag}(\lambda_1,\ldots,\lambda_n)$.

Positive semidefinite (PSD): all $\lambda_i \geq 0$. Equivalent: $\mathbf{x}^\top\mathbf{A}\mathbf{x} \geq 0\; \forall \mathbf{x}$. Covariance matrices are always PSD.

Use in ML: PCA uses eigendecomposition of the sample covariance to find principal directions.

1.5 Singular value decomposition (SVD)

For any $\mathbf{A} \in \mathbb{R}^{m \times n}$:

where:

• $\mathbf{U} \in \mathbb{R}^{m\times m}$: left singular vectors (columns orthonormal).
• $\boldsymbol{\Sigma} \in \mathbb{R}^{m\times n}$: diagonal with singular values $\sigma_1 \geq \sigma_2 \geq \cdots \geq 0$.
• $\mathbf{V} \in \mathbb{R}^{n\times n}$: right singular vectors (columns orthonormal).

Thin SVD: keep only $r = \operatorname{rank}(\mathbf{A})$ nonzero singular values. $\mathbf{A} = \sum_{i=1}^r \sigma_i \mathbf{u}_i \mathbf{v}_i^\top$ (outer product expansion).

Rank-$k$ approximation: truncate to first $k$ singular values — best rank-$k$ approximation in Frobenius and spectral norm (Eckart–Young theorem).

Connections:

• Singular values of $\mathbf{A}$ = square roots of eigenvalues of $\mathbf{A}^\top\mathbf{A}$.
• Right singular vectors = eigenvectors of $\mathbf{A}^\top\mathbf{A}$ (used in PCA).
• SVD is the computational workhorse behind PCA, matrix factorization in recommenders, pseudoinverse.

Pseudoinverse: $\mathbf{A}^+ = \mathbf{V}\boldsymbol{\Sigma}^+\mathbf{U}^\top$ where $\Sigma^+$ inverts nonzero entries. Gives minimum-norm least-squares solution when $\mathbf{A}$ is rank-deficient.

1.6 Matrix calculus (gradients)

Gradient of a scalar w.r.t. a vector $\mathbf{w} \in \mathbb{R}^n$:

Key identities (denominator layout, $\mathbf{a}$ constant):

Hessian: matrix of second partials $\mathbf{H}_{ij} = \partial^2 f / \partial w_i \partial w_j$. PSD Hessian everywhere ⇒ convex function.

2. Calculus and analysis

2.1 Derivative rules recap

Chain rule (scalar): $(f(g(x)))' = f'(g(x)) \cdot g'(x)$.

Chain rule (vector): if $\mathbf{z} = f(\mathbf{y})$ and $\mathbf{y} = g(\mathbf{x})$, then:

This is the backbone of backpropagation.

Product rule: $(fg)' = f'g + fg'$. Quotient rule: $(f/g)' = (f'g - fg')/g^2$.

2.2 Taylor expansion

Multivariate version:

Used in Newton's method (second-order optimization) and understanding convergence of gradient descent.

2.3 Convexity

A set $C$ is convex if $\forall \mathbf{x},\mathbf{y} \in C,\; t\in[0,1]:\; t\mathbf{x}+(1-t)\mathbf{y}\in C$.

A function $f: C \to \mathbb{R}$ is convex if:

Equivalently: $\mathbf{H}(\mathbf{w}) \succeq 0$ (PSD Hessian) everywhere.

Why it matters: any local minimum of a convex function is a global minimum.

Strictly convex: $\mathbf{H} \succ 0$ (positive definite) ⇒ unique global minimum.

Examples in ML:

• MSE loss (linear regression): convex (Hessian = $\frac{2}{n}\mathbf{X}^\top\mathbf{X}$, PSD).
• Cross-entropy (logistic regression): convex in $\mathbf{w}$.
• Ridge objective: strictly convex.
• Neural network losses: non-convex in general.

2.4 Lagrangian optimization and KKT conditions

Constrained optimization: $\min f(\mathbf{w})$ s.t. $g_i(\mathbf{w}) \leq 0$, $h_j(\mathbf{w}) = 0$.

Lagrangian: $\mathcal{L}(\mathbf{w}, \boldsymbol{\alpha}, \boldsymbol{\nu}) = f(\mathbf{w}) + \sum_i \alpha_i g_i(\mathbf{w}) + \sum_j \nu_j h_j(\mathbf{w})$.

KKT conditions (necessary at optimum under constraint qualifications):

1. Stationarity: $\nabla_\mathbf{w} \mathcal{L} = \mathbf{0}$.
2. Primal feasibility: $g_i(\mathbf{w}^\star) \leq 0$.
3. Dual feasibility: $\alpha_i \geq 0$.
4. Complementary slackness: $\alpha_i g_i(\mathbf{w}^\star) = 0$.

SVM is derived directly from KKT conditions on the margin-maximization problem.

3. Probability theory

3.1 Foundations

Sample space $\Omega$: set of all outcomes. Event $A \subseteq \Omega$. Probability measure $P$: $P(\Omega)=1$, $P(A) \geq 0$, countably additive.

Conditional probability: $P(A|B) = P(A \cap B)/P(B)$.

Independence: $P(A \cap B) = P(A)P(B)$.

Bayes' theorem:

In ML: $P(\text{hypothesis}|\text{data}) \propto P(\text{data}|\text{hypothesis})\cdot P(\text{hypothesis})$ — this is the foundation of Bayesian learning.

3.2 Random variables and distributions

PMF (discrete): $P(X=x)$. PDF (continuous): $f(x) = dF/dx$. CDF: $F(x) = P(X \leq x)$.

Expectation: $\mathbb{E}[X] = \sum x P(X=x)$ or $\int x f(x)dx$. Variance: $\text{Var}(X) = \mathbb{E}[(X-\mu)^2] = \mathbb{E}[X^2] - (\mathbb{E}[X])^2$. Standard deviation: $\sigma = \sqrt{\text{Var}(X)}$. Covariance: $\text{Cov}(X,Y) = \mathbb{E}[(X-\mu_X)(Y-\mu_Y)]$.

Linearity of expectation: $\mathbb{E}[aX+bY] = a\mathbb{E}[X]+b\mathbb{E}[Y]$ (always, no independence needed).

3.3 Key distributions in ML

Bernoulli: $X \in \{0,1\}$, $P(X=1)=p$. Mean = $p$, Var = $p(1-p)$. Binary classification labels.

Binomial $\text{Bin}(n,p)$: number of successes in $n$ Bernoulli trials.

Categorical / Multinoulli: $P(X=k) = p_k$, $\sum p_k = 1$. Multi-class labels; output of softmax.

Gaussian $\mathcal{N}(\mu,\sigma^2)$:

Properties: symmetric, unimodal, characterized by mean and variance, 68-95-99.7 rule.

Multivariate Gaussian $\mathcal{N}(\boldsymbol{\mu},\boldsymbol{\Sigma})$:

Used in GMMs, Gaussian processes, LDA.

Uniform: constant density. Used in random initialization.

Exponential: $f(x) = \lambda e^{-\lambda x}$, $x \geq 0$. Memoryless property.

Beta $\text{Beta}(\alpha,\beta)$: distribution over $[0,1]$; conjugate prior to Bernoulli/Binomial.

Dirichlet $\text{Dir}(\boldsymbol{\alpha})$: distribution over probability simplices; conjugate prior to Categorical.

3.4 Maximum likelihood estimation (MLE)

Given i.i.d. data $\{x_i\}_{i=1}^n$ and a parameterized model $p(x|\theta)$, find $\theta$ to maximize the likelihood:

Equivalently maximize the log-likelihood (avoids underflow, same argmax):

Example — Gaussian MLE: $\ell(\mu,\sigma^2) = -\frac{n}{2}\log(2\pi\sigma^2) - \frac{1}{2\sigma^2}\sum_i(x_i-\mu)^2$. Setting $\partial\ell/\partial\mu = 0$: $\hat{\mu} = \bar{x}$. Setting $\partial\ell/\partial\sigma^2 = 0$: $\hat{\sigma}^2 = \frac{1}{n}\sum(x_i-\bar{x})^2$ (biased).

Example — Bernoulli MLE: $\hat{p} = \frac{\sum x_i}{n}$ (fraction of 1s).

MLE and OLS connection: If $y_i = \mathbf{x}_i^\top\mathbf{w} + \varepsilon_i$ with $\varepsilon_i \sim \mathcal{N}(0,\sigma^2)$, then MLE for $\mathbf{w}$ = minimize $\sum(y_i - \mathbf{x}_i^\top\mathbf{w})^2$ = OLS.

3.5 Maximum a posteriori (MAP)

Incorporate a prior $p(\theta)$ via Bayes:

MAP vs regularization: Gaussian prior $\theta \sim \mathcal{N}(\mathbf{0},\frac{1}{\lambda}\mathbf{I})$ gives MAP = Ridge regression. Laplace prior gives MAP = Lasso.

3.6 Law of large numbers and central limit theorem

LLN: $\bar{X}_n \xrightarrow{P} \mathbb{E}[X]$ as $n\to\infty$. Basis for Monte Carlo.

CLT: $\sqrt{n}(\bar{X}_n - \mu) \xrightarrow{d} \mathcal{N}(0,\sigma^2)$. Why Gaussian distribution appears everywhere.

4. Statistics

4.1 Estimators and their properties

An estimator $\hat{\theta}(\mathcal{D})$ is a function of the data.

Bias: $\text{Bias}(\hat\theta) = \mathbb{E}[\hat\theta] - \theta^\star$. Zero bias = unbiased. Variance: $\text{Var}(\hat\theta) = \mathbb{E}[(\hat\theta - \mathbb{E}[\hat\theta])^2]$. Mean squared error: $\text{MSE}(\hat\theta) = \text{Bias}^2(\hat\theta) + \text{Var}(\hat\theta)$.

This is the bias-variance decomposition of an estimator's error — mirrors the ML bias-variance tradeoff exactly.

Consistency: $\hat\theta_n \xrightarrow{P} \theta^\star$ as $n \to \infty$.

Efficiency: estimator with minimum variance among unbiased estimators (Cramér-Rao bound).

4.2 Hypothesis testing

Framework: null hypothesis $H_0$, alternative $H_1$. Test statistic $T$, reject $H_0$ if $T > t_\alpha$.

p-value: probability of observing data at least as extreme as seen, *assuming $H_0$ true*. Small p-value = evidence against $H_0$.

Type I error (false positive): reject $H_0$ when it is true. Controlled at level $\alpha$. Type II error (false negative): fail to reject $H_0$ when it is false. Related to power.

t-test, chi-squared test, ANOVA: standard tests for means, proportions, group comparisons.

4.3 Confidence intervals

A $95\%$ CI $[L,U]$ means: if we repeated the experiment many times, $95\%$ of such intervals would contain the true $\theta^\star$. For large $n$ (CLT):

4.4 Experimental design

Randomized controlled trial (A/B test): gold standard for causal inference. Random assignment breaks confounding.

Confounding: a variable $Z$ affects both the treatment $T$ and outcome $Y$, creating spurious correlation. Models can detect correlation but cannot automatically infer causation from observational data.

Stratification: ensure both groups have similar distributions of known confounders. Used in stratified k-fold CV.

5. Information theory

5.1 Entropy

Shannon entropy of a discrete distribution $p$:

Measures uncertainty / minimum expected bits to encode a sample. Max entropy = uniform distribution. $H=0$ when distribution is deterministic.

5.2 Cross-entropy and KL divergence

Cross-entropy between true $p$ and model distribution $q$:

Used as classification loss: true labels are $p$ (one-hot), model output is $q$ (probabilities).

KL divergence (Kullback–Leibler):

Always $\geq 0$ (Gibbs' inequality); equals 0 iff $p = q$. Not symmetric.

Minimizing cross-entropy ≡ minimizing KL divergence (since $H(p)$ is fixed w.r.t. model parameters).

5.3 Mutual information

Measures statistical dependence (= 0 iff independent). Used in feature selection, information bottleneck.

5.4 Gini impurity (decision trees)

Alternative impurity to entropy (computationally faster, similar results). The CART algorithm minimizes weighted Gini after each split.

*File: notes/01_math_foundations.md — next: notes/02_learning_theory.md*