CMU CS 10701  NONPARAMETRIC CLASSIFICATION AND ERROR ESTIMATION (10 pages)
Previewing pages 1, 2, 3 of 10 page document View the full content.NONPARAMETRIC CLASSIFICATION AND ERROR ESTIMATION
Previewing pages 1, 2, 3 of actual document.
View the full content.View Full Document
NONPARAMETRIC CLASSIFICATION AND ERROR ESTIMATION
0 0 123 views
 Pages:
 10
 School:
 Carnegie Mellon University
 Course:
 Cs 10701  Introduction to Machine Learning
Introduction to Machine Learning Documents

12 pages

16 pages

17 pages

Predicting Realvalued outputs
51 pages

Bayesian Networks (Structure) Learning
11 pages

40 pages

Bayesian Networks – Representation
46 pages

15 pages

20 pages

Machine Learning, Function Approximation and Version Spaces
33 pages

30 pages

10 pages

EM for HMMs a.k.a. The BaumWelch Algorithm
28 pages

Bayesian Networks: Independencies and Inference
22 pages

15 pages

CoTraining for Semi supervised learning (cont.)
51 pages

58 pages

Markov Decision Processes (MDPs)
51 pages

41 pages

Graphical Models and Bayesian Networks
11 pages

20 pages

16 pages

22 pages

EM for HMMs a.k.a. The BaumWelch Algorithm
35 pages

Logistic Regression, cont. Decision Trees
32 pages

Machine Learning, Decision Trees, Overfitting
31 pages

42 pages

13 pages

45 pages

51 pages

59 pages

20 pages

24 pages

21 pages

25 pages

38 pages

20 pages

26 pages

13 pages

44 pages

33 pages

SemiSupervised Learning and Text Analysis
53 pages

36 pages

5 pages

26 pages

18 pages

18 pages

SVM as a Convex Optimization Problem
10 pages

11 pages

22 pages

51 pages

Bayesian Networks – Inference (continued) Learning
36 pages

14 pages

Bayes Nets Representation: joint distribution and conditional independence
16 pages

24 pages

20 pages

Time series, HMMs, Kalman Filters
30 pages

11 pages

Unsupervised Learning Clustering Kmeans
23 pages

16 pages

Markov Decision Processes (MDPs)
48 pages

20 pages

62 pages

PAClearning, VC Dimension and Margin based Bounds (cont.)
39 pages

An introduction to graphical models
19 pages

20 pages

Simple Model Selection Cross Validation Regularization
15 pages

30 pages

Matrix MLE for Linear Regression
4 pages

39 pages

Feature Selection for fMRI Classification
8 pages

Inference in Bayesian Networks
31 pages

40 pages

14 pages

19 pages

NONPARAMETRIC DENSITY ESTIMATION
23 pages

18 pages

37 pages

SVMs, Duality and the Kernel Trick (cont.)
59 pages

Computational biology: Sequence alignment and profile HMMs
42 pages

Bayesian point estimation Gaussians Linear Regression BiasVariance Tradeoff
20 pages

13 pages

Graphical Models meet Margin based Learning
45 pages

10 pages

26 pages

Unsupervised Learning Clustering Kmeans
22 pages

Dimensionality reduction (cont.)
58 pages

17 pages

Logistic Regression (Continued) Generative v. Discriminative Decision Trees
62 pages

27 pages

50 pages

15 pages

What’s learning, revisited Overfitting Bayes optimal classifier Naïve Bayes
43 pages

48 pages

Markov Decision Processes (MDPs)
26 pages

24 pages

16 pages

40 pages

Bayesian Networks – Representation (cont.) Inference
50 pages

23 pages

20 pages

26 pages

28 pages

8 pages

What’s learning? Point Estimation
34 pages

What’s learning? Point Estimation
22 pages

Bayesian Networks – Representation
31 pages

Simple Model Selection Cross Validation Regularization Neural Networks
53 pages

Computational Learning Theory Part 2
16 pages

34 pages

15 pages

29 pages

SVMs, Duality and the Kernel Trick
61 pages

3 pages

What’s learning? Point Estimation
18 pages

Recitation: SVD and dimensionality reduction
21 pages

58 pages

50 pages

11 pages

Logistic Regression (Continued) Generative v. Discriminative Decision Trees
34 pages

11 pages

7 pages

9 pages

23 pages

Support Vector Machines Kernel Methods
22 pages

Bayesian Networks – (Structure) Learning
85 pages

Markov Decision Processes (MDPs)
48 pages

35 pages

Practical Issues in Learning  Overfitting and Model Selection
23 pages

PAClearning, VC Dimension and Marginbased Bounds
32 pages

Learning a probabalistic model of rainfall using graphical models
8 pages

35 pages

The Optimized Physical Model for Real Rover Vehicle
8 pages

52 pages

7 pages

CoTraining for Semi supervised learning (cont.)
52 pages

Machine Learning, Decision Trees, Overfitting
38 pages

49 pages

22 pages

7 pages

2 pages

14 pages

31 pages

16 pages

18 pages

21 pages

Tree Augmented Naïve Bayesian Classifier with Feature Selection for fMRI Data
8 pages

Time series, HMMs, Kalman Filters
30 pages

EM for HMMs a.k.a. The BaumWelch Algorithm
28 pages

35 pages

Bayes Nets DSeparation & Inference
22 pages

22 pages

37 pages

Bayesian Networks – Representation
31 pages

5 pages

47 pages

EM for HMMs a.k.a. The BaumWelch Algorithm
36 pages

27 pages

24 pages

Bayes optimal classifier Naïve Bayes What’s learning, revisited
12 pages

Simple Model Selection Cross Validation Regularization
14 pages

22 pages

Naive Bayes and Logistic Regression
27 pages

Naïve Bayes with Continuous (variables) Logistic Regression
51 pages

Computational Learning Theory and Model Selection
19 pages

10 pages

PAClearning, VC Dimension and Marginbased Bounds
59 pages

Artificial Neural Networks to learn f: X Y
13 pages

17 pages

15 pages

Gaussians Linear Regression BiasVariance Tradeoff
17 pages

32 pages

Bayesian Networks – Inference (continued) Learning
27 pages

Bayesian Networks –(Structure) Learning
85 pages

42 pages

Inductive Programming by Expectation Maximization Algorithm
8 pages

19 pages

20 pages

SVMs, Duality and the Kernel Trick
14 pages

19 pages

Logistic Regression (Continued) Generative v. Discriminative Decision Trees
34 pages

25 pages

Bayesian Networks – Inference (continued) Learning
27 pages

Linear Regression BiasVariance Tradeoff
15 pages

Bayesian Networks – Structure Learning (cont.)
84 pages

Learning from Labeled and Unlabeled Data
54 pages

16 pages

25 pages

32 pages

Bayesian Networks (Structure) Learning
17 pages

27 pages

11 pages

16 pages

56 pages

45 pages

42 pages

boostingxvalidationregularization
47 pages

6 pages

10 pages

50 pages

14 pages

12 pages

9 pages

24 pages

PAClearning, VC Dimension (cont.)
23 pages

15 pages

42 pages

29 pages

15 pages

Expectation Maximization, and Learning from Partly Unobserved Data
45 pages

gaussiansregressionannotated
15 pages

5 pages

51 pages

15 pages

Linear Regression and Artificial Neural Networks
16 pages

3 pages

54 pages

74 pages

Logistic Regression, Generative and Discriminative Classifiers
28 pages

26 pages

37 pages

37 pages

Bayesian Networks – Representation
45 pages

Decision Trees, cont. Boosting
18 pages

8 pages

Unsupervised learning or Clustering (cont.) – Kmeans
63 pages

Simple Model Selection Cross Validation Regularization Neural Networks
20 pages

What’s learning? Point Estimation
18 pages

68 pages

Textual entailment in the domain of physics
7 pages

Inferring Depth from Single Images in Natural Scenes
8 pages

13 pages

Markov Decision Processes (MDPs)
29 pages

12 pages

11 pages

14 pages

35 pages

36 pages

14 pages

Hierarchical Bayesian Models for Text Classification
7 pages

Instancebased Learning (a.k.a. nonparametric methods)
16 pages

What’s learning, revisited Overfitting
26 pages

The Boosting Approach to Machine Learning An Overview
23 pages

24 pages

Bayesian Networks – Structure Learning
84 pages

36 pages

22 pages

28 pages

Feature selection for grasp classification
8 pages

20 pages

37 pages

Dimensionality Reduction_03_31_2011_ann
11 pages

DTrees And Over fitting1112011_final
20 pages

5 pages

13 pages

49 pages

8 pages

13 pages

26 pages
Sign up for free to view:
 This document and 3 million+ documents and flashcards
 High quality study guides, lecture notes, practice exams
 Course Packets handpicked by editors offering a comprehensive review of your courses
 Better Grades Guaranteed
Chapter 7 NONPARAMETRIC CLASSIFICATION AND ERROR ESTIMATION After studying the nonparametric density estimates in Chapter 6 we are now ready to discuss the problem of how to design nonparumetric clussifiers and estimate their classification errors A nonparametric classifier does not rely on any assumption concerning the structure of the underlying density function Therefore the classifier becomes the Bayes classifier if the density estimates converge to the true densities when an infinite number of samples are used The resulting error is the Bayes error the smallest achievable error given the underlying distributions As was pointed out in Chapter 1 the Bayes error is a very important parameter in pattern recognition assessing the classifiability of the data and measuring the discrimination capabilities of the features even before considering what type of classifier should be designed The selection of features always results in a loss of classifiability The amount of this loss may be measured by comparing the Bayes error in the feature space with the Bayes error in the original data space The same is true for a classifier The performance of the classifier may be compared with the Bayes error in the original data space However in practice we never have an infinite number of samples and due to the finite sample size the density estimates and subsequently the estimate of the Bayes error have large biases and variances particularly in a high dimensional space 300 7 Nonparametric Classification and Error Estimation 301 A similar trend was observed in the parametric cases of Chapter 5 but the trend is more severe with a nonparametric approach These problems are addressed extensively in this chapter Both Parzen and kNN approaches will be discussed These two approaches offer similar algorithms for classification and error estimation and give similar results Also the voting kNN procedure is included in this chapter because the procedure is very popular although this approach is slightly different from the kNN density estimation approach 7 1 General Discussion Parzen Approach Classifier As we discussed in Chapter 3 the likelihood ratio classfier is given by InpI X p2 X r where the threshold t is determined in various ways depending on the type of classifier to be designed e g Bayes NeymanPearson minimax etc In this chapter the true density functions are replaced by their estimates discussed in Chapter 6 When the Parzen density estimate with a kernel function IC is used the likelihood ratio classifier becomes where S X X X 2 X is the given data set Equation 7 1 classifies a test sample X into either o1or 02 depending on whether the lefthand side is smaller or larger than a threshold t Error estimation In order to estimate the error of this classifier from the given data set S we may use the resubstitution R and leave one out L methods to obtain the lower and upper bounds for the Bayes error In the R method all available samples are used to design the classifier and the same sample set is tested Therefore when a sample Xi from o1is tested the following equation is used 302 Introduction to Statistical Pattern Recognition If is satisfied Xi is correctly classified and if is satisfied Xi is misclassified The R estimate of the q error cIR is obtained by testing Xi Xyl counting the number of misclassified samples and dividing the number by N I Similarly 2R is estimated by testing xi2 x On the other hand when the L method is applied to test Xi1 Xi must be excluded from the design set Therefore the numerator of 7 2 must be replaced by Again Xi k l N I are tested and the misclassified samples are counted Note that the amount subtracted in 7 3 K 0 does not depend on k When an 02 sample is tested the denominator of 7 2 is modified in the same way Typical kernel functions such as 6 3 generally satisfy 2 0K Y and subsequently 2 0pj Y Then That is the L density estimate is always smaller than the R density estimate Therefore the left hand side of 7 2 is larger in the L method than in the R method and consequently Xi has more of a chance to be misclassified Also note that the L density estimate can be obtained from the R density estimate by simple scalar operations subtracting K 0 and dividing by N 1 Therefore the computation time needed to obtain both the L and R density estimates is almost the same as that needed for the R density estimate alone 7 Nonparametric Classification and Error Estimation 303 H N Approach Classifier Using the kNN density estimate of Chapter 6 the likelihood ratio classifier becomes k l l N 2 lX2I dz xk N x n In dI Xil NN X In k 2 1 N I IC 112 0 r wz 7 5 where n 12r1 n 2 1 IC l 2d from B l and df Y X Y X TC l Y X In order to classify a test sample X the k l t h NN from oI and the k 2 t h NN from o2 are found the distances from X to these neighbors are measured and these distances are inserted into 7 5 to test whether the left hand side is smaller or larger than t In order to avoid unnecessary complexity k k2 is assumed in this chapter 11 Error estimation The classification error based on a given data set S can be estimated by using the L and R methods When Xi1 from o1is tested by the R method Xi1 must be included as a member of the design set Therefore when the kNN s of Xi are found from the wI design set Xi itself is included among these kNN s Figure 7 1 shows how the kNN s are selected and how the distances to the kth NN s are measured for k 2 Note in Fig 7 1 that the locus of points equidistant from Xi becomes ellipsoidal because the distance is normalized by E Also since C l C2 in general two different ellipsoids are used for o and 02 In the R method Xi1 and Xi are the nearest and second nearest neighbors of Xi1 from o1 while X and X are the nearest and second nearest neighbors of Xi1 from 02 Thus On the other hand in the L method Xi is no longer considered a member of the design set Therefore X h and X g N are selected as the nearest and second nearest neighbors of Xi from 0 The selection of o2neighbors is the same as before Thus Introduction to Statistical Pattern Recognition 304 I Fig 7 1 Selection of neighbors 7 7 Obviously d I X N Xl 2 d X k Xl making the left hand side of 7 7 larger than the left hand side of 7 6 Thus Xi is more likely to be misclassified in the L method than in R method Also note that in order to find the NN sample the distances to all samples must be computed and compared Therefore when …
View Full Document