machine learning introductory concepts .

Machine learning fundamentals is discussed in this slide

1. ETHEM ALPAYDIN
© The MIT Press, 2010
[email protected]
http://www.cmpe.boun.edu.tr/~ethem/i2ml2e
Lecture Slides for

3. Learning a Class from Examples
Class C of a “family car”
Prediction:Is car xa family car?
Knowledge extraction: What do people expect from a
family car?
Output:
Positive (+) and negative (–) examples
Input representation:
x
1: price, x
2: engine power
3Lecture Notes for E Alpaydın2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

4. Training set XN
t
tt
,r
1
}{

xX 



negative is if
positive is if
x
x
0
1
r
4






2
1
x
x
x Lecture Notes for E Alpaydın2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

5. Class C   
2121 power engine AND price eepp 
5Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

6. Hypothesis class H



negative is says if
positive is says if
)(
x
x
x
h
h
h
0
1  


N
t
tt
rhhE
1
1x)|(X
6
Error of h onH
Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

7. S, G, and the Version Space
7
most specific hypothesis, S
most general hypothesis, G
h H, between Sand Gis
consistent
and make up the
version space
(Mitchell, 1997)
Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

8. Margin
Choose hwith largest margin
Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0) 8

9. VC Dimension
Npoints can be labeled in 2
N
ways as +/–
HshattersNif there
exists h Hconsistent
for any of these:
VC(H ) = N
9
An axis-aligned rectangle shatters 4 points only !
Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

10. Probably Approximately Correct
(PAC) Learning
How many training examples Nshould we have, such that with probability
at least1 ‒ δ, hhas error at most ε ?
(Blumer et al., 1989)
Each strip is at most ε/4
Pr that we miss a strip 1‒ ε/4
Pr that Ninstances miss a strip (1 ‒ ε/4)
N
Pr that Ninstances 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

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

12. Multiple Classes, C
ii=1,...,KN
t
tt
,r
1
}{

xX 





, if
if
ij
r
j
t
i
t
t
i
C
C
x
x
0
1 






, if
if
ij
h
j
t
i
t
t
i
C
C
x
x
x
0
1
12
Train hypotheses
h
i(x), i =1,...,K:
Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

13. Regression
01
wxwxg  
01
2
2
wxwxwxg    


N
t
tt
xgr
N
gE
1
21
X|
13    


N
t
tt
wxwr
N
wwE
1
2
0101
1
X|, 




tt
t
N
t
tt
xfr
r
rx
1
,X Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)

14. 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: Hmore complex than Cor f
Underfitting: Hless complex than Cor f
Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)14

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

16. 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ın2010 Introduction to Machine Learning 2e © The MIT Press (V1.0) 16

17. Dimensions of a Supervised
Learner
1.Model:
2.Loss function:
3.Optimization procedure:|xg   
t
tt
grLE  |,| xX
17X|min arg* 

E Lecture Notes for E Alpaydın 2010 Introduction to Machine Learning 2e © The MIT Press (V1.0)