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

• US 4,760,604 A
• Filed: 09/12/1985
• Issued: 07/26/1988
• Est. Priority Date: 02/15/1985
• Status: Expired due to Term

• Current Assignee: Nestor, Inc.
• Original Assignee: Nestor, Inc.
• Inventors: Scofield, Christopher L., Cooper, Leon N., Reilly, Douglas L., Elbaum, Charles
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/775,144
• Time in Patent Office: 1,048 Days
• Field of Search: 382/15, 382/36, 382/37, 382/38, 382/39, 364/715
• US Class Current: 382/155
• CPC Class Codes: G06F 18/24143 Distances to neighbourhood prototypes, e.g. restricted Coulomb energy networks [RCEN]
• CPC Class Codes: G06F 18/254 of classification results, e.g. of results related to same input data

Abstract

A system is disclosed for separating and identifying classes of patterns or events which are not necessarily linearly separable. The patterns are represented by an input signal S. The system comprises (1) a plurality of classification units, connected in parallel to receive the input signal S, and (2) a class selection device, responsive to the output signals produced by the classification units, for producing a single output response R representing the class of each respective pattern. In a preferred embodiment each classification unit includes a pattern feature encoding device, responsive to the input signal S, for producing an intermediate signal F_i representative of the features contained in the pattern, and a pattern classifier, responsive to the signal F_i, for producing an output signal R_i representative of the respective class of the pattern, as identified by the features encoded by the feature encoding device.

Claims

1. A system for classification and identification of patterns, each pattern being represented by an input signal S, said system comprising:

(a) a plurality of classification units U₁, U₂ . . . U_i . . . U_k, each unit U_i including;

(1) pattern feature encoding means, responsive to said signal S, for producing an intermediate signal F_i (F₁, F₂ . . . F_i . . . F_k) representative of features contained in the pattern represented by said signal S, each intermediate signal F_i comprising a plurality of signal components (f_1i, f_2i, . . . f_ii . . . f_Mi); and

(2) pattern classification means, responsive to said intermediate signal F_i, for producing an output signal R_i (R₁, R₂ . . . R_i . . . R_k), 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 ; and

(b) class selection means, responsive to all of said output signals R_i produced by said classification units U_i, for producing a single output response R representing the class of said pattern.

2. The system defined in claim 1, wherein each pattern feature encoding means encodes a different set of features in said pattern, whereby all of said intermediate signals F_i produced by said encoding means are unique and different from each other.

3. The system defined in claim 1, wherein each pattern classification means classifies said pattern with respect to a different set of classes, whereby all of said output signals R_i produced by said classification means are unique and different from each other.

4. The system defined in claim 1, wherein said class selection means includes means for selecting the output signal R_i which best represents an identifiable pattern class.

5. The system defined in claim 1, wherein said pattern classification means is a Nestor adaptive module.

6. The system defined in claim 5, wherein said Nestor adaptive module comprises:

(1) a plurality M of input terminals each coupled to receive one scalar component f_i (f₁, f₂ . . . f_i . . . f_M) of an intermediate signal F;

(2) a plurality N of summing means, each summing means having M inputs and an output and being operative to produce a scalar component signal r_j (r₁, r₂ . . . r_j . . . r_N) at its output representing the sum of the signal representations applied to its inputs;

(3) a plurality N of threshold devices, each coupled to one of said summing means, for producing a scalar output response p_i (p₁, p₂ . . . p_i . . . p_N) when the scalar component signal applied thereto exceeds a prescribed threshold level θ

_i ; and

(4) a plurality MXN of junction elements, each junction element coupling one of said input terminals with one of said summing means and providing a transfer of information from the respective input terminal to the respective summing means in dependence upon the signal appearing at the respective input terminal and upon the junction element transfer function,

whereby the respective scalar output responses p₁, p₂ . . . p_N are components of the output response R of said module.

7. The system defined in claim 6, wherein said Nestor adaptive module further comprises a plurality N of scalar multipliers, each coupled between one of said summing means and its associated threshold device, for producing a scalar component signal λ

r_i, where λ

is a multiplier factor.

8. The system defined in claim 7, further comprising means for modifying said multiplier factor λ

of at least one of said scalar multipliers, when in a training mode, so as to avoid ambiguous class separation and identification.

9. The system defined in claim 6, further comprising means for modifying the transfer function of at least one of said junction elements, when in a training mode, in dependence upon the incoming signal applied thereto and the output signal of the summing means with which said respective junction element is associated.

10. The system defined in claim 6, further comprising means for modifying said threshold level θ

, when in a training mode, so as to avoid ambiguous class separation and identification.

11. The system defined in claim 1, wherein said class selection means is a Nestor adaptive module.

12. The system defined in claim 11, wherein said Nestor adaptive module comprises:

(1) a plurality M of input terminals each coupled to receive one scalar component f_i (f₁, f₂ . . . f_i . . . f_M) of an intermediate signal F_i ;

(2) a plurality N of summing means, each summing means having M inputs and an output and being operative to produce a first scalar component signal r_j (r₁, r₂ . . . r_j . . . r_N) at its output representing the sum of the signal representations applied to its inputs;

(3) a plurality N of threshold devices, each coupled to one of said summing means, for producing a scalar output response p_i (p₁, p₂ . . . p_i . . . p_N) when the scalar component signal applied thereto exceeds a prescribed threshold level θ

_i ; and

(4) a plurality MXN of junction elements, each junction element coupling one of said input terminals with one of said summing means and providing a transfer of information from the respective input terminal to the respective summing means in dependence upon the signal appearing at the respective input terminal and upon the junction element transfer function,

whereby the respective scalar output responses p₁, p₂ . . . p_N are components of the output response R of said module.

13. The system defined in claim 12, wherein said Nestor adaptive module further comprises a plurality N of scalar multipliers, each coupled between one of said summing means and its associated threshold device, for producing a scalar component signal λ

r_i, where λ

is a multiplier factor.

14. The system defined in claim 13, further comprising means for modifying said multiplier factor λ

of at least one of said scalar multipliers, when in a training mode, so as to avoid ambiguous class separation and identification.

15. The system defined in claim 12, further comprising means for modifying the transfer function of at least one of said junction elements, when in a training mode, in dependence upon the incoming signal applied thereto and the output signal of the summing means with which said respective junction element is associated.

16. The system defined in claim 12, further comprising means for modifying said threshold level θ

, when in a training mode, so as to avoid ambiguous class separation and identification.

17. The system defined in claim 1, wherein said pattern classification means includes memory means for storing a plurality of prototypes within a multi-dimensional pattern space, and means for comparing an input pattern, represented by said intermediate 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.

18. The system defined in claim 17, 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 means includes means for 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 for producing a response indicative of the class associated with such prototype if said input pattern falls within the region of influence thereof.

19. The system defined in claim 18, 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.

20. The system defined in claim 19, wherein said class selection means includes means for selecting, as said output response R, one of a plurality of output signals produced by said pattern classification means.

21. The system defined in claim 20, wherein each pattern classification means is assigned a prescribed priority indicative of a hierarchy level, and wherein said selecting means selects, as said output response R, the first output signal 1R_i produced by said classification means which has the highest priority, said first output signal being indicative of certain recognition of a particular class by said classification means.

22. The system defined in claim 21, wherein said selecting means includes means for (1) counting the numbers of each class indicated by the second output signal 2R_i, produced by each successive classification means in order of priority, until one class has a majority count, whenever no classification means produces a first output signal 1R_i, and (2) producing said output response R indicative of said majority class.

23. The system defined in claim 18, wherein said pattern classification means further includes means for modifying said prototype information in said memory means, when in the training mode, in response to the receipt of an input pattern.

24. The system defined in claim 23, wherein said means for modifying said prototype information reduces 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.

25. The system defined in claim 24, 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.

26. The system defined in claim 24, 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 means for modifying said prototype information changes 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.

27. The system defined in claim 26, wherein said means for modifying said prototype information expands 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.

28. The system defined in claim 24, wherein said means for modifying said prototype information includes means for 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.

29. The system defined in claim 1, wherein said class selection means includes means for selecting, as said output response R, one of a plurality of output signals produced by said pattern classification means.

30. The system defined in claim 29, wherein each pattern classification means is assigned a prescribed priority indicative of a hierarchy level, and wherein said selecting means selects, as said output response R, the output signal produced by said classification means which has the highest priority.

31. The system defined in claim 1, wherein each output signal R_i comprises a plurality of signal components (r_1i, r_2i . . . r_ii . . . r_Ni).

32. The system defined in claim 1, wherein said output response R comprises a plurality of signal components (p₁, p₂, . . . p_N).