Transcript Introduction to AIS

Introduction to AIS
Emma Hart
Napier University, Scotland
ICARIS 2005
Content
• What is immunology anyway
– And why do we care ?
• Immunology for computer scientists
– Some relevant biological details
• From in-vivo IS to in-silico IS
– Making the step scientifically
• A decade of AIS research
– a snapshot of existing AIS algorithms
• The future of AIS
– What should we be doing next ?
What is the Immune System ?
a complex system of cellular and molecular components
having the primary function of distinguishing self from
not self and defense against foreign organisms or
substances (Dorland's Illustrated Medical Dictionary)
The immune system is a cognitive system whose
primary role is to provide body maintenance
(Cohen)
Immune system was evolutionary selected as a
consequence of its first and primordial function to
provide an ideal inter-cellular communication
pathway (Stewart)
What is the Immune System ?
Classical
Cohen
Matzinger
Varela
• The are many
different viewpoints
• These views are
not mutually
exclusive
• Lots of common
ingredients
From a computational perspective:
Computational Properties
•
•
•
•
•
•
•
•
•
Unique to individuals
Distributed
Imperfect Detection
Anomaly Detection
Learning/Adaption
Memory
Feature Extraction
Diverse
..and more
Systems that are:
•
•
•
•
Robust
Scalable
Flexible
Exhibit graceful
degradation
• Homeostatic
A High Level Overview
The Innate Immune System
• The part of the
immune system with
which we are born
• Doesn’t change or
adapt
• Complement system
• Macrophages
• Cytokines, natural
killer cells
http://www.aids-info.ch/e_te/aas-e-imm.htm
The Adaptive Immune System
http://altmed.creighton.edu/pelvic2/blyphocy
tes.htm
www.hwscience.com/ Bio/HAP/Lymphocyte.jpg
• Adapts to recognise
specific pathogens
• Retains a memory which
speeds up future
responses
• Consists primarily of
lymphocytes which
circulate around the body
• Distributed detection
system without any
central control
Adaptive Immunity
epitope
receptor
lymphocyte
• A detection event occurs
when the receptor of a
lymphocyte binds to an
epitope on a pathogen
• Strength of the bond is
termed the affinity
Low affinity
structurally similar – high affinity
• Each lymphocyte can
have multiple, identical
receptors
Generating Receptor Diversity
Adaptation – Affinity Maturation
1. activation
2. proliferation
High affinity
selected
3. differentiation
antibody
plasma cell
memory cell
cell death
Low affinity
no selection
Affinity Maturation – A Darwinian
process of variation and selection
Initial B-cell
population
Clonal selection
and
hypermutation
Adapted B-Cell
population
The Flaw in the Argument So Far…
• Receptors generated at
random or via somatic
hypermutation might bind
to self proteins
– This would lead to
autoimmunity
• Tolerance is provided by
a set of lymphocytes
called T-helper cells
Immature
T-cells in
thymus
Ubiquitous
self-proteins
Self-tolerant
T-cell death
Matzinger’s View
• Self/Non-self discrimination is not sufficient!
– There is no immune reaction to foreign bacteria in the
gut
– No reaction to food!
– Definition requires self to be confined to the subset
actually seen by lymphocytes during maturation
– Self changes throughout a body’s lifetime
– Medically:
• We can perform transplants (no attack against non-self)
• Certain tumours are fought by the immune system (attack
against self!)
Matzinger’s View: Danger Theory
• The immune system responds to danger,
rather than non-self
• It still fundamentally supports the need for
discrimination,but now
– There is no need to attack everything foreign
– Just attack those things that are dangerous
• Danger is measured by damage to cells
that send out a distress signal when the
cells die an un-natural death
Jerne’s View: The Idiotypic Network
• The cells in the immune
system can recognise
each other as well as
pathogens!
• An antibody has a
paratope and an idiotope
• Paratope-idiotope
interactions leads to
networks of
interconnected antibodies
Jerne’s View
• There is no essential
difference between the
“recognized” and the
“recognizer,”
• Any given antibody might
serve either, or both, functions.
• Immune regulation is based on
the reactivity of antibody with
its own repertoire forming a set
of self-reactive, self-reflective,
self-defining immune activities
Varela’s View
• “From the immune system's perspective,
it only “knows” itself “(Varela et al 1988).
• Sustaining autonomous activity of the
network gradually defines the system
• Impacts (without pre-labelling) either
– Smoothly integrate the system
– Are rejected from the system
• This is known as self-assertion
self
non-self
Stewart’s View
• The network provides a cellular
communication pathway which allows
the system to preserve a perfect integrity
and maintain homeostasis
• Defensive role of the immune system is
secondary
• Immune system was evolutionary selected
as a consequence of its primordial function
to provide this pathway
Cohen’s View
• IS is a cognitive
system
• It’s role is body
maintenance
• Significant departure
from self/non-self
view
Cohen’s View
• IS is a cognitive
system
• It’s role is body
maintenance
• Significant departure
from self/non-self
view
• Forms an internal
history
• Self-organises
• Learns
• Memory
• Makes deterministic
decisions
Cohen’s View
• IS is a cognitive
system
• It’s role is body
maintenance
• Significant departure
from self/non-self
view
• Detect current state of
body’s tissues
• Elicit an appropriate
response
– Co-respondence and
patterns of activity
• Response is result of
collaboration of innate
and adaptive
components
Cohen’s View
• IS is a cognitive
system
• It’s role is body
maintenance
• Significant
departure from
self/non-self view
• Defence against
pathogen is just a
special case of
maintenance
• Autoimmunity is
required!
– Body needs to
recognise state of its
own tissues
– Antigen receptors
exists to achieve this
What is the Immune System ?
- A lot of things!
Classical
Cohen
Matzinger
Varela
AIS
• There are many
different viewpoints
• They are not
mutually exclusive!
•AIS can pick and
choose!
In-vivo IS to In-silico IS
• How do we make the jump ?
• Historically, AIS was rooted in
real immunology
• Now, there is a tendency to
observe-implement
• (but lots of simple and
effective algorithms
developed)
An Interdisciplinary Approach
Mathematics
Biology
Computer Science
Engineering
Analysable, validated systems that fully
exploit the underlying biology
A Conceptual Framework
Danger Signals
modelling
Probes,
Observations,
experiments
Biological
system
Simplifying
abstract
representation
Analytical
framework/
principle
Bio-inspired
algorithms
A Conceptual Framework
modelling
Probes,
Observations,
experiments
Biological
system
Simplifying
abstract
representation
Analytical
framework/
principle
Mathematical
models
Bio-inspired
algorithms
A Conceptual Framework
modelling
Probes,
Observations,
experiments
Biological
system
Simplifying
abstract
representation
Analytical
framework/
principle
Construct a
computational model
Bio-inspired
algorithms
A Conceptual Framework
modelling
Probes,
Observations,
experiments
Biological
system
Simplifying
abstract
representation
Abstract into
algorithms
suitable for an
application
Analytical
framework/
principle
Bio-inspired
algorithms
A Higher-Level Framework
Cross-domain modelling
Meta-probes
Metarepresentation
Meta-framework
Novel-unified
Algorithms
A Meta Framework
• Asking meta-questions of the
computational framework will give
attention to interesting properties:
– Openness
– Diversity
– Interaction
– Structure
– Scale
A Meta Framework
• Asking meta-questions of the
computational framework will give
attention to interesting properties:
– Openness
– Diversity
– Interaction
– Structure
– Scale
How much
continual growth
or development is
required in the
system ?
A Meta Framework
• Asking meta-questions of the
computational framework will give
attention to interesting properties:
– Openness
– Diversity
– Interaction
– Structure
– Scale
How much is
necessary, what
does it cost , does
it combat fragility ?
A Meta Framework
• Asking meta-questions of the
computational framework will give
attention to interesting properties:
– Openness
– Diversity
– Interaction
– Structure
– Scale
What are the levels
of interaction
between agents ?
A Meta Framework
• Asking meta-questions of the
computational framework will give
attention to interesting properties:
– Openness
– Diversity
– Interaction
– Structure
– Scale
Are different levels
required between
agents ?
A Meta Framework
• Asking meta-questions of the
computational framework will give
attention to interesting properties:
– Openness
– Diversity
– Interaction
– Structure
– Scale
How many agents
are required ?
When does “more”
become “different”
?
An Engineering Framework for AIS
Solution
Algorithms
AIS
Affinity
Representation
Application
Timmis, De Castro
A Framework for AIS
Solution
Shape-Space
Algorithms
AIS
Affinity
Binary
Integer
Real-valued
Representation
Application
Symbolic
A Framework for AIS
Solution
Algorithms
AIS
Euclidean
Affinity
Manhattan
Hamming
Representation
Application
A Framework for AIS
Solution
Algorithms
Bone Marrow
Models
Clonal Selection
AIS
Affinity
Negative Selection
Positive Selection
Representation
Application
Immune Network
Models
The Representation Layer
• Real antibodies and antigens consist of
molecules which interact via forces such as Van
der Waals, electrostatic, hydrogen bonding etc.
• How can we represent this computationally ?
The Representation Layer
The Representation Layer
• Any molecule can be described a generalised shape
(Perelson)
– defines its chemical groups,shape and charge distributions
• The generalised shape can be described as L
parameters
– Height,length,width of bumps on combining sites
• An attribute string m=<m1,m2,..mL> consisting of L
attributes can be regarded as a point in LL
dimensional shape-space, m  S
The Representation Layer
Shape-Space
• For an animal possessing N antibodies
– The shape-space S contains N points
– The N points lie in a finite volume V
– (there is only a restricted range of widths,
lengths etc. that a site can assume)
– Antigens are also characterized by
generalised shapes whose complement lies in
V
The Representation Layer
Shape-Space
• An antibody can
recognise any antigen
whose complement lies
within a small surrouding
region of width ε (the
cross-reactivity threshold)
• This results in a volume
vε known as the
recognition region of the
antibody
V
vε
ε
ε
S
vε
The Representation Layer
vε
ε
Not all balls are round….
• The shape of the recognition region
doesn’t have to be spherical
• Different shapes will endow a system with
different properties:
The Representation Layer
Shape Space
• The type of attributes in an application
domain will define the type of shape-space
adopted:
– Real-valued shape-space (real-valued
vectors)
– Integer shape-space (integer values)
– Hamming shape-space (attributes taken from
finite alphabet of size k
– Symbolic shape-space (different attribute
strings, e.g “name”, “colour”)
The Representation Layer
Affinity Layer
• Computationally, the degree of interaction of
an antibody-antigen or antibody-antibody can
be evaluated by a distance or affinity measure
• The choice of affinity measure is crucial:
• It alters the shape-space topology
• It will introduce an inductive bias into the algorithm
• It needs to take into account the data-set used and
the problem you are trying to solve
The Affinity Layer
Hamming Shape-Spaces
Distance measured by:
• The number of
complementary bits
• R-contiguous bits
• R-chunks
• Rogers and Tanimoto
• Multiple contiguous
bits
The Affinity Layer
00111
10110
x d
i
i
i
r
Hamming Shape-Spaces
Distance measured by:
• The number of
complementary bits
• R-contiguous bits
• R-chunks
• Rogers and Tanimoto
• Multiple contiguous
bits
00111
10110
String and detector match if
there is a sequence of size r
where all bits are identical
The Affinity Layer
Introduces positional bias….
Hamming Shape-Spaces
Distance measured by:
• The number of
complementary bits
• R-contiguous bits
• R-chunks
• Rogers and Tanimoto
• Multiple contiguous
bits
String
00111
Detector
10111
R-Chunk detector 1
101
R-Chunk detector 2
R-Chunk detector 3
011
111
Detector matches string if all the bits
of d[i] are equal to the r symbols of
the string in the window specified by
the detector i
The Affinity Layer
Hamming Shape-Spaces
Distance measured by:
• The number of
complementary bits
• R-contiguous bits
• R-chunks
• Rogers and Tanimoto
• Multiple contiguous
bits
String
00111
Detector
10111
R-Chunk detector 1
101
R-Chunk detector 2
R-Chunk detector 3
011
111
Detector matches string if all the bits
of d[i] are equal to the r symbols of
the string in the window specified by
the detector i
The Affinity Layer
Hamming Shape-Spaces
Distance measured by:
• The number of
complementary bits
• R-contiguous bits
• R-chunks
• Rogers and Tanimoto
• Multiple contiguous
bits
String
00111
Detector
10111
R-Chunk detector 1
101
R-Chunk detector 2
R-Chunk detector 3
011
111
Detector matches string if all the bits
of d[i] are equal to the r symbols of
the string in the window specified by
the detector i
The Affinity Layer
Hamming Shape-Spaces
• The number of
complementary bits
• R-contiguous bits
• R-chunks
• Rogers and
Tanimoto
• Multiple contiguous
bits
x d
 x  d  2 x  d
i
i
 r
i
i
i
i
i
i
More selective than
Hamming
The Affinity Layer
i
Hamming Shape-Spaces
Distance measured by:
• The number of
complementary bits
• R-contiguous bits
• R-chunks
• Rogers and Tanimoto
• Multiple contiguous
bits
D  DH   2
li
i
Where DH = Hamming Distance
Li is the length of each
complementary region with 2 or
more consecutive bits
00110011
11101100
11011110
The Affinity Layer
6+22+24=26
Real Valued Shape-Spaces
• Euclidean Distance
D
L
2
(
Ab

Ag
)
 i i
i 1
• Manhattan Distance
L
D   Abi  Agi
i 1
…..beware of the bias introduced….
The Affinity Layer
The Algorithms Layer
• Bone Marrow models (Hightower, Oprea, Kim)
• Clonal Selection
– Clonalg(De Castro), B-Cell (Kelsey)
• Negative Selection
– Forrest, Dasgputa,Kim,….
• Network Models
– Continuous models:Jerne,Farmer
– Discrete models: RAIN (Timmis), AiNET (De Castro)
The Algorithms Layer
Bone Marrow Models
• Use gene libraries to store elements that can be
combined to form antibodies
• Elements in library can be evolved using a genetic
algorithm
• c libraries of length l
cl possible antibodies
A1 A2 A3 A4 A5
B1 B2 B3 B4 B5
A2 B5 C1
The Algorithms Layer
C1 C2 C3 C4 C5
Clonal Selection
– the Clonalg Algorithm
1. Initialisation
2. Antigenic presentation
a.
b.
c.
d.
Affinity evaluation
Clonal selection and expansion
Affinity maturation
Metadynamics
3. Cycle
The Algorithms Layer
Clonalg
• Create a random
population of
individuals (P)
1. Initialisation
2. Antigenic
presentation
a. Affinity evaluation
b. Clonal selection and
expansion
c. Affinity maturation
d. Metadynamics
3. Cycle
The Algorithms Layer
Clonalg
• For each antigenic
pattern in the data-set
S do:
1. Initialisation
2. Antigenic
presentation
a. Affinity evaluation
b. Clonal selection and
expansion
c. Affinity maturation
d. Metadynamics
3. Cycle
The Algorithms Layer
Clonal Selection
1. Initialisation
2. Antigenic
presentation
a. Affinity evaluation
b. Clonal selection and
expansion
c. Affinity maturation
d. Metadynamics
• Present it to the
population P and
determine its affinity
with each element of
the population
3. Cycle
The Algorithms Layer
Clonal Selection
1. Initialisation
2. Antigenic
presentation
a. Affinity evaluation
b. Clonal selection
and expansion
c. Affinity maturation
d. Metadynamics
• Select n highest
affinity elements of P
• Generate clones
proportional to their
affinity with the
antigen
(higher affinity=more
clones)
3. Cycle
The Algorithms Layer
Clonal Selection
1. Initialisation
2. Antigenic
presentation
a. Affinity evaluation
b. Clonal selection and
expansion
c. Affinity maturation
d. Metadynamics
• Mutate each clone
• High affinity=low mutation
rate and vice-versa
• Add mutated individuals
to population P
• Reselect best individual
to be kept as memory m
of the antigen presented
3. Cycle
The Algorithms Layer
Clonal Selection
1. Initialisation
2. Antigenic
presentation
a. Affinity evaluation
b. Clonal selection and
expansion
c. Affinity maturation
d. Metadynamics
3. Cycle
• Replace a number r
of individuals with low
affinity with randomly
generated new ones
The Algorithms Layer
Clonal Selection
1. Initialisation
2. Antigenic
presentation
a. Affinity evaluation
b. Clonal selection and
expansion
c. Affinity maturation
d. Metadynamics
3. Cycle
• Repeat step 2 until a
certain stopping
criteria is met
The Algorithms Layer
Clonal Selection
• End result of applying clonal selection is a
set of antibodies which are representative
of the antigenic data set:
– Performs data reduction
– Used for clustering
– Used for classification (e.g new antigens can
be presented, highest affinity antibody is
indicative of class)
Clonalg for Optimisation
1. Initialisation
2. Antigenic
presentation
a. Affinity evaluation
b. Clonal selection and
expansion
c. Affinity maturation
d. Metadynamics
• We can use Clonalg
for optimisation
• Replace the set of
patterns S by a
function to be
optimised f(x)
• Affinity=value of the
function
3. Cycle
The Algorithms Layer
Negative Selection
Self
strings
Random
Antibody
repertoire
Recognise ?
Yes
Reject
No
Available
repertoire
• Generate random set
of antibodies
• Determine affinity of
each antibody with all
elements in self-set
• If affinity is greater
than some threshold ε
eliminate antibody
• Repeat…
The Algorithms Layer
Negative Selection
Self
strings
Efficient
Methods of
Antibody
generation
Recognise ?
Yes
Reject
No
Available
repertoire
• Generate random set
of antibodies
• Determine affinity of
each antibody with all
elements in self-set
• If affinity is greater
than some threshold ε
eliminate antibody
• Repeat…
The Algorithms Layer
Real-Valued Negative Selection
Random
detectors
Dasgupta et al
For each
detector
Evaluate
quality
detector
overlap ?
Mature
detector
Sufficient
Non-self
Coverage?
Move
detector
Covers
Self ?
Clone
Better
detectors
EXIT
The Algorithms Layer
Network Algorithm
• Network algorithms based on the assumption
that the immune system behaves dynamically
even in the absence of external antigen
• Many continuous versions of this algorithm,
mainly due to immunologists
– Farmer
– Jerne
– Varela and Coutinho
• These models served as inspiration for discrete
network models (Timmis, Neal, De Castro)
The Algorithms Layer
Network Algorithms
• The dynamics can account for emergent
properties such as learning, memory etc.
• Summarised by Perelson
Rate of
population
variation
=
Network
stimulation
Death of
Network
Influx of new
- suppression + elements - unstimulated
elements
The Algorithms Layer
Network Algorithms
• Accounts for emergent properties such as
learning, memory etc.
• Summarised by Perelson
Rate of
population
variation
=
Network
stimulation
Death of
Network
Influx of new
- suppression + elements - unstimulated
elements
Network dynamics
The Algorithms Layer
Network meta-dynamics
Discrete Network Algorithm
(Timmis,Neal)
1. Initialisation
2. Antigenic Presentation For each antigen, do:
a. Clonal selection, network
interactions
b. Metadynamics
c. Clonal Expansion
d. Somatic hypermutation
e. Network Construction
3. Cycle
The Algorithms Layer
Network Algorithm
1. Initialisation
2. Antigenic Presentation For each antigen, do:
a. Clonal selection, network
interactions
b. Metadynamics
c. Clonal Expansion
d. Somatic hypermutation
e. Network Construction
3. Cycle
The Algorithms Layer
Create a network from a
random subset of the
antigens
Network Algorithm
1. Initialisation
2. Antigenic Presentation For each antigen, do:
a. Clonal selection, network
interactions
b. Metadynamics
c. Clonal expansion
d. Somatic hypermutation
e. Network Construction
3. Cycle
The Algorithms Layer
Determine stimulation of
every cell in the network
Network Algorithm
1. Initialisation
2. Antigenic Presentation For each antigen, do:
a. Clonal selection, network
interactions
b. Metadynamics
c. Clonal Expansion
d. Somatic hypermutation
e. Network Construction
3. Cycle
The Algorithms Layer
Eliminate cells with low
stimulation levels
Network Algorithm
1. Initialisation
2. Antigenic Presentation For each antigen, do:
a. Clonal selection, network
interactions
b. Metadynamics
c. Clonal Expansion
d. Somatic hypermutation
e. Network Construction
3. Cycle
The Algorithms Layer
Reproduce the most
stimulated cells
proportional to stimulation
level
Network Algorithm
1. Initialisation
2. Antigenic Presentation For each antigen, do:
a. Clonal selection, network
interactions
b. Metadynamics
c. Clonal Expansion
d. Somatic hypermutation
e. Network Construction
3. Cycle
The Algorithms Layer
Mutate each cell inversely
proportional to its
stimulation
Network Algorithm
1. Initialisation
2. Antigenic Presentation For each antigen, do:
a. Clonal selection, network
interactions
b. Metadynamics
c. Clonal Expansion
d. Somatic hypermutation
e. Network Construction
3. Cycle
The Algorithms Layer
Incorporate successful
mutated clones into the
network
Network Algorithm
1. Initialisation
2. Antigenic Presentation For each antigen, do:
a. Clonal selection, network
interactions
b. Metadynamics
c. Clonal Expansion
d. Somatic hypermutation
e. Network Construction
3. Cycle
The Algorithms Layer
Network Algorithm
• Stimulation of network cells calculated like
this, where dis() is the Euclidean distance
between two vectors


S  1  dis( p)   1  dis( x)    dis( x)
 x 0
 x 0
n
Excitation based on
distance to current
pattern p
Excitation based on
distance to
neighbouring cells
The Algorithms Layer
n
Suppression
based on
distance to
neighbours
Other Network Algorithms
• Many other versions of network algorithms in
practice:
– AiNET - De Castro (clustering)
– Bersini, Hart (simulations)
– Ishiguro, Hart (robotic applications)
– Neal, Timmis (clustering)
• Same basic principles, but variations in methods
of calculating stimulation, suppression, metadynamics
The Algorithms Layer
Example Application Areas
Computer
Security
Network models
Data-Mining
and
classification
Anomaly
Detection
Robotic
Control
Negative
selection
Optimisation
Clonal
Selection
Bone Marrow
The Future of AIS
•
•
•
•
Lots of interesting immunology
Lots of computational models
Lots of algorithms
Some great successes…
The Future of AIS
•
•
•
•
Lots of interesting immunology
Lots of computational models
Lots of algorithms
Some great successes…
Has it really made
a difference ?
The Future of AIS
• Not as much as it could………
Can
it really
make a difference
?
The Future of AIS
• Not as much as it could………
Can
it really
made a difference
?
YES
Where do we go from here
1. Interdisciplinary and structured approach
– Look back to the fundamental immunology
– Look at the interaction of the immune system with
other biological systems (neural, endocrine, etc.)
– Perform proper theoretical analysis of systems
using mathematics
– Use proper developmental methodologies to
abstract computational models
Where do we go from here ?
2. Careful choice of application areas
• Don’t just choose problem domains tackled
by other biological paradigms
• Think carefully about problem features
• Consider what AIS can bring to a problem
area that other paradigms cannot
• Don’t apply AIS for the sake of it…
Some Useful References
• Previous ICARIS proceedings (2002-2005)
• Artificial Immune Systems: A New Computational
Intelligence Approach (De Castro and Timmis)
• Design Principles for the Immune System and
Other Distributed Autonomous Systems (Segel
and Cohen)
• Tending Adam’s Garden (Cohen)
• Artificial Immune Systems and their Applications
(Dasgupta)