CSE 5524: �Foundation of learning - 3

Homework assignment - 1

• Will be released on 2/2 or 2/3

​

• Homework – 2 will very likely be released two weeks after the above date

​

Today

• Recap
• Generalization
• Neural networks overview
• Neural networks

​

​

3

Recap: Key ingredients

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

Case study – 1: regression

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

Case study – 2: classification

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

Gradient-based learning algorithm

• The goal:

​

Gradient-based learning algorithm

• The goal:

​

• Illustration:

Basic gradient descent

• The goal:

​

• Pseudo-code:

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

Today

• Recap
• Generalization
• Neural networks overview
• Neural networks

​

​

10

Training vs. testing

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

11

x

y

In training, we only see training data!

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

Under-fitting vs. over-fitting

• Background: polynomial regression

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

13

[Slides: from USC CSCI567]

Under-fitting vs. over-fitting

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

​

​

​

​

​

​

14

[Slides: from USC CSCI567]

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?

​

​

​

Training data

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

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

Questions?

Regularization

• Searching for “simpler” solution

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

Finding a good regularizer is not always easy

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

Occam’s razor principle

20

All things being equal,

the simplest explanation is usually the best!

Three tools in the search for Truth

• Data: what we observe

​

• Prior: what we prefer & believe

​

• Hypotheses: what the true function may be

​

​

Data (likelihood) & Prior

Three tools in the search for Truth

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

Effect of data

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

More data, less over-fitting

[Figure: Bishop, PRML]

Green: true data distribution

Blue: training data

Red: learned model

Effect of priors

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

Effect of hypothesis space

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

Remark & Plan

• We finish section 11

​

• Section 12: Neural networks

​

• Section 13: Neural networks as distribution transformers

​

• Section 14: Back-propagation (skip in class!)

Today

• Recap
• Generalization
• Neural networks overview
• Neural networks

​

​

29

The progress of deep learning for classification

30

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

The progress of deep learning for classification

Top-5 error rate

General formulation for all these variants

​

​

​

​

​

​

​

​

32

Recap: classification

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

Deep neural networks (DNN)

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”

35

Convolution

36

Feature map (nodes) at layer t

Feature map at layer t+1

“Filter” weights

(3-by-3)

Convolution

37

“Filter” weights

(3-by-3)

Inner product

Feature map (nodes) at layer t

Feature map at layer t+1

Convolution

38

“Filter” weights

(3-by-3)

Inner product

Zero-padding: Set the missing values to be 0

Feature map (nodes) at layer t

Feature map at layer t+1

Convolution example

39

Convolution

40

“Filter” weights

(3-by-3)

“Filter” weights

(3-by-3-by-“2”)

Inner product

Feature map (nodes) at layer t

Feature map at layer t+1

Convolution

41

“Filter” weights

(3-by-3-by-“2”)

Inner product

Feature map (nodes) at layer t

Feature map at layer t+1

One filter for one output “channel” to capture a different “pattern” (e.g., edges, circles, eyes, etc.)

Convolution: properties

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

42

Top-left, Top right: has ears

Middle: has eyes

Convolutional neural networks (CNN)

43

Representative CNN networks

• AlexNet

[Krizhevsky et al., 2012]

​

​

• VGGnet

[Simonyan et al., 2015]

44

• A block: computation
• Edge: nodes/tensors

Representative CNN networks

• GoogleNet [Szegedy et al., 2014]
• Inception

Representative CNN networks

• ResNet

[He et al, 2016]

​

​

​

• DenseNet

[Huang et al, 2017]

46

• A block: computation
• Edge: nodes/tensors

Advantages:

• Optimization
• Collect more information

Representative CNN networks

A general architecture involves

• Multiple layers of convolutions + ReLU (nonlinearity) + pooling + striding
• These result in a (final) feature map
• Positions on the map correspond to the image
• The map goes through FC layers (MLP)
• Usually, we keep the network till the feature map
• For feature extraction
• For down-stream tasks
• For image-to-image search

47

Training a DNN for classification

48

Four factors behind deep learning developments

• Data

​

• Neural network architecture

​

• Powerful “learning” algorithms and loss

​

• Computational resource

Accessibility to large amount of data

50

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

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]

Computational resource

Today

• Recap
• Generalization
• Neural networks overview
• Neural networks

​

​

54

Deep neural networks (DNN)

Re-Introduction

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

Perceptron

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

Perceptron as classifiers

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

Learning a classifier

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

Multi-layer perceptron (MLP)

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

Activations vs. Parameters

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

Fast activation and slow parameters

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