Abstract
Pen and Paper Exercises in Machine Learning is a comprehensive pedagogical resource designed to strengthen the mathematical foundations of machine learning practitioners. By providing a curated set of rigorous exercises with exhaustive, step-by-step solutions, it bridges the gap between high-level conceptual understanding and the granular algebraic mechanics required for advanced research and implementation. This work serves as a "math workout" focused on the unsupervised methods, inference, and learning techniques that form the backbone of probabilistic machine learning.
Introduction
In the modern machine learning landscape, a significant divide has emerged between the ability to "use" ML and the ability to "understand" it. While many students and engineers can implement complex neural networks using high-level libraries, they often struggle when tasked with deriving a gradient for a custom loss function or explaining the flow of evidence in a graphical model.
Author Michael U. Gutmann identifies a specific gap in existing literature: while excellent textbooks exist, their exercises often lack solutions or provide only brief answers, leading to "mathematical rustiness" and frustration. This paper (effectively a short book) addresses this by providing a structured curriculum of derivations that reinforce the mathematical intuition necessary for deep technical proficiency.
Pedagogical Framework and Methods
The methodology of this work is pedagogical rather than algorithmic. It organizes machine learning theory into a structured curriculum of pen-and-paper derivations across several key domains:
- Linear Algebra & Optimization: The exercises move beyond basic matrix multiplication to explore Gram-Schmidt orthogonalization, eigenvalue decompositions for symmetric matrices, and the gradients of matrix-valued functions—concepts essential for understanding backpropagation in complex architectures.
- Graphical Models: A deep dive into Directed Acyclic Graphs (DAGs) and Undirected Graphical Models, focusing on the logic used to determine conditional independence, such as d-separation, moralization, and triangulation.
- Inference & Message Passing: Detailed walkthroughs of the Sum-Product and Max-Sum algorithms on factor graphs, which serve as the foundations of modern probabilistic programming.
- Sampling & Variational Inference: Derivations for Importance Sampling, Rejection Sampling, and the Evidence Lower Bound (ELBO) used in Mean Field Variational Inference.
Rather than using empirical datasets, the work utilizes "toy models" and canonical examples common in ML literature to illustrate concepts, such as the Asia (Chest Clinic) network for probabilistic reasoning, Restricted Boltzmann Machines (RBMs) for undirected modeling, and Hidden Markov Models (HMMs) for sequential data.
Key Insights and Mathematical Philosophy
The resource is built upon several core philosophies regarding technical mastery:
- The "Use it or Lose it" Philosophy: Mathematical skill is a perishable commodity. Even for those who understand the theory, the ability to perform the underlying "algebraic heavy lifting" requires constant practice.
- The Power of Factorization: A recurring theme is how complex joint probability distributions can be broken down into local kernels. The exercises demonstrate exactly how this factorization enables efficient computation (message passing) that would otherwise be computationally intractable.
- Geometric Intuition: The paper provides unique perspectives, such as a derivation of why the absolute value of a determinant represents the area/volume change in a linear transform, providing the "why" behind the Jacobian term in the change of variables formula.
- Change of Measure Perspective: The exercises offer a unique look at the alpha-recursion in HMMs, framing filtering and prediction as a sequence of extensions and corrections rather than just a set of recursive formulas.
Conclusion and Future Directions
The result of this work is a 200+ page open-source manual that serves as a companion to standard texts like Barber’s Bayesian Reasoning and Machine Learning or Bishop’s Pattern Recognition and Machine Learning. It proves fundamental results, such as the convergence of the Power Method to the dominant eigenvector and the fact that Kalman Filter equations are a specific case of Bayesian inference where distributions remain Gaussian.
While the current scope focuses heavily on unsupervised methods, inference, and learning, the author intends for this to be a "living" document. Hosted on GitHub, the project encourages community contributions to expand into modern topics like normalizing flows, diffusion models, and deep reinforcement learning.
Summary updated