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 Real-valued 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 Baum-Welch Algorithm
28 pages
-
Bayesian Networks: Independencies and Inference
22 pages
-
15 pages
-
Co-Training 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 Baum-Welch 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
-
Semi-Supervised 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 K-means
23 pages
-
16 pages
-
Markov Decision Processes (MDPs)
48 pages
-
20 pages
-
62 pages
-
PAC-learning, 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 Bias-Variance Tradeoff
20 pages
-
13 pages
-
Graphical Models meet Margin- based Learning
45 pages
-
10 pages
-
26 pages
-
Unsupervised Learning Clustering K-means
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
-
PAC-learning, VC Dimension and Margin-based 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
-
Co-Training 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 Baum-Welch Algorithm
28 pages
-
35 pages
-
Bayes Nets D-Separation & Inference
22 pages
-
22 pages
-
37 pages
-
Bayesian Networks – Representation
31 pages
-
5 pages
-
47 pages
-
EM for HMMs a.k.a. The Baum-Welch 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
-
PAC-learning, VC Dimension and Margin-based Bounds
59 pages
-
Artificial Neural Networks to learn f: X Y
13 pages
-
17 pages
-
15 pages
-
Gaussians Linear Regression Bias-Variance 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 Bias-Variance 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
-
boosting-xvalidation-regularization
47 pages
-
6 pages
-
10 pages
-
50 pages
-
14 pages
-
12 pages
-
9 pages
-
24 pages
-
PAC-learning, VC Dimension (cont.)
23 pages
-
15 pages
-
42 pages
-
29 pages
-
15 pages
-
Expectation Maximization, and Learning from Partly Unobserved Data
45 pages
-
gaussians-regression-annotated
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.) – K-means
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
-
Instance-based Learning (a.k.a. non-parametric 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 fitting-1-11-2011_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