INTRODUCTION TO �Machine Learning

ETHEM ALPAYDIN

© The MIT Press, 2010

​

alpaydin@boun.edu.tr

http://www.cmpe.boun.edu.tr/~ethem/i2ml2e

Lecture Slides for

CHAPTER 2: �Supervised Learning

Learning a Class from Examples

• Class C of a “family car”
• Prediction: Is car x a family car?
• Knowledge extraction: What do people expect from a family car?
• Output:

Positive (+) and negative (–) examples

• Input representation:

x₁: price, x₂ : engine power

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

3

Training set X

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

4

Class C

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

5

Hypothesis class H

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

6

Error of h on H

S, G, and the Version Space

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

7

most specific hypothesis, S

most general hypothesis, G

h ∈ H, between S and G is

consistent

and make up the

version space

(Mitchell, 1997)

Margin

• Choose h with largest margin

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

8

VC Dimension

• N points can be labeled in 2^N ways as +/–
• H shatters N if there

exists h ∈ H consistent

for any of these:

VC(H ) = N

​

​

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

9

An axis-aligned rectangle shatters 4 points only !

Probably Approximately Correct (PAC) Learning

• How many training examples N should we have, such that with probability at least 1 ‒ δ, h has error at most ε ?

(Blumer et al., 1989)

​

• Each strip is at most ε/4
• Pr that we miss a strip 1‒ ε/4
• Pr that N instances miss a strip (1 ‒ ε/4)^N
• Pr that N instances miss 4 strips 4(1 ‒ ε/4)^N
• 4(1 ‒ ε/4)^N ≤ δ and (1 ‒ x)≤exp( ‒ x)
• 4exp(‒ εN/4) ≤ δ and N ≥ (4/ε)log(4/δ)

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

10

Noise and Model Complexity

Use the simpler one because

• Simpler to use

(lower computational

complexity)

• Easier to train (lower

space complexity)

• Easier to explain

(more interpretable)

• Generalizes better (lower

variance - Occam’s razor)

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

11

Multiple Classes, C_i i=1,...,K

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

12

Train hypotheses

h_i(x), i =1,...,K:

Regression

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

13

Model Selection & Generalization

• Learning is an ill-posed problem; data is not sufficient to find a unique solution
• The need for inductive bias, assumptions about H
• Generalization: How well a model performs on new data
• Overfitting: H more complex than C or f
• Underfitting: H less complex than C or f

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

14

Triple Trade-Off

• There is a trade-off between three factors (Dietterich, 2003):
1. Complexity of H, c (H),
2. Training set size, N,
3. Generalization error, E, on new data
• As N↑, E↓
• As c (H)↑, first E↓ and then E↑

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

15

Cross-Validation

• To estimate generalization error, we need data unseen during training. We split the data as
• Training set (50%)
• Validation set (25%)
• Test (publication) set (25%)
• Resampling when there is few data

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

16

Dimensions of a Supervised Learner

1. Model:

• Loss function:

• Optimization procedure:

Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

17