Negative selection algorithm
The negative selection algorithm is inspired by the self-non-self discrimination behavior observed in the mammalian acquired immune system. The acquired immunity theory takes into account the adaptive behavior of the immune system, including the continuous selection and proliferation of cells that select for 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 for tissues in the body, specifically 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 such that none are autoimmune. This is achieved by a process of negative selection that selects and removes cells that are self-reactive during cell creation and proliferation. This process has been observed in the preparation of T cells, the naïve 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 self-non-self discrimination process by the negative selection algorithm are those of anomaly and change detection systems that model the anticipation of variation from what is known . The principle is achieved by building a pattern of changes, anomalies, or unknown data (non-normal or non-self) by generating patterns that do not match an existing corpus of available patterns (normal or self). The prepared non-normal pattern is then used to monitor existing normal data or streams of new data looking for matches to the non-normal patterns.
The following algorithm provides a pseudocode of the detector generation procedure for the negative selection algorithm.
The following algorithm provides 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 similar pattern recognition and two-class classification problem domains. 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.
