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

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.

REFERENCE TO RELATED PATENTS AND PATENT APPLICATION 
The subject matter of this patent application is related to that of the 
commonly-owned U.S. Pat. Nos. 3,950,733; 4,044,243; 4,254,474 and 
4,326,259, all to Cooper et al., and to the patent application Ser. No. 
775,144 of Copper et al., for "Parallel, Multi-Unit, Adaptive, Nonlinear 
Pattern Class Separator and Identifier," all of which are incorporated 
herein by reference. 
1. Field of the Invention 
This invention relates to adaptive information processing systems. More 
particularly, it relates to self-organizing input-output devices which 
function to separate and identify classes of patterns including those that 
are not linearly separable. 
2. Background of the Invention 
The above-referenced patents and patent application to Cooper et al. 
disclose methods and apparatus (systems) that can learn to classify 
"patterns" or real world "events" even when representations of the same 
are not linearly separable. The patterns or events are detected by some 
data acquisition device and encoded into a set of measurements or features 
the results of which are represented by the signal S, comprised of 
individual signals s.sub.1, s.sub.2, . . . s.sub.k. The signal S could be, 
for example, a signal coming from a camera registering a scene (pattern), 
or the output of a microphone detecting some sound (pattern), or from a 
data base representing events, historical records, etc. (abstract 
patterns). 
In a system comprising a Nestor.RTM. Adaptive Module as described in these 
patents, all input signals S (which are themselves referred to herein as 
"patterns") belonging to the same class should elicit the same final 
response from the system. For example, in an application such as character 
recognition, any version of a handdrawn "2" seen by the system should 
result in an output signal which causes the character font member for "2" 
to be displayed on some output device, video screen, printout, etc. 
A system of this type is an extremely powerful pattern class separator and 
identifier. The system can be trained by a learning procedure which does 
not require the operator to specify the (possibly) complex geography of 
the pattern class in the multidimensional pattern space in which the input 
event is represented. In such a system the input event S is preprocessed 
into an intermediate signal F representing only certain prescribed 
features of the original pattern. Subjecting the input signal S 
(representing the pattern) to this preprocessing step--referred to herein 
as encoding--should preserve enough information to permit patterns to be 
distinguished from each other. Information irrelevant for learning one 
class may be important to distinguish some other class. For this reason, 
it may be difficult to choose a single preprocessing strategy that removes 
all irrelevant information without jeopardizing the ability to distinguish 
some classes. 
The above-referenced patent application Ser. No. 755,144 for "Parallel, 
Multi-Unit, Adaptive, Nonlinear Pattern Class Separator and Identifier" 
describes a multi-unit Nestor System.RTM. which can be regarded as a way 
of linking together a number of Nestor Adaptive Modules. Each component 
Nestor Module can be considered as a complete unit, including its own 
preprocessing and encoding procedures. A pattern is identified by the 
response it produces among these component units. Each unit has its own 
encoding procedures, different from that of any other. A unit's encoding 
procedures define its code space. It is sensitive to certain types of 
information in the input signal. The particular set of features it 
registers may give it a special aptitude for learning some types of 
pattern classes, but not others. To the extent that a class is well 
separated from all others in the pattern space of a given unit and to the 
extent that it is not widely distributed throughout that space, then that 
unit will have a natural "aptitude" for learning this class. At the same 
time, learning other pattern classes may require pooling the resources of 
several component units, none of which alone has sufficient discriminating 
skills, by virtue of its preprocessing and encoding properties, to 
distinguish these classes. In this case the system identifies an example 
of such a class by correlating the responses of a set of units. 
The multi-unit Nestor System disclosed in the above patent application is 
organized to first attempt separation of pattern classes within individual 
code spaces and secondly, for those classes for which that is not 
possible, to subsequently correlate the responses of multiple units to 
produce an identification. Such a system works best when, within the 
pattern spaces of the various events, class distributions are largely (but 
not necessarily wholly) non-overlapping. For the non-overlapping regions 
of the various class territories, effective mapping of the areas 
("covering" with "influence fields" of Nestor Adaptive Module 
"prototypes") can be rapidly achieved by showing the system a suitable 
training set of patterns that is a representative sample of the classes in 
question. Those portions of a class territory that overlap with some other 
class (or classes) must still be properly mapped out ("covered"). This 
territory must be mapped out for each of the classes laying claim to it in 
the pattern space. If this is done and the pattern spaces of the various 
units in the multi-unit system are sufficiently different from one another 
(ideally, but not necessarily, orthogonal) then the overlapping class 
regions of one pattern space will not be reproduced in some other. (Two 
pattern spaces are orthogonal if, for any event, its representation in one 
space is completely uncorrelated with its representation in the other 
space.) Accordingly, correlation of unit responses from multiple units 
will serve to identify the pattern. As an example of multi-unit 
correlation, consider a two unit system in which Unit 1 (U.sub.1) had 
degenerate class territories for classes A and B while Unit 2 (U.sub.2) 
had degenerate regions for B and C. An example of a class B pattern would 
result in the "confused" responses A or B from U.sub.1 and B or C from 
U.sub.2, which could be correlated to produce the identification B. 
When, within the various unit pattern spaces, class regions are largely 
overlapping rather than largely separated, the multi-unit Nestor System 
disclosed in the above referenced patent application will eventually learn 
to separate the classes but may require long training times and large 
numbers of prototypes. This is due to the fact that in some cases the act 
of separating class territories results in their being covered by many 
prototypes, each of which maps out an amount of the class region that is 
small relative to the size of the total class territory. This results in 
long training times for the system to achieve robust performance on the 
problem. 
SUMMARY OF THE INVENTION 
A principal object of the present invention is to provide a pattern class 
separator and identifier which can separate and identify classes of 
patterns having a wide variety of salient features. 
Another object of the present invention is to provide a pattern class 
separator and identifier which can separate and identify classes of 
patterns which may have only small and subtle differences between them. 
Still another object of the present invention is to provide a specific 
software-implemented embodiment of the present invention which is capable 
of achieving the objects stated immediately above. 
These objects, as well as further objects of the present invention that 
will become apparent from the discussion that follows, are achieved, 
according to the present invention, by providing a pattern classification 
and identification system comprised of (a) a plurality of classification 
units, connected in parallel and which receive an input signal S, 
representing each pattern, and (b) a class selection device (CSD), 
responsive to the output signals produced by the classification units, for 
producing a single output response R representing the class of each 
respective pattern. 
The classification units include both "generalizers" and "separators" which 
store "generalizer prototypes" and "separator prototypes," respectively. 
The system operates to compare each input pattern, first to the 
generalizer prototypes to determine whether such pattern falls within the 
region of influence of at least one generalizer prototype. If a unique and 
certain response to a particular input pattern cannot be produced by such 
comparison, the system compares such input pattern with the separator 
prototypes to determine whether the input pattern falls within a region of 
influence of at least one of these separator prototypes. 
The system, according to the present invention, is a modification of the 
multi-unit Nestor System disclosed in the above-referenced patent 
application Ser. No. 775,144. This system is called "GENSEP" for 
"generalizer/separator." In the GENSEP system, the individual units train 
first to develop mappings that cover the class territories with prototypes 
called generalizers. Generalizer prototypes are not explicitly configured 
to achieve separation of classes in the code space of a unit. Rather, the 
system correlates the multi-unit responses of firing generalizers to 
achieve class separation. Another class of prototypes, called separators, 
develop in the system to effect class separation based upon feature 
subsets of the generalizer coding units. 
Because the system is not attempting separation in the generalizer coding 
units, class coverings develop more rapidly, more robustly and with fewer 
numbers of prototypes. This improves the system's ability to produce 
identifications through the correlations of different units' responses, 
provided the units are not identical in terms of the feature measurements 
they apply to characterize the input event. When correlations among units 
cannot resolve a pattern class, then appeal is made to the separator 
prototypes that carry a subset of the input information that may serve to 
distinguish one class from another. Very often, enough "generalizing" 
units can be defined so that the response derived from correlating all 
such units can reduce the number of tentative classifications to two or at 
worst three. (This has been observed for online character recognition for 
the Western alphanumeric characters.) Then it is a simple matter of 
extracting from the generalizing units the appropriate separating feature 
along which pattern distinctions can reliably be made. In GENSEP we 
introduce a mechanism for committing separator prototypes that embody 
class distinctive features. In fact, a number of such separator prototypes 
are defined and training selects separators that are most effective for 
the kinds of class separation required. The separating prototypes can be 
viewed as implementing "rules" for disambiguating confusions; the system 
learns to formulate these rules as required. In this way the separator 
prototypes can distinguish classes of patterns which may have only small 
and subtle differences between them. 
For a full understanding of the present invention, reference should now be 
made to the following detailed description of the preferred embodiments of 
the invention and to the accompanying drawings.

DESCRIPTION OF THE PREFERRED EMBODIMENTS 
The present invention and its preferred embodiments will now be described 
with reference to FIGS. 1-5 of the drawings. 
A. System Organization Units and Prototypes 
In a preferred embodiment of the GENSEP system according to the present 
invention, as illustrated in FIG. 1, each classification unit U includes 
both (1) a pattern feature encoding device, responsive to the input signal 
S, for producing an intermediate signal F representative of the features 
contained in the pattern, and (2) a pattern classifier response to the 
signal F, for producing an output signal R representative of the 
respective class of the pattern, as identified by the features encoded by 
the feature encoding device. 
Each classification unit U.sub.i sees an input S (the output of the data 
acquisition device, or devices, characterizing the input event) and can 
apply a "code" to the signal to extract from it a set of values F.sub.1 . 
. . F.sub.k. As in the Nestor Adaptive Module as disclosed in the 
above-referenced patents, the unit operates to compare the incoming 
pattern vector F to a set of prototypes P.sup.j, j=1. . . N. This produces 
an output classification R which is indicative of the prototype or 
prototypes (if any) that respond to or match the pattern vector F. As each 
Nestor Adaptive Module is trained, it develops a unique set of prototypes 
for classification of incoming patterns. 
Two types of prototypes develop during training in the Nestor Adaptive 
Modules of a GENSEP system: generalizer prototypes and separator 
prototypes. Generalizer prototypes are committed to the memory assigned to 
a particular unit in order to cover class territories as represented in 
that unit's coding space. Separator prototypes are committed between 
certain pairs of generalizer prototypes in order to separate class 
confusions that can be discriminated on the basis of appeal to a small 
subset of information in the code space of the given unit. 
Thus two types of mechanisms are available for class separation in the 
GENSEP system. Initial discriminations are made on the basis of 
correlating the responses of many different units, which responses are the 
result of activity (firing) among generalizers only in the units. Further 
class discrimination is made by appealing to the classes represented among 
firing separator prototypes in each unit. These mechanisms allow the 
system to train rapidly to make appropriate generalizations about a class 
of patterns and to further refine its ability to distinguish that class of 
patterns from all others either by correlating large numbers of feature 
measurements or by defining precise individual feature values for 
discrimination. 
B. Memory 
B1. The "Prototype" 
As described in the U.S. Pat. No. 4,326,259, memory in a Nestor System is 
composed of "prototypes." Each prototype has some number of input lines 
and one output pathway through which it communicates with other elements 
in the system. There are two different types of prototypes in the system: 
generalizer prototypes and separator prototypes. 
B2. Generalizer Prototypes 
Each generalizer prototype has associated with it a set of weighting 
factors (one for each input line), the prototype vector, P, and a 
threshold .theta., governing whether it is "on" or "off" (firing or not 
firing) in response to an input pattern. The threshold defines a "region 
of influence" for the prototype. The region of influence is the set of all 
input events which will cause the prototype to o fire. This threshold may 
be modifiable. If modifiable, it is adjusted so as to gradually increase 
the size of the prototype region of influence, but it is typically not 
beyond some fixed percentage of the dimensionality of the code space 
(ranging approximately from 5 percent to 50 percent). Each generalizer 
prototype has a class, C, associated with it. Finally, each generalizer 
prototype belongs to a particular unit in the system. The unit is 
specified by an index u. Thus, the data set defining a generalizer 
prototype consists of [P; .theta..sub.g ; C; u]. 
B3. Separator Prototypes 
Like a generalizer prototype, each separator prototype has associated with 
it a set of weighting factors (one for each input line), the prototype 
vector, S, and a threshold .theta..sub.s, partially governing whether it 
is "on" or "off" in response to an input pattern. As with generalizer 
prototypes, this threshold defines a "region of influence" for the 
separator. This threshold is modifiable and adjusted by the system in such 
a way as to decrease the size of the influence field of the separator. 
Separators whose influence field is below some minimum size are considered 
phase II (P2) separators; those above the minimum are called phase I (P1) 
separators. This distinction between the two types of separators lies 
primarily in the extent to which they can influence the classification of 
the pattern within a given unit of the system. 
Additionally, each separator is associated with a pair of generalizers, (i, 
j). More than one separator may be associated with the same generalizer 
pair. Each separator has associated with it an index, k, specifying a 
portion of the code values of the pattern space holding the generalizer 
prototypes with which it is associated. In particular, if a given code 
space represents the pattern event in terms of measurements F.sub.1 . . . 
F.sub.m, then the index associated with a separator will be some number k 
on the interval (l, m). 
Finally, each separator has a class associated with it. Unlike the class 
association of a generalizer, the association of a class with a separator 
is a negation. In particular, if a generalizer prototype for class C fires 
in response to an input event, the system will tend towards the assignment 
of class C to the pattern. However, if a separator for class C fires in 
response to the pattern, the system will tend not to assign C as an 
identification of the pattern. Briefly, if a generalizer for C fires, it 
says "C"; if a separator for C fires, it is saying "not C." 
Thus, the set of data defining a separator can be listed as [i;, j; k; S, 
.theta..sub.s ;C]. 
C. Comparing a Pattern with Prototypes 
Presented below is the procedure, according to the present invention, for 
comparing a pattern with a prototype in system memory. Since generalizer 
and separator prototypes have different properties, the procedures for 
comparing a pattern with a generalizer and a separator prototype are 
discussed separately. These procedures determine whether or not the 
prototype in question will fire in response to the pattern. 
C1. Pattern--Generalizer Comparison 
An input pattern appears to a generalizer prototype as a set of signals 
occurring on its N input lines. The operation of comparing a pattern and a 
generalizer prototype can take any of several forms depending on whether 
the input signals to the prototype are binary or continuous valued. Either 
type of signal can be processed. For brevity we review here only the 
procedure for pattern-generalizer comparison for the case of binary valued 
signals arriving on the N input lines of the generalizer. In this case the 
prototype weighting factor assigned to that line is itself a binary 
number. The total prototype activity is a count of the number of input 
lines on which the bit value of the pattern signal, f.sub.j does not match 
the bit value of the weighting vector, P.sub.j. 
##EQU1## 
This total number of unmatched bits is compared against the prototype 
threshold. If the unmatched bit count is less than the threshold, the 
generalizer fires; if it is greater than or equal to the threshold, the 
prototype is silent. Thus, 
##EQU2## 
As has been noted in above-referenced patent application, the operations of 
comparing a pattern with a set of prototypes can occur in parallel; that 
is to say, the comparison of a pattern with each prototype can occur 
simultaneously. Additionally, in the comparison of a pattern with a given 
prototype, the operation performed on a given input line (bit comparison 
for binary valued inputs or multiplication for continuous valued signals) 
can be performed simultaneously on all input lines. This rich parallelism 
is an inherent feature of the Nestor System. 
C2. Pattern--Separator Comparison 
To review, the data structure of a separator is S=[i, j; k; S, 
.theta..sub.s ; C]. Pattern processing by separator prototypes is similar 
to that by generalizers. A set of signals occurring at the M input lines 
of the separator prototype are compared with the separator weighting 
factor values, an unmatched bit count is determined and tested against the 
separator theshold. However, the generalizers with which the separator is 
paired and the feature index k further define the operation of the 
separator on the pattern. For clarity, we assume that the feature values 
[F.sub.1 . . . F.sub.k ] defining the code vector for the pattern in the 
unit are the continuous, real-valued representation and that the binary 
equivalent of this, the set [B.sub.i ], i=1, . . . M is the information 
appearing at the input lines of the generalizer. Then the feature index, 
k, associated with the separator specifies a member of the 
continuous-valued set F. The binary equivalent of F.sub.k will appear as 
input to the separator S. Specifically, let B be a binary mapping that 
converts F.sub. k to a binary valued vector (b.sub.1 . . . b.sub.m). Then 
the separator unmatched sign count is determined as 
##EQU3## 
Finally, for a separator to fire, the following conditions must hold: 
(1) d&lt;.theta..sub.s (separator threshold condition) 
(2) P.sub.i is firing (associated generalizer prototypes are firing) 
(3) P.sub.j is firing 
Note that both generalizers paired with the separator in question must be 
firing for the separator to fire. 
D. Determining the System Response 
D1. Unit Response to a Pattern 
The response of a unit to an incoming pattern consists of the classes 
associated with its firing prototypes. In particular, those classes are 
organized into two lists, the generalizer class list and the separator 
class list. Obviously, due to the conditions required for separator 
firing, if the generalizer class list of a given unit is empty, the 
separator class list for that unit will be empty as well. 
D2. System Response to the Pattern 
The system response to an incoming pattern is determined by the Class 
Selection Mechanism (CSM) as a function of the output class lists (from 
both generalizers and separators) of the system units. The CSM can 
evaluate the contents of the class lists of all units in a variety of ways 
as a function of unit priority. Two preferred embodiments of the class 
selection mechanism are illustrated in FIGS. 2 and 3, respectively. 
As in the multi-unit system described in the abovereferenced patent 
application, units in the GENSEP system can be arranged hierarchically, 
according to priority. Unit priorities are numbers that take on integer 
values 1, 2, 3, etc. A unit of priority n is said to operate at level n in 
the system. In determining the system response, the CSM considers the 
output of each unit in order of decreasing priority. (The highest priority 
is 1.) At each unit, the CSM updates a system vote count for each class 
and checks to determine if any particular class has satisfied the system 
identification criterion to allow for an unambiguous response. A typical 
system identification criterion defines the winning class as the class 
with the largest number of votes, as long as its vote count exceeds some 
minimum vote count (NUMWIN) and so long as the difference between the vote 
count of this class and that of the "runner-up" class exceeds some pre-set 
minimum difference (WINDIF). 
The CSM can update the system vote count in different ways. In one method, 
the CSM polls the system units twice, in each case starting with the 
highest priority unit and moving through the units in order of descending 
priority. In the first polling, the CSM updates the system vote count on 
the basis of the generalizer class list. If a winning class has not been 
found by the time all the generalizer class lists of the lowest priority 
units have been polled, then the CSM initiates a second polling of the 
units. It begins by thresholding the system class list and throwing out 
all those classes below some specified minimum vote count. Then, beginning 
with the highest priority units, the CSM updates the system vote count as 
a function of the classes in the separator class lists for these units. In 
general, the appearance of a class in the separator class list causes the 
system vote count for that class to be decremented by 1. Again, after a 
unit's separator class list has been used to update the system vote count, 
if a winning class has not been found, then the unit of next lowest 
priority is processed. 
In another embodiment of the system, shown in FIG. 3, the CSM polls each 
unit only once. The system vote count is updated as a function of the net 
number of votes for a class given the composition of both the generalizer 
and the separator class lists for the given unit. For example, the 
appearance of a class in the generalizer class list would increment its 
system vote count by 1; the appearance of a class in the separator class 
list would reduce its vote by 1. In such an embodiment, the system tends 
to rely less upon correlations between unit responses as a means of 
distinguishing classes and more on the internal discriminating ability of 
individual coding units at the level of single feature distinctions. 
D3. Types of System Response 
As in the multi-unit Nestor System described in the above-referenced patent 
application, the GENSEP system offers, as a final output, a system class 
list (