Classification algorithms in pattern recognition

Linear and nonlinear methods of pattern classification which have been found useful in laboratory investigations of various recognition tasks are reviewed. The discussion includes correlation methods, maximum likelihood formulations with independence or normality assumptions, the minimax Anderson-Bahadur formula, trainable systems, discriminant analysis, optimal quadratic boundaries, tree and chain expansions of binary probability density functions, and sequential decision schemes. The area of applicability, basic assumptions, manner of derivation, and relative computational complexity of each algorithm are described. Each method is illustrated by means of the same two-class two-dimensional numerical example. The "training set" in this example comprises four samples from either class; the "test set" is the set of all points in the normal distributions characterized by the sample means and sample covariance matrices of the training set. Procedural difficulties stemming from an insufficient number of samples, various violations of the underlying statistical models, linear nonseparability, noninvertible covariance matrices, multimodal distributions, and other experimental facts of life are touched on.