Fully Connected Neural Networks

Ahmad Kalhor-University of Tehran

1

Chapter 2

(Each neuron is connected to all neurons of the next layer)

1.1.1 Fully Connected layers� Ideal to make partitions, maps and encoded/decoded data from a set of distinct inputs.

• one Layer Neural Networks (Perceptron –Adaline -Madaline)
• MLP With one Hidden Layer
• MLP With Two Hidden Layers
• Multilayer Neural Networks
• Auto Encoders
• Restricted Boltzmann Machine
• Deep Belief Neural Networks

​

Ahmad Kalhor-University of Tehran

One-Layer Neural Networks

Ahmad Kalhor-University of Tehran

3

Chapter 2 – part 1

One-layer NNs for classification

Ahmad Kalhor-University of Tehran

4

A simple one-layer network with a M&P neuron

​

One can replace the threshold of the M&P neuron with “0” by adding as an extra input (bias term) as follows:

​

1

Remark

Because of simple structure of one-layer NNs, Such networks only include partitioning layers .

Potential of one-layer NNs in classification

Each M&P neuron can partition the feature space into two regions through using an (n-1) dimensional hyper-plane in the input space.

Example: (n=2) net=w₁x₁+w₂x₂+b b<0,w₁>0_,w₂>0

Ahmad Kalhor-University of Tehran

5

+

-

-

More simple Examples (feature points are separated by a line)

Ahmad Kalhor-University of Tehran

6

AND Logic

OR logic

net=x₁+x₂-1

net=x₁+x₂+1

h=sign(net)

1. The separating line between feature points of two classes is determined in a learning process.
2. It is desired that the determined separating line makes enough big margins by boundary feature points of both classes.

Using one-layer NNs to classify more than two classes

Ahmad Kalhor-University of Tehran

7

For classifying two different classes, which are linearly separable, one M&P neuron is enough.

Assuming m (m >2) classes can be separated linearly through a simple one-layer NN, we want to classify each class with other ones by an independent output(one-hot outputs):

1- Exactly, m M&P neurons are required for classification purpose.

2- Each M&P neuron will separate a certain class from other ones by forming a hyper-plane in feature space.

3- By using such hyper planes, a convex hyper-polygon is appeared .

Example:

w₂₁

w₂₂

b₂

h₂

h₃

w₃₁

w₃₂

b₃

net₁=0

net₂=0

net₃=0

Linear Perceptron Network

Ahmad Kalhor-University of Tehran

8

Chapter 2 – part 1

Linear Perceptron Network (Rosenblatt,1958,59, 62)

Ahmad Kalhor-University of Tehran

9

Learning rules for Perceptron Network

1- Updating rule for the weights:

​

​

where x_i denotes ith input and t denotes the target value for output

2-Updating rule for the bias:

​

• One can show that the above updating rules change the weights and the bias term based on negative-gradient of squared error (loss function).

sign(wi⁺-wi^-)=-sign(gradient of squared error with respect to w)

sign(b⁺-b^-)=-sign(gradient of squared error with respect to b)

Ahmad Kalhor-University of Tehran

10

Learning Algorithm for Perceptron Network

Step 0- initialize the weights, the bias term, the learning rate and the threshold

​

Step 1- for each (input , target) training set, {(s,t)}, do steps 2, 3 and 4.

Step 2- Assign

Step 3- Compute the output vector, h, according to equation (#)

Step 4- if the error, (h-t), is not zero update the weights and the bias term according to equations (*),(**)

Step 5- if the computed error terms for all training pairs (s, t) are zero go to “End” else go to Step1.

Step 6- End.

​

​

Ahmad Kalhor-University of Tehran

11

Some examples

1- Classification of “And logic ” (with bipolar inputs and output) by Linear Perceptron Network

​

​

​

Ahmad Kalhor-University of Tehran

12

A

B

C

x1

x2

n=2

2- Classification of “And logic” (with binary inputs and bipolar output) by Linear Perceptron Network

​

Ahmad Kalhor-University of Tehran

13

A

C

x2

x1

n=2

3- Parity bit

​

Ahmad Kalhor-University of Tehran

14

w3

x3

If all bits are “1” then t=1 else t=-1

n=3

4- Classifying letters A,B,C,D,E,J and K

- Each Letter has three different fonts and totally 21 patterns are defined.�it is desired that each letter with its three patterns being classified.

Each letter is shown through a 9*7 dimensional dot matrix.

​

Example: Letter B

Ahmad Kalhor-University of Tehran

15

# is represented by 1

0 is represented by -1

9 rows (each one includes 7 pixels) make a vector with 63 elements

S_B=[1 1 1 1 1 1 0,………, 1 1 1 1 1 1 0]

n=63

Ahmad Kalhor-University of Tehran

16

Ahmad Kalhor-University of Tehran

17

After training phase, each output neuron separates patterns of a certain class with patterns of other classes.

1. it is concluded that the patterns of each class and other 6 classes can be separated, linearly.
2. 7 determined hyper planes form a convex hyper-polygon in input space.

Ahmad Kalhor-University of Tehran

18

Suppose that all 21 patterns become disturbed with noise: some of pixels #(0) are randomly replaced with 0(#) or become off (up to 30%).

The former trained perceptron Network is applied to classify such disturbed letters. The following table presents the results:

As it is understood the disturbed patterns of different classes can not be separated linearly.

Perceptron Learning Rule Convergence Theorem

Ahmad Kalhor-University of Tehran

19

Theorem:

If there is a weight vector W* such that f(x(p).W*)=t(p) for all P. then for any starting vector w, the perceptron learning rule will converge to a weight vector (not necessarily unique and not necessarily w*) that gives the correct response for all training patterns, and it will do so in a finite number of steps.

Problem

The perceptron learning rule is as follows:

Given a finite set of P input training vectors

x(p) p=1,…,P

Each with an associated target value

t(p), p=1,…..,P

Which is either +1 or -1, and an activation function h=f(net), where

​

​

​

The weights are updated as follows

If (h-t) is not zero then

w(new)=w(old)+tx

Else

No change in the weights

Proof is given in the book�

Ahmad Kalhor-University of Tehran

20

An upper bound for number of iterations in convergence is resulted as follows:

Considering some assumptions it can be concluded that:

1- M addresses a variant of within distance among patterns of each class(WD).

2- m addresses a variant between distance among patterns of two classes(BD)

if in an distribution, all patterns of a class make small WD and patterns of two classes make big BD, the upper bound will be decreased and the convergence may be occurred through less iterations.

Example

Ahmad Kalhor-University of Tehran

21

m=Min(W*x)

M=Max(||x||²)

||W*||=1

Since m₁<<m₂

​

it is expected that K₁>>k₂

K₁ : An upper bound for the number of updating rules required to find the separation line

K₂ : An upper bound for the number of updating rules required to find the separation line

Adaptive Linear Unit (AdaLine)

Ahmad Kalhor-University of Tehran

22

Chapter 2 – part 1

Ahmad Kalhor-University of Tehran

23

AdaLine is a type of one-layer network

The architecture of AdaLine and Perceptron networks are similar but they use different learning rules for the weights and the bias.

• Here, the activation function does not have threshold.

​

​

(1)

Adaptive Linear Unit (AdaLine) (widrow & Hoff 1960)

Learning rules in Adaline

For each training data set (s,t), the updating rules for weights and bias are defined as follows:

​

​

​

​

​

Delta’s leaning rules are defined based on LMS (Least Mean Squares).

error=t-net

Ahmad Kalhor-University of Tehran

24

(2)

Delta is the name of learning rules utilized in AdaLine

Learning Algorithm for AdaLine

Step 0- initialize the weights, the bias term (small random values) and choose a small value for learning rate.

Step 1- for each (input , target) training set, {(s,t)} ,do steps 2, 3 and 4

Step 2- Assign

Step 3- Compute sum of weighted inputs “net” according to equation (1)

Step 4- Update the weights and the bias term according to equations (2).

Step 5- if the computed cost function for all training pairs (s,t) becomes less than a threshold go to “End” and else go to Step1.

Step 6- End

​

​

Ahmad Kalhor-University of Tehran

25

Example

1- Classification of “And logic ” (with bipolar input and output) by AdaLin.

​

​

Ahmad Kalhor-University of Tehran

26

x1

x2

n=2

Final optimized line: net= 2/3 x1 + x2 - 4/3

Delta works based on the Gradient Descent method

Ahmad Kalhor-University of Tehran

27

Cost Function: Square Error between the target and net

Delta updates the weights and the bias of the AdaLine based on the (first order) Gradient Descent method.

Gradient Descent method (First order Gradient)

• Assume J(p) is the loss function of our learning problem in ANN.
• p denotes the vector of all tunable parameters (All weights and bias terms) and It is aimed to minimize J by optimizing p.

​

• Assuming J(p) is a smooth function of p around p:=p₀ , the Taylor expansion of J(p) is defined around p:=p₀ as follows:

​

​

​

Ahmad Kalhor-University of Tehran

28

• Assuming that First order gradient is not zero, one can say that for a small enough variation of p we have:

​

• Defining , and considering as a small enough positive coefficient, we have:

​

​

As a result, while first order gradient is not zero, the loss function will be decreased.

Repeating the above rule, the loss function decreasing is continued until p converges to a local optimal point like p1 . if p1 is equal to p* (the absolute optimal point) the loss function has met his absolute minimum point otherwise a sub-optimal answer in minimizing the function has been resulted.

​

​

Ahmad Kalhor-University of Tehran

29

Local Optimal

P*(optimal point)

P₀ (initial point)

P₁

Delta Convergence Property

Since the error is defined as difference of the target and net (not difference of target and output), the net (not necessarily the output of network) becomes near to the target.

If distribution of patterns in two classes is near together in shape and population, the “Delta” will learn a robust separation hyper-plane among patterns of two classes (Figure a), otherwise, there will no guarantee for true separation (Figure b).

​

Ahmad Kalhor-University of Tehran

30

(a)

(b)

A solution

Replace the “sign” function with a “soft sign” such as “tanh”. Unlike “sign”, “tanh” is smooth and one can compute the new updating rules by gradient descent.

​

​

​

​

�

if is chosen so big then “tanh” will be near to a “sign” function. Now, by decreasing the loss function, the output of network will converge to the target value (as it was done in perception network).

​

Ahmad Kalhor-University of Tehran

31

Using the aforementioned solution

Ahmad Kalhor-University of Tehran

32

1. By applying the aforementioned solution, independent from the shape and populations of patterns, the partitioning line will be converged between patterns of two classes with a large enough margins.
2. This modified version of Delta learning rule has superiority to the perception network which was stopped by finding every partitioning line.

Multi AdaLine (MAdaLine)

Ahmad Kalhor-University of Tehran

33

Chapter 2 – part 1

MAdaLine is made from some AdaLines which are combinated by an “OR” or “AND” M&P neuron.

MAdaLine has the required potential to separate a set of patterns (with a unique label) surrounded by a convex hyper-polygon

Ahmad Kalhor-University of Tehran

34

Multi AdaLine (MAdaLine)

AdaLines

1

AND

Example

Learning the required number of Adalines and their weights, to make an appropriate convex hyper polygon, is not straightforward

1

XOR Example (Widrow & Hoff 1960)

1- Classification of “Xor” logic by MAdaLine

​

​

​

Ahmad Kalhor-University of Tehran

35

x1

n=2

1

OR

A

B

1

Two Algorithms:

MRI: The output neuron is adjusted as an “OR” logic and only the weights and biases of hidden neurons are trained.

MRII: All the weights and biases of hidden and output layers are trained.

Two above algorithms have been explained in the book.

0.5

0.5

0.5

-1

1

-1

-1

1

-1

x2-x1-1=0

x1-x2-1=0

MAdaLine can separate more that one set of patterns surrounded by convex-hyper polygons.

Ahmad Kalhor-University of Tehran

36

AdaLines

1

AND

Example

1

1

1

AND

6

7

2

2

2

2

2

1

1

1

1

2

3

3

3

3

3

3

3

3

3

3

3

3

3

3

3

An illustrative example

Some hidden neurons with near hyper-plans can be merged and the redundancy is decreased.

Disabilities of MAdaLine

1. There is no systematic/straightforward optimization method to update the weights in MAdaLine. Also, MAdaLine can not make analogue outputs for regression Problems.
2. MAdaLine does not work in following cases:

-The patterns of a certain class are divided to more than one convex hyper-polygon shape cluster.

-The patterns of a certain class have a non-convex hyper-polygon shape cluster.

​

​

​

3. Redundancies including correlations and disturbances can not be removed/Filtered by MAdaLine networks.

​

​

​

Ahmad Kalhor-University of Tehran

37

Solutions for aforementioned problems

1- Using gradient search methods 🡪 Multi Layer Percepetron with one hidden layer

(1):Systematic optimization method /Convex shape partitioning/ Mapping

2-Considering two hidden layers in the network 🡪 Multi Layer Percepetron with two hidden layers

(1)+(2):Non-Convex shape partitioning/ Mapping

3-1. Using Encoding Part (auto-encoder/stacked RBMs) with two hidden layers 🡪 Multi Layer Neural Networks

(1)+(2)+(3):Dimensionality Reduction

3-2. Using some Filters and scaling layers 🡪 Convolutional Neural Network

(1)+(2)+(3)+(4):disturbance Filtering

​

​

​

​

​

​

​

​

​

​

​

Ahmad Kalhor-University of Tehran

38

Multi Layer Perceptron with one hidden layer (Rumelhart 1986)

Ahmad Kalhor-University of Tehran

39

Multi-Layer Perceptron (MLP)

with one hidden layer

Ahmad Kalhor-University of Tehran

40

Chapter 2 – part 1

Learning Process of MLP with one hidden layer�Error Back Propagation (BP)

Training Set:

(W, b) are tuned in order to

Loss Function(SSE):

Updating Rules for sample “q” and after “call” stage and assuming the output is scalar (from the “output-layer” in a back-ward manner to the “first-layer”):

Ahmad Kalhor-University of Tehran

41

Learning Algorithm for MLP

0- Scale every input between “0 up to 1” or “-1 up to 1” (to get better results in learning) .

1- Initialize the weights and biases as small random real values. Consider a small learning rate to guarantee a successful local search and then set epoch=0.

2- Apply input(s) of training set to the Network in one of following methods.

2-1 Batch based : All data pints are applied, simultaneously .

2-2 Stochastic based: Data are shuffled and then data points are applied one by one.

2-3 Stochastic mini batch based: training data set are randomly divided to a certain number of subsets (min-batches); then at each time a min-batch is chosen and applied.

3- According to the considered method(2-1, 2-2 or 2-3), compute the outputs of the network, the error and the loss function(Call stage)

4- According to the considered method(2-1, 2-2 or 2-3), use the updating rules for the weights and biases (ReCall stage)

5- If the method 2-2 or 2-3 has been chosen, repeat steps 3 and 4 until all training data points or min-batches are applied, completely.

6- if the loss function is decreased continually for both training and validation sets, let epoch:=epoch+1 and return to 2, else go to the next step.

7- The algorithm is terminated. To check the generalization of the network it is evaluated by the considered validation dataset.

Ahmad Kalhor-University of Tehran

42

Some Important Notes

Ahmad Kalhor-University of Tehran

43

1. How many neurons should be defined in the hidden layer ?�It depends on the required complexity in partitioning (for classification) or mapping(for regression). It is suggested that the appropriate number of neurons optimized from low to up

​

2. To avoid diverging the weights to infinity, which is an invalid learning causing over-fitness, it is suggested to add a regularization term in loss function. (λ≥0 :regulation weight)

​

3. The stop condition become satisfied when the computed loss function of the validation set does not decrease any more.

Although decreasing rate of loss function for training set is important, to avoid over fitness, the decreasing rate of loss function for validation set should be considered for stop condition.

A Simple Example of Call and Recall in an MLP with one hidden layer

Ahmad Kalhor-University of Tehran

44

Call

ReCall

​

*Loss function is decreased

Derivative Chain Rule

Ahmad Kalhor-University of Tehran

45

​

​

​

​

Some notes

1. The gradient rules for any parameter can be computed independently
2. Since some parts of updating rules for parameters in further layers can be saved in backward layers too, in order to reduce the computation load, it is suggested to compute gradients of parameters from further layers to first layers.

3. Since the derivative of sigmoid function is less than one, one can say the norm of gradients for first layers is reduced significantly (gradient vanishing).

illustrative Example1: Function Approximation

Function Sinc(x)=sin(x)/x

• Dimension: n=1 input /m=100 hidden neurons / r=1 output
• Training Set: 140 pairs /Validation Set: 60 pair
• BP strategy: Stochastic point based/ number of epochs=1000
• Loss Function: Root Mean Square Error (RMSE)/ learning rate:

​

Ahmad Kalhor-University of Tehran

46

Illustrative Example2: Classification(Convex Shape)

Ahmad Kalhor-University of Tehran

47

N. of Neurons in Layer1=4

Learning rate=0.001

Learning Method: Batch-Based BP

N. of Training samples=100

N. of validation samples=400

Training set

After Training

Illustrative Example3: Classification (Non-convex Shape)

Ahmad Kalhor-University of Tehran

48

Target Partitions(top view)

N. of Neurons in Layer1=10

Learning rate=0.005

N. of training set=100 samples

N. of validation set=400 samples

Learning set: Batch-Based BP

Training set

Trained Partitions(top view)

After Training

Potential of MLP with one hidden layer in Function Approximation

1. MLP with one hidden layer is a general function approximator

It was proved that: a MLP NN with one hidden layer containing a finite number of neurons can approximate any continuous functions on compact subsets of Rn, Cybenko, 1989. It does not touch upon the algorithmic learnability of those parameters.

2. Though it was mentioned that MAdaLine can not model the family of non-convex functions, due to using softness of tanh() and using not quantized weights in output layer, non-convex regions(maps) can be modeled by MLP with one hidden layer.

3. In such cases, the required redundancy in using hidden neurons is high and hence over fitness will be occurred and the generalization of the network particularly for uncompact subsets (unbounded maps or partitions) is not guaranteed.

​

​

Ahmad Kalhor-University of Tehran

49

Multi-Layer Perceptron (MLP)

with two hidden layers

Ahmad Kalhor-University of Tehran

50

Chapter 2 – part 1

Multi Layer Perceptron with two hidden layers

Ahmad Kalhor-University of Tehran

51

Learning Process of MLP with two hidden layers�Error Back Propagation (BP)

Training Set:

(W, b) is optimized in order to

Loss Function(SSE):

• Updating Rules (from output-layer back-ward to first-layer):

Using error back-propagation, all weight matrices as well as bias vectors should be updated.

Ahmad Kalhor-University of Tehran

52

Potential of the MLP with two hidden layers

1- Partitioning (Classification)

• Considering that the input space is the same feature space, a MLP Network with two hidden layers has the required potential in (reliable) classification of any number of classes with any shape and with any accuracy.

Reliable classification means:(1) the redundancy in number of the required neurons is low (2), the robustness against input uncertainties is high and (3) the generalization for un-compact subsets is high.

• However, it is not known that how many neurons in the hidden layers are required. Also, the weight matrices or bias vectors are not determined for such purposes.

​

Ahmad Kalhor-University of Tehran

53

An Illustrative Example:

Potential of the MLP with two hidden layers

2- Mapping(Regression)

• An MLP with two hidden layers can be used to build any map with any required accuracy .
• Since a Regression problem can be approximated by a classification problem, By increasing the number of classes, an arbitrary smooth map can be approximated and hence any map can be build by any required accuracy.
• However, it is not actually known that how many neurons (in hidden layers ) are required ;also, the weight matrices or bias vectors are not known for such purposes.

​

Ahmad Kalhor-University of Tehran

54

Illustrative Example1: Function Approximation

Function : Sinc(x)=sin(x)/x

• Dimension: n=1 inputs /m1=5 first hidden neurons / m2=5 second hidden neurons / r=1 output
• Training Set/BP strategy/Loss Function/ learning rate (The same used in MLP with one hidden layer)

​

Ahmad Kalhor-University of Tehran

55

Comparison with MLP including one hidden-layer

1. Less number of parameters 2.better accuracy 3.better validation

Illustrative Example2: Classification

Ahmad Kalhor-University of Tehran

56

Target Partitions(top view)

Trained Partitions(top view)

After Training

N. of Neurons in Layer1=2

N. of Neurons in Layer2=2

Learning rate=0.005

N. of training set=100 samples

N. of validation set=400 samples

Learning set: Batch-Based BP

Multi Layer Neural Networks (MLNNs)

Ahmad Kalhor-University of Tehran

57

Chapter 2 – part 1

Multi Layer Neural Networks (MLNNs) �(http://ufldl.stanford.edu/tutorial/supervised/MultiLayerNeuralNetworks/)

• MLNN is a feed-forward network including arbitrary number of (fully-connected or partially connected) layers, in which, each layer contains an arbitrary number of neurons.
• MLNNs with more than one hidden layer can be considered as Deep NNs.
• Applying extra layers allows Feature Extraction: (1) Data dimension-reduction, and (2) Data Filtering and scaling.
• Some known architectures of MLNNs are Auto-encodes, Deep-Belief Neural Networks and Convolutional Neural Networks, which will be introduced and explained later.
• At first, the (supervised) learning algorithm is explained.

Ahmad Kalhor-University of Tehran

58

​

)}

)}

A Simple Example (to introduce the notation)

Ahmad Kalhor-University of Tehran

59

MLNN Learning Algorithm

Ahmad Kalhor-University of Tehran

60

Back propagation Algorithm in Detail

Ahmad Kalhor-University of Tehran

61

The BP algorithm by matrix-vector notation

Ahmad Kalhor-University of Tehran

62

”∙*∙” to denote the element-wise product operator 

For sigmoid function:

Full Gradient Descent Algorithm

Ahmad Kalhor-University of Tehran

63

*Former Introduced MLP with one or two hidden layers can be considered as MLNN with three or four layers.

Dimensionality Reduction in MLNNs

Ahmad Kalhor-University of Tehran

64

Chapter 2 – part 1

Dimensionality Reduction in MLNNs

• In many real-world high dimensional patterns there are correlations among dimensions.
• Existing correlations among inputs avoids reliable and generalized partitioning and mapping in classification and regression problems.
• It is desired that by removing correlations, the input data vector(matrix) is transformed to a space with lower dimension.

​

​

• Since only correlations are removed, no valuable information is reduced, and the new space(with lower dimension) is enough to retrieve the initial input data.

​

​

​

• Some initial layers of a MLNN can be employed for Dimensionality Reduction purposes.

Ahmad Kalhor-University of Tehran

65

Important Notes

1. If there are linear or nonlinear correlations among input dimensions, by removing correlations one can will get a new feature space (with lower dimensions), in which features are independent.

​

• It is possible to retrieve original input-data by using inverse of the transformation.
• In geometric view: if (n-dimensional) input data points are distributed on a (m-dimensional) hyper-surface where m<n, there will be (n-m) independent correlations among dimensions.

​

• By Removing correlations among input dimensions, nullity spaces of the input data will be removed and the variance of the feature space will be maximized.

​

Ahmad Kalhor-University of Tehran

66

Illustrative Examples

Ahmad Kalhor-University of Tehran

67

Removing Linear Correlations by PCA

Assume x denotes an n-dimensional point of the input space: x^T=[1,x₁,x₂,..,x_n] (bias has been augmented)

There will be a linear correlation among different input dimensions, if for all samples of x there is a non-zero real scalars(the normal vector), a^T=[a₀,a₁,..,a_n] , in order that:

One can show for r independent linear correlations, “r” Eigen values of the “Auto Correlation Matrix” (R) are zero and their corresponding Eigen vectors reveal “r” independent linear correlations.

​

​

​

​

Ahmad Kalhor-University of Tehran

68

Dimensionality Reduction and Data Retrieving for Linear Correlations

Ahmad Kalhor-University of Tehran

69

Nonlinear Correlation Removing

• Nonlinear PCA
• Kernel PCA
1. Linear Discriminant Analysis(LDA)
• Multidimensional Scaling (MDS)
•  Isomap
• Locally Linear Embedding (LLE)
•  Laplacian Eigen map
• Local Tangent
• Space Alignment (LTSA)
• Fast map

​

​

Ahmad Kalhor-University of Tehran

70

Two Valuable Notes

1. If data points, which are belonged to a limited patch of the input space, are collected, using simple PCA one will find the dimension of the nullity space.

​

​

​

​

​

• A MLNN with suitable number of layers and neurons can be used to approximate the nonlinear transformation required to remove the nonlinear correlations and dimensionality reduction.

​

​

​

​

​

​

​

Ahmad Kalhor-University of Tehran

71

Patch with limited size

Locally Linear PCA

V(x)=[V₁(x),V₂(x)]

r=dim(V₁(x))

Auto-Encoders

Ahmad Kalhor-University of Tehran

72

Chapter 2 – part 1

Auto-Encoders (Liou and  Huang 2008)

Ahmad Kalhor-University of Tehran

73

Using ANN to Dimension Reduction

Auto-Encoder

1. Auto-Encoders are a variant of MLNNs which are trained in order to remove nonlinear correlations among dimensions of the input data space (Encoding part).
2. To reach the aim of Auto-Encoders in Encoding, an auxiliary supervised learning process is required. Actually Auto Encoders in second part (Decoding part) try to represent the initially taken patterns in the output layer.
3. Auto-Encoders can be learned by the algorithm explained for MLNN. Error Back propagation is utilized to update weights and biases.

An Auto-encoder

Some important notes about Auto-Encoders

1. One can say that AutoEncoders are a variant of “identity function” because:

​

​

• The maximum possible Dimensionality reduction of the input space is equal to the dimension of the nullity space (or the number of all independent correlations).
• It is tried to reach to minimum possible dimension of the data space (z) in Encoding part (First Part).
• To remove more complex nonlinear correlations, one should use more layers (depth) and neurons.
• It is not necessary that the number of neurons in Encoding part(Decoding Part) is decreased (increased) uniformly layer by layer. It is expected that at the end of the Encoding(Decoding) part the number of neurons has been recued (increased) in comparison to the initial dimension of the input data (the decreased dimension of the data).
• If the distribution of the input data is near to the white noise distribution, the nullity space and possible correlations will be vanished(there is no possibility in dimension reduction)
• The nullity space can also be interpreted as the space of disturbance patterns which have occupied the nullity space with rather low repetition or density (infrequent)

​

​

Ahmad Kalhor-University of Tehran

74

Restricted Boltzmann Machine (RBM)  

Ahmad Kalhor-University of Tehran

75

Chapter 2 – part 1

Restricted Boltzmann Machine(RBM)  Paul Smolensky in 1986

• An RBM is another example of neural network utilized in dimensionality reduction .
• It includes only two layers: visible layer and hidden layer.
• It is aimed that by using only one layer of neurons, correlations are partially removed from the input space, “x”, and the new space “a” is appeared in lower dimension (encoding part).
• For decoding part, RBM is used in inverse direction from hidden layer to visible layer.

Ahmad Kalhor-University of Tehran

76

RBM versus Auto-Encoders

• Unlike Auto-Encoder the decoding part is not independent from encoding part.
• In RBM decoding part is the same encoding part in which inputs and outputs are replaced with each others.

​

Ahmad Kalhor-University of Tehran

77

RBM as an Auto-encoder

Training of an RBM

• RBM similar to an Auto-Encoder is learned by trying to retrieve (reconstruct) the initially applied pattern (decoding part).

​

​

​

​

Ahmad Kalhor-University of Tehran

78

Optimization Problem:

2. Learning by Gibbs Sampling�

Ahmad Kalhor-University of Tehran

79

1. Learning by Gradient Search

​

​

​

​

​

​

1. since derivation of the “sigmoid” or “tanh” is a positive scalar (less than one), the sign of gradient is affected directly by the output error and weights.
2. The resulted positive scalar from the derivation can be ignored.

Cascaded RBMs

Ahmad Kalhor-University of Tehran

80

Method

1. Considering the given inputs, train the first RBM.
2. Consider the Hidden layer of the last trained RBM as new inputs.
3. Train a new RBM.
4. If the dimension of the hidden layer is less than the number of inputs, consider the trained RBM as an approved RBM and then return to step 2, else go to next step.
5. Stack RBMs from the first trained one until the last approved one.
6. End.

​

Using Auto-Encoders (or Cascaded RBMs) in Classification and Regression� Deep Belief Network (DBN)

1. Define and train (1) an Auto-Encoder or (2) a Cascaded RBM for dimensionality reduction of the input space
2. Consider the encoding part of the Auto-encoder (or integrated RBMs) as initial layers of a MLNN.
3. Add one or two more hidden fully connected layers to provide the required partitioning or mapping (respectively utilized in Classification or Regression problems)
4. Such NNs are a variant of Deep Learning Networks.
5. Hinton in 2009 introduced and named such networks as Deep Belief Network (DBN) .

Ahmad Kalhor-University of Tehran

81

From Auto-Encoders

(or Cascaded RBMs)

Regular Fully

Connected Layers

Some Important Notes about Deep Belief Network (DBN)

​

1. A DBN includes two parts: Encoding part and partitioning or mapping part.
2. The encoding part is trained through an auto-encoder(or cascaded RBMs) without using the target outputs (unsupervised).
3. However, The second part is trained by target outputs (supervised).
4. One can tune all parameters of the DBN by error back propagation (Fine Tuning).

Ahmad Kalhor-University of Tehran

82

How many hidden layers are required in DBN (at least)?

• For Encoding part, since it is aimed to learn the transformation function for Dimensionality Reduction, (in the worse case) three layers including two hidden layers and the output layer are required.
• It was discussed that for partitioning or mapping cases (in the worse case), two hidden layers are enough.
• Hence, a MLNN with 5 hidden layers is good enough for Dimensionality Reduction (at first part) and partitioning or mapping problems (at second part).

Ahmad Kalhor-University of Tehran

83

Transformation map

Partitioning/Mapping

An illustrative Example

Ahmad Kalhor-University of Tehran

84

h(z₁,z₂)

End of Chapter2

​

​

Thank you

Ahmad Kalhor- University of Tehran

85