Introduction to machine learning
Introduction to machine learning: formal problem statement, losses and risk, empirical risk minimisation, types of learning, basic assumptions and how an engineer chooses and evaluates models.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Machine learning (ML) gives engineers ways to write systems that learn from data instead of being fully hand-coded. In computer engineering you will use ML to build prediction systems (fault detection, sensor-data prediction), classification systems (image or packet classification) and unsupervised analysis (clustering logs); understanding the formal problem, assumptions and how learning is evaluated helps you design, debug and choose models for real systems.
Key ideas
i.i.d. assumption — the training examples are assumed to be independent and identically distributed (i.i.d.) samples from an unknown joint distribution P(X, Y). This is usually stated as an assumption needed for theoretical guarantees like convergence of empirical quantities to their population counterparts.
Hypothesis space — denote by H the set of candidate functions (models) h: X → Y from which the learner chooses. H can be finite, countable or infinite (example: linear functions, neural networks).
Loss function — a function L(y_pred, y_true) ≥ 0 that measures penalty for predicting y_pred when the true label is y_true. Common examples: 0–1 loss for classification L(ŷ,y)=1 if ŷ≠y else 0; squared loss for regression L(ŷ,y)=(ŷ−y)^2.
Expected risk (true risk) — the population average loss of hypothesis h under P: R(h) = E_{(X,Y)~P}[L(h(X), Y)]. This is the quantity we would like to minimise but cannot compute because P is unknown.
Empirical risk — the average loss on the training set: R_emp(h) = (1/n) Σ_{i=1}^n L(h(x_i), y_i). This is computable from data.
Empirical Risk Minimisation (ERM) — the principle “choose h ∈ H that minimises R_emp(h)”. Formally, h_hat = argmin_{h∈H} R_emp(h). ERM is the basic learning rule; it needs regularisation or model selection to avoid overfitting.
Statement connecting empirical and expected risk (asymptotic and finite-sample connection): Under the i.i.d. assumption and if L has finite expectation (e.g., bounded), by the Law of Large Numbers R_emp(h) → R(h) as n → ∞ for any fixed h (pointwise convergence). Also, for a finite H, finite-sample uniform convergence bounds hold: e.g., if L ∈ [0,1], with probability at least 1−δ, sup_{h∈H} |R(h) − R_emp(h)| ≤ sqrt((1/(2n)) ln(2|H|/δ)). (The stronger uniform convergence for infinite H requires capacity measures like VC dimension — see later topics.)
Overfitting and underfitting — if a chosen h fits noise in the training data its training loss is low but true risk is high: overfitting. If h is too simple to capture the pattern, both training and true risk remain high: underfitting. Balancing complexity and fit is central to learning (connected to regularisation and model selection in later topics).
Types of learning (short definitions) — supervised learning: learn from labelled data (X,Y); unsupervised learning: find structure without labels (e.g., clustering); semi-supervised: mix of labelled and unlabelled; online learning: data arrives sequentially and model updates incrementally; reinforcement learning: agent learns by interacting and receiving rewards (see the later topic on reinforcement learning). These categories determine the loss, evaluation and algorithms used.
Model selection and validation — because ERM alone can overfit, we split data conceptually into training and validation (and test) sets, and use criteria like validation loss to select model complexity or hyperparameters. Cross-validation is the standard method (detailed in the Cross-validation topic).
What to draw (diagram): draw a flow from "Data (X,Y)" → "Choose H (hypothesis space)" → "Empirical risk calculation" → "Optimisation (find h minimizing empirical risk)" → "Validation/Test evaluation". Label arrows with 'fit' and 'evaluate', and annotate that P(X,Y) is unknown and i.i.d. is assumed.
Derivation universities ask for (example): show E[R_emp(h)] = R(h) under i.i.d. assumption:
- Write R_emp(h) = (1/n) Σ_{i=1}^n L(h(x_i), y_i).
- Take expectation over the random draw of D: E_D[R_emp(h)] = (1/n) Σ_{i=1}^n E_{(X_i,Y_i)}[L(h(X_i), Y_i)].
- By identical distribution each term equals E_{(X,Y)}[L(h(X),Y)] = R(h).
- Therefore E_D[R_emp(h)] = R(h). (This shows empirical risk is an unbiased estimator of true risk for fixed h.)
Assumptions required for the above: examples (X_i,Y_i) are independent and identically distributed from P(X,Y); and expectation exists (loss finite). State these when you use the result.
Formulas
D = {(x_i, y_i)}_{i=1}^n — training dataset, x_i ∈ X, y_i ∈ Y; units: problem dependent (e.g., volts, bytes) for features; labels have units in regression and are dimensionless for classification; applies always.
R(h) = E_{(X,Y)~P}[L(h(X), Y)] — expected (true) risk; units: same as loss; applies when P is the data-generating distribution (unknown).
R_emp(h) = (1/n) Σ_{i=1}^n L(h(x_i), y_i) — empirical risk (training loss average); units: same as loss; applies to given dataset D.
h_hat = argmin_{h ∈ H} R_emp(h) — ERM rule; applies when selecting model from hypothesis space H.
Bias-Variance is discussed in a later topic; here note the qualitative relation: model complexity ↑ → variance ↑ and bias ↓ (and vice versa).
0-1 loss: L(ŷ,y) = 1 if ŷ ≠ y else 0 — units: dimensionless; used for classification error rate.
squared loss: L(ŷ,y) = (ŷ − y)^2 — units: square of target units; used for regression.
Worked examples
Example 1 — empirical risk comparison (classification with 0–1 loss): Dataset D (n = 5): x ignored, labels y = {1, 0, 1, 1, 0}. Two candidate hypotheses give predictions on these 5 examples as: h1 predictions = {1, 1, 1, 1, 0} h2 predictions = {0, 0, 1, 1, 0}
Step 1: Use 0–1 loss. Compute R_emp(h) = (1/5) count(mismatches). For h1: mismatches at example 2 only → count = 1 → R_emp(h1) = 1/5 = 0.2. For h2: mismatches at examples 1 only → count = 1 → R_emp(h2) = 1/5 = 0.2.
Final answer: Both have the same empirical risk 0.2; if tie-break needed one should use a validation set or prefer the simpler model. Empirical risk: h1 = 0.2, h2 = 0.2.
Example 2 — empirical risk for regression (squared loss): Dataset D (n = 4): (x, y) pairs: (0, 1.0), (1, 2.0), (2, 2.5), (3, 4.0). Two candidate constant predictors: hA(x)=2.0 and hB(x)=mean(y).
Step 1: compute mean(y) = (1.0+2.0+2.5+4.0)/4 = 9.5/4 = 2.375.
Step 2: compute R_emp for squared loss. For hA: errors = (2.0−1.0)^2, (2.0−2.0)^2, (2.0−2.5)^2, (2.0−4.0)^2 = 1.0, 0.0, 0.25, 4.0; sum = 5.25; R_emp(hA)=5.25/4=1.3125. For hB: errors = (2.375−1.0)^2, (2.375−2.0)^2, (2.375−2.5)^2, (2.375−4.0)^2 = 1.890625, 0.140625, 0.015625, 2.640625; sum = 4.6875; R_emp(hB)=4.6875/4=1.171875.
Final answer: hB (mean predictor) has lower empirical risk: 1.171875 vs 1.3125. (Explanation: mean minimises squared loss on the dataset — a standard fact used in regression.)
Common mistakes
- Not specifying the loss function before computing risk; risk depends on the loss chosen (0–1 loss vs squared loss give different orderings).
- Using accuracy/0–1 loss blindly in class-imbalanced problems (precision/recall are better metrics; covered in later topics).
- Treating training error as a reliable estimate of generalisation error without qualifying sample size, hypothesis complexity or giving confidence bounds.
For your exam
Typical question types:
- Definitions: define empirical risk, expected risk, ERM, i.i.d. Provide short, precise statements and assumptions.
- Short notes: explain overfitting vs underfitting and how ERM can lead to overfitting; describe types of learning (supervised/unsupervised/etc.) with examples in engineering.
- Derivations: show E[R_emp(h)] = R(h) (give the steps and assumptions). Explain why law of large numbers justifies ERM asymptotically.
- Numericals: compute empirical risk for given small datasets and candidate hypotheses using specified loss; compare and choose.
- Diagrams: draw the learning pipeline and label data, hypothesis space, ERM step and validation.
What full-marks answers must include:
- Precise definitions with bold terms (dataset, hypothesis space, loss, empirical/expected risk).
- Clear statement of assumptions (i.i.d., loss finite/bounded when used).
- Step-by-step derivations (e.g., expectation of empirical risk) and final conclusion.
- For numerical problems: show all steps, compute sums/averages with units or state dimensionless, and give the final answer in bold.
Quick check
- Define empirical risk in one formula.
- State the i.i.d. assumption in one sentence.
- For 3 labelled examples with labels {0,1,1} and a hypothesis predicting {1,1,1}, what is the empirical risk under 0–1 loss?
Answers: 1) R_emp(h) = (1/n) Σ_{i=1}^n L(h(x_i), y_i). 2) The training examples (X_i,Y_i) are independent and identically distributed samples from the same unknown distribution P(X,Y). 3) Empirical risk = 1/3 (one mismatch out of three).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?