CSC604 (Machine Learning)
Module IV
➢ BY:
DR. ARUNDHATI DAS
Module IV: Clustering
• 4.1 Hebbian Learning rule.
• 4.2 Expectation -Maximization algorithm for clustering.
2
Hebbian Learning rule/ Hebb Method
• The Hebbian Learning Rule is one of the fundamental learning principles in neural
networks, based on the idea that "neurons that fire together, wire together.
• In Hebbian Learning Rule if two interconnected neurons are 'on' simultaneously
then the weights associated with these neurons can be increased by the
modification made in their synaptic gap (strength).
• Hebbian learning states that the weight between two neurons increases if the
activation of one neuron leads to the activation of the other. In simple terms, if two
connected neurons are active at the same time, the strength of their connection is
increased.
• Hebbian learning can be applied in unsupervised learning, especially in clustering
and self-organizing networks. It helps identify patterns and associations in data
without requiring labeled inputs.
• The Hebb rule is more suited for bipolar data (1, -1) than binary data (1, 0).
3
Hebbian Learning rule/ Hebb Method
• The Hebbian Learning Rule is one of the fundamental learning principles in neural
networks, based on the idea that "neurons that fire together, wire together.
• In Hebbian Learning Rule if two interconnected neurons are 'on' simultaneously
then the weights associated with these neurons can be increased by the
modification made in their synaptic gap (strength).
• Hebbian learning states that the weight between two neurons increases if the
activation of one neuron leads to the activation of the other. In simple terms, if two
connected neurons are active at the same time, the strength of their connection is
increased.
• Hebbian learning can be applied in unsupervised learning, especially in clustering
and self-organizing networks. It helps identify patterns and associations in data
without requiring labeled inputs.
• The Hebb rule is more suited for bipolar data (1, -1) than binary data (1, 0).
4
5
Why Hebbian learning rule is used for
clustering?
• Hebbian learning is used for clustering because it helps self-organize
neurons based on the similarity of input data.
• It strengthens connections between neurons that frequently activate
together, allowing patterns to emerge naturally, just like how the
human brain recognizes and groups similar experiences.
6
Hebbian Learning rule
• The weight update in Hebb rule is given by
• Here, y is the output from neighbouring (post synaptic) neuron, a xi is the input from the pre-synaptic neuron.
• When both the neurons are activate together, the connections strengthens resulting in increase in the Wi value.
Meaning, if both xi and y are high, the weight increases, reinforcing the connection.
7
Hebbian Learning rule
• The weight update in Hebb rule is given by
• Here, y is the output from neighbouring (post synaptic) neuron, a xi is the input from the pre-synaptic neuron.
• When both the neurons are activate together, the connections strengthens resulting in increase in the Wi value.
Meaning, if both xi and y are high, the weight increases, reinforcing the connection.
8
Design a Hebb net to implement logical AND function. (Use bipolar inputs and
targets)
9
11
Threshold>=2 Linear Separable
[Link] a Hebb net to implement logical OR function. (Use bipolar inputs and targets)
Q2. Design a Hebb net to implement logical XOR function. (Use bipolar inputs and targets)
Comment on the result.
Threshold>=2 Linear Separable
[Link] a Hebb net to implement logical OR function. (Use bipolar inputs and targets)
Q2. Design a Hebb net to implement logical XOR function. (Use bipolar inputs and targets)
Comment on the result.
Q2. Design a Hebb net to implement logical XOR function. (Use bipolar inputs and targets)
Comment on the result.
14
15
16
17
2 input Logic Gate 3 input Logic Gate
2 inputs (x1,x2) 3 inputs (x1,x2,x3)
2 weights (w1,w2) 3 weights (w1,w2,w3)
1 output (y) 1 output (y)
Variation are 4 Variation are 8
4 times repeated 8 times repeated
Pattern
9 inputs (x1….x9)
9 weights (w1..w9)
2 output (y)
18
20
21
Q. H. W.
D3
x1 x2 x3 x4 Y
1 -1 1 -1 1
1 1 1 -1 1
-1 -1 1 1 -1
1 1 -1 -1 -1
D2
D1
Expectation –Maximization (EM) algorithm
for clustering
23
Expectation –Maximization (EM) algorithm for clustering
• EM algorithm is the base of many unsupervised clustering algorithm.
• The EM algorithm is an iterative optimization algorithm used to estimate the parameters of
statistical models, particularly in the context of models with latent (unobserved) variables or
missing data.
• Observed vs. Unobserved (Latent) Variables: In statistics and machine learning, variables can be categorized
as observed (measured directly) and unobserved (latent) (hidden and inferred).
• Why Use EM for Clustering?
• Unlike k-means, which assigns each data point to one cluster, EM allows for soft clustering, meaning each
point has a probability of belonging to multiple clusters. This is useful when clusters overlap.
• EM algorithm is commonly employed when dealing with likelihood-based estimation problems,
such as those involving Gaussian Mixture Models (GMMs) and Hidden Markov Models
(HMMs).
• EM algorithm provides a general approach to learning in presence of unobserved variables.
• In many practical learning settings, only a subset of relevant features or variables might be
observable. Eg: Hidden Markov, NLP applications, medical imaging.
24
Expectation –Maximization (EM) algorithm for clustering
• The EM algorithm alternates between two steps until convergence:
• Estimation (E-step) : Estimate the expectation from some random data.
• Maximization (M-step): Whatever is estimated should be maximized to find the best result.
• From given data EM learns a theory which tells how each example to be classified and
how to predict the feature value of each class.
• EM algorithm can be applied when the data is missing or incomplete.
• Basically, EM algorithm uses the available observed data of the dataset to estimate the
missing data (Estimation step) and then update the other parameters of the model or
hypothesis (Maximization step).
25
Expectation Maximization
This formula gives the sample mean (i.e., the fraction of heads observed for each coin). Since we
know which flips belong to which coin, we can directly compute the probabilities.
Expectation Maximization
• When Hidden Variables Exist
• We only observe the overall sequence of flips without coin labels.
• If we didn’t know which flip belonged to which coin, we would need a more
complex method, like the Expectation-Maximization (EM) Algorithm, to
estimate θA and θB.
27
Example
Example
Coin C1 is A, Coin C2 is B
Maximum likelihood:
Example with Hidden Variable
Example with Hidden Variable
EM Algorithm
Example with Hidden Variable
Example with Hidden Variable
EM Algorithm: Example
The 5 rounds of 10 coin tosses with 0.5
This one is Binomial Distribution Formula to
calculate probability.
• The binomial formula helps us compute the likelihood that a given set of coin flips came
from either coin A or coin B.
Example with Hidden Variable
• The binomial formula helps us compute the likelihood that a given set of coin flips came from either coin A or coin B.
EM Algorithm: M-Step
Example with Hidden Variable
Example with Hidden Variable
Image courtesy: YouTube
Expectation Maximization