Learning and generalisation, competitive learning, PCA, fuzzy models and decision trees, and stochastic search, with Lab 6.
This chapter completes Unit II. It covers neural networks (learning, generalisation and competitive learning), principal component analysis and its link with neural networks, fuzzy logic (extracting fuzzy models from data and fuzzy decision trees), and stochastic search methods for optimisation. Each topic includes a worked calculation.
6.1 Neural networks: learning and generalisation, competitive learning
An artificial neural network is a model built from simple processing units called neurons, inspired by biological brain cells. Each neuron receives inputs x₁ … xₙ, multiplies each by a weight wᵢ, adds a bias b, and passes the total z = Σwᵢxᵢ + b through an activation function such as the sigmoid σ(z) = 1 / (1 + e^−z), tanh or ReLU (max(0, z)). Neurons are arranged in layers: an input layer, one or more hidden layers, and an output layer. A network with enough hidden neurons can approximate almost any function, which is why neural networks excel at pattern recognition in images, speech and text.
Every line is a weight; the forward pass computes the output from left to right, and backpropagation sends the error from right to left to adjust each weight.
Learning. A network learns by adjusting its weights to reduce the error between its outputs and the targets. In supervised learning this is done by backpropagation: a forward pass computes the output; a loss function measures the error; the error is propagated backwards through the layers to find each weight's gradient; and every weight is updated by gradient descent, w ← w − η ∂E/∂w, where η is the learning rate. One pass through all the training data is an epoch, and training usually runs for many epochs. Networks can also learn without labels (unsupervised learning) or from rewards (reinforcement learning).
Worked example 1 – one learning step of a sigmoid neuron. Inputs x = (1, 0.5), weights w = (0.4, 0.6), bias b = 0.1, target t = 1, learning rate η = 0.5, and squared-error loss.
- Net input: z = 0.4 × 1 + 0.6 × 0.5 + 0.1 = 0.4 + 0.3 + 0.1 = 0.8.
- Output: y = σ(0.8) = 1 / (1 + e^−0.8) = 1 / (1 + 0.4493) = 0.690.
- Error: t − y = 1 − 0.690 = 0.310.
- Error signal: δ = (t − y) × y × (1 − y) = 0.310 × 0.690 × 0.310 = 0.0663.
- Updates (Δwᵢ = η δ xᵢ): Δw₁ = 0.5 × 0.0663 × 1 = 0.0332, Δw₂ = 0.5 × 0.0663 × 0.5 = 0.0166, Δb = 0.5 × 0.0663 = 0.0332.
- New weights: w = (0.4332, 0.6166), b = 0.1332.
- Check: new z = 0.4332 + 0.3083 + 0.1332 = 0.8747, so y = σ(0.8747) = 0.706 — closer to the target of 1 than before. Repeating such steps over many examples is training.
Generalisation. Generalisation is a network's ability to perform well on new, unseen data, which is the real goal of learning. A network that is too simple underfits: it has high error on both training and test data. A network that is too complex, or trained too long, overfits: it memorises noise in the training data, so its training error is very low but its test error is high. Generalisation is improved by using more training data, cross-validation to choose model size, early stopping (halting training when validation error starts to rise), regularisation (L1/L2 penalties on large weights), dropout (randomly switching off neurons during training) and data augmentation.
Worked example 2 – recognising overfitting.
| Hidden neurons | Training accuracy | Test accuracy | Gap | Diagnosis |
|---|---|---|---|---|
| 2 | 72% | 70% | 2 | Underfitting |
| 10 | 91% | 89% | 2 | Good fit |
| 200 | 99% | 75% | 24 | Overfitting |
The 200-neuron network looks best on training data, but its 24-point gap shows it has memorised the training set; the 10-neuron network generalises best.
Competitive learning. Competitive learning is an unsupervised scheme in which the output neurons compete to respond to each input, and only the winner — the neuron whose weight vector is closest to the input — is allowed to learn. This is called winner-takes-all. The steps are: present an input x; find the winning neuron j with the smallest distance ‖x − wⱼ‖; move only the winner's weights towards the input, wⱼ ← wⱼ + η(x − wⱼ); and repeat for all inputs. Over time each neuron's weights settle at the centre of one group of similar inputs, so the network performs clustering. In a Kohonen Self-Organising Map (SOM) the winner's neighbours on a grid are also updated, producing a map in which similar inputs land close together; Learning Vector Quantisation (LVQ) is a supervised variant.
Worked example 3 – one competitive-learning step. Two neurons have weights w₁ = (0.2, 0.8) and w₂ = (0.9, 0.3). The input is x = (0.8, 0.2) and η = 0.5.
- Squared distance to neuron 1: (0.8 − 0.2)² + (0.2 − 0.8)² = 0.36 + 0.36 = 0.72.
- Squared distance to neuron 2: (0.8 − 0.9)² + (0.2 − 0.3)² = 0.01 + 0.01 = 0.02.
- Neuron 2 is closer, so it wins.
- Update: w₂ = (0.9 + 0.5(0.8 − 0.9), 0.3 + 0.5(0.2 − 0.3)) = (0.9 − 0.05, 0.3 − 0.05) = (0.85, 0.25). Neuron 1 is unchanged.
Read more on the blog: Neural Networks.
6.2 Principal component analysis and neural networks
Principal component analysis (PCA) reduces many correlated variables to a few new, uncorrelated variables called principal components, while keeping as much of the original variation as possible. The first component points in the direction along which the data varies most; the second is perpendicular to the first and captures the most remaining variation, and so on. The steps are: (1) centre the data by subtracting each variable's mean (and standardise if units differ); (2) compute the covariance matrix; (3) find its eigenvalues and eigenvectors; (4) sort the eigenvectors by eigenvalue — each eigenvalue is the variance captured by its component; (5) keep the top k components, often enough to explain 90–95% of the variance; and (6) project the data onto them. PCA speeds up later modelling, reduces noise and overfitting, and allows high-dimensional data to be plotted in two dimensions.
Worked example 1 – PCA by hand. Four points: (1, 2), (2, 3), (3, 3), (4, 5).
- Means: x̄ = 10 / 4 = 2.5 and ȳ = 13 / 4 = 3.25. Centred data: (−1.5, −1.25), (−0.5, −0.25), (0.5, −0.25), (1.5, 1.75).
- Covariance matrix (dividing by n − 1 = 3): var(x) = (2.25 + 0.25 + 0.25 + 2.25) / 3 = 5 / 3 = 1.6667; var(y) = (1.5625 + 0.0625 + 0.0625 + 3.0625) / 3 = 4.75 / 3 = 1.5833; cov(x, y) = (1.875 + 0.125 − 0.125 + 2.625) / 3 = 4.5 / 3 = 1.5. So C = [[1.6667, 1.5], [1.5, 1.5833]].
- Eigenvalues solve λ² − (trace)λ + det = 0, with trace = 1.6667 + 1.5833 = 3.25 and det = 1.6667 × 1.5833 − 1.5² = 2.6389 − 2.25 = 0.3889. Then λ = [3.25 ± √(3.25² − 4 × 0.3889)] / 2 = [3.25 ± √9.0069] / 2 = (3.25 ± 3.0012) / 2, giving λ₁ = 3.1256 and λ₂ = 0.1244.
- Variance explained: PC1 = 3.1256 / 3.25 = 96.2%, PC2 = 3.8%. One component is enough.
- Eigenvector for λ₁: from (1.6667 − 3.1256)v₁ + 1.5v₂ = 0, v₂ = 0.9726v₁. Normalising to length 1: v = (0.717, 0.697).
- Projection onto PC1 (score = 0.717 × x-deviation + 0.697 × y-deviation): (1, 2) → −1.947; (2, 3) → −0.533; (3, 3) → 0.184; (4, 5) → 2.296. Four 2-D points are now four single numbers that keep 96% of the information.
PCA and neural networks. PCA and neural networks are connected in two ways. First, PCA is often applied before training a network to reduce the number of inputs, which speeds up learning and reduces overfitting. Second, neural networks can compute principal components themselves. A single linear neuron trained with Oja's rule, Δw = η y (x − y w) where y = w · x, converges to the first principal component. Sanger's rule (the generalised Hebbian algorithm) extends this to several components. A linear autoencoder — a network trained to reproduce its input through a narrow middle layer — learns the same subspace as PCA, and a non-linear autoencoder generalises PCA to curved structures.
Worked example 2 – one step of Oja's rule. Start with w = (1, 0), use the centred point x = (1.5, 1.75) from example 1, and η = 0.1.
- Output: y = w · x = 1 × 1.5 + 0 × 1.75 = 1.5.
- x − y w = (1.5, 1.75) − 1.5 × (1, 0) = (0, 1.75).
- Δw = 0.1 × 1.5 × (0, 1.75) = (0, 0.2625), so w becomes (1, 0.2625).
- The weight vector has turned from pointing along the x-axis towards the principal direction (0.717, 0.697); repeated over many points it converges to it.
Read more on the blog: Principal Component Analysis (PCA).
Lab 6 (R) – Dimensionality reduction with PCA on a houses dataset
Aim: reduce the numeric attributes of a housing dataset to a few principal components. Put your instructor's houses file as houses.csv in the working folder; otherwise the code uses the Boston housing data from the MASS package.
library(MASS)
houses <- if (file.exists("houses.csv")) read.csv("houses.csv") else Boston
# Keep numeric columns and drop rows with missing values
num <- na.omit(houses[sapply(houses, is.numeric)])
dim(num)
# PCA on standardised data (scale. = TRUE is essential when units differ)
pca <- prcomp(num, center = TRUE, scale. = TRUE)
summary(pca) # SD, proportion and cumulative variance
# Variance explained and scree plot
var_exp <- pca$sdev^2 / sum(pca$sdev^2)
plot(var_exp, type = "b", pch = 19, xlab = "Principal component",
ylab = "Proportion of variance", main = "Scree plot")
plot(cumsum(var_exp), type = "b", pch = 19, ylab = "Cumulative variance")
abline(h = 0.90, col = "red", lty = 2)
# Number of components needed for 90% of the variance
k <- which(cumsum(var_exp) >= 0.90)[1]
cat("Components kept:", k, "of", ncol(num), "\n")
round(pca$rotation[, 1:2], 3) # loadings: which variables drive PC1, PC2
reduced <- as.data.frame(pca$x[, 1:k]) # the reduced dataset
head(reduced)
biplot(pca, scale = 0, cex = 0.6) # observations and variables together
6.3 Fuzzy logic: extracting fuzzy models from data, fuzzy decision trees
Classical logic is crisp: a statement is either true (1) or false (0), and a temperature is either "hot" or "not hot". Human reasoning is vaguer — 28 °C is "somewhat warm and slightly hot". Fuzzy logic captures this by letting an element belong to a set to a degree of membership μ between 0 and 1. A membership function defines the degree for each value; common shapes are triangular, trapezoidal and Gaussian. Fuzzy sets are combined with fuzzy operators: AND takes the minimum (μ_A∩B = min(μ_A, μ_B)), OR takes the maximum, and NOT gives 1 − μ. A fuzzy inference system has four stages: fuzzification (converting crisp inputs into membership degrees), rule evaluation (applying IF–THEN rules), aggregation (combining the rule outputs) and defuzzification (converting the result back to a crisp number, for example by the centroid or weighted-average method). In a Mamdani system the rule outputs are fuzzy sets, which makes rules very readable; in a Takagi–Sugeno system the outputs are numbers or linear functions, which makes computation simpler and more accurate.
Worked example 1 – a fuzzy fan controller. Temperature is 28 °C. "Warm" is a triangle from 20 to 40 peaking at 30; "Hot" is a triangle from 25 to 45 peaking at 35. Rules: IF warm THEN fan speed = 50%; IF hot THEN fan speed = 90% (Sugeno singleton outputs).
- Fuzzification: μ_warm(28) = (28 − 20) / (30 − 20) = 0.8; μ_hot(28) = (28 − 25) / (35 − 25) = 0.3.
- Rule strengths: rule 1 fires at 0.8, rule 2 at 0.3.
- Defuzzification by weighted average: speed = (0.8 × 50 + 0.3 × 90) / (0.8 + 0.3) = (40 + 27) / 1.1 = 60.9%.
- A crisp controller with a threshold at 30 °C would switch abruptly between 50% and 90%; the fuzzy controller changes smoothly.
Extracting fuzzy models from data. Instead of asking experts to write the rules, a fuzzy model can be learned from input–output data. First, each variable's range is partitioned into fuzzy sets (low, medium, high), either by hand, by equal division, or by fuzzy c-means clustering. Second, rules are generated from the data: in the Wang–Mendel method, each data pair is assigned, for every variable, to the fuzzy set in which it has the highest membership, producing one rule per record, and the rule is given a degree equal to the product of those memberships. Third, conflicts are resolved: when several rules share the same IF part but differ in the THEN part, the rule with the highest degree is kept. Finally, the membership functions can be tuned with neural networks (ANFIS) or genetic algorithms to improve accuracy.
Worked example 2 – generating one rule by Wang–Mendel. A data record is (temperature = 28, fan speed = 62). Speed sets are "Medium", a triangle 30–50–70, and "High", a triangle 50–90–130.
- Input memberships: warm 0.8, hot 0.3 → choose warm.
- Output memberships: μ_medium(62) = (70 − 62) / (70 − 50) = 0.4; μ_high(62) = (62 − 50) / (90 − 50) = 0.3 → choose medium.
- Rule: IF temperature is warm THEN speed is medium, with degree 0.8 × 0.4 = 0.32.
- If another record produces "IF warm THEN high" with degree 0.20, the conflict is resolved in favour of the rule with degree 0.32.
Fuzzy decision trees. A fuzzy decision tree extends an ordinary decision tree so that a record can follow several branches at once, each to the degree of its membership. When choosing a split, the tree computes fuzzy entropy and fuzzy information gain from the sums of membership values in each class rather than from crisp counts. At prediction time, the conclusions of all the leaves a record reaches are combined, weighted by the record's membership along each path. Fuzzy decision trees handle noisy data and values near boundaries smoothly, are less sensitive to small changes in the data, and still produce readable fuzzy rules.
Worked example 3 – fuzzy entropy and fuzzy prediction.
- At a node, the summed memberships are 3.2 for class buy and 0.8 for not buy, total 4.0, so p(buy) = 0.8 and p(not buy) = 0.2.
- Fuzzy entropy = −0.8 log₂ 0.8 − 0.2 log₂ 0.2 = 0.8 × 0.322 + 0.2 × 2.322 = 0.258 + 0.464 = 0.722 bits.
- A customer aged 33 belongs to "young" with μ = 0.4 and to "middle-aged" with μ = 0.6. The young leaf predicts P(buy) = 0.2 and the middle-aged leaf predicts 0.7.
- Combined prediction = 0.4 × 0.2 + 0.6 × 0.7 = 0.08 + 0.42 = 0.50 — a crisp tree would have used only one leaf and answered 0.2 or 0.7.
Read more on the blog: Fuzzy Logic.
6.4 Stochastic search methods
Stochastic search methods solve optimisation problems by exploring possible solutions with the help of randomness. They are used when the search space is too large to check every solution and when the objective function has many local optima, where a purely greedy method gets stuck. Random search simply samples solutions at random and keeps the best. Hill climbing with random restarts improves a solution step by step and restarts from random points to escape local optima. Simulated annealing imitates the slow cooling of metal: it always accepts a better move, and accepts a worse move with probability e^(−ΔE / T), where ΔE is how much worse the move is and T is a "temperature" that is lowered gradually, so the search explores widely at first and settles down later. Genetic algorithms evolve a population of candidate solutions through selection (fitter solutions are more likely to become parents), crossover (parents exchange parts) and mutation (random small changes). Other methods include tabu search, ant-colony optimisation and particle swarm optimisation. Stochastic methods do not guarantee the global optimum, but they usually find very good solutions quickly.
Worked example 1 – simulated annealing acceptance. A move makes the solution worse by ΔE = 5.
- At a high temperature T = 10: P(accept) = e^(−5/10) = e^(−0.5) = 0.607 — the search often accepts worse moves and explores freely.
- At a low temperature T = 1: P(accept) = e^(−5) = 0.0067 — worse moves are almost never accepted, so the search settles into the best region found.
Worked example 2 – one generation of a genetic algorithm. Maximise f(x) = x² for whole numbers x from 0 to 31, coded as 5-bit strings.
| String | x | f(x) = x² | Selection probability f / Σf |
|---|---|---|---|
| 01101 | 13 | 169 | 169 / 1,170 = 0.144 |
| 11000 | 24 | 576 | 576 / 1,170 = 0.492 |
| 01000 | 8 | 64 | 64 / 1,170 = 0.055 |
| 10011 | 19 | 361 | 361 / 1,170 = 0.309 |
| Total | 1,170 | 1.000 |
- Selection (roulette wheel): the string 11000 has a 49.2% chance of being picked each time; suppose 01101 and 11000 are chosen as parents.
- Crossover after the 4th bit: 0110|1 and 1100|0 exchange tails to give 01100 (x = 12) and 11001 (x = 25).
- Fitness of the new child 11001: 25² = 625, better than the best parent's 576.
- Mutation (flipping a random bit with small probability, e.g. 0.001) keeps diversity; repeated over generations the population moves towards the optimum 11111 (x = 31, f = 961).
Read more on the blog: Stochastic Search.
Independent study notes written in my own words, for learning purposes. Not affiliated with any university or course provider. R, RStudio, Hadoop, Amazon S3, Tableau, Power BI and other product names are trademarks of their respective owners.