Artificial Immune System for Recognizing Patterns
- Created on Monday, 01 August 2005
This method offers robust performance in analysis of large sets of data.
A method of recognizing or classifying patterns is based on an artificial immune system (AIS), which includes an algorithm and a computational model of nonlinear dynamics inspired by the behavior of a biological immune system. The method has been proposed as the theoretical basis of the computational portion of a star-tracking system aboard a spacecraft. In that system, a newly acquired star image would be treated as an antigen that would be matched by an appropriate antibody (an entry in a star catalog). The method would enable rapid convergence, would afford robustness in the face of noise in the star sensors, would enable recognition of star images acquired in any sensor or spacecraft orientation, and would not make an excessive demand on the computational resources of a typical spacecraft. Going beyond the star-tracking application, the AIS-based pattern-recognition method is potentially applicable to pattern- recognition and -classification processes for diverse purposes — for example, reconnaissance, detecting intruders, and mining data.
This AIS method is capable of efficient analysis of large sets of data, including sets that are characterized by high dimensionality and/or are acquired over long time intervals. When the method is used for unsupervised or supervised classification, the amount of computation scales linearly with the number of dimensions and offers performance that is both (a) nearly independent of the total size of the set of data and (b) equal to or better than the performances of traditional clustering methods. When used for pattern recognition, the method efficiently finds appropriate matches in the data. The method enables efficient classification of a high-dimensional set of data in a single pass through the data, and quickly flags outliers in much the same way as the human immune system produces antibodies to invading antigens.
The AIS model in this method is embodied in a set of partial differential equations that approximate some aspects of the dynamics of a network of immune-system B cells:
where bi is the number of cells of clone i, t is time, s is a rate of influx, p is a maximal growth rate, ? is a growth clone-size threshold, f(hi,h'i) is a cell activation function, hi is a binding field, h'i is a cross-linking field, KiA is a measure of the affinity of a clone-i antibody for the antigen (the pattern to be recognized), and d is a death rate. The functions f(hi,h'i), hi, and h'i are defined by additional equations that must be omitted here for the sake of brevity. Suffice it to say that the cell activation function, f(hi,h'i), depends on the binding between the B-cell populations in the network. Cells having greater affinity with the incoming pattern (cells representing closer matches to the pattern) clone themselves (with or without mutation) faster than do those having lesser affinities (representing poorer matches).
The unsupervised classification process for this model starts with a single sequential presentation of the data to a randomly initialized set of cell populations. As a result of this mode of presentation, the amount of computation in the classification process is of the order of a number proportional to the number of dimensions of the input data. An affinity radius around each incoming pattern is used to cull the number of clone populations that respond each time. The system is allowed to evolve in time, and the clone population that survives is used as the class for each pattern. Typically, 10 to 20 computational cycles are all that are needed for convergence for each incoming item.
The method has been demonstrated by applying it to a high dimensional data set representing images, synthesized from images acquired by a spaceborne imaging spectrometer in 18 wavelength bands, that show various attributes of the Marquesas Islands and vicinity (see figure). Details of individual islands are difficult to discern in any one of the images, but after classification of the image data by the present AIS method, the dominant island groups can be discerned more easily.
This work was done by Terrance Huntsberger of Caltech for NASA’s Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.techbriefs.com/tsp under the Information Sciences category.
The software used in this innovation is available for commercial licensing. Please contact Karina Edmonds of the California Institute of Technology at (818) 393-2827. Refer to NPO-40256.
This Brief includes a Technical Support Package (TSP).
Artificial Immune System for Recognizing Patterns (reference NPO-40256) is currently available for download from the TSP library.
Please Login at the top of the page to download.