Adaptive algorithms for designing two-category linear pattern classifiers have been widely used on nonseparable pattern sets even though they do not directly minimize the number of classification errors and their optimality for pattern classification is not completely known. Many of these algorithms have been shown to be asymptotically optimal for patterns from Gaussian distributions with equal-covariance matrices. However, their relative efficiencies for design with a finite number of patterns have not been known. This paper uses truncated Taylor series expansions to evaluate the misadjustment, or extra probability of error, that results when these algorithms are used to design a linear classifier with a finite number of patterns. The expressions have been evaluated for three algorithms-- the fixed-increment error-correction algorithm, the relaxation error-correction algorithm, and the least-mean-square (LMS) algorithm--used with patterns from Gaussian distributions with equal-covariance matrices.

The results of a study undertaken to determine the feasibility of automatic interpretation of ship photographs using the spatial moments of the image as features to characterize the image are reported. The photo interpretation consisted of estimating the location, orientation, dimensions, and heading of the ship. The study used simulated ship images in which the outline of the ship was randomly filled with black and white cells to give a low-resolution high-contrast image of the ship such as might be obtained by a high-resolution radar. The estimates were made using polynomials of invariant moments formed by transformations of the original spatial moments, e. g., density-invariant moments, central moments, rotation-invariant moments, etc. The transformations to invariant moments were chosen using physical reasoning. The best moments for the polynomials were chosen using linear regression. The performance of the method of moments on these low-resolution images was found to be comparable to that of a human photointerpreter and to certain heuristic techniques that would be more difficult to implement than the method of moments.

Adaptive algorithms for designing two-category linear pattern classifiers have been developed and studied in recent years. When the pattern sets are nonseparable, the adaptive algorithms do not directly minimize the number of classification errors, which is the usual goal in pattern classifier design: furthermore, they also are not minimum-error optimal, i.e., they do not generally minimize the probability of error for the classifier. However, the least-mean-square (LMS) adaptive algorithm has been shown to yield classifiers that are asymptotically minimum-error optimal for patterns from Gaussian equal-covariance distributions. A technique is also known for designing asymptotically minimum-error optimal linear classifiers for patterns from Gaussian distributions with unequal covariance matrices. This paper shows that classifiers designed with the "error-correction" algorithms have these same asymptotic properties: the error-correction algorithms are asymptotically minimum-error optimal for patterns drawn from Gaussian equal-covariance distributions and they can be used to design asymptotically minimum-error optimal linear classifiers for patterns from Gaussian distributions with unequal covariance matrices. In addition, because the error-correction algorithms use only part of the patterns in determining the classifier weights, they are asymptotically minimum-error optimal for patterns from distributions that have only Gaussian tails in the regions where their patterns are misclassified or close to misclassified, and that are almost arbitrary elsewhere.

This note derives a relationship between the weights of certain types of R-category linear pattern classifiers and the weights of R two-category linear pattern classifiers. With this relationship R-category classifiers can be designed with computer algorithms for two-category classifier design. Previously proposed R-category classifiers have had to be designed with special R-category classifier design aigorithms.

Abstract—A common nonparametric method for designing linear discriminant functions for pattern classification is the iterative, or "adaptive," weight adjustment procedure, which designs the discriminant function to do well on a set of typical patterns. This paper presents a linear programming formulation of discriminant function design which minimizes the same objective function as the "fixed-increment" adaptive method. With this formulation, as with the adaptive methods, weights which tend to minimize the number of classification errors are computed for both separable and nonseparable pattern sets, and not just for separable pattern sets as has been the emphasis in previous linear programming formulations.