Mathematical Foundations for Machine Learning

The landscape of machine learning, despite its practical applications and computational emphasis, is fundamentally a mathematical discipline. At its core, every algorithm, from the simplest linear regression to the most sophisticated deep neural network, implements mathematical operations on data representations. Understanding these mathematical foundations is not merely preparatory work for what follows; it constitutes the essential framework through which we interpret why algorithms work, when they fail, and how they can be improved. This chapter develops the mathematical prerequisites that will recur throughout this text, establishing the notation, concepts, and intuitions necessary for rigorous engagement with classical machine learning methods.

The mathematical machinery required falls naturally into several interconnected domains. Linear algebra provides the language for representing data and transformations in high-dimensional spaces. Probability theory and statistics offer the framework for reasoning under uncertainty and making inferences from samples. Optimization theory addresses the fundamental question of how machines learn by finding parameters that minimize or maximize objectives. Information theory quantifies uncertainty and provides the theoretical foundation for many decision-making principles. These four pillars are not independent topics but rather deeply interwoven aspects of a coherent mathematical edifice that supports the entire field of machine learning.

Vector Spaces and Linear Transformations

The study of machine learning begins with understanding how we represent data mathematically. A dataset consisting of $n$ observations, each described by $d$ features, is naturally represented as a matrix $\mathbf{X} \in \mathbb{R}^{n \times d}$, where each row corresponds to an observation and each column to a feature. This representation, seemingly simple, carries profound implications. The choice of feature representation determines what structure exists in the data and what algorithms can exploit that structure effectively.

A vector space (or linear space) is a set of objects called vectors, together with two operations—vector addition and scalar multiplication—that satisfy a specific collection of axioms. For our purposes, we work primarily with $\mathbb{R}^d$, the space of real-valued $d$-dimensional vectors, equipped with the standard operations of component-wise addition and multiplication by real scalars. The dimension of a vector space is the minimum number of vectors required to span the space, meaning any vector in the space can be expressed as a linear combination of these basis vectors.

The concept of linear independence is crucial for understanding dimensionality. A set of vectors $\{\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_k\}$ is linearly independent if no vector in the set can be expressed as a linear combination of the others. If $k = d$ and the vectors are independent in $\mathbb{R}^d$, they form a basis, and every vector in the space has a unique representation in terms of this basis. The rank of a matrix $\mathbf{X}$ is the dimension of the subspace spanned by its rows (or columns), representing the effective number of independent features or independent samples in the data.

Linear transformations, implemented as matrix multiplication, form the backbone of many machine learning operations. A transformation $T: \mathbb{R}^d \rightarrow \mathbb{R}^m$ is linear if it satisfies $T(\mathbf{u} + \mathbf{v}) = T(\mathbf{u}) + T(\mathbf{v})$ and $T(c\mathbf{u}) = cT(\mathbf{u})$ for all vectors $\mathbf{u}, \mathbf{v}$ and scalars $c$. Every such transformation can be represented by a matrix $\mathbf{A} \in \mathbb{R}^{m \times d}$ such that $T(\mathbf{x}) = \mathbf{A}\mathbf{x}$. The geometric interpretation is illuminating: linear transformations can rotate vectors, stretch or compress them along certain directions, and project them onto lower-dimensional subspaces—operations that correspond directly to dimensionality reduction, feature extraction, and representation learning in machine learning contexts.

The norm of a vector provides a measure of its "length" or "magnitude." The $L^p$ norm of a vector $\mathbf{x} \in \mathbb{R}^d$ is defined as:

$$\|\mathbf{x}\|_p = \left(\sum_{i=1}^{d} |x_i|^p\right)^{1/p}$$

The $L^2$ norm (Euclidean norm), where $p = 2$, is the most commonly used in machine learning. It corresponds to the familiar notion of distance in physical space and satisfies the Cauchy-Schwarz inequality:

$$|\mathbf{x}^T \mathbf{y}| \leq \|\mathbf{x}\|_2 \|\mathbf{y}\|_2$$

The $L^1$ norm, measuring the sum of absolute values, is more robust to outliers, while the $L_\infty$ norm captures the maximum absolute component. The choice of norm significantly affects algorithm behavior, as it determines what constitutes "similar" or "close" in the data space.

Matrix Operations and Properties

Matrices encode linear transformations, and their algebraic properties directly influence machine learning algorithms. The multiplication of matrices $\mathbf{A} \in \mathbb{R}^{m \times n}$ and $\mathbf{B} \in \mathbb{R}^{n \times p}$ yields $\mathbf{C} = \mathbf{A}\mathbf{B} \in \mathbb{R}^{m \times p}$, where:

$$c_{ij} = \sum_{k=1}^{n} a_{ik} b_{kj}$$

This operation corresponds to composing linear transformations: applying $\mathbf{B}$ then $\mathbf{A}$. The identity matrix $\mathbf{I}_n$ acts as the multiplicative identity, so $\mathbf{A}\mathbf{I}_n = \mathbf{I}_m \mathbf{A} = \mathbf{A}$.

The transpose of a matrix, denoted $\mathbf{A}^T$, exchanges rows and columns: if $\mathbf{A}_{ij} = a_{ij}$, then $(\mathbf{A}^T)_{ij} = a_{ji}$. The transpose satisfies $(\mathbf{A}\mathbf{B})^T = \mathbf{B}^T \mathbf{A}^T$. A matrix is symmetric if $\mathbf{A} = \mathbf{A}^T$, and such matrices arise naturally when representing certain transformations and covariance structures.

The determinant of a square matrix $\mathbf{A} \in \mathbb{R}^{n \times n}$, denoted $\det(\mathbf{A})$ or $|\mathbf{A}|$, encodes crucial information about the linear transformation it represents. If $\det(\mathbf{A}) = 0$, the matrix is singular or non-invertible, meaning the transformation it represents collapses space onto a lower-dimensional subspace, irrecoverably losing information. If $\det(\mathbf{A}) \neq 0$, the matrix is invertible (nonsingular), and there exists a unique matrix $\mathbf{A}^{-1}$ such that $\mathbf{A}\mathbf{A}^{-1} = \mathbf{A}^{-1}\mathbf{A} = \mathbf{I}$.

The trace of a matrix, $\text{tr}(\mathbf{A}) = \sum_{i=1}^{n} a_{ii}$, equals the sum of its diagonal elements and satisfies $\text{tr}(\mathbf{A}\mathbf{B}) = \text{tr}(\mathbf{B}\mathbf{A})$ (when both products are defined). This cyclic property of the trace proves remarkably useful in statistical calculations and theoretical derivations.

Positive semidefinite matrices play a fundamental role in probability and statistics. A symmetric matrix $\mathbf{A} \in \mathbb{R}^{n \times n}$ is positive semidefinite if $\mathbf{x}^T \mathbf{A} \mathbf{x} \geq 0$ for all $\mathbf{x} \in \mathbb{R}^n$. It is positive definite if the inequality is strict for all nonzero $\mathbf{x}$. These matrices correspond to valid covariance structures and define convex functions, properties essential to many machine learning algorithms.

The condition number of a matrix, defined as the ratio of its largest to smallest singular value, measures how numerical computations involving the matrix behave. High condition numbers indicate that the matrix is "ill-conditioned," meaning small changes in input can cause large changes in output—an important consideration when algorithms involve solving linear systems or inverting matrices.

Eigenvalues and Eigenvectors

Eigenvalues and eigenvectors reveal the fundamental geometric structure of linear transformations. For a square matrix $\mathbf{A} \in \mathbb{R}^{n