Parallel, multi-unit, adaptive, nonlinear pattern class separator and identifier

• US 5,054,093 A
• Filed: 04/08/1988
• Issued: 10/01/1991
• Est. Priority Date: 09/12/1985
• Status: Expired due to Term

• Current Assignee: Charles Elbaum, Christopher L. Scofield, Douglas L. Reilly, Leon N. Cooper
• Original Assignee: Charles Elbaum, Christopher L. Scofield, Douglas L. Reilly, Leon N. Cooper
• Inventors: Scofield, Christopher L., Cooper, Leon N., Reilly, Douglas L., Elbaum, Charles
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US07/179,427
• Time in Patent Office: 1,271 Days
• Field of Search: 382/14, 382/15, 382/16, 364/513
• US Class Current: 382/159
• CPC Class Codes: G06F 18/254 of classification results, e.g. of results related to same input data

Abstract

A system for separating and identifying classes of patterns or events which are not necessarily linearly separable. During a training process of the system, new prototypes are created when prior stored prototypes fail to properly classify an input pattern, and previously stored prototypes are modified when an input pattern falls within the sphere of influence of a prototype associated with a different class than the input pattern.

Claims

1. A method for classification and identification of patterns in a system comprising input means for receiving an input signal representing each input pattern as a location in multi-dimensional pattern space, memory means for storing information and computer means connected to said input means and said memory means, said method comprising the steps of:

(a) storing in said memory means a plurality of prototypes within said multi-dimensional pattern space, each prototype being associated with a particular pattern class;

(b) comparing an input pattern, represented by said signal, with each of said prototypes stored in said memory means to determine whether said input pattern falls within a region of influence of at least one of said prototypes;

(c) storing a new prototype in said memory means when such input pattern fails to fall within the region of influence of any previously stored prototype; and

(d) modifying one or more of said prototypes in said memory means, in response to the receipt of an input pattern, to prevent said input pattern from falling within the sphere of influence of a prototype associated with a different pattern class than said input pattern;

whereby said method tends to develop a pattern space in which each incoming input pattern falls only within the regions of influence of prototypes associated with the same class as the input pattern.

2. The method defined in claim 1, wherein each prototype includes, as prototype information stored in said memory means, a vector location in said multi-dimensional pattern space;

a scalar distance defining the size of a region of influence about said vector location in said pattern space; and

a particular class with which said prototype is associated; and

wherein said comparing step includes the steps of (1) determining whether the location of said input pattern in said pattern space falls within the region of influence of one or more of said prototypes, and (2) producing a response indicative of the class associated with such prototype if said input pattern falls within the region of influence thereof.

3. The method defined in claim 2, wherein each prototype is designated by one of at least two types, said designated type being stored in said memory means for its associated prototype as a part of said prototype information, wherein a first type of prototype produces a first output signal 1R_i indicative of the certain recognition of the class of an input pattern that falls within the region of influence thereof, and wherein a second type of prototype produces a second output signal 2R_i indicative of a possible, but not certain recognition of the class of an input pattern that falls within the region of influence thereof.

4. The method defined in claim 2, further comprising the step of modifying said prototype information in said memory means, when in the training mode, in response to the receipt of an input pattern.

5. The method defined in claim 1, wherein said step of modifying said prototype information includes the step of reducing said scalar distance of a prototype if an input pattern falls within the region of influence of such prototype, thereby producing a response R_i indicative of the class associated with such prototype, when the class is incorrect, said scalar distance being reduced sufficiently so that said input pattern falls outside of said region of influence of such prototype.

6. The method defined in claim 5, wherein said scalar distance is reduced to a value substantially equal to, but less than the distance between the vector locations in said pattern space of such prototype and said input pattern.

7. The method defined in claim 5, wherein each prototype is designated by one of at least two types, said designated type being stored in said memory means for its associated prototype as a part of said prototype information, wherein a first type of prototype produces a first output signal 1R_i indicative of the certain recognition of the class of an input pattern that falls within the region of influence thereof, and wherein a second type of prototype produces a second output signal 2R_i indicative of a possible, but not certain recognition of the class of an input pattern that falls within the region of influence thereof;

and wherein said step of modifying said prototype information includes the step of changing the designated type of a prototype from a first type to a second type when said scalar distance of such prototype is reduced below a prescribed threshold value.

8. The method defined in claim 7, wherein said step of modifying said prototype information includes the step of expanding said scalar distance of a given prototype out to the nearest region of influence of a prototype of said first type, whenever the designated type of such given prototype has been changed from a first type to a second type.

9. The method defined in claim 1, wherein said step of storing a new prototype in said memory means includes the step of storing a new prototype in said memory means when an input pattern fails to fall within the region of influence of any previously stored prototype associated with the same class as the class of the input pattern.

10. In a system for classification and identification of patterns, each pattern being represented by a pattern signal S, comprised of a plurality of signal components s₁, s₂, . . . s_k, said system comprising at least one classification unit U_i including pattern classification means, responsive to said pattern signal S, for producing an output response signal R_i representative of a proposed respective class of said pattern represented by said signal S, said pattern classification means including:

(1) memory means for storing a plurality of prototypes within a multi-dimensional pattern space, each prototype including, as prototype information stored in said memory means;

a vector location in said pattern space, a region of influence about said vector location of said prototype, and a particular class with which said prototype is associated;

(2) means for comparing the vector location of an input pattern, represented by said pattern signal S, with at least one of said prototype stored in said memory means to determine whether said input pattern location falls within the region of influence of said at least one prototype, and for producing an output response signal R_i, indicative of the class associated with such prototype, if said input pattern location falls within the region of influence thereof;

(3) means for storing in said memory means a new prototype, if said input pattern location falls outside the region of influence of said prototypes stored in said memory means, said new prototype including, as prototype information stored in said memory means;

the vector location of said input pattern, a region of influence about said vector location, and the particular class to which said input pattern belongs; and

(4) means for modifying the region of influence of a given prototype associated with a particular class if the location of an input pattern of another, different class falls within said region of influence of said given prototype;

whereby said system tends to develop a pattern space in which each incoming input pattern falls only within the regions of influence of prototypes associated with the same class as the input pattern.

11. The pattern classification system defined in claim 10, wherein said region of influence of each prototype is a scalar distance.

12. The pattern classification system defined in claim 11, wherein said scalar distance assigned to each new prototype associated with a particular class is no greater than the distance to the nearest region of influence of all other existing prototypes associated with other classes.

13. The pattern classification system defined in claim 12, wherein said scalar distance has a maximum default value if the regions of influence of the other existing prototypes, associated with other classes, are farther away than said maximum value.

14. The pattern classification system defined in claim 12, wherein said scalar distance has a prescribed minimum value, said new prototype not being stored in said memory means as a standard prototype if the region of influence of at least one other existing prototype associated with another class is less than said prescribed minimum value.

15. The pattern classification system defined in claim 10, wherein each prototype further includes, as prototype information stored in said memory means, a label specifying the phase type of the respective prototype and wherein a first phase type is specified for a given prototype if said given prototype does not overlap any other first phase type prototype associated with a different class and said region of influence of said given prototype is greater than a prescribed minimum size.

16. The pattern classification system defined in claim 15, wherein said region of influence of each prototype is a scalar distance, whereby said prescribed minimum size is a prescribed minimum distance.

17. The pattern classification system defined in claim 16, wherein a second phase type is specified for a given prototype if the region of influence of another existing prototype extends closer to the vector location of said given prototype than said prescribed minimum distance.

18. The pattern classification system defined in claim 15, further comprising means for modifying the region of influence of a given prototype associated with a particular class if the location of an input pattern of another, different class falls within said region of influence of said given prototype.

19. The pattern classification system defined in claim 10, wherein said region of influence of said given prototype is modified to exclude said input pattern location therefrom.

20. The pattern classification system defined in claim 19, wherein said region of influence of each prototype is a scalar distance and wherein said scalar distance of said given prototype is reduced to exclude said input pattern location from said region of influence.

21. The pattern classification system defined in claim 20, wherein said label of said given prototype specifies a first phase type.

22. The pattern classification system defined in claim 21, wherein said label of said given prototype is converted from a first phase type to a second phase type if said scalar distance thereof is reduced below a prescribed minimum value.

23. The pattern classification system defined in claim 16, wherein a first phase type is specified for a given prototype if the class of an input pattern location that falls within its region of influence is necessarily the same as the class with which said given prototype is associated, whereby first phase type prototypes associated with different classes cannot overlap in said pattern space.

24. The pattern classification system defined in claim 16, wherein a second phase type is specified for a given prototype if the class of an input pattern location that falls within its region of influence may be, but is not necessarily the same as the class with which said given prototype is associated, whereby second phase type prototype associated with different classes can overlap in said pattern space thereby forming a confusion zone.

25. The pattern classification system defined in claim 24, further comprising means, responsive to an input pattern signal, for counting the second phase type prototypes associated with each class in a confusion zone at the location of said input pattern, and for producing a classification unit output signal R_i in dependence upon the prototype count.

26. The pattern classification system defined in claim 25, wherein said classification output signal R_i indicates the class associated with the greatest number of second phase type prototypes at said input pattern location.

27. The pattern classification system defined in claim 10, wherein said system comprises a plurality of said classification units U₁, U₂, . . . U_i, . . . U_k, which produce output signals R1, R₂, . . . R_i, . . . R_k, respectively, and wherein said system further includes class selection means, responsive to all of said output signals R₁, R₂, . . . R_i, . . . R_k, for producing a single output response R representing a class of said pattern.

28. The pattern classification system defined in claim 26, wherein each classification unit U_i further includes pattern feature encoding means, responsive to said signal S, for producing an intermediate signal F_i, comprised of signal components F₁, F₂ . . . F_k, representative of features contained in the pattern represented by said signal S;

and

wherein said pattern classification means is responsive to said intermediate signal F_i, for producing an output signal R_i representative of a proposed respective class of said pattern represented by said signal S as identified by the features represented by said intermediate signal F_i.

29. The pattern classification system defined in claim 28, wherein said system comprises a plurality of said classification units U₁, U₂, . . . U_i, . . . U_k, which produce output signals R1, R₂, . . . R_i, . . . R_k, respectively, and wherein said system further includes class selection means, responsive to all of said output signals R₁, R₂, . . . R_i, . . . R_k, for producing a single output response R representing a class of said pattern.

30. The pattern classification system defined in claim 27, wherein said classification units are arranged in a descending order of priority, from highest to lowest, and wherein said class selection means includes means for setting said output response R equal to the class indicated by the output signal R_i of that classification unit having the highest priority which provides unambiguously the class of an input pattern.

31. The pattern classification system defined in claim 29, wherein said classification units are arranged in a descending order of priority, from highest to lowest, and wherein said class selection means includes means for setting said output response R equal to the class indicated by the output signal R_i of that classification unit having the highest priority which provides unambiguously the class of an input pattern.

32. The pattern classification system defined in claim 27, wherein said class selection means includes means for setting the output response R equal to the class indicated by the majority of the output signals R_i.

33. The pattern classification system defined in claim 29, wherein said class selection means includes means for setting the output response R equal to the class indicated by the majority of the output signals R_i.

34. The pattern classification system defined in claim 32, wherein said class selection means includes means for setting the output response R equal to the class indicated by the majority of the output signals when none of said classification units provides unambiguously the class of an input pattern.

35. The pattern classification system defined in claim 33, wherein said class selection means includes means for setting the output response R equal to the class indicated by the majority of the output signals when none of said classification units provides unambiguously the class of an input pattern.

36. The pattern classification system defined in claim 10, further comprising means for deleting a given prototype from said memory means.

37. The pattern classification system defined in claim 10, further comprising means for modifying the region of influence of a given prototype associated with a particular class if the location of an input pattern of another, different class falls within said region of influence of said given prototype.

38. The pattern classification system defined in claim 37, wherein said region of influence of said given prototype is modified to exclude said input pattern location therefrom.

39. The pattern classification system defined in claim 38, wherein said region of influence of each prototype is a scalar distance and wherein said scalar distance of said given prototype is reduced to exclude said input pattern location from said region of influence.

40. A method for classification and identification of patterns, each pattern being represented by a pattern signal S, comprised of a plurality of signal components s₁, . . . s₂, . . . s_k, said method utilizing a computer system, responsive to said pattern signal S, for producing an output signal R₁ representative of a proposed respective class of said pattern represented by said signal S, said computer system comprising (a) memory means, and (b) logic means, coupled to said memory means, for carrying out said method, said method comprising the steps of:

(1) storing a plurality of prototypes within a multi-dimensional pattern space, each prototype including, as prototype information stored in said memory means;

a vector location in said pattern space, a region of influence about said vector location of said prototype, and a particular class with which said prototype is associated;

(2) comparing the vector location of an input pattern, represented by said pattern signal S, with at least one of said prototypes stored in said memory means to determine whether said input pattern location falls within the region of influence of said at least one prototype, and producing an output response signal R_i, indicative of the class associated with such prototype, if said input pattern location falls within the region of influence thereof;

(3) storing in said memory means a new prototype, if said input pattern location falls outside the region of influence of said prototypes stored in said memory means, said new prototype including, as prototype information stored in said memory means;

the vector location of said input pattern, a region of influence about said vector location, and the particular class to which said input pattern belongs; and

(4) modifying the region of influence of a given prototype associated with a particular class if the location of an input pattern of another, different class falls within said region of influence of said given prototype;

whereby said method tends to develop a pattern space in which each incoming input pattern falls only within the regions of influence of prototypes associated with the same class as the input pattern.

41. The pattern classification method defined in claim 40, wherein said region of influence of each prototype is a scalar distance.

42. The pattern classification method defined in claim 41, wherein said scalar distance assigned to each new prototype associated with a particular class is no greater than the distance to the nearest region of influence of all other existing prototypes associated with other classes.

43. The pattern classification method defined in claim 42, wherein said scalar distance has a maximum default value if the regions of influence of the other existing prototypes, associated with other classes, are farther away than said maximum value.

44. The pattern classification method defined in claim 42, wherein said scalar distance has a prescribed minimum value, said new prototype not being stored in said memory means as a standard prototype if the region of influence of at least one other existing prototype associated with another class is less than said prescribed minimum value.

45. The pattern classification method defined in claim 40, wherein each prototype further includes, as prototype information stored in said memory means, a label specifying the phase type of the respective prototype and wherein a first phase type is specified for a given prototype if said given prototype does not overlap any other first phase type prototype associated with a different class and said region of influence of said given prototype is greater than a prescribed minimum size.

46. The pattern classification method defined in claim 45, wherein said region of influence of each prototype is a scalar distance, whereby said prescribed minimum size is a prescribed minimum distance.

47. The pattern classification method defined in claim 46, wherein a second phase type is specified for a given prototype if the region of influence of another existing prototype extends closer to the vector location of said given prototype than said prescribed minimum distance.

48. The pattern classification method defined in claim 45, further comprising the step of modifying the region of influence of a given prototype associated with a particular class if the location of an input pattern of another, different class falls within said region of influence of said given prototype.

49. The pattern classification method defined in claim 40, wherein said region of influence of said given prototype is modified to exclude said input pattern location therefrom.

50. The pattern classification method defined in claim 49, wherein said region of influence of each prototype is a scalar distance and wherein said scalar distance of said given prototype is reduced to exclude said input pattern location from said region of influence.

51. The pattern classification method defined in claim 50, wherein said label of said given prototype specifies a first phase type.

52. The pattern classification method defined in claim 51, wherein said label of said given prototype is converted from a first phase type to a second phase type if said scalar distance thereof is reduced below a prescribed minimum value.

53. The pattern classification method defined in claim 46, wherein a first phase type is specified for a given prototype if the class of an input pattern location that falls within its region of influence is necessarily the same as the class with which said given prototype is associated, whereby first phase type prototypes associated with different classes cannot overlap in said pattern space.

54. The pattern classification method defined in claim 46, wherein a second phase type is specified for a given prototype if the class of an input pattern location that falls within its region of influence may be, but is not necessarily the same as the class with which said given prototype is associated, whereby second phase type prototypes associated with different classes can overlap in said pattern space thereby forming a confusion zone.

55. The pattern classification method defined in claim 54, further comprising the step of counting the second phase type prototypes associated with each class in a confusion zone at the location of said input pattern, and producing a classification unit output signal R_i in dependence upon the prototype count.

56. The pattern classification method defined in claim 55, wherein said signal producing step includes the step of causing said classification output signal R_i to indicate the class associated with the greatest number of second phase type prototypes at said input pattern location.

57. The pattern classification method defined in claim 40, wherein said computer system is organized into a plurality of pattern classification units U₁, U₂, . . . U_i, . . . U_k, which produce output signals R1, R₂, . . . R_i, . . . R_k, respectively, and wherein said method further comprises the step of selecting a class, in response to said output signals R₁, R₂, . . . R_i, . . . R_k, for producing a single output response R representing a class of said pattern.

58. The pattern classification method defined in claim 56, wherein said method further includes the steps of encoding features of the input pattern represented by the said signal S, within each respective classification unit U_i, and producing an intermediate signal F_i, comprised of signal components F₁, F₂ . . . F_k, representative of features contained in the pattern represented by said signal S;

and

wherein said comparison step (2) includes the step of comparing the vector location of an input pattern as represented by said intermediate signal F_i and producing an output signal R_i representative of a proposed respective class of said pattern represented by said signal S as identified by the features represented by said intermediate signal F_i.

59. The pattern classification method defined in claim 58, wherein said computer system is organized in a plurality of said classification units U₁, U₂, . . . U_i, . . . U_k, which produce output signals R1, R₂, . . . R_i, . . . R_k, respectively, and wherein said method further includes the step of selecting a pattern class in response to said output signals R₁, R₂, . . . R_i, . . . R_k, and producing a single output response R representing a class of said pattern.

60. The pattern classification method defined in claim 57, wherein said classification units are arranged in a descending order of priority, from highest to lowest, and wherein said class selecting step includes the step of setting said output response R equal to the class indicated by the output signal R_i of that classification unit having the highest priority which provides unambiguously the class of an input pattern.

61. The pattern classification method defined in claim 59, wherein said classification units are arranged in a descending order of priority, from highest to lowest, and wherein said class selection means includes means for setting said output response R equal to the class indicated by the output signal R_i of that classification unit having the highest priority which provides unambiguously the class of an input pattern.

62. The pattern classification method defined in claim 57, wherein said class selection step includes the step of setting the output response R equal to the class indicated by the majority of the output signals R_i.

63. The pattern classification method defined in claim 59, wherein said class selection step includes the step of setting the output response R equal to the class indicated by the majority of the output signals R_i.

64. The pattern classification method defined in claim 62, wherein said class selection step includes the step of setting the output response R equal to the class indicated by the majority of the output signals when none of said classification units provides unambiguously the class of an input pattern.

65. The pattern classification method defined in claim 63, wherein said class selection step includes the step of setting the output response R equal to the class indicated by the majority of the output signals when none of said classification units provides unambiguously the class of an input pattern.

66. The pattern classification method defined in claim 40, further comprising the step of deleting a given prototype from said memory means.

67. The pattern classification method defined in claim 40, further comprising the step of modifying the region of influence of a given prototype associated with a particular class if the location of an input pattern of another, different class falls within said region of influence of said given prototype.

68. The pattern classification method defined in claim 67, wherein said region of influence of said given prototype is modified to exclude said input pattern location therefrom.

69. The pattern classification method defined in claim 68, wherein said region of influence of each prototype is a scalar distance and wherein said scalar distance of said given prototype is reduced to exclude said input pattern location from said region of influence.

70. A method for classification and identification of patterns in a system comprising input means for receiving an input signal F representing each input pattern as a location in a multi-dimensional pattern space, memory means for storing information and computer means connected to said input means and said memory means, said method comprising the steps of:

(a) storing in said memory means a plurality of prototypes within said multi-dimensional pattern space, each prototype including, as prototype information stored in said memory means, a vector location in said multi-dimensional pattern space, a scalar distance defining the size of a region of influence about said vector location in said pattern space, and a particular class with which said prototype is associated; and

(b) comparing an input pattern, represented by said signal F, with each of said prototypes stored in said memory means to determine whether said input pattern falls within a region of influence of at least one of said prototypes;

wherein said comparing step includes the steps of (1) determining whether the location of said input pattern in said pattern space falls within the region of influence of one or more of said prototypes, and (2) producing a response indicative of the class associated with such prototype if said input pattern falls within the region of influence thereof;

wherein each prototype is designated by one of at least two types, said designated type being stored in said memory means for its associated prototype as a part of said prototype information; and

wherein a first type of prototype produces a first output signal 1R_i indicative of the certain recognition of the class of an input pattern that falls within the region of influence thereof, and wherein a second type of prototype produces a second output signal 2R_i indicative of a possible, but not certain recognition of the class of an input pattern that falls within the region of influence thereof.