An immunological approach to change detection: theoretical results
- 23 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
This paper examines some of the theoretical foundations of the distributable change detection method introduced by Forrest et al., including fundamental bounds on some of its parameters. A short overview is given of the reasoning behind this method, its immunological counterpart and its computer implementation. The amount of information that is lost by splitting a data stream into unordered strings can be estimated, and this estimate can be used to guide the choice of string length. A lower bound on the size of the detector set is derived, based on information-theoretic grounds. The principle of holes (undetectable nonself strings) is illustrated, along with a proof of their existence for a large class of matching rules. The influence of holes on the achievable failure rate is discussed, along with guidelines on how to avoid them.Keywords
This publication has 8 references indexed in Scilit:
- A sense of self for Unix processesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- An immunological approach to change detection: algorithms, analysis and implicationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Self-nonself discrimination in a computerPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Elements of Information TheoryPublished by Wiley ,2001
- T cell tolerance by clonal elimination in the thymusCell, 1987
- The thermodynamics of computation—a reviewInternational Journal of Theoretical Physics, 1982
- Theoretical studies of clonal selection: Minimal antibody repertoire size and reliability of self-non-self discriminationJournal of Theoretical Biology, 1979
- On the Length of Programs for Computing Finite Binary SequencesJournal of the ACM, 1966