Negative Selection Algorithms Without Generating Detectors

Maciej Liskiewicz, Johannes Textor

Abstract

Negative selection algorithms are immune-inspired classifiers that are trained on negative examples only. Classification is performed by generating detectors that match none of the negative examples, and these detectors are then matched against the elements to be classified. This can be a performance bottleneck: A large number of detectors may be required for acceptable sensitivity, or finding detectors that match none of the negative examples may be difficult. In this paper, we show how negative selection can be implemented without generating detectors explicitly, which for many detector types leads to polynomial time algorithms whereas the common approach to sample detectors randomly takes exponential time in the worst case.

In particular, we show that negative selection on strings with generating all detectors can be efficiently simulated without detectors if, and only if, an associated decision problem can be answered efficiently, regardless the detector type. We also show how to efficiently simulate the more general case in which only a limited number of detectors is generated. For many detector types this non-exhaustive negative selection is more meaningful but it can be computationally more difficult, which we illustrate using Boolean monomials.
Original languageEnglish
Title of host publicationProceedings of the 12th Annual Conference on Genetic and Evolutionary Computation
Number of pages8
Place of PublicationNew York, NY, USA
PublisherACM
Publication date07.2010
Pages1047-1054
ISBN (Print)978-1-4503-0072-8
DOIs
Publication statusPublished - 07.2010
EventGECCO '10 Proceedings of the 12th annual conference on Genetic and evolutionary computation - Portland, United States
Duration: 07.07.201011.07.2010

Fingerprint

Dive into the research topics of 'Negative Selection Algorithms Without Generating Detectors'. Together they form a unique fingerprint.

Cite this