Design of pattern classifiers using optimization techniques

Abstract

Of the various approaches to the design of pattern classifiers, those that depend on a given finite set of patterns have received considerable attention in the literature. These approaches fall into two categories depending upon whether or not the class affiliation of patterns in the given set is known and often aim at a design which is optimal in some predefined sense. The investigations reported in this thesis pertain to the above two problems. The problem of designing a pattern classifier given a finite set of patterns and their class affiliations reduces to the solution of simultaneous linear inequalities. Algorithms for finding a solution to linear inequalities are proposed. Specifically, the algorithms are based on the conjugate gradient method for optimization (with and without constraints) of an error function. Convergence of the proposed procedures to a solution is established and computer simulation results are presented to bring out their merits on practical problems. The problem of designing a pattern classifier with a given finite set of patterns without class affiliations is posed as the problem of clustering, and algorithms are proposed for finding the clusters. Computer simulation results are presented. One of the algorithms is adaptive in nature and processes the data sequentially. It also turns out to be a generalization of Chernoff's procedure. Some modifications are discussed. The second algorithm is derived from an optimization point of view and is shown to converge to a local minimum of a criterion function. The structure of the various classifiers obtained by the proposed procedures is linear. Linear classifiers are realized by a set of weights. In practice, the measuring devices can cause the values of features of patterns as well as the values of weights to be erroneous due to random fluctuations. A reliable design is desired under these circumstances, which it is shown, leads to solution of nonlinear programming problems. Applications of proposed methods to design of handwritten letter classifiers as well as of a learning controller for a re-entry vehicle are presented.