A Recurrent Architecture of Independent
Single Immune Systems

by: Stefan Schadwinkel

Contents

1 Introduction 8

1.1 Background 8
1.2 Fundamental Ideas  8

2 The Core Immune Learning Algorithm 9

2.1 Problem Description 9
2.2 Deciding the Immune Principles to be used for Problem Solving 9
2.3 Engineering the Artificial Immune System 11

2.3.1 Defining the Types of Immune Components to be used  11
2.3.2 Defining the Mathematical Representation for the Elements of the AIS 11
2.3.3 Applying Immune Principles to Problem Solving 13
2.3.4 The Metadynamics of the AIS 15

2.4 Reverse Mapping from AIS to the Real Problem  15
2.5 The Full Learning Algorithm in Pseudocode 15

2.5.1 The aiNet Algorithm 15
2.5.2 The Isis Algorithm  16
2.5.3 Comparison of aiNet and Isis 17

3 The Architecture 18

3.1 The Concept 18
3.2 The Ra Algorithms 19

3.2.1 The Learning Algorithm: raCreate 19
3.2.2 The Classification Algorithm: raCluster 19

4 Implementation 20

4.1 Implemented Classes 20
4.2 Invoking the Algorithms 21

4.2.1 Isis 21
4.2.2 raCreate 23
4.2.3 raCluster 24
4.2.4 raGraph 25

5 Data Preprocessing 25

6 Results 27

6.1 Results with the Identity Shapespace 35

6.1.1 Level 4 Clusters with Identity Shapespace 37
6.1.2 Comments 39

6.2 Results with the Convolution Shapespace  40

6.2.1 Level 2 Clusters with Convolution Shapespace  40
6.2.2 Comments  45

6.3 Results with the Fourier Shapespace 45

6.3.1 Level 1 Clusters with Fourier Shapespace 47
6.3.2 Comments  48

6.4 Comparison of the Algorithm Behaviour Across the Different Shapespaces 49

7 Further Possibilities for the Ra/Isis Approach 50

7.1 Parametertuning 50

7.1.1 Hierarchical Parameters 50

7.2 Shapespaces  50

7.2.1 Hierarchical Shapespaces 51

7.3 Clustering Unusual Data 51
7.4 Data Analysis and Other Learning Algorithms 51
7.5 Classification 51

7.5.1 Hierarchical Classification 52
7.5.2 Classification Networks 52
7.5.3 Subsequent Classification 52

8 Analysis of the Algorithm Behaviour 53
8.1 Ra/Isis vs. Common Aglomerative Clustering 53
8.2 Comparison of Ra/Isis with Self Organizing Maps 53

8.2.1 Results of Applying the Data to a SOM 54

9 Conclusion 64

1 Introduction

This section will explain the background and the fundamental ideas of this work.

1.1 Background

This work is based on a diploma thesis by Changxing Dong [Dong04]. In [Dong04], the e ects of di erent shapespaces on the behaviour of artifi- cial immune system algorithms are evaluated. For that purpose a pattern recognition task was used. In this case, chinese characters should be learned and recognized. Each character was adapted individually using the CLONALG algorithm [dCT02]. The resulting set of antibody patterns, the duration of running the algorithm and the quality of recog- nition were then used to evaluate the differences between the di erent shapespaces.

1.2 Fundamental Ideas

In [Dong04], each character was modelled as a single antigen pattern. Each of these patterns was adapted by the algorithm into one antibody pattern, a pattern that would match the incoming antigen. This approach results in an one on one mapping of the character to its recognizing pattern. Although this is fine, if one is just interested in an analysis of the behaviour of algorithms, it is of little practical use, since the most optimal output of the algorithm is equivalent to the input. In [Dong04], the characters are used in three di erent fonts to do further comparisons. Now, the initial focus of this work, was to create a system, that would adapt all the incoming antigen patterns using the same set of antibody patterns. That idea is based on discrete models of the immune network theory as proposed in [dCT02], especially on the aiNet algorithm [dCT00, dCT02]. The system would get all the chinese characters as input antigens and create a set of antibody patterns that match these input patterns. A specific antibody would then represent a cluster across the input patterns. That cluster contains all the patterns that are matched by the specific antibody. Following that approach, the goal was, to create a set of antibody patterns, that would somehow adapt the structure of the chinese chracters. The used chinese characters were taken from the GB2312-80 font set, that ships with Microsoft Windows XP. By their nature, some characters look very similiar. The algorithm should be able to group similiar patterns together, at best across different fonts.

With that goal in mind, the algorithm has to find an equilibrium between generalizing di erent, but similiar, patterns on the one hand, and discriminating between patterns, that are very distinct, on the other. Since the di erent fonts provide each character in a different way, the grouping must be done using a higher or more abstract level, using conceptual properties rather than pixels alone. The highlighting of conceptual properties shall be provided by the shapespace concept. That provides a transformation of the input data which emphasizes conceptual properties. Each antibody matches antigens in its recognition region, which is determined by the used cross reactivity threshold. More complex recognition regions can be created by grouping the recognition regions of several antibodies together. That grouping can be created using the same clustering algorithm. For that purpose, matching by similiarity instead of matching by complementarity is used. By that, the output antibodies can be seen as higher level antigens that can be grouped together by mapping them to higher level antibodies. Through iteration of that idea, a conceptual hierarchy is created. As the used artificial immune algorithms are heuristic by design, these clusters can’t be guaranteed to be disjunct.

2 The Core Immune Learning Algorithm

To design the algorithm, I followed the Guidelines for the Design of AIS from the book Artificial Immune Systems: A New Computational Intelligence Approach [dCT02]. The algorithm developed in this section, is the core clustering algo- rithm. The usage of this algorithm to create the hierarchy is explained in a later section of this document.

2.1 Problem Description

The task to be solved is, as already outlined, to create a system capable of grouping together similiar input patterns. The base algorithm has only to be able to map one or more input patterns to one recognizing pattern. The input patterns are binary pixel matrices, with a dimension of 16 for both x and y directions. Two main elements can be indentified: the patterns to be mapped and the patterns onto which the input patterns are mapped. The algorithm is called Isis, an abreviation of I independent Single Immune System.

2.2 Deciding the Immune Principles to be used for Problem Solving

Following conceptual immune priciples will be used:

1. Abstract models of Immune Cells, Molecules and their Interactions

• Only two types of cells are used:

(a) antigens, corresponding to the input patterns
(b) antibodies, corresponding to the recognizer patterns

• The matching between the cells is done using an a nity mea- sure. Matching by similiarity is used: the more equal antigen and antibody, the higher the a nity. The distance measure used for calculating the a nity can be varied by the user.
• The input patterns come as 16x16 pixel matrices. These can be interpreted as binary strings with a length of 256. On these matrices a shapespace transformation can be calculated, that weights each pixel with an integer value. Generally, the data on which the algorithm works is an integer matrix. The shapespace transformation can be varied by the user.

2. Algorithms and Processes

These Algorithms and Processes will be used in the full algorithm:

• Clonal Selection
• Clonal Expansion
• A nity Maturation
• Somatic Hypermutation
• Cell Aging
• Simulating an Immune Reaction

Note, that all these are just subprocesses, used as parts of the complete learning algorithm, which is developed.

3. Immune Network Models

[...]