Information Technology Reference
In-Depth Information
4.1
Permutation Masks for Inducing Other Holes
As explained above, a permutation mask is a bijective mapping and therefore can
increase
or
reduce
the number of holes — there also exists permutation masks
which results in self elements which neither increase nor reduce the number of
holes. The simplest examples is the identity permutation mask.
For reducing the number of holes,
π
must be chosen at an appropriate value,
and a certain number of detectors must be generable.
Reconsider the self elements
s
1
= 0001
,s
2
= 1000 in figure (2). One can see
that elements
h
1
= 1001 and
h
2
= 0000 are not detectable by the
r
-contiguous
and
r
-chunk matching rule. However, after applying the permutation mask
π
0
=
(1243), i.e.
π
0
(
s
1
) = 0010
,
0
(
s
2
) = 0100
one can verify (see Fig. 3) that holes
h
1
,h
2
are eliminated.
r −
1
π
0
(0001)
=
{
0010
}
=
{π
0
(
s
1
)
}
001
010
π
0
(1000)
=
{
0100
}
=
{π
0
(
s
2
)
}
010
100
Fig. 3.
The permutated self elements
π
0
(
s
1
)and
π
0
(
s
2
) induce no holes by
r
-contiguous
and
r
-chunk matching rule
However, it is also clear that (1243)(2431)
,
(4312) and (3124) represent
the same permutation, namely the cycle permutation of
π
0
= (1243). Specif-
ically, all cycle permutations of an arbitrary selected
π
leads, in terms of the
r
-chunk and
r
-contiguous matching, to the same holes.
On the other hand, there do exist permutation masks which do not reduce
holes, i.e.
π
(
s
i
)=
s
j
,for
i
=
j
and self elements
s
1
,s
2
,...,s
|S|
. An example is
the permutation
π
1
= (14)(2)(3), as
π
1
(
s
1
)=
s
2
and
π
1
(
s
2
)=
s
1
.
Furthermore, as mentioned above, a permutation mask can also increase the
number of holes. In our subsequent presented experiments this is illustrated for
instance in figures
5
5(c) and 5(d).
5
Permutation Masks Experiments in Hamming Negative
Selection
In [18,8] results were presented which demonstrated the coherence between the
matching threshold
r
and generalization regions when the
r
-chunk matching rule
in Hamming negative selection is applied. Recall, as holes are not detectable by
any detector, holes must represent unseen self elements, or in other words holes
must represent generalization regions. In the following experiment we will investi-
gate how randomly determined permutation masks will influence the occurrence
5
With and without permutation mask.
