BAI702,Machine Learning-II

MODULE 4
14.2 VECTOR QUANTISATION

Data compression, which is used both for storing data and for the transmission of speech and image data. The reason
that the applications are related is that both replace the current input by the cluster centre that it belongs to. For noise
reduction we do this to replace the noisy input with a cleaner one, while for data compression we do it to reduce the
number of datapoints that we [Link] of these things can be understood by considering them as examples of data
communication. Suppose that I want to send data to you, but that I have to pay for each databit I transmit, so I want
to keep the amount of data that I send to a minimum. I notice that there are lots of repeated datapoints, so I decide to
encode my data before I send it, so that instead of sending the entire set, we agree on a codebook of prototype
vectors together. Now, instead of transmitting the actual data, I can transmit the index of that datapoint
in the codebook, which is shorter.

There is one problem with the scenario so far, which is that the codebook won’t contain every possible datapoint.
What happens when I want to send a datapoint and it isn’t in the codebook? In that case we need to accept that our
data will not look exactly the same, and I send you the index of the prototype vector that is closest to [Link] is
known as vector quantization. Figure shows an interpretation of prototype vectors in two dimensions. The dots at
the centre of each cell are the prototype vectors, and any datapoint that lies within a cell is represented by the dot.
The name for each cell is the Voronoi set of a particular proto- type. Together, they produce the Voronoi tesselation
of the space. If you connect together every pair of points that share an edge, as is shown by the dotted lines, then you
get the Delaunay triangulation, which is the optimal way to organise the space to perform function
[Link] question is how to choose the prototype vectors, and this is where competitive learning comes in.
We need to choose prototype vectors that are as close as possible to all of the possible inputs that we might see. This
application is called learning vector quantization because we are learning an efficient vector quantisation. The k-
means algorithm can be used to solve the problem if we know how large we want our codebook to be. However,
another algorithm turns out to be more useful, the Self-Organising Feature Map.

FIGURE 1. The Voronoi tesselation of space that performs vector quantisation. Any datapoint is represented by the
dot within its cell, which is the prototype vector.

14.3 THE SELF-ORGANISING FEATURE MAP

By far the most commonly used competitive learning algorithm is the Self-Organising Feature Map (often
abbreviated to SOM), which was proposed by Teuvo Kohonen in 1988. Kohonen was considering the question of
how sensory signals get mapped into the cerebral cortex of the brain with an order. For example, in the auditory
cortex, which deals with the sounds that we hear, neurons that are excited (i.e., that are caused to fire) by similar

1
BAI702,Machine Learning-II

sounds are positioned closely together, whereas two neurons that are excited by very different sounds will be far
[Link] are two novel departures in this for us: firstly, the relative locations of the neurons in the network
matters (this property is known as feature mapping—nearby neurons correspond to similar input patterns), and
secondly, the neurons are arranged in a grid with connections between the neurons, rather than in layers with
connections only between the different layers. In the auditory cortex there appears to be sheets of neurons arranged
in 2D, and that is the typical arrangement of neurons for the SOM: a grid of neurons arrangedin 2D, as can be seen
in Figure 2. A 1D line of neurons is also sometimes used. In mathematical terms, the SOM demonstrates relative
ordering preservation, which is sometimes known as topology preservation. The relative ordering of the inputs
should be preserved by the ordering in the neurons, so that neurons that are close together represent inputs that are
close together, while neurons that are far apart represent inputs that are far apart This topology preservation is not
necessarily possible, because the SOM typically uses a 1D or 2D array of neurons, and most of our input spaces are
of much higher dimensionality than that. This means that the ordering cannot be preserved. A different way to see
the same thing is given in Figure 3,where mismatches between the topology of the input space and map lead to
changes in therelative ordering. The best that can be said is that SOM is perfectly topology-preserving,which means
that if the dimensionality of the input and the map correspond, then the topology of the input space will be
preserved.

FIGURE 2. The Self-Organising Map network.

FIGURE [Link] inputs in 1D (a straight line), a 2D grid, and a 3D cube are represented

2
BAI702,Machine Learning-II

by a 2D grid of neurons, the relative ordering is not perfectly preserved.

14.3.1 The SOM Algorithm:

In Kohonen’s SOM algorithm, the weight update rule is modified instead, so that information about neighbouring
neurons is included in the learning rule, which makes the algorithm simpler. The algorithm is a competitive learning
algorithm, so that one neuron is chosen as the winner, but when its weights are updated, so are those of its
neighbours, although to a lesser extent. Neurons that are not within the neighbourhood are ignored, not repelled.

• Initialisation
– choose a size (number of neurons) and number of dimensions d for the map
– either:
∗ choose random values for the weight vectors so that they are all different OR
∗ set the weight values to increase in the direction of the first d principal
components of the dataset

• Learning
– repeat:
∗ for each datapoint:select the best-matching neuron nb using the minimum Euclidean distance between the
weights and the input,

∗ update the weight vector of the best-matching node using:

where η(t) is the learning rate.

∗ update the weight vector of all other neurons using:

where ηn(t) is the learning rate for neighbourhood nodes, and h(nb, t) is the neighbourhood function, which decides
whether each neuron should be included in the neighbourhood of the winning neuron (so h = 1 for neighbours and h
= 0 for non-neighbours)
∗ reduce the learning rates and adjust the neighbourhood function, typically by η(t+1) = αη(t) k/kmax
where 0 ≤ α ≤ 1 decides how fast the size decreases, k is the number of iterations the algorithm has been running for,
and kmax is when you want the learning to stop. The same equation is used for both learning rates (η, ηn) and the
neighbourhood function h(nb, t).
– until the map stops changing or some maximum number of iterations is exceeded.
• Usage
– for each test point:
∗ select the best-matching neuron nb using the minimum Euclidean distance between the weights and the input:

14.3.2 Neighbourhood Connections

The size of the neighbourhood is thus another parameter that we need to control. How large should the
neighbourhood of a neuron be? If we start our network off with random weights, as we did for the MLP, then at the
beginning of learning, the network is pretty well unordered (as the weights are random, two nodes that are very close
in weight space could be on opposite sides of the map, and vice versa) and so it makes sense that the
neighbourhoods should be large, so that we get the rough ordering of the network correct. However, once the
network has been learning for a while, the rough ordering has already been created, and the algorithm starts to fine-

3
BAI702,Machine Learning-II

tune the individual local regions of the network. At this stage, the neighbourhoods should be small, as is shown in
Figure 4. It therefore makes sense to reduce the size of the neighbourhood as the network adapts. These two phases
of learning are also known as ordering and convergence. Typically, we reduce the neighborhood size by a small
amount at each iteration of the algorithm. We control the learning rate η in exactly the same way, so that it starts off
large and decreases over time, as is shown in the algorithm below. The fact that the size of the neighborhood
changes as the algorithm runs has consequences for an implementation. There is no point using actual connections
between nodes, since the number of these will change as the algorithm runs. We therefore set up a matrix that
measures the distances between nodes in the network and choose the nodes in the neighborhood of a particular node
as those within a neighborhood radius that shrinks as the algorithm runs.

FIGURE 4. Top: Initially, similar input vectors excite neurons that are far apart, so that the neighbourhood (shown
as a circle) needs to be large. Bottom: Later on during training the neighbourhood can be smaller, because similar
input vectors excite neurons that are close together.

14.3.3 Self-Organisation

A particularly interesting aspect of feature mapping is that we get a global ordering of the neurons in the network,
despite the fact that the interactions are all local, since neurons that are very far apart do not interact with each other.
We thus get a global ordering of the space using only a set of local interactions, which is amazing. This is known as
self-organisation, and it appears everywhere. It is part of the growing science of complexity. To see how common
self-organisation is, consider a flock of birds flying in formation. The birds cannot possibly know exactly where
each other are, so how do they keep in formation? In fact, simulations have shown that if each bird just tries to stay
diagonally behind the bird to its right, and fly at the same speed, then they form perfect flocks, no matter how they
start off and what objects are placed in their way. So the global ordering of the whole flock can arise from the
local interactions of each bird looking to the one on its right (or left).

14.3.4 Network Dimensionality and Boundary Conditions

Noise and other inaccuracies in data often lead to it being represented in more dimensions than are actually required,
and so finding the intrinsic dimensionality can help to reduce the noise. We also need to consider the boundaries of
the network. In some cases, it makes sense that the edges of the map of neurons is strictly defined — for example, if
we are arranging sounds from low pitch to high pitch, then the lowest and highest pitches we can hear are obvious
endpoints. However, it is not always the case that such boundaries are clearly defined. In this case we might want to
remove the boundary conditions. The choice of the number of dimensions and the boundary conditions depends on
the problem that we are considering. The one cost that this has is that the map distances get more complicated to
calculate,since we now need to calculate the distances allowing for the wrap around. This can be done using modulo
arithmetic, but it is easier to think about taking copies of the map and putting them around the map, so that the
original map has copies of itself all around: one above, one below, to the right and left, and also diagonally above
and below, as is shown in Figure Now we keep one of the points in the original map, and the distance to the second
node is the smallest of the distances between the first node and the copies of the second node in the different maps

4
BAI702,Machine Learning-II

(including the original). By treating the distances in x and y separately, the number of distances that has to be
computed can be [Link] with the competitive learning algorithm that we considered earlier, the size of theSOM
is defined before we start learning. The size of the network (that is, the number of neurons that we put into it)
decides how fine-grained the learning is. If there are very few neurons, then the best that the network can do is to
find gross generalisations that link the data. However, if there are very large numbers of neurons, then the network
can represent every input without ever needing to generalise at all. This is yet another example of overfitting.
Clearly, then, choosing the correct size of network is important. The common approach is to test out several
different sizes of network, such as 5 × 5 and 10 × 10 and see how well the network learns.

14.3.5 Examples of Using the SOM

1. SOM with Random 2D Data

 Data: 2D points uniformly distributed in [−1,1][-1, 1][−1,1].

 Initial weights (random): Map is disordered.
 After training:
o 10 iterations → Neighbouring nodes represent nearby data points (topological ordering).
 PCA initialization:
o Not very useful for random data.
o Speeds up convergence: Similar ordering achieved in 5 iterations.

2. SOM on Iris Dataset

 Map size: 5 × 5 SOM

 Training: 100 iterations
 No class labels given during training.
 Result:
o Data points of the same class cluster together on the map.
 Conclusion:
o SOM performs unsupervised clustering.
o Class separation can be inferred using post-processing (e.g., LDA-like methods).

3. SOM on Ecoli Dataset (Harder Problem)

 Dataset: Protein localization (UCI repository).

 Task: More complex than Iris.
 Results:
o Clusters are less clear in test data.
o Clearer clusters in training data.

5
BAI702,Machine Learning-II

Markov Chain Monte Carlo

(MCMC) Methods

15.1 SAMPLING

This is done it using the [Link]() function in NumPy, and also sampling from Gaussian distributions using
[Link]().

15.1.1 Random Numbers

The basis of all of these sampling methods is in the generation of random numbers, and this is something that
computers are not really capable of doing. However, there are plenty of algorithms that produce pseudo-random
numbers, the simplest of which is the linear congruential generator. This is a very simple function that is defined by
a recurrence relation you put one number in to get the second number, and then feed that back in to get the third, and
then repeat the cycle

where a,c, and m are parameters that have to be chosen carefully. All of them, and the initial input x0 (which is
known as the seed), are integers, and so are all of the outputs. The modulus function means that the largest number
that can be produced is m, and so there are at most m numbers that can be produced by the algorithm. Once one
number appears a second time, the whole pattern will repeat again since the equation only uses the current output as
input. The length of the sequence between repeats is the period, and it should obviously be as long as possible, since
it is the most obvious non-randomness in the algorithm. There has been a lot of investigation of choices of the
parameters so that the period is length m, so that every integer between 0 and m is produced before the pattern
cycles.

The other troublesome thing about random numbers is that it is not actually possible to prove that a sequence of
numbers is truly random. There are several tests that can be made of a sequence of numbers to see if they seem to be
random. Examples include calculating the entropy of the sequence using a compression algorithm on the sequence
and just checking how many numbers are odd compared to even. However, you can never guarantee that a sequence
is random, just that it hasn’t failed most of the tests.

15.1.2 Gaussian Random Numbers

The usual method of doing this is the Box–Muller scheme, which uses a pair of uniformly randomly distributed
numbers in order to make two independent Gaussian-distributed numbers with zero mean and unit variance.
Suppose that we had two independent zero mean, unit variance normals. Then their product is:

If we use polar coordinates instead (so x = rsin(θ) and y = rcos(θ)) then we would have r2 = x2 +y2 and θ =
tan−1(y/x). Both of these are uniformly distributed random variables (0 ≤ r ≤ 1 and 0 ≤ θ < 2π). In other words, θ =
2πU1 where U1 is a uniformly distributed random variable. Now we just need a similar expression for r. We can
write that:

6
BAI702,Machine Learning-II

If we use the change of variables 1 2r′2 = s (so that r′dr′ = ds) then:

The Box–Muller Scheme

• Pick two uniformly distributed random numbers 0 ≤ U1,U2 ≤ 1

• Set θ =2πU1 and r =p(−2ln(U2))
• Then x = rcos(θ) and y = rsin(θ) are independent Gaussian-distributed variables with zero mean and unit variance.

FIGURE 15.1 Histogram of 1,000 Gaussian samples created by the Box–Muller scheme. The line gives the
Gaussian distribution with zero mean and unit variance.

15.2 MONTE CARLO OR BUST

The Monte Carlo principle states that if you take independent and identically distributed (i.e., well-
behaved) samples x(i) from an unknown high-dimensional distribution p(x), then as the number of
samples gets larger the sample distribution will converge to the true distribution. In other words,
sampling works. Written mathematically, this says:

7
BAI702,Machine Learning-II

The fact that the sample distribution becomes more and more like the true one as we take more and more samples
tells us that samples are more likely to be drawn from parts of the distribution that have high probability. This is
very useful, since places where there are more samples will allow us to approximate the function well in those
regions, and we only really care about the appearance of the function in those places—if the probability is small,
then it doesn’t matter that the number of samples is small (the area is sparsely covered) since the probability is low
there anyway. If we use methods that don’t know anything about the probability (such as sampling based on a
uniform grid and using splines or something similar), then we have to treat all areas of the space as equally likely,
which means that there is going to be a lot of computational resources wasted. There is another benefit, too. In
addition to using the samples to approximate the expectation, we can also find a maximum, that is, the most likely
outcome, from the samples

15.3 THE PROPOSAL DISTRIBUTION

Introduction:In many practical problems, the target probability distribution p(x) is difficult or computationally
expensive to sample from directly. The Proposal Distribution Method overcomes this difficulty by introducing a
simpler distribution q(x), known as the proposal distribution.

Unnormalised Target Distribution

The target distribution is often known only up to a normalisation constant:

p(x) = (1/Zp) * p~(x)

where p~(x) is the unnormalised distribution.

Choice of Proposal Distribution

A proposal distribution q(x) is chosen such that:

- It is easy to sample from

- It covers the support of p(x)

- There exists a constant M such that p~(x) ≤ Mq(x)

Rejection Sampling Principle

Samples drawn from q(x) are accepted or rejected using rejection sampling to ensure correctness.

8
BAI702,Machine Learning-II

Algorithm Steps

1. Sample x* from q(x)

2. Generate u ~ Uniform(0, Mq(x*))

3. Accept x* if u < p~(x*)

4. Otherwise reject and repeat

Efficiency

Efficiency depends on M. Smaller M gives fewer rejections.

Advantages

- Simple implementation

- No need for normalisation constant

- Applicable to complex distributions

Limitations

- Inefficient for poor choice of q(x)

- High rejection rate in high dimensions

FIGURE 15.3 The histogram shows samples of a mixture of two Gaussians (given by the solid line)

9
BAI702,Machine Learning-II

FIGURE 15.4 The histogram shows samples created using sampling-importance-resampling from a mixture of two
Gaussians.

15.4 MARKOV CHAIN MONTE CARLO

15.4.1 Markov Chain

In probabilistic terms a chain is a sequence of possible states, where the probability of being in state s at
time t is a function of the previous states. A Markov chain is a chain with the Markov property, i.e., the
probability at time t depends only on the state at t − 1, The set of possible states are linked together by
transition probabilities that say how likely it is that you move from the current state to each of the
others, and they are generally written as a matrix T. They might be constant, or functions of some other
variables, but here we will assume that they are constant. Given a chain, we can perform a random walk
on the chain by choosing a start state and randomly choosing each successive state according to the
transition probabilities. The link to sampling that we need is that if the transition probabilities reflect the
distribution that we wish to sample from, then a random walk will explore that distribution. One
problem with this is that random walks are very inefficient at exploring space, since they move back
towards the start as often as they move away, which means the distance they move from the start
scales as √t, where t is the number of samples. We therefore want to explore more efficiently than just
using a random walk. We do this by setting up our Markov chain so that it reflects the distribution we
wish to sample from, and we want the distribution p(x(i)) to converge to the actual distribution p(x) no
matter what state we start from. Since we can start from any state, this tells us that every state is
reachable from every other state, which means that the chain is irreducible so that the transition matrix
can’t be cut up into smaller matrices. The chain also has to be ergodic, which means that we will revisit

10
BAI702,Machine Learning-II

every state, so that the probability of visiting any particular state in the future never goes to zero, but is
not periodic, which means that we can visit at any time, not just every k iterations for some constant k.
We also want the distribution p(x) to be invariant to the Markov chain, which means that the transition
probabilities don’t change the distribution:

15.4.2 The Metropolis–Hastings Algorithm

11
BAI702,Machine Learning-II

Key Concepts Covered:

• Importance Sampling
• Weight computation
• Estimation of expectations
• Variance reduction techniques
• Practical considerations

Importance Sampling:
Importance Sampling is a technique used to estimate properties of a target distribution using samples drawn from a
different distribution.

Let p(x) be the target distribution and q(x) be the proposal distribution.
The expectation is estimated as:

E[f(x)] = Σ f(x) p(x) / q(x)

Weights:
Each sample is assigned a weight:
w(x) = p(x) / q(x)

These weights correct the bias introduced by sampling from q(x).

Advantages:
• Reduces variance
• Efficient for rare events
• Flexible choice of proposal distribution

Limitations:
• Sensitive to poor proposal choice
• Weight degeneracy problem

Applications:
• Bayesian inference
• Machine learning
• Signal processing

12