TY - GEN

T1 - Efficient negative selection algorithms by sampling and approximate counting

AU - Textor, Johannes

PY - 2012

Y1 - 2012

N2 - Negative selection algorithms (NSAs) are immune-inspired anomaly detection schemes that are trained on normal data only: A set of consistent detectors - i.e., detectors that do not match any element of the training data - is generated by rejection sampling. Then, input elements that are matched by the generated detectors are classified as anomalous. NSAs generally suffer from exponential runtime. Here, we investigate the possibility to accelerate NSAs by sampling directly from the set of consistent detectors. We identify conditions under which this approach yields fully polynomial time randomized approximation schemes of NSAs with exponentially large detector sets. Furthermore, we prove that there exist detector types for which the approach is feasible even though the only other known method for implementing NSAs in polynomial time fails. These results provide a firm theoretical starting point for implementing efficient NSAs based on modern probabilistic techniques like Markov Chain Monte Carlo approaches.

AB - Negative selection algorithms (NSAs) are immune-inspired anomaly detection schemes that are trained on normal data only: A set of consistent detectors - i.e., detectors that do not match any element of the training data - is generated by rejection sampling. Then, input elements that are matched by the generated detectors are classified as anomalous. NSAs generally suffer from exponential runtime. Here, we investigate the possibility to accelerate NSAs by sampling directly from the set of consistent detectors. We identify conditions under which this approach yields fully polynomial time randomized approximation schemes of NSAs with exponentially large detector sets. Furthermore, we prove that there exist detector types for which the approach is feasible even though the only other known method for implementing NSAs in polynomial time fails. These results provide a firm theoretical starting point for implementing efficient NSAs based on modern probabilistic techniques like Markov Chain Monte Carlo approaches.

UR - http://www.scopus.com/inward/record.url?scp=84866382198&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-32937-1_4

DO - 10.1007/978-3-642-32937-1_4

M3 - Conference contribution

AN - SCOPUS:84866382198

SN - 9783642329364

VL - 7491 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 32

EP - 41

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

T2 - 12th International Conference on Parallel Problem Solving from Nature, PPSN 2012

Y2 - 1 September 2012 through 5 September 2012

ER -