Negative selection algorithm
The negative selection algorithm is inspired by the self-non-self discriminating behavior observed in the immune system acquired by mammals. The theory of acquired immunity takes into account the adaptive behavior of the immune system, including the continued selection and proliferation of cells that select potentially harmful (and usually foreign) material in the body. An interesting aspect of this process is that it is responsible for managing a population of immune cells that do not select tissues in the body, in particular it does not create self-reactive immune cells called autoimmunity.
This problem is known as self-discrimination, and it involves the preparation and ongoing maintenance of a repertoire of immune cells so that none are autoimmune. This is achieved by a negative selection process which selects and removes cells that are autoreactive during cell creation and proliferation. This process has been observed in the preparation of T cells, the naive versions of which are matured using a positive and negative selection process in the thymus.
The principle of self-non-self discrimination suggests that the anticipatory assumptions made in the clonal selection are filtered by regions of infeasibility (protein conformations that bind to self-tissues). Moreover, the self-non-self immunological paradigm proposes the modeling of the unknown domain (pathogen encountered) by modeling the complement of what is known. This is not intuitive because the natural tendency is to classify unknown information by what is different from what is known, rather than guessing the unknown information and filtering those guesses by what is known.
The information processing principles of the process of self-non-self discrimination by the negative selection algorithm are those of the anomaly and change detection systems which model the anticipation of the variation of what is known. . The principle is achieved by building a model of changes, anomalies or unknown data (non-normal or non-self) by generating models that do not correspond to an existing corpus of available models (normal or self). The prepared non-normal model is then used to monitor existing normal data or new data streams by looking for matches with the non-normal models.
The following algorithm provides a pseudocode of the detector generation procedure for the negative selection algorithm.
The following algorithm provides a pseudocode of the detector application procedure for the negative selection algorithm.
The negative selection algorithm was designed for change detection, novelty detection, intrusion detection and recognition of similar patterns and two-class classification problem areas. Traditional negative selection algorithms used binary representations and binary matching rules such as Hamming distance and r-contiguous bits.
A data representation should be selected that best suits a given problem domain, and a matching rule is in turn selected or matched to the data representation. Detectors can be prepared without prior knowledge of the definition field other than the known dataset (normal or standalone).
The algorithm can be configured to balance the convergence of the detectors (quality of matches) and the complexity space (number of detectors). The lack of dependency between detectors means that the preparation and application of detectors are inherently parallel and suitable for distributed and parallel implementation, respectively.