Browse Prior Art Database

Decision Function Design Algorithm for Pattern Recognition

IP.com Disclosure Number: IPCOM000083860D
Original Publication Date: 1975-Aug-01
Included in the Prior Art Database: 2005-Mar-01
Document File: 4 page(s) / 50K

Publishing Venue

IBM

Related People

King, JH: AUTHOR [+2]

Abstract

There is now broad understanding of pattern identification based on the theory of approximating polynomial discriminate functions. However, many, if not most, of the algorithms that theoretically can generate the optimum set of parameters (coefficients) for a specified structure are computationally unattractive (too much time), or even impossible for systems having a large number of parameters.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 4

Decision Function Design Algorithm for Pattern Recognition

There is now broad understanding of pattern identification based on the theory of approximating polynomial discriminate functions. However, many, if not most, of the algorithms that theoretically can generate the optimum set of parameters (coefficients) for a specified structure are computationally unattractive (too much time), or even impossible for systems having a large number of parameters.

Often it has proven convenient and practical to fix the structure of the decision network at the outset, and then attempt to determine that set of parameters which optimizes the performance within this constraint. Techniques for calculating the values of the parameters of decision structures that minimize various types of convex objective functions (error functions) fall into two general classes.

In the first class there are found two subclasses, parametric and nonparametric methods. With the first subclass, the assumption is made that the form of the underlying probability distributions are known and the problem becomes one of estimating the parameters of the distributions from each of the several classes of input finite samples. With the second subclass, no assumption about the form of the underlying distributions is made, except that they can be suitably approximated by a weighted sum of distributions of simple form.

In the other major class of decision structure design techniques, there are found the various adaptive methods. Here the usual approach is to fix the form of the decision structure (network) and then employ some type of iteration error correction procedure, which will approximately minimize the average error rate on the design sample. Theory has predicted and practice has shown that good approximations to optimal decision procedures are realizable within the framework or linear structures, provided that the function or transformation realized by the preprocessing (feature detection) belongs to a certain class.

Within the framework of linear structures, there are eseentially two general ways to calculate parameter values. The first is based on estimation of joint probability from the samples of patterns in each class. The second is comprised of various adaptive error correction algorithms. From practical experience it has been found that the adaptive schemes not only yield high performance, but are quite economical of design time. The present algorithm is an iterative or adaptive algorithm. This adaptive algorithm has the advantages of greater speed of convergence, and requires smaller design samples than earlier adaptive algorithms and provides better performance from the converged design.

The following is a mathematical description of the design algorithm followed by a flow chart of the algorithm, followed by a more detailed step-by-step description. (Basic notation is appended.)

(Image Omitted)

The following steps are carried out as indicated on the flow chart of F...