Transcript Artificial Immune Systems: A New Computaional Intelligence

Artificial Immune Systems: A
New Computational
Intelligence Approach
New Trends in Intelligent Information Processing
and Web Mining.
Zakopane, Poland,
June 2-5, 2003
Jonathan Timmis
Computing Laboratory
University of Kent
CT2 7NF. UK.
[email protected]
http:/www.cs.kent.ac.uk/~jt6
Novel paradigms are proposed and
accepted not necessarily for being faithful
to their sources of inspiration, but for
being useful and feasible
What do I want to achieve?
Give you a taster of what AIS is all about
Define an AIS
Why do we find the immune system useful?
Explain what AIS are
Show you where they are being used
Some high level case studies
Comments for the future
I won’t
Talk about all areas of AIS and applications
Talk too much about how AIS relate to other
bioinspired ideas (although I will mention it)
Go into too much detail: this is an introduction
Outline
What are AIS?
Useful immunology
Thinking about AIS
Application Areas and Case Studies
The Future
Why the Immune System?
Recognition
Anomaly detection
Noise tolerance
Robustness
Feature extraction
Diversity
Reinforcement learning
Memory; Dynamically changing coverage
Distributed
Multi-layered
Adaptive
A Definition
AIS are adaptive systems inspired by
theoretical immunology and observed
immune functions, principles and models,
which are applied to complex problem
domains
Some History
Developed from the field of theoretical
immunology in the mid 1980’s.
Suggested we ‘might look’ at the IS
1990 – Bersini first use of immune algos to
solve problems
Forrest et al – Computer Security mid
1990’s
Hunt et al, mid 1990’s – Machine learning
Scope of AIS:
Computer Security(Forrest’94’96’98,
Kephart’94, Lamont’98’01,02,
Dasgupta’99’01, Bentley’00’01,02)
Anomaly Detection (Dasgupta’96’01’02)
Fault Diagnosis (Ishida’92’93, Ishiguro’94)
Data Mining & Retrieval (Hunt’95’96,
Timmis’99’01, ’02)
Pattern Recognition (Forrest’93, Gibert’94, de
Castro ’02)
Adaptive Control (Bersini’91)
Scope of AIS (Cont……):
Job shop Scheduling (Hart’98, ’01, ’02)
Chemical Pattern Recognition (Dasgupta’99)
Robotics (Ishiguro’96’97,Singh’01)
Optimization (DeCastro’99,Endo’98, de Castro
’02)
Web Mining (Nasaroui’02)
Fault Tolerance (Tyrrell, ’01, ’02, Timmis ’02)
Autonomous Systems (Varela’92,Ishiguro’96)
Engineering Design Optimization (Hajela’96 ’98,
Nunes’00)
And so on …
Outline
What are AIS?
Useful immunology
Thinking about AIS
Application Areas and Case Studies
The Future
Role of the Immune System
Protect our bodies from pathogen and
viruses
Primary immune response
Launch a response to invading pathogens
Secondary immune response
Remember past encounters
Faster response the second time around
How does it work: A simplistic view
Immune cells
There are two primarily types of
lymphocytes:
B-lymphocytes (B cells)
T-lymphocytes (T cells)
Others types include macrophages,
phagocytic cells, cytokines, etc.
Self/Non-Self Recognition
Immune system needs to be able to
differentiate between self and non-self cells
Antigenic encounters may result in cell
death, therefore
Some kind of positive selection
Some element of negative selection
Antigen
Substances capable of starting a specific
immune response commonly are referred to
as antigens
This includes some pathogens such as
viruses, bacteria, fungi etc .
Immune Pattern Recognition
BCR or Antibody
B-cell Receptors (Ab)
Epitopes
Antigen
B-cell
The immune recognition is based on the complementarity
between the binding region of the receptor and a portion of
the antigen called epitope.
Antibodies present a single type of receptor, antigens
might present several epitopes.
This means that each antibody can recognize a single antigen
Clonal Selection
Clonal deletion
(negative selection)
Self-antigen
Proliferation
(Cloning)
M
M
Antibody
Memory cells
Selection
Differentiation
Plasma cells
Foreign antigens
Self-antigen
Clonal deletion
(negative selection)
Main Properties of Clonal
Selection (Burnet, 1978)
Elimination of self antigens
Proliferation and differentiation on contact of mature
lymphocytes with antigen
Restriction of one pattern to one differentiated cell and
retention of that pattern by clonal descendants;
Generation of new random genetic changes,
subsequently expressed as diverse antibody patterns by
a form of accelerated somatic mutation
Immune Network Theory
Idiotypic network (Jerne, 1974)
B cells co-stimulate each other
Treat each other a bit like antigens
Creates an immunological memory
Suppression
Negative response
Paratope
Ag
1
2
Idiotope
3
Antibody
Activation
Positive response
Reinforcement Learning and
Immune Memory
Repeated exposure to an antigen throughout
a lifetime
Primary, secondary immune responses
Remembers encounters
No need to start from scratch
Memory cells
Continuous learning
Learning (2)
Antibody Concentration
Cross-Reactive
Response
Secondary Response
Primary Response
Lag
Lag
Response
to Ag1
Lag
Response
to Ag1
...
...
Antigen Ag1
Antigens
Ag1, Ag2
...
Response to
Ag1 + Ag3
Response
to Ag2
...
Antigen
Ag1 + Ag3
Time
Immune System: Summary
Define host (body cells) from external entities.
When an entity is recognized as foreign (or
dangerous)- activate several defense mechanisms
leading to its destruction (or neutralization).
Subsequent exposure to similar entity results in
rapid immune response.
Overall behavior of the immune system is an
emergent property of many local interactions.
So it is useful?
Outline
What are AIS?
Useful immunology
Thinking about AIS
Application Areas and Case Studies
The Future
Artificial Immune Systems
AIS are adaptive systems inspired by
theoretical immunology and observed
immune functions, principles and models,
which are applied to complex problem
domains
This Section
General Framework for describing and
constructing AIS models
A short review of where AIS are used today
Can not cover them all, far too many
Also we are not experts in all application areas !
Where are AIS headed?
What do want from a
Framework?
In a computational world we work with
representations and processes. Therefore,
we need:
To be able to describe immune system
components
Be able to describe their interactions
Quite high level abstractions
Capture general purpose processes that can be
applied to various areas
General Framework for AIS
Immune Algorithms
Affinity Measures
Representation
Application Domain
Representation – Shape Space
Describe the general shape of a molecule
•Describe interactions between molecules
•Degree of binding between molecules
Representation
Vectors
Ab = Ab1, Ab2, ..., AbL
Ag = Ag1, Ag2, ..., AgL
Real-valued shape-space
Integer shape-space
Binary shape-space
Symbolic shape-space
Define their Interaction
Define the term Affinity
Distance measures such as Hamming,
Manhattan etc. etc.
Affinity Threshold
Basic Immune Models and
Algorithms
Negative Selection Algorithms
Clonal Selection Algorithm
Immune Network Models
Somatic Hypermutation
Negative Selection (NS) Algorithms
Forrest 1994: Idea taken from the negative
selection of T-cells in the thymus
Applied initially to computer security
Split into two parts:
Censoring
Monitoring
Self
strings (S)
Generate
random strings
(R0)
Detector Set
(R)
Match
No
Yes
Reject
Detector
Set (R)
Protected
Strings (S)
Match
Yes
Non-self
Detected
No
Clonal Selection Algorithm (de
Castro & von Zuben, 2001)
1. Initialisation: Randomly initialise a population (P)
2. Antigenic Presentation: for each pattern in Ag, do:
2.1 Antigenic binding: determine affinity to each P’
2.2 Affinity maturation: select n highest affinity from P and clone
and mutate prop. to affinity with Ag, then add new mutants to P
3. Metadynamics:
3.1 select highest affinity P to form part of M
3.2 replace n number of random new ones
4. Cycle: repeat 2 and 3 until stopping criteria
Discrete Immune Network
Models (Timmis & Neal, 2001)
1.
2.
Initialisation: create an initial network from a sub-section of the antigens
Antigenic presentation: for each antigenic pattern, do:
2.1 Clonal selection and network interactions: for each network cell,
determine its stimulation level (based on antigenic and network interaction)
2.2 Metadynamics: eliminate network cells with a low stimulation
2.3 Clonal Expansion: select the most stimulated network cells and
reproduce them proportionally to their stimulation
2.4 Somatic hypermutation: mutate each clone
2.5 Network construction: select mutated clones and integrate
3. Cycle: Repeat step 2 until termination condition is met
Somatic Hypermutation
Mutation rate in proportion to affinity
Very controlled mutation in the natural immune
system
Trade-off between the normalized antibody
affinity D* and its mutation rate ,
1
0.9
0.8
0.7
 = 5
0.6

0.5
 = 10
0.4
 = 20
0.3
0.2
0.1
0
0
0.1
0.2
0.3
0.4
0.5
D*
0.6
0.7
0.8
0.9
1
Case Study: Data Mining
Data mining: Problem
description
More benchmark problem in this case
Assume a set of labelled vectors
Classification
AIRS: (Artificial Immune
Recognition System) Watkins 2003
Clonal Selection
Based initially on immune networks, though
found this did not work
Resource allocation
Somatic hypermutation
Eventually
Antibody/antigen binding
AIRS: Mapping from IS to AIS
Antibody
Recognition
Ball
Antigens
Immune Memory
Feature Vector
Combination of feature
vector and vector class
Training Data
Memory cells—set of
mutated ARBs
Classification
Stimulation of an ARB is based not only on its
affinity to an antigen but also on its class when
compared to the class of an antigen
Allocation of resources to the ARBs also takes
into account the ARBs’ classifications when
compared to the class of the antigen
Memory cell hyper-mutation and replacement is
based primarily on classification and secondarily
on affinity
AIRS Algorithm
Data normalization and initialization
Memory cell identification and ARB
generation
Competition for resources in the
development of a candidate memory cell
Potential introduction of the candidate
memory cell into the set of established
memory cells
AIRS: Performance Evaluation
Fisher’s Iris Data Set
Pima Indians Diabetes
Data Set
Ionosphere Data Set
Sonar Data Set
Classification Accuracy
Important to maintain accuracy
AIRS1: Accuracy
AIRS2: Accuracy
Iris
96.7
96.0
Ionosphere
94.9
95.6
Diabetes
74.1
74.2
Sonar
84.0
84.9
Features
No need to know best architecture to get
good results
Default settings within a few percent of the
best it can get
User-adjustable parameters optimize
performance for a given problem set
Generalization and data reduction
aiNET: Artificial Immune
Network for Data Mining
Problem description
More benchmark problem in this case
Assume a set of unlabelled vectors
We can ask the questions:
Is there a large amount of redundancy?
Are there any groups or subgroups intrinsic to
the data?
What is the structural or spatial distribution?
aiNET: Immune principles
employed
B-cells (antibodies)
Antigens
Antibody/antigen binding
Clonal selection process
Immune network theory
Combined with statistical analysis tools
Data mining: Immune Network
Algorithm
1. Initialization: create an initial random population of network antibodies;
2. Antigenic presentation: for each antigenic pattern, do:
2.1 Clonal selection and expansion:
2.2 Affinity maturation:
2.3 Clonal interactions:
2.4 Clonal suppression:
2.5 Metadynamics:
2.6 Network construction:
3. Network interactions:
4. Network suppression:
5. Diversity:
6. Cycle: repeat Steps 2 to 4 until a pre-specified number of iterations is reached.
Data mining: Mapping from IS to
aiNET
Immune System
aiNET
B-cell (antibody)
Internal data vector
Antigen
Training data vector
Binding
Calculation of Euclidean distance
Cell cloning
Duplication of internal data vectors
Somatic hypermutation
Affinity proportional mutation
Immune network
Network of internal data vectors
Metadynamics
Removal and creation of internal data
vectors
Data mining: Clustering (aiNet)
Limited visualisation
Interpret via MST or
dendrogram
Compression rate of
81%
Successfully identifies
the clusters
Training Pattern
Training Patterns
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
11
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
5 55
1
1
1
1
1
1
2
1
1
2
1
1
1
2
1
1
1
1
1
1
2
1
2
2
2
2
5
1
1
5
2
5
5
1
2
2
1
1
5
5
2
2
5
5
1
1
1
2
2
5
5
2
5
5
5
5
5
2
2
1
1
5
5
5
5
5
2
2
2
2
2
2
5
5
5
5
2
2
1
1
5
5
5
5
5
1
2
2
2
2
2
1
1
1
1
5
5
5
5
5
5
1
1
1
2
2
66
5
5
1
2
2
2
6
6
5
5
5
5
2
2
2
2
2
1
66
6
6 55
5
5
5
2
2
2
1
1
5
5
1
2
2
2
22
2
5
1
1
1
2
2
2
5
2
5
5
5
2
2
2
2
1
5
5
1
1
1
2
2
5
5
5
5
5
5
1
2
2
2
5
5
5
1
1
2
2
2
1
1
5
5
2
2
2
1
5
1
2
2
2
2
2
5
5
5
2
1
1
1
1
5
5
1
5
5
1
5
5
1
5
5
1
2 2
1
1
1
1
1
5
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0.8
0.6
0.4
0.2
0
4 4
4444 44
444
4
4
4
4
4
4
4
4
4
4
4
44
4
4
4
4
4
4
4
4
4
4
4
4
4
44
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
44
4
4
4
4
4
4
4
4
4
444
4
443
3
3
3 3
33
3
3
3
3 3
3
3
3
33
33
3
3
3
3
33
3
3
3
3
3
33
3
3
3
3
3
3
3
3
3
3
33
3
3
3
3
3
3
3
3
3
3
3
3
3
33
3
3
3
33
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
33
3
33
3
3 3
3
3
3
3
3
33
0
0.2
8
8
8
8
88
8
8
7
8
8
7
7
8
8
7
7
8
7
8
8
7
7
88
8
7
8
8
7
8
777
8
8
7
7
88
8
77
8
7
8
8
7
7
7
88
8
7
8
7
7
7
8
8
7
7
7
88
7
7
8
8
7
8
88
7
8
777
8
8
7
8
8
8
77
7
8
8
8
8
8
77
8
7
8
77
7
7
7
8
7
7
0.4
0.6
0.8
1
Result immune network
Data mining:Hierarchical
Clustering (aiNET)
0
1-1
1-2
2-1
1-3
2-2
1-4
2-3
1-5
2-4
Other Interesting Applications
Immune Network for continuous learning (Neal
2002)
Track moving data over time
Maintains clusters in absence of patterns
Useful for dynamic environments
Continuous Classification
Email classification of interesting/non-interesting
emails
Changing profile of the user
Maintain classification accuracy
Comparable to Naïve Bayes
New Trends
Danger Theory
Not self/non-self but Danger/Non-Danger
Immune response is initiated in the tissues.
Danger Zone.
This makes it context dependant
Could this be useful for Web Mining?
Summary
Covered much, but there is much work not covered
(so apologies to anyone for missing theirs)
Immune metaphors
Antibodies and their interactions
Immune learning and memory
Self/non-self
• Negative selection
Application of immune metaphors
The Future
Rapidly emerging field
Much work is very diverse
Framework helps a little
More formal approach required?
Wide possible application domains
What is it that makes the immune system unique?
More work with immunologists
Theories such as Danger theory, Self-Assertion may
have something to say to AIS
The Future (2)
ARTIST: A Network for Artificial Immune
Systems (EPSRC funded network)
Work towards:
A theoretical foundation for AIS as a new CI
Extraction of accurate metaphors
Immune System Modelling
Application of AIS
Train PhD students
Fund workshops/meetings
Coordinate and Disseminate UK based AIS
research (links to Europe)
The Future (hopefully)
IT IS: Information Technology Inspired by the
Immune System
FP 6 IP:
16 institutions across Europe
Create a European Library of immune algorithms
Theoretical analysis of AIS
Application of AIS
• Autonomous boat
• Immunoinformatics
• Web Mining
Modelling of Immune System
AIS Resources: Books
Artificial Immune Systems and Their
Applications by Dipankar Dasgupta (Editor)
Springer Verlag, January 1999.
Artificial Immune Systems: A New
Computational Intelligence Approach
by Leandro N. de Castro, Jonathan Timmis,
Springer Verlag, November 2002.
Immunocomputing: Principles and
Applications by Alexander O. Tarakanov,
Victor A. Skormin, Svetlana P. Sokolova,
Springer Verlag, April 2003.
AIS Related Events in 2003:
Special Session on Artificial Immune Systems at the Congress on
Evolutionary Computation (CEC), December 8-12, 2003, Canberra,
Australia.
Special Session on Immunity-Based Systems at Seventh
International Conference on Knowledge-Based Intelligent
Information & Engineering Systems (KES), September 3-5, 2003,
University of Oxford, UK.
Second International Conference on Artificial Immune Systems
(ICARIS), September 1-3, 2003, Napier University, Edinburgh, UK.
Tutorial on Artificial Immune Systems at 1st Multidisciplinary
International Conference on Scheduling: Theory and Applications
(MISTA), 12 August 2003, The University of Nottingham, UK.
Tutorial on Immunological Computation at International Joint
Conference on Artificial Intelligence (IJCAI), August 10, 2003,
Acapulco, Mexico.
Special Track on Artificial Immune Systems at Genetic and
Evolutionary Computation Conference (GECCO), Chicago, USA,
July 12-16, 2003