UNIT ‐II
BPN AND BAM
Back Propagation Network
• Rumelhart (early 80’s), Werbos (74),…, explosion
of neural net interest
• Multi‐layer supervised learning
• Able to train multi‐layer perceptrons (and other
topologies)
• Uses differentiable sigmoid function which is the
smooth (squashed) version of the threshold
function
• Error is propagated back through earlier layers of
the network
Multi-Layer Perceptrons
In contrast to perceptrons, multilayer networks can learn not only multiple decision
boundaries, but the boundaries may be nonlinear. The typical architecture of a multi-layer
perceptron (MLP) is shown below.
Output nodes
Internal nodes
x1 w1
x2 net
w2 Σ
O = σ(net) = 1 / 1 + e -net
w0
wn
xn
Input nodes
To make nonlinear partitions on the space we need to define each unit as a nonlinear
function (unlike the perceptron). One solution is to use the sigmoid unit. Another reason
for using sigmoids are that they are continuous unlike linear thresholds and are thus
differentiable at all points.
Back-Propagation Algorithm
Multi-layered perceptrons can be trained using the back-propagation algorithm described
next.
Goal: To learn the weights for all links in an interconnected multilayer network.
Forward Propagation
We begin by defining our measure of error:
Given example X, compute the output of every node until we reach th
E(W) = ½ Σd Σk (tkd – okd) 2
k varies along the output nodes and d over the training examples.
The idea is to use again a gradient descent over the space of weights to find a global
minimum (no guarantee).
• Propagate example X forward through the network
Algorithm:
• Propagate errors backward through the network
1. Create a network with nin input nodes, nhidden internal nodes, and nout output
nodes.
2. Initialize all weights to small random numbers.
3. Until error is small do:
For each example X do
Internal Compute sigmoid
function
Input
Example
1. It implements a gradient descent search over the weight space.
Backward Propagation 2. It may become trapped in local minima.
3. In practice, it is very effective.
A. For each output node k compute the error: 4. How to avoid local minima?
δk = Ok (1-Ok)(tk – Ok)
B. For each hidden unit h, calculate the error:
δh = Oh (1-Oh) Σk Wkh δk where ΔWji = η δj Xji
C. Update each network weight: (Wji and Xji are the input and weight of node i to node j)
C. Wji = Wji + ΔWji
A momentum term, depending on the weight value at last iteration, may also be added to
the update rule as follows. At iteration n we have the following:
ΔWji (n) = η δj Xji + αΔWji (n)
Where α ( 0 <= α <= 1) is a constant called the momentum.
1. It increases the speed along a local minimum.
2. It increases the speed along flat regions.
Remarks on Back-propagation
b) Use stochastic gradient descent.
c) Use different networks with different initial values for the weights.
Multi-layered perceptrons have high representational power. They can represent the
following:
1. Boolean functions. Every boolean function can be represented with a network
having two layers of units.
2. Continuous functions. All bounded continuous functions can also be
approximated with a network having two layers of units.
3. Arbitrary functions. Any arbitrary function can be approximated with a network
with three layers of units.
Generalization and overfitting:
One obvious stopping point for backpropagation is to continue iterating until the error is
below some threshold; this can lead to overfitting.
Validation set
Error
Training set
Number of weight
Use a validation set and stop until the error is small in this set.
Overfitting can be avoided using the following strategies.
Use 10 fold cross validation.
Use weight decay; the weights are decreased slowly on each iteration.
Applications of Neural Networks
Neural networks have broad applicability to real world business problems. They have
already been successfully applied in many industries.
Since neural networks are best at identifying patterns or trends in data, they are well
suited for prediction or forecasting needs including:
sales forecasting
industrial process control
customer research
data validation
risk management
target marketing
Applications of BPN‐
Paint Quality Assessment
Applications of BPN‐
4:1 Video Data Compression
Applications of BPN‐
4:1 Video Data Compression
Backpropagation Learning
• Notations:
– Weights: two weight matrices:
from(1input
w ,0) layer (0) to hidden layer (1)
from
w( 2hidden
,1) layer (1) to output layer (2)
w2(1,1,0from
weight ) node 1 at layer 0 to node 2 in layer 1
– Training samples: pair of
{( x p , d p ) p = 1,..., P}
so it is supervised learning
– Input pattern: x p = ( x p ,1 ,..., x p ,n )
– Output pattern: o p = (o p ,1 ,..., o p ,k )
– Desired output: d p = (d p ,1 ,..., d p ,k )
– Error:
p, j p, j− dfor output j when xp is applied
l = o error p, j
P K
sum square error = ∑ ∑ (l p , j ) 2
p =1 j =1
This error drives learning (change and
w(1,0) ) w( 2,1)
Backpropagation Learning
• Sigmoid function again:
– Differentiable:
1
S ( x) =
1 + e− x
1 −x
S ' ( x) = − −x 2
⋅ (1 + e )'
(1 + e )
1 −x
=− −x 2
⋅ ( − e )
(1 + e ) Saturatio Saturatio
n
1 e−x n
= ⋅ region region
1 + e 1 + e− x
−x
= S ( x)(1 − S ( x))
– When |net| is sufficiently large, it moves into one of the two
saturation regions, behaving like a threshold or ramp function.
• Chain rule of differentiation
dz dz dy dx
if z = f ( y ), y = g ( x), x = h(t ) then = ⋅ ⋅ = f ' ( y ) g ' ( x)h' (t )
dt dy dx dt
Backpropagation Learning
• Forward computing:
– Apply an input vector x to input nodes
– Computing output vector x(1) on hidden layer
x (j1) = S (net (j1) ) = S (∑ w(j1,i,0) xi )
i
– Computing the output vector o on output layer
ok = S (netk( 2) ) = S (∑ wk( 2, ,j1) x (j1) )
j
– The net is said to be a map from input x to output o
• Objective of learning: P K
– reduce sum square error ∑ ∑ (l p , j )
2
p =1 j =1
for the given P training samples as much as possible (to
zero if possible)
Backpropagation Learning
• Idea of BP learning:
– Update of weights in w(2, 1) (from hidden layer to output layer):
delta rule as in a single layer net using sum square error
– Delta rule is not applicable to updating weights in w(1, 0) (from
input and hidden layer) because we don’t know the desired
values for hidden nodes
– Solution: Propagating errors at output nodes down to hidden
nodes, these computed errors on hidden nodes drives the
update of weights in w(1, 0) (again by delta rule), thus called
error BACKPROPAGATION (BP) learning
– How to compute errors on hidden nodes is the key
– Error backpropagation can be continued downward if the net
has more than one hidden layer
– Proposed first by Werbos (1974), current formulation by
Rumelhart, Hinton, and Williams (1986)
Backpropagation Learning
• Generalized delta rule:
– Consider sequential learning mode: for a given sample (xp, dp)
E = ∑k (l p ,k ) 2
– Update of weights by gradient descent
For weight in w(2, 1): Δwk( 2, ,j1) ∝ (−∂E / ∂wk( 2, ,j1) )
For weight in w(1, 0): Δw(j1,i,0) ∝ (−∂E / ∂w(j1,i,0) )
– Derivation of update rule for w(2, 1):
since E is a function of lk = dk – ok, dk – ok is a function net k,( 2)
and net k( 2)is a function of wk( 2, ,j1,) by chain rule
Backpropagation Learning
ok
– Derivation of update rule for w(j1,i,0)
wk( 2, ,j1)
consider hidden node j:
weight w(j1,i,0)influences net (j1) j
it sends S (net (j1) )to all output nodes w(j1,i,0)
∴ all K terms in E are functions of w(j1,i,0) i
E = ∑ k ( d k − ok ) 2 , ok = S ( net k( 2 ) ), net k( 2 ) = ∑ j x (j1) wk( 2, ,j1) ,
x (j1) = S ( net (j1) ), net (j1) = ∑i xi w (j1,i, 0 )
by ∂E ∂S (net k( 2) ) ∂net k( 2) ∂x (j1) ∂net (j1)
chain ∂ok ∂net k( 2) ∂x (j1) ∂net (j1) ∂w(j1,i)
rule
Backpropagation Learning
– Update rules:
for outer layer weights w(2, 1) :
where δ k = (d k − ok ) S ' (net k( 2) )
for inner layer weights w(1, 0) :
where μ j = (∑k δ k wk , j ) S ' (net j )
( 2,1) (1)
Weighted sum of
errors from output
layer
Note: if S is a logistic function,
then S’(x) = S(x)(1 – S(x))
Backpropagation Learning
• Pattern classification:
– Two classes: 1 output node
– N classes: binary encoding (log N) output nodes
better using N output nodes, a class is represented as
(0,..., 0,1, 0,.., 0)
– With sigmoid function, nodes at output layer will never be 1 or
0, but either 1 – ε or ε.
– Error reduction becomes slower when moving into saturation
regions (when ε is small).
– For fast learning, for a given error bound ε,
set error lp,k = 0 if |dp,k – op,k| ≤ ε
– When classifying a input x using a trained BP net, classify it to
the kth class if with dk. > dl for all l != k
Backpropagation Learning
• Pattern classification: an example
– Classification of myoelectric signals
• Input pattern: 3 features (NIF, VT, RR), normalized to real
values between 0 and 1
• Output patters: 2 classes: (success, failure)
– Network structure: 2‐5‐3
• 3 input nodes, 2 output nodes,
• 1 hidden layer of 5 nodes
• η = 0.95, α = 0.4 (momentum)
– Error bound ε = 0.05
– 332 training samples
– Maximum iteration = 20,000
– When stopped, 38 patterns remain misclassified
Hopfield Memories is of 2 types
Discrete Hopfield NNs
Continuous Hopfield NNs
Associative Memories is of 2
types
Hopfield Memory
Bidirection Memory
BPN Architecture
BPN Data Structure
Feedforward/Feedback NNs
Feedforward NNs
The connections between units do not form cycles.
Usually produce a response to an input quickly.
Most feedforward NNs can be trained using a wide variety of
efficient algorithms.
Feedback or recurrent NNs
There are cycles in the connections.
In some feedback NNs, each time an input is presented, the NN
must iterate for a potentially long time before it produces a
response.
Usually more difficult to train than feed forward NNs.
Supervised‐
Learning NNs
• Feedforward NNs
– Perceptron
– Adaline, Madaline
– Backpropagation (BP)
– Artmap
– Learning Vector Quantization (LVQ)
– Probabilistic Neural Network (PNN)
– General Regression Neural Network (GRNN)
• Feedback or recurrent NNs
– Brain-State-in-a-Box (BSB)
– Fuzzy Congitive Map (FCM)
– Boltzmann Machine (BM)
– Backpropagation through time (BPTT)
Unsupervised‐
Learning NNs
• Feedforward NNs
– Learning Matrix (LM)
– Sparse Distributed Associative Memory (SDM)
– Fuzzy Associative Memory (FAM)
– Counterprogation (CPN)
• Feedback or Recurrent NNs
– Binary Adaptive Resonance Theory (ART1)
– Analog Adaptive Resonance Theory (ART2, ART2a)
– Discrete Hopfield (DH)
– Continuous Hopfield (CH)
– Discrete Bidirectional Associative Memory (BAM)
– Kohonen Self-organizing Map/Topology-preserving map
(SOM/TPM)
The Hopfield
NNs
• In 1982, Hopfield, a Caltech physicist,
mathematically tied together many
of the ideas from previous research.
• A fully connected, symmetrically
weighted network where each node
functions both as input and output
node.
• Used for
– Associated memories
Combinatorial optimization
Hamming Distance
Hopfield Memory for TSP
Associative
Memories
• An associative memory is a content-addressable
structure that maps a set of input patterns to a
set of output patterns.
• Two types of associative memory: autoassociative
and heteroassociative.
• Auto-association
– retrieves a previously stored pattern that most closely
resembles the current pattern.
• Hetero-association
– the retrieved pattern is, in general, different from the
input pattern not only in content but possibly also in type
and format.
Associative
Memories
Auto-association
A memory
A
Hetero-association
Niagara Waterfall
memory
Optimization
Problems
• Associate costs with energy
functions in Hopfield Networks
– Need to be in quadratic form
• Hopfield Network finds local,
satisfactory soluions, doesn’t choose
solutions from a set.
• Local optimums, not global.
The Discrete Hopfield
NNs
w1n w2n w3n
w13 w23 wn3
w12 w32 wn2
w21 w31 wn1
1 2 3 ... n
I1 I2 I3 In
v1 v2 v3 vn
BAM Architecture
BAM Energy landscape
Auto associative bam
architecture
Single layer structure of bam
Hopfield memory architecture
Inhibitory connections between peS FOR TSP
PROBLEM
BAM DATASTRUCTURE
Backpropagation Learning
• Architecture:
– Feedforward network of at least one layer of non‐linear hidden
nodes, e.g., # of layers L ≥ 2 (not counting the input layer)
– Node function is differentiable
most common: sigmoid function
• Learning: supervised, error driven,
generalized delta rule
• Call this type of nets BP nets
• The weight update rule
(gradient descent approach)
• Practical considerations
• Variations of BP nets
• Applications
Review questions
• Discuss the role of generalized delta rule
in neural networks.
• What is the importance of hamming distance in
visualizing the data space.
• Discuss the pros and cons of BPN architecture
• State the importance of BAM energy function.
• How the Hopfield memory model is useful for
optimizaion problems.
References
• J. A. Freeman and D. M. Skapura, Neural Networks‐ Algorithms,
Applications and Programming Techniques, Pearson Education(
singapore) Pvt. Ltd., 1991.
(Chapters 3 &4)
• [Link]
• [Link]/webus/tutorial/BPN_tutorial.html
/neural_networks.htm