MACHINE LEARNING

Comprehensive Study Notes

Tom M. Mitchell

McGraw-Hill . 1997 . Study Edition

Chapter 1 — Linear Models & SVM

Chapter 2 — Decision Trees
Chapter 3 — Random Forests
Chapter 4 — Logistic Regression
Chapter 5 — K-Means Clustering
Chapter 6 — Hierarchical Clustering & Association Rules
Chapter 7 — Principal Component Analysis
Chapter 8 — Independent Component Analysis
Machine Learning — Tom M. Mitchell

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

2
Machine Learning — Tom M. Mitchell

6.3 Dendrogram Interpretation

6.4 Association Rule Mining
6.5 Apriori Algorithm

7 Principal Component Analysis (PCA)

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

3
 Machine Learning — Tom M. Mitchell

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 = w^T . x + b = w0 + w1.x1 + w2.x2 + ... + [Link]

MSE Loss: L(w) = (1/N) . SUM (yi - y_hati)^2

Gradient of MSE: dL/dw = (2/N) . X^T . (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||^2 Shrinks all weights smoothly; no exact zeros All features relevant

Lasso (L1) lambda||w||1 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.

4
Machine Learning — Tom M. Mitchell

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: w^T.x + b = 0

Class +1 side: w^T.x + b > 0

Class -1 side: w^T.x + b < 0

Distance from point x: r = |w^T.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( ceil(D^2/rho^2), 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 . (w^[Link] + b) >= 1 for all i

Support vectors satisfy EQUALITY: yi.(w^[Link] + b) = 1

PRIMAL QP:

Minimise: Phi(w) = (1/2) . w^T . w

Subject to: yi . (w^[Link] + b) >= 1 for all training points i

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

5
Machine Learning — Tom M. Mitchell

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 [Link] — 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).SUMi SUMj [Link].(xi^[Link])

Subject to: (1) SUMi [Link] = 0 (2) alphai >= 0

SOLUTION:

w* = SUMi [Link]

b* = yk - (w*)^[Link] for any k with alphak != 0

CLASSIFIER:

f(x) = sign( SUMi [Link].(xi^T.x) + b )

Non-zero alphai => xi IS a support vector

1.7 Soft-Margin SVM — Non-Separable Data

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.(w^[Link] + 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 & 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 [Link] with K(xi,xj) = phi(xi).phi(xj), working implicitly in that space without
ever computing phi(x).

6
Machine Learning — Tom M. Mitchell

Standard Kernel Functions:

Linear: K(x,z) = x^T.z

Polynomial: K(x,z) = (1 + x^T.z)^p

RBF/Gaussian:K(x,z) = exp(-gamma.||x-z||^2) gamma large => complex boundary

Sigmoid: K(x,z) = tanh(beta0.x^T.z + beta1)

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

Kernelised classifier: f(x) = sign( SUMi [Link].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||^2 min (1/2)||w||^2 + [Link]

Constraint yi([Link]+b) >= 1 yi([Link]+b) >= 1-xii

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

Key hyperparameter None C (penalty for slack)

Risk Infeasible if inseparable Overfit if C too large

7
Machine Learning — Tom M. Mitchell

CHAPTER 2

Decision Trees

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

2.1 Introduction & 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.

8
Machine Learning — Tom M. Mitchell

Entropy: E(S) = -SUM_{i=1}^{c} pi * log2(pi)

Convention: 0 * log2(0) = 0

Info Gain: G(S,A) = E(S) - SUM_{v in Values(A)} (|S_v|/|S|) * E(S_v)

S_v = subset of S where attribute A = v

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

SplitInfo: = -SUM_v (|S_v|/|S|) * log2(|S_v|/|S|)

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

2.4 Gini Impurity (CART)

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

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

Gini = 0.5 -> maximum impurity for binary classification

Gini Gain(A) = Gini(parent) - SUM_v (|D_v|/|D|) * Gini(D_v)

CART always produces binary splits; 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

9
Machine Learning — Tom M. Mitchell

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(Outlook=Rain, Humidity) = 0.971 - [2/5*E(high) + 3/5*E(normal)] = 0.02

G(Outlook=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

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

Humidity=Normal: Yes | Humidity=High: No

The final learned rule set (Disjunctive Normal Form):

Rule1: (Outlook=Sunny ^ Humidity=High) -> No

Rule2: (Outlook=Sunny ^ Humidity=Normal) -> Yes

Rule3: (Outlook=Overcast) -> Yes

Rule4: (Outlook=Rain ^ Wind=Strong) -> No

Rule5: (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.

While (not done): repeat Step 2.

Rule Post-Pruning (C4.5):

10
Machine Learning — Tom M. Mitchell

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) = -SUM_{v=1}^{k} (|S_v|/|S|) * log2(|S_v|/|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) = (2^G(S,A) - 1) / (Cost(A)+1)^w [Mitchell 1997]

11
Machine Learning — Tom M. Mitchell

CHAPTER 3

Random Forests

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

3.1 Introduction & 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 sigma^2 and pairwise
correlation rho:

Ensemble variance = rho*sigma^2 + (1-rho)*sigma^2/B

As B -> inf this approaches rho*sigma^2 (irreducible floor)

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

driving ensemble variance toward this floor.

Two concepts behind Random Forests:

1. Wisdom of the crowd: large group of diverse experts > single expert

2. Diversification: uncorrelated set of trees reduces 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.

12
Machine Learning — Tom M. Mitchell

Bootstrap Sample D_b: sampled WITH REPLACEMENT from D, |D_b| = 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 x_i, predict using ONLY trees that did NOT train on x_i.

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)

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 = sqrt(p) (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.

13
Machine Learning — Tom M. Mitchell

FI(j) = (1/B) * SUM_b SUM_{t in T_b} [ Delta_impurity(t) * I(feature(t)=j) * p(t) ]

where:

Delta_impurity(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

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

14
Machine Learning — Tom M. Mitchell

p=3 features => m = sqrt(3) ~= 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

Med: {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 sqrt(p) for classification

max_depth Maximum depth of each tree None (fully grown)

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 & Disadvantages

15
Machine Learning — Tom M. Mitchell

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 trees Computationally expensive for very large datasets

Handles high-dimensional data and missing values well Biased toward features with more levels in categorical variables

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

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

Parallelisable — trees can be trained independently Slower prediction time vs linear models

16
Machine Learning — Tom M. Mitchell

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

When to Use Logistic Regression

Use when: (1) you need calibrated probability estimates, (2) the data is approximately linearly separable, (3)
interpretability of coefficients matters, (4) the dataset is large. It 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 (e.g. whether cells are cancerous, a
mouse is obese).

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 backprop]

P(y=1|x) = sigma(w^T*x + b)

P(y=0|x) = 1 - sigma(w^T*x + b)

Decision rule: predict class 1 if P(y=1|x) >= 0.5 <=> w^T*x + b >= 0

Threshold: values above threshold -> 1, values below -> 0

Threshold is typically 0.5 but can be tuned.

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.

17
Machine Learning — Tom M. Mitchell

Straight line: y = b0 + b1*x1 + b2*x2 + ... + bn*xn

Divide by (1-y): y/(1-y) = e^(b0 + b1*x1 + ...)

Take log: log(y/(1-y)) = b0 + b1*x1 + ... <- LOG-ODDS (logit)

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

Log-Odds: log(p/(1-p)) = w^T*x linear in x

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

Decision boundary: p = 0.5 <=> z = 0 <=> w^T*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)*SUM_i [ yi*log(y_hat_i) + (1-yi)*log(1-y_hat_i) ]

Gradient: dJ/dw = (1/N)*SUM_i (y_hat_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 sigmoid. Pass/Fail, Yes/No, Spam/Not Spam

Multinomial 3+, unord 3+ unordered outcomes. Uses Softmax. Cat / Dog / Bird

Ordinal 3+, ord 3+ ordered outcomes. Proportional odds. Low / Medium / High

Softmax (K classes): P(y=k|x) = exp(w_k^T*x) / SUM_j exp(w_j^T*x)

Categorical Cross-Entropy: J = -(1/N)*SUM_i SUM_k y_ik * log P(y=k|xi)

18
Machine Learning — Tom M. Mitchell

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 = SUM_k SUM_{x in C_k} ||x - mu_k||^2

Centroid: mu_k = (1/|C_k|) * SUM_{x in C_k} x

Euclidean (L2): d(x,y) = sqrt(SUM_i (x_i - y_i)^2) [most common]

Manhattan (L1): d(x,y) = SUM_i |x_i - y_i|

Maximum norm: d(x,y) = max_i |x_i - y_i|

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

19
Machine Learning — Tom M. Mitchell

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.

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

Unique examples per bootstrap sample ~= 63.2%

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

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)

4 medicines with 2 attributes each. Initial centroids: c1=(1,1) [Medicine A], c2=(2,1) [Medicine B].

20
Machine Learning — Tom M. Mitchell

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

Group1={A,B} c1=(1.5,1.0)

Group2={C,D} c2=(4.5,3.5)

Iter 2: No reassignments -> CONVERGED

Final: Group1={A,B} Group2={C,D}

5.6 Choosing K — Elbow Method, Silhouette, Gap Statistic

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.

21
Machine Learning — Tom M. Mitchell

May converge to local minimum — run multiple times with different seeds.

22
Machine Learning — Tom M. Mitchell

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(centroidA, centroidB) Can produce inversions in dendrogram

Ward's Linkage

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. Classic application:
market basket analysis. A rule has the form A -> B.

23
Machine Learning — Tom M. Mitchell

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

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.

24
Machine Learning — Tom M. Mitchell

CHAPTER 7

Principal Component Analysis (PCA)

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

7.1 Motivation & 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 ML model performance by eliminating noise dimensions.
Enables 2D/3D visualisation of high-dimensional data.
Limitation: components are linear combinations — not interpretable as individual features. Does not use
class labels (unsupervised). For supervised dim. reduction, use LDA.

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

25
Machine Learning — Tom M. Mitchell

Variance: Var(X) = (1/n) * SUM_i (x_i - x_bar)^2

Covariance: Cov(X,Y) = (1/n) * SUM_i (x_i - x_bar)(y_i - y_bar)

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(feature_i, feature_j) [d x d symmetric PSD]

Matrix form: C = (1/n) * X_c^T * X_c (X_c = centred data)

Eigenvalue equation: C * u = lambda * u

Characteristic eqn: det(C - lambda*I) = 0 (solve for eigenvalues)

Then solve: (C - lambda_k * I) * u_k = 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

7.3 PCA Step-by-Step Procedure

Step 1: Collect data X (n x 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 x d)

Step 5: Solve det(C - lambda*I) = 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 x K)

Step 8: Project: Z = X_c * U (n x 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).

26
Machine Learning — Tom M. Mitchell

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_c^T*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 - lambda*I) = 0:

lambda^2 - 8.584*lambda + 3.080 = 0

=> lambda_1 = 8.22 lambda_2 = 0.38

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

Step 6: Eigenvector for lambda_1 = 8.22:

(C - 8.22I)*u = 0 => 5.3*u1 = 3.667*u2 => u1 = 0.692*u2

Normalise (u1^2+u2^2=1): u2=0.822, u1=0.569

PC1 = [0.569, 0.822]

Step 7: Project onto PC1 (z_i = X_c_i . PC1):

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

7.5 PCA Sample Problem — From Class Notes

Two attributes X and Y, each sampled three times. Combined into matrix S:

X = [1, 0, -1]^T Y = [-1, 1, 0]^T

S = [[1, -1], (3 x 2 matrix of attribute vectors)

[0, 1],

[-1, 0]]

Un-normalised Covariance Matrix C = S^T * S:

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

[-1,1,0]] [0, 1], [-1, 2]]

[-1, 0]]

C = [[2,-1],

[-1,2]]

Eigenvalues — solve det(C - lambda*I) = 0:

|2-lambda -1 |

|-1 2-lambda| = 0

(2-lambda)^2 - 1 = lambda^2 - 4*lambda + 3 = 0

=> lambda_1 = 3 (larger) lambda_2 = 1 (smaller)

27
Machine Learning — Tom M. Mitchell

Eigenvectors (solve (C - lambda*I)*u = 0 for each lambda):

For lambda_2 = 1:

(C - I)*u = [[1,-1],[-1,1]]*[u1,u2]^T = 0

=> u1 = u2

Normalised: v = (1/sqrt(2)) * [1, 1]^T

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

(C - 3I)*u = [[-1,-1],[-1,-1]]*[u1,u2]^T = 0

=> u1 = -u2

Normalised: u = (1/sqrt(2)) * [1, -1]^T

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

=> u is the FIRST PRINCIPAL COMPONENT direction

Principal Component Matrix P = S * U:

U = (1/sqrt(2)) * [[1, 1], [-1, 1]] (eigenvectors as columns)

P = (1/sqrt(2)) * [[1,-1],[0,1],[-1,0]] * [[1,1],[-1,1]]

= (1/sqrt(2)) * [[2, 0],[-1, 1],[-1,-1]]

P1 = (1/sqrt(2)) * [2, -1, -1]^T (projection onto PC1)

P2 = (1/sqrt(2)) * [0, 1, -1]^T (projection onto PC2)

Verification: P^T * P = diag(lambda_1, lambda_2) = [[3, 0],[0, 1]]

Reconstruction: P * U^T = 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 = SUM_{k=K+1}^{d} lambda_k (sum of discarded eigenvalues).
Verify your calculation: P^T * P should equal diag(lambda_1, lambda_2, ...) — off-diagonals must be zero.
Related techniques: ICA (non-Gaussian independence), Multidimensional Scaling (preserves inter-point
distances), LDA (maximises class separation).

28
Machine Learning — Tom M. Mitchell

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: x_1(t) = a_11*s_1(t) + a_12*s_2(t)

x_2(t) = a_21*s_1(t) + a_22*s_2(t)

Matrix form: x = A * s

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

s : original source signals (n x 1) -- UNKNOWN

A : mixing matrix (n x n) -- UNKNOWN

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

BSS Pipeline: s_1,...,s_n --[A]--> x_1,...,x_n --[W]--> u_1,...,u_n

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

x_j = a_j1*s_1 + a_j2*s_2 + ... + a_jn*s_n for all j

In columns of matrix A: x = SUM_{i=1}^{n} a_i * s_i

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

29
Machine Learning — Tom M. Mitchell

Assumption 1: The components s_1, ..., s_n are statistically independent: p(s_1,...,s_n) = product p(s_i).
Assumption 2: The independent components must have non-Gaussian distributions — at most one
source may be Gaussian.
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{y^4} - 3*(E{y^2})^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(y_Gaussian) - 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 s_i by scalar c and dividing the corresponding column
a_i of A by c leaves x unchanged: (a_i/c)*(c*s_i) = a_i*s_i. Resolution: fix unit variance E{s_i^2} = 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. Swapping s_1 and s_2 while swapping columns a_1 and
a_2 produces the exact same mixture x. 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.

30
Machine Learning — Tom M. Mitchell

8.6 Statistical Illustration of ICA

Two independent components with uniform distributions:

p(s_i) = 1/(2*sqrt(3)) if |s_i| <= sqrt(3), else 0

This distribution has zero mean and variance = 1.

Mixing matrix: A_0 = [[2, 3],

[2, 1]]

x_1 = 2*s_1 + 3*s_2

x_2 = 2*s_1 + 1*s_2

Joint distribution of (s_1, s_2): SQUARE shape (independent uniform sources)

Joint distribution of (x_1, x_2): PARALLELOGRAM shape

Key insight: The EDGES of the parallelogram are the COLUMNS of A_0!

Column 1 of A_0 = [2, 2]^T => direction (2,2) = one edge

Column 2 of A_0 = [3, 1]^T => direction (3,1) = other edge

This means: in principle, estimate ICA by finding joint density of (x_1,x_2)

and locating the edges. HOWEVER: this only works for uniform distributions

and is computationally complex. We need a method that works for ANY distribution.

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 - tanh^2(u)

g(u) = u*exp(-u^2/2) g'(u) = (1-u^2)*exp(-u^2/2)

3. Orthogonalise: w_i = w_i - SUM_{j lt i} (w_i^T*w_j)*w_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

31
Machine Learning — Tom M. Mitchell

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

Similarity Feature extraction Feature extraction

Similarity Dimension reduction Dimension reduction

32
Machine Learning — Tom M. Mitchell

CHAPTER —

Quick Reference Formula Sheet

Key equations from all chapters — compact reference for study and review.

Linear Models & SVM

y = w^T.x + b

MSE: L = (1/N).SUM(yi - y_hati)^2

SVM hard-margin: min (1/2)||w||^2 s.t. yi([Link]+b) >= 1

SVM soft-margin: min (1/2)||w||^2 + [Link] s.t. yi([Link]+b) >= 1-xii

RBF Kernel: K(x,z) = exp(-gamma||x-z||^2)

Dual classifier: f(x) = sign(SUM [Link].K(xi,x) + b)

Decision Trees
Entropy: E(S) = -SUM pi.log2(pi)

Info Gain: G(S,A) = E(S) - SUMv (|Sv|/|S|).E(Sv)

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

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

Random Forests
m (classification) = sqrtp m (regression) = p/3

OOB fraction ~= 36.8% | Unique per tree ~= 63.2%

Predict (class): majority_vote { T1(x),...,TB(x) }

FI(j) = (1/B).SUMb SUMt [ Deltaimpurity(t).I(feature(t)=j).p(t) ]

Logistic Regression

33
Machine Learning — Tom M. Mitchell

sigma(z) = 1/(1+e^(-z))

Log-Odds: log(p/(1-p)) = w^T.x

Cross-Entropy: J = -(1/N).SUM[[Link](y_hat)+(1-yi).log(1-y_hat)]

Softmax: P(y=k|x) = exp(wk^T.x) / SUMj exp(wj^T.x)

K-Means Clustering
Assignment: c(i) = argmin_k ||x(i) - muk||^2

Update: muk = (1/|Ck|).SUM_{xinCk} x

WCSS: J = SUMk SUM_{xinCk} ||x - muk||^2

Association Rules
Support(A->B) = count(A and B) / N

Confidence(A->B) = count(A and B) / count(A)

Lift(A->B) = Confidence(A->B) / Support(B)

PCA
C = (1/n).Xc^[Link]

Eigendecomp: C.u = lambda.u <=> det(C-lambdaI) = 0

Projection: Z = Xc.U (U = top-K eigenvectors)

Var explained: lambdak / SUMi lambdai

Reconstruct: X_approx = Z.U^T + mu

ICA
Mixing: x = A.s Demixing: u = W.x = A^(-1).x

Independence: p(s1,...,sn) = p(s1).....p(sn)

Kurtosis: kurt(y) = E{y^4} - 3.(E{y^2})^2

Negentropy: J(y) = H(yGauss) - H(y) >= 0

FastICA: w = E{x.g(w^T.x)} - E{g'(w^T.x)}.w

34
Machine Learning — Tom M. Mitchell

CHAPTER —

Algorithm Comparison & Summary

Master reference tables for algorithm selection, comparison, and entropy values.

Master Algorithm Reference

Algorithm Type Task Key Parameters Loss / Criterion

Linear Regression Supervised Regression w, b MSE

Logistic Regression Supervised Classification w, b Cross-Entropy

SVM Supervised Classification C, kernel, gamma Hinge Loss

Decision Tree Supervised Class./Regr. max_depth, crit. Entropy/Gini

Random Forest Supervised Class./Regr. B, m features Gini/Entropy

K-Means Unsupervised Clustering K WCSS

K-Medoids Unsupervised Clustering K Total Distance

Hierarchical Unsupervised Clustering Linkage Distance

PCA Unsupervised Dim. Reduction K components Var Captured

ICA Unsupervised Signal Sep. n components Non-Gaussianity

Decision Tree vs Random Forest

Criterion Decision Tree Random Forest

Model type Single model Ensemble (B trees)

Overfitting High tendency Low tendency

Variance High Low

Bias Low Low

Interpretability High (visual rules) Low (black box)

Training speed Fast Slower (B trees)

Prediction accuracy Moderate High

Feature selection All features / node Random m / node

35
Machine Learning — Tom M. Mitchell

Criterion Decision Tree Random Forest

Noise robustness Low High

Model Selection Guide

Situation Best Algorithm Key Reason

Continuous output, linear data Linear Regression Efficient, closed-form solution

Binary classification, need probability Logistic Regression Probabilistic output (0–1)

Non-linear classification SVM + RBF Kernel Kernel maps to high-dim space

Need interpretable rules Decision Tree Visual if-then structure

Highest accuracy classification Random Forest Ensemble, low variance

Group unlabelled numeric data K-Means Simple, fast, scalable

Clustering, K unknown Hierarchical Dendrogram — cut any level

Reduce feature dimensions PCA Preserves maximum variance

Separate mixed signals ICA Statistical independence

Clustering with outliers K-Medoids Robust to extreme values

Entropy Quick Reference

Distribution Entropy Notes

All same class (pure) 0 bits log2(1) = 0

Binary 50/50 split 1.000 bits Maximum entropy for 2 classes

Binary 9/14 vs 5/14 0.940 bits PlayTennis full set

Binary 2/5 vs 3/5 0.971 bits Sunny/Rain subsets

Pure 4/4 vs 0/4 0 bits Overcast — pure leaf

3 equal classes 1.585 bits log2(3)

c equal classes log2(c) bits Maximum entropy formula

36