1 of 113

1

EC 500 A1: �Foundation of learning - 2

2 of 113

Today

  • Recap
  • Gradient-based learning algorithms
  • Generalization
  • Neural networks
  • Why are neural networks powerful?
  • CNN Revisit & Extensions

​

​

2

3 of 113

Example: image classification (ideal case)

3

Dog

Bird

Neural Network

(encoder)

Feature vector

……

Has four legs

Has wing

 

 

 

……

1

0

 

……

0

1

 

4 of 113

Example: image classification (training)

4

 

Dog

Neural Network

(encoder)

Feature vector

……

……

……

 

 

 

Bird

?

 

5 of 113

Case study – 2: classification

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

 

 

 

……

6 of 113

Case study – 2: classification

  • One-hot coding for y:

​

​

​

​

  • 0-1 loss:

​

  • Cross-entropy loss:

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

……

7 of 113

Case study – 2: classification

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

8 of 113

Basic gradient descent

  • The goal:

​

  • Pseudo-code:

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

9 of 113

Surrogate loss function

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

10 of 113

10

Questions?

11 of 113

Today

  • Recap
  • Gradient-based learning algorithms
  • Generalization
  • Neural networks
  • Why are neural networks powerful?
  • CNN Revisit & Extensions

​

​

11

12 of 113

Stochastic gradient descent (SGD)

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

13 of 113

Stochastic gradient descent (SGD)

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

14 of 113

Modern optimizers

15 of 113

“Homework” for you

  • Google or ask ChatGPT about:
    • Multi-layer perceptron
    • Backpropagation
    • PyTorch
    • GitHub
    • Hugging Face

​

​

16 of 113

Today

  • Recap
  • Gradient-based learning algorithms
  • Generalization
  • Neural networks
  • Why are neural networks powerful?
  • CNN Revisit & Extensions

​

​

16

17 of 113

Empirical risk minimization (ERM)

  • How can we learn f from (input, output) data pairs ?

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

 

18 of 113

Training vs. testing

  • Models learned from the training data should be applicable to test data

18

 

 

x

y

In training, we only see training data!

Choosing a more complicated hypothesis class does not necessarily lead to lower test errors!

19 of 113

Under-fitting vs. over-fitting

  • Background: polynomial regression

20 of 113

Under-fitting vs. over-fitting

  • Training data are generated from a sin function + noise
    • Under-fitting

K too small: simple

​

​

​

​

​

​

    • Over-fitting

K too large: complicated

training error = 0

20

[Slides: from USC CSCI567]

 

 

 

21 of 113

Under-fitting vs. over-fitting

  • Training data are generated from a sin function + noise
    • Just good enough

​

​

​

​

​

​

21

[Slides: from USC CSCI567]

 

22 of 113

Under-fitting vs. over-fitting

  • Over-fitting:
    • Small training error
    • Large test error (even larger than some other “simpler” models)

​

  • How to quantify hypothesis class’ complexity?
    • Polynomial regression: larger K, larger complexity

​

  • How to choose K?

​

​

​

 

23 of 113

 

Training data

Train

Val

Treating “Val” as the “pseudo” test data!

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

Data distribution

24 of 113

24

Questions?

25 of 113

Regularization

  • Searching for “simpler” solution

 

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

26 of 113

Finding a good regularizer is not always easy

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

27 of 113

Occam’s razor principle

27

All things being equal,

the simplest explanation is usually the best!

28 of 113

Three tools in the search for Truth

  • Data: what we observe

​

  • Prior: what we prefer & believe

​

  • Hypotheses: what the true function may be

​

​

29 of 113

More data, less over-fitting

 

 

 

[Figure: Bishop, PRML]

Green: true data distribution

Blue: training data

Red: learned model

30 of 113

30

Questions?

31 of 113

Today

  • Recap
  • Gradient-based learning algorithms
  • Generalization
  • Neural networks
  • Why are neural networks powerful?
  • CNN Revisit & Extensions

​

​

31

32 of 113

The progress of deep learning for classification

32

ImageNet-1K (ILSVRC)

  • 1,000 object classes
  • 1,000 training images/class
  • Each image contains just one class of object!

​

Metric: Top-k accuracy

  • For each image, return a list of top-k possible classes
  • If the true class is within the list, the classification is correct

33 of 113

The progress of deep learning for classification

[Simonyan et al., 2015]

[Szegedy et al., 2015]

[Huang et al., 2017]

[He et al., 2016]

[Krizhevsky et al., 2012]

Top-5 error rate

34 of 113

General formulation for all these variants

​

​

​

​

​

​

​

​

34

 

Image (pixels)

 

 

 

 

35 of 113

Recap: classification

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

 

 

 

36 of 113

Deep neural networks (DNN)

37 of 113

Convolution

A special computation between layers

  • A current node is not directly affected by “all nodes in the previous layer”
  • The network “weights” on the edges can be “re-used”

37

38 of 113

Convolution: properties

  • Process nearby pixels together
  • Translation invariant: “local patterns” can show up at different pixel locations
  • Can process arbitrary-size images

38

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

Top-left, Top right: has ears

Middle: has eyes

39 of 113

Convolutional neural networks (CNN)

39

Shared weights

Vectorization + FC layers

Max pooling + down-sampling

  • Remove redundancy
  • Translation-tolerant
  • Enlarge receptive filed

40 of 113

Training a DNN for classification

  •  

40

100: elephant

 

Minimize the empirical risk

41 of 113

41

Questions?

42 of 113

Four factors behind deep learning developments

  • Data

​

  • Neural network architecture

​

  • Powerful “learning” algorithms and loss

​

  • Computational resource

43 of 113

Accessibility to large amount of data

43

44 of 113

Flexible neural networks for modeling

Visual transformers

[Liu et al., 2021]

[Battaglia et al., 2018]

Graph neural networks

[Qi et al., 2017]

PointNet

ConvNet

[Huang et al., 2017]

[Gu et al., 2024]

Recurrent neural networks

45 of 113

Powerful algorithms + losses to learn from data

Bi-level optimization

[Finn et al., 2017]

Adversarial learning

[Ganin et al., 2016]

[He et al., 2020]

Contrastive learning

Diffusion (denoising)

[Ho et al., 2020]

Autoregressive

[El-Nouby et al., 2024]

Preference learning

[Rafailov et al., 2023]

46 of 113

Computational resource

47 of 113

47

Questions?

48 of 113

Perceptron

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

 

 

 

 

 

 

 

49 of 113

Perceptron

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

 

 

 

 

 

 

 

50 of 113

Perceptron

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

 

 

 

 

 

 

 

51 of 113

Perceptron

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

 

 

 

 

 

 

 

52 of 113

Perceptron as classifiers

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

53 of 113

Learning a classifier

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

54 of 113

54

Questions?

55 of 113

Multi-layer perceptron (MLP)

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

Element-wise

56 of 113

Activations vs. Parameters

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

57 of 113

Why do we need activation?

  •  

58 of 113

Deep Nets

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

59 of 113

Deep learning: learning with neural nets

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

What are neural nets? What is deep learning?

60 of 113

Layers

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

61 of 113

Layers

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

62 of 113

Deep Nets

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

63 of 113

Deep Nets

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

64 of 113

Deep Nets

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

65 of 113

Deep Nets

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

66 of 113

Deep learning: learning with neural nets

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

67 of 113

67

Questions?

68 of 113

Data structure (in training)

  • Image classification problem

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

69 of 113

Data structure (in training)

  • Image classification problem

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

70 of 113

Data structure (in training)

  • Image classification problem

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

71 of 113

Data structure (in training)

  • Image classification problem

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

72 of 113

Data structure (in training)

  • Image classification problem

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

Stochastic Gradient Descent

73 of 113

Data structure (in training)

  • Image classification problem

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

Stochastic Gradient Descent

74 of 113

Data structure (in training)

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

Batch size = 3

75 of 113

Data structure (in training)

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

Batch size = 3

76 of 113

Reading

  • Read 12.7.3
  • Read 12.7.4
  • Read 12.8

77 of 113

Today

  • Recap
  • Neural networks
  • Why are neural networks powerful?

​

​

77

78 of 113

Why are neural networks powerful?

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

79 of 113

Geometric “transformation” perspective

Function

Data transformation

Data mapping

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

80 of 113

What is this function?

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

81 of 113

What is this function?

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

82 of 113

What is this function?

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

83 of 113

What is this function?

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

84 of 113

Put together

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

85 of 113

2D examples

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

 

Observation?

86 of 113

2D examples

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

 

Which one is more “diverse”?

87 of 113

What does a neural network classifier want to do?

  •  

88 of 113

Visualizing a neural network classifier (binary)

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

 

89 of 113

Visualizing a neural network classifier (binary)

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

90 of 113

How is a neural network trained?

[Figure credit: A. Torralba, P. Isola, and W. T. Freeman, Foundations of Computer Vision.]

91 of 113

Today

  • Recap
  • Gradient-based learning algorithms
  • Generalization
  • Neural networks
  • Why are neural networks powerful?
  • CNN Revisit & Extensions

​

​

91

92 of 113

Convolutional neural networks (CNN)

92

Vectorization + FC layers

93 of 113

A simple CNN classifier

93

94 of 113

A simple CNN classifier

94

95 of 113

A simple CNN classifier

95

96 of 113

A simple CNN classifier

96

97 of 113

A simple CNN classifier

97

98 of 113

A simple CNN classifier

98

99 of 113

99

Questions?

100 of 113

What if the image size changes?

100

Vectorization + FC layers

101 of 113

Revisit the bird image

101

How to apply?

102 of 113

Convolutional neural networks (CNN) for detection

102

103 of 113

Convolutional neural networks (CNN) for segmentation

103

104 of 113

Spatial output

104

105 of 113

A simple CNN classifier

105

106 of 113

Spatial output

106

107 of 113

107

Questions?

108 of 113

Popular CNN architectures

  • Encoder, decoder

108

109 of 113

Popular CNN architectures

  • Encoder + decoder for segmentation

109

110 of 113

Popular CNN architectures

  • U-Net: Encoder + decoder + skip links

110

111 of 113

111

Questions?

112 of 113

Besides translation, CNNs need to tackle object scale

112

113 of 113

Feature pyramid networks

113

[Feature Pyramid Networks for Object Detection, CVPR 2017]