Linear Decision Functions, with Application to Pattern Recognition

Abstract

Many pattern recognition machines may be considered to consist of two principal parts, a receptor and a categorizer. The receptor makes certain measurements on the unknown pattern to be recognized; the categorizer determines from these measurements the particular allowable pattern class to which the unknown pattern belongs. This paper is concerned with the study of a particular class of categorizers, the linear decision function. The optimum linear decision function is the best linear approximation to the optimum decision function in the following sense: 1) "Optimum" is taken to mean minimum loss (which includes minimum error systems). 2) "Linear" is taken to mean that each pair of pattern classes is separated by one and only one hyperplane in the measurement space. This class of categorizers is of practical interest for two reasons: 1) It can be empirically designed without making any assumptions whatsoever about either the distribution of the receptor measurements or the a priori probabilities of occurrence of the pattern classes, providing an appropriate pattern source is available. 2) Its implementation is quite simple and inexpensive. Various properties of linear decision functions are discussed. One such property is that a linear decision function is guaranteed to perform at least as well as a minimum distance categorizer. Procedures are then developed for the estimation (or design) of the optimum linear decision function based upon an appropriate sampling from the pattern classes to be categorized.