Transcript Machine Learning

Evaluating Hypotheses
• Sample error, true error
• Confidence intervals for observed hypothesis error
• Estimators
• Binomial distribution, Normal distribution,
Central Limit Theorem
• Paired t-tests
• Comparing Learning Methods
CS 5751 Machine
Learning
Chapter 5 Evaluating Hypotheses
1
Problems Estimating Error
1. Bias: If S is training set, errorS(h) is optimistically
biased
bias  E[errorS (h)]  errorD (h)
For unbiased estimate, h and S must be chosen
independently
2. Variance: Even with unbiased S, errorS(h) may
still vary from errorD(h)
CS 5751 Machine
Learning
Chapter 5 Evaluating Hypotheses
2
Two Definitions of Error
The true error of hypothesis h with respect to target function f
and distribution D is the probability that h will misclassify
an instance drawn at random according to D.
errorD (h)  Pr  f ( x)  h( x)
xD
The sample error of h with respect to target function f and
data sample S is the proportion of examples h misclassifies
1
errorS (h)     f ( x)  h( x) 
n xS
where   f ( x)  h( x)  is 1 if f ( x)  h( x), and 0 otherwise
How well does errorS(h) estimate errorD(h)?
CS 5751 Machine
Learning
Chapter 5 Evaluating Hypotheses
3
Example
Hypothesis h misclassifies 12 of 40 examples in S.
12
errorS (h) 
 .30
40
What is errorD(h)?
CS 5751 Machine
Learning
Chapter 5 Evaluating Hypotheses
4
Estimators
Experiment:
1. Choose sample S of size n according to
distribution D
2. Measure errorS(h)
errorS(h) is a random variable (i.e., result of an
experiment)
errorS(h) is an unbiased estimator for errorD(h)
Given observed errorS(h) what can we conclude
about errorD(h)?
CS 5751 Machine
Learning
Chapter 5 Evaluating Hypotheses
5
Confidence Intervals
If
• S contains n examples, drawn independently of h and each
other
• n  30
Then
• With approximately N% probability, errorD(h) lies in
interval
errorS (h)(1  errorS (h))
errorS (h)  z N
n
where
N% : 50% 68% 80% 90% 95% 98% 99%
z N : 0.67 1.00 1.28 1.64 1.96 2.33 2.53
CS 5751 Machine
Learning
Chapter 5 Evaluating Hypotheses
6
Confidence Intervals
If
• S contains n examples, drawn independently of h and each
other
• n  30
Then
• With approximately 95% probability, errorD(h) lies in
interval
errorS (h)(1  errorS (h))
errorS (h) 1.96
n
CS 5751 Machine
Learning
Chapter 5 Evaluating Hypotheses
7
errorS(h) is a Random Variable
• Rerun experiment with different randomly drawn S (size n)
• Probability of observing r misclassified examples:
Binomial distribution for n=40, p=0.3
0.14
0.12
P(r)
0.10
0.08
0.06
0.04
0.02
0.00
0
5
10
15
20
r
25
30
35
40
n!
P(r ) 
errorD (h) r (1  errorD (h)) nr
r!(n  r )!
CS 5751 Machine
Learning
Chapter 5 Evaluating Hypotheses
8
Binomial Probability Distribution
Binomial distribution for n=40, p=0.3
0.14
0.12
P(r ) 
P(r)
0.10
0.08
0.06
n!
p r (1  p) nr
r!(n  r )!
0.04
0.02
0.00
0
5
10
15
20
r
25
30
35
40
Probabilty P(r) of r heads in n coin flips, if p  Pr (heads)
n
 Expected, or mean value of X : E[X]   iP (i )  np
i 0
 Variance of X : Var(X)  E[( X  E[ X ]) 2 ]  np (1  p )
 Standard deviation of X : σ X  E[( X  E[ X ]) 2 ]  np (1  p )
CS 5751 Machine
Learning
Chapter 5 Evaluating Hypotheses
9
Normal Probability Distribution
Normal distribution with mean 0, standard deviation 1
0.4
0.35
P(r ) 
0.3
0.25
0.2
0.15
1
2πσ
 12  xσμ 
2
2
e
0.1
0.05
0
-3
-2.5
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
2.5
3
The probabilit y that X will fall into the interval (a,b) is given by

b
a
p( x)dx
 Expected, or mean value of X : E[X]  μ
 Variance of X : Var(X)  σ 2
 Standard deviation of X : σ X  σ
CS 5751 Machine
Learning
Chapter 5 Evaluating Hypotheses
10
Normal Distribution Approximates Binomial
errors (h) follows a Binomial distributi on, with
 mean μ errorS ( h )  errorD (h)
 standard deviation
σ errorS ( h )
errorD (h)(1  errorD (h))

n
Approximat e this by a Normal distributi on with
 mean μ errorS ( h )  errorD (h)
 standard deviation
σ errorS ( h )
CS 5751 Machine
Learning
errorS (h)(1  errorS (h))

n
Chapter 5 Evaluating Hypotheses
11
Normal Probability Distribution
0.4
0.35
0.3
0.25
0.2
0.15
0.1
0.05
0
-3
-2.5
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
2.5
3
80% of area (probabili ty) lies in   1.28σ
N% of area (probabili ty) lies in   z Nσ
N% : 50% 68% 80% 90% 95% 98% 99%
z N : 0.67 1.00 1.28 1.64 1.96 2.33 2.53
CS 5751 Machine
Learning
Chapter 5 Evaluating Hypotheses
12
Confidence Intervals, More Correctly
If
• S contains n examples, drawn independently of h and each
other
• n  30
Then
• With approximately 95% probability, errorS(h) lies in
interval
errorD (h)(1  errorD (h))
errorD (h) 1.96
n
• equivalently, errorD(h) lies in interval
errorD (h)(1  errorD (h))
errorS (h) 1.96
n
• which is approximately
errorS (h)(1  errorS (h))
errorS (h) 1.96
n
CS 5751 Machine
Learning
Chapter 5 Evaluating Hypotheses
13
Calculating Confidence Intervals
1. Pick parameter p to estimate
• errorD(h)
2. Choose an estimator
• errorS(h)
3. Determine probability distribution that governs estimator
• errorS(h) governed by Binomial distribution, approximated
by Normal when n  30
4. Find interval (L,U) such that N% of probability mass falls
in the interval
• Use table of zN values
CS 5751 Machine
Learning
Chapter 5 Evaluating Hypotheses
14
Central Limit Theorem
Consider a set of independen t, identicall y distribute d random
variables Y1 Yn , all governed by an arbitrary probabilit y distributi on
with mean  and finite variance  2 . Define the sample mean
1 n
Y   Yi
n i 1
Central Limit Theorem . As n  , the distributi on governing Y
σ2
approaches a Normal distributi on, with mean  and variance
.
n
CS 5751 Machine
Learning
Chapter 5 Evaluating Hypotheses
15
Difference Between Hypotheses
Test h1 on sample S1 , test h2 on S 2
1. Pick parameter to estimate
d  errorD (h1 )  errorD (h2 )
2. Choose an estimator
d  errorS1 (h1 )  errorS 2 (h2 )
3. Determine probabilit y distributi on that governs estimator
σd 
errorS1 (h1 )(1  errorS1 (h1 ))
n1

errorS 2 (h2 )(1  errorS 2 (h2 ))
n2
4. Find interval (L, U) such that N% of probabilit y mass falls
in the interval
errorS1 (h1 )(1  errorS1 (h1 )) errorS 2 (h2 )(1  errorS 2 (h2 ))
ˆ
d  zN

n1
n2
CS 5751 Machine
Learning
Chapter 5 Evaluating Hypotheses
16
Paired t test to Compare hA,hB
1. Partition data into k disjoint t est sets T1,T2 ,...,Tk of
equal size, where this size is at least 30.
2. For i from 1 to k do
δ i  errorTi (hA )  errorTi (hB )
3. Return the value d, where
1 k
δ  δ i
k i 1
N% confidence interval estimate for d :
δ  t N,k-1sδ
k
1
2
sδ 
(
δ

δ
)
 i
k (k  1) i 1
Note δ i approximately Normally distri buted
CS 5751 Machine
Learning
Chapter 5 Evaluating Hypotheses
17
Comparing Learning Algorithms LA and LB
1. Partition data D0 into k disjoint t est sets T1,T2 ,...Tk of equal size,
where this size is at least 30.
2. For i from 1 to k , do
use Ti for the test set, and the remaining data for traini ng set Si
 Si  {D0  Ti }
 hA  LA(S i )
 hB  LB(S i )
 δ i  errorTi (hA )  errorTi (hB )
3. Return the value δ , where
1 k
δ  δ i
k i 1
CS 5751 Machine
Learning
Chapter 5 Evaluating Hypotheses
18
Comparing Learning Algorithms LA and LB
What we would like to estimate:
ES  D [errorD ( LA ( S ))  errorD ( LB (S ))]
where L(S) is the hypothesis output by learner L using
training set S
i.e., the expected difference in true error between hypotheses output
by learners LA and LB, when trained using randomly selected
training sets S drawn according to distribution D.
But, given limited data D0, what is a good estimator?
Could partition D0 into training set S and training set T0 and
measure
errorT0 ( LA ( S 0 ))  errorT0 ( LB ( S 0 ))
even better, repeat this many times and average the results
(next slide)
CS 5751 Machine
Learning
Chapter 5 Evaluating Hypotheses
19
Comparing Learning Algorithms LA and LB
Notice we would like to use the paired t test on δ to
obtain a confidence interval
But not really correct, because the training sets in
this algorithm are not independent (they overlap!)
More correct to view algorithm as producing an
estimate of
ES  D0 [errorD ( LA ( S ))  errorD ( LB ( S ))]
instead of
ES  D [errorD ( LA ( S ))  errorD ( LB (S ))]
but even this approximation is better than no
comparison
CS 5751 Machine
Learning
Chapter 5 Evaluating Hypotheses
20