Assessing and Comparing Classification Algorithms.ppt

1、Assessing and Comparing Classification Algorithms,Introduction Resampling and Cross Validation Measuring Error Interval Estimation and Hypothesis Testing Assessing and Comparing Performance,Lecture Notes for E Alpaydn 2004 Introduction to Machine Learning The MIT Press (V1.1),2,Introduction,Question

2、s: Assessment of the expected error of a learning algorithm: Is the error rate of 1-NN less than 2%? Comparing the expected errors of two algorithms: Is k-NN more accurate than MLP ? Training/validation/test sets Resampling methods: K-fold cross-validation,Lecture Notes for E Alpaydn 2004 Introducti

3、on to Machine Learning The MIT Press (V1.1),3,Algorithm Preference,Criteria (Application-dependent): Misclassification error, or risk (loss functions) Training time/space complexity Testing time/space complexity Interpretability Easy programmability Cost-sensitive learning,Assessing and Comparing Cl

4、assification Algorithms,Introduction Resampling and Cross Validation Measuring Error Interval Estimation and Hypothesis Testing Assessing and Comparing Performance,Lecture Notes for E Alpaydn 2004 Introduction to Machine Learning The MIT Press (V1.1),5,Resampling and K-Fold Cross-Validation,The need

5、 for multiple training/validation setsXi,Vii: Training/validation sets of fold i K-fold cross-validation: Divide X into k, Xi,i=1,.,KTi share K-2 parts,Lecture Notes for E Alpaydn 2004 Introduction to Machine Learning The MIT Press (V1.1),6,52 Cross-Validation,5 times 2 fold cross-validation (Diette

6、rich, 1998),Lecture Notes for E Alpaydn 2004 Introduction to Machine Learning The MIT Press (V1.1),7,Bootstrapping,Draw instances from a dataset with replacement Prob that we do not pick an instance after N drawsthat is, only 36.8% is new!,Assessing and Comparing Classification Algorithms,Introducti

7、on Resampling and Cross Validation Measuring Error Interval Estimation and Hypothesis Testing Assessing and Comparing Performance,Lecture Notes for E Alpaydn 2004 Introduction to Machine Learning The MIT Press (V1.1),9,Measuring Error,Error rate = # of errors / # of instances = (FN+FP) / N Recall =

8、# of found positives / # of positives = TP / (TP+FN) = sensitivity = hit rate Precision = # of found positives / # of found= TP / (TP+FP) Specificity = TN / (TN+FP) False alarm rate = FP / (FP+TN) = 1 - Specificity,Methods for Performance Evaluation,How to obtain a reliable estimate of performance?P

9、erformance of a model may depend on other factors besides the learning algorithm: Class distribution Cost of misclassification Size of training and test sets,Learning Curve,Learning curve shows how accuracy changes with varying sample size Requires a sampling schedule for creating learning curve: Ar

10、ithmetic sampling (Langley, et al) Geometric sampling (Provost et al)Effect of small sample size: Bias in the estimate Variance of estimate,ROC (Receiver Operating Characteristic),Developed in 1950s for signal detection theory to analyze noisy signals Characterize the trade-off between positive hits

11、 and false alarms ROC curve plots TP (on the y-axis) against FP (on the x-axis) Performance of each classifier represented as a point on the ROC curve changing the threshold of algorithm, sample distribution or cost matrix changes the location of the point,http:/en.wikipedia.org/wiki/Receiver_operat

12、ing_characteristic,http:/www.childrensmercy.org/stats/ask/roc.asp,ROC Curve,- 1-dimensional data set containing 2 classes (positive and negative) - any points located at x t is classified as positive,ROC Curve,(TP,FP): (0,0): declare everything to be negative class (1,1): declare everything to be po

13、sitive class (1,0): idealDiagonal line: Random guessing Below diagonal line:prediction is opposite of the true class,Using ROC for Model Comparison,No model consistently outperform the other M1 is better for small FPR M2 is better for large FPRArea Under the ROC curve Ideal: Area = 1 Random guess:Ar

14、ea = 0.5,How to Construct an ROC curve,Use classifier that produces posterior probability for each test instance P(+|A)Sort the instances according to P(+|A) in decreasing orderApply threshold at each unique value of P(+|A)Count the number of TP, FP, TN, FN at each thresholdTP rate, TPR = TP/(TP+FN)

15、FP rate, FPR = FP/(FP + TN),How to construct an ROC curve,Threshold =,ROC Curve:,+ + - + - - - + - +,+,-,Reverse of above order,Assessing and Comparing Classification Algorithms,Introduction Resampling and Cross Validation Measuring Error Interval Estimation and Hypothesis Testing Assessing and Comp

16、aring Performance,Lecture Notes for E Alpaydn 2004 Introduction to Machine Learning The MIT Press (V1.1),19,Interval Estimation,X = xt t where xt N ( , 2) m N ( , 2/N),100(1- ) percent confidence interval,Lecture Notes for E Alpaydn 2004 Introduction to Machine Learning The MIT Press (V1.1),20,When

17、2 is not known:,Lecture Notes for E Alpaydn 2004 Introduction to Machine Learning The MIT Press (V1.1),21,Hypothesis Testing,Reject a null hypothesis if not supported by the sample with enough confidence X = xt t where xt N ( , 2)H0: = 0 vs. H1: 0 Accept H0 with level of significance if 0 is in the

18、100(1- ) confidence intervalTwo-sided test,Lecture Notes for E Alpaydn 2004 Introduction to Machine Learning The MIT Press (V1.1),22,One-sided test: H0: 0 vs. H1: 0 Accept ifVariance unknown: Use t, instead of z Accept H0: = 0 if,Assessing and Comparing Classification Algorithms,Introduction Resampl

19、ing and Cross Validation Measuring Error Interval Estimation and Hypothesis Testing Assessing and Comparing Performance,Lecture Notes for E Alpaydn 2004 Introduction to Machine Learning The MIT Press (V1.1),24,Assessing Error: H0: p p0 vs. H1: p p0,Single training/validation set: Binomial TestIf err

20、or prob is p0, prob that there are e errors or less in N validation trials is,1- ,Accept if this prob is less than 1- ,N=100, e=20,Lecture Notes for E Alpaydn 2004 Introduction to Machine Learning The MIT Press (V1.1),25,Normal Approximation to the Binomial,Number of errors X is approx N with mean N

21、p0 and var Np0(1-p0),Accept if this prob for X = e is less than z1-,1- ,Lecture Notes for E Alpaydn 2004 Introduction to Machine Learning The MIT Press (V1.1),26,Paired t Test,Multiple training/validation sets xti = 1 if instance t misclassified on fold i Error rate of fold i:With m and s2 average a

22、nd var of pi we accept p0 or less error ifis less than t,K-1,Lecture Notes for E Alpaydn 2004 Introduction to Machine Learning The MIT Press (V1.1),27,K-Fold CV Paired t Test,Use K-fold cv to get K training/validation folds pi1, pi2: Errors of classifiers 1 and 2 on fold i pi = pi1 pi2 : Paired difference on fold i The null hypothesis is whether pi has mean 0,