MODULE 4
Data Compression and Codebook Approach
• Data compression is closely related to competitive learning, as both
methods replace raw inputs with representative prototypes to reduce
redundancy.
• In the context of communication, instead of transmitting the entire
dataset, a sender and receiver agree on a codebook of prototype vectors.
• The sender then transmits only the index of the prototype vector that
corresponds to the data, rather than the data itself.
• This significantly reduces the amount of information that must be sent.
Furthermore, efficiency can be improved by using shorter indices for more
common datapoints, a principle widely used in modern sound and image
compression algorithms.
Vector Quantisation and Prototype Selection
• A limitation of the codebook approach is that it cannot contain every
possible datapoint.
• When a datapoint is not in the codebook, it is approximated by
transmitting the index of the nearest prototype vector, a method known as
vector quantisation, which is the foundation of lossy compression.
• Prototype vectors divide the input space into regions known as Voronoi
sets.
• The key challenge is selecting prototype vectors that best represent
potential inputs. This process, called learning vector quantisation (LVQ),
can be achieved through algorithms such as k-means, or more advanced
methods like the Self-Organising Feature Map (SOFM).
Introduction to Self-Organising Feature Map
(SOM)
• The Self-Organising Feature Map (SOM),
proposed by Teuvo Kohonen in 1988, is one of
the most widely used competitive learning
algorithms.
• SOM was designed to explain how sensory
signals are mapped into the cerebral cortex
with an ordered structure.
• Example: In the auditory cortex, neurons that
respond to similar sounds are positioned
close to each other, while neurons that
respond to very different sounds are farther
apart.
Two key concepts in SOM:
• Feature Mapping – nearby neurons respond
to similar input patterns.
• Topology Preservation – neurons are arranged
in a 1D or 2D grid, preserving the relative
order of inputs.
Topology Preservation in SOM
• SOM arranges neurons in a grid structure
(1D or 2D).
• The relative order of the input is
preserved, so similar inputs are mapped
close together, and dissimilar inputs are
mapped farther apart.
• This property, known as topology
preservation, ensures that the map
reflects the structure of the input space.
Limitation: For high-dimensional data,
perfect preservation is not always possible.
Best case: If input dimensionality matches
the SOM grid, topology can be preserved
effectively.
Feature Mapping through Neuron Interactions
• SOM introduces interaction between neurons in the same layer through
lateral connections.
• When one neuron “wins” (activates), it influences the neighboring neurons.
• Neurons close in the network should represent similar features → positive
connections pull them closer.
• Neurons far apart should represent different features → negative
connections push them away.
• Very distant neurons are ignored, since they already represent unrelated
features.
• This ensures that the map organizes features smoothly, preserving
similarity across the network.
SOM Algorithm
Cont.
Neighbourhood Connections
• The neighbourhood size is an important
parameter in Self-Organizing Maps
(SOM).
• At the beginning of training, the weights
are random and unordered.
• A large neighbourhood is used so that
the network achieves a rough ordering of
the map.
• As training progresses, the network
begins to fine-tune the local regions, and
the neighbourhood size is gradually
reduced.
• This process takes place in two phases:
ordering with a large neighbourhood and
convergence with a small neighbourhood.
Weight Initialization and Alternatives
• Another way to initialize weights is to use Principal Components Analysis
(PCA), which aligns weights with the largest directions of variation in the
data.
• This approach allows training to begin with a small neighbourhood size, but
it requires batch learning and is not suited for online adaptation.
• While this can be a limitation, one option is to ignore the restriction and
still use SOM in practice.
• Alternatively, specialized models such as Fritzke’s Growing Neural Gas and
Marsland’s Grow When Required Network are designed for situations
where continuous, unsupervised online learning is required.
Self-Organisation
• Self-organisation refers to the spontaneous emergence of global order from local
interactions among neurons, without any external supervision.
• In Self-Organizing Maps, each neuron competes to represent input data, and the
winning neuron along with its neighbors updates its weights based on a
neighborhood function.
• Over time, these local updates lead to a topologically ordered map that reflects
the structure of the input space.
• This process is analogous to birds flying in formation, where each bird adjusts its
position based on nearby birds, resulting in a coordinated group movement.
• The system learns to organize itself naturally, making it highly effective for tasks
like clustering, dimensionality reduction, and data visualization.
• The key insight is that complex, structured behavior can arise from simple,
decentralized rules.
Network Dimensionality and Boundary
Conditions
• Self-Organizing Maps (SOMs) are typically arranged in 1D or 2D grids,
but the choice of dimensionality affects how well the network
represents data.
• In rectangular grids, neurons at the edges behave differently due to
limited neighbors, leading to edge effects that distort learning.
• To mitigate this, boundary conditions must be carefully considered—
especially when the goal is uniform neighborhood interaction across
the map.
Circular and Toroidal Boundary Conditions
One solution to edge effects is to wrap the network boundaries:
• In 1D, a linear chain of neurons is wrapped into a circle, allowing each
neuron to have symmetric neighbors.
• In 2D, the rectangular grid is wrapped into a torus, eliminating edges
and ensuring uniform topology. This transformation ensures that all
neurons are treated equally during learning, improving map
consistency and reducing bias.
Diagram
Distance Computation in Toroidal Maps
• In toroidal SOMs, computing distances between neurons requires
considering multiple copies of the map.
• Instead of using Euclidean distance on a flat grid, the algorithm
selects the shortest path across all possible wrap-around
connections.
• This approach preserves neighborhood relationships even across
boundaries, ensuring accurate weight updates and topological
integrity.
Sampling and Pseudo-Random Numbers
• Sampling is a core technique in often requiring random numbers
drawn from specific distributions.
• Computers generate pseudo-random numbers—deterministic
sequences that mimic randomness.
• A common method is the Linear Congruential Generator (LCG),
defined by:
• This method produces a sequence with a fixed period, and the quality
of randomness depends on parameter selection.
Parameter Selection and Mersenne Twister
• Choosing good parameters is critical to avoid patterns and ensure
long periods. Example values used in practice:
• Modern algorithms like the Mersenne Twister improve upon LCGs by
using Mersenne primes to achieve extremely long periods and better
statistical properties.
• Despite improvements, all pseudo-random generators are
deterministic and must be seeded carefully to avoid repetition.
Testing Randomness
• It’s impossible to prove that a sequence is truly random. Instead, we
apply statistical tests to check for signs of predictability:
• Entropy analysis: Measures uncertainty in the sequence
• Compression tests: Random sequences resist compression
• Odd/even balance: Checks uniformity in binary properties
Generating Gaussian Random Numbers
• Computers typically generate uniform
random numbers, but many applications
require samples from a Gaussian distribution.
• The Box–Muller scheme transforms two
uniform random variables into two
independent standard normal variables:
• This produces samples with zero mean and
unit variance, suitable for simulations and
probabilistic models.
Histogram of Gaussian Samples
• The Box–Muller method
effectively approximates the
Gaussian distribution.
• The histogram of 1,000 samples
closely follows the theoretical
bell curve, confirming the
method’s accuracy.
• This visual validation is crucial
when assessing the quality of
random number generators in
practice.
Efficiency and Rejection Sampling
• Box–Muller includes a rejection step: if the sampled point lies
outside the unit circle, it’s discarded and resampled.
• This adds computational cost but avoids complex transformations.
• Alternative methods like the Ziggurat algorithm are more efficient
for large-scale sampling.
• Rejection sampling is widely used because it balances simplicity and
performance, especially when targeting specific distributions.
Monte Carlo Sampling and Expectation
Estimation
Dirac Delta and Sampling Accuracy
Proposal Distribution and Rejection Sampling
Rejection Sampling
Importance Sampling
Cont.
Metropolis-Hastings Algorithm
Cont.