Parallel, multi-unit, adaptive pattern classification system using inter-unit correlations and an intra-unit class separator methodology

• US 4,958,375 A
• Filed: 02/17/1988
• Issued: 09/18/1990
• Est. Priority Date: 02/17/1988
• Status: Expired due to Term

• Current Assignee: Nestor, Inc.
• Original Assignee: Nestor, Inc.
• Inventors: Cooper, Leon N., Reilly, Douglas L., Elbaum, Charles, Scofield, Christopher L.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US07/156,830
• Time in Patent Office: 944 Days
• Field of Search: 382/14, 382/15, 382/36, 382/38, 382/39, 382/37, 382/30, 364/715, 364/900
• 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 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. At least some of the pattern classification units include generalizer units having a memory for storing a number of generalizer "prototypes" and a comparator for comparing the vector location of an input pattern with each of the generalizer prototypes.

Claims

1. In a system for classification and identification of patterns, each pattern being represented by an input signal S, said system comprising at least one classification unit U_i including:

(1) pattern feature encoding means, responsive to said signal S, for producing an intermediate signal F, comprised of signal components F₁, F₂ . . . F_i . . . F_k, representative of features contained in the pattern represented by said signal S; and

(2) pattern classification means, responsive to said intermediate signal F, 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;

the improvement wherein said pattern classification means include;

(a) generalizer means comprising;

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

a vector location in said pattern space;

a scalar distance, in a given range between a minimum and maximum value, defining the size of a region of influence about said vector location of said generalizer prototype; and

a particular class with which said generalizer prototype is associated; and

(ii) means for comparing the vector location of an input pattern, represented by said intermediate signal F, with a plurality of said generalizer prototypes stored in said memory means to determine whether said input pattern location falls within a region of influence of at least one of said generalizer prototypes, and for producing a generalizer output classification response, indicative of the class associated with said at least one generalizer prototype, if said input pattern location falls within the region of influence thereof;

(b) separator means comprising;

(i) memory means for storing a plurality of separator prototypes within said pattern space, each separator prototype including, as prototype information stored in said memory means;

a vector location in said pattern space;

a scalar distance defining the size of a region of influence about said vector location of said separator prototype;

a particular class with which said separator prototype is associated;

the identity of a pair of generalizer prototypes with which said separator prototype is associated; and

an index specifying a portion of the signal components F₁, F₂ . . . . F_i . . . F_k of the pattern space holding the generalizer prototypes with which said separator prototype is associated;

(ii) means for comparing the location of an input pattern, represented by the signal components of said intermediate signal F identified by the respective index of a separator prototype, with at least one of said separator prototypes stored in said memory means to determine whether said input pattern location falls within a region of influence of such separator prototype, and for producing a separator output classification response, indicative the class of said input pattern, if said input pattern location falls within the region of influence of such separator prototype; and

(c) polling means, responsive to said generalizer means and said separator means, for producing a classification unit output signal R_i, in dependence upon said generalizer and separator output classification responses;

thereby to identify patterns which fall within the regions of influence of a plurality of generalizer prototypes.

2. The system defined in claim 1, wherein said generalizer means further include means for modifying said scalar distance defining the size of a region of influence of each generalizer prototype, within said given range, when said system is in a training mode.

3. The system defined in claim 1, wherein said maximum value defines a region of influence for the respective generalizer prototype of approximately five percent to fifty percent said pattern space.

4. The system defined in claim 1, wherein each generalizer prototype further includes, as prototype information stored in said generalizer memory means, a set of weighting factors (W₁, W₂ . . . W_i . . . W_k), one for each respective component (F₁, F₂ . . . F_i . . . F_k) of said intermediate signal F, and wherein said pattern classification means further include means for multiplying each intermediate signal component F_i by the respective, associated weighting factor W_i or means for performing a bit comparison between the input signal F_i and the weighting factor W_i, to produce a weighted signal component F'"'"'_i for comparison by said comparing means.

5. The system defined in claim 1, further comprising means for adjusting said generalizer weighting factors, when in a training mode, to modify the output classification response R_i of said pattern classification means.

6. The system defined in claim 1, wherein said separator means further include means for modifying said scalar distance defining the size of a region of influence of each separator prototype, when said system is in a training mode.

7. The system defined in claim 1, wherein each separator prototype further includes, as prototype information stored in said separator memory means, a set of weighting factors(W₁, W₂ . . . W_i . . . W_k), one for each respective component (F₁, F₂ . . . F_i . . . F_k) of said intermediate signal F, and wherein said pattern classification means further include means for multiplying each intermediate signal component F_i by the respective, associated weighting factor W_i, or means for performing a bit comparison between the input signal F_i and the weighting factor W_i, to produce a weighted signal component F'"'"'_i for comparison by said comparing means.

8. The system defined in claim 7, further comprising means for adjusting said separator weighting factors, when in a training mode, to modify the output classification response R_i of said pattern classification means.

9. The system defined in claim 1, wherein each pattern classification means which comprise generalizer means and separator means further include means for determining the pair of generalizer prototypes associated with each separator prototype.

10. The system defined in claim 1, wherein said system includes a plurality of said classification units U_i, U₂, . . . U_i, . . . U_k which produce output signals R₁, R₂, . . . R_i . . . U_k, respectively, and wherein paid system 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 the class of said pattern.

11. A method for classification and identification of patterns in a system comprising input means for receiving an input signal F comprised of signal components F₁, F₂ . . . F_i . . . F_k 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 to said memory means, said method comprising the steps of:

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

a vector location in said pattern space;

a scalar distance, in a range between minimum and maximum value, defining the size of a region of influence about said vector location of said generalizer prototype; and

a particular class with which said generalizer prototype is associated;

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

(c) producing a generalizer output classification response, indicative of the class associated with said at least one generalizer prototype, if said input pattern location falls within the region of influence thereof;

(d) storing in said memory means a plurality of separator prototypes within said pattern space, each separator prototype including, as prototype information stored in said separator memory means;

a vector location in said pattern space;

a scalar distance defining the size of a region of influence about said vector location of said separator prototype;

a particular class with which said separator prototype is associated;

the identity of a pair of generalizer prototypes with which said separator prototype is associated; and

an index specifying a portion of the signal components F₁, F₂, . . . F_i . . . F_k of the pattern space holding the generalizer prototypes with which said separator prototype is associated;

(e) comparing the location of an input pattern, represented by the signal components of said input signal F identified by the respective index of a separator prototype, with at least one of said separator prototypes stored in said memory means to determine whether said input pattern location falls within a region of influence of such separator prototype;

(f) producing a separator output classification response, indicative of the pattern class, if said input pattern location falls within the region of influence such separator prototype; and

(g) producing an output signal R_i, indicative of the class of the input pattern represented by said input signal F_i, in dependence upon said generalizer and separator output classification responses;

thereby to identify patterns which fall within the regions of influence of a plurality of generalizer prototypes.

12. The method defined in claim 11, further comprising the step of modifying said scalar distance defining the size of a region of influence of each generalizer prototype, within said given range, while in a training mode.

13. The method defined in claim 11, wherein said maximum value defines a region of influence for the respective generalizer prototype of approximately five percent to fifty percent of said pattern space.

14. The method defined in claim 11, wherein each generalizer prototype further includes, as prototype information stored in said memory means, a set of generalizer weighting factors (W₁, W₂ . . . W_i . . . W_k), one for each respective component (F₁, F₂ . . . F_i . . . F_k) of said input signal F, and wherein said method further comprises the step of multiplying each input signal F_i by the respective, associated, generalizer weighting factor W_i or of performing a bit comparison between the input signal F_i and the weighting factor W_i, to produce a weighted signal F'"'"'_i for utilization in said comparing step.

15. The method defined in claim 14, further comprising the step of adjusting said generalizer weighting factors, when in a training mode.

16. The method defined in claim 11, further comprising the step of modifying said scalar distance defining the size and region of influence of each separator prototype, when in a training mode.

17. The method defined in claim 11, wherein each separator prototype further includes, as prototype information stored in said memory means, a set of separator weighting factors (W₁, W₂ . . . W_i . . . W_k), one for each respective component (F₁, F₂ . . . F_i . . . F_k) of said input signal F, and wherein said method further includes the step of multiplying each input signal component F_i by the respective, associated, separator weighting factor W_i or of performing a bit comparison between the input signal F_i and the weighting factor W_i, to produce a weighted signal component F'"'"'_i for utilization in said comparing step.

18. The method defined in claim 17, further comprising the step of adjusting said separation weighting factors, when in a training mode.

19. The method defined in claim 11, further comprising the step of determining the pair of generalizer prototypes associated with each separator prototype.