1.

Vector Quantisation (VQ)

Vector Quantisation is a way to replace each input vector with one representative vector
chosen from a small set. You can think of it as “rounding” a continuous input space into a
finite set of codewords (prototypes). The key idea is competitive learning: given an input
x, the prototype that best matches x wins, and x is represented by that winner.

1.1 Why VQ matters: compression and denoising

The text motivates VQ through a communication scenario: transmitting data is expensive,
so we first agree on a “codebook” of prototype vectors. Instead of sending the full vector
x each time, we send the index of the closest prototype. This is shorter (fewer bits), so it
compresses the data.

Noise reduction is closely related: a noisy input is replaced by its cluster centre
(prototype), which tends to remove small random variations. So VQ can be seen as a
general “replace input by cluster centre” mechanism that either saves bits (compression)
or improves signal quality (denoising).

 Lossless vs lossy: VQ is typically lossy because many different inputs map to the
same prototype (information is discarded).
 Good codebook: prototypes should be placed so that typical inputs are close to some
prototype, minimising average distortion.
 Bit allocation idea: common prototypes can be assigned shorter indices (variable-
length coding), improving compression efficiency.

1.2 Geometry: Voronoi cells and tessellation

In two dimensions, each prototype defines a region of points that are closer to it than to
any other prototype. This region is the Voronoi set (cell) for that prototype. Collectively,
the cells partition the space into a Voronoi tessellation. Any point inside a cell is
represented by the prototype at that cell’s centre.

 Nearest-prototype rule: choose j* = argmin_j ||x − w_j||, and represent x by w_{j*}.

 Quantisation error (distortion): e = ||x − w_{j*}||. Training tries to reduce average
error over the dataset.
 Interpretation: each cell is a “bucket” of similar inputs that are treated as identical
after quantisation.

Figure (illustrative): Voronoi tessellation used for Vector Quantisation (inputs map to
nearest prototypes).

1.3 Delaunay triangulation

The text notes that if we connect prototypes whose Voronoi cells share an edge, we get
the Delaunay triangulation. This triangulation provides a natural neighbour structure
among prototypes. Intuitively, it tells you which prototypes are “adjacent” in the
partition, which can be useful when doing function approximation or local interpolation
between nearby prototypes.

1.4 Choosing prototypes

We need a method to place prototypes in good locations. One approach is k-means,
which alternates between assigning each point to its nearest centre and moving centres to
the mean of assigned points. The competitive-learning view is similar: pick a winner and
move it toward the input. This produces prototypes located in dense regions of the input
distribution.

 If k (codebook size) is known: k-means is a standard solution.

 If you also want topology / neighbourhood structure in the prototypes: use SOM (next
section).

2. Self-Organising Feature Map (SOM)

A Self-Organising Map is a grid (usually 2D) of neurons where each neuron stores a
weight vector w_j in the same space as the inputs. Training is competitive: for each input
x, one neuron becomes the Best Matching Unit (BMU). Unlike k-means, SOM also
updates the BMU’s neighbours on the grid, so the map learns an ordered (topological)
representation.

2.1 Feature mapping & topology preservation (exam core)

Feature mapping means the physical layout of neurons matters. If two neurons are
neighbours on the grid, they should represent similar inputs. This is called topology
(relative ordering) preservation. The goal is: close in input space ⇒ close on the map, and
far in input space ⇒ far on the map.

Important limitation: the SOM grid is often 1D or 2D, but inputs may be much higher
dimensional. Therefore the map can only approximately preserve topology. Some pairs of
points may become neighbours on the map even if they are far apart in the original space
(projection distortion).
 What SOM gives you: a low-dimensional “atlas” of high-dimensional data, where
neighbourhoods often correspond to similarity.
 Why it helps: visualization, clustering structure, and a structured codebook for
quantisation.
 When it is perfect: when map dimensionality matches the intrinsic dimensionality of
data.

2.2 Lateral interaction intuition (“Mexican hat”)

Biological motivation: in sensory cortex, a firing neuron tends to excite nearby neurons
and inhibit more distant ones. A common mathematical form is the “Mexican hat”:
positive influence near the winner and negative influence further away. Kohonen’s
practical SOM simplifies this: update the winner and its neighbours (with decreasing
strength) and ignore the rest.

Figure (illustrative): “Mexican hat” lateral interaction profile (excitation near winner,
inhibition further away).

2.3 SOM network structure

Inputs connect to all SOM neurons (conceptually). Each neuron has a weight vector.
During training, the BMU is found by nearest-weight matching. Then, instead of
changing only the BMU, neurons within a neighbourhood radius on the grid are also
updated, producing an ordered map.

Figure (illustrative): SOM grid, BMU and neighbourhood (neighbour neurons also
adapt).

2.4 SOM algorithm (step-by-step, with intuition)

Key notation: input x; weights w_j; BMU index n_b; learning rates η(t) for BMU and
η_n(t) for neighbours; neighbourhood function h(n_b,t).

Initialisation
 Choose map size (e.g., 5×5, 10×10) and map dimensionality d (commonly 2).
 Random initial weights: gives no ordering; requires large neighbourhood early to
“organise” the map.
 PCA initialisation: initialise weights along first principal components; partially pre-
orders the map, so smaller neighbourhoods can be used earlier (batch setting).

Training loop
For each input x, do the following:
 Find BMU: n_b = argmin_j ||x − w_j|| (minimum Euclidean distance). This is the
“winner”.
 Update BMU: w_{n_b} ← w_{n_b} + η(t) (x − w_{n_b}). The winner moves toward
x.
 Update neighbours: for neuron j within neighbourhood radius around n_b, update w_j
← w_j + η_n(t) h(n_b,j,t) (x − w_j). Neighbours move toward x but typically less
than the BMU.
 Decrease η(t) and shrink the neighbourhood radius over time. Early: global ordering;
late: local fine tuning.
 Stop after max iterations or when weight changes become negligible.

Why shrinking neighbourhood is crucial

If the neighbourhood stays large forever, the map remains too smooth and cannot
represent local details. If the neighbourhood is tiny from the start (with random init), the
map can become disordered and may not organise globally. Hence, training is commonly
described in two phases: (1) ordering (large neighbourhood), then (2) convergence (small
neighbourhood).

Using the trained SOM

To map a new point x, compute its BMU using the same nearest-weight rule. The BMU’s
grid location serves as a low-dimensional representation and can also be used for
clustering/visualization.

2.5 Neighbourhood connections and implementation details

Because the neighbourhood changes over time, implementations usually do not store
fixed lateral connections. Instead, they compute distances between grid positions and
treat all nodes within a radius as neighbours. The text shows a map distance matrix used
to quickly find neighbours each iteration.

 Neighbourhood function choices: hard (0/1 within radius) or soft (Gaussian decay
with distance).
 Distance metric: based on grid coordinates (map space), not weight space.
 Batch vs online: SOM is described as mainly batch-oriented; online use is possible
but convergence guarantees are weaker.

2.6 Self-organisation (conceptual takeaway)

Self-organisation refers to the emergence of a global order from only local interactions:
each update depends only on a winner and its neighbours, yet the whole map becomes
ordered. The text compares this to flocking: simple local rules can create coherent global
patterns.

2.7 Network dimensionality, intrinsic dimensionality, and boundary conditions

The SOM grid can be 1D, 2D, or more. The best choice depends on intrinsic
dimensionality: the number of dimensions needed to represent the data structure. Data
embedded in higher dimensions can still have low intrinsic dimensionality (e.g., points on
a plane inside 3D space).

Boundary conditions: if map edges are artificial, you can “wrap” the map (1D:
line→circle, 2D: rectangle→torus). This reduces edge effects but requires wrap-around
distance computations (often implemented via modulo arithmetic or by imagining tiled
copies of the map and taking the shortest distance).

2.8 Choosing map size (bias–variance style trade-off)

Map size controls granularity. Too few neurons forces broad generalisation (underfitting).
Too many neurons can represent nearly every input without generalising (overfitting
analogue). The text suggests trying several sizes (e.g., 5×5, 10×10) and evaluating
quality.

3. Sampling Foundations

3.1 Pseudo-random numbers (why “random” is tricky)

Sampling methods rely on random numbers, but computers generate deterministic
sequences called pseudo-random numbers. A classic generator is the linear congruential
generator (LCG): x_{n+1} = (a x_n + c) mod m. Good parameter choices make the
period long, but the sequence is still not truly random.
 Period: length before the sequence repeats; longer is better.
 Seed: the initial x_0; changing seed changes the generated sequence.
 Practical note: NumPy uses the Mersenne Twister (mentioned in the text) for uniform
samples.

3.2 Gaussian sampling: Box–Muller (with intuition)

Uniform random numbers are easy to generate, but many algorithms need Gaussian
noise. Box–Muller transforms two independent uniform samples U1 and U2 into two
independent standard normal samples. The trick uses polar coordinates: choose a random
angle θ (uniform on [0,2π)) and a radius r chosen so that the resulting (x,y) has the
Gaussian density.

 θ = 2πU1
 r = sqrt(−2 ln(U2))
 x = r cos θ, y = r sin θ ⇒ x,y ~ N(0,1) independent

The text also describes an alternative “reject outside unit circle” method: sample points in
a square, reject those outside the circle, then apply a transform. Trade-off: one method
computes sin/cos; the other discards some samples.

3.3 Monte Carlo principle (why sampling works)

Monte Carlo sampling says that if we draw independent, identically distributed samples
from a distribution p(x), then as the number of samples N grows, the empirical
distribution converges to p(x). Consequently, integrals/expectations can be approximated
by sample averages. This is powerful for high-dimensional problems where exact
integration is hard.

 Empirical distribution: p_N(x) = (1/N) Σ δ(x^(i)=x) → p(x) as N→∞.

 Expectation estimate: E[f] ≈ (1/N) Σ f(x^(i)).
 High-probability regions naturally receive more samples, focusing computation
where it matters.
4. Proposal distributions, Rejection Sampling, and Importance Sampling

4.1 Rejection sampling (deep explanation)

When p(x) is hard to sample from directly, we choose an easy proposal distribution q(x)
that we can sample. We also assume we can evaluate an unnormalised density p~(x)
proportional to p(x): p(x) = p~(x)/Z (unknown Z). If we can find M such that p~(x) ≤ M
q(x) everywhere, then M q(x) forms an envelope above p~(x). By sampling under the
envelope and rejecting the “extra” area, accepted x values follow p(x).

 Pick M and proposal q(x) such that p~(x) ≤ M q(x) for all x.
 Sample x* ~ q(x).
 Sample u ~ Uniform(0, M q(x*)).
 Accept if u < p~(x*); otherwise reject and repeat.

 Acceptance rate depends on how tight the envelope is; smaller M gives higher
acceptance.
 In high dimensions, it becomes difficult to design a good envelope, and rejection rates
can become extremely high.

Figure (illustrative): Rejection sampling—accept points under target p~(x) inside

envelope M q(x).
4.2 Importance sampling (what it fixes and what it risks)
Importance sampling avoids rejection by keeping every sample but weighting them. If we
draw x^(i) from q(x), then we correct the mismatch between q and p using weights
w(x)=p(x)/q(x). The expectation E_p[f] can be estimated by Σ w_i f(x_i) / Σ w_i
(normalised weights).

 Benefit: no samples wasted (unlike rejection).

 Risk: if q(x) is a poor match to p(x), weights become extremely uneven (weight
degeneracy), making the estimator noisy.
 Design goal: choose q(x) to cover all regions where p(x) is large (support coverage).

4.3 Sampling-Importance-Resampling (SIR)

SIR turns weighted samples into unweighted samples by resampling: draw from the set
{x_i} using probabilities proportional to normalised weights w_i. This concentrates
samples in high-probability regions without explicit rejection, but introduces duplicates
(some x_i repeated) and can reduce diversity if weights are too concentrated.

 Draw N samples from q(x).

 Compute weights w_i = p(x_i)/q(x_i) and normalise them to sum to 1.
 Resample N times from {x_i} with probabilities w_i.

5. Markov Chain Monte Carlo (MCMC)

5.1 Markov chains: building a sampler via transitions

A Markov chain is a sequence of states where the next state depends only on the current
one. In MCMC, we design transition rules so that the chain spends time in each region
proportional to the desired distribution p(x). As we simulate the chain, the visited states
become dependent samples from p(x).

 Irreducible: any state can be reached from any other (eventually).

 Ergodic (and aperiodic): the chain revisits regions and does not get stuck cycling.
 Invariant distribution: p(x) is unchanged by the transition operator T.

Detailed balance (why it matters)

A common way to guarantee invariance is the detailed balance condition: p(x) T(x,x′) =
p(x′) T(x′,x). This symmetry implies reversibility and ensures p(x) is a stationary
distribution of the chain.

5.2 Metropolis–Hastings (MH) algorithm (explained)

MH uses a proposal distribution q(x*|x) to suggest a new state x*. It then accepts or
rejects that proposal so that the resulting Markov chain satisfies detailed balance. Unlike
rejection sampling, if a proposal is rejected, MH does not discard the iteration; it repeats
the current state, which preserves the chain structure.

Acceptance probability (using unnormalised p~):

α = min(1, p~(x*) q(x|x*) / ( p~(x) q(x*|x) ) ).

 Start from an initial value x0 (choose something reasonable).

 Propose x* ~ q(x*|x_i).
 Compute α and draw u ~ Uniform(0,1).
 If u < α: accept (x_{i+1}=x*). Else: reject but keep state (x_{i+1}=x_i).
 If q is symmetric (q(x*|x)=q(x|x*)), the proposal terms cancel → the original
Metropolis algorithm.
 Tuning q matters: small proposal steps → high acceptance but slow exploration; large
steps → low acceptance and many repeats.
 Practical concepts: burn-in (discard early samples), thinning (optional), and checking
mixing/acceptance rate.

Figure (illustrative): Metropolis sampler trace (top) and histogram vs target (bottom).

5.3 Simulated annealing (finding maxima)

Sometimes we want the single best state (maximum of p) rather than samples. Simulated
annealing modifies MH so that it gradually becomes less willing to accept worse moves.
It does this by introducing a temperature T that decreases over time, effectively sampling
from p(x)^{1/T}. As T→0, probability mass concentrates near the maximum.

 High T: exploratory, accepts many moves including worse ones.

 Low T: exploitative, mostly accepts improvements; converges toward maxima.
 Cooling schedule is crucial: too fast can trap in local maxima; too slow costs
computation.
5.4 Gibbs sampling (when conditionals are available)
Gibbs sampling is an MCMC method that becomes extremely simple when we can
sample from full conditional distributions p(x_j | x_-j). Instead of proposing an arbitrary
x*, we directly draw the next value of one variable from its conditional given the current
values of all others.

1. Initialise all variables (x1, x2, …, xn).

2. Repeat: for j = 1..n, sample x_j from p(x_j | x_1, …, x_{j-1}, x_{j+1}, …, x_n).
3. Collect samples after burn-in.

Why acceptance is always 1: the proposal is exactly the conditional distribution, and
when plugged into the Metropolis–Hastings acceptance ratio, all terms cancel, producing
α=1. So every proposed update is accepted.

5.5 Beta–binomial example

The text gives an example where the joint distribution factors into components that yield
simple conditionals, enabling Gibbs sampling. The key takeaway is that Gibbs is natural
for models like Bayesian networks, where local conditional probabilities are readily
available.

6. Quick Revision

6.1 SOM – key points to memorise

 BMU selection: n_b = argmin_j ||x − w_j||.
 BMU update: w_{n_b} ← w_{n_b} + η(t)(x − w_{n_b}).
 Neighbour update: w_j ← w_j + η_n(t) h(n_b,j,t)(x − w_j).
 Neighbourhood radius shrinks over time: ordering phase → convergence phase.
 Map size controls granularity; torus boundary can reduce edge effects.

6.2 MCMC – key points to memorise

 Rejection sampling: accept under p~(x) beneath envelope M q(x).
 Importance sampling: weight w(x)=p(x)/q(x); risk of weight degeneracy.
 Detailed balance: p(x)T(x,x′)=p(x′)T(x′,x) ensures invariance.
 Metropolis–Hastings acceptance: α=min(1, p~(x*)q(x|x*)/(p~(x)q(x*|x))).
 Gibbs: sample from full conditionals; acceptance probability is 1.

7. Practice Questions (Self-test)

 Explain Vector Quantisation and how Voronoi tessellation defines the quantisation
regions.
 Describe SOM training and explain why neighbourhood and learning rate should
decrease over time.
 Compare k-means prototypes vs SOM prototypes. What extra structure does SOM
provide?
 Explain rejection sampling using the envelope principle. What makes it inefficient in
high dimensions?
 Derive the importance sampling estimator for E[f] and discuss what happens when q
is a poor match to p.
 State and explain detailed balance. Why is it useful in MCMC?
 Write the Metropolis–Hastings algorithm and explain the effect of proposal step size
on mixing/acceptance.
 Explain simulated annealing and how temperature affects acceptance of worse moves.
 Explain Gibbs sampling and why its acceptance probability is always 1 when
sampling from full conditionals.
8. Solved Numerical Examples

Example 8.1 – SOM map size: number of neurons (5×5 and 10×10)
Problem: The text suggests trying SOM sizes such as 5×5 and 10×10. Compute the
number of neurons (prototypes) in each map.

4. Solution:

 A 5×5 map has 5×5 = 25 neurons.

 A 10×10 map has 10×10 = 100 neurons.

Interpretation: In vector-quantisation terms, the codebook would contain 25 or 100

prototype vectors. A larger map gives finer granularity but may generalise less.

Example 8.2 – Rejection sampling: expected accepted samples for M = 0.8 and M =
2
Problem: The text states that with M = 0.8 the algorithm rejects about half of the samples,
and with M = 2 it rejects about 85% of samples. If we generate 1,000 proposals, how
many samples do we expect to accept in each case?

5. Solution:

 Case 1: M = 0.8 → rejection ≈ 50% → acceptance ≈ 50%.

 Expected accepted ≈ 0.50 × 1,000 = 500 samples.
 Case 2: M = 2 → rejection ≈ 85% → acceptance ≈ 15%.
 Expected accepted ≈ 0.15 × 1,000 = 150 samples.

Extra: To obtain about 500 accepted samples, you need about 500/0.50 = 1,000 proposals
when M = 0.8, but about 500/0.15 ≈ 3,334 proposals when M = 2. This shows why
choosing a tight envelope (small M) matters.

Example 8.3 – Monte Carlo estimate from 10 trials (patience example)

Problem: The text describes playing 10 games of patience and winning 6. Estimate the
probability of winning based on this Monte Carlo sample.
6. Solution:

 Monte Carlo estimate of win probability = wins / trials = 6 / 10 = 0.6 (60%).

Interpretation: With only 10 trials this estimate has high uncertainty, but it illustrates the
Monte Carlo principle: sample frequency approximates true probability as the number of
trials increases.

Example 8.4 – Linear congruential generator: maximum period with m = 2^32

Problem: The text gives an example parameter choice m = 2^32 for a linear congruential
generator. What is the maximum possible period (number of distinct states) in this case?

7. Solution:

 m = 2^32 = 4,294,967,296 (i.e., 4,294,967,296).

Maximum period is m when parameters are chosen so the generator cycles through all
integers 0 … m−1 before repeating. So the longest possible period here is 4,294,967,296.

Example 8.5 – SOM neighbourhood: “eight closest nodes” concept

Problem: In the SOM diagram description, the text mentions connections shown to the
eight closest nodes (a configurable parameter). How many immediate neighbours does a
grid neuron have in this setting?

8. Solution:

 In a 2D grid, if we count all adjacent nodes horizontally, vertically, and diagonally, a

non-edge neuron has 8 immediate neighbours (the Moore neighbourhood).

Interpretation: Updating these 8 neighbours helps enforce local smoothness and

topological ordering; edge neurons have fewer neighbours unless toroidal boundary
conditions are used.