SEN3:
Incremental Learning of Classificators
Jürgen Rahmel,
Aldo v.
Wangenheim
Überblick
Das SEN3 (Self-Editing
Nearest Neighbor Net) kombiniert die inkrementelle Konstruktion einer
Netzwerkstruktur mit der Intention des Editing-Konzepts, wie es schon früh
für die Nearest-Neighbor-Klassifikation verwendet wurde. Verbindendes
Element ist das Ausnutzen einer Nachbarschaftsbeziehung von Neuronen, wie
sie im Kohonen-Netz oder in den GCS (Growing Cell Structures) vorkommt.
Ein wichtiger Punkt bei der Entwicklung der SEN3-Netzwerke war die Notwendigkeit
eines nicht iterativen und damit online einsetzbaren Lernverfahrens, das
auf unveränderten Trainingsbeispielen operiert. Eine Heuristik, die
in SEN3 Anwendung findet, ist die Aussage, daß es bei beabsichtigter
Reduktion der Repräsentanten (Prototypen) besser ist, die Dichte der
Repräsentanten im Zentrum von Clustern zu verringern und die Klassengrenzen
möglichst so gut wie bisher zu beschreiben.
Konstruktion: Sei
die Menge T der N Trainingsbeispiele gegeben, sei Tm
eine m-elementige Teilmenge der Trainingsmenge
T, und sei Tn
= T - Tm. Jedem Neuron r sei eine Menge Nr
ausgewählter Nachbarn zugeordnet. Abbildung 1 zeigt die Konstruktion
des Netzwerks an einem einfachen Beispiel. Sei |T| =10, m=5,
es gibt 2 Klassen und für jedes eingefügt Neuron r werden
dessen zwei nächste Nachbarn in die Menge Nr aufgenommen.
Teilbild a) zeigt bereits alle t in T, obwohl im ersten
Schritt nur die t in Tm betrachtet werden.
Abb.1: Konstruktion
des SEN3-Netzwerkes
Zunächst werden die Nr für die Neuronen
r
in Tm mit den jeweils zwei nächsten Nachbarn initialisiert,
wobei durch die Symmetrie dieser Nachbarschaftsrelation manche Neuronen
mehr als zwei Nachbarn haben können (Teilbild b):
Nachdem die m Neuronen
aus Tm initialisiert sind, werden für die Elemente der
Trainingsmenge die weiteren Neuronen gemäß der Auswahlbedingung
angefügt, d.h. jeweils mit den zwei nächsten, bereits vorhandenen
Nachbarn verknüpft. (Teilbild c) zeigt dies für eine willkürlich
gewählte Reihenfolge der t in Tn.
Editing: Das Durchführen
eines Editing-Schrittes verringert die Zahl der in der Netzstruktur vorhandenen
Neuronen. Dabei werden alle Neuronen gelöscht, die nur mit Neuronen
der gleichen Klasse benachbart sind. Dies hat zur Folge, daß vornehmlich
die Neuronen in der Nähe der Klassengrenzen bestehen bleiben und weiterhin
als Klassifikatoren dienen können. Die Klassifizierungsgüte bleibt
daher weitgehend erhalten, obwohl z.T. eine erhebliche Reduktion der Repräsentanten
stattgefunden hat. Somit wird die Zahl der Berechnungen in der Klassifikationsphase
wesentlich verringert.
Rechnerisch kann gezeigt
werden, daß, wenn m möglichst klein gewählt wird, nur noch
etwas mehr als die Hälfte der Distanzberechnungen durchgeführt
werden müssen, als es für alle N Trainingsbeispiele auf einmal
der Fall ist. Versuche mit verschiedenen Datenmengen zeigten, daß
die Wahl von m unkritisch ist und daher von Effizienzkriterien abhängig
gemacht werden kann. Die Einsparung kann noch größer werden,
wenn während des Einfügens der Neuronen für Tn
ein Editier-Schritt durchgeführt wird und sich so die Zahl der Neuronen
in der Netz-Struktur möglicherweise weiter verringert. Zukünftige
Untersuchungen müssen den Zusammenhang zwischen dem Einsatz der Editier-Schritte
und der theoretischen und praktischen Klassifikationsfähigkeit des
Netzes klären.
Resultate: Für
die Daten der HOM-Skala
zur Graduierung von Hirntumoren wurden verschiedene Netzwerkmodelle
trainiert. Von den 679 zur Zeit verfügbaren Datensätzen wurden
113 für das Training benutzt. Tabelle 1 zeigt die Ergebnisse.
Tabelle 1: Lernen
der HOM-Skala, ein Vergleich
Neben der Klassifikationsleistung ist insbesondere das Zeitverhalten
des SEN3-Netzwerks interessant. Es verbleiben nur 42 Neuronen im Netzwerk.
Das Multi Layer Backpropagation Netzwerk zeigt zwar die besten Resultate,
die zwei verborgenen Schichten mit 20 bzw. 50 Neuronen lassen den Berechnungsaufwand
jedoch in untragbare Höhen klettern.
Performancevergleiche auf
der Basis verschiedener anderer Datenmengen zeigten, daß die SEN3-Netzwerke
Resultate erzielten, die mit konventionellen Netzwerkarchitekturen mindestens
vergleichbar sind, wobei meist weniger Neuronen benötigt werden und
der Rechenaufwand stets um Größenordnungen reduziert wurde.
Literatur
Jürgen Rahmel:
KoDiag: Eine Methodik zur Erstellung konnektionistischer Expertensysteme,
Diplomarbeit, Universität Kaiserslautern, 1994 (Kapitel 5: Inkrementelle
Lernverfahren)
RAHMEL, Juergen; WANGENHEIM,
Aldo Von. KoDiag: A Connectionist Expert System. In: ISIKNH´94 -
INTERNATIONAL SYMPOSIUM ON INTEGRATING KNOWLEDGE AND NEURAL HEURISTICS,
PENSACOLA, FLORIDA, 1994
