Method and arrangement for pattern recognition on the basis of statistics

• US 6,205,247 B1
• Filed: 12/08/1998
• Issued: 03/20/2001
• Est. Priority Date: 06/08/1996
• Status: Expired due to Fees

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: Franke, Jürgen, Breuer, Thomas, Hanisch, Wilfried
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Mariam, Daniel G.
• Application Number:
  US09/202,027
• Time in Patent Office: 833 Days
• Field of Search: 382/155, 382/156, 382/157, 382/159, 382/224, 382/228, 382/227
• US Class Current: 382/228
• CPC Class Codes: G06F 18/24317 Piecewise classification, i.e. whereby each classification requires several discriminant rules
• CPC Class Codes: G06F 18/2453 non-linear, e.g. polynomial classifier

Abstract

A method and an arrangement are presented for pattern recognition on the basis of statistics. According to the method, for an object to be recognized on the basis of a complete set of two-class or multiclass classifiers, the association with each target class of the class set is estimated with a numerical value that is produced by cascaded use of polynomial classifiers. According to the invention, on a learning sample in which all class patterns to be recognized are sufficiently represented, there is a selection, from all the two-class or multiclass classifiers by way of their estimation vector spectrum, of those two-class or multiclass classifiers with estimations contributing the most to minimize a scalar quantity calculated over the estimation vector spectrum and having high separating relevance. The selected two-class or multiclass classifiers are subsequently used to form, via an expanded learning sample, estimation vectors from which expanded characteristic vectors are produced by polynomial linking. An evaluation classifier is formed on the basis of said characteristic vectors for estimating all target classes.

Claims

1. A method of pattern recognition on the basis of statistics, which, for an object to be recognized, estimates an association of each target class of a class set with a numerical value on the basis of a complete ensemble of two- or multi-class classifiers, the numerical value resulting from cascaded application of polynomial classifiers, comprising the steps of:

selecting the two- or multi-class classifiers whose estimates contribute the most, with high separation relevance, to minimizing a scalar measure calculated over an estimation-vector spectrum, from all two- or multi-class classifiers, over their estimation-vector spectrum on a learning sample in which all class patterns to be recognized are represented sufficiently;

using the selected two- or multi-class classifiers to form estimate vectors over an expanded learning sample;

using said estimate vectors to generate feature vectors that have been expanded through polynomial linking; and

on the basis of said feature vectors, calculating an assessment classifier for estimating onto all target classes.

2. The method according to claim 1, wherein said step of selecting includes the step of using a sum of error squares in a discrimination space as said scalar measure.

3. The method according to claim 1, wherein said step of selecting includes the step of using entropy in a distribution space as said scalar measure, wherein frequency of appearance of each feature state of the two- or multi-class classifier estimates is determined over all feature states.

4. The method according to claim 1, further comprising the steps of:

dividing a large target-class quantity into a plurality of target-class quantities, for which said selecting of the two- or multi-class classifiers is performed, and wherein, from this, the assessment classifier is generated; and

determining a resulting total estimate from results of the assessment classifiers.

5. The method according to claim 4, wherein said determining step includes the step of forming a Cartesian-expanded product vector from result vectors of the assessment classifiers, from which Cartesian-expanded product vector a quadratic assessment classifier that determines the total estimate is formed.

6. The pattern-recognition method according to claim 4, wherein said determining step includes the steps of forming a Cartesian-expanded product vector from result vectors of the assessment classifiers;

transferring said Cartesian-expanded product vector into a transformed vector by means of a subspace transformation using a transformation matrix having a corresponding eigenvalue distribution;

adapting a quadratic classifier using only the most critical components of said transformed vector, which components correspond to the eigenvalue distribution of the transformation matrix; and

using the adapted quadratic classifier, mapping the transformed and reduced vector onto target classes for an estimated value.

7. The method according to claim 4, further comprising the step of, prior to activation of the step of selecting the two- or multi-class classifiers, a meta-class classifier that is trained over groups of class quantities generates estimates over the groups, which contain characters;

and wherein;

said step of selecting includes the step of activating the two- or multi-class classifiers for the characters of the groups whose estimated values lie above an established threshold; and

said determining step includes the step of linking the group estimates to the estimates of the respectively-associated character-assessment classifiers for the character classes contained in the respective group according to a unified rule such that the sum over all character estimates linked in this manner yields a number that can be normalized to 1.

8. An arrangement for pattern recognition on the basis of statistics, which, for an object to be recognized, estimates an association of each target class of a class set with a numerical value on the basis of a complete ensemble of two- or multi-class classifiers, the numerical value resulting from cascaded application of polynomial classifiers, comprising:

means for statistically-optimized selection of the two- or multi-class classifiers whose estimates contribute the most, with high separation relevance, to minimizing a scalar measure calculated over an estimation-vector spectrum, from a complete ensemble of all two- or multi-class classifiers based on their estimation-vector spectrum over a learning sample in which all class patterns to be recognized are represented to a sufficient extent;

means for generating polynomial-expanded feature vectors that represent the order of the system of selected two- or multi-class classifiers, said polynomial-expanded feature vectors being formed over an expanded learning sample, said expanding carried out by means of polynomial linking; and

means for calculating an assessment classifier that uses the feature vectors of the system of selected two- or multi-class classifiers to calculate an estimation vector that, for each target class, contains a numerical value as an approximated conclusion probability regarding the association of a classified pattern with said class of patterns.

9. A method of pattern recognition for estimating input characters using probabilities of their memberships in n character classes, comprising the steps of:

performing an optimal selection procedure, the optimal selection procedure determining from a given system of N statistically non-independent classifiers a set of K classifiers that contribute the most to minimizing a scalar classification measure for all comparable subsystems of fixed dimension K, where K<

N;

adjusting K such that a linear K-dimensional output vector of the subsystem can be polynomially extended to at least quadratic terms below a predetermined magnitude of terms; and

constructing an optimal assessment classifier that uses the polynomially-extended output vector of the optimal subsystem as its input and maps it to a final probability vector for the n classes as its output.