Information Technology Reference
In-Depth Information
selection, i.e. the negative selection algorithm which operates on Hamming shape-
space and employs the
r
-chunk matching rule and permutation masks.
3.1
Holes as Generalization Regions
The
r
-contiguous and
r
-chunk matching rule induce undetectable elements —
termed holes (see Fig. 2). In general, all matching rules which match over a
certain element length induce holes. This statement is theoretically investigated
in [15,14] and empirically explored
3
in [16]. Holes are some
4
elements from
U
\
S
seen
, i.e. elements not seen during the training phase. For these elements, no
detectors can be generated and therefore they cannot be recognized and classified
as non-self elements. However, the term holes is not an accurate expression, as
holes are
necessary
to generalize beyond the training set. A detector set which
generalizes well ensures that seen and unseen self elements are
not
recognized
by any detector, whereas all other elements are recognized by detectors and
classified as non-self. Hence, holes must represent unseen self elements; or in
other words, holes must represent
generalization regions
in the shape-space
U
l
.
r −
1
001
=
{
0001
,
1001
}
=
{s
1
,h
1
}
0001
000
1000
100
000
=
{
1000
,
0000
}
=
{s
2
,h
2
}
Fig. 2.
Self elements
s
1
= 0001 and
s
2
= 1000 induce holes
h
1
,h
2
, i.e. elements which
are not detectable with
r
-contiguous and
r
-chunk matching rules for
r
=3
4
Permutation Masks
Permutation masks were proposed by Hofmeyr [3,9] for reducing the number of
holes. A permutation mask is a bijective mapping
π
that specifies a reordering
for all elements
a
i
U
l
∈
, i.e.
a
1
→
π
(
a
1
)
,a
2
→
π
(
a
2
)
,...,a
|Σ|
l
→
π
(
a
|Σ|
l
).
More formally, a permutation
π
n
matrix, where the first row are elements
a
1
,a
2
,...,a
n
and the second row the
new arrangement
π
(
a
1
)
,π
(
a
2
)
,...,π
(
a
n
), i.e.
∈
S
n
,where
n
∈
N
, can be written as a 2
×
a
1
a
2
...
a
n
π
(
a
1
)
π
(
a
2
)
... π
(
a
n
)
For the sake of simplicity we will use the equivalent
cycle notation
[17] to specify
a permutation. A permutation in cycle notation can be written as (
b
1
b
2
... b
n
)
and means “
b
1
becomes
b
2
, ..., b
n−
1
becomes
b
n
,
b
n
becomes
b
1
. In addition, this
notation allows the identity and non-cyclic mappings, for instance (
b
1
)(
b
2
b
3
)(
b
4
)
means :
b
1
→
b
4
.
3
Hamming,
r
-contiguous,
r
-chunk and Rogers & Tanimoto matching rule.
4
The number of holes is controlled by the matching threshold
r
.
b
1
,
b
2
→
b
3
,b
3
→
b
2
and
b
4
→