1 of 71

Lecture 12: Neural Networks

1

2 of 71

2

  • Section this week: machine learning
  • Reading:
    • Szeliski 5.3
    • Goodfellow Deep Feedforward Networks
  • Start thinking about project

3 of 71

Today

3

  • Brief history of neural networks
  • Computation in neural networks
  • Multi-layer perceptrons (for PS4)
  • Estimating gradients (to be continued next class).

4 of 71

Recall: limitations to linear classifiers

4

0

1

+

-

​

0

1

0

0

0

1

0

1

x1

x2

-

-

AND

x2

x1

5 of 71

Limitations to linear classifiers

5

0

1

x2

+

-

​

0

1

0

0

1

1

1

1

x1

x1

x2

+

OR

+

6 of 71

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

- +

​

7 of 71

“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)

8 of 71

“Classic” recognition without neural nets

8

[Xiao et al., “SUN database”, 2010]

Hand-crafted features

edge orientation histogram

θ

9 of 71

“Classic” object recognition without neural nets

Edges

Texture

Colors

Segments

Parts

Learned

Feature extractors

“clown fish”

Classifier

Source: Isola, Torralba, Freeman

9

10 of 71

Object recognition

“clown fish”

Learned

Source: Isola, Torralba, Freeman

10

11 of 71

Object recognition

“clown fish”

Learned

Neural net

Source: Isola, Torralba, Freeman

11

12 of 71

Minsky and Papert, Perceptrons, 1972

12

Source: Isola, Torralba, Freeman

13 of 71

Perceptrons, 1958

time

enthusiasm

Minsky and Papert, 1972

13

Based on slide by: Isola, Torralba, Freeman

14 of 71

Parallel Distributed Processing (PDP), 1986

14

Source: Isola, Torralba, Freeman

15 of 71

Perceptrons, 1958

time

enthusiasm

Minsky and Papert, 1972

PDP book, 1986

15

Source: Isola, Torralba, Freeman

16 of 71

LeCun convolutional neural networks

16

Source: Isola, Torralba, Freeman

17 of 71

17

Source: Isola, Torralba, Freeman

18 of 71

Neural networks to recognize handwritten digits and human faces? yes

Neural networks for tougher problems?

not really

18

Source: Isola, Torralba, Freeman

19 of 71

Machine learning circa 2000

19

Source: Isola, Torralba, Freeman

  • Neural Information Processing Systems (NeurIPS), is a top conference on machine learning.
  • For the 2000 conference:
    • title words predictive of paper acceptance: “Belief Propagation” and “Gaussian”.
    • title words predictive of paper rejection: “Neural” and “Network”.

20 of 71

Perceptrons, 1958

time

enthusiasm

Minsky and Papert, 1972

PDP book, 1986

Neural network winter, 2000

20

Source: Isola, Torralba, Freeman

21 of 71

Krizhevsky, Sutskever, and Hinton, NeurIPS 2012 “AlexNet”

21

Source: Isola, Torralba, Freeman

22 of 71

Krizhevsky, Sutskever, and Hinton, NeurIPS 2012

22

Source: Isola, Torralba, Freeman

23 of 71

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

24 of 71

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

25 of 71

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 ?

26 of 71

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 ?

27 of 71

Inspiration: Neurons

27

Image source: Khan academy

28 of 71

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.

29 of 71

Object recognition

29

“clown fish”

Neural network

Source: Isola, Torralba, Freeman

30 of 71

Computation in a neural net

30

Input vector

Output vector

Neuron (a.k.a unit)

Adapted from: Isola, Torralba, Freeman

31 of 71

Computation in a neural net

31

Output representation

Input representation

xi

Source: Isola, Torralba, Freeman

yj

wij

Linear layer

32 of 71

Computation in a neural net

32

Input representation

xi

Output representation

yj

wij

Linear layer

weights

bias

bj

Source: Isola, Torralba, Freeman

33 of 71

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

34 of 71

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

35 of 71

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

36 of 71

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.

37 of 71

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

38 of 71

Example: linear classification with a perceptron

y

38

x1

Source: Isola, Torralba, Freeman

x2

y = xT w + b

39 of 71

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

40 of 71

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

41 of 71

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

42 of 71

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

43 of 71

Computation in a neural net — nonlinearity

43

g(y)

y

Sigmoid

  • Interpretation as firing rate of neuron
  • Bounded between [0,1]
  • Saturation for large +/- inputs
  • Gradients go to zero
  • Centered at 0.5. Better in practice to use: tanh(y) = 2g(y) − 1

1

g(y) = (y) =

1 + e-y

Source: Isola, Torralba, Freeman

44 of 71

Computation in a neural net — nonlinearity

44

y

Rectified linear unit (ReLU)

g(y) = max(0, y)

  • Unbounded output (on positive side)
  • Efficient to implement:
  • Also seems to help convergence (6x speedup vs. tanh in [Krizhevsky et al. 2012])

g(y)

  • Drawback: if strongly in negative region, unit is dead forever (no gradient).
  • Default choice: widely used in current models!

Source: Isola, Torralba, Freeman

45 of 71

Computation in a neural net — nonlinearity

45

  • Has non-zero gradients everywhere (unlike ReLU)

g(y)

y

Leaky ReLU

  • where α is small (e.g., 0.02)
  • Efficient to implement:

g(y) =

Source: Isola, Torralba, Freeman

46 of 71

Deep nets

“clown fish”

Linear

Non-linearity

…

f (x) = fL(. . . f2(f1(x)))

46

Source: Isola, Torralba, Freeman

Linear

Softmax

47 of 71

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”

48 of 71

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)

49 of 71

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)

50 of 71

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)

51 of 71

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)

52 of 71

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)

53 of 71

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

54 of 71

Computation has a simple form

y = W(n)g(W(n-1) . . . g(W(3)g(W(2)(g(W(1)x)))))

​

  • Composition of linear functions with nonlinearities in between
  • For example, matrix multiplications with ReLU, max(0, x) afterwards
  • Do a matrix multiplication, set all negative values to 0, repeat

55 of 71

Deep learning

y1

“clown fish”

Loss

Learned

x1

55

Source: Isola, Torralba, Freeman

56 of 71

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

57 of 71

Tensors

(multi-dimensional arrays)

57

…

Furry?

Is a fish?

Size

# Stripes

…

Each layer is a representation of the data

Source: Isola, Torralba, Freeman

58 of 71

Tensors

58

​

​

​

​

​

​

​

​

…

Nbatch

(multi-dimensional arrays)

C(1)

Source: Isola, Torralba, Freeman

59 of 71

Tensors

(multi-dimensional arrays)

59

Nbatch

C(1)

Source: Isola, Torralba, Freeman

60 of 71

Tensors

60

Nbatch

C(1)

C(2)

Nbatch

Source: Isola, Torralba, Freeman

(multi-dimensional arrays)

61 of 71

Representational power

  • 1 layer? Linear decision surface.
  • 2+ layers? In theory, can represent any function!

– Simple proof by M. Nielsen

http://neuralnetworksanddeeplearning.com/chap4.html

  • But issue is efficiency: very wide two layers vs narrow deep model? In practice, more layers helps.

61

Source: Isola, Torralba, Freeman

62 of 71

Example: perceptron

x1

x2

y

y = σ(W(1)x)

x2

x1

62

63 of 71

Example: multilayer perceptron (MLP)

x1

x2

y

y = σ(W(2) max(0, W(1)x))

x2

x1

63

64 of 71

Example: multilayer perceptron (MLP)

x2

x1

4 “hidden” units

64

2D vector

65 of 71

Example: multilayer perceptron (MLP)

x2

x1

4 “hidden” units

2D vector

What does this unit do?

65

66 of 71

How do we learn the parameters?

y1

“clown fish”

Loss

Learned

x1

Source: Isola, Torralba, Freeman

67 of 71

Learning parameters

Squared loss with single-variable network:

67

Example source: Roger Grosse

68 of 71

Learning parameters

​

Want: derivatives

Squared loss with single-variable network:

x

y

68

Example source: Roger Grosse

69 of 71

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

70 of 71

Computing derivatives with the chain rule

Example source: Roger Grosse

70

71 of 71

Limitations to this approach

  • Inefficient! Lots of redundant computation

​

  • We’ll also need to extend this to multivariable functions

​

  • Next lecture: backpropagation

71