Transcript Aritficial Immune Systems-

Artificial Immune Systems
Andrew Watkins
Why the Immune System?
• Recognition
– Anomaly detection
– Noise tolerance
•
•
•
•
•
•
•
•
Robustness
Feature extraction
Diversity
Reinforcement learning
Memory
Distributed
Multi-layered
Adaptive
Definition
AIS are adaptive systems inspired by
theoretical immunology and observed
immune functions, principles and models,
which are applied to complex problem
domains
(de Castro and Timmis)
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
How does it work?
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 different antibodies can recognize a single antigen
Immune Responses
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
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)
Immune Network Theory
• Idiotypic network (Jerne, 1974)
• B cells co-stimulate each other
– Treat each other a bit like antigens
• Creates an immunological memory
Paratope
Suppression
Negative response
Ag
1
2
Idiotope
3
Antibody
Activation
Positive response
Shape Space Formalism
• Repertoire of the
immune system is
complete (Perelson, 1989)
• Extensive regions of
complementarity
• Some threshold of
recognition
Ve
e
V

Ve


e


Ve
e


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
General Framework for AIS
Solution
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
•Complement threshold
Define their Interaction
• Define the term Affinity
• Affinity is related to distance
– Euclidian
D
L
2
(
Ab

Ag
)
 i
i
i 1
• Other distance measures such as Hamming,
Manhattan etc. etc.
• Affinity Threshold
Basic Immune Models and
Algorithms
•
•
•
•
•
Bone Marrow Models
Negative Selection Algorithms
Clonal Selection Algorithm
Somatic Hypermutation
Immune Network Models
Bone Marrow Models
• Gene libraries are used to create antibodies from
the bone marrow
• Use this idea to generate attribute strings that
represent receptors
• Antibody production through a random
concatenation from gene libraries
An individual genome corresponds to four libraries:
Library 1
A1 A2 A3 A4 A5 A6 A7 A8
A3
Library 2
Library 3
B1 B2 B3 B4 B5 B6 B7 B8
Library 4
C1 C2 C3 C4 C5 C6 C7 C8
B2
D1 D2 D3 D4 D5 D6 D7 D8
C8
A3
B2
C8
D5
A3 B2 C8 D5
Expressed Ab molecule
= four 16 bit segments
= a 64 bit chain
D5
Negative Selection 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
Detector Set
(R)
Self
strings (S)
Generate
random strings
(R0)
Match
No
Yes
Reject
Detector
Set (R)
Protected
Strings (S)
Match
Yes
Non-self
Detected
No
Clonal Selection Algorithm (de
Castro & von Zuben, 2001)
Randomly initialise a population (P)
For each pattern in Ag
Determine affinity to each Ab in P
Select n highest affinity from P
Clone and mutate prop. to affinity with Ag
Add new mutants to P
endFor
Select highest affinity Ab in P to form part of M
Replace n number of random new ones
Until stopping criteria
Immune Network Models
(Timmis & Neal, 2001)
Initialise the immune network (P)
For each pattern in Ag
Determine affinity to each Ab in P
Calculate network interaction
Allocate resources to the strongest members of P
Remove weakest Ab in P
EndFor
If termination condition met
exit
else
Clone and mutate each Ab in P (based on a given probability)
Integrate new mutants into P based on affinity
Repeat
Somatic Hypermutation
• Mutation rate in proportion to affinity
• Very controlled mutation in the natural immune
system
• The greater the antibody affinity the smaller its
mutation rate
• Classic trade-off between exploration and
exploitation
How do AIS Compare?
• Basic Components:
– AIS  B-cell in shape space (e.g. attribute
strings)
• Stimulation level
– ANN  Neuron
• Activation function
– GA  chromosome
• fitness
Comparing
• Structure (Architecture)
– AIS and GA fixed or variable sized
populations, not connected in population based
AIS
– ANN and AIS
• Do have network based AIS
• ANN typically fixed structure (not always)
• Learning takes place in weights in ANN
Comparing
• Memory
– AIS  in B-cells
• Network models in connections
– ANN  In weights of connections
– GA  individual chromosome
Comparing
•
•
•
•
•
•
Adaptation
Dynamics
Metadynamics
Interactions
Generalisation capabilities
Etc. many more.
Where are they used?
•
•
•
•
•
•
Dependable systems
Scheduling
Robotics
Security
Anomaly detection
Learning systems
Artificial Immune Recognition
System (AIRS):
An Immune-Inspired Supervised
Learning Algorithm
AIRS: Immune Principles
Employed
• Clonal Selection
• Based initially on immune networks, though
found this did not work
• Somatic hypermutation
– Eventually
• Recognition regions within shape space
• Antibody/antigen binding
AIRS: Mapping from IS to AIS
• Antibody
• Recognition
Ball (RB)
• Antigens
• Immune Memory
Feature Vector
Combination of feature
vector and vector class
Training Data
Memory cells—set of
mutated Artificial RBs
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
Memory Cell Identification
A
Memory Cell Pool
ARB Pool
MCmatch Found
A
1
Memory Cell Pool
MCmatch
ARB Pool
ARB Generation
A
1
Memory Cell Pool
MCmatch
Mutated Offspring
2
ARB Pool
Exposure of ARBs to Antigen
1
A
Memory Cell Pool
MCmatch
3
Mutated Offspring
2
ARB Pool
Development of a Candidate
Memory Cell
1
A
Memory Cell Pool
MCmatch
3
Mutated Offspring
2
ARB Pool
Comparison of MCcandidate and
MCmatch
1
A
Memory Cell Pool
MCmatch
3
Mutated Offspring
4
2
A
MC candidate
ARB Pool
Memory Cell Introduction
1
A
Memory Cell Pool
MCmatch
3
Mutated Offspring
2
4
5
A
MCcandidate
ARB Pool
Memory Cells and Antigens
Memory Cells and Antigens
AIRS: Performance Evaluation
Fisher’s Iris Data Set
Pima Indians Diabetes
Data Set
Ionosphere Data Set
Sonar Data Set
Iris
1
Grobian
(rough)
2
SSV
3
Ionosphere
100%
Diabetes
Sonar
3-NN +
simplex
98.7%
Logdisc
77.7%
TAP MFT
Bayesian
92.3%
98.0%
3-NN
96.7%
IncNet
77.6%
Naïve MFT Bayesian
90.4%
C-MLP2LN
98.0%
IB3
96.7%
DIPOL92
77.6%
SVM
90.4%
4
PVM 2 rules
98.0%
MLP + BP
96.0%
Linear Discr. Anal.
77.5%77.2%
Best 2-layer MLP
+ BP, 12 hidden
90.4%
5
PVM 1 rule
97.3%
AIRS
94.9
SMART
76.8%
MLP+BP, 12 hidden
84.7%
6
AIRS
96.7
C4.5
94.9%
GTO DT (5xCV)
76.8%
MLP+BP, 24 hidden
84.5%
7
FuNe-I
96.7%
RIAC
94.6%
ASI
76.6%
1-NN, Manhatten
84.2%
8
NEFCLASS
96.7%
SVM
93.2%
Fischer discr. anal
76.5%
AIRS
84.0
9
CART
96.0%
Non-linear
perceptron
92.0%
MLP+BP
76.4%
MLP+BP, 6
hidden
83.5%
10
FUNN
95.7%
FSM +
rotation
92.8%
LVQ
75.8%
FSM methodology?
83.6%
11
1-NN
92.1%
LFC
75.8%
1-NN Euclidean
82.2%
12
DB-CART
91.3%
RBF
75.7%
DB-CART, 10xCV
81.8%
13
Linear
perceptron
90.7%
NB
75.573.8%
CART, 10xCV
67.9%
14
OC1 DT
89.5%
kNN, k=22, Manh
75.5%
15
CART
88.9%
MML
75.5%
…
...
22
AIRS
74.1
23
C4.5
73.0%
11 others reported with lower
scores, including Bayes,
Kohonen, kNN, ID3 …
AIRS: Observations
• ARB Pool formulation was over
complicated
– Crude visualization
– Memory only needs to be maintained in the
Memory Cell Pool
• Mutation Routine
– Difference in Quality
– Some redundancy
AIRS: Revisions
• Memory Cell Evolution
– Only Memory Cell Pool has different classes
– ARB Pool only concerned with evolving
memory cells
• Somatic Hypermutation
– Cell’s stimulation value indicates range of
mutation possibilities
– No longer need to mutate class
Comparisons: 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
• Why bother?
Comparisons: Data Reduction
• Increase data reduction—increased
efficiency
Training Set Size
AIRS1: Memory Cells
AIRS2: Memory Cells
Iris
120
42.1 / 65%
30.9 / 74%
Ionosphere
200
140.7 / 30%
96.3 /
Diabetes
691
470.4 /
32%
273.4 /
Sonar
192
144.6 /
25%
177.7 / 7%
52%
60%
Features of AIRS
• 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
More Information
• http://www.cs.ukc.ac.uk/people/rpg/abw5
• http://www.cs.ukc.ac.uk/people/staff/jt6
• http://www.cs.ukc.ac.uk/aisbook