Constructing classification weights matrices for pattern recognition systems using reduced element feature subsets

Claim 3

A method as set forth in claim 1 wherein matrices Z and W are constructed utilizing an iterated supervised training process.

Claim 4

A method as set forth in claim 1 wherein said step of searching is performed utilizing a genetic search process.

Claim 5

A method as set forth in claim 1 wherein said step of searching is performed deterministically.

Claim 6

A method as set forth in claim 1 wherein submatrix Z' is an array whose columns are the columns of Z selected by the subset S and further wherein submatrix W' is an array whose rows and columns are the rows and columns of W selected by subset S.

Claim 7

A method as set forth in claim 1 wherein said pattern recognition system is an optical character recognition system and said input device is an optical character capture device.

Claim 8

A method as set forth in claim 1 wherein said pattern recognition system is a sonar detection system and said input device is a sonar signal capture device.

Claim 9

A method as set forth in claim 1 wherein said pattern recognition system is a finger print identification system and said input device is a finger print scanner.

Claim 10

A method as set forth in claim 1 wherein said pattern recognition system is a face print identification system and said input device is a face scanner.

Claim 11

A method as set forth in claim 1 wherein said pattern recognition system is a voice print identification system and said input device is a voice capture device.

Claim 14

A method as set forth in claim 11 wherein said pattern recognition system is an optical character recognition system.

Claim 15

A method as set forth in claim 11 wherein matrices Z and W are constructed utilizing an iterated supervised training process.

Claim 16

A method as set forth in claim 11 wherein said step of searching is performed utilizing a genetic search process.

Claim 19

A method as set forth in claim 15 wherein classification efficiency is defined as the percentage of characters in said predefined set of examplars that said linear discriminator weights matrix correctly identifies.

Claim 20

A pattern recognition system, comprising: a programmable digital computer; and an input device coupled to said digital computer and providing a set of patterns to be classified by said system, to said computer in a normalized form; said programmable digital computer comprising means for constructing a classification weights matrix A' for said system from a first set of signals, available to said computer, representing a correlation matrix Z between a predetermined set of exemplar feature vectors, each representing the values of a predefined set of F features, and a set of classification target vectors corresponding to said feature vectors, and from a second set of signals, available to said computer, representing the autocorrelation matrix W of said set of exemplar feature vectors, and means for performing pattern recognition of unclassified patterns using the classification weights matrix, wherein said means for constructing further comprises: (c1) means for determining a classification efficiency of selected subsets of said set of F features, wherein said means for determining the classification efficiency for a given subset further comprises: (c11) means for constructing, utilizing said given subset, submatrices of said correlation and autocorrelation matrices; (c12) means for forming a weights matrix for a linear discriminator, in the vector space of said given subset of features, as a function of said submatrices, and (c13) means for testing said linear discriminator weights matrix on a predefined set of exemplars to yield the classification efficiency of said given subset; (c2) means for searching a space of f-element subsets of said set of F features, where f is prespecified and less than F, for an f element subset having a maximum classification efficiency; (c3) means for selecting one of the f-element subsets in said space as having a maximum classification efficiency as a result of the search performed by said means for searching; and (c4) means for defining said classification weights matrix A' as the product of submatrix Z' of said correlation matrix Z, and an inverse of submatrix W' of said autocorrelation matrix W, where submatrices Z' and W' are constructed as a function of said subset having the maximum classification efficiency.

Claim 21

A pattern recognition system, comprising: a programmable digital computer; and an input device coupled to said digital computer and providing a set of patterns to be classified by said system, to said computer in a normalized form; said programmable digital computer comprising means for constructing a classification weights matrix A' for said system from a first set of signals, available to said computer, representing a correlation matrix Z between a predetermined set of exemplar feature vectors, each representing the values of a predefined set of F features, and a set of classification target vectors corresponding to said feature vectors, and from a second set of signals, available to said computer, representing the autocorrelation matrix W of said set of exemplar feature vectors, and means for performing pattern recognition of unclassified patterns using the classification weights matrix, wherein said means for constructing further comprises: (c1) means for determining a classification efficiency of selected subsets of said set of F features, wherein said means for determining the classification efficiency for a given subset further comprises: (c11) means for constructing, utilizing said given subset, submatrices of said correlation and autocorrelation matrices; (c12) means for forming a weights matrix for a linear discriminator, in the vector space of said given subset of features, as a function of said submatrices, and (c13) means for testing said linear discriminator weights matrix on a predefined set of exemplars to yield the classification efficiency of said given subset; (c2) means for searching a space of f-element subsets of said set of F features, where f is prespecified and less than F, for an f element subset having a maximum classification efficiency; (c3) means for selecting one of the f-element subsets in said space as having a maximum classification efficiency as a result of the search performed by said means for searching; and (c4) means for defining said classification weights matrix A' as the product of submatrix Z' of said correlation matrix Z, and an inverse of submatrix W' of said autocorrelation matrix W, where submatrices Z' and W' are constructed as a function of said subset having the maximum classification efficiency.

Claim 22

Apparatus as set forth in claim 17 wherein said pattern recognition system is an optical character recognition system.

Claim 23

Apparatus as set forth in claim 17 wherein said means for searching is operative to perform a genetic search.

Claim 26

A method as set forth in claim 20 further comprising the step of iteratively performing, so long as one of a set of search termination conditions has not been met, a search, over the space of f-element subsets of said predetermined set of said set of F features, for an individual which satisfies a stopping condition.

Claim 27

A method as set forth in claim 21 wherein said set of search termination conditions include stopping conditions that are based on the evaluated fitness of an individual along with stopping conditions that are not based on the evaluated fitness of an individual.

Claim 28

A method as set forth in claim 21 wherein said search is a genetic search.

Claim 29

A method as set forth in claim 23 wherein said genetic search comprises the steps of: (a) randomly selecting two disjoint sets of individuals, each consisting of t individuals, where t is<<P, to determine the most fit individual in each disjoint subset to serve as parents in the genetic search; (b) determining the most fit individual in each disjoint subset to serve as parents; (c) forming two children from the parents determined in step (b) to be most fit; (d) evaluating the fitness of the children; and (e) entering the new children into said population displacing the two least fit individuals thereby maintaining the population at fixed size P.

Claim 30

A method as set forth in claim 24 further comprising the step of mutating the children prior to performing said step of evaluating the fitness of said children.