01_Foundations

Module 0 — Foundations of Machine Learning

Source: Lec 2 — Introduction to Machine Learning.

Notation used throughout the course. A data point is ${\vec{X}}_i=[x_{i1},\dots ,x_{im}{]}^T\in {\mathbb{R}}^m$ ($m$ features). There are $n$ training instances. A class label is $y_i$. Test point: ${\vec{X}}_0$.

---

C1. What Is Machine Learning? (Samuel, Mitchell, the three paradigms)

Intuition

A normal program = rules written by a human. A learning program = rules extracted from examples. Think of a child learning to recognise dogs: nobody gives the child a definition; the child sees many dogs and “just gets it”. Machine learning is that, with performance you can measure.

Formal definitions

• Samuel (1959): ML is the field of study that gives computers the ability to learn without being explicitly programmed.
• Mitchell (1997): A program learns from experience $E$ with respect to a task $T$ and performance measure $P$ if its performance on $T$, measured by $P$, improves with experience $E$.
• Paradigms: Supervised (labelled data), Unsupervised (no labels), Reinforcement (reward signal; mentioned, not studied in the course).

Mathematical formulation

Let $P(E)$ denote performance after seeing experience $E$. Learning with respect to $(T,P)$ means: for experiences $E_1\subset E_2$, $P_T(E_2)\ge P_T(E_1)\text{(typically strictly, and measured on data not used for training).}$

Derivation / reasoning

Why must $P$ be measured on unseen data? If $P$ is measured on the training set, a lookup table achieves perfect $P$ with zero “understanding”. Mitchell’s definition is only meaningful when $P$ reflects performance on the task in general, i.e. on new instances. This is the seed of the whole generalisation / overfitting theme (C7, C13).

Key insights

1. Always identify the triple $(T,P,E)$ before choosing an algorithm.
2. $E$ determines the paradigm: labelled → supervised; unlabelled → unsupervised.
3. “Improves with experience” is a testable, quantitative statement.

Worked examples

Example 1 — Very Easy

• Problem: An email program learns to flag spam by watching which emails the user marks as spam. Identify $T$, $P$, $E$.
• Asked: The three components.
• Concept: Mitchell’s definition.
• Approach: Task = what the program does; experience = what it watches; performance = how success is scored.
• Solution: $T$ = classify incoming emails as spam / not spam. $E$ = a database of emails with the user’s spam/not-spam labels. $P$ = fraction of new emails classified correctly.
• Final answer: $T$: spam classification; $E$: labelled emails; $P$: classification accuracy on new emails.
• Key lesson: The three parts are three different objects; don’t merge them.

Example 2 — Easy

• Problem: Label each as supervised, unsupervised or reinforcement: (a) predicting house prices from past sales with prices; (b) grouping customers by purchase behaviour with no labels; (c) a robot learning to walk by receiving $+1$ when it moves forward and $-1$ when it falls.
• Asked: Paradigm for each.
• Concept: Paradigms are defined by the type of feedback.
• Approach: Ask “what feedback does the learner receive?”
• Solution: (a) Each training house has its price (the target) → supervised (regression). (b) No target → unsupervised (clustering). (c) Feedback is a delayed scalar reward, not a correct answer → reinforcement.
• Final answer: (a) supervised, (b) unsupervised, (c) reinforcement.
• Key lesson: Supervision = a correct answer per example; reward is weaker.

Example 3 — Moderate

• Problem: A program for recognising handwritten digits is evaluated on a fixed test set of 1000 images. After training on $E_1$=500 images its test accuracy is 71 %; after $E_2$=2000 images it is 88 %; after $E_3$=8000 images it is 87.5 %. Does the program “learn” per Mitchell? Over which range?
• Asked: Whether $P$ improves with $E$.
• Concept: Mitchell’s definition (improvement, not necessarily monotone forever).
• Approach: Compare $P$ at successive experience levels.
• Solution: $P(E_1)=0.71$, $P(E_2)=0.88$, $P(E_3)=0.875$. $P(E_2)-P(E_1)=0.17>0$: improvement. $P(E_3)-P(E_2)=-0.005$: tiny decline, within the statistical noise of a 1000-image test set (one standard error is about $\sqrt{0.88\cdot 0.12/1000}\approx 0.010$, bigger than 0.005).
• Final answer: Yes, it learns from 500→2000 images; from 2000→8000 the change is statistically indistinguishable from zero (performance has plateaued).
• Key lesson: Learning curves saturate; compare differences with sampling noise.

Example 4 — Hard

• Problem: Two programs are trained on the same 1000 labelled digit images. Program A stores every training image and its label and answers a test image with the label of an identical stored image if one exists, otherwise guesses “0”. Program B fits a smooth classifier. Results: A: training accuracy 100 %, test accuracy 10 %. B: training 94 %, test 92 %. Which has learned in Mitchell’s sense, and what should $P$ be?
• Asked: Which program learned; what must $P$ measure.
• Concept: $P$ must be measured on unseen instances of $T$.
• Approach: Evaluate the two programs under both choices of $P$.
• Solution: (i) If $P$ = training accuracy: A scores 100 %, B 94 % → A looks better — absurd, since A does not generalise. (ii) If $P$ = test accuracy: A = 10 % (equal to a random guess among 10 digits), B = 92 %. Now, does A’s test accuracy improve with experience? Only if a test image happens to equal a stored one; for new handwriting, no. B improves with experience.
• Final answer: B has learned; the correct $P$ is accuracy on unseen instances.
• Key lesson: Memorisation is not learning; generalisation is the point.

Example 5 — Very Hard

• Problem: A learner is given experience sets $E$ of size $n$ and is evaluated by $P$ = accuracy on a fixed test set of 200 points. Three programs give $P(n)$ for $n=100,400,1600$: Program X: $0.60,0.72,0.80$. Program Y: $0.70,0.70,0.70$. Program Z: $0.55,0.60,0.58$. Z’s test set accidentally contains 20 points that also appear in the training sets once $n=400$. (a) Which programs learn? (b) What is Z’s accuracy on the non-leaked 180 test points at $n=400$, assuming Z gets all 20 leaked points right?
• Asked: Learning judgement and corrected accuracy.
• Concept: Mitchell’s definition + leakage invalidates $P$.
• Approach: (a) look at trend; (b) remove leaked points from numerator and denominator.
• Solution: (a) X: strictly increasing → learns. Y: constant → does not improve → not learning (a fixed rule). Z: noisy; ignore leakage for now: $0.55\to 0.60\to 0.58$, non-monotone. (b) Correct answers at $n=400$: $0.60\times 200=120$. Subtract the 20 leaked (all correct): $120-20=100$ correct among $180$ clean points $\Rightarrow 100/180=0.5556$. At $n=100$ no leakage: $0.55$. So the clean accuracy goes $0.55\to 0.556$: practically no improvement; Z’s apparent gain was leakage.
• Final answer: X learns; Y and Z do not (Z’s clean accuracy $\approx 0.556$ vs $0.55$).
• Key lesson: A test set contaminated by training data silently inflates $P$ — always check train/test disjointness.

Common mistakes

• Treating training accuracy as performance.
• Saying “learning requires labels” (unsupervised learning has none).

Exam traps

• “Define ML” questions: give both Samuel and Mitchell; Mitchell is the formal one.
• The definition says improves; a constant program does not learn.

Connections

Evaluation (C11–C13), overfitting (C7), supervised/unsupervised split (C2–C3).

Mastery checklist

• State Samuel’s and Mitchell’s definitions.
• Identify $(T,P,E)$ for any story.
• Explain why $P$ must be on unseen data.

---

C2. Supervised Learning: Classification vs Regression

Intuition

Supervised learning = learning with an answer key. You get $(X_i,y_i)$ pairs and must predict $y$ for new $X$. If the answer is a category (spam / not spam) it is classification; if it is a number (price) it is regression.

Formal definition

Given training data $\{({\vec{X}}_i,y_i){\}}_{i=1}^n$, ${\vec{X}}_i\in {\mathbb{R}}^m$, learn a function $h$ (the inferred function) so that $h({\vec{X}}_0)$ estimates the target of a new ${\vec{X}}_0\in {\mathbb{R}}^m$.

• Classification: $y_i\in \{1,\dots ,c\}$ (discrete).
• Regression: $y_i\in \mathbb{R}$ (continuous).

Mathematical formulation

Empirical risk for loss $\ell$: $\hat{R}(h)=\frac{1}{n}{\sum }_{i=1}^n\ell (h({\vec{X}}_i),y_i),$ with ${\ell }_{0\text{-}1}(\hat{y},y)=1[\hat{y}\ne y]$ for classification and ${\ell }_{sq}(\hat{y},y)=(\hat{y}-y{)}^2$ for regression.

Derivation

Why not just minimise $\hat{R}$ to zero? A lookup table does it. We want small true risk $R(h)=\mathbb{E}[\ell (h(X),y)]$; $\hat{R}$ is only an estimate, so we evaluate on held-out data.

Key insights

• Same input, different target type → different algorithm family.
• Every classifier in this course (trees, Bayes, kNN, logistic, SVM, perceptron, NN) fits this template.

Worked examples

Example 1 — Very Easy

• Problem: Classify as classification or regression: (a) predict a patient’s blood sugar level; (b) predict whether a tumour is malignant.
• Asked: Task type.
• Concept: Target type.
• Approach: Discrete vs continuous target.
• Solution: (a) blood sugar is a real number → regression. (b) malignant/benign is two categories → classification.
• Final answer: (a) regression; (b) classification.
• Key lesson: Look at $y$, not $X$.

Example 2 — Easy

• Problem: The data table below has features (age, income) and target “buys” ∈ {yes,no}: $(25,30)\to$no, $(40,80)\to$yes, $(35,60)\to$yes. State $n$, $m$, ${\vec{X}}_2$, $y_2$.
• Asked: Notation.
• Concept: Training-set notation.
• Approach: Count rows and columns.
• Solution: Rows = 3 → $n=3$. Feature columns = 2 → $m=2$. ${\vec{X}}_2=[40,80{]}^T$, $y_2=\text{yes}$.
• Final answer: $n=3,m=2,{\vec{X}}_2=[40,80{]}^T,y_2=\text{yes}$.
• Key lesson: $m$ counts features, not including the target.

Example 3 — Moderate

• Problem: Data $(x,y)$: $(0,1),(1,3),(2,5),(3,8)$. Hypothesis $h(x)=2x+1$. Compute the empirical squared loss ${\hat{R}}_{sq}$ and the number of points a rounding classifier ”$h(x)$ rounded equals $y$” gets right.
• Asked: ${\hat{R}}_{sq}(h)$.
• Concept: Empirical risk.
• Approach: Compute predictions and residuals.
• Solution: $h(0)=1,h(1)=3,h(2)=5,h(3)=7$. Residuals $y-h$: $0,0,0,1$. Squared: $0,0,0,1$. ${\hat{R}}_{sq}=\frac{1}{4}(0+0+0+1)=0.25$. Rounding matches: first three equal, fourth $7\ne 8$ → 3 correct of 4.
• Final answer: ${\hat{R}}_{sq}=0.25$; 3/4 correct.
• Key lesson: The same predictions can be scored by different losses.

Example 4 — Hard

• Problem: House prices (in lakhs): sizes $50,60,70,80,90$; prices $30,34,41,45,50$. A manager wants “cheap” ($<40$) vs “expensive”. Option 1: regress price, then threshold at 40. Option 2: train a classifier directly. The regressor is $\hat{p}(s)=0.5s+5$. Compute the threshold classifier’s accuracy and decide which size $s^{\ast }$ is the decision boundary.
• Asked: Accuracy and boundary.
• Concept: A regressor induces a classifier.
• Approach: Predict, threshold, compare with true labels.
• Solution: Predictions: $s=50\to 30$; $60\to 35$; $70\to 40$; $80\to 45$; $90\to 50$. True labels (price $<40$ → cheap): $30$ C, $34$ C, $41$ E, $45$ E, $50$ E. Predicted labels with rule “predicted $<40$ is cheap”: $30$ C, $35$ C, $40$ E (not $<40$), $45$ E, $50$ E → all five match → accuracy $5/5$. Boundary: $0.5s+5=40\Rightarrow s^{\ast }=70$ (ties at 70 go to expensive).
• Final answer: Accuracy 100 %, boundary $s^{\ast }=70$.
• Key lesson: A regression model contains classification information, but the tie-breaking at the boundary must be fixed.

Example 5 — Very Hard

• Problem: A “lookup” learner stores training pairs; for a test $x$ already stored it returns the stored $y$, otherwise it returns the majority training label. Training set: $(1,A),(2,A),(3,A),(4,B)$. Test set: $(1,A),(5,B),(6,B),(7,A)$. Compute training 0-1 risk, test 0-1 risk, and compare to the constant predictor “A”.
• Asked: Three error rates.
• Concept: Generalisation gap.
• Approach: Majority label first, then evaluate each point.
• Solution: Majority label = A (3 vs 1). Training: every stored point is returned exactly → 0 errors → risk 0. Test: $x=1$ stored → A, correct. $x=5$: unseen → A, true B → error. $x=6$: A, true B → error. $x=7$: A, true A → correct. Test risk $=2/4=0.5$. Constant “A” predictor: test predictions all A: correct on $(1,A)$ and $(7,A)$ → 2 correct, risk 0.5. Training risk of constant A: 1 error of 4 → 0.25.
• Final answer: Lookup: train 0, test 0.5. Constant A: train 0.25, test 0.5. The lookup learner shows a gap of 0.5 and no test advantage.
• Key lesson: Zero training error can coexist with no generalisation; the gap is what matters.

Common mistakes

• Using the wrong loss (squared error on categorical labels).
• Counting the target as a feature.

Exam traps

• Binary labels coded $\{0,1\}$ vs $\{-1,+1\}$ change formulas (logistic uses $\{0,1\}$; SVM and perceptron use $\{-1,+1\}$).
• “Logistic regression” is a classifier.

Connections

Every later module. Regression → C26; classification → C4–C25, C27–C34, C49+.

Mastery checklist

• Define classification and regression.
• Write the empirical risk for 0-1 and squared loss.
• Explain train vs test risk.

---

C3. Unsupervised Learning & Feature Engineering

Intuition

No answer key. Two things you can still do: group similar items (clustering) or describe how the data is spread (density estimation). Separately, you can clean up the features: keep the useful ones (selection) or build new better ones (extraction).

Formal definitions

• Clustering: partition data into groups; high similarity within, low across.
• Density estimation: estimate the distribution $p(\vec{X})$.
• Feature selection (supervised): score each feature using class labels (e.g. ${\chi }^2$ statistic, information gain), keep top-scoring ones.
• Feature extraction (unsupervised): build new features from old ones without labels (e.g. PCA, entropy-based methods).

Mathematical formulation

${\chi }^2$ for a feature-vs-class contingency table with observed $O_{ij}$ and expected $E_{ij}=\frac{({\text{row}}_i)({\text{col}}_j)}{N}$: ${\chi }^2={\sum }_{i,j}\frac{(O_{ij}-E_{ij}{)}^2}{E_{ij}}.$ Information gain of a feature $f$ is defined in C4.

Derivation

Expected counts $E_{ij}$ are what we would see if feature and class were independent: $P({\text{row}}_i,{\text{col}}_j)=P({\text{row}}_i)P({\text{col}}_j)\Rightarrow E_{ij}=N\cdot \frac{r_i}{N}\cdot \frac{c_j}{N}=\frac{r_i{c}_j}{N}$. Large deviation from independence → feature carries information about class → high score.

Key insights

• Selection keeps original features (interpretable); extraction creates new ones.
• Supervised ⇒ selection (uses labels); unsupervised ⇒ extraction (does not).
• Variance is not relevance (see Example 5).

Worked examples

Example 1 — Very Easy

• Problem: Is PCA feature selection or feature extraction? Is it supervised?
• Asked: Category.
• Concept: Taxonomy.
• Approach: PCA builds new axes and ignores labels.
• Solution: New features → extraction; no labels → unsupervised.
• Final answer: Unsupervised feature extraction.
• Key lesson: Selection = keep; extraction = build.

Example 2 — Easy

• Problem: Information-gain scores: outlook 0.247, temperature 0.029, humidity 0.152, wind 0.048. Select the top 2 features.
• Asked: Top-2.
• Concept: Score-based selection.
• Approach: Sort descending.
• Solution: $0.247>0.152>0.048>0.029$. Top two: outlook, humidity.
• Final answer: {outlook, humidity}.
• Key lesson: Selection is just ranking by a score.

Example 3 — Moderate

• Problem: Word “free” present/absent vs spam/ham: present&spam=30, present&ham=10, absent&spam=20, absent&ham=40. Compute ${\chi }^2$.
• Asked: ${\chi }^2$.
• Concept: ${\chi }^2$ feature score.
• Approach: Row/column totals → expected counts → sum.
• Solution: Row totals: present $=40$, absent $=60$. Column totals: spam $=50$, ham $=50$; $N=100$. $E_{11}=40\cdot 50/100=20$, $E_{12}=20$, $E_{21}=60\cdot 50/100=30$, $E_{22}=30$. Deviations: $30-20=10,10-20=-10,20-30=-10,40-30=10$. ${\chi }^2=\frac{100}{20}+\frac{100}{20}+\frac{100}{30}+\frac{100}{30}=5+5+3.333+3.333=16.667$.
• Final answer: ${\chi }^2\approx 16.67$ (strongly dependent on class; high score).
• Key lesson: Expected counts come from independence.

Example 4 — Hard

• Problem: Features $x_1$ and $x_2$ are exact duplicates and both perfectly predict the class; $x_3$ is pure noise. A selector picks the top-2 by information gain. A PCA extractor keeps 1 component. Compare what each keeps. Four points: $(x_1,x_2,x_3)$ = $(0,0,5)$ class 0; $(0,0,-5)$ class 0; $(1,1,5)$ class 1; $(1,1,-5)$ class 1.
• Asked: Which representation is better and why.
• Concept: Redundancy.
• Approach: Compute IG per feature; compute covariance.
• Solution: Class entropy $=1$ bit. Split on $x_1$: $x_1=0\to$ both class 0 (entropy 0); $x_1=1\to$ both class 1 (entropy 0). IG$(x_1)=1-0=1$; same for $x_2$. For $x_3$: $x_3=5\to$ one class 0, one class 1 (entropy 1); same for $-5$; IG$(x_3)=1-1=0$. Selector keeps $\{x_1,x_2\}$ — redundant, same information twice. PCA: centred data $x_1,x_2\in \{\pm 0.5\}$ with variance $0.25$ each and covariance $0.25$; $x_3$ has variance $25$ and zero covariance with the others. The largest variance direction is $x_3$ (variance 25) — pure noise! PCA with one component keeps noise and discards the class information.
• Final answer: Selection keeps two redundant but relevant features; one-component PCA keeps only the noise axis. Here selection wins.
• Key lesson: Unsupervised extraction maximises variance, not relevance.

Example 5 — Very Hard

• Problem: Points (class): $(-10,-1)$−, $(10,-1)$−, $(-10,1)$+, $(10,1)$+. (a) Compute PCA’s first direction and the 1-D projected class separation. (b) Compute the information gain of splitting on sign of $x_1$ and on sign of $x_2$. (c) Which is better and what is the lesson?
• Asked: PCA direction, IGs, conclusion.
• Concept: Variance ≠ discriminability.
• Approach: Covariance matrix, eigen, project.
• Solution: (a) Means: ${\bar{x}}_1=0,{\bar{x}}_2=0$. $\mathrm{Var}(x_1)=\frac{1}{4}(100\cdot 4)=100$; $\mathrm{Var}(x_2)=\frac{1}{4}(1\cdot 4)=1$; $\mathrm{Cov}=\frac{1}{4}[(-10)(-1)+(10)(-1)+(-10)(1)+(10)(1)]=\frac{1}{4}[10-10-10+10]=0$. $S=\mathrm{diag}(100,1)$, eigenvalues $100,1$; first PC $=[1,0{]}^T$. Projection onto it gives coordinates $-10,10,-10,10$ for classes $-,-,+,+$: both classes occupy both values → total overlap. (b) Splitting on $x_1$: groups $\{(-10,-1)-,(-10,1)+\}$ and $\{(10,-1)-,(10,1)+\}$, each entropy 1 → IG$=1-1=0$. Splitting on $x_2$: groups all − and all + → entropy 0 → IG$=1$. (c) PCA direction has IG 0; the low-variance axis has IG 1.
• Final answer: PCA’s direction is $[1,0{]}^T$ (no class information); $x_2$ separates perfectly.
• Key lesson: Use supervised selection (or supervised projection such as Fisher’s discriminant, C48) when classification is the goal.

Common mistakes

• Believing the highest-variance feature is the most useful.
• Mixing up “selection” and “extraction”.

Exam traps

• ${\chi }^2$ and IG both need labels → supervised.
• Feature extraction may be applied before a supervised learner but is itself unsupervised.

Connections

IG (C4), PCA (C43–C48), clustering (C35–C42).

Mastery checklist

• Distinguish selection vs extraction and supervised vs unsupervised.
• Compute ${\chi }^2$ from a $2\times 2$ table.
• Explain why PCA can discard class-relevant directions.