Lecture 12: Neural Networks
1
2
Today
3
Recall: limitations to linear classifiers
4
0
1
+
-
| 0 | 1 |
0 | 0 | 0 |
1 | 0 | 1 |
x1
x2
-
-
AND
x2
x1
Limitations to linear classifiers
5
0
1
x2
+
-
| 0 | 1 |
0 | 0 | 1 |
1 | 1 | 1 |
x1
x1
x2
+
OR
+
Limitations to linear classifiers
6
0
1
| 0 | 1 |
0 | 1 | 0 |
1 | 0 | 1 |
x1
x
1
x2
XOR
| + - | |
No linear classifier can solve this [Papert & Minsky 1972] | ||
x2 | - + | |
“Classic” recognition without neural nets
Feature extractors
Edges
Texture
Colors
Segments
Parts
“clown fish”
Classifier
7
Source: Isola, Torralba, Freeman
(finite key of labels possible - 0, 1, 2, 3… - don’t think about natural language processing yet)
“Classic” recognition without neural nets
8
[Xiao et al., “SUN database”, 2010]
Hand-crafted features
edge orientation histogram
θ
“Classic” object recognition without neural nets
Edges
Texture
Colors
Segments
Parts
Learned
Feature extractors
“clown fish”
Classifier
Source: Isola, Torralba, Freeman
9
Object recognition
“clown fish”
Learned
Source: Isola, Torralba, Freeman
10
Object recognition
“clown fish”
Learned
Neural net
Source: Isola, Torralba, Freeman
11
Minsky and Papert, Perceptrons, 1972
12
Source: Isola, Torralba, Freeman
Perceptrons, 1958
time
enthusiasm
Minsky and Papert, 1972
13
Based on slide by: Isola, Torralba, Freeman
Parallel Distributed Processing (PDP), 1986
14
Source: Isola, Torralba, Freeman
Perceptrons, 1958
time
enthusiasm
Minsky and Papert, 1972
PDP book, 1986
15
Source: Isola, Torralba, Freeman
LeCun convolutional neural networks
16
Source: Isola, Torralba, Freeman
17
Source: Isola, Torralba, Freeman
Neural networks to recognize handwritten digits and human faces? yes
Neural networks for tougher problems?
not really
18
Source: Isola, Torralba, Freeman
Machine learning circa 2000
19
Source: Isola, Torralba, Freeman
Perceptrons, 1958
time
enthusiasm
Minsky and Papert, 1972
PDP book, 1986
Neural network winter, 2000
20
Source: Isola, Torralba, Freeman
Krizhevsky, Sutskever, and Hinton, NeurIPS 2012 “AlexNet”
21
Source: Isola, Torralba, Freeman
Krizhevsky, Sutskever, and Hinton, NeurIPS 2012
22
Source: Isola, Torralba, Freeman
28 years
time
enthusiasm
Perceptrons, 1958
Minsky and Papert, 1972
PDP book, 1986
Neural net winter, 2000
Krizhevsky, Sutskever, Hinton, 2012
28 years
?
23
Source: Isola, Torralba, Freeman
What comes next?
time
enthusiasm
Perceptrons, 1958
Minsky and Papert, 1972
PDP book, 1986
Neural net winter, 2000
Krizhevsky, Sutskever, Hinton, 2012
24
Source: Isola, Torralba, Freeman
What comes next?
time
enthusiasm
Perceptrons, 1958
Minsky and Papert, 1972
PDP book, 1986
AI winter, 2000
Krizhevsky, Sutskever, Hinton, 2012
28 years 28 years
25
Source: Isola, Torralba, Freeman
2028 ?
What comes next?
time
enthusiasm
Perceptrons, 1958
Minsky and Papert, 1972
PDP book, 1986
AI winter, 2000
Krizhevsky, Sutskever, Hinton, 2012
28 years 28 years
26
Source: Isola, Torralba, Freeman
2028 ?
Inspiration: Neurons
27
Image source: Khan academy
Inspiration: Hierarchical Representations
[Serre, 2014]
28
Source: Isola, Torralba, Freeman
Best to treat as inspiration. The neural nets we’ll talk about aren’t very biologically plausible.
Object recognition
29
“clown fish”
Neural network
Source: Isola, Torralba, Freeman
Computation in a neural net
30
Input vector
Output vector
Neuron (a.k.a unit)
Adapted from: Isola, Torralba, Freeman
Computation in a neural net
31
Output representation
Input representation
xi
Source: Isola, Torralba, Freeman
yj
wij
Linear layer
Computation in a neural net
32
Input representation
xi
Output representation
yj
wij
Linear layer
weights
bias
bj
Source: Isola, Torralba, Freeman
Computation in a neural net
33
yj = xT wj + bj
Input representation
Output representation
yj
Linear layer
weights
bias
wj
bj
parameters of the model
Source: Isola, Torralba, Freeman
Computation in a neural net
34
Input representation
Output representation
yj
Linear layer Full layer
weights
bias
wj
bj
parameters of the model
y = Wx + b
Computation in a neural net
35
Input representation
Output representation
yj
Linear layer Full layer
weights + bias
wj
bj
y = Wx
Can again simplify notation by appending a 1 to
What’s the problem with this idea?
36
W1x
x
W2W1x
W3W2W1x
Consider stacking multiple layers:
Can be expressed as single linear layer!
Limited power, e.g. can’t solve XOR.
Solution: simple nonlinearity
Input representation
Output representation
g(y)
y g(y)
b
1, if y > 0
0, otherwise
y
Pointwise Non-linearity
37
Source: Isola, Torralba, Freeman
Example: linear classification with a perceptron
y
38
x1
Source: Isola, Torralba, Freeman
x2
y = xT w + b
Example: linear classification with a perceptron
y
39
x1
Source: Isola, Torralba, Freeman
x2
y = xT w + b
g(y) =
1, if y > 0
0, otherwise
Example: linear classification with a perceptron
y
40
Source: Isola, Torralba, Freeman
x1
x2
y = xT w + b
g(y) =
1, if y > 0
0, otherwise
Computation in a neural net — nonlinearity
Input representation
Output representation
g(y)
y g(y)
b
g(y) =
1, if y > 0
0, otherwise
y
Can’t use with gradient descent,
41
Source: Isola, Torralba, Freeman
∂
∂y
g = 0
Computation in a neural net — nonlinearity
42
g(y)
y g(y)
b
y
Input representation
Output representation
Sigmoid
g(y) = c(y) =
1
1 + e-y
Source: Isola, Torralba, Freeman
Computation in a neural net — nonlinearity
43
g(y)
y
Sigmoid
1
g(y) = (y) =
1 + e-y
Source: Isola, Torralba, Freeman
Computation in a neural net — nonlinearity
44
y
Rectified linear unit (ReLU)
g(y) = max(0, y)
g(y)
Source: Isola, Torralba, Freeman
Computation in a neural net — nonlinearity
45
g(y)
y
Leaky ReLU
g(y) =
Source: Isola, Torralba, Freeman
Deep nets
“clown fish”
Linear
Non-linearity
…
f (x) = fL(. . . f2(f1(x)))
46
Source: Isola, Torralba, Freeman
Linear
Softmax
Stacking layers
47
Output representation
y
b(2)
j
W(2)
j
Input representation
Intermediate representation
h
b(1)
j
W(1)
Source: Isola, Torralba, Freeman
j
h = “hidden units”
Stacking layers
48
Input representation
Intermediate representation
Output representation
h
y
W(1)
Source: Isola, Torralba, Freeman
W(2)
b(1)
b(2)
= {W(1),..., W(L), b(1), . . . , b(L)}
h = g(W(1)x + b(1))
y = W(2)h + b(2)
Stacking layers
49
Input representation
Intermediate representation
Output representation
h
y
W(1)
Source: Isola, Torralba, Freeman
W(2)
b(1)
b(2)
positive
negative
= {W(1),..., W(L), b(1), . . . , b(L)}
h = g(W(1)x + b(1))
y = W(2)h + b(2)
Stacking layers
50
Input representation
Intermediate representation
Output representation
h
y
W(1)
Source: Isola, Torralba, Freeman
W(2)
b(1)
b(2)
positive
negative
= {W(1),..., W(L), b(1), . . . , b(L)}
h = g(W(1)x + b(1))
y = W(2)h + b(2)
Stacking layers
51
Input representation
Intermediate representation
Output representation
h
y
W(1)
Source: Isola, Torralba, Freeman
W(2)
b(1)
b(2)
positive
negative
= {W(1),..., W(L), b(1), . . . , b(L)}
h = g(W(1)x + b(1))
y = W(2)h + b(2)
Stacking layers
52
Input representation
Intermediate representation
Output representation
h
y
W(1)
Source: Isola, Torralba, Freeman
W(2)
b(1)
b(2)
positive
negative
= {W(1),..., W(L), b(1), . . . , b(L)}
h = g(W(1)x + b(1))
y = W(2)h + b(2)
Connectivity patterns
53
Input representation
Output representation
W(1)
y
Fully connected layer
Locally connected layer (Sparse W)
Input representation
W(1)
Output representation
y
Source: Isola, Torralba, Freeman
Computation has a simple form
y = W(n)g(W(n-1) . . . g(W(3)g(W(2)(g(W(1)x)))))
Deep learning
y1
“clown fish”
Loss
Learned
x1
55
Source: Isola, Torralba, Freeman
Batch processing
56
Loss
Loss
Loss
…
⌃
| | | | |
Images
Features
Vectorized code is often much more efficient. Often you’ll operate on whole minibatch at once.
Source: Isola, Torralba, Freeman
Tensors
(multi-dimensional arrays)
57
…
Furry?
Is a fish?
Size
# Stripes
…
Each layer is a representation of the data
Source: Isola, Torralba, Freeman
Tensors
58
…
Nbatch
(multi-dimensional arrays)
C(1)
Source: Isola, Torralba, Freeman
Tensors
(multi-dimensional arrays)
59
Nbatch
C(1)
Source: Isola, Torralba, Freeman
Tensors
60
Nbatch
C(1)
C(2)
Nbatch
Source: Isola, Torralba, Freeman
(multi-dimensional arrays)
Representational power
– Simple proof by M. Nielsen
http://neuralnetworksanddeeplearning.com/chap4.html
61
Source: Isola, Torralba, Freeman
Example: perceptron
x1
x2
y
y = σ(W(1)x)
x2
x1
Example source: http://playground.tensorflow.org
62
Example: multilayer perceptron (MLP)
x1
x2
y
y = σ(W(2) max(0, W(1)x))
x2
x1
Example source: http://playground.tensorflow.org
63
Example: multilayer perceptron (MLP)
x2
x1
4 “hidden” units
Example source: http://playground.tensorflow.org
64
2D vector
Example: multilayer perceptron (MLP)
x2
x1
4 “hidden” units
2D vector
What does this unit do?
Example source: http://playground.tensorflow.org
65
How do we learn the parameters?
y1
“clown fish”
Loss
Learned
x1
Source: Isola, Torralba, Freeman
Learning parameters
Squared loss with single-variable network:
67
Example source: Roger Grosse
Learning parameters
Want: derivatives
Squared loss with single-variable network:
x
y
68
Example source: Roger Grosse
Learning parameters
Writing out the layers explicitly:
z = wx + b
t = σ(z)
2
L = 1 (y − t)2
How do we do this? Use the chain rule!
Example source: Roger Grosse
69
Computing derivatives with the chain rule
Example source: Roger Grosse
70
Limitations to this approach
71