Method and apparatus for hierarchical input classification using a neural network

• US 5,638,491 A
• Filed: 01/23/1995
• Issued: 06/10/1997
• Est. Priority Date: 06/19/1992
• Status: Expired due to Term

• Current Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Original Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Inventors: Moed, Michael C.
• Primary Examiner(s): Davis, George B.
• Application Number:
  US08/376,819
• Time in Patent Office: 869 Days
• Field of Search: 395/23, 395/20, 395/24, 395/11, 382/156
• US Class Current: 706/20
• CPC Class Codes: G06F 18/23213 with fixed number of clusters, e.g. K-means clustering
• CPC Class Codes: G06F 18/24137 Distances to cluster centroïds
• CPC Class Codes: G06F 18/2414 Smoothing the distance, e.g. radial basis function networks [RBFN]
• CPC Class Codes: G06F 18/24143 Distances to neighbourhood prototypes, e.g. restricted Coulomb energy networks [RCEN]
• CPC Class Codes: G06V 30/19107 Clustering techniques
• CPC Class Codes: G06V 30/19173 Classification techniques

Abstract

An input is classified into one of a plurality of possible outputs. A top-level classifier generates an approximate identification for the input as one of the possible outputs and selects two or more neural networks corresponding to the approximate identification. The selected neural networks generate two or more identifications for the input as one or more of the possible outputs. A postprocessor classifies the input as one of the possible outputs in accordance with the two or more identifications of the selected neural networks. According to an alternative embodiment, a top-level classifier selects a subset of neurons of a neural network and the subset of neurons identifies the input as one of the possible outputs.

Claims

1. A method for classifying an input into one of a plurality of possible outputs, comprising the steps of:

(a) applying a top-level classifier to the input to generate an approximate identification for the input as one of the possible outputs;

(b) using the approximate identification to select a subset of available cluster classifiers;

(c) applying said selected cluster classifiers to the input to generate two or more identifications for the input as one or more of the possible outputs; and

(d) classifying the input as one of the possible outputs in accordance with said two or more identifications.

2. The method of claim 1, wherein:

each of the cluster classifiers employs one or more neurons; and

at least two of the cluster classifiers share a common output.

3. The method of claim 1, wherein step (a) comprises the step of implementing K-means clustering.

4. The method of claim 1, wherein at least one of the cluster classifiers is based on a feature space different from at least one other of the cluster classifiers.

5. The method of claim 1, wherein the input corresponds to a character.

6. The method of claim 1, wherein the top-level classifier and each of the cluster classifiers are associated with the same feature space.

7. A system for classifying an input into one of a plurality of possible outputs, comprising:

(a) means for applying a top-level classifier to the input to generate an approximate identification for the input as one of the possible outputs;

(b) means for using the approximate identification to select a subset of available cluster classifiers;

(c) means for applying said selected cluster classifiers to the input to generate two or more identifications for the input as one or more of the possible outputs; and

(d) means for classifying the input as one of the possible outputs in accordance with said two or more identifications.

8. The system of claim 7, wherein:

each of the cluster classifiers employs one or more neurons; and

at least two of the share a common output.

9. The system of claim 7, wherein means (a) comprises means for implementing K-means clustering.

10. The system of claim 7, wherein at least one of the cluster classifiers is based on a feature space different from at least one other of the cluster classifiers.

11. The system of claim 7, wherein the input corresponds to a character.

12. The system of claim 7, wherein the top-level classifier and each of the cluster classifiers are associated with the same feature space.

13. A system for classifying an input into one of a plurality of possible outputs, comprising:

(a) a top-level classifier;

(b) a plurality of cluster classifiers; and

(c) a postprocessor, wherein;

the top-level classifier generates an approximate identification for the input as one of the possible outputs and uses the approximate identification to select a subset of the cluster classifiers;

the selected cluster classifiers generate two or more identifications for the input as one or more of the possible outputs; and

the postprocessor classifies the input as one of the possible outputs in accordance with the two or more identifications of the cluster classifiers.

14. The system of claim 13, wherein:

each of the cluster classifiers comprises one or more neurons; and

at least two of the cluster classifiers share a common output.

15. The system of claim 13, wherein the top-level classifier implements K-means clustering.

16. The system of claim 13, wherein at least one of the cluster classifiers is based on a feature space different from at least one other of the cluster classifiers.

17. The system of claim 13, wherein the input corresponds to a character.

18. The system of claim 13, wherein the top-level classifier and each of the cluster classifiers are associated with the same feature space.