Mathematical Foundations of Machine Learning

Mathematical Foundations of Machine Learning

The journey into machine learning begins not with algorithms or implementations, but with the elegant mathematical structures that underpin them. Understanding why machine learning works—why a neural network can recognize faces, why a support vector machine can separate spam from legitimate email, or why an ensemble of decision trees can predict housing prices with remarkable accuracy—requires a deep appreciation of the mathematical principles that govern these methods. This chapter establishes the essential mathematical toolkit that will accompany us throughout this book, providing the foundation upon which all subsequent algorithms, theories, and practical implementations rest.

The three pillars of mathematical machinery essential for classical machine learning are linear algebra, probability theory, and optimization theory. Linear algebra provides the language for representing data and models in high-dimensional spaces, enabling us to manipulate millions of features efficiently through matrix operations. Probability theory offers the framework for reasoning under uncertainty, allowing us to make predictions, quantify confidence, and incorporate prior knowledge into our models. Optimization theory gives us the tools to find the best parameters of our models by minimizing or maximizing objective functions, the computational heart of every learning algorithm. Together, these mathematical disciplines form a cohesive framework that transforms the abstract goal of "learning from data" into precise mathematical optimization problems that can be solved algorithmically.

1.1 Linear Algebra Fundamentals

Linear algebra is the mathematical discipline that studies vectors, vector spaces, and linear transformations. In the context of machine learning, we represent our data as vectors in high-dimensional spaces, where each dimension corresponds to a feature or attribute. A dataset of $n$ samples, each with $d$ features, is naturally represented as an $n \times d$ matrix $X \in \mathbb{R}^{n \times d}$, where each row represents a data point and each column represents a feature across all samples. This matrix representation is not merely convenient notation; it enables the use of highly optimized linear algebra libraries that can perform operations on millions of elements in parallel.

Vector Spaces and Operations

A vector space (or linear space) is a collection of vectors that can be added together and multiplied by scalars to produce another vector in the same space. Formally, a set $\mathcal{V}$ is a vector space over the field $\mathbb{R}$ if for any vectors $\mathbf{u}, \mathbf{v}, \mathbf{w} \in \mathcal{V}$ and any scalars $a, b \in \mathbb{R}$, the following properties hold: vector addition is commutative ($\mathbf{u} + \mathbf{v} = \mathbf{v} + \mathbf{u}$) and associative ($\mathbf{u} + (\mathbf{v} + \mathbf{w}) = (\mathbf{u} + \mathbf{v}) + \mathbf{w}$); there exists an additive identity (the zero vector $\mathbf{0}$) such that $\mathbf{v} + \mathbf{0} = \mathbf{v}$; every vector has an additive inverse such that $\mathbf{v} + (-\mathbf{v}) = \mathbf{0}$; scalar multiplication distributes over vector addition ($a(\mathbf{u} + \mathbf{v}) = a\mathbf{u} + a\mathbf{v}$) and over field addition ($(a + b)\mathbf{v} = a\mathbf{v} + b\mathbf{v}$); and scalar multiplication is associative ($(ab)\mathbf{v} = a(b\mathbf{v})$).

The dimension of a vector space is the minimum number of vectors needed to span the space—that is, to represent any vector in the space as a linear combination of these basis vectors. In machine learning, we frequently work in high-dimensional spaces where the number of dimensions can far exceed the number of samples. Consider a text classification problem where each document is represented by the frequency of occurrence of words from a vocabulary of 50,000 words. Each document is a point in $\mathbb{R}^{50000}$, a space of astronomical dimensionality. While intuition from low-dimensional geometry often fails in such spaces (a phenomenon known as the "curse of dimensionality"), the algebraic structure remains valid and exploitable.

The inner product (or dot product) between two vectors $\mathbf{u}, \mathbf{v} \in \mathbb{R}^d$ is defined as $\langle \mathbf{u}, \mathbf{v} \rangle = \mathbf{u}^\top \mathbf{v} = \sum_{i=1}^d u_i v_i$. The inner product induces the Euclidean norm (or $\ell_2$ norm) $\|\mathbf{v}\|_2 = \sqrt{\langle \mathbf{v}, \mathbf{v} \rangle} = \sqrt{\sum_{i=1}^d v_i^2}$, which measures the length of a vector. Two vectors are orthogonal if their inner product is zero: $\langle \mathbf{u}, \mathbf{v} \rangle = 0$. The cosine similarity between two vectors measures the angle between them and is defined as $\cos(\theta) = \frac{\langle \mathbf{u}, \mathbf{v} \rangle}{\|\mathbf{u}\|_2 \|\mathbf{v}\|_2}$. This measure plays a crucial role in many machine learning algorithms, from document retrieval using TF-IDF vectors to collaborative filtering in recommendation systems.

Matrix Operations and Properties

Matrices represent linear transformations between vector spaces. An $m \times n$ matrix $A$ maps vectors from $\mathbb{R}^n$ to $\mathbb{R}^m$: for $\mathbf{x} \in \mathbb{R}^n$, the transformation is $\mathbf{y} = A\mathbf{x}$ where $y_i = \sum_{j=1}^n A_{ij} x_j$. This operation is computationally efficient, requiring $O(mn)$ scalar multiplications and additions, and can be parallelized across rows and, with appropriate blocking, across cache hierarchies.

The transpose of a matrix $A \in \mathbb{R}^{m \times n}$ is denoted $A^\top \in \mathbb{R}^{n \times m}$, with entries $A^\top_{ij} = A_{ji}$. Symmetric matrices satisfy $A = A^\top$. The trace of a square matrix $A \in \mathbb{R}^{n \times n}$ is the sum of its diagonal elements: $\text{tr}(A) = \sum_{i=1}^n A_{ii}$. The trace operator has several useful properties: $\text{tr}(A^\top) = \text{tr}(A)$, $\text{tr}(AB) = \text{tr}(BA)$ for conformable matrices (the cyclic property), and $\text{tr}(A + B) = \text{tr}(A) + \text{tr}(B)$.

Matrix multiplication $C = AB$ where $A \in \mathbb{R}^{m \times k}$ and $B \in \mathbb{R}^{k \times n}$ produces $C \in \mathbb{R}^{m \times n}$ with entries $C_{ij} = \sum_{l=1}^k A_{il} B_{lj}$. Note that matrix multiplication is generally not commutative: $AB \neq BA$ in most cases. However, the product $A^\top A$ is always symmetric since $(A^\top A)^\top = A^\top A$.

The determinant of a square matrix $A \in \mathbb{R}^{n \times n}$, denoted $\det(A)$ or $|A|$, is a scalar that encodes important properties of the linear transformation represented by $A$. The determinant equals zero if and only if the matrix is singular (non-invertible), which means the transformation collapses at least one dimension. For a $2 \times 2$ matrix $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$, the determinant is $ad - bc$. For larger matrices, the determinant can be computed recursively or through LU decomposition. While direct computation of determinants is $O(n!)$, the concept is crucial for understanding eigenvalues.

The inverse of a matrix $A \in \mathbb{R}^{n \times n}$, denoted $A^{-1}$, satisfies $A A^{-1} = A^{-1} A = I_n$, where $I_n$ is the $n \times n$ identity matrix. Only square matrices with full rank (linearly independent rows and columns) have inverses. The inverse can be computed using Gaussian elimination ($O(n^3)$) or through more numerically stable methods like LU decomposition with partial pivoting. In the context of machine learning, matrix inverses appear frequently when solving linear systems in linear regression (though in practice we rarely explicitly compute inverses due to numerical stability concerns).

Eigenvalues and Eigenvectors

Eigenvalues and eigenvectors are perhaps the most profound concepts in linear algebra for machine learning practitioners. An eigenvector of a square matrix $A \in \mathbb{R}^{n \times n}$ is a non-zero vector $\mathbf{v} \