Machine Learning Fundamentals (part 1: 4.1–4.4)
Open in the Padhaiko app4.1 Foundations and four pillars of machine learning
Machine Learning (ML) studies computer algorithms that improve automatically through experience on a class of tasks measured by performance (Tom Mitchell). Rather than hard-coding rules, an ML system learns parameters from data.
The Four Pillars of Machine Learning
As framed in modern mathematical ML foundations (Deisenroth, Faisal, & Ong), machine learning rests on four interconnected pillars:
| Pillar | Core Mathematical Focus | Role in Machine Learning |
|---|---|---|
| 1. Data & Linear Algebra | Vectors, matrices, inner products, projections, SVD, eigenvalues | Represents datasets as feature matrices and transforms high-dimensional features |
| 2. Model (Analytic Geometry & Functions) | Hypothesis spaces, linear/nonlinear maps, kernels, basis functions | Defines how inputs map to predictions |
| 3. Objective / Loss & Optimization | Calculus, gradients, Lagrange multipliers, convexity, gradient descent | Measures prediction error and searches for optimal parameters |
| 4. Probability & Statistics (Learning / Generalization) | Distributions, Bayes' rule, MLE, MAP, bias–variance | Models uncertainty and ensures learned models generalize to unseen test data |
- Learning paradigms at a glance: Supervised (labelled pairs ), Unsupervised (unlabelled ), Semi-supervised (few labels + many unlabelled), and Reinforcement Learning (agent–environment rewards).
4.2 Review of mathematics for machine learning
Machine learning algorithms rely on three core branches of mathematics:
1. Linear Algebra
- Vectors and norms: Feature vector ; Euclidean norm ; norm .
- Matrices and projections: Dataset matrix ( samples, features). Inner product .
- Eigenvalues and SVD: Symmetric covariance matrix has orthogonal eigenvectors used in PCA; any matrix admits a Singular Value Decomposition .
2. Vector Calculus
- Gradient (): Vector of partial derivatives pointing in the direction of steepest ascent; points in the direction of steepest descent.
- Jacobian () and Hessian (): For vector-valued , . For scalar , the Hessian describes local curvature (positive definite indicates a strict local minimum).
- Chain rule: Backpropagation and gradient computation compose derivatives across layers: .
3. Probability and Information Theory
- Random variables, expectation, variance: , .
- Covariance matrix: .
- Entropy & KL divergence: Shannon entropy measures uncertainty; Kullback–Leibler (KL) divergence measures how much distribution differs from .
4.3 Continuation optimization; Unconstraint optimization, constraint optimization, convex optimization
Training an ML model means solving an optimization problem .
Continuous vs. Combinatorial & Unconstrained Optimization
In continuous optimization (the syllabus refers to this as continuation/continuous optimization), parameters vary smoothly over real space rather than discrete choices.
- Unconstrained optimization: .
- First-order necessary condition: at a smooth minimum , (stationary point).
- Second-order sufficient condition: and Hessian (positive definite).
- Gradient descent update: , where is the learning rate.
Constrained Optimization
- Lagrange multipliers (equality constraints): Introduce and form the Lagrangian , setting and .
- KKT (Karush–Kuhn–Tucker) conditions (inequality constraints): Generalize Lagrange multipliers with requiring:
- Primal feasibility (),
- Dual feasibility (),
- Complementary slackness (),
- Stationarity (). (Used centrally to derive Support Vector Machines!)
Convex Optimization
Convex Set and Convex Function
- A set is convex if for any and , .
- A function is convex if for all and :
For twice-differentiable , convexity holds iff the Hessian is positive semi-definite () everywhere.
Crucial property: In a convex optimization problem (minimizing a convex function over a convex set), every local minimum is a global minimum—guaranteeing that gradient descent finds the globally optimal solution (e.g., linear regression, logistic regression, SVM).
4.4 Review of machine learning pipeline
An end-to-end ML pipeline turns raw data into deployed predictions: Data Collection Preprocessing & Feature Engineering Train/Validation/Test Split Model Selection & Training Hyperparameter Tuning Evaluation & Deployment.
4.4.1 Model development: Generative versus discriminative
For classification into class given input features :
| Aspect | Generative Models | Discriminative Models |
|---|---|---|
| What it learns | Joint distribution | Posterior directly or a decision boundary |
| Classification rule | Apply Bayes' rule: | Evaluate or |
| Can generate new ? | Yes (can sample synthetic features) | No |
| Data efficiency & accuracy | Works well with small data if model assumptions hold | Often higher asymptotic accuracy with enough data (fewer assumptions on ) |
| Examples | Naive Bayes, Gaussian Discriminant Analysis, HMMs | Logistic Regression, SVM, Decision Trees, Neural Networks |
4.4.2 Learning algorithm
A learning algorithm takes training data , a hypothesis space , and an objective/loss function , and outputs the parameter vector minimizing empirical risk:
where is per-sample loss (e.g., squared error for regression, cross-entropy for classification) and is a regularization penalty. Optimization uses closed-form normal equations, Batch Gradient Descent, Stochastic Gradient Descent (SGD), or Mini-batch SGD / Adam.
4.4.3 Capacity, overfitting and underfitting
- Model capacity: The range of functions a model family can fit (controlled by polynomial degree, tree depth, number of neural weights).
- Underfitting (high bias): Capacity is too low to capture the underlying pattern; both training error and test error are high.
- Overfitting (high variance): Capacity is too high; the model memorizes training noise, giving very low training error but high test/generalization error.
- Regularization (e.g., weight decay , sparsity , early stopping, dropout) restricts effective capacity to prevent overfitting.
4.4.4 Hyperparameters and validation sets
- Parameters vs. Hyperparameters: Parameters () are learned automatically from training data; hyperparameters (learning rate , regularization strength , polynomial degree , tree depth) are set before training begins.
- Three-way split:
- Training set: fits model parameters.
- Validation set: tunes hyperparameters and selects the best model (never touch the test set for tuning!).
- Test set: used once at the end to give an unbiased estimate of generalization error.
- -fold Cross-Validation: When data is scarce, split training data into equal folds; train on folds and validate on the remaining fold, averaging validation scores across all runs.
4.4.5 Estimators, bias and variance
Let be a point estimator of a true parameter/function .
Bias, Variance, and MSE Decomposition
- Bias: . An estimator is unbiased if .
- Variance: , measuring sensitivity to fluctuations in the training sample.
- Bias–Variance Trade-off (MSE decomposition): For squared error, expected test error at decomposes into:
where is irreducible noise. Increasing model complexity typically decreases bias while increasing variance.
4.4.6 Review of MLE and MAP and cross entropy
- Maximum Likelihood Estimation (MLE): Choose that maximizes the probability (likelihood) of observing the training data:
- Maximum A Posteriori (MAP) Estimation: Incorporates a prior via Bayes' rule:
A zero-mean Gaussian prior on weights yields regularization; a Laplace prior yields regularization.
- Cross-Entropy Loss: For true distribution (one-hot label ) and predicted probability ():
- Binary cross-entropy: .
- Multi-class cross-entropy: . Minimizing cross-entropy is mathematically identical to maximizing the conditional log-likelihood (MLE)!
Worked Out Examples
4.1
Consider the unconstrained objective . Verify that is convex, find its exact global minimum, and perform two iterations of gradient descent starting at with learning rate .
Convexity and exact global minimum: Compute first and second derivatives:
Since everywhere, is strictly convex. Setting gives the unique global minimum (where ).
First gradient descent step ():
- Gradient: .
- Update: .
Second gradient descent step ():
- Gradient: .
- Update: .
- Objective value: (decreasing from toward ).
is strictly convex () with exact minimum . Gradient descent yields and ().
4.2
A coin is tossed times and lands heads times. Let . (a) Find the Maximum Likelihood Estimate . (b) Assuming a prior , find the MAP estimate .
Maximum Likelihood Estimate (MLE): The log-likelihood is . Setting :
MAP Estimate with prior:
Notice how the symmetric prior shrinks the estimate slightly from toward .
, while .
4.3
A binary classifier outputs predicted probabilities for sample (true label ) and for sample (true label ). Compute the average binary cross-entropy loss (using natural logarithm ).
Sample 1 ():
Sample 2 ():
Average BCE loss:
Average binary cross-entropy loss .
Exercises
Exercise: Foundations, Optimization, and ML Pipeline
State the four mathematical pillars of machine learning and distinguish between generative and discriminative models with examples.
Four pillars: Data/Linear Algebra (feature matrices, projections, decompositions), Model/Analytic Geometry (hypothesis functions), Optimization (loss minimization via gradients/convexity), and Probability/Statistics (uncertainty, MLE/MAP, generalization).
Generative vs. Discriminative: Generative models learn (e.g., Naive Bayes) and can sample new inputs; discriminative models learn or the decision boundary directly (e.g., Logistic Regression, SVM) without modelling .
The four pillars are linear algebra, model geometry, optimization, and probability/statistics. Generative models learn (e.g., Naive Bayes), while discriminative models learn directly (e.g., Logistic Regression).
Using Lagrange multipliers, minimize subject to the linear constraint .
Form the Lagrangian:
Set partial derivatives to zero:
- .
- .
Substitute into constraint :
Thus , , and minimum value .
Minimum occurs at with minimum value .
Differentiate between underfitting and overfitting using model capacity, training error, validation error, bias, and variance. How do validation sets and -fold cross-validation help choose hyperparameters?
Underfitting vs. Overfitting: Underfitting happens when model capacity is too low (high bias, low variance), causing high training error and high validation error. Overfitting happens when capacity is too high (low bias, high variance), giving very low training error but high validation error.
Role of validation / -fold CV: Parameters are learned on the training set, while hyperparameters (e.g., , depth) are compared on a separate validation set (or averaged over cross-validation folds) so the test set remains untouched for final unbiased evaluation.
Underfitting has high bias and high train/validation error; overfitting has high variance, low train error, and high validation error. Validation sets and -fold CV tune hyperparameters without leaking the test set.
At a test point , a regression model has , , and irreducible noise variance . Calculate the expected Mean Squared Error (MSE) at .
Use the bias–variance decomposition:
Substitute values:
Expected MSE .
Explain why minimizing cross-entropy loss is equivalent to Maximum Likelihood Estimation (MLE), and calculate the average binary cross-entropy loss (in nats) for predictions with true labels .
Equivalence: For Bernoulli labels with , the dataset likelihood is . Taking the negative log-likelihood gives , which is exact binary cross-entropy.
Calculation:
- Sample 1 (): .
- Sample 2 (): .
- Average: .
Minimizing cross-entropy equals minimizing negative log-likelihood (MLE). Average BCE loss nats.