Machine Learning

Machine learning is a branch of artificial intelligence in which a computer learns patterns from data and improves its performance on a task with experience, without being explicitly programmed with rules. Formally (Mitchell): a program learns from experience $E$ with respect to task $T$ and performance measure $P$ if its performance on $T$, measured by $P$, improves with $E$.

Types of learning

1. Supervised learning: The training data contains inputs together with the correct labels. The model learns a mapping $x \rightarrow y$. Classification (spam or not spam) predicts discrete labels and regression (house price) predicts continuous values. Examples: linear regression, decision tree, SVM, Naive Bayes, k-NN.
2. Unsupervised learning: The data has no labels. The model finds hidden structure such as clusters or lower-dimensional representations. Examples: k-means, hierarchical clustering, PCA, association rules.
3. Semi-supervised learning: A small amount of labelled data is combined with a large amount of unlabelled data (e.g. image classification with few labelled photos).
4. Reinforcement learning: An agent interacts with an environment, takes actions and receives rewards or penalties. It learns a policy that maximises cumulative reward (game playing, robotics, self-driving).

Clustering is an unsupervised learning technique that groups unlabelled data objects into clusters so that objects in the same cluster are highly similar to each other and dissimilar to objects in other clusters. Similarity is usually measured by a distance such as Euclidean distance. Uses include customer segmentation, document grouping and image segmentation.

Approaches to clustering

• Partitioning methods: Divide $n$ objects into $k$ clusters (k is given in advance) and iteratively improve the partition, e.g. k-means and k-medoids.
• Hierarchical methods: Build a tree of clusters (dendrogram). Agglomerative (bottom-up) merges the closest clusters step by step; divisive (top-down) splits one big cluster repeatedly.
• Density-based methods: Clusters are dense regions separated by sparse regions. They find arbitrary-shaped clusters and handle noise, e.g. DBSCAN, OPTICS.
• Grid-based methods: The space is divided into a grid of cells and clustering is done on cells, which is fast, e.g. STING.
• Model-based methods: Assume data comes from a mixture of probability distributions and fit them, e.g. Gaussian Mixture Models with EM.

Sensitivity (recall, true positive rate) is the proportion of actual positives that the model correctly identifies:

$\text{Sensitivity} = \frac{TP}{TP + FN}$

Specificity (true negative rate) is the proportion of actual negatives that the model correctly identifies:

$\text{Specificity} = \frac{TN}{TN + FP}$

Confusion matrix is a table that compares actual classes with predicted classes of a classifier.

Example: A disease test on 100 people gives TP = 40, FN = 10, FP = 5, TN = 45.

• Accuracy $= (40+45)/100 = 0.85$
• Sensitivity $= 40/(40+10) = 0.80$
• Specificity $= 45/(45+5) = 0.90$
• Precision $= 40/(40+5) = 0.889$

Thus the test detects 80% of the sick people and correctly clears 90% of the healthy ones.

Linear regression is a supervised learning method that models the relationship between a dependent variable $y$ and one or more independent variables $x$ by fitting a straight line (hyperplane). For one feature the hypothesis is

$h_\theta(x) = \theta_0 + \theta_1 x$

The parameters are chosen to minimise the cost function (mean squared error):

$J(\theta_0,\theta_1) = \frac{1}{2m}\sum_{i=1}^{m}\left(h_\theta(x^{(i)}) - y^{(i)}\right)^2$

Gradient descent is an iterative optimisation algorithm that finds the parameters minimising $J$.

1. Initialise $\theta_0,\theta_1$ (e.g. with 0 or random values).
2. Choose learning rate $\alpha$.
3. Repeat until convergence, updating all parameters simultaneously:

$\theta_0 := \theta_0 - \alpha\frac{1}{m}\sum_{i=1}^{m}\left(h_\theta(x^{(i)})-y^{(i)}\right)$

$\theta_1 := \theta_1 - \alpha\frac{1}{m}\sum_{i=1}^{m}\left(h_\theta(x^{(i)})-y^{(i)}\right)x^{(i)}$

4. Stop when $J$ stops decreasing noticeably or after a fixed number of iterations.

The gradient gives the direction of steepest increase, so moving opposite to it reduces the cost. If $\alpha$ is too small, convergence is slow; if too large, the algorithm may overshoot and diverge. For linear regression $J$ is convex, so gradient descent reaches the global minimum. Variants are batch, stochastic and mini-batch gradient descent.

• Training set: The portion of data used to fit the model, i.e. to learn the parameters (weights). Typically about 60-70%.
• Validation set: Data not used for fitting, used to tune hyperparameters (such as k, tree depth, learning rate), to select among models and to detect over-fitting. Typically 15-20%.
• Test set: Data kept completely unseen until the end, used once to estimate the final generalisation performance of the chosen model. Typically 15-20%.

Training vs testing

The line of best fit is the straight line that best represents the relationship between two variables in a scatter plot. It passes as close as possible to all the data points and is used to predict $y$ for a given $x$.

$\hat{y} = a + bx$

It is found by the least squares method, which minimises the sum of squared residuals $\sum (y_i - \hat{y}_i)^2$, where the residual is the vertical distance between an observed point and the line. The coefficients are

$b = \frac{n\sum xy - \sum x \sum y}{n\sum x^2 - (\sum x)^2}, \qquad a = \bar{y} - b\bar{x}$

Properties

• It always passes through the mean point $(\bar{x},\bar{y})$.
• The sum of residuals is zero.
• Slope $b$ shows the change in $y$ per unit change in $x$; the intercept $a$ is the value of $y$ at $x=0$.
• The closeness of fit is measured by the correlation coefficient $r$ or $R^2$.

Example: For points (1,2), (2,4), (3,5), (4,6), (5,8): $\bar{x}=3,\bar{y}=5$, $b = 14/10 = 1.4$, $a = 0.8$, so the line is $\hat{y}=0.8+1.4x$.

In machine learning the same line is obtained by linear regression using the normal equation or gradient descent.

Naive Bayes is a probabilistic supervised classifier based on Bayes' theorem with the "naive" assumption that all features are conditionally independent given the class.

How it works

For a class $C_k$ and feature vector $X=(x_1,\dots,x_n)$:

$P(C_k\mid X) = \frac{P(X\mid C_k)\,P(C_k)}{P(X)}$

With independence assumed,

$P(X\mid C_k)=\prod_{i=1}^{n}P(x_i\mid C_k)$

Steps:

1. Compute the prior $P(C_k)$ of each class from training data.
2. Compute the likelihood $P(x_i\mid C_k)$ of each feature value for each class (use Laplace smoothing to avoid zero probabilities).
3. For a new instance, compute $P(C_k)\prod_i P(x_i\mid C_k)$ for every class.
4. Predict the class with the largest value (the denominator $P(X)$ is common and can be ignored).

Merits

• Simple, very fast to train and predict.
• Works well with small training data and high-dimensional data (text, spam filtering).
• Handles multi-class problems and both discrete and continuous features.

Demerits

• The independence assumption rarely holds in real data.
• Zero-frequency problem unless smoothing is used.
• Probability estimates are often poor; continuous features need distribution assumptions (e.g. Gaussian).

K-means algorithm

1. Choose the number of clusters $k$ and select $k$ initial centroids.
2. Assign each object to the nearest centroid (Euclidean distance).
3. Recompute each centroid as the mean of the objects assigned to it.
4. Repeat steps 2-3 until the assignments (centroids) no longer change.

Solution ($k=2$): take $O_1(1,1.5)$ and $O_2(1,4.5)$ as the initial centroids $C_1,C_2$.

Iteration 1 (distances to $C_1(1,1.5)$ and $C_2(1,4.5)$)

New centroids:

$C_1 = \left(\frac{1+2+3}{3},\frac{1.5+1.5+2.5}{3}\right) = (2,\,1.83)$

$C_2 = \left(\frac{1+2+3}{3},\frac{4.5+3.5+4}{3}\right) = (2,\,4.0)$

Iteration 2 (distances to $C_1(2,1.83)$ and $C_2(2,4)$)

The assignments are unchanged, so the algorithm has converged.

Final clusters: Cluster 1 = {O1, O3, O5} with centroid (2, 1.83); Cluster 2 = {O2, O4, O6} with centroid (2, 4.0).

Perceptron

A perceptron is the simplest artificial neuron and a linear binary classifier. It computes a weighted sum of inputs plus bias and passes it through a step activation:

$y = f\left(\sum_{i=1}^{n} w_i x_i + b\right), \qquad f(z)=\begin{cases}1 & z\ge 0\\ 0 & z<0\end{cases}$

Learning rule: $w_i \leftarrow w_i + \eta\,(t-y)\,x_i$, where $t$ is the target and $\eta$ the learning rate. It can only solve linearly separable problems (AND, OR but not XOR). Multi-layer perceptrons overcome this using hidden layers and the back propagation algorithm.

Back propagation algorithm

Back propagation trains a multilayer feed-forward network by gradient descent on the error, propagating the error backward from output to input.

1. Initialise weights and biases with small random values.
2. Forward pass: for each training example, compute hidden outputs $o_j=\sigma(\sum w_{ij}x_i+b_j)$ and then output outputs $o_k$, with $\sigma(z)=1/(1+e^{-z})$.
3. Compute error at the output: $\delta_k = o_k(1-o_k)(t_k-o_k)$.
4. Backward pass: for each hidden unit $j$, $\delta_j = o_j(1-o_j)\sum_k w_{jk}\delta_k$.
5. Update weights: $w_{ij} \leftarrow w_{ij} + \eta\,\delta_j\,o_i$ and biases $b_j \leftarrow b_j + \eta\,\delta_j$.
6. Repeat for all examples (epochs) until the error is small enough.

Example: Network with inputs $x_1=1, x_2=0$, one hidden neuron $h$ with $w_{1h}=0.5, w_{2h}=0.4$, $b_h=0$, and an output neuron with $w_{ho}=0.3$, $b_o=0$, target $t=1$, $\eta=0.5$.

• Forward: $z_h=0.5$, $o_h=\sigma(0.5)=0.622$; $z_o=0.3(0.622)=0.187$, $o_o=\sigma(0.187)=0.547$.
• Output error: $\delta_o = 0.547(0.453)(1-0.547)=0.112$.
• Hidden error: $\delta_h = 0.622(0.378)(0.3)(0.112)=0.0079$.
• Updates: $w_{ho}=0.3+0.5(0.112)(0.622)=0.335$; $w_{1h}=0.5+0.5(0.0079)(1)=0.504$; $w_{2h}$ stays 0.4 (since $x_2=0$).

The next forward pass gives an output closer to 1, so the error decreases.

How SVM works

A Support Vector Machine is a supervised classifier that finds the hyperplane $w^Tx+b=0$ that separates two classes with the maximum margin. Points closest to the hyperplane are the support vectors; only they determine the boundary. For non-separable data, a soft margin (parameter $C$) allows some errors, and the kernel trick (polynomial, RBF) maps the data to a higher-dimensional space where a linear separation is possible. Prediction: class $+1$ if $w^Tx+b>0$, else $-1$.

Functional margin

For a training example $(x^{(i)},y^{(i)})$ with $y^{(i)}\in\{-1,+1\}$:

$\hat{\gamma}^{(i)} = y^{(i)}\left(w^Tx^{(i)}+b\right)$

A large positive value means a confident and correct prediction. For the training set it is $\hat\gamma=\min_i\hat\gamma^{(i)}$. It can be made arbitrarily large by scaling $(w,b)$, so it is not a true distance.

Geometric margin

The actual Euclidean distance of a point from the hyperplane:

$\gamma^{(i)} = y^{(i)}\left(\frac{w^T}{\|w\|}x^{(i)}+\frac{b}{\|w\|}\right)$

It is invariant to scaling of $(w,b)$.

Relationship

$\gamma^{(i)}=\frac{\hat{\gamma}^{(i)}}{\|w\|}$

If $\|w\|=1$ the two margins are equal.

Optimum margin classifier

It chooses $w,b$ to maximise the geometric margin $\gamma$. Fixing the functional margin $\hat\gamma=1$ (by scaling), maximising $\gamma=1/\|w\|$ is equivalent to the convex quadratic problem

$\min_{w,b}\ \frac12\|w\|^2 \quad \text{subject to}\quad y^{(i)}(w^Tx^{(i)}+b)\ge 1,\ \forall i$

Solved through its Lagrangian dual, $w=\sum_i\alpha_i y^{(i)}x^{(i)}$ where $\alpha_i>0$ only for support vectors. The resulting classifier has the widest possible gap between the classes and hence good generalisation.

Over-fitting occurs when a model learns the training data too well, including its noise and random fluctuations, so it has very low training error but high error on unseen data. It happens when the model is too complex relative to the amount of data (high variance, low bias). It is identified by a large gap between training and validation/test accuracy.

Example: Fitting a degree-9 polynomial through 10 noisy points lying roughly on a line gives zero training error, but the curve wiggles wildly and predicts new points badly, whereas a straight line generalises well. Similarly, a decision tree grown until every leaf is pure may memorise the training set and give 100% training but 70% test accuracy.

Prevention

• Collect more training data.
• Use a simpler model (fewer features, lower polynomial degree, smaller network).
• Regularisation (L1/L2 penalty on weights, dropout in neural networks).
• Cross-validation and a separate validation set to tune hyperparameters.
• Early stopping when validation error starts rising.
• Pruning for decision trees.
• Feature selection or dimensionality reduction.
• Ensemble methods such as bagging and random forests.

Perceptron

A perceptron is a single artificial neuron and the simplest linear binary classifier. It takes inputs $x_1,\dots,x_n$ with weights $w_i$ and bias $b$, and outputs

$y=\begin{cases}1 & \sum_i w_ix_i+b\ge 0\\ 0 & \text{otherwise}\end{cases}$

Weights are learned with $w_i \leftarrow w_i+\eta(t-y)x_i$, where $t$ is the target output and $\eta$ the learning rate. It converges only if the classes are linearly separable.

K-means clustering

K-means is an unsupervised partitioning algorithm that divides data into $k$ clusters.

1. Select $k$ and choose $k$ initial centroids (randomly).
2. Assign every point to the nearest centroid using Euclidean distance.
3. Recompute each centroid as the mean of its assigned points.
4. Repeat steps 2 and 3 until centroids stop changing (or a maximum number of iterations is reached).

It minimises the within-cluster sum of squares $\sum_{j=1}^{k}\sum_{x\in C_j}\|x-\mu_j\|^2$. It is simple and fast, but needs $k$ in advance, is sensitive to initial centroids and outliers, and finds only spherical clusters.

Naive Bayes

Strengths

• Very fast training and prediction; needs only counting of frequencies.
• Works well with small datasets and very high-dimensional data such as text classification and spam filtering.
• Naturally multi-class and gives probabilistic outputs.
• Few hyperparameters and little tuning.

Weaknesses

• The conditional independence assumption is rarely true; correlated features reduce accuracy.
• Zero-probability problem unless smoothing is used.
• Cannot learn interactions between features.
• Probability estimates are poorly calibrated.

Comparison with SVM

Naive Bayes is preferred for quick baselines and small or text data; SVM for higher accuracy when features are interdependent.

Why dimensionality reduction is useful

• Reduces the curse of dimensionality: with many features, data becomes sparse and models over-fit.
• Lowers storage, memory and training time.
• Removes redundant, correlated and noisy features, improving accuracy.
• Makes visualisation possible by reducing data to 2D or 3D.
• Makes models simpler and easier to interpret.

Methods: PCA, LDA, t-SNE, feature selection.

Choosing an algorithm for a given data set

No single algorithm is best (no free lunch), so the choice is guided by the data and the problem:

1. Type of problem: labelled target with categories gives classification, numeric target gives regression, no labels gives clustering or dimensionality reduction, sequential decisions give reinforcement learning.
2. Size of data: small data suits Naive Bayes, linear models, k-NN; large data suits neural networks, gradient boosting.
3. Number and type of features: many features suit linear models, SVM or regularised models; mixed categorical features suit decision trees.
4. Linearity: linear relationship gives linear/logistic regression; non-linear gives SVM with kernel, trees, neural networks.
5. Interpretability needed: decision trees and linear models over black-box models.
6. Speed and resources for training and prediction.
7. Experimentation: try a few candidate models, compare them by cross-validation using suitable metrics (accuracy, F1, RMSE), tune hyperparameters and pick the best one that does not over-fit.

This justifies choosing by data characteristics plus empirical validation rather than by a fixed rule.

ROC curve

The Receiver Operating Characteristic (ROC) curve plots the True Positive Rate (sensitivity, $TP/(TP+FN)$) on the y-axis against the False Positive Rate ($FP/(FP+TN)$) on the x-axis for all possible classification thresholds. A curve close to the top-left corner indicates a good classifier; the diagonal represents random guessing. The area under the curve (AUC) summarises performance: 1 is perfect, 0.5 is no better than chance.

Fraud detection calculation

• Flagged as fraud = 50, of which truly fraud: $TP=45$, so $FP=50-45=5$.
• Fraudulent transactions not flagged: $FN=30$.

$\text{Precision}=\frac{TP}{TP+FP}=\frac{45}{50}=0.90$

$\text{Recall}=\frac{TP}{TP+FN}=\frac{45}{75}=0.60$

$F1=\frac{2\times 0.90\times 0.60}{0.90+0.60}=\frac{1.08}{1.5}=0.72$

So precision is 90%, recall 60% and F1-score 0.72. The system is accurate when it flags, but misses 40% of the frauds.

Hierarchical clustering builds a hierarchy (tree) of clusters, shown as a dendrogram, without needing the number of clusters in advance.

• Agglomerative (bottom-up): start with each object as its own cluster; repeatedly merge the two closest clusters until one cluster remains.
• Divisive (top-down): start with all objects in one cluster; repeatedly split until each object is separate.

Distance between clusters is measured by single linkage (minimum), complete linkage (maximum), average linkage or centroid distance. Cutting the dendrogram at a chosen height gives the desired number of clusters.

Using regression to find the best-fit line

Linear regression models $\hat y=\theta_0+\theta_1x$ and finds the parameters that minimise the sum of squared errors between actual and predicted values:

$J=\sum_{i=1}^{m}\left(y_i-\theta_0-\theta_1x_i\right)^2$

Setting the partial derivatives to zero gives

$\theta_1=\frac{\sum(x_i-\bar x)(y_i-\bar y)}{\sum(x_i-\bar x)^2},\qquad \theta_0=\bar y-\theta_1\bar x$

(or the same result is reached iteratively by gradient descent). The resulting line passes through $(\bar x,\bar y)$ and is the line of best fit, which can then predict $y$ for new $x$.

(a) Supervised vs. unsupervised learning

(b) Sensitivity and specificity

Sensitivity (true positive rate) is the fraction of actual positives correctly detected, $TP/(TP+FN)$. Specificity (true negative rate) is the fraction of actual negatives correctly identified, $TN/(TN+FP)$. They are derived from the confusion matrix and are used especially in medical testing: a highly sensitive test rarely misses disease, a highly specific test rarely gives false alarms. Raising one usually lowers the other, as shown on the ROC curve.

(c) Bayesian belief network

A Bayesian belief network is a directed acyclic graph in which nodes represent random variables and edges represent conditional (causal) dependencies. Each node has a conditional probability table $P(X\mid \text{Parents}(X))$. The joint probability is

$P(x_1,\dots,x_n)=\prod_{i=1}^{n}P\left(x_i\mid \text{Parents}(x_i)\right)$

It allows reasoning under uncertainty, such as computing the probability of disease given symptoms, and unlike Naive Bayes it permits dependencies between variables.

Need of the confusion matrix

Accuracy alone can be misleading, especially for imbalanced data (a model predicting "no fraud" always can be 99% accurate). The confusion matrix tabulates actual versus predicted classes:

It is needed because

• it shows the types of errors (false positives and false negatives), which have different costs;
• it allows computing accuracy $=\frac{TP+TN}{TP+TN+FP+FN}$, precision $=\frac{TP}{TP+FP}$, recall $=\frac{TP}{TP+FN}$, specificity and F1-score;
• it shows which classes are confused with each other in multi-class problems;
• it helps compare models and choose thresholds.

Framework for building a machine learning system

1. Problem definition: state the goal, the task type (classification, regression, clustering) and the success metric.
2. Data collection: gather relevant data from databases, sensors, web, surveys.
3. Data preparation (pre-processing): clean missing values, noise and duplicates; encode categorical data; scale/normalise.
4. Exploratory analysis and feature engineering: visualise, select, extract or reduce features.
5. Splitting data: into training, validation and test sets.
6. Model selection and training: choose candidate algorithms and fit them to the training set.
7. Evaluation and tuning: assess on validation data (cross-validation, confusion matrix, ROC) and tune hyperparameters; handle over/under-fitting.
8. Testing: measure final performance on the unseen test set.
9. Deployment: integrate the model into an application or service.
10. Monitoring and maintenance: track performance, detect data drift and retrain with new data.

The process is iterative; results at later steps often send the developer back to earlier steps.

Entropy measures the impurity (uncertainty) of a set $S$ of examples:

$H(S)=-\sum_{i}p_i\log_2 p_i$

It is 0 for a pure set and 1 for a two-class set split equally.

Information gain is the expected reduction in entropy after splitting on attribute $A$:

$IG(S,A)=H(S)-\sum_{v\in A}\frac{|S_v|}{|S|}H(S_v)$

ID3 selects, at each node, the attribute with the highest information gain.

Construction

Data: 3 Yes (days 1, 3, 5) and 2 No (days 2, 4).

$H(S)=-\tfrac35\log_2\tfrac35-\tfrac25\log_2\tfrac25=0.971$

Outlook: Sunny {Yes, No} gives $H=1$; Overcast {Yes} gives $0$; Rain {No, Yes} gives $1$.

$IG=0.971-\left(\tfrac25(1)+\tfrac15(0)+\tfrac25(1)\right)=0.171$

Temperature: Hot {Y, N, Y} gives $H=0.918$; Mild {N} gives $0$; Cold {Y} gives $0$.

$IG=0.971-\tfrac35(0.918)=0.971-0.551=0.420$

Humidity: High {Y, N, Y, N} gives $H=1$; Normal {Y} gives $0$.

$IG=0.971-\tfrac45(1)=0.171$

Wind: Weak {Y, Y, N, Y} gives $H=0.811$; Strong {N} gives $0$.

$IG=0.971-\tfrac45(0.811)=0.322$

Temperature has the highest gain (0.420), so it is the root.

• Mild gives No (pure).
• Cold gives Yes (pure).
• Hot contains days 1, 2, 3 {Y, N, Y}. Splitting by Wind: Weak (days 1, 3) gives Yes and Strong (day 2) gives No, so gain is highest and the subtree is pure.

Decision tree

Temperature
├── Mild  -> No
├── Cold  -> Yes
└── Hot   -> Wind
              ├── Weak   -> Yes
              └── Strong -> No

Bias-variance trade-off

The expected prediction error of a model can be decomposed as

$\text{Error}=\text{Bias}^2+\text{Variance}+\text{Irreducible noise}$

• Bias is the error from wrong or over-simple assumptions; high bias causes under-fitting.
• Variance is the sensitivity of the model to small changes in the training data; high variance causes over-fitting.

Making a model more complex lowers bias but raises variance, and a simpler model does the opposite. The trade-off is to choose the complexity that minimises total error, usually found with validation.

K-NN algorithm

1. Choose $k$.
2. Compute the distance (Euclidean) between the query and each training example.
3. Take the $k$ nearest examples.
4. Predict the majority class (or the average for regression).

Applying it to the table

The query Sija $=\{\text{Machine Learning}=60,\ \text{GIS}=80\}$ is described by two numeric marks, but the given table has the categorical attributes Outlook, Temperature, Humidity and Wind, and contains no Machine Learning or GIS values. Distances between Sija and the five days therefore cannot be computed from the table as it stands. With the table's own attributes, a new day is classified as follows: encode each attribute, count the number of mismatching attributes (Hamming distance) to every day, pick the $k$ closest days (for example $k=3$) and take the majority of their Decision values. For a query with numeric attributes such as Sija, the distance to a training record $(a,b)$ would be $d=\sqrt{(60-a)^2+(80-b)^2}$, and the Decision of the majority of the $k$ nearest records would be assigned to Sija.

Bias-variance trade-off

The expected error of a model on unseen data is

$\text{Error}=\text{Bias}^2+\text{Variance}+\text{Irreducible error}$

• Bias is the error caused by overly simple assumptions (under-fitting).
• Variance is the error caused by sensitivity to the particular training sample (over-fitting).

The trade-off: lowering one tends to raise the other, so the best model balances the two to minimise total error.

Effect of increasing complexity

• Low complexity: a linear model fitted to curved (quadratic) data has high bias and low variance. It under-fits and gives high error on both training and test data.
• Moderate complexity: a degree-2 polynomial matches the true pattern; bias and variance are both low, so test error is lowest.
• High complexity: a degree-10 polynomial or a very deep decision tree fits the training noise: bias is very low, variance is high, training error is near zero but test error rises.

So as complexity increases, bias decreases and variance increases. Test error is U-shaped, and the optimum is at the bottom of the U. Regularisation, more data and cross-validation help control it.

Decision tree algorithm

A decision tree is a supervised model (classification and regression) that represents decisions as a tree: internal nodes test an attribute, branches are the outcomes of the test, and leaf nodes hold the class label or value.

Building (top-down, recursive, e.g. ID3, C4.5, CART):

1. Start with all training examples at the root.
2. Select the best attribute using a splitting measure: information gain (entropy) in ID3, gain ratio in C4.5, or Gini index in CART.
3. Split the data by the attribute's values into child nodes.
4. Repeat recursively on each child until the node is pure, no attributes remain, or a stopping condition is met.
5. Prune the tree to avoid over-fitting.

To classify a new example, follow the tests from the root to a leaf.

Advantages

• Easy to understand and interpret; can be visualised and converted to rules.
• Handles numeric and categorical data with little pre-processing (no scaling).
• Captures non-linear relationships and feature interactions.
• Fast prediction.

Disadvantages

• Prone to over-fitting without pruning.
• Unstable: small changes in data can produce a very different tree.
• Greedy splitting may not give the globally optimal tree.
• Biased toward attributes with many values; poor for imbalanced classes.

Structure of a neural network

An artificial neural network consists of layers of interconnected neurons:

• Input layer: one neuron per feature; passes the inputs on.
• Hidden layer(s): neurons compute $a=f\left(\sum w_ix_i+b\right)$ using weights $w$, bias $b$ and a non-linear activation $f$ (sigmoid, tanh, ReLU).
• Output layer: produces the prediction (sigmoid or softmax for classes, linear for regression).

Each connection has a weight; the weights and biases are the parameters learned.

Learning process in supervised learning

1. Initialise weights randomly.
2. Forward propagation: feed a training input through the layers to get the predicted output $\hat y$.
3. Compute loss: compare with the true label $y$ using a loss function such as mean squared error or cross-entropy.
4. Back propagation: propagate the error backward using the chain rule to compute the gradient of the loss with respect to every weight.
5. Update weights by gradient descent: $w\leftarrow w-\eta\,\dfrac{\partial L}{\partial w}$, with learning rate $\eta$.
6. Repeat over all training examples (epochs, usually in mini-batches) until the loss converges or validation error stops improving.

Finally the network is evaluated on unseen test data; regularisation, dropout and early stopping reduce over-fitting.

(a) Data (already sorted, $n=10$): 22, 25, 29, 30, 31, 33, 35, 36, 40, 45

• Minimum $=22$
• Maximum $=45$
• Median $=\dfrac{31+33}{2}=32$ (average of the 5th and 6th values)
• $Q_1$ = median of the lower half (22, 25, 29, 30, 31) $=29$
• $Q_3$ = median of the upper half (33, 35, 36, 40, 45) $=36$

Five-number summary: 22, 29, 32, 36, 45. $\text{IQR}=36-29=7$.

Outlier fences: $29-1.5(7)=18.5$ and $36+1.5(7)=46.5$; all values lie inside, so there are no outliers.

(b) Box plot (on an age scale):

age: 20    25    30    35    40    45
      |-----[=====|====]-------------|
     22    29    32   36            45
     min   Q1   median Q3          max

The box extends from $Q_1=29$ to $Q_3=36$ with a line at the median 32. The whiskers extend to the minimum 22 on the left and the maximum 45 on the right. The longer right whisker shows slight positive skew.

Naive Bayes: $P(C\mid \text{offer, win})\propto P(C)\,P(\text{offer}\mid C)\,P(\text{win}\mid C)$ (features assumed independent).

Spam:

$0.4\times0.8\times0.6=0.192$

Not Spam:

$0.6\times0.1\times0.05=0.003$

Normalising with $P(\text{evidence})=0.192+0.003=0.195$:

$P(\text{Spam}\mid\text{offer, win})=\frac{0.192}{0.195}\approx0.985$

$P(\text{Not Spam}\mid\text{offer, win})=\frac{0.003}{0.195}\approx0.015$

Since $0.192>0.003$, the email is classified as Spam (about 98.5% probability).

Principal Component Analysis (PCA) is an unsupervised dimensionality-reduction technique that transforms correlated features into a smaller set of uncorrelated variables (principal components) that retain most of the variance.

Steps

1. Standardise the data: subtract the mean of each feature (and divide by the standard deviation if scales differ) so each feature has mean 0.
2. Compute the covariance matrix of the features: $C=\frac{1}{n-1}X^TX$
3. Compute eigenvalues and eigenvectors of $C$ by solving $Cv=\lambda v$ (or use SVD). Eigenvectors give the directions of the components; eigenvalues give the variance along them.
4. Sort eigenvectors by decreasing eigenvalue.
5. Select the top $k$ components that explain enough variance (e.g. 95%), using the explained variance ratio $\lambda_i/\sum\lambda_j$.
6. Form the projection matrix $W$ from the chosen eigenvectors.
7. Transform the data: $Z=XW$, giving the new $n\times k$ dataset.

The first component captures the maximum variance, the second is orthogonal to it and captures the next largest, and so on.

Initial centroids: $C_1=(1,1)$, $C_2=(5,4)$.

Assignment step (Euclidean distance)

Update step

$C_1=\left(\frac{1+2}{2},\frac{1+1}{2}\right)=(1.5,\,1)$

$C_2=\left(\frac{4+5}{2},\frac{3+4}{2}\right)=(4.5,\,3.5)$

After one iteration: Cluster 1 = {(1,1), (2,1)} with centroid (1.5, 1); Cluster 2 = {(4,3), (5,4)} with centroid (4.5, 3.5).

SVM maximum margin classification

SVM finds, among all hyperplanes $w^Tx+b=0$ that separate the two classes, the one with the maximum margin, i.e. the largest distance to the nearest training points of either class. The nearest points are the support vectors; they lie on the margin hyperplanes $w^Tx+b=\pm1$, and the margin width is $2/\|w\|$. Maximising it is equivalent to

$\min_{w,b}\ \tfrac12\|w\|^2\quad\text{s.t.}\quad y_i(w^Tx_i+b)\ge1$

A larger margin gives better generalisation. Non-separable data uses a soft margin (parameter $C$) or kernels.

   x2
    |   o        o   (class +1)
    |      o     \  w.x+b = +1
    |  ----------\----------- w.x+b = 0   (max-margin hyperplane)
    |   x      x  \  w.x+b = -1
    |        x        (class -1)
    +------------------------- x1
   (support vectors lie on the dashed margin lines;
    margin width = 2/||w||)

Fit analysis

Training accuracy 95%, validation 80% and test 78%.

• The training accuracy is high, so the model is not under-fitting (under-fitting would show low accuracy on training data too).
• There is a large gap (about 15-17 points) between training and validation/test accuracy, while validation and test are close to each other.

Hence the model is over-fitted: it has memorised the training data, including noise, and generalises poorly. The close validation and test scores show the drop is consistent, not an accident of one split. Remedies: regularisation, simpler model, more data, cross-validation, early stopping, feature reduction. A well-fitted model would show training and validation accuracies both high and close together.

Confusion matrix

A confusion matrix is a table that summarises the performance of a classifier by comparing actual and predicted classes.

Example: A spam filter classifies 100 emails: TP = 40, FN = 10, FP = 5, TN = 45. Then accuracy $=\frac{85}{100}=0.85$, precision $=\frac{40}{45}=0.89$, recall $=\frac{40}{50}=0.80$.

Linear regression by least squares

$\bar X=\frac{15}{5}=3,\ \bar Y=\frac{25}{5}=5$

$b=\frac{\sum(X-\bar X)(Y-\bar Y)}{\sum(X-\bar X)^2}=\frac{14}{10}=1.4$

$a=\bar Y-b\bar X=5-1.4(3)=0.8$

Best-fit line:

$Y=0.8+1.4X$

At $X=4.5$:

$Y=0.8+1.4(4.5)=0.8+6.3=7.1$

K-nearest neighbour (KNN)

KNN is a simple, instance-based (lazy) supervised algorithm. To classify a query point:

1. Choose $k$ and a distance measure (usually Euclidean).
2. Compute the distance from the query to all training points.
3. Select the $k$ nearest points.
4. Predict the majority class (or the average value for regression).

No model is built during training; all the work is done at prediction time.

Effect of $k$ on bias and variance

• Small $k$ (e.g. 1): the boundary is very flexible and follows noise, so low bias, high variance (over-fitting).
• Large $k$: predictions are averaged over many neighbours and the boundary is smooth, so high bias, low variance (under-fitting). If $k=n$, it always predicts the majority class.

$k$ is chosen by cross-validation, usually odd to avoid ties.

Separating hyperplane

Class $+1$: (2,2), (4,4); class $-1$: (4,0), (0,0). The maximum-margin hyperplane has support vectors (2,2), (4,0), (0,0). Writing $w^Tx+b=+1$ for (2,2) and $-1$ for the negatives:

• (0,0): $b=-1$
• (4,0): $4w_1+b=-1\Rightarrow w_1=0$
• (2,2): $2w_2+b=1\Rightarrow w_2=1$

So $w=(0,1)$, $b=-1$. Check (4,4): $4-1=3\ge1$, so it is correctly classified. Dual check: $w=\sum\alpha_iy_ix_i$ gives $\alpha=\tfrac12$ for (2,2), $\tfrac14$ for (4,0), and $\tfrac14$ for (0,0), all positive and balanced ($\tfrac12=\tfrac14+\tfrac14$).

$x_2-1=0 \quad\text{i.e.}\quad x_2=1$

The margin is $2/\|w\|=2$.