MACHINE

LEARNING
Comprehensive Study Notes

TOM M. MITCHELL
Machine Learning -- Tom M. Mitchell 1

TABLE OF CONTENTS
1 Supervised Learning: Linear Models & SVM
1.1 Linear Models & Regularisation
1.2 SVM Definition & Motivation
1.3 Linear Separators & Margin
1.4 Why Maximum Margin -- VC Theory
1.5 Hard-Margin SVM (Primal QP)
1.6 Dual Formulation & Lagrange Multipliers
1.7 Soft-Margin SVM & Slack Variables
1.8 Feature Spaces
1.9 The Kernel Trick
1.10 Mercer's Theorem & Kernel Functions
1.11 Hard vs Soft Comparison
1.12 Extensions & Applications
2 Decision Trees
2.1 Introduction & ID3
2.2 Entropy & Information Gain
2.3 Gini Impurity
2.4 Worked Example -- PlayTennis
2.5 Overfitting & Pruning
3 Random Forests
3.1 Ensemble Learning Theory
3.2 Bagging
3.3 Random Feature Selection
3.4 OOB Error
3.5 Feature Importance
3.6 Worked Examples
4 Logistic Regression
4.1 Sigmoid Function
4.2 Logit Derivation
4.3 Cross-Entropy Loss
4.4 Multiclass Extensions
4.5 Regularisation
5 K-Means Clustering
5.1 Theory & Objective
5.2 Algorithm
5.3 K-Means++ Initialisation
5.4 Convergence & Complexity
5.5 Worked Examples
5.6 Elbow Method & K-Medoids
6 Hierarchical Clustering & Association Rules
6.1 Agglomerative & Divisive
6.2 Linkage Criteria
6.3 Dendrogram Interpretation
Machine Learning -- Tom M. Mitchell 2

6.4 Association Rule Mining

6.5 Apriori Algorithm
7 Principal Component Analysis
7.1 Motivation & Geometry
7.2 Covariance & Eigendecomposition
7.3 Step-by-Step Procedure
7.4 Explained Variance
7.5 Worked Examples
8 Independent Component Analysis (ICA)
8.1 Cocktail Party Problem
8.2 ICA Assumptions
8.3 Non-Gaussianity & Kurtosis
8.4 Ambiguities
8.5 FastICA Algorithm
8.6 ICA vs PCA
Machine Learning -- Tom M. Mitchell 3

CHAPTER 1

Linear Models & SVM

This chapter introduces the foundations of supervised learning -- from linear regression to the
mathematical elegance of Support Vector Machines.

1.1 Linear Models -- Theory

A linear model predicts a continuous output by computing a weighted sum of the input features plus
a scalar bias term. It is the simplest and most interpretable family of machine learning models, and
forms the foundation for neural networks and SVMs. The hypothesis function maps an
n-dimensional input vector x to a scalar prediction y. The model has n+1 parameters: weight vector
w and bias b.
Linear Prediction: y = wT · x + b = w0 + w1x1 + w2x2 + ... + wnxn
MSE Loss: L(w) = (1/N) · SUM (yi - y^i)2
Gradient of MSE: dL/dw = (2/N) · XT · (Xw - y)
Gradient Descent: w := w - alpha · dL/dw
L2 (Ridge): L_reg = L(w) + lambda||w||2
L1 (Lasso): L_reg = L(w) + lambda||w||1

Regularisation Summary
Method Penalty Effect Best For

Ridge (L2) lambda||w||<super>2</super>

Shrinks all weights smoothly; no exact zeros
All features relevant

Lasso (L1) lambda||w||₁

Drives irrelevant weights to zero Feature selection

Elastic Net L1 + L2 Combines both; handles correlated features

General purpose

1.2 What is a Support Vector Machine?

An SVM is a system for efficiently training linear learning machines in kernel-induced feature
spaces, while respecting the insights of generalisation theory. SVMs find the optimal separating
hyperplane that maximises the margin between two classes. Training reduces to a convex quadratic
programme -- guaranteeing a unique global minimum with no local minima.
Key Intuition. Among all valid separating hyperplanes, SVM selects the unique one that is
equidistant from both classes -- the maximum-margin hyperplane. The classifier is fully determined
by a small subset of training points called support vectors; all other points are irrelevant.

1.3 Linear Separators and the Margin

For binary classification we seek a hyperplane w·x + b = 0 separating the two classes. The
perceptron finds any separating hyperplane; SVM finds the unique best one -- the maximum-margin
hyperplane.
Hyperplane: wT·x + b = 0
Class +1 side: wT·x + b > 0
Machine Learning -- Tom M. Mitchell 4

Class -1 side: wT·x + b < 0

Distance from x: r = |wT·x + b| / ||w||
Total margin width: rho = 2 / ||w||

1.4 Why Maximum Margin? -- VC Theory

A skinny margin is more flexible (higher complexity), more prone to overfitting. A fat margin is less
complex and generalises better. Vapnik (1995) proved:
VC Bound: h <= min( [D2/rho2], m0 ) + 1

where: rho = margin, D = diameter of smallest enclosing sphere, m0 =

dimensionality
* Larger margin rho => smaller VC dimension => lower model complexity.
* Maximising margin minimises complexity regardless of dimensionality.
* Solution depends only on support vectors, not on number of features.

1.5 Hard-Margin SVM -- Mathematical Formulation

Assume data is perfectly linearly separable. In canonical form, all points lie at distance >= 1 from the
hyperplane. The class constraints become:
Constraint (unified): yi · (wT·xi + b) >= 1 for all i
Support vectors satisfy EQUALITY: yi·(wT·xi + b) = 1

PRIMAL QP:
Minimise: PHI(w) = (1/2) · wT · w
Subject to: yi · (wT·xi + b) >= 1 for all training points i

Convex QP => unique global minimum, guaranteed convergence, no local minima.

1.6 Dual Formulation and Lagrange Multipliers

Solving via the Lagrangian dual associates multiplier alphai >= 0 with every constraint. Three major
advantages: (1) training points appear only as inner products xi·xj -- enabling the kernel trick; (2)
variables are alphai (one per point); (3) convex QP with linear constraints -- efficient solvers exist.
DUAL PROBLEM -- maximise:
Q(alpha) = SUMi alphai - (1/2)·SUMiSUMj alphai·alphaj·yi·yj·(xiT·xj)

Subject to: (1) SUMi alphai·yi = 0 (2) alphai >= 0

SOLUTION:
w* = SUMi alphai·yi·xi
b* = yk - (w*)T·xk for any k with alphak != 0

CLASSIFIER:
f(x) = sign( SUMi alphai·yi·(xiT·x) + b )

Non-zero alphai => xi IS a support vector

1.7 Soft-Margin SVM -- Non-Separable Data

Machine Learning -- Tom M. Mitchell 5

Real datasets are rarely perfectly separable. The soft-margin SVM (Cortes & Vapnik, 1995)
introduces slack variables xii >= 0 permitting some margin violations. Hyperparameter C controls the
trade-off between margin width and violations.
Slack variable interpretation:
xii = 0 : outside margin, correctly classified
xii in (0, 1] : inside margin, correctly classified
xii > 1 : misclassified

SOFT-MARGIN PRIMAL:
Minimise: (1/2)·||w||2 + C · SUMi xii
Subject to: yi·(wT·xi+b) >= 1-xii and xii >= 0

C large => narrow margin (risk: overfit)

C small => wide margin (risk: underfit)

1.8-1.10 Feature Spaces, Kernels and Mercer's Theorem

When data is not linearly separable in input space, map it to a higher-dimensional feature space
phi(x). The kernel trick replaces the inner product xi·xj with K(xi,xj) = phi(xi)·phi(xj), working implicitly
in that space without ever computing phi(x).
Standard Kernel Functions:
Linear: K(x,z) = xT·z
Polynomial: K(x,z) = (1 + xT·z)p
RBF/Gaussian: K(x,z) = exp(-gamma·||x-z||2) gamma large => complex boundary
Sigmoid: K(x,z) = tanh(beta0·xT·z + beta1)

Mercer's Theorem: K is a valid kernel <=> Gram matrix K is positive

semi-definite

Kernelised classifier: f(x) = sign( SUMi alphai·yi·K(xi,x) + b )

1.11 Hard-Margin vs Soft-Margin -- Summary

Aspect Hard-Margin SVM Soft-Margin SVM

Data requirement Perfectly linearly separable Any (allows violations)

Primal objective min (1/2)||w||<super>2</super> min (1/2)||w||<super>2</super> + C·SUMxi

Constraint y(w·x+b) >= 1 y(w·x+b) >= 1-xi

Dual alpha range 0 <= alpha 0 <= alpha <= C

Key hyperparameter None C (penalty for slack)

Risk Infeasible if inseparable Overfit if C too large

Machine Learning -- Tom M. Mitchell 6

CHAPTER 2

Decision Trees
Non-parametric supervised learning via hierarchical if-then-else rules. (Mitchell 1997; Russell &
Norvig 2003)

2.1 Introduction and Theoretical Foundation

Decision tree induction is a simple but powerful learning paradigm. A set of training examples is
broken down into smaller and smaller subsets while an associated decision tree gets incrementally
developed. The tree can be thought of as a set of sentences in Disjunctive Normal Form (DNF). The
most widely used algorithms are ID3 (Quinlan, 1986), C4.5 (Quinlan, 1993), and CART (Breiman,
1984).

Problems well-suited to Decision Tree Learning:

* Attribute-value paired elements
* Discrete target function
* Disjunctive descriptions of the target function
* Works well with missing or erroneous training data
* Highly interpretable -- can be visualised and converted to rules

2.2 Building a Decision Tree

Step 1: Test all attributes; select the one that is the best root.
Step 2: Break up training set into subsets based on root node branches.
Step 3: Test remaining attributes; find which fits best under each branch.
Step 4: Continue recursively until one of these stopping conditions:
* (a) All examples in a subset are of one type -> LEAF
* (b) No examples left -> return majority classification of parent
* (c) No more attributes -> default to majority classification

2.3 Entropy and Information Gain (ID3/C4.5)

Entropy is the minimum number of bits needed to classify an arbitrary example. A pure node (single
class) has entropy 0. A maximally mixed binary node (50/50) has entropy 1 bit. Information Gain
measures entropy reduction from a split.
Entropy: E(S) = -SUMi=1c pi · log2(pi)
Convention: 0 · log2(0) = 0

Info Gain: G(S,A) = E(S) - SUMvinValues(A) (|Sv|/|S|) · E(Sv)

Sv = subset of S where attribute A = v

Gain Ratio: GR(S,A) = G(S,A) / SplitInfo(S,A)

SplitInfo: = -SUMv (|Sv|/|S|) · log2(|Sv|/|S|)

=> GainRatio corrects ID3's bias toward high-cardinality attributes

Machine Learning -- Tom M. Mitchell 7

2.4 Gini Impurity (CART)

Gini(t) = 1 - SUMj [p(j|t)]2

Gini = 0 -> pure node (all same class)

Gini = 0.5 -> maximum impurity for binary classification

Gini Gain(A) = Gini(parent) - SUMv (|Dv|/|D|) · Gini(Dv)

CART always produces binary splits and uses Gini for classification. ID3/C4.5 use Entropy and
produce multi-way splits.

2.5 Worked Example -- PlayTennis Dataset

Day Outlook Temp Humidity Wind Play?

1 Sunny Hot High Weak No

2 Sunny Hot High Strong No

3 Overcast Hot High Weak Yes

4 Rain Mild High Weak Yes

5 Rain Cool Normal Weak Yes

6 Rain Cool Normal Strong No

7 Overcast Cool Normal Strong Yes

8 Sunny Mild High Weak No

9 Sunny Cool Normal Weak Yes

10 Rain Mild Normal Weak Yes

11 Sunny Mild Normal Strong Yes

12 Overcast Mild High Strong Yes

13 Overcast Hot Normal Weak Yes

14 Rain Mild High Strong No

Step 1: E(S) = -(9/14)·log2(9/14) - (5/14)·log2(5/14) = 0.940 bits

Step 2 -- Information Gains:

G(S, Outlook) = 0.940 - [5/14·0.971 + 4/14·0.000 + 5/14·0.971] = 0.246
G(S, Humidity) = 0.940 - [7/14·0.985 + 7/14·0.592] = 0.151
G(S, Wind) = 0.940 - [8/14·0.811 + 6/14·1.000] = 0.048
G(S, Temp) = 0.940 - [4/14·1.000 + 6/14·0.918 + 4/14·0.811]= 0.029

Step 3: ROOT = Outlook (highest gain = 0.246)

Overcast branch: pure (all Yes) -> LEAF = Yes

Rain sub-tree (5 examples: 3 Yes, 2 No):

G(Rain, Humidity) = 0.971 - [2/5·E(high) + 3/5·E(normal)] = 0.02
G(Rain, Wind) = 0.971 - [3/5·0 + 2/5·0] = 0.971
=> Wind selected (gain 0.971 >> 0.02)
Wind=Weak: Yes | Wind=Strong: No
Machine Learning -- Tom M. Mitchell 8

Sunny sub-tree -> split on Humidity (Gain = 0.971)

Humidity=Normal: Yes | Humidity=High: No

The final learned rule set (Disjunctive Normal Form):

Rule 1: (Outlook=Sunny ^ Humidity=High) -> No
Rule 2: (Outlook=Sunny ^ Humidity=Normal) -> Yes
Rule 3: (Outlook=Overcast) -> Yes
Rule 4: (Outlook=Rain ^ Wind=Strong) -> No
Rule 5: (Outlook=Rain ^ Wind=Weak) -> Yes

2.6 Overfitting, Pruning, and Stopping Criteria

A fully grown tree achieves zero training error by creating one leaf per example. This is classic
overfitting. According to Mitchell (1997): a hypothesis h overfits training set D if there exists h' that
outperforms h on the total distribution of instances D is a subset of.

Reduced-Error Pruning:
* Step 1: Grow the full decision tree on training set.
* Step 2: Randomly select and remove a node.
* Step 3: Replace node with its majority classification.
* Step 4: If performance on validation set is same or better -> keep change.
* Repeat until no further improvement.

Rule Post-Pruning (C4.5):

* Step 1: Grow the full decision tree on training set.
* Step 2: Convert the tree into a set of rules.
* Step 3: Remove antecedents that reduce validation set error rate.
* Step 4: Sort resulting rules by accuracy; use sorted list for classification.

Cost-Complexity Pruning (CART): Penalise tree size with regularisation parameter alpha. Grow a
sequence of trees; select alpha by cross-validation.
Pre-pruning (early stopping): Stop splitting if gain < threshold, node has fewer than min_samples,
or max_depth is reached. Less reliable than post-pruning.

2.7 Attribute Selection: GainRatio and Cost-Sensitive

The Information Gain equation G(S,A) is biased toward attributes with many values (e.g. a unique ID
column would have perfect gain but be useless -- a "Super Attribute"). GainRatio corrects this:
SplitInfo(S,A) = -SUMv=1k (|Sv|/|S|) · log2(|Sv|/|S|)
where k = number of values of attribute A

GainRatio(S,A) = G(S,A) / SplitInfo(S,A)

Cost-sensitive attribute selection (when some tests are expensive):
G'(S,A) = G(S,A) / Cost(A)
G'(S,A) = G(S,A)2 / Cost(A) [Mitchell 1997]
G'(S,A) = (2G(S,A) - 1) / (Cost(A)+1)w [Mitchell 1997]
Machine Learning -- Tom M. Mitchell 9

CHAPTER 3

Random Forests
Ensemble learning via bagging and random feature selection -- reducing variance without increasing
bias. (Breiman, 2001)

3.1 Introduction and History

Random Forest is an ensemble learning method that constructs a multitude of decision trees during
training and outputs the class that is the mode (classification) or mean prediction (regression) of the
individual trees. It was introduced by Leo Breiman in 2001, combining two key ideas: Bagging and
Random Feature Selection. The method builds on the earlier Random Subspace Method (Ho,
1995/1998), which built multiple trees in randomly selected subspaces of the feature space.

3.2 Ensemble Learning Theory

The theoretical justification comes from the bias-variance decomposition. A single deep tree has low
bias (flexible) but high variance (sensitive to training set). For B trees with individual variance sigma2
and pairwise correlation rho:
Ensemble variance = rho·sigma2 + (1-rho)·sigma2/B

As B -> inf this approaches rho·sigma2 (irreducible floor)

Key insight: Random feature selection REDUCES rho (inter-tree correlation),

driving ensemble variance toward this floor.
Two core concepts underlie Random Forests:
* Wisdom of the crowd: a large group of diverse, uncorrelated experts outperforms any single
expert.
* Diversification: an uncorrelated set of trees reduces overall variance.

3.3 Bootstrap Aggregating (Bagging)

Bagging (Breiman, 1994) creates diversity by training each tree on a different bootstrap sample of
the training data. Each bootstrap sample has N instances, but some original instances may appear
multiple times and others not at all.
Bootstrap Sample Db: sampled WITH REPLACEMENT from D, |Db| = N

P(instance not selected in one draw) = (1 - 1/N)N -> e-1 ~= 36.8%

=> Unique examples per tree ~= 63.2%
=> Out-of-Bag (OOB) samples ~= 36.8% (not used for that tree)

OOB Error: for each xi, predict using ONLY trees that did NOT train on xi.
Majority vote these OOB predictions -> free unbiased test-error estimate.
As reliable as 5-fold cross-validation. No separate validation set needed.

3.4 Random Feature Selection (Random Subspace Method)

Machine Learning -- Tom M. Mitchell 10

At each node split, only a random subset of m features (out of p total) is evaluated. This is the key
difference from plain Bagged Trees -- it decorrelates the trees further. Without this, all trees would
use the same dominant features at the root, making them highly correlated.
Classification default: m = sqrtp (Breiman's default)
Regression default: m = p/3

Larger m => stronger individual trees, more correlated (higher variance)

Smaller m => weaker individual trees, more diverse (lower variance)

Tuning m is often the most impactful hyperparameter after n_estimators.

CAVEAT: When the fraction of RELEVANT features is small, small m performs
poorly.

3.5 The Random Forest Algorithm

INPUT: Training data D (N samples, p features), B trees, m features/split

FOR each tree b = 1 to B:

1. Draw bootstrap sample D_b (N samples, with replacement) from D
2. Grow UNPRUNED decision tree T_b on D_b:
At each node:
(a) Randomly select m features from p total
(b) Find best split among those m features (highest Gini Gain / Info Gain)
(c) Split node; recurse until pure / min_samples / max_depth

PREDICT (classification): majority_vote { T_1(x), T_2(x), ..., T_B(x) }

PREDICT (regression): y_hat = (1/B) * SUM_{b=1}^{B} T_b(x)

3.6 Feature Importance (MDI)

Mean Decrease in Impurity (MDI): for each feature j, sum the total weighted impurity decrease
across all nodes and all trees where feature j was used as the split variable, then normalise.
FI(j) = (1/B) · SUMb SUMtinT [ DELTAImpurity(t) · I(feature(t)=j) · p(t) ]
b

where:
DELTAImpurity(t) = impurity decrease at node t
I(feature(t)=j) = 1 if feature j was used at node t
p(t) = fraction of training samples reaching node t

Normalise so all FI(j) sum to 1.

Permutation Importance (alternative): shuffle feature j in OOB set;

measure increase in OOB error -- more reliable for correlated features.

3.7 Worked Example -- Buy Product Dataset

Dataset of 10 samples. Features: Age (<=30 / 31-40 / >40), Income (High/Medium/Low), Student
(Yes/No). Target: Buys Product (Yes/No).

# Age Income Student Buys?

1 <=30 High No No

2 <=30 High No No
Machine Learning -- Tom M. Mitchell 11

# Age Income Student Buys?

3 31-40 High No Yes

4 >40 Medium No Yes

5 >40 Low Yes Yes

6 >40 Low Yes No

7 31-40 Low Yes Yes

8 <=30 Medium No No

9 <=30 Low Yes Yes

10 <=30 Medium Yes Yes

p=3 features => m = sqrt3 ~= 2 features per split

Bootstrap Sample 1 (Tree 1): {1,3,4,4,5,6,7,8,9,10} Yes=6, No=4

Bootstrap Sample 2 (Tree 2): {1,1,2,3,5,6,7,8,9,9} Yes=5, No=5
Bootstrap Sample 3 (Tree 3): {2,3,4,5,5,6,7,8,10,10} Yes=6, No=4

Tree 1 Root Split -- features {Age, Income} randomly selected:

Parent Gini = 1 - [(6/10)2 + (4/10)2] = 0.48

Gini after Age split:

<=30: {1,2,8,9,10} Yes=2, No=3 Gini=0.48
31-40: {3,7} Yes=2, No=0 Gini=0.00 (PURE!)
>40: {4,5,6} Yes=2, No=1 Gini=0.444
Weighted = (5/10)·0.48 + (2/10)·0.00 + (3/10)·0.444 = 0.373
Gini Gain(Age) = 0.48 - 0.373 = 0.107

Gini after Income split:

High: {1,2,3} Yes=1, No=2 Gini=0.444
Medium: {4,8,10} Yes=2, No=1 Gini=0.444
Low: {5,6,7,9} Yes=3, No=1 Gini=0.375
Weighted = (3/10)·0.444 + (3/10)·0.444 + (4/10)·0.375 = 0.416
Gini Gain(Income) = 0.48 - 0.416 = 0.064

Decision: Age selected as root (Gini Gain 0.107 > 0.064)

Prediction for new instance: Age=<=30, Income=Medium, Student=Yes

Tree 1: Yes | Tree 2: Yes | Tree 3: Yes
Majority Vote -> YES (person will buy product)

3.8 Hyperparameters
Hyperparameter Description Default / Typical

n_estimators Number of trees in the forest 100-500

max_features Features considered at each split sqrtp for classification

max_depth Maximum depth of each tree None (fully grown)

Machine Learning -- Tom M. Mitchell 12

Hyperparameter Description Default / Typical

min_samples_split Min samples required to split a node 2

min_samples_leaf Min samples at a leaf node 1

bootstrap Whether to use bootstrap samples True

oob_score Use OOB samples for error estimation False

criterion Splitting criterion gini

3.9 Advantages and Disadvantages

Advantages Disadvantages

High accuracy -- one of the best off-the-shelf classifiers

Less interpretable than a single decision tree (black box)

Resistant to overfitting due to averaging across many Computationally

trees expensive for very large datasets

Handles high-dimensional data and missing values well

Biased toward features with more levels in categoricals

Provides feature importance rankings High memory consumption when many trees are built

OOB error provides unbiased generalisation estimatePerforms poorly when fraction of relevant features is small

Parallelisable -- trees can be trained independently Slower prediction time vs linear models
Machine Learning -- Tom M. Mitchell 13

CHAPTER 4

Logistic Regression
Supervised classification algorithm modelling P(y=1|x) -- a linear model for the log-odds of class
membership.

4.1 Introduction and Motivation

Logistic Regression is one of the most widely used supervised machine learning algorithms. It is
used for predicting categorical dependent variables using a given set of independent variables.
Unlike linear regression, which gives exact values, logistic regression gives probabilistic values
between 0 and 1. Despite the name, it is a classification algorithm, not a regression algorithm. It
belongs to the family of Generalised Linear Models (GLMs).
Use logistic regression when: (1) calibrated probability estimates are needed, (2) the data is
approximately linearly separable, (3) interpretability of coefficients matters, or (4) the dataset is
large. It also forms the output layer of neural networks for classification tasks.

4.2 The Logistic (Sigmoid) Function

In logistic regression, instead of fitting a regression line, we fit an S-shaped logistic function
(sigmoid) which maps any real value to (0, 1). The curve indicates the likelihood of an event
occurring.
sigma(z) = 1 / (1 + e-z) [S-shaped, maps R -> (0,1)]

sigma(0) = 0.5 | sigma(+inf) -> 1 | sigma(-inf) -> 0

sigma'(z) = sigma(z) · (1 - sigma(z)) [convenient for backpropagation]

P(y=1|x) = sigma(wT·x + b)
P(y=0|x) = 1 - sigma(wT·x + b)

Decision rule: predict class 1 if P(y=1|x) >= 0.5 <=> wT·x + b >= 0
Threshold: values above threshold -> 1, values below -> 0 (typically 0.5, but
tunable)

4.3 Logit Derivation -- Why It Is a Linear Model

Logistic regression is called a linear model because the log-odds (logit) of the output probability is a
linear function of the inputs.
Straight line: y = b0 + b1x1 + b2x2 + ... + bnxn
Divide by (1-y): y/(1-y) = e(b0 + b1x1 + ...)
Take log: log(y/(1-y)) = b0 + b1x1 + ... <- LOG-ODDS (logit)

Odds: p/(1-p) range: (0, +inf)

Log-Odds: log(p/(1-p)) = wT·x [linear in x]

Solving for p: p = ez/(1+ez) = 1/(1+e-z) <- sigmoid!

Machine Learning -- Tom M. Mitchell 14

Decision boundary: p = 0.5 <=> z = 0 <=> wT·x = 0

=> Linear decision boundary in input space

4.4 Training: Cross-Entropy Loss

Parameters are learned by Maximum Likelihood Estimation (MLE). The cross-entropy loss is convex
in w, guaranteeing convergence to the global minimum with gradient descent.
Cross-Entropy Loss: J(w) = -(1/N)·SUMi [ yi·log(y^i) + (1-yi)·log(1-y^i) ]

Gradient: dJ/dw = (1/N)·SUMi (y^i - yi)·xi

Update rule: w := w - alpha · dJ/dw
With L2 reg: w := w - alpha · (dJ/dw + lambda·w)

4.5 Assumptions for Logistic Regression

* The dependent variable must be categorical in nature.
* The independent variables should not have multi-collinearity.
* The observations should be independent of each other.
* The independent variables should be linearly related to the log-odds.

4.6 Types of Logistic Regression

Type Classes Description Example

Binomial 2 Two possible outcomes. Uses [Link]/Fail, Yes/No, Spam/Not Spam

Multinomial 3+, unord 3+ unordered outcomes. Uses [Link] / Dog / Bird

Ordinal 3+, ord 3+ ordered outcomes. Proportional odds.

Low / Medium / High

Softmax (K classes): P(y=k|x) = exp(wkT·x) / SUMj exp(wjT·x)

Categorical Cross-Entropy: J = -(1/N)·SUMiSUMk yik · log P(y=k|xi)

Machine Learning -- Tom M. Mitchell 15

CHAPTER 5

K-Means Clustering
Unsupervised partitional clustering -- grouping N data points into K disjoint subsets by minimising
within-cluster sum of squares.

5.1 Introduction and Theory

Clustering is the classification of objects into different groups -- partitioning a dataset into subsets so
that data in each subset share common traits. K-Means (MacQueen, 1967; Lloyd, 1982) is the most
widely used partitional clustering algorithm. It assumes object attributes form a vector space and
minimises the sum-of-squares criterion. K-Means is an instance of the EM algorithm: the E-step
assigns points to the nearest centroid; the M-step recomputes centroids. Each iteration is
guaranteed to decrease or maintain WCSS -- but only to a local minimum.
WCSS Objective: J = SUMk SUMxinC ||x - muk||2
k
Centroid: muk = (1/|Ck|) · SUMxinC x
k

Euclidean (L2): d(x,y) = sqrt(SUMi(xi-yi)2) [most common]

Manhattan (L1): d(x,y) = SUMi |xi-yi|
Maximum norm: d(x,y) = maxi |xi-yi|
Mahalanobis: corrects for different scales and correlations

5.2 Algorithm Steps

Step 1: Decide value of K (number of clusters).
Step 2: Initialise K centroids (random or K-Means++).
* Option A: Take first K samples as single-element clusters.
* Option B: Assign remaining (N-K) samples to nearest centroid; recompute after each.
Step 3: For each sample, compute distance to all centroids. If sample is not in the cluster with
closest centroid, move it there. Update centroids of gaining and losing clusters.
Step 4: Repeat Step 3 until no new assignments occur (convergence).
Time complexity per iteration: O(N · K · d)

5.3 K-Means++ Initialisation

Standard random initialisation can lead to poor local minima. K-Means++ (Arthur & Vassilvitskii,
2007) provides O(log K)-competitive initialisation:
* Step 1: Choose first centroid uniformly at random from data points.
* Step 2: For each point x, compute D(x) = distance to nearest already-chosen centroid.
* Step 3: Choose next centroid with probability proportional to D(x)2.
* Step 4: Repeat Steps 2-3 until K centroids chosen; then run standard K-Means.

5.4 Worked Numerical Example 1 -- K=2, 7 Points

Machine Learning -- Tom M. Mitchell 16

Point x y Iter 0 Cluster Iter 1 Cluster Final

P1 1.0 1.0 C1 C1 C1

P2 1.5 2.0 C1 C1 C1

P3 3.0 4.0 C1 (tie) C2 C2

P4 5.0 7.0 C2 C2 C2

P5 3.5 5.0 C2 C2 C2

P6 4.5 5.0 C2 C2 C2

P7 3.5 4.5 C2 C2 C2

Initial centroids: m1=(1,1), m2=(5,7)

Iter 0 centroids:
C1={P1,P2,P3} m1 = ((1+1.5+3)/3, (1+2+4)/3) = (1.83, 2.33)
C2={P4,P5,P6,P7} m2 = ((5+3.5+4.5+3.5)/4, (7+5+5+4.5)/4) = (4.13, 5.38)

Iter 1: P3 distance check:

d(P3, m1) = sqrt((3-1.83)2 + (4-2.33)2) = 2.04
d(P3, m2) = sqrt((3-4.13)2 + (4-5.38)2) = 1.78 -> P3 moves to C2!

C1={P1,P2} m1=(1.25, 1.50)

C2={P3,P4,P5,P6,P7} m2=(3.90, 5.10)

Iter 2: No reassignments -> CONVERGED

Final: C1={P1,P2} | C2={P3,P4,P5,P6,P7}

5.5 Worked Numerical Example 2 -- Medicine Dataset (K=2)

Four medicines with two attributes each. Initial centroids: c1=(1,1) [Medicine A], c2=(2,1) [Medicine
B].
Medicine A=(1,1), B=(2,1), C=(4,3), D=(5,4)

Iter 0 distances (Euclidean):

d(A,c1)=0.00 d(A,c2)=1.00 -> Group 1
d(B,c1)=1.00 d(B,c2)=0.00 -> Group 2
d(C,c1)=3.61 d(C,c2)=2.83 -> Group 2
d(D,c1)=5.00 d(D,c2)=4.24 -> Group 2

New centroids: c1=(1,1), c2=((2+4+5)/3, (1+3+4)/3) = (3.67, 2.67)

Iter 1: Medicine B now closer to c1 -> moves to Group 1

Group 1={A,B} c1=(1.5, 1.0)
Group 2={C,D} c2=(4.5, 3.5)

Iter 2: No reassignments -> CONVERGED

Final: Group 1={A,B} | Group 2={C,D}

5.6 Choosing K -- Elbow Method, Silhouette, Gap Statistic

Machine Learning -- Tom M. Mitchell 17

WCSS always decreases as K increases (K=N gives WCSS=0). The optimal K is at the "elbow" --
the point of diminishing returns.

Method Measure Optimal K

Elbow WCSS vs K -- look for kink Where WCSS curve bends

Silhouette Cohesion vs separation [-1, 1] K with highest average score

Gap Statistic WCSS vs random reference data K where gap is maximised

5.7 K-Medoids (PAM) -- Robustness to Outliers

K-Medoids uses actual data points (medoids) as cluster centres rather than means. This makes it
far more robust to extreme values:
Example: Dataset = {1, 3, 5, 7, 1009}
Mean = (1+3+5+7+1009)/5 = 205 <- heavily skewed by outlier
Median = 5 <- robust, unaffected by outlier
* K-Medoids advantage: not affected by extreme values.
* K-Medoids disadvantage: more computationally expensive than K-Means.

5.8 Weaknesses of K-Means

* Must specify K in advance -- unknown in most real applications.
* Sensitive to initialisation -- use K-Means++ to mitigate.
* Assumes spherical, similarly-sized clusters -- fails on non-convex shapes (use DBSCAN
instead).
* Sensitive to outliers -- use K-Medoids for robust clustering.
* Results may differ between runs for small datasets due to random initialisation.
* May converge to local minimum -- run multiple times with different seeds.
Machine Learning -- Tom M. Mitchell 18

CHAPTER 6

Hierarchical Clustering & Association Rules

Nested partitions via dendrograms, and market basket analysis via the Apriori algorithm.

6.1 Hierarchical Clustering

Hierarchical clustering builds a nested sequence of partitions represented as a dendrogram. Unlike
K-Means, no value of K is required in advance -- the dendrogram can be cut at any level. The height
of a merge point represents the inter-cluster distance at that merge.

6.2 Linkage Criteria

Linkage Distance Formula Characteristic

Single min d(a,b) for ainA, binB Chaining; elongated clusters

Complete max d(a,b) for ainA, binB Compact, equal-diameter clusters

Average mean d(a,b) for ainA, binB Balance of single & complete

Ward Increase in total WCSS at merge Minimises within-cluster variance; best default

Centroid d(centroid_A, centroid_B) Can produce inversions in dendrogram

Ward's Linkage is generally considered the best default for most applications because it directly
minimises the within-cluster variance at each merge -- equivalent to running agglomerative
clustering with the same objective as K-Means.

6.3 Reading a Dendrogram

* The x-axis shows individual data points (or small clusters).
* The y-axis shows the inter-cluster distance at which clusters were merged.
* To obtain K clusters: draw a horizontal cut; the number of vertical lines intersected equals K.
* A good cut has a large vertical jump just before it -- the two clusters being merged are
genuinely dissimilar.

6.4 Association Rule Mining

Association rule mining discovers frequent co-occurrence patterns in transaction datasets. The
classic application is market basket analysis. A rule has the form A -> B.
Support(A->B) = P(A U B) = count(A and B) / N
Confidence(A->B) = P(B|A) = count(A and B) / count(A)
Lift(A->B) = Confidence(A->B) / Support(B)

Lift > 1 : A and B positively correlated (useful rule)

Lift = 1 : A and B independent (useless rule)
Lift < 1 : A and B negatively correlated (avoid together)

6.5 Apriori Algorithm

Machine Learning -- Tom M. Mitchell 19

Apriori (Agrawal & Srikant, 1994) exploits the Apriori principle: if an item set is frequent (support >=
min_support), all its subsets are frequent; conversely, if an item set is infrequent, all its supersets
are infrequent. This prunes the exponential search space dramatically.
* Step 1. Find all frequent 1-item sets (items meeting min_support).
* Step 2. Generate candidate 2-item sets from frequent 1-item sets; prune those with infrequent
subsets.
* Step 3. Repeat, generating k-item sets from (k-1)-item sets, until no more frequent sets.
* Step 4. Generate association rules from each frequent item set with confidence >=
min_confidence.
Machine Learning -- Tom M. Mitchell 20

CHAPTER 7

Principal Component Analysis (PCA)

Linear dimensionality reduction via eigendecomposition of the covariance matrix. (Pearson, 1901;
Hotelling, 1933)

7.1 Motivation and Goals

PCA addresses the challenge of high-dimensional data. Given data points in d dimensions, it
converts them to data points in r < d dimensions with minimal loss of information. It finds a new
orthogonal coordinate system aligned with the directions of maximum variance.

Benefits of dimensionality reduction:

* Compresses data -- reduces storage and computation.
* Reduces redundant / correlated features (addresses multicollinearity).
* Improves model performance by eliminating noise dimensions.
* Enables 2D/3D visualisation of high-dimensional data.
Limitation. Components are linear combinations and are not interpretable as individual features.
PCA is unsupervised -- it does not use class labels. For supervised dimensionality reduction, use
LDA.
Problem formulation (Andrew Ng): reduce from n-dimension to k-dimension -- find k vectors onto
which to project the data so as to minimise the projection error.

7.2 Covariance and Eigendecomposition

Covariance is a measure of how much each dimension varies from the mean with respect to each
other. The covariance matrix C is a d×d symmetric positive semi-definite matrix.
Variance: Var(X) = (1/n) · SUMi (xi - x-)2
Covariance: Cov(X,Y) = (1/n) · SUMi (xi-x-)(yi-y-)

Cov > 0 : both dimensions increase/decrease together

Cov < 0 : one increases as the other decreases
Cov = 0 : features are linearly uncorrelated

Covariance matrix: C[i,j] = Cov(featurei, featurej) [d×d symmetric PSD]

Matrix form: C = (1/n) · XcT · Xc (Xc = centred data)

Eigenvalue equation: C · u = lambda · u

Characteristic eqn: det(C - lambdaI) = 0 (solve for eigenvalues)
Then solve: (C - lambdakI) · uk = 0 (for eigenvectors)

Properties of symmetric C:
All eigenvalues are real and >= 0
Eigenvectors for distinct eigenvalues are orthogonal
Larger eigenvalue => more variance captured in that direction
Machine Learning -- Tom M. Mitchell 21

7.3 PCA Step-by-Step Procedure

Step 1: Collect data X (n × d)
Step 2: Compute mean: mu = (1/n) · SUM_i x_i
Step 3: Centre data: X_c = X - mu [subtract mean from each row]
Step 4: Covariance: C = (1/n) · X_c^T · X_c (d × d)
Step 5: Solve det(C - lambdaI) = 0 => eigenvalues lambda_1 >= lambda_2 >= ...
Solve (C - lambda_k·I)·u_k = 0 => eigenvectors u_k
Step 6: Sort eigenvectors by eigenvalue (descending)
Step 7: Select top K: U = [u_1 | u_2 | ... | u_K] (d × K)
Step 8: Project: Z = X_c · U (n × K)

Reconstruction: X_approx = Z · U^T + mu

Variance explained by PC_k: lambda_k / SUM_i lambda_i
Choose K such that cumulative explained variance >= 95%
Verify: P^T · P = diag(lambda_1, lambda_2, ...) [off-diagonals = 0]

7.4 Worked Numerical Example -- 6 Points (Full Walkthrough)

Dataset: x1=(2,1), x2=(3,5), x3=(4,3), x4=(5,6), x5=(6,7), x6=(7,8).
Step 1: Data X = {(2,1),(3,5),(4,3),(5,6),(6,7),(7,8)}
Step 2: Mean mu = (4.5, 5.0)
Step 3: Centred data:
(-2.5,-4.0) (-1.5,0.0) (-0.5,-2.0) (0.5,1.0) (1.5,2.0) (2.5,3.0)

Step 4: Covariance C = (1/6)·X_cT·X_c:

C[1,1]=2.917 C[2,2]=5.667 C[1,2]=3.667
C = [[2.917, 3.667], [3.667, 5.667]]

Step 5: Eigenvalues -- solve det(C - lambdaI) = 0:

lambda2 - 8.584·lambda + 3.080 = 0
=> lambda1 = 8.22 lambda2 = 0.38

Variance explained by PC1: 8.22/8.60 = 95.6% => 1 component suffices!

Step 6: Eigenvector for lambda1 = 8.22:

(C - 8.22I)·u = 0 => 5.3·u1 = 3.667·u2 => u1 = 0.692·u2
Normalise (u12+u22=1): u2=0.822, u1=0.569
PC1 = [0.569, 0.822]

Step 7: Project onto PC1 (zi = Xc,i · PC1):

z1=-4.711 z2=-0.854 z3=-1.929 z4=1.107 z5=2.498 z6=3.889

7.5 Worked Example -- Sample Problem

Two attributes X and Y, each sampled three times, are combined into a data matrix S. The following
example illustrates the complete PCA procedure, including eigendecomposition and projection.
X = [1, 0, -1]T Y = [-1, 1, 0]T

S = [[1, -1],
[0, 1],
[-1, 0]]
Computing the unnormalised covariance matrix C = ST·S:
Machine Learning -- Tom M. Mitchell 22

C = [[1,0,-1], · [[1,-1], = [[2, -1],

[-1,1, 0]] [0, 1], [-1, 2]]
[-1, 0]]
Eigenvalues are found by solving det(C - lambdaI) = 0:
|2-lambda -1 |
|-1 2-lambda | = 0

(2-lambda)2 - 1 = lambda2 - 4lambda + 3 = 0

=> lambda1 = 3 (larger) lambda2 = 1 (smaller)
The corresponding eigenvectors are obtained by solving (C - lambdaI)·u = 0 for each eigenvalue:
For lambda2 = 1:
(C - I)·u = [[1,-1],[-1,1]]·[u1,u2]T = 0
=> u1 = u2
Normalised: v = (1/sqrt2)·[1, 1]T

For lambda1 = 3 (larger eigenvalue = first principal component):

(C - 3I)·u = [[-1,-1],[-1,-1]]·[u1,u2]T = 0
=> u1 = -u2
Normalised: u = (1/sqrt2)·[1, -1]T

Note: u is the eigenvector associated with the LARGER eigenvalue (lambda1=3)

=> u is the FIRST PRINCIPAL COMPONENT direction
The principal component matrix P is computed by projecting S onto the eigenvectors:
U = (1/sqrt2) · [[1, 1], [-1, 1]] (eigenvectors as columns)

P = (1/sqrt2) · [[1,-1],[0,1],[-1,0]] · [[1,1],[-1,1]]

= (1/sqrt2) · [[2, 0],[-1, 1],[-1,-1]]

P1 = (1/sqrt2) · [2, -1, -1]T (projection onto PC1)

P2 = (1/sqrt2) · [0, 1, -1]T (projection onto PC2)

Verification: PT·P = diag(lambda1, lambda2) = [[3, 0],[0, 1]]

Reconstruction: P·UT = S (original data recovered)

7.6 Key Points and Common Mistakes

* Always standardise features (zero mean, unit variance) before PCA if they have different scales
-- otherwise high-variance features dominate the components.
* PCA is unsupervised -- uses only X, not class labels. For supervised dimensionality reduction,
use LDA (Linear Discriminant Analysis).
* PCA finds uncorrelated components (2nd order statistics). For statistically independent
components, use ICA (higher-order statistics).
* Reconstruction error = SUMk=K+1d lambdak (sum of discarded eigenvalues).
* Verify your calculation: PT·P should equal diag(lambda1, lambda2, ...) -- off-diagonals must be
zero.
* Related techniques: ICA (non-Gaussian independence), Multidimensional Scaling (preserves
inter-point distances), LDA (maximises class separation).
Machine Learning -- Tom M. Mitchell 23

CHAPTER 8

Independent Component Analysis (ICA)

Blind source separation via statistical independence -- recovering original signals from observed
mixtures. (Bell & Sejnowski, 1995)

8.1 The Cocktail Party Problem

Two people speak simultaneously in a room. Two microphones at different positions each record a
different linear mixture of the two voices. ICA recovers the original speech signals from only the
microphone recordings -- without knowing where the speakers are or what they said. This is Blind
Source Separation (BSS): "blind" because we know very little about the mixing matrix A and make
little assumption on source signals.
Mixing model:
x1(t) = a11·s1(t) + a12·s2(t)
x2(t) = a21·s1(t) + a22·s2(t)

Matrix form: x = A · s

x : observed mixture vector (n×1) -- OBSERVED

s : original source signals (n×1) -- UNKNOWN
A : mixing matrix (n×n) -- UNKNOWN

ICA Goal: find W = A-1 such that u = W·x ~= s (recover sources)

BSS Pipeline: s1,...,sn -[A]-> x1,...,xn -[W]-> u1,...,un

(blind sources) (observed) (recovered estimates)

8.2 ICA Model Definition

The statistical model is called the ICA model. It is a generative model: it describes how recorded
data are generated by mixing the individual components. The time index t is dropped -- we assume
mixtures and sources are random variables, and observed values are samples/realisations of these
variables.
xj = aj1·s1 + aj2·s2 + ... + ajn·sn for all j

In columns of matrix A: x = SUMi=1n ai · si

Without loss of generality, assume both mixture variables and independent

components
have ZERO MEAN. If not, centre by subtracting sample mean.

8.3 ICA Assumptions

* Assumption 1: The components s1, ..., sn are statistically independent: p(s1,...,sn) = PROD
p(si).
* Assumption 2: The independent components must have non-Gaussian distributions -- at most
one source may be Gaussian.
Machine Learning -- Tom M. Mitchell 24

* Assumption 3: The mixing matrix A is square and full rank (n sources, n sensors). This can
sometimes be relaxed.
* Assumption 4: Only x(t) is observed. Both A and s(t) are completely unknown.

Why Non-Gaussianity is Required. The Central Limit Theorem (CLT) states that the sum of
independent random variables tends toward a Gaussian. Therefore a mixture of non-Gaussian
sources is more Gaussian than any individual source. ICA exploits this by finding projections that
are as non-Gaussian as possible -- these are most likely the original sources. A Gaussian
distribution is the only distribution fully characterised by its mean and variance (2nd order statistics).
ICA needs higher-order statistics.

8.4 Measuring Non-Gaussianity

Kurtosis (4th-order statistic):
kurt(y) = E{y4} - 3·(E{y2})2

Gaussian: kurt = 0 (reference)

Super-Gaussian: kurt > 0 (heavy tails, e.g. Laplace, speech signals)
Sub-Gaussian: kurt < 0 (flat tails, e.g. Uniform distribution)

Negentropy (more robust, always non-negative):

J(y) = H(yGaussian) - H(y)
J >= 0 always | J = 0 only for Gaussian | Maximise J to find ICA components

8.5 Ambiguities of ICA

Two fundamental, irresolvable ambiguities exist in the ICA model:
Ambiguity 1 -- Variance (Energy) of Components Cannot Be Determined. In x = As, both A and
s are unknown. Multiplying source si by scalar c and dividing the corresponding column ai of A by c
leaves x unchanged: (ai/c)·(c·si) = ai·si. Resolution: fix unit variance E{si2} = 1. A sign ambiguity (±1)
remains but is insignificant in most applications.
Ambiguity 2 -- Order of Components Cannot Be Determined. Since s and A are unknown, you
can reorder source signals in any way and rearrange the corresponding columns of A -- observed
data x remains identical. This ambiguity cannot be resolved by ICA alone. Any ordering of the
independent components is equally valid.
These ambiguities are generally not problematic because the shape of independent components is
correctly recovered, sign rarely matters for signal separation, and ordering is irrelevant when all
components are recovered correctly.

8.6 Statistical Illustration of ICA

Consider two independent components with uniform distributions:
p(si) = 1/(2sqrt3) if |si| <= sqrt3, else 0
(zero mean, unit variance)

Mixing matrix: A0 = [[2, 3], [2, 1]]

x1 = 2·s1 + 3·s2
x2 = 2·s1 + 1·s2
Machine Learning -- Tom M. Mitchell 25

Joint distribution of (s1, s2): SQUARE shape (independent uniform sources)

Joint distribution of (x1, x2): PARALLELOGRAM shape

Key insight: The EDGES of the parallelogram are the COLUMNS of A0!
Column 1 of A0 = [2, 2]T => direction (2,2) = one edge
Column 2 of A0 = [3, 1]T => direction (3,1) = other edge

This means: in principle, estimate ICA by finding joint density of (x1,x2)

and locating the edges. However, this only works for uniform distributions and
is
computationally complex. A general method is required.

8.7 FastICA Algorithm

FastICA (Hyvärinen & Oja, 1997) uses fixed-point iteration to find weights that maximise
non-Gaussianity (negentropy). It converges cubically -- much faster than gradient methods.
PRE-PROCESSING (required):
1. Centre: subtract mean E{x} = 0
2. Whiten: transform so Cov(x) = I
(removes 2nd-order structure; ICA now only needs to find a rotation)

FOR each component i = 1 to n:

1. Initialise w_i randomly; normalise: w_i = w_i / ||w_i||
2. Update: w_new = E{x · g(w_i^T·x)} - E{g'(w_i^T·x)} · w_i

Common g functions:
g(u) = tanh(u) g'(u) = 1 - tanh2(u)
g(u) = u·exp(-u2/2) g'(u) = (1-u2)·exp(-u2/2)

3. Orthogonalise: w_i = w_i - SUM_{j 4. Normalise: w_i = w_i / ||w_i||

5. Converge if ||w_new - w_old|| < tol; else repeat Step 2

8.8 ICA vs PCA -- Detailed Comparison

Aspect PCA ICA

Goal Decorrelate features (max variance)Find statistically independent features

Statistics 2nd order (covariance) Higher order (kurtosis, negentropy)

Components Orthogonal (uncorrelated) Independent (not necessarily orthogonal)

Non-Gaussian? Not required Required (at most 1 Gaussian source)

Ordering By variance (largest first) No natural ordering

Scaling Eigenvalue determines scale Fixed to unit variance

Use case Dim. reduction, visualisation Signal separation, feature extraction

Gaussian src. Works fine CANNOT separate -- all mixtures Gaussian