Learning system with prototype replacement

• US 5,649,070 A
• Filed: 02/17/1995
• Issued: 07/15/1997
• Est. Priority Date: 02/17/1995
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mohan, Rakesh, Bolle, Rudolf Maarten, Connell, Jonathan Hudson
• Primary Examiner(s): Hafiz, Tariq R.
• Application Number:
  US08/394,525
• Time in Patent Office: 879 Days
• Field of Search: 395/54, 395/68, 395/77, 395/20, 395/10, 382/110, 382/155, 382/159, 382/160, 382/209, 382/224, 382/225
• US Class Current: 706/14
• CPC Class Codes: G06F 18/24133 Distances to prototypes
• CPC Class Codes: G06V 20/68 Food, e.g. fruit or vegetables

Abstract

One or more sets of prototype descriptions for a number of classes of objects stored on a computer database are maintained. These prototypes are used as a basis for identifying the class of a presented object. A trainer determines when a new prototype is required to be added to the database based on current match results. This allows the system to be trained to recognize items in classes that deviate significantly from the items that were initially used to determine the classification rules. A determination is made about which prototypes can be deleted on the basis of their match histories. This allows the system to automatically optimize itself to work with a bounded collection of prototypes. In addition, it allows the system to track variations in class characteristics over time and adjust the corresponding set of prototypes appropriately.

Claims

1. An adaptive classifier apparatus comprising:

means for scanning a test object and outputting a parameter signal representing a scanned physical parameter of the test object;

means for receiving said parameter signal and for generating a test feature data based on said parameter signal;

means for retrievably storing a first plurality of a prototype feature data and a second plurality of a prototype feature data;

classifying means for comparing said test feature data to each of said first plurality and to each of said second plurality of prototype feature data and for generating a classifier data indicating which of said first plurality and said second plurality has a prototype feature data comparing closest to said test feature data;

means for generating an event signal associated with said generating a classifier data;

means for generating a usefulness data corresponding to each of said first plurality and said second plurality of prototype feature data, said usefulness data representing a frequency and recency relative to said event signal that its associated prototype feature datum is the prototype feature datum comparing closest with the test feature;

means for modifying said stored first plurality of prototype feature data and said stored second plurality of prototype feature data based on said usefulness data.

2. An adaptive classifier apparatus according to claim 1 wherein said means for generating a usefulness data increases said usefulness data by a first amount at each event count at which the prototype feature datum associated with said usefulness data compares closest to the test feature data and decreases said usefulness data by a second amount at each event count at which the prototype feature datum associated with said usefulness data does not compare closest to the test feature data.

3. An adaptive classifier apparatus according to claim 1 further comprising:

means for storing a data associated with said test feature data as one of said first plurality of prototype feature data in response to said classifier data indicating said test feature data as comparing closest with a prototype feature data of said first plurality; and

means for storing a data associated with said test feature data as one of said second plurality of prototype feature data in response to said classifier data indicating said test feature data as comparing closest with a prototype feature data of said second plurality.

4. An adaptive classifier apparatus according to claim 3 wherein

said means for storing a first plurality of prototype data and second plurality of prototype data stores a maximum population data for said first plurality and a maximum population data for said second plurality, said maximum populations being less than a maximum physical storage capacity of said means and wherein

said means for modifying said first and second plurality of prototype feature data deletes a prototype feature data in accordance with said maximum population data and in an order of deletion based on said usefulness data.

5. An adaptive classifier apparatus according to claim 1 wherein means for receiving said scanned parameter signal generates a test feature data representing a visual characteristic of said test object, and wherein said first plurality of prototype feature data and said second plurality of prototype feature data represent prototype visual characteristics.

6. An adaptive classifier apparatus according to claim 5 wherein said visual characteristic of the test object is a color characteristic and wherein said prototype visual characteristics are color characteristics.

8. An adaptive classifier apparatus according to claim 5 wherein said visual characteristic of the test object is a size characteristic and wherein said prototype visual characteristics are size characteristics.

9. An adaptive classifier apparatus according to claim 1 wherein

said means for storing a first plurality of prototype data and second plurality of prototype data establishes a maximum population for said first plurality and a maximum population for said second plurality, said maximum populations being less than a maximum physical storage capacity of said means and wherein

said means for deleting a classifier feature data deletes said classifier data in accordance with said maximums and in an order of deletion based on said usefulness data.

10. An adaptive classifier apparatus according to claim 1 wherein said classifier means includes means for generating a proximity value representing a similarity between said test feature data and each of said first plurality of prototype feature data and said second plurality of prototype feature data.

11. An adaptive classifier apparatus according to claim 10 wherein said classifier means further includes:

means for storing a predetermined threshold; and

means for generating a strength data, based on said proximity value and said predetermined threshold, corresponding to said generated classifier data.

12. An adaptive classifier apparatus according to claim 10 further comprising:

means for storing a third plurality of prototype feature data and wherein said classifier means comprises

means for detecting a prototype feature data from said first plurality of prototype feature data comparing closest to said test feature data,

means for detecting a prototype feature data from said second plurality of prototype feature data comparing closest to said test feature data, and

means for detecting a prototype feature data from said third plurality of prototype feature data comparing closest to said test feature data; and

means for generating a class option data representing a relative order of a magnitude of the proximity value corresponding to said closest prototype feature point from said first, second and third plurality of prototype feature data.

13. An adaptive classifier apparatus according to claim 12 further comprising means for displaying said class option data.

14. An adaptive classifier apparatus according to claim 13 wherein said classifier means includes means for storing a predetermined threshold, and further comprising

means for suppressing a display of a class option data based on said proximity values and said threshold.

15. An adaptive classifier apparatus according to claim 10 wherein said classifier means comprises:

means for detecting a difference between said test feature data and each of said first plurality and each of said second plurality of prototype feature data and for generating said proximity data based on said detected difference;

means for detecting an Nth nearest neighbor classifier feature datum from among said first and second plurality of prototype feature data, based on said proximity data, and

wherein said classifier data reflects which of said first plurality and said second plurality that said Nth nearest neighbor feature datum point is associated with.

7. An adaptive classifier apparatus according to claim wherein said visual characteristic of the test object is a texture characteristic and wherein said prototype visual characteristics are texture characteristics.