1 of 54

CSE 5524: �Foundation of learning - 2

2 of 54

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

​

3 of 54

Grade distribution and final project information

  • Will be finalized in early to mid February

4 of 54

Background information

5 of 54

Today

  • Recap of learning
  • Recap of classification
  • Gradient-based learning algorithms
  • Generalization

​

​

​

5

6 of 54

Recap: learning

  • Goal: extract lessons from past experience to solve future problems
  • Process: Searching for an algorithm that solves past instances of the problem

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

7 of 54

Recap: learning

Temperature

People at beach

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

8 of 54

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

9 of 54

Recap: Key ingredients

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

10 of 54

Recap: 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.]

 

11 of 54

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

12 of 54

Today

  • Recap of learning
  • Recap of classification
  • Gradient-based learning algorithms
  • Generalization

​

​

​

12

13 of 54

Case study – 2: classification

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

 

 

 

14 of 54

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.]

15 of 54

Case study – 2: classification

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

16 of 54

Case study – 2: classification

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

17 of 54

Today

  • Recap of learning
  • Recap of classification
  • Gradient-based learning algorithms
  • Generalization

​

​

​

17

18 of 54

Gradient-based learning algorithm

  • The goal:

​

19 of 54

Gradient-based learning algorithm

  • The goal:

​

  • Illustration:

Derivative (-)

GOAL: minimum error

 

 

 

 

 

 

20 of 54

Basic gradient descent

  • The goal:

​

  • Pseudo-code:

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

21 of 54

Basic gradient descent

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

 

22 of 54

Effects of learning rate

Too small

Too large

About right

 

 

 

 

23 of 54

Learning rate schedule

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

24 of 54

Momentum

Too small

Too large

About right

25 of 54

Momentum

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

 

26 of 54

Momentum

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

27 of 54

Gradient descent always useful?

  • Differentiable
  • Meaningful “guidance”

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

PyTorch could handle it!

28 of 54

29 of 54

Surrogate loss function

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

30 of 54

Stochastic gradient descent (SGD)

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

31 of 54

Stochastic gradient descent (SGD)

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

32 of 54

Modern optimizers

33 of 54

Example: image classification

33

[Gif credits: Gradient descent 3Blue1Brown series S3 E2]

A sequence of “learnable” computation!

34 of 54

Example: image classification (training)

35 of 54

Today

  • Recap of learning
  • Recap of classification
  • Gradient-based learning algorithms
  • Generalization

​

​

​

35

36 of 54

Recap: learning

  •  

36

37 of 54

Training vs. testing

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

37

 

 

x

y

In training, we only see training data!

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

38 of 54

Under-fitting vs. over-fitting

  • Background: polynomial regression

39 of 54

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

39

[Slides: from USC CSCI567]

 

 

 

40 of 54

Under-fitting vs. over-fitting

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

​

​

​

​

​

​

40

[Slides: from USC CSCI567]

 

41 of 54

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?

​

​

​

 

42 of 54

 

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.]

43 of 54

Questions?

44 of 54

Regularization

  • Searching for “simpler” solution

 

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

45 of 54

Finding a good regularizer is not always easy

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

46 of 54

Occam’s razor principle

46

All things being equal,

the simplest explanation is usually the best!

47 of 54

Three tools in the search for Truth

  • Data: what we observe

​

  • Prior: what we prefer & believe

​

  • Hypotheses: what the true function may be

​

​

48 of 54

Data (likelihood) & Prior

49 of 54

Three tools in the search for Truth

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

50 of 54

Effect of data

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

51 of 54

More data, less over-fitting

 

 

 

[Figure: Bishop, PRML]

Green: true data distribution

Blue: training data

Red: learned model

52 of 54

Effect of priors

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

53 of 54

Effect of hypothesis space

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

54 of 54

Remark

  • We finish section 11