An Introduction to

Neural Nets & Deep Learning

Slides by Rajesh Rao, Hung-yi Lee,
Ismini Lourentzou, Noah Smith
The human brain is extremely
good at classifying images
Can we develop classification methods by
emulating the brain?

2
Brain Computer: What is it?

Human brain contains a

massively
interconnected net of
1010-1011 (10 billion)
neurons (cortical cells)

Biological Neuron
- The simple “arithmetic
computing” element

3
Neurons communicate via spikes

Inputs

Output spike
(electrical pulse)

Output spike roughly dependent on whether

sum of all inputs reaches a threshold
6
 Neurons as “Threshold Units”
• Artificial neuron:
• m binary inputs (-1 or 1), 1 output (-1 or 1)
• Synaptic weights wji
• Threshold i
Non-linearity
w1i Weighted Sum Threshold

Inputs uj w2i Output vi

(-1 or +1)
w3i (-1 or +1)

vi  ( w jiu j  i )
j

(x) = 1 if7 x > 0 and -1 if x  0

 “Perceptrons” for Classification
• Fancy name for a type of layered “feed-forward”
networks (no loops)

• Uses artificial neurons (“units”) with binary inputs and

outputs
Multilayer

Single-layer

8
Perceptrons and Classification
• Consider a single-layer perceptron
• Weighted sum forms a linear hyperplane

w u
j
ji j  i  0
• Everything on one side of this hyperplane is in class 1
(output = +1) and everything on other side is class 2 (output
= -1)
• Any function that is linearly separable can be
computed by a perceptron

9
Linear Separability
• Example: AND is linearly separable
Linear hyperplane
u1 u2 AND
-1 -1 -1 u2
(1,1) v
1 -1 -1 1  = 1.5
-1 1 -1
u1
1 1 1 -1 1

-1 u1 u2

v = 1 iff u1 + u2 – 1.5 > 0

Similarly for OR and NOT

10
What about the XOR function?
u1 u2 XOR ?
u2
-1 -1 1 (1,1)
1
1 -1 -1 1
u1
-1 1 -1 -1
1 1 1 -1

Can a perceptron separate the +1

outputs from the -1 outputs?

11
Linear Inseparability
• Perceptron with threshold units fails if classification
task is not linearly separable
• Example: XOR
• No single line can separate the “yes” (+1)
outputs from the “no” (-1) outputs!

u2
(1,1)
Minsky and Papert’s book 1
showing such negative
results put a damper on
X 1
u1
neural networks research -1
for over a decade! -1

12
How do we deal with
linear inseparability?

13
 Idea 1: Multilayer Perceptrons
• Removes limitations of single-layer networks
• Can solve XOR
• Example: Two-layer perceptron that computes XOR

x y
• Output is +1 if and only if x + y – 2(x + y – 1.5) – 0.5 > 0

14
Multilayer Perceptron: What does it do?
out
y
2
1 1
1

?

2

1
1 2
2 1
1
1 1
1
x y
x
1 2

15
Multilayer Perceptron: What does it do?
out y 1 =-1
1 x  y  0
2 2
=1
1
1 x  y  0
y  1
1
x 2
1 2
1
2 1
1
1
x y
x
1 2

16
Multilayer Perceptron: What does it do?
out
y =-1
2
=1

1
2
1 =1 =-1
1
1 2 x y  0 2 x y  0
x y
x
1 2

17
Multilayer Perceptron: What does it do?

y =-1
out
2
=1
1 1
1
 1
2 -  >0
1 2

=1 =-1

1
x y x
1 2

18
 Idea 2: Activation functions
Non-linearities needed to learn complex (non-linear) representations of data,
otherwise the NN would be just a linear function W1 W2 𝑥 = 𝑊𝑥

[Link]

More layers and neurons can approximate more complex functions

Full list: [Link]

Activation Functions
Linear activation Logistic activation

  z  z   z 
1
1  e  z

1
Σ z
z
0
Threshold Hyperbolic tangent activation
ReLU activation
1  e 2u
 1, if
  z   sign( z )  
z  0,
 u   tanhu  
1, if z  0. 1  e 2u

1
1

-1
z 0 z
-1
20
 Activation: Sigmoid
Takes a real-valued number and
“squashes” it into range between 0 and
1.
𝑅𝑛 → 0,1

[Link]

+ Nice interpretation as the firing rate of a neuron

• 0 = not firing at all
• 1 = fully firing

- Sigmoid neurons saturate and kill gradients, thus NN will barely learn
• when the neuron’s activation are 0 or 1 (saturate)
� gradient at these regions almost zero
� almost no signal will flow to its weights
� if initial weights are too large then most neurons would saturate
 Activation: Tanh
Takes a real-valued number and
“squashes” it into range between -1
and 1.
𝑅𝑛 → −1,1

[Link]

- Like sigmoid, tanh neurons saturate

- Unlike sigmoid, output is zero-centered
- Tanh is a scaled sigmoid: tanh 𝑥 = 2𝑠𝑖𝑔𝑚 2𝑥 − 1
 Activation: ReLU
Takes a real-valued number and
thresholds it at zero f 𝑥 = max(0, 𝑥)

𝑅𝑛 → 𝑅+𝑛

[Link]

Most Deep Networks use ReLU nowadays

� Trains much faster

• accelerates the convergence of SGD
• due to linear, non-saturating form
� Less expensive operations
• compared to sigmoid/tanh (exponentials etc.)
• implemented by simply thresholding a matrix at zero
� More expressive
� Reduces the gradient vanishing problem
Example Application
• Handwriting Digit Recognition

Machine “2”
Handwriting Digit Recognition

Input Output

y1
0.1 is 1
x1
x2 y2
0.7 is 2
The image
is “2”

……
……
……

x256 y10
0.2 is 0
16 x 16 = 256
Ink → 1 Each dimension represents
No ink → 0 the confidence of a digit.
Example Application
• Handwriting Digit Recognition

x1 y1
x2
y2
Machine “2”
……

……
x256 256 10 y10
𝑓: 𝑅 →𝑅
In deep learning, the function 𝑓 is
represented by neural network
Element of Neural Network
Neuron 𝑓: 𝑅 𝐾 → 𝑅

a1 w1 z  a1w1  a2 w2    aK wK  b

a2 w2
z  z 
 a
wK
…

aK weights
Activation
function
b
bias
Neural Network
neuron
Input Layer 1 Layer 2 Layer L Output
x1 …… y1
x2 …… y2

……
……

……

……

……
xN …… yM
Input Output
Layer Hidden Layers Layer

Deep means many hidden layers

Example of Neural Network
1 4 0.98
1
-2
1
-1 -2 0.12
-1
1
0
Sigmoid Function  z 
1
 z   z
1 e z
Example of Neural Network
1 4 0.98 2 0.86 3 0.62
1
-2 -1 -1
1 0 -2
-1 -2 0.12 -2 0.11 -1 0.83
-1
1 -1 4
0 0 2
 Example of Neural Network
1 0.73 2 0.72 3 0.51
0
-2 -1 -1
1 0 -2
-1 0.5 -2 0.12 -1 0.85
0
1 -1 4
0 0 2

𝑓: 𝑅 2 → 𝑅 2 1 0.62 0 0.51
𝑓 = 𝑓 =
−1 0.83 0 0.85
Different parameters define different function
Matrix Operation
1 4 0.98
1 y1
-2
1
-1 -2 0.12
-1 y2
1
0

𝜎 1 −2 1 +
1 = 0.98
−1 1 −1 0 0.12
4
−2
 Neural Network
x1 …… y1
x 2 W1 W2 ……
WL y2
b1 b2 bL

……
……

……

……

……
xN x a1 ……
a2 y yM

𝜎 W1 x + b1
𝜎 W2 a1 + b2
𝜎 WL aL-1 + bL
 Neural Network
x1 …… y1
x 2 W1 W2 ……
WL y2
b1 b2 bL

……
……

……

……

……
xN x a1 ……
a2 y yM

Using parallel computing techniques

y =𝑓 x
to speed up matrix operation

=𝜎 WL …𝜎 W2 𝜎 W1 x + b1 + b2 … + bL
 Softmax
• Softmax layer as the output layer

Ordinary Layer

z1   
y1   z1
In general, the output of
z2   
y2   z 2
network can be any value.

May not be easy to interpret

z3   
y3   z 3
 Softmax
Probability:
• Softmax layer as the output layer  1 > 𝑦𝑖 > 0
 𝑖 𝑦𝑖 = 1
Softmax Layer

3 0.88 3

e
20
z1 e e z1
 y1  e z1 zj

j 1

1 0.12 3
z2 e e z 2 2.7
 y2  e z2
e
zj

j 1
0.05 ≈0 3
z3 -3 
e
e
z3 zj
e y3  e z3

3 j 1

 e zj

j 1
 How to set network parameters
𝜃 = 𝑊 1 , 𝑏1 , 𝑊 2 , 𝑏 2 , ⋯ 𝑊 𝐿 , 𝑏 𝐿
x1 …… y1
0.1 is 1

x2

Softmax
…… y2
0.7 is 2
……

……

……
x256 …… y10
0.2 is 0
16 x 16 = 256
Ink → 1 Set the network parameters 𝜃 such that ……
No ink → 0
Input: How to let thethe
y1 has neural
maximum value
network achieve this
Input: y2 has the maximum value
Training Data
• Preparing training data: images and their labels

“5” “0” “4” “1”

“9” “2” “1” “3”

Using the training data to find

the network parameters.
 Given a set of network parameters 𝜃,
Cost each example has a cost value.

“1”

x1 …… y0.2
1 1
x2 …… y2
0.3 0
Cost
……

……
……

……

……
x256 …… y0.5 𝐿(𝜃) 0
10

target
Cost can be Euclidean distance or cross
entropy of the network output and target
Total Cost
For all training data … Total Cost:
𝑅
x1 NN 𝑦1 y1
𝐶 𝜃 = 𝐿𝑟 𝜃
𝐿1 𝜃
𝑟=1
x2 NN 𝑦2 y2
𝐿2 𝜃 How bad the network
parameters 𝜃 is on
x3 NN 𝑦3 y3
this task
𝐿3 𝜃
……
……

……
……

Find the network

parameters 𝜃 ∗ that
xR NN 𝑦𝑅 yR
minimize this value
𝐿𝑅 𝜃
 Assume there are only two
parameters w1 and w2 in a
Gradient Descent network.
Error Surface 𝜃 = 𝑤1 , 𝑤2

The colors represent the value of C. Randomly pick a

starting point 𝜃 0
Compute the
negative gradient
𝑤2 𝜃∗ at 𝜃 0
−𝜂𝛻𝐶 𝜃 0 −𝛻𝐶 𝜃 0
−𝛻𝐶 𝜃 0 Times the
𝜕𝐶 𝜃 0 /𝜕𝑤1 learning rate 𝜂
𝜃0 𝛻𝐶 𝜃 0 =
𝜕𝐶 𝜃 0 /𝜕𝑤2 −𝜂𝛻𝐶 𝜃 0
𝑤1
 Gradient Descent
Eventually, we would
Randomly pick a
reach a minima …..
starting point 𝜃 0
Compute the
2−𝜂𝛻𝐶 𝜃2 negative gradient
−𝜂𝛻𝐶 𝜃 1𝜃
𝑤2 2 at 𝜃 0
−𝛻𝐶
−𝛻𝐶 𝜃1 𝜃
𝜃1 −𝛻𝐶 𝜃 0
Times the
learning rate 𝜂
𝜃0
−𝜂𝛻𝐶 𝜃 0
𝑤1
 Local Minima
• Gradient descent never guarantee global minima
Different initial
point 𝜃 0

𝐶 Reach different minima,

so different results
Who is Afraid of Non-Convex
Loss Functions?
𝑤1 𝑤2 [Link]
_lecun_wia/
Besides local minima ……
cost
Very slow at the
plateau
Stuck at saddle point

Stuck at local minima

𝛻𝐶 𝜃 𝛻𝐶 𝜃 𝛻𝐶 𝜃
≈0 =0 =0
parameter space
 Mini-batch
 Randomly initialize 𝜃 0
x1 NN y1 𝑦1  Pick the 1st batch
Mini-batch

𝐿1 𝐶 = 𝐿1 + 𝐿31 + ⋯
x31 NN y31 𝑦 31 𝜃1 ← 𝜃 0 − 𝜂𝛻𝐶 𝜃 0
𝐿31  Pick the 2nd batch
……

𝐶 = 𝐿2 + 𝐿16 + ⋯
𝜃 2 ← 𝜃1 − 𝜂𝛻𝐶 𝜃1
x2 NN y2 𝑦2
Mini-batch

…
𝐿2
C is different each time
x16 NN y16 𝑦16 when we update
𝐿16 parameters!
……
SGD vs. GD
Convergence curves
• GD: O(1/t2), SGD: O(1/sqrt(t))
 Mini-batch Faster Better!
 Randomly initialize 𝜃 0
x1 NN y1 𝑦1  Pick the 1st batch
Mini-batch

𝐶1 𝐶 = 𝐶 1 + 𝐶 31 + ⋯
x31 NN y31 𝑦 31 𝜃1 ← 𝜃 0 − 𝜂𝛻𝐶 𝜃 0
𝐶 31  Pick the 2nd batch
……

𝐶 = 𝐶 2 + 𝐶 16 + ⋯
𝜃 2 ← 𝜃1 − 𝜂𝛻𝐶 𝜃1
x2 NN y2 𝑦2
Mini-batch

…
𝐶2  Until all mini-batches
have been picked
x16 NN y16 𝑦16
𝐶 16 one epoch
……

Repeat the above process

 Backpropagation:
Computing Gradients
• If we choose a differentiable loss, then the the whole
function will be differentiable with respect to all parameters.
• Because of non-linear activations whose combination is not
convex, the overall learning problem is not convex.
• What does (stochastic) (sub)gradient descent do with non-
convex functions? It finds a local minimum.
• To calculate gradients, we need to use the chain rule from
calculus.
• Special name for (S)GD with chain rule invocations:
backpropagation.
Backpropagation
Backpropagation
Backpropagation
Backpropagation
Backpropagation
Backpropagation
Backpropagation
Backpropagation
Backpropagation
Backpropagation
Derivative w.r.t. Matrix Multiplication
𝑤11 𝑤12 𝑤13 𝑥1 𝑤11 𝑥1 + 𝑤12 𝑥2 + 𝑤13 𝑥3 𝑑1
𝑤21 𝑤22 𝑤23 𝑥2 = 𝑤21 𝑥1 + 𝑤22 𝑥2 + 𝑤23 𝑥3 = 𝑑2
𝑤31 𝑤32 𝑤33 𝑥3 𝑤31 𝑥1 + 𝑤32 𝑥2 + 𝑤33 𝑥3 𝑑3

wij only influences di

𝜕𝑑𝑖
= 𝑥𝑗
𝜕𝑤𝑖𝑗
If we are given 𝑑

𝑑1 𝑥1 𝑑1 𝑥2 𝑑1 𝑥3 𝑑1
𝜕𝐿
= 𝑑2 𝑥1 𝑑2 𝑥2 𝑑2 𝑥3 = 𝑑2 𝑥1 𝑥2 𝑥3 = 𝑑𝑥 𝑇
𝜕𝑊
𝑑3 𝑥1 𝑑3 𝑥2 𝑑3 𝑥3 𝑑3
Backpropagation
 Part II:
Why Deep?
Deeper is Better?
Word Error Word Error
Layer X Size Layer X Size
Rate (%) Rate (%)
1 X 2k 24.2
2 X 2k 20.4 Not surprised, more
3 X 2k 18.4 parameters, better
4 X 2k 17.8 performance
5 X 2k 17.2 1 X 3772 22.5
7 X 2k 17.1 1 X 4634 22.6
1 X 16k 22.1
Seide, Frank, Gang Li, and Dong Yu. "Conversational Speech Transcription
Using Context-Dependent Deep Neural Networks." Interspeech. 2011.
Universality Theorem
Any continuous function f

f : R N  RM
Can be realized by a network
with one hidden layer
Reference for the reason:
(given enough hidden [Link]
neurons) [Link]/[Link]

Why “Deep” neural network not “Fat” neural network?

Fat + Short v.s. Thin + Tall
The same number
of parameters

Which one is better?

……

x1 x2 …… xN x1 x2 …… xN

Shallow Deep
Fat + Short v.s. Thin + Tall
Word Error Word Error
Layer X Size Layer X Size
Rate (%) Rate (%)
1 X 2k 24.2
2 X 2k 20.4
3 X 2k 18.4
4 X 2k 17.8
5 X 2k 17.2 1 X 3772 22.5
7 X 2k 17.1 1 X 4634 22.6
1 X 16k 22.1
Seide, Frank, Gang Li, and Dong Yu. "Conversational Speech Transcription
Using Context-Dependent Deep Neural Networks." Interspeech. 2011.
Why Deep?
• Deep → Modularization
Classifier Girls with
1 long hair

Classifier Boys with

2 long hair
Image
weak Little examples
Classifier Girls with
3 short hair

Classifier Boys with

4 short hair
 Why Deep? Each basic classifier can have
sufficient training examples.

• Deep → Modularization

Boy or Girl?

Image Basic
Classifier
Long or
short?

Classifiers for the

attributes
 Why Deep?
can be trained by little data

• Deep → Modularization
Classifier Girls with
1 long hair
Boy or Girl? Classifier Boys with
2 fine long Little
hair data
Image Basic
Classifier Classifier Girls with
Long or 3 short hair
short?
Classifier Boys with
Sharing by the 4 short hair
following classifiers
as module
Traditional ML vs. Deep Learning
Most machine learning methods work well because of human-designed
representations and input features
ML becomes just optimizing weights to best make a final prediction
 What is Deep Learning (DL) ?
A machine learning subfield of learning representations of data. Exceptional effective
at learning patterns.
Deep learning algorithms attempt to learn (multiple levels of) representation by using
a hierarchy of multiple layers
If you provide the system tons of information, it begins to understand it and respond
in useful ways.

[Link]
 Part III:
Convolutional Neural Nets
Feature Learning

Unlabeled images

Learning
algorithm

Feature representation
Convolution

5x5 input. 3x3 filter/kernel/feature detector. 3x3

convolved feature/
Multiple filters

Original image
Features at successive convolutional layers

+/- 45 degree
edges in Layer 1

Corners and other edge color conjunctions in Layer 2

Visualizing and Understanding Convolutional Networks,

Matthew D. Zeiler and Rob Fergus, ECCV 2014
Features at successive convolutional layers

More complex invariances than Layer 2. Similar textures e.g. mesh patterns (R1C1); Text (R2C4).

Visualizing and Understanding Convolutional Networks,

Matthew D. Zeiler and Rob Fergus, ECCV 2014
Features at successive convolutional layers

Significant variation, more class specific. Entire objects with significant pose variation.
Dog faces (R1C1); Bird legs (R4C2). Keyboards (R1C1); dogs (R4).

Visualizing and Understanding Convolutional Networks,

Matthew D. Zeiler and Rob Fergus, ECCV 2014
Max pooling
CNN architecture
Object Recognition

123