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
 
Search WWH ::




Custom Search