PV021: Neural networks
Tomáš Brázdil
1
Course organization
Course materials:
▶ Main: The lecture
▶ Neural Networks and Deep Learning by Michael Nielsen
http://neuralnetworksanddeeplearning.com/
(Extremely well-written online textbook (a little outdated))
▶ Deep Learning by Ian Goodfellow, Yoshua Bengio, and Aaron
Courville
http://www.deeplearningbook.org/
("Classical" overview of the theory of neural networks (a little outdated))
▶ Probabilistic Machine Learning: An Introduction by Kevin Murphy
https://probml.github.io/pml-book/book1.html
(Greatly advanced ML textbook with (almost) up-to-date basic neural
networks.)
▶ Infinitely many online tutorials on everything (to build intuition)
Suggested: deeplearning.ai courses by Andrew Ng
2
Course organization
Evaluation:
▶ Project (Dr. Tomáš Foltýnek)
▶ implementation of a selected model + analysis of given data
▶ implementation C/C++/Java/Rust without the use of any
specialized libraries for data analysis and machine
learning
▶ need to get over a given accuracy threshold (a gentle one,
just to eliminate non-functional implementations)
3
Course organization
Evaluation:
▶ Project (Dr. Tomáš Foltýnek)
▶ implementation of a selected model + analysis of given data
▶ implementation C/C++/Java/Rust without the use of any
specialized libraries for data analysis and machine
learning
▶ need to get over a given accuracy threshold (a gentle one,
just to eliminate non-functional implementations)
▶ Oral exam
▶ I may ask about anything from the lecture! You will get
a detailed manual specifying the mandatory knowledge.
3
FAQ
Q: Why can we not use specialized libraries in projects?
4
FAQ
Q: Why can we not use specialized libraries in projects?
A: In order to "touch" the low level implementation details of the
algorithms. You should not even use libraries for linear algebra
and numerical methods so that you will be confronted with
rounding errors and numerical instabilities.
4
FAQ
Q: Why can we not use specialized libraries in projects?
A: In order to "touch" the low level implementation details of the
algorithms. You should not even use libraries for linear algebra
and numerical methods so that you will be confronted with
rounding errors and numerical instabilities.
Q: Why should you attend this course when there are infinitely
many great reasources elsewhere?
A: There are at least two reasons:
▶ You may discuss issues with me, my colleagues and other
students.
▶ I will make you truly learn fundamentals by heart.
4
Notable features of the course
▶ Use of mathematical notation and reasoning (mandatory for
the exam)
▶ Sometimes goes deeper into statistical underpinnings of neural
networks learning
▶ The project demands a complete working solution which must
satisfy a prescribed performance specification
5
Notable features of the course
▶ Use of mathematical notation and reasoning (mandatory for
the exam)
▶ Sometimes goes deeper into statistical underpinnings of neural
networks learning
▶ The project demands a complete working solution which must
satisfy a prescribed performance specification
An unusual exam system! You can repeat the oral exam as many
times as needed (only the best grade goes into IS).
5
Notable features of the course
▶ Use of mathematical notation and reasoning (mandatory for
the exam)
▶ Sometimes goes deeper into statistical underpinnings of neural
networks learning
▶ The project demands a complete working solution which must
satisfy a prescribed performance specification
An unusual exam system! You can repeat the oral exam as many
times as needed (only the best grade goes into IS).
An example of an instruction email (from another course with the
same system):
It is typically not sufficient to devote a single
afternoon to the preparation for the exam.
You have to know _everything_ (which means every
single thing) starting with the slide 42
and ending with the slide 245 with notable exceptions
of slides: 121 - 123, 137 - 140, 165, 167.
Proofs presented on the whiteboard are also mandatory.
5
Machine learning in general
▶ Machine learning = construction of systems that learn their
functionality from data
(... and thus do not need to be programmed.)
6
Machine learning in general
▶ Machine learning = construction of systems that learn their
functionality from data
(... and thus do not need to be programmed.)
▶ spam filter
▶ learns to recognize spam from a database of "labeled"
emails
▶ consequently can distinguish spam from ham
6
Machine learning in general
▶ Machine learning = construction of systems that learn their
functionality from data
(... and thus do not need to be programmed.)
▶ spam filter
▶ learns to recognize spam from a database of "labeled"
emails
▶ consequently can distinguish spam from ham
▶ handwritten text reader
▶ learns from a database of handwritten
letters (or text) labeled by their correct
meaning
▶ consequently is able to recognize text
6
Machine learning in general
▶ Machine learning = construction of systems that learn their
functionality from data
(... and thus do not need to be programmed.)
▶ spam filter
▶ learns to recognize spam from a database of "labeled"
emails
▶ consequently can distinguish spam from ham
▶ handwritten text reader
▶ learns from a database of handwritten
letters (or text) labeled by their correct
meaning
▶ consequently is able to recognize text
▶ · · ·
▶ and lots of much, much more sophisticated applications ...
6
Machine learning in general
▶ Machine learning = construction of systems that learn their
functionality from data
(... and thus do not need to be programmed.)
▶ spam filter
▶ learns to recognize spam from a database of "labeled"
emails
▶ consequently can distinguish spam from ham
▶ handwritten text reader
▶ learns from a database of handwritten
letters (or text) labeled by their correct
meaning
▶ consequently is able to recognize text
▶ · · ·
▶ and lots of much, much more sophisticated applications ...
▶ Basic attributes of learning algorithms:
▶ representation: ability to capture the inner structure of
training data
▶ generalization: ability to work properly on new data
6
Machine learning in general
Machine learning algorithms typically construct mathematical
models of given data. The models may be subsequently
applied to fresh data.
7
Machine learning in general
Machine learning algorithms typically construct mathematical
models of given data. The models may be subsequently
applied to fresh data.
There are many types of models:
▶ decision trees
▶ support vector machines
▶ hidden Markov models
▶ Bayes networks and other graphical models
▶ neural networks
▶ · · ·
Neural networks, based on models of a (human) brain, form
a natural basis for learning algorithms!
7
Artificial neural networks
▶ Artificial neuron is a rough mathematical approximation
of a biological neuron.
▶ (Aritificial) neural network (NN) consists of a number of
interconnected artificial neurons. "Behavior" of the network
is encoded in connections between neurons.
σ
ξ
x1 x2 xn
y
Zdroj obrázku: http://tulane.edu/sse/cmb/people/schrader/
8
Why artificial neural networks?
Modelling of biological neural networks (computational
neuroscience).
▶ simplified mathematical models help to identify important
mechanisms
▶ How the brain receives information?
▶ How the information is stored?
▶ How the brain develops?
▶ · · ·
9
Why artificial neural networks?
Modelling of biological neural networks (computational
neuroscience).
▶ simplified mathematical models help to identify important
mechanisms
▶ How the brain receives information?
▶ How the information is stored?
▶ How the brain develops?
▶ · · ·
▶ neuroscience is strongly multidisciplinary; precise
mathematical descriptions help in communication among
experts and in design of new experiments.
I will not spend much time on this area!
9
Why artificial neural networks?
Neural networks in machine learning.
▶ Typically primitive models, far from their biological
counterparts (but often inspired by biology).
10
Why artificial neural networks?
Neural networks in machine learning.
▶ Typically primitive models, far from their biological
counterparts (but often inspired by biology).
▶ Strongly oriented towards concrete application domains:
▶ decision making and control - autonomous vehicles,
manufacturing processes, control of natural resources
▶ games - backgammon, poker, GO, Starcraft, ...
▶ finance - stock prices, risk analysis
▶ medicine - diagnosis, signal processing (EKG, EEG, ...), image
processing (MRI, CT, WSI ...)
▶ text and speech processing - machine translation, text
generation, speech recognition
▶ other signal processing - filtering, radar tracking, noise
reduction
▶ art - music and painting generation, deepfakes
▶ · · ·
I will concentrate on this area!
10
Important features of neural networks
▶ Massive parallelism
▶ many slow (and "dumb") computational elements work in
parallel on several levels of abstraction
11
Important features of neural networks
▶ Massive parallelism
▶ many slow (and "dumb") computational elements work in
parallel on several levels of abstraction
▶ Learning
▶ a kid learns to recognize a rabbit after seeing several
rabbits
11
Important features of neural networks
▶ Massive parallelism
▶ many slow (and "dumb") computational elements work in
parallel on several levels of abstraction
▶ Learning
▶ a kid learns to recognize a rabbit after seeing several
rabbits
▶ Generalization
▶ a kid is able to recognize a new rabbit after seeing several
(old) rabbits
11
Important features of neural networks
▶ Massive parallelism
▶ many slow (and "dumb") computational elements work in
parallel on several levels of abstraction
▶ Learning
▶ a kid learns to recognize a rabbit after seeing several
rabbits
▶ Generalization
▶ a kid is able to recognize a new rabbit after seeing several
(old) rabbits
▶ Robustness
▶ a blurred photo of a rabbit may still be classified as an
image of a rabbit
11
Important features of neural networks
▶ Massive parallelism
▶ many slow (and "dumb") computational elements work in
parallel on several levels of abstraction
▶ Learning
▶ a kid learns to recognize a rabbit after seeing several
rabbits
▶ Generalization
▶ a kid is able to recognize a new rabbit after seeing several
(old) rabbits
▶ Robustness
▶ a blurred photo of a rabbit may still be classified as an
image of a rabbit
▶ Graceful degradation
▶ Experiments have shown that damaged neural network is
still able to work quite well
▶ Damaged network may re-adapt, remaining neurons may
take on functionality of the damaged ones
11
The aim of the course
▶ We will concentrate on
▶ basic techniques and principles of neural networks,
▶ fundamental models of neural networks and their
applications.
▶ You should learn
▶ basic models
(multilayer perceptron, convolutional networks, recurrent networks,
transformers, autoencoders and generative adversarial networks)
12
The aim of the course
▶ We will concentrate on
▶ basic techniques and principles of neural networks,
▶ fundamental models of neural networks and their
applications.
▶ You should learn
▶ basic models
(multilayer perceptron, convolutional networks, recurrent networks,
transformers, autoencoders and generative adversarial networks)
▶ Simple applications of these models
(image processing, a little bit of text processing)
12
The aim of the course
▶ We will concentrate on
▶ basic techniques and principles of neural networks,
▶ fundamental models of neural networks and their
applications.
▶ You should learn
▶ basic models
(multilayer perceptron, convolutional networks, recurrent networks,
transformers, autoencoders and generative adversarial networks)
▶ Simple applications of these models
(image processing, a little bit of text processing)
▶ Basic learning algorithms
(gradient descent with backpropagation)
12
The aim of the course
▶ We will concentrate on
▶ basic techniques and principles of neural networks,
▶ fundamental models of neural networks and their
applications.
▶ You should learn
▶ basic models
(multilayer perceptron, convolutional networks, recurrent networks,
transformers, autoencoders and generative adversarial networks)
▶ Simple applications of these models
(image processing, a little bit of text processing)
▶ Basic learning algorithms
(gradient descent with backpropagation)
▶ Basic practical training techniques
(data preparation, setting various hyper-parameters, control of
learning, improving generalization)
12
The aim of the course
▶ We will concentrate on
▶ basic techniques and principles of neural networks,
▶ fundamental models of neural networks and their
applications.
▶ You should learn
▶ basic models
(multilayer perceptron, convolutional networks, recurrent networks,
transformers, autoencoders and generative adversarial networks)
▶ Simple applications of these models
(image processing, a little bit of text processing)
▶ Basic learning algorithms
(gradient descent with backpropagation)
▶ Basic practical training techniques
(data preparation, setting various hyper-parameters, control of
learning, improving generalization)
▶ Basic information about current implementations
(TensorFlow-Keras, Pytorch)
12
Biological neural network
▶ Human neural network consists of approximately 1011 (100
billion on the short scale) neurons; a single cubic
centimeter of a human brain contains almost 50 million
neurons.
▶ Each neuron is connected with approx. 104 neurons.
▶ Neurons themselves are very complex systems.
13
Biological neural network
▶ Human neural network consists of approximately 1011 (100
billion on the short scale) neurons; a single cubic
centimeter of a human brain contains almost 50 million
neurons.
▶ Each neuron is connected with approx. 104 neurons.
▶ Neurons themselves are very complex systems.
Rough description of nervous system:
▶ External stimulus is received by sensory receptors (e.g.
eye cells).
13
Biological neural network
▶ Human neural network consists of approximately 1011 (100
billion on the short scale) neurons; a single cubic
centimeter of a human brain contains almost 50 million
neurons.
▶ Each neuron is connected with approx. 104 neurons.
▶ Neurons themselves are very complex systems.
Rough description of nervous system:
▶ External stimulus is received by sensory receptors (e.g.
eye cells).
▶ Information is futher transfered via peripheral nervous
system (PNS) to the central nervous systems (CNS) where
it is processed (integrated), and subseqently, an output
signal is produced.
13
Biological neural network
▶ Human neural network consists of approximately 1011 (100
billion on the short scale) neurons; a single cubic
centimeter of a human brain contains almost 50 million
neurons.
▶ Each neuron is connected with approx. 104 neurons.
▶ Neurons themselves are very complex systems.
Rough description of nervous system:
▶ External stimulus is received by sensory receptors (e.g.
eye cells).
▶ Information is futher transfered via peripheral nervous
system (PNS) to the central nervous systems (CNS) where
it is processed (integrated), and subseqently, an output
signal is produced.
▶ Afterwards, the output signal is transfered via PNS to
effectors (e.g. muscle cells).
13
Biological neural network
Zdroj: N. Campbell and J. Reece; Biology, 7th Edition; ISBN: 080537146X
14
Summation
15
Biological and Mathematical neurons
16
Formal neuron (without bias)
σ
ξ
x1 x2 xn
y
w1 w2
· · ·
wn
▶ x1, . . . , xn ∈ R are inputs
17
Formal neuron (without bias)
σ
ξ
x1 x2 xn
y
w1 w2
· · ·
wn
▶ x1, . . . , xn ∈ R are inputs
▶ w1, . . . , wn ∈ R are weights
17
Formal neuron (without bias)
σ
ξ
x1 x2 xn
y
w1 w2
· · ·
wn
▶ x1, . . . , xn ∈ R are inputs
▶ w1, . . . , wn ∈ R are weights
▶ ξ is an inner potential;
almost always ξ = n
i=1 wixi
17
Formal neuron (without bias)
σ
ξ
x1 x2 xn
y
w1 w2
· · ·
wn
▶ x1, . . . , xn ∈ R are inputs
▶ w1, . . . , wn ∈ R are weights
▶ ξ is an inner potential;
almost always ξ = n
i=1 wixi
▶ y is an output given by y = σ(ξ)
where σ is an activation function;
e.g. a unit step function
σ(ξ) =



1 ξ ≥ h ;
0 ξ < h.
where h ∈ R is a threshold.
17
Formal neuron (with bias)
σ
ξ
x1 x2 xn
x0 = 1
bias
threshold
y
w1 w2
· · ·
wn
w0 = −h
▶ x0 = 1, x1, . . . , xn ∈ R are inputs
18
Formal neuron (with bias)
σ
ξ
x1 x2 xn
x0 = 1
bias
threshold
y
w1 w2
· · ·
wn
w0 = −h
▶ x0 = 1, x1, . . . , xn ∈ R are inputs
▶ w0, w1, . . . , wn ∈ R are weights
18
Formal neuron (with bias)
σ
ξ
x1 x2 xn
x0 = 1
bias
threshold
y
w1 w2
· · ·
wn
w0 = −h
▶ x0 = 1, x1, . . . , xn ∈ R are inputs
▶ w0, w1, . . . , wn ∈ R are weights
▶ ξ is an inner potential;
almost always ξ = w0 + n
i=1 wixi
18
Formal neuron (with bias)
σ
ξ
x1 x2 xn
x0 = 1
bias
threshold
y
w1 w2
· · ·
wn
w0 = −h
▶ x0 = 1, x1, . . . , xn ∈ R are inputs
▶ w0, w1, . . . , wn ∈ R are weights
▶ ξ is an inner potential;
almost always ξ = w0 + n
i=1 wixi
▶ y is an output given by y = σ(ξ)
where σ is an activation
function;
e.g. a unit step function
σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
(The threshold h has been substituted
with the new input x0 = 1 and the weight
w0 = −h.)
18
Neuron and linear separation
ξ = 0
ξ > 0
ξ > 0
ξ < 0
ξ < 0
▶ inner potential
ξ = w0 +
n
i=1
wixi
determines a separation
hyperplane in
the n-dimensional input space
▶ in 2d line
▶ in 3d plane
▶ · · ·
19
Neuron geometry
20
Neuron and linear separation
σ σ( wixi)
x1 xn
· · ·
1/0 by A/B
w1 wn
n = 8 · 8, i.e. the number of pixels in the images. Inputs are
binary vectors of dimension n (black pixel ≈ 1, white pixel ≈ 0).
21
Neuron and linear separation
σ
x1 xn
· · ·
x0 = 1
1/0 pro A/B
w1 wn
w0
n = 8 · 8, i.e. the number of pixels in the images. Inputs are
binary vectors of dimension n (black pixel ≈ 1, white pixel ≈ 0).
22
Neuron and linear separation
¯w0 + n
i=1 ¯wixi = 0
w0 + n
i=1 wixi = 0
A
A
A A
B
B
B
▶ Red line classifies incorrectly
▶ Green line classifies correctly
(may be a result of
a correction by a learning
algorithm)
23
Neuron and linear separation (XOR)
0
(0, 0)
1
(0, 1)
1
(0, 1)
0
(1, 1)
x1
x2
▶ No line separates ones from
zeros.
24
Neural networks
Neural network consists of formal neurons interconnected in
such a way that the output of one neuron is an input of several
other neurons.
In order to describe a particular type of neural networks we
need to specify:
▶ Architecture
How the neurons are connected.
▶ Activity
How the network transforms inputs to outputs.
▶ Learning
How the weights are changed during training.
25
Architecture
Network architecture is given as a digraph whose nodes are
neurons and edges are connections.
We distinguish several categories of
neurons:
▶ Output neurons
▶ Hidden neurons
▶ Input neurons
(In general, a neuron may be both input and
output; a neuron is hidden if it is neither input,
nor output.)
26
Architecture – Cycles
▶ A network is cyclic (recurrent) if its architecture contains a
directed cycle.
27
Architecture – Cycles
▶ A network is cyclic (recurrent) if its architecture contains a
directed cycle.
▶ Otherwise it is acyclic (feed-forward)
27
Architecture – Multilayer Perceptron (MLP)
Input
Hidden
Output
x1 x2
y1 y2
▶ Neurons partitioned into layers;
one input layer, one output layer,
possibly several hidden layers
28
Architecture – Multilayer Perceptron (MLP)
Input
Hidden
Output
x1 x2
y1 y2
▶ Neurons partitioned into layers;
one input layer, one output layer,
possibly several hidden layers
▶ layers numbered from 0; the
input layer has number 0
▶ E.g. three-layer network has
two hidden layers and one
output layer
28
Architecture – Multilayer Perceptron (MLP)
Input
Hidden
Output
x1 x2
y1 y2
▶ Neurons partitioned into layers;
one input layer, one output layer,
possibly several hidden layers
▶ layers numbered from 0; the
input layer has number 0
▶ E.g. three-layer network has
two hidden layers and one
output layer
▶ Neurons in the i-th layer are
connected with all neurons in
the i + 1-st layer
28
Architecture – Multilayer Perceptron (MLP)
Input
Hidden
Output
x1 x2
y1 y2
▶ Neurons partitioned into layers;
one input layer, one output layer,
possibly several hidden layers
▶ layers numbered from 0; the
input layer has number 0
▶ E.g. three-layer network has
two hidden layers and one
output layer
▶ Neurons in the i-th layer are
connected with all neurons in
the i + 1-st layer
▶ Architecture of a MLP is typically
described by numbers of neurons
in individual layers (e.g. 2-4-3-2)
28
Activity
Consider a network with n neurons, k input and ℓ output.
29
Activity
Consider a network with n neurons, k input and ℓ output.
▶ State of a network is a vector of output values of all
neurons.
(States of a network with n neurons are vectors of Rn
)
▶ State-space of a network is a set of all states.
29
Activity
Consider a network with n neurons, k input and ℓ output.
▶ State of a network is a vector of output values of all
neurons.
(States of a network with n neurons are vectors of Rn
)
▶ State-space of a network is a set of all states.
▶ Network input is a vector of k real numbers, i.e.
an element of Rk .
▶ Network input space is a set of all network inputs.
(sometimes we restrict ourselves to a proper subset of Rk
)
29
Activity
Consider a network with n neurons, k input and ℓ output.
▶ State of a network is a vector of output values of all
neurons.
(States of a network with n neurons are vectors of Rn
)
▶ State-space of a network is a set of all states.
▶ Network input is a vector of k real numbers, i.e.
an element of Rk .
▶ Network input space is a set of all network inputs.
(sometimes we restrict ourselves to a proper subset of Rk
)
▶ Initial state
Input neurons set to values from the network input
(each component of the network input corresponds to an input
neuron)
Values of the remaining neurons set to 0.
29
Activity – computation of a network
▶ Computation (typically) proceeds in discrete steps.
30
Activity – computation of a network
▶ Computation (typically) proceeds in discrete steps.
In every step the following happens:
30
Activity – computation of a network
▶ Computation (typically) proceeds in discrete steps.
In every step the following happens:
1. A set of neurons is selected according to some rule.
2. The selected neurons change their states according to their
inputs (they are simply evaluated).
(If a neuron does not have any inputs, its value remains constant.)
30
Activity – computation of a network
▶ Computation (typically) proceeds in discrete steps.
In every step the following happens:
1. A set of neurons is selected according to some rule.
2. The selected neurons change their states according to their
inputs (they are simply evaluated).
(If a neuron does not have any inputs, its value remains constant.)
A computation is finite on a network input ⃗x if the state
changes only finitely many times (i.e. there is a moment in
time after which the state of the network never changes).
We also say that the network stops on ⃗x.
30
Activity – computation of a network
▶ Computation (typically) proceeds in discrete steps.
In every step the following happens:
1. A set of neurons is selected according to some rule.
2. The selected neurons change their states according to their
inputs (they are simply evaluated).
(If a neuron does not have any inputs, its value remains constant.)
A computation is finite on a network input ⃗x if the state
changes only finitely many times (i.e. there is a moment in
time after which the state of the network never changes).
We also say that the network stops on ⃗x.
▶ Network output is a vector of values of all output neurons
in the network (i.e., an element of Rℓ).
Note that the network output keeps changing throughout
the computation!
30
Activity – computation of a network
▶ Computation (typically) proceeds in discrete steps.
In every step the following happens:
1. A set of neurons is selected according to some rule.
2. The selected neurons change their states according to their
inputs (they are simply evaluated).
(If a neuron does not have any inputs, its value remains constant.)
A computation is finite on a network input ⃗x if the state
changes only finitely many times (i.e. there is a moment in
time after which the state of the network never changes).
We also say that the network stops on ⃗x.
▶ Network output is a vector of values of all output neurons
in the network (i.e., an element of Rℓ).
Note that the network output keeps changing throughout
the computation!
MLP uses the following selection rule:
In the i-th step evaluate all neurons in the i-th layer.
30
Activity – semantics of a network
Definition
Consider a network with n neurons, k input, ℓ output.
Let A ⊆ Rk and B ⊆ Rℓ. Suppose that the network stops on
every input of A.
Then we say that the network computes a function F : A → B if
for every network input ⃗x the vector F(⃗x) ∈ B is the output of
the network after the computation on ⃗x stops.
31
Activity – semantics of a network
Definition
Consider a network with n neurons, k input, ℓ output.
Let A ⊆ Rk and B ⊆ Rℓ. Suppose that the network stops on
every input of A.
Then we say that the network computes a function F : A → B if
for every network input ⃗x the vector F(⃗x) ∈ B is the output of
the network after the computation on ⃗x stops.
31
Activity – semantics of a network
Definition
Consider a network with n neurons, k input, ℓ output.
Let A ⊆ Rk and B ⊆ Rℓ. Suppose that the network stops on
every input of A.
Then we say that the network computes a function F : A → B if
for every network input ⃗x the vector F(⃗x) ∈ B is the output of
the network after the computation on ⃗x stops.
Example 1
This network computes a function
from R2 to R.
31
Activity – inner potential and activation functions
In order to specify activity of the network, we need to specify
how the inner potentials ξ are computed and what are
the activation functions σ.
32
Activity – inner potential and activation functions
In order to specify activity of the network, we need to specify
how the inner potentials ξ are computed and what are
the activation functions σ.
We assume (unless otherwise specified) that
ξ = w0 +
n
i=1
wi · xi
here ⃗x = (x1, . . . , xn) are inputs of the neuron and
⃗w = (w1, . . . , wn) are weights.
32
Activity – inner potential and activation functions
In order to specify activity of the network, we need to specify
how the inner potentials ξ are computed and what are
the activation functions σ.
We assume (unless otherwise specified) that
ξ = w0 +
n
i=1
wi · xi
here ⃗x = (x1, . . . , xn) are inputs of the neuron and
⃗w = (w1, . . . , wn) are weights.
There are special types of neural networks where the inner
potential is computed differently, e.g., as a "distance" of
an input from the weight vector:
ξ = ⃗x − ⃗w
here ||·|| is a vector norm, typically Euclidean.
32
Activity – inner potential and activation functions
There are many activation functions, typical examples:
▶ Unit step function
σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
33
Activity – inner potential and activation functions
There are many activation functions, typical examples:
▶ Unit step function
σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
▶ (Logistic) sigmoid
σ(ξ) =
1
1 + e−λ·ξ
here λ ∈ R is a steepness parameter.
▶ Hyperbolic tangens
σ(ξ) =
1 − e−ξ
1 + e−ξ
▶ ReLU
σ(ξ) = max(ξ, 0)
33
Activity – XOR
1 1
σ 01 σ0 1
σ
0
1
−22 2 −2
1
−1
1
3
−2
▶ Activation function is a unit
step function
σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
▶ The network computes
XOR(x1, x2)
x1 x2 y
1 1 0
1 0 1
0 1 1
0 0 0
34
Activity – XOR
1 1
σ
11 σ0 1
σ
0
1
−22 2 −2
1
−1
1
3
−2
▶ Activation function is a unit
step function
σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
▶ The network computes
XOR(x1, x2)
x1 x2 y
1 1 0
1 0 1
0 1 1
0 0 0
34
Activity – XOR
0 0
σ 01 σ0 1
σ
0
1
−22 2 −2
1
−1
1
3
−2
▶ Activation function is a unit
step function
σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
▶ The network computes
XOR(x1, x2)
x1 x2 y
1 1 0
1 0 1
0 1 1
0 0 0
34
Activity – XOR
0 0
σ 01 σ
1 1
σ
0
1
−22 2 −2
1
−1
1
3
−2
▶ Activation function is a unit
step function
σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
▶ The network computes
XOR(x1, x2)
x1 x2 y
1 1 0
1 0 1
0 1 1
0 0 0
34
Activity – XOR
1 0
σ 01 σ0 1
σ
0
1
−22 2 −2
1
−1
1
3
−2
▶ Activation function is a unit
step function
σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
▶ The network computes
XOR(x1, x2)
x1 x2 y
1 1 0
1 0 1
0 1 1
0 0 0
34
Activity – XOR
1 0
σ
11 σ
1 1
σ
0
1
−22 2 −2
1
−1
1
3
−2
▶ Activation function is a unit
step function
σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
▶ The network computes
XOR(x1, x2)
x1 x2 y
1 1 0
1 0 1
0 1 1
0 0 0
34
Activity – XOR
1 0
σ
11 σ
1 1
σ
1
1
−22 2 −2
1
−1
1
3
−2
▶ Activation function is a unit
step function
σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
▶ The network computes
XOR(x1, x2)
x1 x2 y
1 1 0
1 0 1
0 1 1
0 0 0
34
Activity – XOR
0 1
σ 01 σ0 1
σ
0
1
−22 2 −2
1
−1
1
3
−2
▶ Activation function is a unit
step function
σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
▶ The network computes
XOR(x1, x2)
x1 x2 y
1 1 0
1 0 1
0 1 1
0 0 0
34
Activity – XOR
0 1
σ
11 σ
1 1
σ
0
1
−22 2 −2
1
−1
1
3
−2
▶ Activation function is a unit
step function
σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
▶ The network computes
XOR(x1, x2)
x1 x2 y
1 1 0
1 0 1
0 1 1
0 0 0
34
Activity – XOR
0 1
σ
11 σ
1 1
σ
1
1
−22 2 −2
1
−1
1
3
−2
▶ Activation function is a unit
step function
σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
▶ The network computes
XOR(x1, x2)
x1 x2 y
1 1 0
1 0 1
0 1 1
0 0 0
34
Activity – MLP and linear separation
0
(0, 0)
1
(0, 1)
1
(0, 1)
0
(1, 1)
P1 P2
x1
x2
σ1 σ 1
σ1
−22 2 −2
1
−1
1
3
−2
▶ The line P1 is given by
−1 + 2x1 + 2x2 = 0
▶ The line P2 is given by
3 − 2x1 − 2x2 = 0
35
Activity – example
x1
1
σ
0
1
σ0 1
σ
0
1
1
2
−5
1
−2
11
−2
−1
The activation function is
the unit step function
σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
The input is equal to 1
36
Activity – example
x1
1
σ
1
1
σ0 1
σ
0
1
1
2
−5
1
−2
11
−2
−1
The activation function is
the unit step function
σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
The input is equal to 1
36
Activity – example
x1
1
σ
1
1
σ
1 1
σ
0
1
1
2
−5
1
−2
11
−2
−1
The activation function is
the unit step function
σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
The input is equal to 1
36
Activity – example
x1
1
σ
1
1
σ
1 1
σ
1
1
1
2
−5
1
−2
11
−2
−1
The activation function is
the unit step function
σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
The input is equal to 1
36
Activity – example
x1
1
σ
0
1
σ
1 1
σ
1
1
1
2
−5
1
−2
11
−2
−1
The activation function is
the unit step function
σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
The input is equal to 1
36
Learning
Consider a network with n neurons, k input and ℓ output.
37
Learning
Consider a network with n neurons, k input and ℓ output.
▶ Configuration of a network is a vector of all values of
weights.
(Configurations of a network with m connections are elements of Rm
)
▶ Weight-space of a network is a set of all configurations.
37
Learning
Consider a network with n neurons, k input and ℓ output.
▶ Configuration of a network is a vector of all values of
weights.
(Configurations of a network with m connections are elements of Rm
)
▶ Weight-space of a network is a set of all configurations.
▶ initial configuration
weights can be initialized randomly or using some sophisticated
algorithm
37
Learning algorithms
Learning rule for weight adaptation.
(the goal is to find a configuration in which the network computes
a desired function)
38
Learning algorithms
Learning rule for weight adaptation.
(the goal is to find a configuration in which the network computes
a desired function)
▶ Supervised learning
▶ The desired function is described using training examples
that are pairs of the form (input, output).
▶ Learning algorithm searches for a configuration which
"corresponds" to the training examples, typically by
minimizing an error function.
38
Learning algorithms
Learning rule for weight adaptation.
(the goal is to find a configuration in which the network computes
a desired function)
▶ Supervised learning
▶ The desired function is described using training examples
that are pairs of the form (input, output).
▶ Learning algorithm searches for a configuration which
"corresponds" to the training examples, typically by
minimizing an error function.
▶ Unsupervised learning
▶ The training set contains only inputs.
▶ The goal is to determine distribution of the inputs
(clustering, deep belief networks, etc.)
38
Supervised learning – illustration
A
A
A A
B
B
B
▶ classification in the plane using
a single neuron
39
Supervised learning – illustration
A
A
A A
B
B
B
▶ classification in the plane using
a single neuron
▶ training examples are of the form
(point, value) where the value is
either 1, or 0 depending on whether
the point is either A, or B
39
Supervised learning – illustration
A
A
A A
B
B
B
▶ classification in the plane using
a single neuron
▶ training examples are of the form
(point, value) where the value is
either 1, or 0 depending on whether
the point is either A, or B
▶ the algorithm considers examples
one after another
▶ whenever an incorrectly classified
point is considered, the learning
algorithm turns the line in
the direction of the point
39
Summary – Advantages of neural networks
▶ Massive parallelism
▶ neurons can be evaluated in parallel
40
Summary – Advantages of neural networks
▶ Massive parallelism
▶ neurons can be evaluated in parallel
▶ Learning
▶ many sophisticated learning algorithms used to "program"
neural networks
40
Summary – Advantages of neural networks
▶ Massive parallelism
▶ neurons can be evaluated in parallel
▶ Learning
▶ many sophisticated learning algorithms used to "program"
neural networks
▶ generalization and robustness
▶ information is encoded in a distributed manner in weights
▶ "close" inputs typicaly get similar values
40
Summary – Advantages of neural networks
▶ Massive parallelism
▶ neurons can be evaluated in parallel
▶ Learning
▶ many sophisticated learning algorithms used to "program"
neural networks
▶ generalization and robustness
▶ information is encoded in a distributed manner in weights
▶ "close" inputs typicaly get similar values
▶ Graceful degradation
▶ damage typically causes only a decrease in precision of
results
40
Expressive power of neural networks
41
Formal neuron (with bias)
σ
ξ
x1 x2 xn
x0 = 1
bias
threshold
y
w1 w2
· · ·
wn
w0 = −h
▶ x0 = 1, x1, . . . , xn ∈ R are inputs
▶ w0, w1, . . . , wn ∈ R are weights
▶ ξ is an inner potential;
almost always ξ = w0 + n
i=1 wixi
▶ y is an output given by y = σ(ξ)
where σ is an activation
function;
e.g. a unit step function
σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
42
Boolean functions
Activation function: unit step function σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
43
Boolean functions
Activation function: unit step function σ(ξ) =



1 ξ ≥ 0 ;
0 ξ < 0.
σ
x1 x2 xn
x0 = 1
y = AND(x1, . . . , xn)
1 1
· · ·
1
−n
σ
x1 x2 xn
x0 = 1
y = OR(x1, . . . , xn)
1 1
· · ·
1
−1
σ
x1
x0 = 1
y = NOT(x1)
−1
0
43
Boolean functions
Theorem
Let σ be the unit step function. Two layer MLPs, where each
neuron has σ as the activation function, are able to compute all
functions of the form F : {0, 1}n → {0, 1}.
44
Boolean functions
Theorem
Let σ be the unit step function. Two layer MLPs, where each
neuron has σ as the activation function, are able to compute all
functions of the form F : {0, 1}n → {0, 1}.
Proof.
▶ Given a vector ⃗v = (v1, . . . , vn) ∈ {0, 1}n, consider a neuron
N⃗v whose output is 1 iff the input is ⃗v:
σ
y
x1 xi xn
x0 = 1
w1 wi
· · ·· · ·
wn
w0 w0 = − n
i=1 vi
wi =



1 vi = 1
−1 vi = 0
▶ Now let us connect all outputs of all neurons N⃗v satisfying
F(⃗v) = 1 using a neuron implementing OR. □
44
Non-linear separation
x1 x2
y
▶ Consider a three layer network; each neuron
has the unit step activation function.
▶ The network divides the input space in two
subspaces according to the output (0 or 1).
45
Non-linear separation
x1 x2
y
▶ Consider a three layer network; each neuron
has the unit step activation function.
▶ The network divides the input space in two
subspaces according to the output (0 or 1).
▶ The first (hidden) layer divides the input
space into half-spaces.
45
Non-linear separation
x1 x2
y
▶ Consider a three layer network; each neuron
has the unit step activation function.
▶ The network divides the input space in two
subspaces according to the output (0 or 1).
▶ The first (hidden) layer divides the input
space into half-spaces.
▶ The second layer may e.g. make
intersections of the half-spaces ⇒ convex
sets.
45
Non-linear separation
x1 x2
y
▶ Consider a three layer network; each neuron
has the unit step activation function.
▶ The network divides the input space in two
subspaces according to the output (0 or 1).
▶ The first (hidden) layer divides the input
space into half-spaces.
▶ The second layer may e.g. make
intersections of the half-spaces ⇒ convex
sets.
▶ The third layer may e.g. make unions of some
convex sets.
45
Non-linear separation – illustration
x1 xk
· · ·
· · ·
· · ·
y ▶ Consider three layer networks; each neuron
has the unit step activation function.
▶ Three layer nets are capable of
"approximating" any "reasonable" subset A of
the input space Rk .
46
Non-linear separation – illustration
x1 xk
· · ·
· · ·
· · ·
y ▶ Consider three layer networks; each neuron
has the unit step activation function.
▶ Three layer nets are capable of
"approximating" any "reasonable" subset A of
the input space Rk .
▶ Cover A with hypercubes (in 2D squares, in
3D cubes, ...)
46
Non-linear separation – illustration
x1 xk
· · ·
· · ·
· · ·
y ▶ Consider three layer networks; each neuron
has the unit step activation function.
▶ Three layer nets are capable of
"approximating" any "reasonable" subset A of
the input space Rk .
▶ Cover A with hypercubes (in 2D squares, in
3D cubes, ...)
▶ Each hypercube K can be separated using
a two layer network NK
(i.e. a function computed by NK gives 1 for
points in K and 0 for the rest).
46
Non-linear separation – illustration
x1 xk
· · ·
· · ·
· · ·
y ▶ Consider three layer networks; each neuron
has the unit step activation function.
▶ Three layer nets are capable of
"approximating" any "reasonable" subset A of
the input space Rk .
▶ Cover A with hypercubes (in 2D squares, in
3D cubes, ...)
▶ Each hypercube K can be separated using
a two layer network NK
(i.e. a function computed by NK gives 1 for
points in K and 0 for the rest).
▶ Finally, connect outputs of the nets NK
satisfying K ∩ A ∅ using a neuron
implementing OR.
46
Power of ReLU
x
· · ·
y Consider a two layer network
▶ with a single input and single output;
▶ hidden neurons with the ReLU activation:
σ(ξ) = max(ξ, 0);
▶ the output neuron with identity activation:
σ(ξ) = ξ (linear model)
47
Power of ReLU
x
· · ·
y Consider a two layer network
▶ with a single input and single output;
▶ hidden neurons with the ReLU activation:
σ(ξ) = max(ξ, 0);
▶ the output neuron with identity activation:
σ(ξ) = ξ (linear model)
For every continuous function f : [0, 1] → [0, 1] and ε > 0 there
is a network of the above type computing a function
F : [0, 1] → R such that |f(x) − F(x)| ≤ ε for all x ∈ [0, 1].
47
Power of ReLU
x
· · ·
y Consider a two layer network
▶ with a single input and single output;
▶ hidden neurons with the ReLU activation:
σ(ξ) = max(ξ, 0);
▶ the output neuron with identity activation:
σ(ξ) = ξ (linear model)
For every continuous function f : [0, 1] → [0, 1] and ε > 0 there
is a network of the above type computing a function
F : [0, 1] → R such that |f(x) − F(x)| ≤ ε for all x ∈ [0, 1].
For every open subset A ⊆ [0, 1] there is a network of the
above type such that for "most" x ∈ [0, 1] we have that x ∈ A iff
the network’s output is > 0 for the input x.
Just consider a continuous function f where f(x) is the minimum difference
between x and a point on the boundary of A. Then uniformly approximate f
using the networks. 47
48
48
48
48
48
48
48
Non-linear separation - sigmoid
Theorem (Cybenko 1989 - informal version)
Let σ be a continuous function which is sigmoidal, i.e. satisfies
σ(x) =



1 for x → +∞
0 for x → −∞
For every "reasonable" set A ⊆ [0, 1]n, there is a two layer
network where each hidden neuron has the activation function
σ (output neurons are linear), that satisfies the following:
For "most" vectors ⃗v ∈ [0, 1]n we have that ⃗v ∈ A iff the network
output is > 0 for the input ⃗v.
For mathematically oriented:
▶ "reasonable" means Lebesgue measurable
▶ "most" means that the set of incorrectly classified vectors has
the Lebesgue measure smaller than a given ε > 0
49
Non-linear separation - practical illustration
▶ ALVINN drives a car
50
Non-linear separation - practical illustration
▶ ALVINN drives a car
▶ The net has 30 × 32 = 960 inputs
(the input space is thus R960
)
50
Non-linear separation - practical illustration
▶ ALVINN drives a car
▶ The net has 30 × 32 = 960 inputs
(the input space is thus R960
)
▶ Input values correspond to
shades of gray of pixels.
50
Non-linear separation - practical illustration
▶ ALVINN drives a car
▶ The net has 30 × 32 = 960 inputs
(the input space is thus R960
)
▶ Input values correspond to
shades of gray of pixels.
▶ Output neurons "classify" images
of the road based on their
"curvature".
Image source: http://jmvidal.cse.sc.edu/talks/ann/alvin.html
50
Function approximation - two-layer networks
Theorem (Cybenko 1989)
Let σ be a continuous function which is sigmoidal, i.e., is
increasing and satisfies
σ(x) =



1 for x → +∞
0 for x → −∞
For every continuous function f : [0, 1]n → [0, 1] and every ε > 0
there is a function F : [0, 1]n → [0, 1] computed by a two layer
network where each hidden neuron has the activation function
σ (output neurons are linear), that satisfies the following
|f(⃗v) − F(⃗v)| < ε for every ⃗v ∈ [0, 1]n
.
51
Neural networks and computability
▶ Consider recurrent networks (i.e., containing cycles)
52
Neural networks and computability
▶ Consider recurrent networks (i.e., containing cycles)
▶ with real weights (in general);
52
Neural networks and computability
▶ Consider recurrent networks (i.e., containing cycles)
▶ with real weights (in general);
▶ one input neuron and one output neuron (the network
computes a function F : A → R where A ⊆ R contains all
inputs on which the network stops);
52
Neural networks and computability
▶ Consider recurrent networks (i.e., containing cycles)
▶ with real weights (in general);
▶ one input neuron and one output neuron (the network
computes a function F : A → R where A ⊆ R contains all
inputs on which the network stops);
▶ parallel activity rule (output values of all neurons are
recomputed in every step);
52
Neural networks and computability
▶ Consider recurrent networks (i.e., containing cycles)
▶ with real weights (in general);
▶ one input neuron and one output neuron (the network
computes a function F : A → R where A ⊆ R contains all
inputs on which the network stops);
▶ parallel activity rule (output values of all neurons are
recomputed in every step);
▶ activation function
σ(ξ) =



1 ξ ≥ 1 ;
ξ 0 ≤ ξ ≤ 1 ;
0 ξ < 0.
52
Neural networks and computability
▶ Consider recurrent networks (i.e., containing cycles)
▶ with real weights (in general);
▶ one input neuron and one output neuron (the network
computes a function F : A → R where A ⊆ R contains all
inputs on which the network stops);
▶ parallel activity rule (output values of all neurons are
recomputed in every step);
▶ activation function
σ(ξ) =



1 ξ ≥ 1 ;
ξ 0 ≤ ξ ≤ 1 ;
0 ξ < 0.
▶ We encode words ω ∈ {0, 1}+ into numbers as follows:
δ(ω) =
|ω|
i=1
ω(i)
2i
+
1
2|ω|+1
E.g. ω = 11001 gives δ(ω) = 1
2 + 1
22 + 1
25 + 1
26
(= 0.110011 in binary form).
52
Neural networks and computability
A network recognizes a language L ⊆ {0, 1}+ if it computes a
function F : A → R (A ⊆ R) such that
ω ∈ L iff δ(ω) ∈ A and F(δ(ω)) > 0.
53
Neural networks and computability
A network recognizes a language L ⊆ {0, 1}+ if it computes a
function F : A → R (A ⊆ R) such that
ω ∈ L iff δ(ω) ∈ A and F(δ(ω)) > 0.
▶ Recurrent networks with rational weights are equivalent to
Turing machines
▶ For every recursively enumerable language L ⊆ {0, 1}+
there is a recurrent network with rational weights and less
than 1000 neurons, which recognizes L.
▶ The halting problem is undecidable for networks with at
least 25 neurons and rational weights.
▶ There is "universal" network (equivalent of the universal
Turing machine)
53
Neural networks and computability
A network recognizes a language L ⊆ {0, 1}+ if it computes a
function F : A → R (A ⊆ R) such that
ω ∈ L iff δ(ω) ∈ A and F(δ(ω)) > 0.
▶ Recurrent networks with rational weights are equivalent to
Turing machines
▶ For every recursively enumerable language L ⊆ {0, 1}+
there is a recurrent network with rational weights and less
than 1000 neurons, which recognizes L.
▶ The halting problem is undecidable for networks with at
least 25 neurons and rational weights.
▶ There is "universal" network (equivalent of the universal
Turing machine)
▶ Recurrent networks are super-Turing powerful
53
Neural networks and computability
A network recognizes a language L ⊆ {0, 1}+ if it computes a
function F : A → R (A ⊆ R) such that
ω ∈ L iff δ(ω) ∈ A and F(δ(ω)) > 0.
▶ Recurrent networks with rational weights are equivalent to
Turing machines
▶ For every recursively enumerable language L ⊆ {0, 1}+
there is a recurrent network with rational weights and less
than 1000 neurons, which recognizes L.
▶ The halting problem is undecidable for networks with at
least 25 neurons and rational weights.
▶ There is "universal" network (equivalent of the universal
Turing machine)
▶ Recurrent networks are super-Turing powerful
▶ For every language L ⊆ {0, 1}+
there is a recurrent network
with less than 1000 nerons which recognizes L.
53
Summary of theoretical results
▶ Neural networks are very strong from the point of view of
theory:
▶ All Boolean functions can be expressed using two-layer
networks.
▶ Two-layer networks may approximate any continuous
function.
▶ Recurrent networks are at least as strong as Turing
machines.
54
Summary of theoretical results
▶ Neural networks are very strong from the point of view of
theory:
▶ All Boolean functions can be expressed using two-layer
networks.
▶ Two-layer networks may approximate any continuous
function.
▶ Recurrent networks are at least as strong as Turing
machines.
▶ These results are purely theoretical!
▶ "Theoretical" networks are extremely huge.
▶ It is very difficult to handcraft them even for simplest
problems.
▶ From practical point of view, the most important
advantages of neural networks are: learning,
generalization, robustness.
54
Neural networks vs classical computers
Neural networks "Classical" computers
Data implicitly in weights explicitly
Computation naturally parallel sequential, localized
Robustness robust w.r.t. input corruption
& damage
changing one bit may
completely crash the
computation
Precision imprecise, network recalls a
training example "similar" to
the input
(typically) precise
Programming learning manual
55
History & implementations
56
History of neurocomputers
▶ 1951: SNARC (Minski et al)
▶ the first implementation of neural network
▶ a rat strives to exit a maze
▶ 40 artificial neurons (300 vacuum tubes, engines, etc.)
57
History of neurocomputers
▶ 1957: Mark I Perceptron (Rosenblatt et al) - the first
successful network for image recognition
▶ single layer network
▶ image represented by 20 × 20 photocells
▶ intensity of pixels was treated as the input to a perceptron
(basically the formal neuron), which recognized figures
▶ weights were implemented using potentiometers, each set
by its own engine
▶ it was possible to arbitrarily reconnect inputs to neurons to
demonstrate adaptability
58
History of neurocomputers
▶ 1960: ADALINE (Widrow & Hof)
▶ single layer neural network
▶ weights stored in a newly invented electronic component
memistor, which remembers history of electric current in
the form of resistance.
▶ Widrow founded a company Memistor Corporation, which
sold implementations of neural networks.
▶ 1960-66: several companies concerned with neural
networks were founded.
59
History of neurocomputers
▶ 1967-82: dead still after publication of a book by Minski &
Papert (published 1969, title Perceptrons)
▶ 1983-end of 90s: revival of neural networks
▶ many attempts at hardware implementations
▶ application specific chips (ASIC)
▶ programmable hardware (FPGA)
▶ hw implementations typically not better than "software"
implementations on universal computers (problems with
weight storage, size, speed, cost of production etc.)
60
History of neurocomputers
▶ 1967-82: dead still after publication of a book by Minski &
Papert (published 1969, title Perceptrons)
▶ 1983-end of 90s: revival of neural networks
▶ many attempts at hardware implementations
▶ application specific chips (ASIC)
▶ programmable hardware (FPGA)
▶ hw implementations typically not better than "software"
implementations on universal computers (problems with
weight storage, size, speed, cost of production etc.)
▶ end of 90s-cca 2005: NN suppressed by other machine
learning methods (support vector machines (SVM))
▶ 2006-now: The boom of neural networks!
▶ deep networks – often better than any other method
▶ GPU implementations
▶ ... specialized hw implementations (Google’s TPU)
60
Some highlights
▶ Breakthrough in image recognition.
Accuracy of image recognition improved by an order of magnitude in 5
years.
▶ Breakthrough in game playing.
Superhuman results in Go and Chess almost without any human
intervention. Master level in Starcraft, poker, etc.
▶ Breakthrough in machine translation.
Switching to deep learning produced a 60% increase in translation
accuracy compared to the phrase-based approach previously used in
Google Translate (in human evaluation)
▶ Breakthrough in speech processing.
▶ Breakthrough in text generation.
GPT-4 generates pretty realistic articles, short plays (for a theatre) have
been successfully generated, etc.
61
Example
This slide was automatically generated byaskig GPT-4 "Give
me a beamer slide with complexity of Steepest descent,
Neton’s method and BFGS".
62
Example Source
63
History in waves ...
Figure: The figure shows two of the three historical waves of artificial
neural nets research, as measured by the frequency of the phrases
"cybernetics" and "connectionism" or "neural networks" according to
Google Books (the third wave is too recent to appear).
64
Current hardware – What do we face?
Increasing dataset size ...
... weakly-supervised pre-training using hashtags from
the Instagram uses 3.6 ∗ 109 images.
Revisiting Weakly Supervised Pre-Training of Visual Perception Models. Singh et al.
https://arxiv.org/pdf/2201.08371.pdf, 2022
65
GPT-3 Training Dataset
45 TB text data from multiple sources
Source: Kindra Cooper. OpenAI GPT-3: Everything You Need to Know. Springboard. 2023
66
Current hardware – What do we face?
... and thus increasing size of neural networks ...
2. ADALINE
4. Early back-propagation network (Rumelhart et al., 1986b)
8. Image recognition: LeNet-5 (LeCun et al., 1998b)
10. Dimensionality reduction: Deep belief network (Hinton et al., 2006)
... here the third "wave" of neural networks started
15. Digit recognition: GPU-accelerated multilayer perceptron (Ciresan et al., 2010)
18. Image recognition (AlexNet): Multi-GPU convolutional network (Krizhevsky et al., 2012)
20. Image recognition: GoogLeNet (Szegedy et al., 2014a)
67
GPT-4’s Scale: GPT-4 has 1.8 trillion parameters across 120 layers, which is
over 10 times larger than GPT-3.
68
Current hardware – What do we face?
... as a reward we get this ...
Figure: Since deep networks reached the scale necessary to
compete in the ImageNetLarge Scale Visual Recognition Challenge,
they have consistently won the competition every year, and yielded
lower and lower error rates each time. Data from Russakovsky et al.
(2014b) and He et al. (2015).
69
Current hardware
In 2012, Google trained a large network of 1.7
billion weights and 9 layers
The task was image recognition (10 million
youtube video frames)
The hw comprised a 1000 computer network
(16 000 cores), computation took three days.
70
Current hardware
In 2012, Google trained a large network of 1.7
billion weights and 9 layers
The task was image recognition (10 million
youtube video frames)
The hw comprised a 1000 computer network
(16 000 cores), computation took three days.
In 2014, similar task performed on Commodity
Off-The-Shelf High Performance Computing
(COTS HPC) technology: a cluster of GPU
servers with Infiniband interconnects and MPI.
Able to train 1 billion parameter networks on
just 3 machines in a couple of days.
Able to scale to 11 billion weights (approx. 6.5
times larger than the Google model) on 16
GPUs. 70
Current hardware – NVIDIA DGX Station
▶ 8x GPU (Nvidia A100 80GB
Tensor Core)
▶ 5 petaFLOPS
▶ System memory: 2 TB
▶ Network: 200 Gb/s InfiniBand
71
Deep learning in clouds
Big companies offer cloud services for deep learning:
▶ Amazon Web Services
▶ Google Cloud
▶ Deep Cognition
▶ ...
Advantages:
▶ Do not have to care (too much) about technical problems.
▶ Do not have to buy and optimize highend hw/sw, networks etc.
▶ Scaling & virtually limitless storage.
Disadvatages:
▶ Do not have full control.
▶ Performance can vary, connectivity problems.
▶ Have to pay for services.
▶ Privacy issues.
72
Current software
▶ TensorFlow (Google)
▶ open source software library for numerical computation
using data flow graphs
▶ allows implementation of most current neural networks
▶ allows computation on multiple devices (CPUs, GPUs, ...)
▶ Python API
▶ Keras: a part of TensorFlow that allows easy description of
most modern neural networks
▶ PyTorch (Facebook)
▶ similar to TensorFlow
▶ object oriented
▶ ... majority of new models in research papers implemented
in PyTorch
https://www.cioinsight.com/big-data/pytorch-vs-tensorflow/
▶ Theano (dead):
▶ The "academic" grand-daddy of deep-learning frameworks,
written in Python. Strongly inspired TensorFlow (some
people developing Theano moved on to develop
TensorFlow).
▶ There are others: Caffe, Deeplearning4j, ... 73
Current software – Keras
74
Current software – Keras functional API
75
Current software – TensorFlow
76
Current software – TensorFlow
77
Current software – PyTorch
78
Other software implementations
Most "mathematical" software packages contain some support
of neural networks:
▶ MATLAB
▶ R
▶ STATISTICA
▶ Weka
▶ ...
The implementations are typically not on par with the previously
mentioned dedicated deep-learning libraries.
79
MLP training – theory
80
Architecture – Multilayer Perceptron (MLP)
Input
Hidden
Output
x1 x2
y1 y2
▶ Neurons partitioned into layers;
one input layer, one output layer,
possibly several hidden layers
▶ layers numbered from 0; the
input layer has number 0
▶ E.g., a three-layer network has
two hidden layers and one
output layer
▶ Neurons in the i-th layer are
connected with all neurons in
the i + 1-st layer
▶ Architecture of a MLP is typically
described by the numbers of
neurons in individual layers (e.g.,
2-4-3-2)
81
MLP – architecture
Notation:
▶ Denote
▶ X a set of input neurons
▶ Y a set of output neurons
▶ Z a set of all neurons (X, Y ⊆ Z)
82
MLP – architecture
Notation:
▶ Denote
▶ X a set of input neurons
▶ Y a set of output neurons
▶ Z a set of all neurons (X, Y ⊆ Z)
▶ individual neurons denoted by indices i, j etc.
▶ ξj is the inner potential of the neuron j after the computation
stops
82
MLP – architecture
Notation:
▶ Denote
▶ X a set of input neurons
▶ Y a set of output neurons
▶ Z a set of all neurons (X, Y ⊆ Z)
▶ individual neurons denoted by indices i, j etc.
▶ ξj is the inner potential of the neuron j after the computation
stops
▶ yj is the output of the neuron j after the computation stops
(define y0 = 1 is the value of the formal unit input)
82
MLP – architecture
Notation:
▶ Denote
▶ X a set of input neurons
▶ Y a set of output neurons
▶ Z a set of all neurons (X, Y ⊆ Z)
▶ individual neurons denoted by indices i, j etc.
▶ ξj is the inner potential of the neuron j after the computation
stops
▶ yj is the output of the neuron j after the computation stops
(define y0 = 1 is the value of the formal unit input)
▶ wji is the weight of the connection from i to j
(in particular, wj0 is the weight of the connection from the formal unit
input, i.e., wj0 = −bj where bj is the bias of the neuron j)
82
MLP – architecture
Notation:
▶ Denote
▶ X a set of input neurons
▶ Y a set of output neurons
▶ Z a set of all neurons (X, Y ⊆ Z)
▶ individual neurons denoted by indices i, j etc.
▶ ξj is the inner potential of the neuron j after the computation
stops
▶ yj is the output of the neuron j after the computation stops
(define y0 = 1 is the value of the formal unit input)
▶ wji is the weight of the connection from i to j
(in particular, wj0 is the weight of the connection from the formal unit
input, i.e., wj0 = −bj where bj is the bias of the neuron j)
▶ j← is a set of all i such that j is adjacent from i
(i.e. there is an arc to j from i)
82
MLP – architecture
Notation:
▶ Denote
▶ X a set of input neurons
▶ Y a set of output neurons
▶ Z a set of all neurons (X, Y ⊆ Z)
▶ individual neurons denoted by indices i, j etc.
▶ ξj is the inner potential of the neuron j after the computation
stops
▶ yj is the output of the neuron j after the computation stops
(define y0 = 1 is the value of the formal unit input)
▶ wji is the weight of the connection from i to j
(in particular, wj0 is the weight of the connection from the formal unit
input, i.e., wj0 = −bj where bj is the bias of the neuron j)
▶ j← is a set of all i such that j is adjacent from i
(i.e. there is an arc to j from i)
▶ j→ is a set of all i such that j is adjacent to i
(i.e. there is an arc from j to i)
82
MLP – activity
▶ inner potential of neuron j:
ξj =
i∈j←
wjiyi
83
MLP – activity
▶ inner potential of neuron j:
ξj =
i∈j←
wjiyi
▶ activation function σj for neuron j (arbitrary differentiable)
83
MLP – activity
▶ inner potential of neuron j:
ξj =
i∈j←
wjiyi
▶ activation function σj for neuron j (arbitrary differentiable)
▶ State of non-input neuron j ∈ Z \ X after the computation
stops:
yj = σj(ξj)
(yj depends on the configuration ⃗w and the input ⃗x, so we sometimes
write yj(⃗w,⃗x) )
83
MLP – activity
▶ inner potential of neuron j:
ξj =
i∈j←
wjiyi
▶ activation function σj for neuron j (arbitrary differentiable)
▶ State of non-input neuron j ∈ Z \ X after the computation
stops:
yj = σj(ξj)
(yj depends on the configuration ⃗w and the input ⃗x, so we sometimes
write yj(⃗w,⃗x) )
▶ The network computes a function R|X|
do R|Y|
. Layer-wise computation:
First, all input neurons are assigned values of the input. In the ℓ-th step,
all neurons of the ℓ-th layer are evaluated.
83
MLP – learning
▶ Given a training dataset T of the form
⃗xk , ⃗dk k = 1, . . . , p
Here, every ⃗xk ∈ R|X| is an input vector end every ⃗dk ∈ R|Y|
is the desired network output. For every j ∈ Y, denote by
dkj the desired output of the neuron j for a given network
input ⃗xk (the vector ⃗dk can be written as dkj j∈Y
).
84
MLP – learning
▶ Given a training dataset T of the form
⃗xk , ⃗dk k = 1, . . . , p
Here, every ⃗xk ∈ R|X| is an input vector end every ⃗dk ∈ R|Y|
is the desired network output. For every j ∈ Y, denote by
dkj the desired output of the neuron j for a given network
input ⃗xk (the vector ⃗dk can be written as dkj j∈Y
).
▶ Error function:
E(⃗w) =
p
k=1
Ek (⃗w)
where
Ek (⃗w) =
1
2
j∈Y
yj(⃗w,⃗xk ) − dkj
2
This is just an example of an error function; we shall see other error
functions later. 84
MLP – learning algorithm
Batch algorithm (gradient descent):
The algorithm computes a sequence of weight vectors
⃗w(0), ⃗w(1), ⃗w(2), . . ..
▶ weights in ⃗w(0) are randomly initialized to values close to 0
▶ in the step t + 1 (here t = 0, 1, 2 . . .), weights ⃗w(t+1) are
computed as follows:
w
(t+1)
ji
= w
(t)
ji
+ ∆w
(t)
ji
85
MLP – learning algorithm
Batch algorithm (gradient descent):
The algorithm computes a sequence of weight vectors
⃗w(0), ⃗w(1), ⃗w(2), . . ..
▶ weights in ⃗w(0) are randomly initialized to values close to 0
▶ in the step t + 1 (here t = 0, 1, 2 . . .), weights ⃗w(t+1) are
computed as follows:
w
(t+1)
ji
= w
(t)
ji
+ ∆w
(t)
ji
where
∆w
(t)
ji
= −ε(t) ·
∂E
∂wji
(⃗w(t)
)
is a weight update of wji in step t + 1 and 0 < ε(t) ≤ 1 is
a learning rate in step t + 1.
85
MLP – learning algorithm
Batch algorithm (gradient descent):
The algorithm computes a sequence of weight vectors
⃗w(0), ⃗w(1), ⃗w(2), . . ..
▶ weights in ⃗w(0) are randomly initialized to values close to 0
▶ in the step t + 1 (here t = 0, 1, 2 . . .), weights ⃗w(t+1) are
computed as follows:
w
(t+1)
ji
= w
(t)
ji
+ ∆w
(t)
ji
where
∆w
(t)
ji
= −ε(t) ·
∂E
∂wji
(⃗w(t)
)
is a weight update of wji in step t + 1 and 0 < ε(t) ≤ 1 is
a learning rate in step t + 1.
Note that ∂E
∂wji
(⃗w(t)
) is a component of the gradient ∇E, i.e. the weight update
can be written as ⃗w(t+1)
= ⃗w(t)
− ε(t) · ∇E(⃗w(t)
).
https://towardsdatascience.com/a-visual-explanation-of-gradient-descent-methods-momentum-adagrad-rmsprop-
85
MLP – error function gradient
For every wji we have
∂E
∂wji
=
p
k=1
∂Ek
∂wji
86
MLP – error function gradient
For every wji we have
∂E
∂wji
=
p
k=1
∂Ek
∂wji
where for every k = 1, . . . , p holds
∂Ek
∂wji
=
∂Ek
∂yj
· σ′
j (ξj) · yi
86
MLP – error function gradient
For every wji we have
∂E
∂wji
=
p
k=1
∂Ek
∂wji
where for every k = 1, . . . , p holds
∂Ek
∂wji
=
∂Ek
∂yj
· σ′
j (ξj) · yi
and for every j ∈ Z ∖ X we get
∂Ek
∂yj
= yj − dkj for j ∈ Y
86
MLP – error function gradient
For every wji we have
∂E
∂wji
=
p
k=1
∂Ek
∂wji
where for every k = 1, . . . , p holds
∂Ek
∂wji
=
∂Ek
∂yj
· σ′
j (ξj) · yi
and for every j ∈ Z ∖ X we get
∂Ek
∂yj
= yj − dkj for j ∈ Y
∂Ek
∂yj
=
r∈j→
∂Ek
∂yr
· σ′
r (ξr ) · wrj for j ∈ Z ∖ (Y ∪ X)
(Here all yj are in fact yj(⃗w,⃗xk )).
86
Derivation of backprop.
Consider k = 1, . . . , p and a weight wji. By the chain rule:
∂Ek
∂wji
=
87
Derivation of backprop.
Consider k = 1, . . . , p and a weight wji. By the chain rule:
∂Ek
∂wji
=
∂Ek
∂yj
·
∂yj
∂wji
=
87
Derivation of backprop.
Consider k = 1, . . . , p and a weight wji. By the chain rule:
∂Ek
∂wji
=
∂Ek
∂yj
·
∂yj
∂wji
=
∂Ek
∂yj
·
∂yj
∂ξj
·
∂ξj
∂wji
=
87
Derivation of backprop.
Consider k = 1, . . . , p and a weight wji. By the chain rule:
∂Ek
∂wji
=
∂Ek
∂yj
·
∂yj
∂wji
=
∂Ek
∂yj
·
∂yj
∂ξj
·
∂ξj
∂wji
=
∂Ek
∂yj
· σ′
j (ξj) · yi
since
∂yj
∂ξj
=
∂(σj(ξj))
∂ξj
= σ′
j (ξj)
∂ξj
∂wji
=
∂ r∈j←
wjr yr
∂wji
= yi
87
Derivation of backdrop. (cont.)
For j ∈ Y :
∂Ek
∂yj
=
∂ 1
2 r∈Y (yr − dkr )2
∂yj
= yj − dkj
88
Derivation of backdrop. (cont.)
For j ∈ Y :
∂Ek
∂yj
=
∂ 1
2 r∈Y (yr − dkr )2
∂yj
= yj − dkj
... and another application of the chain rule:
For j Y :
∂Ek
∂yj
=
88
Derivation of backdrop. (cont.)
For j ∈ Y :
∂Ek
∂yj
=
∂ 1
2 r∈Y (yr − dkr )2
∂yj
= yj − dkj
... and another application of the chain rule:
For j Y :
∂Ek
∂yj
=
r∈j→
∂Ek
∂yr
·
∂yr
∂yj
=
88
Derivation of backdrop. (cont.)
For j ∈ Y :
∂Ek
∂yj
=
∂ 1
2 r∈Y (yr − dkr )2
∂yj
= yj − dkj
... and another application of the chain rule:
For j Y :
∂Ek
∂yj
=
r∈j→
∂Ek
∂yr
·
∂yr
∂yj
=
r∈j→
∂Ek
∂yr
·
∂yr
∂ξr
·
∂ξr
∂yj
=
88
Derivation of backdrop. (cont.)
For j ∈ Y :
∂Ek
∂yj
=
∂ 1
2 r∈Y (yr − dkr )2
∂yj
= yj − dkj
... and another application of the chain rule:
For j Y :
∂Ek
∂yj
=
r∈j→
∂Ek
∂yr
·
∂yr
∂yj
=
r∈j→
∂Ek
∂yr
·
∂yr
∂ξr
·
∂ξr
∂yj
=
r∈j→
∂Ek
∂yr
· σ′
r (ξr ) · wrj
since
∂yr
∂ξr
=
∂(σr (ξr ))
∂ξr
= σ′
r (ξr )
∂ξr
∂yj
=
∂ s∈r←
wrsys
∂yj
= wrj
88
MLP – error function gradient (history)
▶ If yj = σj(ξj) = 1
1+e
−ξj
for all j ∈ Z, then
σ′
j (ξj) = yj(1 − yj)
89
MLP – error function gradient (history)
▶ If yj = σj(ξj) = 1
1+e
−ξj
for all j ∈ Z, then
σ′
j (ξj) = yj(1 − yj)
and thus for all j ∈ Z ∖ X:
∂Ek
∂yj
= yj − dkj for j ∈ Y
∂Ek
∂yj
=
r∈j→
∂Ek
∂yr
· yr (1 − yr ) · wrj for j ∈ Z ∖ (Y ∪ X)
89
MLP – computing the gradient
Compute ∂E
∂wji
= p
k=1
∂Ek
∂wji
as follows:
90
MLP – computing the gradient
Compute ∂E
∂wji
= p
k=1
∂Ek
∂wji
as follows:
Initialize Eji := 0
(By the end of the computation: Eji = ∂E
∂wji
)
90
MLP – computing the gradient
Compute ∂E
∂wji
= p
k=1
∂Ek
∂wji
as follows:
Initialize Eji := 0
(By the end of the computation: Eji = ∂E
∂wji
)
For every k = 1, . . . , p do:
90
MLP – computing the gradient
Compute ∂E
∂wji
= p
k=1
∂Ek
∂wji
as follows:
Initialize Eji := 0
(By the end of the computation: Eji = ∂E
∂wji
)
For every k = 1, . . . , p do:
1. forward pass: compute yj = yj(⃗w,⃗xk ) for all j ∈ Z
90
MLP – computing the gradient
Compute ∂E
∂wji
= p
k=1
∂Ek
∂wji
as follows:
Initialize Eji := 0
(By the end of the computation: Eji = ∂E
∂wji
)
For every k = 1, . . . , p do:
1. forward pass: compute yj = yj(⃗w,⃗xk ) for all j ∈ Z
2. backward pass: compute ∂Ek
∂yj
for all j ∈ Z using
backpropagation (see the next slide!)
90
MLP – computing the gradient
Compute ∂E
∂wji
= p
k=1
∂Ek
∂wji
as follows:
Initialize Eji := 0
(By the end of the computation: Eji = ∂E
∂wji
)
For every k = 1, . . . , p do:
1. forward pass: compute yj = yj(⃗w,⃗xk ) for all j ∈ Z
2. backward pass: compute ∂Ek
∂yj
for all j ∈ Z using
backpropagation (see the next slide!)
3. compute ∂Ek
∂wji
for all wji using
∂Ek
∂wji
:=
∂Ek
∂yj
· σ′
j (ξj) · yi
90
MLP – computing the gradient
Compute ∂E
∂wji
= p
k=1
∂Ek
∂wji
as follows:
Initialize Eji := 0
(By the end of the computation: Eji = ∂E
∂wji
)
For every k = 1, . . . , p do:
1. forward pass: compute yj = yj(⃗w,⃗xk ) for all j ∈ Z
2. backward pass: compute ∂Ek
∂yj
for all j ∈ Z using
backpropagation (see the next slide!)
3. compute ∂Ek
∂wji
for all wji using
∂Ek
∂wji
:=
∂Ek
∂yj
· σ′
j (ξj) · yi
4. Eji := Eji + ∂Ek
∂wji
The resulting Eji equals ∂E
∂wji
.
90
MLP – backpropagation
Compute ∂Ek
∂yj
for all j ∈ Z as follows:
91
MLP – backpropagation
Compute ∂Ek
∂yj
for all j ∈ Z as follows:
▶ if j ∈ Y, then ∂Ek
∂yj
= yj − dkj
91
MLP – backpropagation
Compute ∂Ek
∂yj
for all j ∈ Z as follows:
▶ if j ∈ Y, then ∂Ek
∂yj
= yj − dkj
▶ if j ∈ Z ∖ Y ∪ X, then assuming that j is in the ℓ-th layer and
assuming that ∂Ek
∂yr
has already been computed for all
neurons in the ℓ + 1-st layer, compute
∂Ek
∂yj
=
r∈j→
∂Ek
∂yr
· σ′
r (ξr ) · wrj
(This works because all neurons of r ∈ j→
belong to the ℓ + 1-st layer.)
91
Complexity of the batch algorithm
Computation of ∂E
∂wji
(⃗w(t−1)) stops in time linear in the size of
the network plus the size of the training set.
(assuming unit cost of operations including computation of σ′
r (ξr ) for given ξr )
92
Complexity of the batch algorithm
Computation of ∂E
∂wji
(⃗w(t−1)) stops in time linear in the size of
the network plus the size of the training set.
(assuming unit cost of operations including computation of σ′
r (ξr ) for given ξr )
Proof sketch: The algorithm does the following p times:
92
Complexity of the batch algorithm
Computation of ∂E
∂wji
(⃗w(t−1)) stops in time linear in the size of
the network plus the size of the training set.
(assuming unit cost of operations including computation of σ′
r (ξr ) for given ξr )
Proof sketch: The algorithm does the following p times:
1. forward pass, i.e. computes yj(⃗w,⃗xk )
92
Complexity of the batch algorithm
Computation of ∂E
∂wji
(⃗w(t−1)) stops in time linear in the size of
the network plus the size of the training set.
(assuming unit cost of operations including computation of σ′
r (ξr ) for given ξr )
Proof sketch: The algorithm does the following p times:
1. forward pass, i.e. computes yj(⃗w,⃗xk )
2. backpropagation, i.e. computes ∂Ek
∂yj
92
Complexity of the batch algorithm
Computation of ∂E
∂wji
(⃗w(t−1)) stops in time linear in the size of
the network plus the size of the training set.
(assuming unit cost of operations including computation of σ′
r (ξr ) for given ξr )
Proof sketch: The algorithm does the following p times:
1. forward pass, i.e. computes yj(⃗w,⃗xk )
2. backpropagation, i.e. computes ∂Ek
∂yj
3. computes ∂Ek
∂wji
and adds it to Eji (a constant time operation
in the unit cost framework)
92
Complexity of the batch algorithm
Computation of ∂E
∂wji
(⃗w(t−1)) stops in time linear in the size of
the network plus the size of the training set.
(assuming unit cost of operations including computation of σ′
r (ξr ) for given ξr )
Proof sketch: The algorithm does the following p times:
1. forward pass, i.e. computes yj(⃗w,⃗xk )
2. backpropagation, i.e. computes ∂Ek
∂yj
3. computes ∂Ek
∂wji
and adds it to Eji (a constant time operation
in the unit cost framework)
The steps 1. - 3. take linear time w.r.t. the number of network
weights.
92
Complexity of the batch algorithm
Computation of ∂E
∂wji
(⃗w(t−1)) stops in time linear in the size of
the network plus the size of the training set.
(assuming unit cost of operations including computation of σ′
r (ξr ) for given ξr )
Proof sketch: The algorithm does the following p times:
1. forward pass, i.e. computes yj(⃗w,⃗xk )
2. backpropagation, i.e. computes ∂Ek
∂yj
3. computes ∂Ek
∂wji
and adds it to Eji (a constant time operation
in the unit cost framework)
The steps 1. - 3. take linear time w.r.t. the number of network
weights.
Note that the speed of convergence of the gradient descent cannot be
estimated ...
92
Illustration of the gradient descent – XOR
Source: Pattern Classification (2nd Edition); Richard O. Duda, Peter E. Hart, David G. Stork
93
MLP – learning algorithm
Online algorithm:
The algorithm computes a sequence of weight vectors
⃗w(0), ⃗w(1), ⃗w(2), . . ..
▶ weights in ⃗w(0) are randomly initialized to values close to 0
▶ in the step t + 1 (here t = 0, 1, 2 . . .), weights ⃗w(t+1) are
computed as follows:
w
(t+1)
ji
= w
(t)
ji
+ ∆w
(t)
ji
where
∆w
(t)
ji
= −ε(t) ·
∂Ek
∂wji
(w
(t)
ji
)
is the weight update of wji in the step t + 1 and 0 < ε(t) ≤ 1
is the learning rate in the step t + 1.
There are other variants determined by the selection of the training examples
used for the error computation (more on this later).
94
SGD
▶ weights in ⃗w(0)
are randomly initialized to values close to 0
▶ in the step t + 1 (here t = 0, 1, 2 . . .), weights ⃗w(t+1)
are
computed as follows:
▶ Choose (randomly) a set of training examples T ⊆ {1, . . . , p}
▶ Compute
⃗w(t+1)
= ⃗w(t)
+ ∆⃗w(t)
where
∆⃗w(t)
= −ε(t) ·
k∈T
∇Ek (⃗w(t)
)
▶ 0 < ε(t) ≤ 1 is a learning rate in step t + 1
▶ ∇Ek (⃗w(t)
) is the gradient of the error of the example k
Note that the random choice of the minibatch is typically implemented by
randomly shuffling all data and then choosing minibatches sequentially.
95
Regression: Output and Error
▶ For regression, the output activation is typically the
identity, i.e., yi = σ(ξi) = ξi for i ∈ Y.
96
Regression: Output and Error
▶ For regression, the output activation is typically the
identity, i.e., yi = σ(ξi) = ξi for i ∈ Y.
▶ A training dataset
⃗xk , ⃗dk k = 1, . . . , p
Here, every ⃗xk ∈ R|X| is an input vector end every ⃗dk ∈ R|Y|
is the desired network output. For every i ∈ Y, denote by
dki the desired output of the neuron i for a given network
input ⃗xk (the vector ⃗dk can be written as (dki)i∈Y ).
96
Regression: Output and Error
▶ For regression, the output activation is typically the
identity, i.e., yi = σ(ξi) = ξi for i ∈ Y.
▶ A training dataset
⃗xk , ⃗dk k = 1, . . . , p
Here, every ⃗xk ∈ R|X| is an input vector end every ⃗dk ∈ R|Y|
is the desired network output. For every i ∈ Y, denote by
dki the desired output of the neuron i for a given network
input ⃗xk (the vector ⃗dk can be written as (dki)i∈Y ).
▶ The error function mean squared error (mse):
E(⃗w) =
1
p
p
k=1
Ek (⃗w)
where
Ek (⃗w) =
1
2
i∈Y
yi(⃗w,⃗xk ) − dki
2
96
Maximum Likelihood vs Least Squares
Fix a training set D = (x1, d1) , (x2, d2) , . . . , xp, dp , dk ∈ R.
Consider a single output neuron o.
97
Maximum Likelihood vs Least Squares
Fix a training set D = (x1, d1) , (x2, d2) , . . . , xp, dp , dk ∈ R.
Consider a single output neuron o.
Assume that each dk was generated randomly as follows
dk = yo(⃗w,⃗xk ) + ϵk
▶ ⃗w are unknown constants
▶ ϵk are normally distributed with mean 0 and an unknown
variance σ2
97
Maximum Likelihood vs Least Squares
Fix a training set D = (x1, d1) , (x2, d2) , . . . , xp, dp , dk ∈ R.
Consider a single output neuron o.
Assume that each dk was generated randomly as follows
dk = yo(⃗w,⃗xk ) + ϵk
▶ ⃗w are unknown constants
▶ ϵk are normally distributed with mean 0 and an unknown
variance σ2
Assume that ϵ1, . . . , ϵp have been generated independently.
97
Maximum Likelihood vs Least Squares
Fix a training set D = (x1, d1) , (x2, d2) , . . . , xp, dp , dk ∈ R.
Consider a single output neuron o.
Assume that each dk was generated randomly as follows
dk = yo(⃗w,⃗xk ) + ϵk
▶ ⃗w are unknown constants
▶ ϵk are normally distributed with mean 0 and an unknown
variance σ2
Assume that ϵ1, . . . , ϵp have been generated independently.
Denote by p(d1, . . . , dp | ⃗w, σ2
) the probability density of the values
d1, . . . , dn assuming fixed x1, . . . , xp, ⃗w, σ2
.
(For the interested: The independence and definition of dk ’s imply
p(d1, . . . , dp | ⃗w, σ2
) =
p
k=1
N[yo(⃗w,⃗xk ), σ2
](dk )
N[yo(⃗w,⃗xk ), σ2
](dk ) is a normal dist. with the mean yo(⃗w,⃗xk ) and var. σ2
.)
97
Maximum Likelihood vs Least Squares
Our goal is to find the weights ⃗w that maximize the likelihood
L(⃗w, σ2
) := p(d1, . . . , dp | ⃗w, σ2
)
But now with the fixed values d1, . . . , dn from the training
set!
98
Maximum Likelihood vs Least Squares
Our goal is to find the weights ⃗w that maximize the likelihood
L(⃗w, σ2
) := p(d1, . . . , dp | ⃗w, σ2
)
But now with the fixed values d1, . . . , dn from the training
set!
Theorem
The unique ⃗w that minimize the least squares error E[⃗w]
maximize L(⃗w, σ2) for an arbitrary variance σ2.
98
Classification: Output and Error
▶ The output activation function softmax:
yi = σi(ξj1
, . . . , ξjk
) =
eξi
j∈Y eξj
Here Y = {j1, . . . , jk }
99
Classification: Output and Error
▶ The output activation function softmax:
yi = σi(ξj1
, . . . , ξjk
) =
eξi
j∈Y eξj
Here Y = {j1, . . . , jk }
▶ A training dataset
⃗xk , ⃗dk k = 1, . . . , p
Here, every ⃗xk ∈ R|X| is an input vector end every
⃗dk ∈ {0, 1}|Y| is the desired network output. For every i ∈ Y,
denote by dki the desired output of the neuron i for a given
network input ⃗xk (the vector ⃗dk can be written as (dki)i∈Y ).
99
Classification: Output and Error
▶ The output activation function softmax:
yi = σi(ξj1
, . . . , ξjk
) =
eξi
j∈Y eξj
Here Y = {j1, . . . , jk }
▶ A training dataset
⃗xk , ⃗dk k = 1, . . . , p
Here, every ⃗xk ∈ R|X| is an input vector end every
⃗dk ∈ {0, 1}|Y| is the desired network output. For every i ∈ Y,
denote by dki the desired output of the neuron i for a given
network input ⃗xk (the vector ⃗dk can be written as (dki)i∈Y ).
▶ The error function (categorical) cross entropy:
E(⃗w) = −
1
p
p
k=1 i∈Y
dki log(yi(⃗w,⃗xk ))
99
Gradient with Softmax & Cross-Entropy
Assume that V is the layer just below the output layer Y.
E(⃗w) = −
1
p
p
k=1 i∈Y
dki log(yi(⃗w,⃗xk ))
= −
1
p
p
k=1 i∈Y
dki log


eξi
j∈Y eξj


= −
1
p
p
k=1 i∈Y
dki


ξi − log


j∈Y
eξj




= −
1
p
p
k=1 i∈Y
dki


ℓ∈V
wiℓyℓ − log


j∈Y
e ℓ∈V wjℓyℓ




Now compute the derivatives δE
δyℓ
for ℓ ∈ V.
100
Binary Classification: Output and Error
Assume a single output neuron o ∈ Y = {o}.
▶ The output activation function logistic sigmoid:
σo(ξo) =
eξo
eξo + 1
=
1
1 + e−ξo
101
Binary Classification: Output and Error
Assume a single output neuron o ∈ Y = {o}.
▶ The output activation function logistic sigmoid:
σo(ξo) =
eξo
eξo + 1
=
1
1 + e−ξo
▶ A training dataset
T = ⃗x1, d1 , ⃗x2, d2 , . . . , ⃗xp, dp
Here ⃗xk = (xk0, xk1 . . . , xkn) ∈ Rn+1, xk0 = 1, is the k-th
input, and dk ∈ {0, 1} is the desired output.
101
Binary Classification: Output and Error
Assume a single output neuron o ∈ Y = {o}.
▶ The output activation function logistic sigmoid:
σo(ξo) =
eξo
eξo + 1
=
1
1 + e−ξo
▶ A training dataset
T = ⃗x1, d1 , ⃗x2, d2 , . . . , ⃗xp, dp
Here ⃗xk = (xk0, xk1 . . . , xkn) ∈ Rn+1, xk0 = 1, is the k-th
input, and dk ∈ {0, 1} is the desired output.
▶ The error function (Binary) cross-entropy:
E(⃗w) = −
p
k=1
dk log(yo(⃗w,⃗xk ))+(1−dk ) log(1−yo(⃗w,⃗xk ))
101
Cross-entropy vs max likelihood
Consider our model giving a probability yo(⃗w,⃗x) given input ⃗x.
102
Cross-entropy vs max likelihood
Consider our model giving a probability yo(⃗w,⃗x) given input ⃗x.
Recall that the training dataset is
T = ⃗x1, d1 , ⃗x2, d2 , . . . , ⃗xp, dp
Here ⃗xk = (xk0, xk1 . . . , xkn) ∈ Rn+1, xk0 = 1, is the k-th input,
and dk ∈ {0, 1} is the expected output.
102
Cross-entropy vs max likelihood
Consider our model giving a probability yo(⃗w,⃗x) given input ⃗x.
Recall that the training dataset is
T = ⃗x1, d1 , ⃗x2, d2 , . . . , ⃗xp, dp
Here ⃗xk = (xk0, xk1 . . . , xkn) ∈ Rn+1, xk0 = 1, is the k-th input,
and dk ∈ {0, 1} is the expected output.
The likelihood:
L(⃗w) =
p
k=1
yo(⃗w,⃗xk )
dk
· 1 − yo(⃗w,⃗xk )
(1−dk )
log(L) =
p
k=1
dk · log(yo(⃗w,⃗xk )) + (1 − dk ) · log(1 − yo(⃗w,⃗xk ))
and thus − log(L) = the cross-entropy.
Minimizing the cross-entropy maximizes the log-likelihood
(and vice versa).
102
Squared Error vs Logistic Output Activation
Consider a single neuron model y = σ(w · x) = 1/(1 + e−w·x)
where w ∈ R is the weight (ignore the bias).
A training dataset T = {(x, d)} where x ∈ R and d ∈ {0, 1}.
103
Squared Error vs Logistic Output Activation
Consider a single neuron model y = σ(w · x) = 1/(1 + e−w·x)
where w ∈ R is the weight (ignore the bias).
A training dataset T = {(x, d)} where x ∈ R and d ∈ {0, 1}.
Squared error E(w) = 1
2 (y − d)2.
δE
δw
= (y − d) · y · (1 − y) · x
103
Squared Error vs Logistic Output Activation
Consider a single neuron model y = σ(w · x) = 1/(1 + e−w·x)
where w ∈ R is the weight (ignore the bias).
A training dataset T = {(x, d)} where x ∈ R and d ∈ {0, 1}.
Squared error E(w) = 1
2 (y − d)2.
δE
δw
= (y − d) · y · (1 − y) · x
Thus
▶ If d = 1 and y ≈ 0, then δE
δw ≈ 0
▶ If d = 0 and y ≈ 1, then δE
δw ≈ 0
The gradient of E is small even though the model is wrong!
103
Squared Error vs Logistic Output Activation
Consider a single neuron model y = σ(w · x) = 1/(1 + e−w·x)
where w ∈ R is the weight (ignore the bias).
A training dataset T = {(x, d)} where x ∈ R and d ∈ {0, 1}.
Cross-entropy error E(w) = −d · log(y) − (1 − d) · log(1 − y).
103
Squared Error vs Logistic Output Activation
Consider a single neuron model y = σ(w · x) = 1/(1 + e−w·x)
where w ∈ R is the weight (ignore the bias).
A training dataset T = {(x, d)} where x ∈ R and d ∈ {0, 1}.
Cross-entropy error E(w) = −d · log(y) − (1 − d) · log(1 − y).
For d = 1
δE
δw
= −
1
y
· y · (1 − y) · x = −(1 − y) · x
which is close to −x for y ≈ 0.
103
Squared Error vs Logistic Output Activation
Consider a single neuron model y = σ(w · x) = 1/(1 + e−w·x)
where w ∈ R is the weight (ignore the bias).
A training dataset T = {(x, d)} where x ∈ R and d ∈ {0, 1}.
Cross-entropy error E(w) = −d · log(y) − (1 − d) · log(1 − y).
For d = 1
δE
δw
= −
1
y
· y · (1 − y) · x = −(1 − y) · x
which is close to −x for y ≈ 0.
For d = 0
δE
δw
= −
1
1 − y
· (−y) · (1 − y) · x = y · x
which is close to x for y ≈ 1.
103
MLP training – practical issues
104
Practical issues of gradient descent
▶ Training efficiency:
▶ What size of a minibatch?
▶ How to choose the learning rate ε(t) and control SGD ?
▶ How to pre-process the inputs?
▶ How to initialize weights?
▶ How to choose desired output values of the network?
105
Practical issues of gradient descent
▶ Training efficiency:
▶ What size of a minibatch?
▶ How to choose the learning rate ε(t) and control SGD ?
▶ How to pre-process the inputs?
▶ How to initialize weights?
▶ How to choose desired output values of the network?
▶ Quality of the resulting model:
▶ When to stop training?
▶ Regularization techniques.
▶ How large network?
For simplicity, I will illustrate the reasoning on MLP + mse.
Later we will see other topologies and error functions with
different but always somewhat related issues.
105
Issues in gradient descent
▶ Small networks: Lots of local minima where the descent
gets stuck.
▶ The model identifiability problem: Swapping incoming
weights of neurons i and j leaves the same network
topology – weight space symmetry.
▶ Recent studies show that for sufficiently large networks, all
local minima have low values of the error function.
106
Issues in gradient descent
▶ Small networks: Lots of local minima where the descent
gets stuck.
▶ The model identifiability problem: Swapping incoming
weights of neurons i and j leaves the same network
topology – weight space symmetry.
▶ Recent studies show that for sufficiently large networks, all
local minima have low values of the error function.
Saddle points
One can show (by a combinatorial
argument) that larger networks
have exponentially more saddle
points than local minima.
106
Issues in gradient descent – too slow descent
▶ flat regions
107
Issues in gradient descent – too fast descent
▶ steep cliffs: the gradient is extremely large, descent skips
important weight vectors
108
Issues in gradient descent – local vs global
structure
What if we initialize on the left?
109
Gradient Descent in Large Networks
Theorem
Assume (roughly),
▶ activation functions: "smooth" ReLU (softplus)
σ(z) = log(1 + exp(z))
In general: Smooth, non-polynomial, analytic, Lipschitz continuous.
▶ inputs ⃗xk of Euclidean norm equal to 1, desired values dk such
that all |dk | are bounded by a constant,
▶ the number of hidden neurons per layer sufficiently large
(polynomial in certain numerical characteristics of inputs roughly
measuring their similarity, and exponential in the depth of the network),
▶ the learning rate constant and sufficiently small.
The gradient descent converges (with high probability w.r.t. random
initialization) to a global minimum with zero error at a linear rate.
Later, we get to a special type of network called ResNet where the above
result demands only polynomially many neurons per layer (w.r.t. depth). 110
Issues in computing the gradient
▶ vanishing and exploding gradients
∂Ek
∂yj
= yj − dkj for j ∈ Y
∂Ek
∂yj
=
r∈j→
∂Ek
∂yr
· σ′
r (ξr ) · wrj for j ∈ Z ∖ (Y ∪ X)
111
Issues in computing the gradient
▶ vanishing and exploding gradients
∂Ek
∂yj
= yj − dkj for j ∈ Y
∂Ek
∂yj
=
r∈j→
∂Ek
∂yr
· σ′
r (ξr ) · wrj for j ∈ Z ∖ (Y ∪ X)
▶ inexact gradient computation:
▶ Minibatch gradient is only an estimate of the true gradient.
▶ Note that the standard deviation of the estimate is (roughly)
σ/
√
m where m is the size of the minibatch and σ is the
variance of the gradient estimate for a single training
example.
(E.g. minibatch size 10 000 means 100 times more computation
than the size 100 but gives only 10 times less deviation.)
111
Minibatch size
▶ Larger batches provide a more accurate estimate of the gradient
but with less than linear returns.
112
Minibatch size
▶ Larger batches provide a more accurate estimate of the gradient
but with less than linear returns.
▶ Multicore architectures are usually underutilized by extremely
small batches.
112
Minibatch size
▶ Larger batches provide a more accurate estimate of the gradient
but with less than linear returns.
▶ Multicore architectures are usually underutilized by extremely
small batches.
▶ If all examples in the batch are to be processed in parallel (as is
the typical case), then the amount of memory scales with the
batch size. For many hardware setups, this is the limiting factor
in batch size.
112
Minibatch size
▶ Larger batches provide a more accurate estimate of the gradient
but with less than linear returns.
▶ Multicore architectures are usually underutilized by extremely
small batches.
▶ If all examples in the batch are to be processed in parallel (as is
the typical case), then the amount of memory scales with the
batch size. For many hardware setups, this is the limiting factor
in batch size.
▶ It is common (especially when using GPUs) for power of 2 batch
sizes to offer better runtime. The typical power of 2 batch sizes
ranges from 32 to 256, with 16 sometimes being attempted for
large models.
112
Minibatch size
▶ Larger batches provide a more accurate estimate of the gradient
but with less than linear returns.
▶ Multicore architectures are usually underutilized by extremely
small batches.
▶ If all examples in the batch are to be processed in parallel (as is
the typical case), then the amount of memory scales with the
batch size. For many hardware setups, this is the limiting factor
in batch size.
▶ It is common (especially when using GPUs) for power of 2 batch
sizes to offer better runtime. The typical power of 2 batch sizes
ranges from 32 to 256, with 16 sometimes being attempted for
large models.
▶ Small batches can offer a regularizing effect, perhaps due to the
noise they add to the learning process.
It has been observed in practice that when using a larger batch,
there is a degradation in the quality of the model, as measured
by its ability to generalize.
("On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima." Keskar et al, ICLR’17)
112
Momentum
The issue in the gradient descent:
▶ ∇E(⃗w(t)) constantly changes direction (but the error
steadily decreases).
113
Momentum
The issue in the gradient descent:
▶ ∇E(⃗w(t)) constantly changes direction (but the error
steadily decreases).
Solution: In every step, add the change made in the previous
step (weighted by a factor α):
∆⃗w(t)
= −ε(t) ·
k∈T
∇Ek (⃗w(t)
) + α · ∆⃗w(t−1)
where 0 < α < 1.
113
Momentum – illustration
114
SGD with momentum
▶ weights in ⃗w(0)
are randomly initialized to values close to 0
▶ in the step t + 1 (here t = 0, 1, 2 . . .), weights ⃗w(t+1)
are
computed as follows:
▶ Choose (randomly) a set of training examples T ⊆ {1, . . . , p}
▶ Compute
⃗w(t+1)
= ⃗w(t)
+ ∆⃗w(t)
where
∆⃗w(t)
= −ε(t) ·
k∈T
∇Ek (⃗w(t)
) + α∆⃗w(t−1)
▶ 0 < ε(t) ≤ 1 is a learning rate in step t + 1
▶ 0 < α < 1 measures the "influence" of the momentum
▶ ∇Ek (⃗w(t)
) is the gradient of the error of the example k
Note that the random choice of the minibatch is typically implemented by
randomly shuffling all data and then choosing minibatches sequentially.
115
Learning rate
116
Search for the learning rate
▶ Use settings from a successful solution of a similar problem as a
baseline.
▶ Search for the learning rate using the learning monitoring:
▶ Search through values from small (e.g. 0.001) to (0.1),
possibly multiplying by 2.
▶ Train for several epochs, observe the learning curves (see
cross-validation later).
117
Adaptive learning rate
▶ Power scheduling: Set ϵ(t) = ϵ0/(1 + t/s) where ϵ0 is an initial
learning rate and s is a constant number
(after s steps the learning rate is ϵ0/2, after 2s it is ϵ0/3 etc.)
118
Adaptive learning rate
▶ Power scheduling: Set ϵ(t) = ϵ0/(1 + t/s) where ϵ0 is an initial
learning rate and s is a constant number
(after s steps the learning rate is ϵ0/2, after 2s it is ϵ0/3 etc.)
▶ Exponential scheduling: Set ϵ(t) = ϵ0 · 0.1t/s
.
(the learning rate decays faster than in the power scheduling)
118
Adaptive learning rate
▶ Power scheduling: Set ϵ(t) = ϵ0/(1 + t/s) where ϵ0 is an initial
learning rate and s is a constant number
(after s steps the learning rate is ϵ0/2, after 2s it is ϵ0/3 etc.)
▶ Exponential scheduling: Set ϵ(t) = ϵ0 · 0.1t/s
.
(the learning rate decays faster than in the power scheduling)
▶ Piecewise constant scheduling: A constant learning rate for a
number of steps/epochs, then a smaller learning rate, and so on.
118
Adaptive learning rate
▶ Power scheduling: Set ϵ(t) = ϵ0/(1 + t/s) where ϵ0 is an initial
learning rate and s is a constant number
(after s steps the learning rate is ϵ0/2, after 2s it is ϵ0/3 etc.)
▶ Exponential scheduling: Set ϵ(t) = ϵ0 · 0.1t/s
.
(the learning rate decays faster than in the power scheduling)
▶ Piecewise constant scheduling: A constant learning rate for a
number of steps/epochs, then a smaller learning rate, and so on.
▶ 1cycle scheduling: Start by increasing the initial learning rate
from ϵ0 linearly to ϵ1 (approx. ϵ1 = 10ϵ0) halfway through
training. Then decrease from ϵ1 linearly to ϵ0. Finish by dropping
the learning rate by several orders of magnitude (still linearly).
According to a 2018 paper by Leslie Smith, this may converge much
faster (100 epochs vs 800 epochs on the CIFAR10 dataset).
For a comparison of some methods, see: AN EMPIRICAL STUDY OF LEARNING RATES IN DEEP NEURAL
NETWORKS FOR SPEECH RECOGNITION, Senior et al
118
AdaGrad
So far, we have considered fixed schedules for learning rates.
It is better to have
▶ larger rates for weights with smaller updates,
▶ smaller rates for weights with larger updates.
AdaGrad uses individually adapting learning rates for each
weight.
119
SGD with AdaGrad
▶ weights in ⃗w(0)
are randomly initialized to values close to 0
▶ in the step t + 1 (here t = 0, 1, 2 . . .), compute ⃗w(t+1)
:
▶ Choose (randomly) a minibatch T ⊆ {1, . . . , p}
▶ Compute
w
(t+1)
ji
= w
(t)
ji
+ ∆w
(t)
ji
120
SGD with AdaGrad
▶ weights in ⃗w(0)
are randomly initialized to values close to 0
▶ in the step t + 1 (here t = 0, 1, 2 . . .), compute ⃗w(t+1)
:
▶ Choose (randomly) a minibatch T ⊆ {1, . . . , p}
▶ Compute
w
(t+1)
ji
= w
(t)
ji
+ ∆w
(t)
ji
where
∆w
(t)
ji
= −
η
r
(t)
ji
+ δ
·
k∈T
∂Ek
∂wji
(⃗w(t)
)
and
r
(t)
ji
= r
(t−1)
ji
+


k∈T
∂Ek
∂wji
(⃗w(t)
)


2
▶ η is a constant expressing the influence of the learning rate,
typically 0.01.
▶ δ > 0 is a smoothing term (typically 1e-8) avoiding division by 0.
120
RMSProp
The main disadvantage of AdaGrad is the accumulation of
gradients throughout the learning process.
In case the learning needs to get over several "hills" before
settling in a deep "valley," the weight updates get far too small
before getting to it.
RMSProp uses an exponentially decaying average to discard
history from the extreme past so that it can converge rapidly
after finding a convex bowl as if it were an instance of the
AdaGrad algorithm initialized within that bowl.
121
SGD with RMSProp
▶ weights in ⃗w(0)
are randomly initialized to values close to 0
▶ in the step t + 1 (here t = 0, 1, 2 . . .), compute ⃗w(t+1)
:
▶ Choose (randomly) a minibatch T ⊆ {1, . . . , p}
▶ Compute
w
(t+1)
ji
= w
(t)
ji
+ ∆w
(t)
ji
122
SGD with RMSProp
▶ weights in ⃗w(0)
are randomly initialized to values close to 0
▶ in the step t + 1 (here t = 0, 1, 2 . . .), compute ⃗w(t+1)
:
▶ Choose (randomly) a minibatch T ⊆ {1, . . . , p}
▶ Compute
w
(t+1)
ji
= w
(t)
ji
+ ∆w
(t)
ji
where
∆w
(t)
ji
= −
η
r
(t)
ji
+ δ
·
k∈T
∂Ek
∂wji
(⃗w(t)
)
and
r
(t)
ji
= ρr
(t−1)
ji
+ (1 − ρ)


k∈T
∂Ek
∂wji
(⃗w(t)
)


2
▶ η is a constant expressing the influence of the learning rate
(Hinton suggests ρ = 0.9 and η = 0.001).
▶ δ > 0 is a smoothing term (typically 1e-8) avoiding division by 0.
122
Other optimization methods
There are more methods, such as AdaDelta and Adam
(RMSProp combined with momentum).
A natural question: Which algorithm should one choose?
123
Other optimization methods
There are more methods, such as AdaDelta and Adam
(RMSProp combined with momentum).
A natural question: Which algorithm should one choose?
Unfortunately, there is currently no consensus on this point.
According to a recent study, the family of algorithms with
adaptive learning rates (represented by RMSProp and
AdaDelta) performed fairly robustly, no single best algorithm
has emerged.
123
Other optimization methods
There are more methods, such as AdaDelta and Adam
(RMSProp combined with momentum).
A natural question: Which algorithm should one choose?
Unfortunately, there is currently no consensus on this point.
According to a recent study, the family of algorithms with
adaptive learning rates (represented by RMSProp and
AdaDelta) performed fairly robustly, no single best algorithm
has emerged.
Currently, the most popular optimization algorithms actively in
use include SGD, SGD with momentum, RMSProp, RMSProp
with momentum, AdaDelta, and Adam.
The choice of which algorithm to use, at this point, seems to
depend largely on the user’s familiarity with the algorithm.
123
Choice of (hidden) activations
Generic requirements imposed on activation functions:
1. differentiability
(to do gradient descent)
2. non-linearity
(linear multi-layer networks are equivalent to single-layer)
3. monotonicity
(local extrema of activation functions induce local extrema of the error
function)
4. "linearity"
(i.e. preserve as much linearity as possible; linear models are easiest to
fit; find the "minimum" non-linearity needed to solve a given task)
The choice of activation functions is closely related to input
preprocessing and the initial choice of weights.
124
Input preprocessing
▶ Some inputs may be much larger than others.
For example, the height vs. weight of a person, the max.
speed of a car (in km/h) vs. its price (in CZK), etc.
125
Input preprocessing
▶ Some inputs may be much larger than others.
For example, the height vs. weight of a person, the max.
speed of a car (in km/h) vs. its price (in CZK), etc.
▶ Large inputs have a greater influence on the training than
the small ones. Also, too large inputs may slow down
learning (saturation of some activation functions).
125
Input preprocessing
▶ Some inputs may be much larger than others.
For example, the height vs. weight of a person, the max.
speed of a car (in km/h) vs. its price (in CZK), etc.
▶ Large inputs have a greater influence on the training than
the small ones. Also, too large inputs may slow down
learning (saturation of some activation functions).
▶ Typical standardization:
▶ average = 0 (subtract the mean)
▶ variance = 1 (divide by the standard deviation)
Here, the mean and standard deviation may be estimated
from the data (the training set).
(illustration of standard deviation)
125
Initial weights - intuition
▶ Assume weights are chosen randomly. What distribution?
126
Initial weights - intuition
▶ Assume weights are chosen randomly. What distribution?
Consider the behavior of a deep network:
▶ Small weights make the values of inner potentials vanish.
▶ Large weights make the values of inner potentials explode.
Hence, we want to choose weights so that the inner
potentials of neurons are stable
(similar in all layers of the network).
126
Normal LeCun initialization
▶ Assume the input data have the mean = 0 and the variance = 1.
Consider a neuron j from the first layer with n inputs. Assume its
weights are chosen randomly by the normal distribution
N(0, w2
).
Assume that all random choices are independent of each other.
▶ The rule: Choose the standard deviation of weights w so that
the standard deviation of ξj (denote by oj) satisfies oj ≈ 1.
127
Normal LeCun initialization
▶ Assume the input data have the mean = 0 and the variance = 1.
Consider a neuron j from the first layer with n inputs. Assume its
weights are chosen randomly by the normal distribution
N(0, w2
).
Assume that all random choices are independent of each other.
▶ The rule: Choose the standard deviation of weights w so that
the standard deviation of ξj (denote by oj) satisfies oj ≈ 1.
▶ Basic properties of the variance of independent variables give
oj =
√
n · w.
Thus by putting w = 1
n we obtain oj = 1.
127
Normal LeCun initialization
▶ Assume the input data have the mean = 0 and the variance = 1.
Consider a neuron j from the first layer with n inputs. Assume its
weights are chosen randomly by the normal distribution
N(0, w2
).
Assume that all random choices are independent of each other.
▶ The rule: Choose the standard deviation of weights w so that
the standard deviation of ξj (denote by oj) satisfies oj ≈ 1.
▶ Basic properties of the variance of independent variables give
oj =
√
n · w.
Thus by putting w = 1
n we obtain oj = 1.
▶ The same works for higher layers; n corresponds to the number
of neurons in the layer one level lower.
This gives normal LeCun initialization:
wi ∼ N 0,
1
n
127
Derivation of the LeCun initialization
Consider a single neuron without bias with the inner potential
ξ =
n
i=1
wixi
128
Derivation of the LeCun initialization
Consider a single neuron without bias with the inner potential
ξ =
n
i=1
wixi
Consider all wi and xi as independent random variables
(hence also ξ is a random variable) where
▶ wi ∈ N(0, w2) for i = 1, . . . , n where w is a constant,
▶ Exi = 0 and Var[xi] = E[(xi − Exi)2] = 1 for i = 1, . . . , n
128
Derivation of the LeCun initialization
Consider a single neuron without bias with the inner potential
ξ =
n
i=1
wixi
Consider all wi and xi as independent random variables
(hence also ξ is a random variable) where
▶ wi ∈ N(0, w2) for i = 1, . . . , n where w is a constant,
▶ Exi = 0 and Var[xi] = E[(xi − Exi)2] = 1 for i = 1, . . . , n
We prove that Var[ξ] = n · w2 as follows:
128
Derivation of the LeCun initialization
Consider a single neuron without bias with the inner potential
ξ =
n
i=1
wixi
Consider all wi and xi as independent random variables
(hence also ξ is a random variable) where
▶ wi ∈ N(0, w2) for i = 1, . . . , n where w is a constant,
▶ Exi = 0 and Var[xi] = E[(xi − Exi)2] = 1 for i = 1, . . . , n
We prove that Var[ξ] = n · w2 as follows:
Eξ = E
n
i=1
wixi =
n
i=1
Ewixi
ind.
=
n
i=1
EwiExi = 0
128
Derivation of the LeCun initialization
Consider a single neuron without bias with the inner potential
ξ =
n
i=1
wixi
Consider all wi and xi as independent random variables
(hence also ξ is a random variable) where
▶ wi ∈ N(0, w2) for i = 1, . . . , n where w is a constant,
▶ Exi = 0 and Var[xi] = E[(xi − Exi)2] = 1 for i = 1, . . . , n
We prove that Var[ξ] = n · w2 as follows:
Eξ = E
n
i=1
wixi =
n
i=1
Ewixi
ind.
=
n
i=1
EwiExi = 0
and Var[wixi] = E[w2
i
x2
i
] − E[wixi]2 ind.
= E[w2
i
]E[x2
i
] − 0 = w2
128
Derivation of the LeCun initialization
Consider a single neuron without bias with the inner potential
ξ =
n
i=1
wixi
Consider all wi and xi as independent random variables
(hence also ξ is a random variable) where
▶ wi ∈ N(0, w2) for i = 1, . . . , n where w is a constant,
▶ Exi = 0 and Var[xi] = E[(xi − Exi)2] = 1 for i = 1, . . . , n
We prove that Var[ξ] = n · w2 as follows:
Eξ = E
n
i=1
wixi =
n
i=1
Ewixi
ind.
=
n
i=1
EwiExi = 0
and Var[wixi] = E[w2
i
x2
i
] − E[wixi]2 ind.
= E[w2
i
]E[x2
i
] − 0 = w2
implies
Var[ξ] = Var[
n
i=1
wixi]
ind.
=
n
i=1
Var[wixi] =
n
i=1
w2
= n · w2
128
Normal Glorot initialization
The previous heuristic for weight initialization ignores the variance of
the gradient (i.e., it is concerned only with the "size" of activations in
the forward pass).
129
Normal Glorot initialization
The previous heuristic for weight initialization ignores the variance of
the gradient (i.e., it is concerned only with the "size" of activations in
the forward pass).
Glorot & Bengio (2010) presented a normalized initialization by
choosing weights randomly from the following normal distribution:
N 0,
2
m + n
= N 0,
1
(m + n)/2
Here n is the number of inputs to the layer, m is the number of
neurons in the layer above.
129
Normal Glorot initialization
The previous heuristic for weight initialization ignores the variance of
the gradient (i.e., it is concerned only with the "size" of activations in
the forward pass).
Glorot & Bengio (2010) presented a normalized initialization by
choosing weights randomly from the following normal distribution:
N 0,
2
m + n
= N 0,
1
(m + n)/2
Here n is the number of inputs to the layer, m is the number of
neurons in the layer above.
This is designed to compromise between the goal of initializing all
layers to have the same activation variance and the goal of initializing
all layers to have the same gradient variance.
This gives normal Glorot initialization (also called normal Xavier
initialization):
wi ∼ N (0,
2
m + n
129
Uniform LeCun initialization
▶ Assume that the input data have mean = 0 and variance = 1.
Consider a neuron j from the first layer with n inputs. Assume its
weights are chosen randomly by the uniform distribution
U(−w, w).
Assume that all random choices are independent of each other.
▶ As before, we want the standard deviation oj of the inner
potential ξj to be approximately 1.
▶ Basic properties of the variance of independent variables give
oj = n
3 · w.
Thus by putting w = 3
n we obtain oj = 1.
We obtain uniform LeCun initialization:
wi ∼ U

−
3
n
,
3
n


130
Uniform Glorot initialization
Similarly to the normal case, we want to normalize the initialization
w.r.t. both forward and backward passes.
We obtain uniform Glorot initialization (aka uniform Xavier init.):
wi ∼ U

−
6
m + n
,
6
m + n

 = U


−
3
(m + n)/2
,
3
(m + n)/2


Here n is the number of inputs to the layer, m is the number of
neurons in the layer above.
131
Modern activation functions
For hidden neurons, sigmoidal functions are often substituted with
piece-wise linear activation functions. Most prominent is ReLU:
σ(ξ) = max{0, ξ}
▶ THE default activation function recommended for most
feedforward neural networks.
▶ As close to linear function as possible; very simple; does not
saturate for large potentials.
▶ Dead for negative potentials.
132
Normal He initialization
▶ The ReLU is not as sensitive to the large variance of
the inner potential as sigmoidal functions (large variance
does not matter as much).
133
Normal He initialization
▶ The ReLU is not as sensitive to the large variance of
the inner potential as sigmoidal functions (large variance
does not matter as much).
▶ Still, the variance is good to be constant (at least due to
the output layer).
133
Normal He initialization
▶ The ReLU is not as sensitive to the large variance of
the inner potential as sigmoidal functions (large variance
does not matter as much).
▶ Still, the variance is good to be constant (at least due to
the output layer).
▶ LeCun initialization cannot be justified for ReLU due to
the following reason:
The ReLU is not a symmetric function. So even if the inner
potential ξj has variance = 1, it is not true of the output
(the variance is halved).
133
Normal He initialization
▶ The ReLU is not as sensitive to the large variance of
the inner potential as sigmoidal functions (large variance
does not matter as much).
▶ Still, the variance is good to be constant (at least due to
the output layer).
▶ LeCun initialization cannot be justified for ReLU due to
the following reason:
The ReLU is not a symmetric function. So even if the inner
potential ξj has variance = 1, it is not true of the output
(the variance is halved).
Modifying the normal LeCun initialization to take the halving
variance into account, we obtain normal He initialization:
wi ∈ N 0,
2
n
LeCun is wi ∈ N 0,
1
n
133
More modern activation functions
▶ Leaky ReLU (green board):
▶ Generalizes ReLU, not dead for negative potentials.
▶ Experimentally not much better than ReLU.
134
More modern activation functions
▶ Leaky ReLU (green board):
▶ Generalizes ReLU, not dead for negative potentials.
▶ Experimentally not much better than ReLU.
▶ ELU: "Smoothed" ReLU:
σ(ξ) =



α(exp(ξ) − 1) for ξ < 0
ξ for ξ ≥ 0
Here α is a parameter, ELU converges to −α as ξ → −∞. As
opposed to ReLU: Smooth, always non-zero gradient (but
saturates), slower to compute.
134
More modern activation functions
▶ Leaky ReLU (green board):
▶ Generalizes ReLU, not dead for negative potentials.
▶ Experimentally not much better than ReLU.
▶ ELU: "Smoothed" ReLU:
σ(ξ) =



α(exp(ξ) − 1) for ξ < 0
ξ for ξ ≥ 0
Here α is a parameter, ELU converges to −α as ξ → −∞. As
opposed to ReLU: Smooth, always non-zero gradient (but
saturates), slower to compute.
▶ SELU: Scaled variant of ELU: :
σ(ξ) = λ



α(exp(ξ) − 1) for ξ < 0
ξ for ξ ≥ 0
Self-normalizing, i.e. output of each layer will tend to preserve
a mean (close to) 0 and a standard deviation (close to) 1 for
λ ≈ 1.050 and α ≈ 1.673, properly initialized weights (see below)
and normalized inputs (zero mean, standard deviation 1).
134
135
Initializing with Normal Distribution
Denote by n the number of inputs to the initialized layer, and m the
number of neurons in the layer.
▶ normal Glorot:
wi ∼ N (0,
2
m + n
Suitable for none, tanh, logistic, softmax
136
Initializing with Normal Distribution
Denote by n the number of inputs to the initialized layer, and m the
number of neurons in the layer.
▶ normal Glorot:
wi ∼ N (0,
2
m + n
Suitable for none, tanh, logistic, softmax
▶ normal He:
wi ∈ N 0,
2
n
Suitable for ReLU, leaky ReLU
136
Initializing with Normal Distribution
Denote by n the number of inputs to the initialized layer, and m the
number of neurons in the layer.
▶ normal Glorot:
wi ∼ N (0,
2
m + n
Suitable for none, tanh, logistic, softmax
▶ normal He:
wi ∈ N 0,
2
n
Suitable for ReLU, leaky ReLU
▶ normal LeCun:
wi ∼ N 0,
1
n
Suitable for SELU (by the authors)
136
How to choose activation of hidden neurons
▶ The default is ReLU.
▶ According to Aurélien Géron:
SELU > ELU > leakyReLU > ReLU > tanh > logistic
For discussion see: Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow: Concepts, Tools, and
Techniques to Build Intelligent Systems, Aurélien Géron
137
Batch normalization (roughly)
Intuition: Instead of keeping mean = 0 and variance = 1
implicitly due to a clever weight initialization, we may
renormalize values of neurons throughout the layers.
138
Batch normalization (roughly)
Intuition: Instead of keeping mean = 0 and variance = 1
implicitly due to a clever weight initialization, we may
renormalize values of neurons throughout the layers.
Consider the ℓ-th layer of the network.
Note that the output values of neurons in the ℓ-th layer can be
seen as inputs to the sub-network consisting of all layers above
the ℓ-th one.
138
Batch normalization (roughly)
Intuition: Instead of keeping mean = 0 and variance = 1
implicitly due to a clever weight initialization, we may
renormalize values of neurons throughout the layers.
Consider the ℓ-th layer of the network.
Note that the output values of neurons in the ℓ-th layer can be
seen as inputs to the sub-network consisting of all layers above
the ℓ-th one.
What if we standardize the values of the ℓ-th layer as we did
with the input data?
For this we need to form a "dataset" of values of the ℓ-th layer.
138
Batch normalization (roughly)
Let us consider the ℓ-th layer with n neurons.
Consider a batch of training examples:
{(⃗xk , ⃗dk ) | k = 1, . . . , p}
(This is typically a minibatch.)
139
Batch normalization (roughly)
Let us consider the ℓ-th layer with n neurons.
Consider a batch of training examples:
{(⃗xk , ⃗dk ) | k = 1, . . . , p}
(This is typically a minibatch.)
▶ For every k = 1, . . . , p: Compute the values of neurons in
the ℓ-th layer for the input ⃗xk and obtain a vector
⃗zk = (zk1, . . . , zkn)
139
Batch normalization (roughly)
Let us consider the ℓ-th layer with n neurons.
Consider a batch of training examples:
{(⃗xk , ⃗dk ) | k = 1, . . . , p}
(This is typically a minibatch.)
▶ For every k = 1, . . . , p: Compute the values of neurons in
the ℓ-th layer for the input ⃗xk and obtain a vector
⃗zk = (zk1, . . . , zkn)
▶ Set all components of all vectors ⃗zk to the mean = 0 and
the variance = 1 and obtain normalized vectors: ˆz1, . . . , ˆzp.
139
Batch normalization (roughly)
Let us consider the ℓ-th layer with n neurons.
Consider a batch of training examples:
{(⃗xk , ⃗dk ) | k = 1, . . . , p}
(This is typically a minibatch.)
▶ For every k = 1, . . . , p: Compute the values of neurons in
the ℓ-th layer for the input ⃗xk and obtain a vector
⃗zk = (zk1, . . . , zkn)
▶ Set all components of all vectors ⃗zk to the mean = 0 and
the variance = 1 and obtain normalized vectors: ˆz1, . . . , ˆzp.
▶ For every k = 1, . . . , p give
⃗γ · ˆzk + ⃗δ
as the output of the ℓ-th layer instead of ⃗zk . Here ⃗γ and ⃗δ
are new trainable weights.
139
Generalization
140
Generalization
Intuition: Generalization = ability to cope with new unseen
instances.
Data are mostly noisy, so it is not good idea to fit exactly.
In case of function approximation, the network should not
return exact results as in the training set.
141
Generalization
Intuition: Generalization = ability to cope with new unseen
instances.
Data are mostly noisy, so it is not good idea to fit exactly.
In case of function approximation, the network should not
return exact results as in the training set.
More formally: It is typically assumed that the training set has
been generated as follows:
dkj = gj(⃗xk ) + Θkj
where gj is the "underlying" function corresponding to
the output neuron j ∈ Y and Θkj is random noise.
The network should fit gj not the noise.
Methods improving generalization are called regularization
methods.
141
Regularization
Regularization is a big issue in neural networks, as they
typically use a huge amount of parameters and thus are very
susceptible to overfitting.
142
Regularization
Regularization is a big issue in neural networks, as they
typically use a huge amount of parameters and thus are very
susceptible to overfitting.
von Neumann: "With four parameters I can fit an elephant,
and with five I can make him wiggle his trunk."
... and I ask you prof. Neumann:
What can you fit with 40GB of parameters??
142
Early stopping
Early stopping means that we stop learning before it reaches
a minimum of the error E.
When to stop?
143
Early stopping
Early stopping means that we stop learning before it reaches
a minimum of the error E.
When to stop?
In many applications the error function is not the main thing we
want to optimize.
E.g. in the case of a trading system, we typically want to maximize our profit
not to minimize (strange) error functions designed to be easily differentiable.
Also, as noted before, minimizing E completely is not good for
generalization.
For start: We may employ standard approach of training on one
set and stopping on another one.
143
Early stopping
Divide your dataset into several subsets:
▶ training set (e.g. 60%) – train the network here
▶ validation set (e.g. 20%) – use to stop the training
▶ test set (e.g. 20%) – use to evaluate the final model
What to use as a stopping rule?
144
Early stopping
Divide your dataset into several subsets:
▶ training set (e.g. 60%) – train the network here
▶ validation set (e.g. 20%) – use to stop the training
▶ test set (e.g. 20%) – use to evaluate the final model
What to use as a stopping rule?
You may observe E (or any other function of interest) on the
validation set, if it does not improve for last k steps, stop.
Alternatively, you may observe the gradient, if it is small for
some time, stop.
(some studies shown that this traditional rule is not too good: it may happen
that the gradient is larger close to minimum values; on the other hand, E
does not have to be evaluated which saves time.)
To compare models you may use ML techniques such as
various types of cross-validation etc.
144
Size of the network
Similar problem as in the case of the training duration:
▶ Too small network is not able to capture intrinsic properties
of the training set.
▶ Large networks overfit faster.
Solution: Optimal number of neurons :-)
145
Size of the network
Similar problem as in the case of the training duration:
▶ Too small network is not able to capture intrinsic properties
of the training set.
▶ Large networks overfit faster.
Solution: Optimal number of neurons :-)
▶ there are some (useless) theoretical bounds
▶ there are algorithms dynamically adding/removing neurons
(not much use nowadays)
▶ In practice: Start with an existing network solving similar
problem.
If you are trully desperate trying to solve a brand new problem, you may
try an ancient rule of thumb: the number of neurons ≈ ten times less
than the number of training instances.
Experiment, experiment, experiment.
145
Feature extraction
Consider a two-layer network. Hidden neurons are supposed to
represent "patterns" in the inputs.
Example: Network 64-2-3 for letter classification:
146
Ensemble methods
Techniques for reducing generalization error by combining
several models.
The reason that ensemble methods work is that different models will usually
not make all the same errors on the test set.
Idea: Train several different models separately, then have all of
the models vote on the output for test examples.
147
Ensemble methods
Techniques for reducing generalization error by combining
several models.
The reason that ensemble methods work is that different models will usually
not make all the same errors on the test set.
Idea: Train several different models separately, then have all of
the models vote on the output for test examples.
Bagging:
▶ Generate k training sets T1, ..., Tk by sampling from T
uniformly with replacement.
If the number of samples is |T |, then on average |Ti| = (1 − 1/e)|T |.
▶ For each i, train a model Mi on Ti.
▶ Combine outputs of the models: for regression by
averaging, for classification by (majority) voting.
147
Dropout
The algorithm: In every step of the gradient descent
▶ choose randomly a set N of neurons, each neuron is included
independently with probability 1/2,
(in practice, different probabilities are used as well).
▶ do forward and backward propagations only using the selected
neurons
(i.e. leave weights of the other neurons unchanged)
148
Dropout
The algorithm: In every step of the gradient descent
▶ choose randomly a set N of neurons, each neuron is included
independently with probability 1/2,
(in practice, different probabilities are used as well).
▶ do forward and backward propagations only using the selected
neurons
(i.e. leave weights of the other neurons unchanged)
Dropout resembles bagging: Large ensemble of neural networks is
trained "at once" on parts of the data.
Dropout is not exactly the same as bagging: The models share
parameters, with each model inheriting a different subset of
parameters from the parent neural network. This parameter sharing
makes it possible to represent an exponential number of models with
a tractable amount of memory.
In the case of bagging, each model is trained to convergence on its respective
training set. This would be infeasible for large networks/training sets.
148
Dropout – details
▶ The inner potential of a neuron j without dropout:
ξj =
i∈j←
wjiyi
▶ The inner potential of a neuron j with dropout:
ri ∼ Bernoulli(1/2) for all i ∈ j← ∖ {0}
ξj =
i∈j←
wji(riyi)
(Intuitively, randomly chosen neurons are masked out.)
▶ During inference do not drop out neurons and multiply
values of neurons with 1/2.
This compensates for the fact that without the drop out there are twice
as many neurons.
149
Weight decay and L2 regularization
Generalization can be improved by removing "unimportant" weights.
Penalising large weights gives stronger indication about their
importance.
150
Weight decay and L2 regularization
Generalization can be improved by removing "unimportant" weights.
Penalising large weights gives stronger indication about their
importance.
In every step we decrease weights (multiplicatively) as follows:
w
(t+1)
ji
= (1 − ζ)w
(t)
ji
− ε ·
∂E
∂wji
(⃗w(t)
)
Intuition: Unimportant weights will be pushed to 0, important weights
will survive the decay.
150
Weight decay and L2 regularization
Generalization can be improved by removing "unimportant" weights.
Penalising large weights gives stronger indication about their
importance.
In every step we decrease weights (multiplicatively) as follows:
w
(t+1)
ji
= (1 − ζ)w
(t)
ji
− ε ·
∂E
∂wji
(⃗w(t)
)
Intuition: Unimportant weights will be pushed to 0, important weights
will survive the decay.
Weight decay is equivalent to the gradient descent with a constant
learning rate ε and the following error function:
E′
(⃗w) = E(⃗w) +
ζ
2ε
(⃗w · ⃗w)
Here ζ
2ε (⃗w · ⃗w) is the L2 regularization that penalizes large weights.
We use the gradient descent with a constant learning rate to illustrate
the equivalence between L2 regularization and the weight decay. Both
methods can be combined with other learning algorithnms (AdaGrad, etc.).
150
More optimization, regularization ...
There are many more practical tips, optimization methods,
regularization methods, etc.
For a very nice survey see
http://www.deeplearningbook.org/
... and also all other infinitely many urls concerned with deep
learning.
151