1 of 24

CS60050: Machine Learning

Sourangshu Bhattacharya

2 of 24

CROSS-VALIDATION

3 of 24

The test set method

Slide 3

Good news:

Very very simple
Can then simply choose the method with the best test-set score

Bad news:

What’s the downside?

4 of 24

The test set method

Slide 4

Good news:

Very very simple
Can then simply choose the method with the best test-set score

Bad news:

Wastes data: we get an estimate of the best method to apply to 30% less data
If we don’t have much data, our test-set might just be lucky or unlucky

We say the “test-set estimator of performance has high variance”

5 of 24

LOOCV (Leave-one-out Cross Validation)

Slide 5

x

y

For k=1 to R

1. Let (x_k,y_k) be the k^threcord

6 of 24

LOOCV (Leave-one-out Cross Validation)

Slide 6

x

y

For k=1 to R

Let (x_k,y_k) be the k^threcord
Temporarily remove (x_k,y_k)

from the dataset

7 of 24

LOOCV (Leave-one-out Cross Validation)

Slide 7

x

y

For k=1 to R

Let (x_k,y_k) be the k^threcord
Temporarily remove (x_k,y_k)

from the dataset

Train on the remaining R-1 datapoints

8 of 24

LOOCV (Leave-one-out Cross Validation)

Slide 8

For k=1 to R

Let (x_k,y_k) be the k^threcord
Temporarily remove (x_k,y_k)

from the dataset

Train on the remaining R-1 datapoints
Note your error (x_k,y_k)

x

y

9 of 24

LOOCV (Leave-one-out Cross Validation)

Slide 9

For k=1 to R

Let (x_k,y_k) be the k^threcord
Temporarily remove (x_k,y_k)

from the dataset

Train on the remaining R-1 datapoints
Note your error (x_k,y_k)

When you’ve done all points, report the mean error.

x

y

10 of 24

LOOCV (Leave-one-out Cross Validation)

Slide 10

For k=1 to R

Let (x_k,y_k) be the k^threcord
Temporarily

remove (x_k,y_k) from the dataset

Train on the

remaining R-1

datapoints

Note your

error (x_k,y_k)

When you’ve done all points, report the mean error.

^MSELOOCV

= 2.12

x

y

x

y

x

y

x

y

x

y

x

y

x

11 of 24

LOOCV for Quadratic Regression

Slide 11

For k=1 to R

Let (x_k,y_k) be the k^threcord
Temporarily

remove (x_k,y_k) from the dataset

Train on the

remaining R-1

datapoints

Note your

error (x_k,y_k)

When you’ve done all points, report the mean error.

^MSELOOCV

=0.962

x

y

x

y

x

y

x

y

x

y

x

y

x

12 of 24

LOOCV for Join The Dots

Slide 12

For k=1 to R

Let (x_k,y_k) be the k^threcord
Temporarily

remove (x_k,y_k) from the dataset

Train on the

remaining R-1

datapoints

Note your

error (x_k,y_k)

When you’ve done all points, report the mean error.

^MSELOOCV

=3.33

x

y

x

y

x

y

x

y

x

y

x

y

x

13 of 24

Which kind of Cross Validation?

Slide 13

	Downside	Upside
Test-set	Variance: unreliable estimate of future performance	Cheap
Leave- one-out	Expensive. Has some weird behavior	Doesn’t waste data

..can we get the best of both worlds?

14 of 24

k-fold Cross Validation

Slide 14

x

y

Randomly break the dataset into k partitions (in our example we’ll have k=3 partitions colored Red Green and Blue)

15 of 24

k-fold Cross Validation

Slide 15

x

y

Randomly break the dataset into k partitions (in our example we’ll have k=3 partitions colored Red Green and Blue)

For the red partition: Train on all the points not in the red partition. Find the test-set sum of errors on the red points.

16 of 24

k-fold Cross Validation

Slide 16

x

y

Randomly break the dataset into k partitions (in our example we’ll have k=3 partitions colored Red Green and Blue)

For the red partition: Train on all the points not in the red partition. Find the test-set sum of errors on the red points.

For the green partition: Train on all the points not in the green partition.

Find the test-set sum of errors on the green points.

17 of 24

k-fold Cross Validation

Slide 17

x

y

Randomly break the dataset into k partitions (in our example we’ll have k=3 partitions colored Red Green and Blue)

For the red partition: Train on all the points not in the red partition. Find the test-set sum of errors on the red points.

For the green partition: Train on all the points not in the green partition.

Find the test-set sum of errors on the green points.

For the blue partition: Train on all the

points not in the blue partition. Find the test-set sum of errors on the blue points.

18 of 24

k-fold Cross Validation

Slide 18

x

y

Randomly break the dataset into k partitions (in our example we’ll have k=3 partitions colored Red Green and Blue)

For the red partition: Train on all the points not in the red partition. Find the test-set sum of errors on the red points.

For the green partition: Train on all the points not in the green partition.

Find the test-set sum of errors on the green points.

For the blue partition: Train on all the

points not in the blue partition. Find the test-set sum of errors on the blue points.

Then report the mean error

Linear Regression

MSE_3FOLD=2.05

19 of 24

k-fold Cross Validation

x

y

Randomly break the dataset into k partitions (in our example we’ll have k=3 partitions colored Red Green and Blue)

For the red partition: Train on all the points not in the red partition. Find the test-set sum of errors on the red points.

For the green partition: Train on all the points not in the green partition.

Find the test-set sum of errors on the green points.

For the blue partition: Train on all the

points not in the blue partition. Find the test-set sum of errors on the blue points.

Then report the mean error

Quadratic Regression

MSE_3FOLD=1.11

Slide 33

20 of 24

k-fold Cross Validation

Slide 20

x

y

Randomly break the dataset into k partitions (in our example we’ll have k=3 partitions colored Red Green and Blue)

For the red partition: Train on all the points not in the red partition. Find the test-set sum of errors on the red points.

For the green partition: Train on all the points not in the green partition.

Find the test-set sum of errors on the green points.

For the blue partition: Train on all the

points not in the blue partition. Find the test-set sum of errors on the blue points.

Then report the mean error

Joint-the-dots

MSE_3FOLD=2.93

21 of 24

Which kind of Cross Validation?

Slide 21

	Downside	Upside
Test-set	Variance: unreliable estimate of future performance	Cheap
Leave- one-out	Expensive. Has some weird behavior	Doesn’t waste data
10-fold	Wastes 10% of the data. 10 times more expensive than test set	Only wastes 10%. Only 10 times more expensive instead of R times.
3-fold	Wastier than 10-fold. Expensivier than test set	Slightly better than test- set
R-fold	Identical to Leave-one-out

22 of 24

CV-based Model Selection

Slide 22

•

Step 2: Whichever model class gave best CV score: train it

with all the data, and that’s the predictive model you’ll use.

Example: Choosing number of hidden units in a one- hidden-layer neural net.
Step 1: Compute 10-fold CV error for six different model classes:

Algorithm	TRAINERR	10-FOLD-CV-ERR	Choice
0 hidden units
1 hidden units
2 hidden units			⌦
3 hidden units
4 hidden units
5 hidden units

23 of 24

CV-based Model Selection

Slide 23

Example: Choosing “k” for a k-nearest-neighbor regression.
Step 1: Compute LOOCV error for six different model classes:

Algorithm	TRAINERR	10-fold-CV-ERR	Choice
K=1
K=2
K=3
K=4			⌦
K=5
K=6

•

Step 2: Whichever model class gave best CV score: train it

with all the data, and that’s the predictive model you’ll use.

24 of 24

CV-based Model Selection

Slide 24

Can you think of other decisions we can ask Cross Validation to make for us, based on other machine learning algorithms in the class so far?

Degree of polynomial in polynomial regression
Whether to use full, diagonal or spherical Gaussians in a Gaussian Bayes Classifier.
The Kernel Width in Kernel Regression
The Kernel Width in Locally Weighted Regression
The Bayesian Prior in Bayesian Regression

These involve choosing the value of a real-valued parameter. What should we do?

Idea One: Consider a discrete set of values (often best to consider a set of values with exponentially increasing gaps, as in the K-NN example).

Idea Two: Compute

and then

do gradianet descent.

∂ Parameter

∂ LOOCV