PadhaikoAll subjects

Machine Learning Fundamentals (part 1: 4.1–4.4)

Artificial Intelligence (ENCT 351)

Open in the Padhaiko app

4.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:

The Four Pillars of Machine Learning
PillarCore Mathematical FocusRole in Machine Learning
1. Data & Linear AlgebraVectors, matrices, inner products, projections, SVD, eigenvaluesRepresents datasets as feature matrices and transforms high-dimensional features
2. Model (Analytic Geometry & Functions)Hypothesis spaces, linear/nonlinear maps, kernels, basis functionsDefines how inputs map to predictions
3. Objective / Loss & OptimizationCalculus, gradients, Lagrange multipliers, convexity, gradient descentMeasures prediction error and searches for optimal parameters
4. Probability & Statistics (Learning / Generalization)Distributions, Bayes' rule, MLE, MAP, bias–varianceModels uncertainty and ensures learned models generalize to unseen test data

4.2 Review of mathematics for machine learning

Machine learning algorithms rely on three core branches of mathematics:

1. Linear Algebra

2. Vector Calculus

3. Probability and Information Theory

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.

Constrained Optimization

Convex Optimization

Definition

Convex Set and Convex Function

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 :

AspectGenerative ModelsDiscriminative Models
What it learnsJoint distribution Posterior directly or a decision boundary
Classification ruleApply Bayes' rule: Evaluate or
Can generate new ?Yes (can sample synthetic features)No
Data efficiency & accuracyWorks well with small data if model assumptions holdOften higher asymptotic accuracy with enough data (fewer assumptions on )
ExamplesNaive Bayes, Gaussian Discriminant Analysis, HMMsLogistic 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

4.4.4 Hyperparameters and validation sets

4.4.5 Estimators, bias and variance

Let be a point estimator of a true parameter/function .

Definition

Bias, Variance, and MSE Decomposition

where is irreducible noise. Increasing model complexity typically decreases bias while increasing variance.

4.4.6 Review of MLE and MAP and cross entropy

A zero-mean Gaussian prior on weights yields regularization; a Laplace prior yields regularization.

Worked Out Examples

Example 4.1

4.1 (6 marks)

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 ).
Answer:

is strictly convex () with exact minimum . Gradient descent yields and ().

Example 4.2

4.2 (6 marks)

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 .

Answer:

, while .

Example 4.3

4.3 (5 marks)

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:

Answer:

Average binary cross-entropy loss .

Exercises

Exercise: Foundations, Optimization, and ML Pipeline

Question 1

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 .

Answer:

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).

Question 2

Using Lagrange multipliers, minimize subject to the linear constraint .

Form the Lagrangian:

Set partial derivatives to zero:

  • .
  • .

Substitute into constraint :

Thus , , and minimum value .

Answer:

Minimum occurs at with minimum value .

Question 3

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.

Answer:

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.

Question 4

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:

Answer:

Expected MSE .

Question 5

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: .
Answer:

Minimizing cross-entropy equals minimizing negative log-likelihood (MLE). Average BCE loss nats.

← Knowledge Representation and Probabilistic ReasoningMachine Learning Fundamentals (part 2: 4.5–4.8) →