CS 363: Neural Networks

Lecture-6
Associative Memory
 Types of NN
Feedforward
◼ No feedback during operation (only during determination
of weights)
◼ Perceptron
◼ Backpropagation

Recurrent (feedback during operation)

◼ Hopfield
◼ Kohonen
◼ Associative memory
 Associations

• Associations are a concept which we are very familiar with

humans, since our memories clearly operate using
associations to link facts, places, events, people and other
concepts together.

• For example, visiting a location may remind you of a specific

person.
 Associations

• Human memory connects items (ideas, sensations) that are:

– occur simultaneously

– occur in close succession

– similar

– contrary

• In other words, items which occur close to one another

(either in space or time) are associated in memory somehow.
 Associative Memory

• An associative memory neural net may serve as a highly

simplified model of human memory.

• Neural networks are capable of solving many classes of

problem.

• These include pattern classification, function approximation,

data clustering and control.

• Any neural network which can perform pattern recognition

can act as an associative memory.
 Associative Memory

• This can be seen in that pattern recognition involves the

association of a data vector with a class.

• We view the data as our input, and the class as our output

• The main property of an associative memory is mapping of

input patterns into output patterns of neural activity
 Associative Memory

• A memory is “filled” through a learning process

• During learning an input pattern called a key is presented to

the memory that transforms it into a memorized pattern

• During recall a noised or incomplete version of the original

key is presented to the memory

• Regardless of the imperfect input key, the associative memory

outputs the corresponding memorized output pattern
 Associative Memory

• An Example of Associative Recall:

– Recall a stored pattern by a noisy
input pattern
– Often call this type of NN
“associative memory”
– Neural associative memories are
able to operate with noisy or
incomplete data (they generalize)
 Associative Memory
Input: Pattern (often noisy/corrupted)
Output: Corresponding pattern (complete / relatively noise-free)
Process
1. Load input pattern onto core group of highly-interconnected
neurons.
2. Run core neurons until they reach a steady state.
3. Read output off of the states of the core neurons.

Inputs Outputs

Input: (1 0 1 -1 -1) Output: (1 -1 1 -1 -1)

 Properties of associative memories

• An associative memory is distributed

– the stored data is distributed over the network.

– this enables increased fault tolerance

• Input pattern (key) and output (memorized pattern) are

vectors

• Information is stored in memory using a large number of

neurons

• Information contained in the key determines the “address” of

the pattern in the memory
 Types of associative memories

• Autoassociative memory:
– data items are associated with themselves.

– input vector (key) is associated to its self in the memory

– dimension of input and output vectors is the same

• Heteroassociative memory:
– arbitrary input vectors (keys) are associated with arbitrary memorized
vectors

– dimension of input and output vectors can be different

 Types of associative memories
Auto-associative: X = Y

*Recognize noisy versions of a pattern

Hetero-associative Bidirectional: X <> Y

BAM = Bidirectional Associative Memory

*Iterative correction of input and output

 Architectures of associative memories

• Architectures of NN associative memory

– single layer: for auto (and some hetero)
associative
– two layers: for heteroassociative
• Learning algorithms for AM
– Hebbian learning rule and its variations
– gradient descent
• Analysis
– storage capacity (how many patterns can be
remembered correctly in AM)
– learning convergence
 Hopfield Networks

• The Hopfield network is an example of an

autoassociative memory.
• The Hopfield network is known as a recurrent
network, which means its outputs are fed back into its
inputs.
• These networks were introduced to collect and
retrieve memory and store various patterns.
 Hopfield Networks

• The Hopfield network consists of associative memory.

• This memory allows the system to retrieve the
memory using an incomplete portion.
• The network can restore the closest pattern using the
data captured in associative memory.
• This feature of Hopfield networks makes it a good
candidate for pattern recognition.
 Hopfield Networks

• It consists of a single layer of neurons, which are fully

connected and have symmetric weights.
• Each neuron accepts its input from the outputs of all other
neurons and its own input.
• The input and output sizes must be the same in these
networks.
 Single-layer n-neuron Hopfield network

x1 1 y1

Output S ignals
Input S ignals

x2 2 y2

xi i yi

xn n yn
 How it works?
• Here, a neuron is either on or off the situation.
• The state of a neuron (on +1 or off 0) will be restored, relying
on the input it receives from the other neuron.
• A Hopfield network is at first prepared to store various
patterns or memories.
• Afterward, it is ready to recognize any of the learned patterns
by uncovering partial or even some corrupted data about that
pattern, i.e., it eventually settles down and restores the
closest pattern.
• Thus, similar to the human brain, the Hopfield model has
stability in pattern recognition.
 How it works?
• Example: Suppose we have trained our Hopfield Net on the three
patterns given in the following figure,

• Next we input a pattern which is a bit like one of these, say the left
most one given in the following figure. Leave the network to run. It
gradually alters the pattern we give it until it has reconstructed one
of the originals ones, the right most one.
 How it works?

• Example of how Hopfield network

can reconstruct images.
• These are binary images with 130 x 180
pixels.
• The images on the right were recalled
by the memory after presentation of
the corrupted images shown on the left.
• The middle column shows some
intermediate states.
• A sparsely connected Hopfield network
with seven stored images was used.
Hopfield Networks Types
 Discrete Hopfield Network

• It is a fully interconnected neural network where

each unit is connected to every other unit.

• It behaves in a discrete manner, i.e. it gives finite

distinct output, generally of two types:
– Binary (0/1): the output is either 0 or 1.

– Bipolar (-1/1): the output is either -1 (When output < 0) or

1 (When output > 0)
 Discrete Hopfield Network
• The weights associated with this network is symmetric in
nature and has the following properties:
– wij = wji
– wii = 0  0 w12 w13  w1n 
w 0 w23  w2 n 
 21 
W =  w31 w32 0  w3 n 
 
      
 wn1 wn 2 wn 3  0 

• This is a form of Hebbian learning.

• This learning rule has the advantage that it is very quick to
calculate, especially when compared to learning methods
such as backpropagation
 Structure & Architecture
• The architecture of the Hopfield network consists of
the following elements:
– Individual nodes preserve their states until required an
update.
– The node to be updated is selected randomly.
– Each node is connected to all other nodes except itself.
– The state of each node is either 0/1 or 1/-1.
– The Hopfield network structure is symmetric, i.e., Wij = Wji
for all i's and j's.
 Structure & Architecture

• The figure shows a sample representation of a Discrete Hopfield Neural

Network architecture having the following elements:
• x1, x2, x3 -> represents the input.
• y1, y2, y3 -> represents output obtained from each neuron.
• Wij -> weight associated with the connection between the ith and the jth
neuron.
 Four Components
How to train the network?
How to update a node?
What sequence should use when updating nodes?
How to stop?
 Training Algorithm
• For an autoassociative net, the training input and target
output vectors are identical.
• The process of training is often called storing the vectors,
which may be binary or bipolar.
• A stored vector can be retrieved from distorted or partial
(noisy) input if the input is sufficiently close to it.
• It is based on the Hebbian principle.
• In training, algorithm weights are updated using a specific
rule.
• The rule is different for binary and bipolar.
 Training Algorithm
• For storing a set of 'N' input patterns [ X(n) where n =
1 to N ], the rule followed is as follows:
• The weight matrix W to store a set of input vectors,
where:
– In case of input vectors being binary, the weight matrix
W={wij} is given by:

for all i ≠ j `

– When the input vectors are bipolar, the weight matrix

W={wij} can be defined as:

where wij = 0 for all i = j

 Testing Algorithm
• Step 0: Initialize the weights to store patterns, i.e., weights
obtained from training algorithm (using Hebb rule, outer
product)
• Step 1: When the activations of the net are not converged,
then perform Steps 2-8.
• Step 2: Perform Steps 3-7 for each input vector X.
• Step 3: Make the initial activations of the net equal to the
external input vector X:
yi = xi for i = 1 to N
• Step 4: Perform Steps 5-7 for each unit yi. (Here, the units are
updated in random order)
 Testing Algorithm
• Step 5: Calculate the net input of the network:

• Step 6: Apply the activations over the net input to calculate

the output:

where θi is the threshold and is normally taken as zero.

• Step 7: Now feed back the obtained output yi to all other
units. Thus, the activation vectors are updated.
• Step 8: Finally, test the network for convergence.
– If there are convergence, this indicates that the net recognizes the
input vector as the training vector X(n) where n = 1 to N.
 Example 1

• We are required to create Discrete Hopfield Network

with bipolar representation of input vector as [1 1 1 -1]
or [1 1 1 0] (in case of binary representation) is stored in
the network.

• Test the Hopfield network with missing entries in the first

and second component of the stored vector (i.e. [0 0 1
0]).

• Does the net recognize the input vector?

 Step by Step Solution
• Step 0 - given input vector, x = [1 1 1 -1] (bipolar) and we
initialize the weight matrix (wij)as:
= Xi(n)TXj(n)

• and weight matrix with no self connection is:

 Step by Step Solution
• Step 1: When the activations of the net are not converged,
perform Steps 2-8.

• Step 2: Perform Steps 3-7 for each input vector X.

• Step 3 : input vector x with missing entries, x = [0 0 1 0] ([x1 x2

x3 x4]) (binary)
– Make yi = x = [0 0 1 0] ([y1 y2 y3 y4])

• Step 4: Perform Steps 5-7 for each unit yi. (Here, the units are
updated in random order)
– we will do the next steps for all values of yi and check if there is
convergence or not
 Step by Step Solution
choose unit y1 to update its activation:
 Step by Step Solution
• now for next unit, we will take updated value via feedback.
(i.e. y = [1 0 1 0])
• choose unit y3 to update its activation:
 Step by Step Solution
• now for next unit, we will take updated value via feedback.
(i.e. y = [1 0 1 0])
• choose unit y4 to update its activation:
 Step by Step Solution
• now for next unit, we will take updated value via feedback.
(i.e. y = [1 0 1 0])
• choose unit y2 to update its activation:

• The response of the net indicates that it recognize the vector

as the training vector x = [1 1 1 -1]
 Note
• The differences in the stored vector take one of two
forms: "mistakes or noisy" in the data or "missing"
data:
– The only "mistakes" we consider are changes from + 1 to -
1 or vice versa.
– We use the term "missing" data to refer to a component
that has the value 0, rather than either + 1 or -1