NEURAL NETWORKS AND DEEP LEARNING

Subject Code - CSE_ 3273

CREDITS – 03

Module -2

1
INTRODUCTION

Discussion on

➢ Cover’s theorem on the separability of patterns. Illustrated by revisiting the XOR

problem

➢ Radial-basis functions, setting the stage for the construction of radial-basis function (RBF)

➢ The K-means algorithm. Popular, algorithm for clustering, which is well suited for
training the hidden layer in an unsupervised manner

➢ K-means clustering algorithm to describe a recursive implementation of least-squares

estimation for training the output layer of the RBF network in a supervised manner

2
 INTRODUCTION

The supervised training of a neural network may be approached in several different ways.

The back-propagation learning algorithm for multilayer perceptrons, or application of a recursive

technique known in statistics as stochastic approximation.

In this chapter, we take a completely different approach. Specifically, we solve the problem of
classifying nonlinearly separable patterns by proceeding in a hybrid manner, involving two stages:

➢ The first stage transforms a given set of nonlinearly separable patterns into a new set for which,
under certain conditions, the likelihood of the transformed patterns becoming linearly separable
is high; the mathematical justification of this transformation is traced to an early paper by Cover
(1965).
➢ The second stage completes the solution to the prescribed classification problem by using least-
squares estimation.

3
 INTRODUCTION

Implementation of hybrid approach to pattern classification by using a radial-basis function

(RBF) network, the structure of which consists of only three layers:

➢ The input layer is made up of source nodes (sensory units) that connect the network to its
environment.
➢ The second layer, consisting of hidden units, applies a nonlinear transformation from the
input space to the hidden (feature) space. For most applications, the dimensionality of the
only hidden layer of the network is high; this layer is trained in an unsupervised manner
using stage 1 of the hybrid learning procedure.
➢ The output layer is linear, designed to supply the response of the network to the activation
pattern applied to the input layer; this layer is trained in a supervised manner using stage 2 of
the hybrid procedure.

4
COVER’S THEOREM ON THE SEPARABILITY OF PATTERNS

When a radial-basis function (RBF) network is used to perform a complex pattern classification
task, the problem is basically solved by first transforming it into a high dimensional space in a
nonlinear manner and then separating the classes in the output layer. The underlying justification is
found in Cover’s theorem on the separability of patterns, which, in qualitative terms, may be stated
as follows (Cover, 1965):

A complex pattern-classification problem, cast in a high-dimensional space nonlinearly,

is more likely to be linearly separable than in a low-dimensional space, provided that the
space is not densely populated.

Radial-basis function (RBF)- Multilayer perceptron 5

COVER’S THEOREM ON THE SEPARABILITY OF PATTERNS

6
Phi are hidden functions in hidden layers which separates class H1 and H2
COVER’S THEOREM ON THE SEPARABILITY OF PATTERNS

m0 is the dimensionality of input and mapping X into high dimensionality space m1.
7
COVER’S THEOREM ON THE SEPARABILITY OF PATTERNS

When linearly separable

Got good surface which linearly separates.

Reverse map of phi space into input space is no longer hyperplane , its is a hyper
surface.

Inverse image of this hyperplane separates input plane and it is a hyper surface. 8
COVER’S THEOREM ON THE SEPARABILITY OF PATTERNS

9
COVER’S THEOREM ON THE SEPARABILITY OF PATTERNS

10
COVER’S THEOREM ON THE SEPARABILITY OF PATTERNS

Cover considered, probability of belonging to class either H1 or H2 among all possible dichotomies. When
m increases probability of m increases hence better separability.
11
THE XOR PROBLEM

The four patterns of

the XOR problem

12
THE XOR PROBLEM

13
 THE XOR PROBLEM

In this example, there is no increase in the

dimensionality of the hidden space compared with
the input space. In other words, nonlinearity
exemplified by the use of Gaussian hidden functions
is sufficient to transform the XOR problem into a
linearly separable one. 14
THE INTERPOLATION PROBLEM

An interpolation problem is a mathematical problem that involves finding a

function that estimates the value of a dependent variable based on a set of
independent variables.

It's a type of estimation that's used in engineering and science

•The interpolation function passes through all the data points in the dataset.
•The function provides a smooth and continuous estimation.
•Interpolation is useful when reliable data points are available.

15
 THE INTERPOLATION PROBLEM

➢ The important point that emerges from Cover’s theorem on the separability of patterns is that
in solving a nonlinearly separable pattern-classification problem, there is usually practical
benefit to be gained by mapping the input space into a new space of high enough dimension.

➢ Basically, a nonlinear mapping is used to transform a nonlinearly separable classification

problem into a linearly separable one with high probability.

Interpolation is a process of determining the unknown values that lie in between the known data points. It is mostly
used to predict the unknown values.
16
THE INTERPOLATION PROBLEM

➢ Consider then a feedforward network with an input layer, a single hidden layer, and
an output layer consisting of a single unit.

➢ We have purposely chosen a single output unit to simplify the exposition without
loss of generality. The network is designed to perform a nonlinear mapping from
the input space to the hidden space, followed by a linear mapping from the hidden
space to the output space.

17
THE INTERPOLATION PROBLEM

Let mo denote the dimension of the input space

18
THE INTERPOLATION PROBLEM

For strict interpolation as specified here, the interpolating surface (i.e., function F) is constrained to pass through
all the training data points.

Mapping of N dimensional real numbers into 1 dimensional real numbers. 19

 THE INTERPOLATION PROBLEM

Taking different phi functions which are centered around different Xi. There are N such phi functions; hence
N such synaptic weights will be there in N dimensional hidden functions to single output space. 20
THE INTERPOLATION PROBLEM

21
 RADIAL-BASIS-FUNCTION NETWORKS

Envision a radial-basis-function (RBF) network in the form of a layered structure having three layers:.

22
RADIAL-BASIS-FUNCTION NETWORKS

23
RADIAL-BASIS-FUNCTION NETWORKS

24
RADIAL-BASIS-FUNCTION NETWORKS

25
 RADIAL-BASIS-FUNCTION NETWORKS

Having a hidden layer of the same size as the input layer could be wasteful of computational
resources, particularly when dealing with large training samples.

When the hidden layer of the RBF network is specified in the manner described in Eq. (5.20), we
find that any correlation existing between adjacent data points in the training sample is
correspondingly transplanted into adjacent units in the hidden layer. Stated in another way, there is
redundancy of neurons in the hidden layer when they are chosen in accordance with Eq. (5.20) by

Gaussian function as the radial-basis function

26
RADIAL-BASIS-FUNCTION NETWORKS

Unlike the case for a multilayer perceptron, the training of an RBF network does not involve
the back propagation of error signals.

Moreover, the approximating function realized by both of these two RBF structures has the
same mathematical form,

27
RADIAL-BASIS-FUNCTION NETWORKS

28
• ALGORITHM 1: RBF NETWORK (DIRECT WEIGHT COMPUTATION)

• Input
• Training set 𝑥𝑖 𝑦𝑖
• Number of RBF neurons 𝑀
• Spread parameter 𝜎

Algorithm Steps
• Select RBF centers 𝑐1 , 𝑐2 , … , 𝑐𝑀
• Fix Gaussian spread 𝜎
• For each input 𝑥𝑖 and center 𝑐𝑗 ,compute:
∣∣𝑥𝑖 −𝑐𝑗 ∣∣2
• 𝜙𝑖𝑗 = exp −
2𝜎2
• Form the RBF activation matrix Φ
• Compute output weights (one-shot):
• 𝑤 = ൫Φ𝑇 Φ)−1 Φ𝑇 𝑦
• Output is obtained using:

• 𝑦ො = ෍ 𝑤𝑗 𝜙𝑗 𝑥
𝑗
Note: No iterative weight updation is performed.

29
ALGORITHM : RBF NETWORK (ITERATIVE WEIGHT UPDATION)
• Input
• Training samples 𝑥𝑖 𝑦𝑖
• Learning rate 𝜂
• RBF centers and σ (fixed)

• Algorithm Steps
• Initialize output weights 𝑤𝑗 randomly (small values)
• For each epoch:
• For each training sample 𝑥𝑖 𝑦𝑖 :
• Compute RBF activations:
∣∣𝑥𝑖 −𝑐𝑗 ∣∣2
• 𝜙𝑗 𝑥𝑖 = exp −
2𝜎2
• Compute network output:

• 𝑦ො𝑖 = ෍ 𝑤𝑗 𝜙𝑗 𝑥𝑖
𝑗
• Compute error:
• 𝑒𝑖 = 𝑦𝑖 − 𝑦ො𝑖
• Update weights:
• 𝑤𝑗𝑛𝑒𝑤 = 𝑤𝑗𝑜𝑙𝑑 + 𝜂 𝑒𝑖 𝜙𝑗 𝑥𝑖
• Stop when error is minimum or maximum epochs reached

30
 K-MEANS CLUSTERING

In designing the RBF network of Fig. 5.4, a key issue that needs to be addressed is how to
compute the parameters of the Gaussian units that constitute the hidden layer by using unlabeled
data.

In other words, the computation is to be performed in an unsupervised manner. In this section, we

describe a solution to this problem that is rooted in clustering, by which we mean the following:

Clustering is a form of unsupervised learning whereby a set of observations (i.e., data points)
is partitioned into natural groupings or clusters of patterns in such a way that the measure of
similarity between any pair of observations assigned to each cluster minimizes a specified cost
function.

31
K-MEANS CLUSTERING

32
 K-MEANS CLUSTERING

To do this encoding, we need a measure of similarity between every pair of vectors xi and ,
which is denoted by d(xi, ).When the measure d(xi, ) is small enough, both xi and are assigned to
the same cluster; otherwise, they are assigned to different clusters.

33
K-MEANS CLUSTERING

Set of K clusters

34
K-MEANS CLUSTERING

35
K-MEANS CLUSTERING

Clustering problem as follows:

Given a set of N observations, find the encoder C that assigns these observations to the K
clusters in such a way that, within each cluster, the average measure of dissimilarity of the
assigned observations from the cluster mean is minimized.

36
K-MEANS CLUSTERING

With encoder C being unknown, how do we minimize the cost function J(C)? To
address this key question, we use an iterative descent algorithm, each iteration of
which involves a two-step optimization.

37
K-MEANS CLUSTERING

38
 K-MEANS CLUSTERING

of Cover’s theorem—that is, that the dimensionality of the hidden layer is high enough.

K-means algorithm is indeed computationally powerful enough to transform a set of

nonlinearly separable patterns into separable ones in accordance with this theorem.
39
K-MEANS CLUSTERING

Reference: Internet: [Link]

40
K-MEANS CLUSTERING

Reference: Internet: [Link] 41

K-MEANS CLUSTERING

Reference: Internet: [Link]

42
K-MEANS CLUSTERING

Calculate new centroids

Reference: Internet: [Link]

43
K-MEANS CLUSTERING

First cluster has one data point . Hence centroid remains same

Second cluster has 5 datapoints.

A1: (2,20)
B1:
(8+5+7+6+4=30/5=6
(4+8+5+4+9=30/5=6)

Reference: Internet: [Link]

44
K-MEANS CLUSTERING

Reference: Internet: [Link]

45
K-MEANS CLUSTERING

Reference: Internet: [Link]

46
K-MEANS CLUSTERING

C2 has changed from cluster 2 to 1. Hence not converged.

Calculate the new centroid.

Reference: Internet: [Link]
47
K-MEANS CLUSTERING

B1 has changed from cluster 2 to 1. Hence not converged.

Calculate the new centroid.

Reference: Internet: [Link]
48
K-MEANS CLUSTERING

No change. Hence converged.

Reference: Internet: [Link]

49
 RECURSIVE LEAST-SQUARES ESTIMATION OF THE WEIGHT VECTOR

R(n)-> Correlation matrix

W(n)->Weight vector
r(n)-> Desired response

The Least Square method is a mathematical technique that minimizes the sum of squared differences between
observed and predicted values 50
 RECURSIVE LEAST-SQUARES ESTIMATION OF THE WEIGHT VECTOR

Solve 5.30 to find

w(n)->Weight vector

resulting algorithm is called the recursive least-squares (RLS) algorithm.

51
 RECURSIVE LEAST-SQUARES ESTIMATION OF THE WEIGHT VECTOR

The RLS algorithm

Consider the correlation vector

52
 RECURSIVE LEAST-SQUARES ESTIMATION OF THE WEIGHT VECTOR

The RLS algorithm

53
RECURSIVE LEAST-SQUARES ESTIMATION OF THE WEIGHT VECTOR

54
RECURSIVE LEAST-SQUARES ESTIMATION OF THE WEIGHT VECTOR

g(n) is called the gain vector of the RLS algorithm

prior estimation error (n)

55
Hybrid Learning Procedure for RBF Networks

The K-means algorithm for training the hidden layer is applied first; it is then followed by the RLS
algorithm for training the output layer. Hereafter, we refer to this hybrid learning procedure as the
“Kmeans, RLS” algorithm, aimed at training an RBF network with the following composition:

56
Hybrid Learning Procedure for RBF Networks

57
Hybrid Learning Procedure for RBF Networks

An attractive feature of the “K-means, RLS” algorithm is its computational efficiency, which
follows from the fact that the K-means and RLS algorithms are both computationally efficient in
their own individual ways. The only questionable feature of the algorithm is the absence of an
overall optimality criterion that combines the training of the hidden and output layers, assuring
the whole system of optimality in some statistical sense. 58
 Self-Organizing Map

In unsupervised learning, the requirement is to discover significant patterns, or features, of the

input data through the use of unlabeled examples. That it to say, the network operates in accordance
with the rule:
Learn from examples without a teacher.

59
SELF-ORGANIZING MAP (Kohonen Self-
Organizing Feature Map)
• In many real-world problems, training data is available without target
outputs. In such cases, supervised neural networks cannot be applied
directly. To handle this situation, unsupervised neural networks are used.
• A Self-Organizing Map (SOM) is a powerful unsupervised learning neural
network proposed by Teuvo Kohonen. It performs clustering, pattern
discovery, and data visualization by mapping high-dimensional input data
onto a low-dimensional (usually two-dimensional) grid, while preserving
the topological structure of the input data.

60
• The central idea of SOM is:
• Similar input patterns should activate neurons that are
physically close to each other in the output map.
• Thus:
• Inputs that are similar → mapped to nearby neurons
• Inputs that are dissimilar → mapped to farther neurons
• This property is called topology preservation.

61
Why SOM is Called “Self-Organizing?
• SOM is called self-organizing because:
• There is no teacher
• No target output is provided
• The network automatically organizes itself
• Neurons compete and cooperate during learning
• The structure of the map emerges automatically from the data.

62
Architecture of SOM
• SOM consists of two layers:
• 1. Input Layer
• Contains m neurons
• Each neuron represents one input feature
• No computation is done here
• Simply distributes input values
• 2. Output Layer (Competitive Layer)
• Neurons arranged in a 1-D or 2-D lattice
• Each neuron has a weight vector of dimension m
• Neurons are connected through a neighborhood relationship
SOM has no hidden layers.

63
Learning Mechanism in SOM
Learning in SOM occurs in two stages:
• Competition
• Cooperation
• Both are essential.
Competition (Winner Selection)
• When an input vector 𝑥is presented:
• All output neurons compete
• The neuron whose weight vector is closest to the input wins
• The winning neuron is called the:
• Best Matching Unit (BMU)
• The winner is selected using the minimum distance criterion:
• 𝑖 𝑥 = arg min ∥ 𝑥 − 𝑤𝑗 ∥
𝑗
• Usually, Euclidean distance is used.

64
Neighborhood Concept

• After the winner is found, neighboring neurons are also allowed

to learn.
• Important points:
• Neighborhood is defined based on map topology
• NOT based on weight distance
• Neurons closer to the winner learn more
• This process ensures smooth mapping and topology
preservation.

65
 Neighborhood Functions
• (a) Hard Neighborhood (b) Gaussian Neighborhood Function
2
Function 𝑑𝑗,𝑖
ℎ𝑗,𝑖 = exp − 2
1, 𝑑𝑗,𝑖 ≤ 𝑟 2𝜎
• ℎ𝑗,𝑖 = ቊ Topological Distance (Map Space) – dj,i
0, otherwise
All neurons are updated
• Only winner and its Update amount decreases with distance
neighbors update Produces smooth learning
• Sharp boundary Used in practical SOM implementations
Why all neurons update in Gaussian SOM?
Because the exponential function never
becomes zero, only very small.

66
Learning Rate (η)

• The learning rate controls:

• Magnitude of weight change
• Speed of learning
• Behavior:
• Initially large → fast learning
• Gradually decreases → stable convergence
• A common decay rule is:
• 𝜂 𝑛 = 𝜂0 𝑒 −𝑛/𝑇

67
• Weight Update Rule (General SOM Equation)
𝑤𝑗 𝑛 + 1 = 𝑤𝑗 𝑛 + 𝜂 𝑛 ℎ𝑗,𝑖 𝑛 𝑥 𝑛 − 𝑤𝑗 𝑛
• Where:
𝜂 𝑛 =learning rate
• ℎ𝑗,𝑖 𝑛 =neighborhood function
• 𝑥 𝑛 =input vector

68
 SELF-ORGANIZING MAP

There are three basic steps involved in the application of the algorithm after initialization:
sampling, similarity matching, and [Link] three steps are repeated until formation of the feature
map has been [Link] algorithm is summarized as follows:

69
SELF-ORGANIZING MAP

70
 Exercise 1: SOM using Hard Neighborhood Function
Consider the unsupervised learning network (Self-
Organizing Map) shown in the figure above.
The network consists of two input neurons 𝑈1 and 𝑈2and five
output (competitive) neurons 𝐶1 , 𝐶2 , 𝐶3 , 𝐶4 ,and 𝐶5.
The input vector applied to the network is:
𝑥 = 0.3 0.4
Assume:
Learning rate 𝜂 = 0.3
Output neurons are arranged in a 1-D linear topology
Hard neighbourhood function is used
Neighbourhood radius 𝑟 = 1
Tasks:
Compute the Euclidean distance between the input vector
and each output neuron.
Identify the winning neuron (Best Matching Unit).
Identify the neighbouring neurons based on the given radius.
Update the weights of the winning neuron and its neighbours
using the SOM learning rule.
Tabulate the updated weight vectors.
71
 SOM using Gaussian Neighbourhood Function
• Consider the same Self-Organizing Map shown in the figure above with the same
initial weights and input vector:
𝑥 = 0.3 0.4
• Learning rate 𝜂 = 0.3
• Neurons are arranged in a 1-D linear topology
• Gaussian neighbourhood function is used
• Neighbourhood width 𝜎 = 1
• The Gaussian neighbourhood function is defined as:
2
𝑑𝑗,𝑖
ℎ𝑗,𝑖 = exp − 2
2𝜎
• here 𝑑𝑗,𝑖 is the topological distance between neuron 𝑗and the winning neuron 𝑖.
Tasks:
• Determine the winning neuron using the Euclidean distance criterion.
• Compute the Gaussian neighbourhood function values for all output neurons.
• Update the weights of all output neurons using the SOM learning rule.
• Compare the weight updates with those obtained using the hard neighbourhood
function.
• Explain why distant neurons undergo smaller weight changes in the Gaussian 72
neighbourhood case.
PROPERTIES OF THE FEATURE MAP

73
PROPERTIES OF THE FEATURE MAP

74
PROPERTIES OF THE FEATURE MAP

75
PROPERTIES OF THE FEATURE MAP

76
PROPERTIES OF THE FEATURE MAP

77
PROPERTIES OF THE FEATURE MAP

78
PROPERTIES OF THE FEATURE MAP

79
PROPERTIES OF THE FEATURE MAP

•Density matching means the SOM allocates more neurons to regions of the input space where data
occurs frequently
•Regions with few data samples are represented by fewer neurons

How SOM Achieves Density Matching

Frequently occurring input patterns:
Win more often during training
Pull nearby neurons towards them
As a result:
More weight vectors cluster in dense input regions
Sparse regions attract fewer neurons

80
PROPERTIES OF THE FEATURE MAP

81
PROPERTIES OF THE FEATURE MAP

82
CASE STUDIES- REFER JOURNALS

83