Concordia University's DEC LAB: Research at the DEC LAB

The aim of project CellNet is the creation of a software system capable of automatically evolving complete pattern recognizers for arbitrary pattern sets, and utilizing as little expert input as possible. This is, indeed, an ambitious goal, requiring much additional work. This paper describes a step toward that goal: Using the CellNet system, use co-evolution to evolve increasingly more robust pattern recognizers capable of correctly classifying noisy and deformed patterns from a large pattern database. One important result of this approach is the elimination of the perennial problem of overfitting.

A Pattern Recognition System is almost always defined in terms of two functionalities: the description of patterns and the identification of those patterns. The first functionality is called feature extraction and the second, pattern classification. Since there are many types of patterns in this world ranging from the images of fruit flies to those of signatures and thumb prints, the focus of most research endeavours in pattern recognition has rightfully been directed towards the invention of features that can capture what is most distinctive about a pattern. This leads to two overlapping areas of research associated with features: feature selection and feature creation. Feature selection has to do with choosing a small set of features from a larger set, in order to maximize the rate of recognition of an associated classifier, and simultaneously reduce the (computational) cost of classification. Feature creation, on the other hand, has to do with the creation or growth of complex features from a finite set of simpler ones, also for the benefit of an associated classifier. Both areas of research are reviewed below.

Siedlecki in [11] is the first paper to suggest the use of GA for feature selection. Ten years later, Kudo [6] demonstrates the superiority of GA over a number of traditional search & optimization methods, for sets with a large number of features. Vafaie [13] shows that a GA is better than Backward Elimination in some respects, including robustness. Guo [4] uses a GA for selecting the best set of inputs for a neural network used for fault diagnosis of nuclear power plant problems. Moser [8] surveys previous attempts at speeding up the action of GA, and then proposes two new architectures of his own: VeGA, which uses parallelism to simultaneously evaluate different sets of features (on one computer), and DveGA, which utilizes an adaptive load balancing algorithm to use a network of heterogeneous computers to carry out the various evaluations. Shi [10] applies a GA to the selection of relevant features in hand-written Chinese character recognition. Fung [2] uses a GA to minimize the number of features required to achieve a minimum acceptable hit-rate, in signature recognition. Yeung [14] succeeds in using a GA in tuning four selectivity parameters of a Neocognitron, which is used to recognize images of hand-written Arabic Numerals.

The first paper to speak about feature creation appears to be [12]. In his work, Stentiford uses evolution to create and combine a set of features (into a vector), which is compared to reference vectors, using nearest-neighbour classifiers. A single feature is a set of black- or white-expecting pixel locations. The results were generated using a training set of 30,600 printed characters and a test set of 10,200 printed characters. The error rate, on the test set, was 1.01%, and was obtained using 316 nearest-neighbour classifiers automatically generated by the evolutionary system. More recently, a group of researchers including Melanie Mitchell used evolution to create features for use in analyzing satellite and other remote-sensing captured images [1]. Specifically, the researchers defined a genetic programming scheme for evolving complete image processing algorithms for, for example, identifying areas of open water. Their system called GENIE successfully evolved algorithms that were able to identify the intended ground features with 98% accuracy.

It was natural for researchers to move from feature creation to attempt to create whole pattern recognition systems. After all, the hardest part of successful pattern recognition is the selection/creation of the right set of features. Indeed, the first such systems seem to have focused on the evolution of features or feature complexes, which are useful for classification. Two systems described below do this. CellNet [5] blurs the line between feature selection and the construction of binary classifiers out of these features. HELPR [9] also evolves feature detectors, but the classification module is completely separate from the feature extraction module. Other differences exist, but, both attempts are the only systems, that we know of, that aim at using artificial evolution to synthesize complete recognition systems (though currently for different application domains), with minimum human intervention.

CellNet is an ongoing research project aiming at the production of an autonomous pattern recognition software system, for a large selection of pattern types. Ideally, a CellNet operator would need little to no specialized knowledge to operate the system. To achieve this, CellNet divides the problem (and hence the solution) into two parts: feature creation and classifier synthesis.

The long-term goal of the CellNet project is the inclusion of methodologies for the simultaneous evolution of both feature and classifiers (Cells and Nets); at present, however, a set of hard-coded features are used. Some interesting perspectives are offered as to how an evolvable feature creation framework may be structured; The most interesting of these suggestions is the use of a pre-processing routine deconstructing images using techniques inspired by pre-attentive vision in humans - from there, a wide array of possible machine learning techniques may be used.

In its current form, CellNet is capable of evolving classifiers for a given set of patterns. To achieve this it uses a specialized genetic operator: Merger. Merger is an operator, somewhat similar to that used in MessyGAs [3], designed to allow the algorithm to search increasingly larger feature spaces in an incremental manner; This is different from a normal GA, where the dimensionality of the search space is fixed at the start of the run. CellNet is cast as a general system, capable of self-adapting to many hand-written alphabets, currently having been applied to both Arabic and Indian numbers. This paper may be viewed as an extension of the CellNet system - as such, CellNet is described in more detail in section 2.

HELPR is composed of two modules: a features extraction module and a classification module. The classification system is not evolvable; only the feature extractor is. The feature extraction module is made of a set of feature detectors. Its input is the raw input pattern and its output is feature vector. The system is designed to handle signals (not visual patterns or patterns in general).

Each feature extractor has two stages: a transformation network followed by a capping mechanism. A transformation network utilizes a set of morphological operations (such as Open and Erode) with structuring elements in addition to a small number of arithmetic operations (such as addition and multiplication). As such a transformation network (or TN) represents a mixed morpho-arithmatic expression which transforms an n-element digitized input signal into an n-element output signal. The purpose of the TN is to highlight those features of the input signal that are most distinctive of the target classes. On the other hand, the purpose of the capping mechanism (which is a single-layer of perceptrons) is to transform the n-element signal coming out of the TN into a k-element array of scalars, where k is the number of target classes defined by the user. Ideally, every element will return a +1 for a single class and -1 for the rest.

The most interesting features of this work is that a) it adopts a holistic approach to the evolution of pattern classifiers: it boldly states, starting with the title, that such a goal is possible; b) it demonstrates that it is possible for a computerized system to automatically evolve a pattern classifier, which can be used for a real-world application; c) it augments the standard evolutionary processes in very creative ways to produce a customized system, which perform well and e) it suggests that it is possible to use of a small set of morphological operations (in addition to simple arithmetic) to characterize a wide range of signals. There is no doubt that this paper, as well as the CellNet architecture are examples of a new trend in pattern classification: that of the autonomous pattern recognizer. However, there is also no doubt that both works still have a number of deficiencies to deal with.

Both HELPR and CellNet only evolve part of the system: other parts of the system are hard-coded. In addition, both systems have a large number of parameters that are manually set by an expert user. Finally, both systems only work on specific input signals/images; the promise of extension is there but not yet realized. This is why the following set of problems must be dealt with:

1. Feature Creation (or Detection) mechanisms that are suited to large sets of classification problems. This is to eliminate the need for serious re-configuration or worse still, re-engineering, every time a different application domain is targeted.

2. Elimination of Parameters, many of which need to be set by the user before the system is exploited. These parameters include: probability distributions types, probability values, population size, number of feature extractors and so on.

3. Thorough Testing of the evolved system against a diverse set of pattern databases (and not just Radar signatures or Arabic Numerals), and doing so, without subjecting the system to any amount of re-configuration.

This paper may be viewed as a step towards the realization of points 2 and 3; Co-Evolution is demonstrated to help eliminate the problem of overfitting in the creation of a classifier, hence eliminating the need for an expert to manually determine the correct parameters; Additionally, the camouflage routines presented aid in the diversification of a given pattern database, allowing for greater variance in any given set of data.

CellNet hunters were first introduced in [5], a reader interested in their formal representation is urged to consult that source - our implementation is identical. However, given they are an entirely new and rather complicated representation for pattern recognizers, we offer an informal explanation of their structure, along with some illustrative examples.

The basis on which Hunters are built is a set of normalized feature functions; The functions (all applied to thinned figures) used by CellNet CoEv are {parameterized histograms, central moments, Fourier descriptors, Zernike moments, normalized width (of a bounding box), normalized height, normalized length, number of terminators, numer of intersections}. However, for the purposes of explanation, we shall assume that our examples use only two: F₁ and F₂. This assumption is made for ease of visual representation of a 2-dimensional Feature Space, and is easily generalized.

A Hunter is a binary classifier - a structure which accepts an image as input, and outputs a classification. The fitness function which is used to drive the Genetic Algorithm determines which digit the agent classifies; For example, assuming our fitness function specifies that we are evolving Hunters to recognize the digit "ONE", a Hunter which returns "yes" given an image will implicitly be stating that the image is a "ONE", as opposed to "NOT-ONE", i.e. any other digit. We will refer to these classes as the primary class and the non-primary class. Hence, a Hunter outputs a value from {PRIMARY, NON-PRIMARY, UNCERTAIN} when presented with an image.

A Hunter consists of Cells, organized in a Net. A Cell is a logical statement - it consists of the index of a Feature Function, along with bounds. Every cell is represented by the following format:

Feature Function F_i

Bound b₁

Bound b₂

Provided with an image I, a cell returns TRUE, if b₁ < F_i (I) < b₂, and FALSE otherwise.

A Net is an overall structure which organizes cells into a larger tri-valued logical statement. That is, a Net is a logical structure which combines the TRUE / FALSE values of its constituent Cells to return a value from {PRIMARY, NON-PRIMARY, UNCERTAIN}.

The structure of a Net is as follows: A Net is a tree, with a voting mechanism as its root node. At depth 1, there are a set of one or more Chromosomes.

Chromosomes consist of trees which begin with a Class Bit - this bit determines whether or not the Chromosome votes for "PRIMARY" or "NON-PRIMARY". Following the Class Bit is a tree of one or more Cells, connected into a logical structure by AND and NOT nodes. A Chromosome may be represented as a string as follows:

Class Bit C

[NOT]

Cell₁

AND

[NOT]

Cell₂

AND

Hence, a chromosome is a logical statement, which returns TRUE or FALSE. A Chromosome will return C if the logical statement returns TRUE - otherwise it will remain silent.

A Net is a collection of such Chromosomes, connected via a Vote mechanism. The Vote mechanism collects input from each Chromosome (although some Chromosomes will remain silent), consisting of a series of zero or more values of "PRIMARY" or "NON-PRIMARY". The Vote mechanism will tally the number of each, and output the majority, or "UNCERTAIN" in the case of no input or a tie.

For example, consider the following Example Agent, specified by the two Chromosomes chromosome1 and chromosome2:

A Hunter is a Net - that is, a Hunter is an organized collection of one or more Cells, which when presented with an image, will return one of "PRIMARY", "NON-PRIMARY" or "UNCERTAIN". The complexity of a Hunter is the number of cells it contains, regardless of organization.

The following are some examples of Hunters with complexity one, and interpretations in a two-dimensional feature space. Assume the Primary class is "ONE", and the non-primary class is "NOT-ONE".

Our first Hunter, A₁, consist of a single cell in a single chromosome - It is illustrated in Fig. 2.1.3.1. It is instructive to consider the Feature Space of all images on the basis of Feature F₁ and F₂ - every image maps to an <x,y> coordinate in this space, and hence may be drawn in a unit square. Agent A₁ may be viewed as a statement which partitions Feature Space into three disjoint sets - this is also illustrated in Fig. 2.1.3.1. A second Hunter, A2, is illustrated in Fig. 2.1.3.2; This agent's partition of the same feature space is also illustrated.

Thus far, we have given examples only of Hunters with complexity one - this is the state of the CellNet Co-Ev system when initialized. What follows is a system of cooperative co-evolution which generates agents of increasing complexity.

Cooperative Co-evolution is achieved through the inclusion of a new Genetic Operator, augmenting the typical choices of Crossover and Mutation. This new operator, Merger, serves to accept two Hunters and produce a single new Hunter of greater complexity; The complexity of the merged Hunter will be the sum of the complexities of the parents.

Merger operates at the level of Chromosomes - when merging two Hunters, Chromosomes are paired randomly, and merged either Horizontally or Vertically. Vertical Merger simply places both Chromosomes in parallel under the Vote mechanism - they are now in direct competition to determine the outcome of the Vote. Horizontal Merger, on the other hand, combines the two Chromosomes to produce a single and more complex Chromosome, where the two original Chromosomes are connected via a AND or AND-NOT connective. Hence, Horizontal Merger serves to refine a particular statement in the vote mechanism.

There are several decisions made when selecting which type of Merger is undertaken, and how connections are made in the Horizontal case - these decisions are under the control of two Affinity bits which are associated with each Chromosome. These Affinity bits ensure that all decisions are under genetic control, and may be selected for. For more detail, refer to [5].

The Cooperative Co-evolution of Hunters, as realized through Merger is a technical process, more easily explained visually. We re-consider agents A₁ and A₂ of Section 3.1.3, considering their children through the Merger operator.

Consider the Horizontal Merger of Hunters A₁ and A₂ - here, we produce agent A₃ by combining the Chromosomes of A₁ and A₂ into one new one, linked via an AND connective. As is visible in Fig. 2.1.5.1, Horizontal Merger may be viewed as the refinement of a partition created by two Chromosomes.

In contrast, consider the Vertical Merger of these same two Hunters, producing agent A₄ - in this case, the Chromosomes are combined directly under the Vote mechanism. As shown in Fig. 2.1.5.2, Vertical Merger may be loosely be viewed as the union of the partitions generated by two Chromosomes.