On dimensionality, sample size, and classification error of nonparametric linear classification algorithms

Abstract

This paper compares two nonparametric linear classification algorithms $the zero empirical error classifier and the maximum margin classifier - with parametric linear classifiers designed to classify multivariate Gaussian populations. Formulae and a table for the mean expected probability of misclassification MEP/sub N/ are presented. They show that the classification error is mainly determined by N/p, a learning-set size/dimensionality ratio. However, the influences of learning-set size on the generalization error of parametric and nonparametric linear classifiers are quite different. Under certain conditions the nonparametric approach allows us to obtain reliable rules, even in cases where the number of features is larger than the number of training vectors.