Gemeinsam statt einsam

Neuronales Netz auf Multitransputerbasis

Dr. Karl Sarnow

Mit allem Respekt vor der wirklich phantastischen Natur, es ist schon beinahe als `nat�rlich� anzusehen, wenn man Transputer und neuronale Netze eine �beraus effektive Verbindung eingehen l��t. So pr�sentiert die Firma hema eine Transputerstation samt neuronalem Netz, das unter anderem Objekte erkennt, die auf einem kleinen Drehteller vor einer Fernsehkamera rotieren. Das Besondere: Die Objekte werden unabh�ngig von der Drehtellerposition erkannt. Ist also das Invarianzproblem der Mustererkennung prinzipiell gel�st?

Unterthema: Das Nestor-Netzwerk
Unterthema: Stufen des Bilderkennungssystems
Unterthema: Thema-Konfiguration f�r Drehtellerapplikation

Europ�ische Sternstunden in der Entwicklung der Computertechnologie sind selten und werden daher mit besonderem Interesse wahrgenommen. Ein solcher Meilenstein war die Entwicklung des Transputers durch die englische Firma Inmos, die inzwischen zur SGS-Thompson-Gruppe geh�rt. Heute gibt es eine ganze Familie von Transputern, mit dem T222 als kleinstem (16-Bit-Transputer), �ber den T805 (32-Bit-Transputer mit FPU) bis zum 10mal leistungsf�higeren T9000, dessen Auslieferung kurz bevorsteht. Als Sprachen stehen inzwischen die meisten imperativen Programmiersprachen wie C, Pascal, Fortran, Modula 2 und Ada, mit zus�tzlichen Eigenschaften paralleler Programmierung versehen, sowie die eigens f�r Transputer entwickelte Sprache Occam [1] zur Verf�gung.

Original und Kopie

Neuronale Netze sind dem Versuch entsprungen, die Eigenschaften des menschlichen Gehirns dadurch nachzubilden, da� man die Eigenschaften der Bausteine menschlicher Intelligenz, der Neuronen, modelliert. Dabei sind neuronale Netze aber weder in Plastik eingepackte, ausgediente biologische Gehirne noch ist man sonderlich bem�ht, den k�nstlichen Neuronen exakt biologische Funktionsweisen beizubringen. Man begn�gt sich in Hinblick auf die begrenzte Rechenkapazit�t der Von-Neumann-Maschinen und des g�nzlich verschiedenen Arbeitsprinzips realer neuronaler Netze (ein Analogcomputer h�tte wahrscheinlich gr��ere Chancen, ein biologisches Neuron zu simulieren) mit einfachen mathematischen Modellneuronen.

Im Gehirn eines normal entwickelten Menschen werkeln grob gesch�tzt 10¹⁰ Neuronen zusammen. Eine ungeheuer gro�e Zahl verglichen mit der Anzahl aktiver Bauelemente heutiger Computer. Hinzu kommt, da� jedes biologische Neuron nicht einfach ein Schaltelement ist, sondern am ehesten als Summenverst�rker mit Schwellenschaltung und anschlie�ender Pulscodemodulationseinheit beschrieben werden kann; ein kleiner Analogrechner also. Kein Wunder, da� das menschliche Gehirn Aufgaben mit gr��ter Leichtigkeit erledigt, f�r die Rechner mit Von-Neumann-Architektur - selbst bei Einengung des Problemraums - verzweifelt, oftmals vergeblich ackern.

Schon bei diesem �u�erst oberfl�chlichen Vergleich biologischer neuronaler Netzwerke mit klassischen Von-Neumann-Maschinen wird klar, da� ein Ansatz mit vielen vernetzten PUs (ohne C wie Central) einer effektiven Implementation neuronaler Netze sehr n�tzlich sein kann. Man kommt so deren Struktur n�her, als dies �ber eine einzelne, wenngleich emsig schuftende CPU m�glich ist. Davon abgesehen, w�re diese wegen der immensen Anzahl von Verbindungen schon bei kleindimensionierten Netzen �berfordert. Zwar werden in absehbarer Zeit Transputersysteme auf (im Verh�ltnis zu biologischen Systemen l�cherlich) wenige Elemente beschr�nkt bleiben, dennoch aber hat man mit einem - zugegeben sehr grobk�rnigen - Transputernetz einen wichtigen Schritt in Richtung eines `Biological Computing� getan.

Das Besondere

Ein Transputersystem an sich w�re noch keine Neuigkeit, die c't-Leser beeindrucken k�nnte. Atari hatte eine ATW (einschlafen lassen), Parsytec bietet gro�dimensionierte Transputersysteme an; dennoch: wirklich interessant erscheint hier die Portierung der amerikanischen Netzwerksoftware `Nestor Learning System� (NLS) [2, 3] auf eine Transputerplattform.

NLS ist eine Entwicklung der US-Firma Nestor (Mitbegr�nder: Nobelpreistr�ger Leon N. Cooper), deren Vertrieb in Deutschland die Firma usp (Stuttgart) �bernommen hat. Eingebettet im NLS fungiert das `Nestor Development System� (NDS), mit dem das neuronale Netz dimensioniert werden kann. Dieser nicht zeitkritische Programmteil wird weiterhin auf einem normalen PC laufen. Ungeachtet dessen kann das neuronale Netz mit einer erheblichen Beschleunigung rechnen - zum einen wegen der gegen�ber dem 80386 erh�hten Rechenleistung eines T805-Prozessors, zum anderen wegen der m�glichen Arbeitsteilung der Transputer, die in einen nahezu linearen Anstieg der Rechengeschwindigkeit mit der Anzahl der Transputerknoten einm�nden soll.

Karussell

Herausgegriffen aus den vielf�ltigen Anwendungsm�glichkeiten sei die Applikation zur Erkennung von Objekten unter Verwendung des bereits angesprochenen Drehtelleraufbaus. Der schematische Aufbau weicht nicht vom �blichen Klassifikationssystem ab: Aus den Sensorsignalen (Videokamerasignal) wird nach einer Vorverarbeitung ein Merkmalsvektor abstrahiert (Segmentierung), der in das neuronale Netz eingespeist wird und eine reaktive Ausgabe (Response) erzeugt (die erkannte Klasse). Diese Reaktion l��t sich bei industriell eingesetzten Systemen weiter benutzen, um Roboter zu steuern, Ger�te zu schalten oder einfach eine Ausgabe auf dem Bildschirm zu erzeugen. F�r die Vorverarbeitung bietet hema eine ganze Palette von Einsteckkarten an, von einfachen I/O-Karten bis hin zum Frame-Grabber. Entsprechende Ausgabekarten unterst�tzen die Umsetzung der erkannten Klasse in aktorische Signale.

Ein faszinierendes Beispiel der Objekterkennung mit neuronalen Netzen: die Drehtellerapplikation.

In der Drehtellerapplikation nimmt die Kamera zun�chst ein Bild mit 256 Graustufen auf. Das Bild wird binarisiert, das hei�t, durch Schwellwertvergleich in ein reines S/W-Bild �berf�hrt. Mit dem Bin�rbild arbeitet der Ableitungsoperator (gebildet wird die 1. Ableitung der Helligkeit als Funktion des Ortes im Bild; siehe auch [4]), der die Kanten des Objekts hervortreten l��t. Anschlie�end erfolgt die Vektorisierung der Kontur des Bildes unter Zuhilfenahme eines Polygonzugs mit �quidistanten (gleichabst�ndigen) Ecken. Von jedem Punkt des Polygonzuges wird nun die L�nge zu jedem anderen Punkt bestimmt und in einem Merkmalsvektor abgelegt. Enth�lt das Polygon m Eckpunkte, so erh�lt man also m Merkmals- oder Featurevektoren (Ansichten). Dieses auf den ersten Blick umst�ndliche Verfahren besitzt allerdings den Vorteil, da� man sich der angestrebten Drehungsinvarianz n�hert. Im Idealfalle bedeutet dies eine Bilderkennung unabh�ngig von der Drehposition des Tellers.

In der Lernphase des neuronalen Netzes wird entsprechend der Nestor-Philosophie des RCE-Netzes (Restricted Coulomb Energy) jeder Ansicht ein Zwischenneuron zugewiesen, wobei die verschiedenen Ansichten eines Gegenstandes (Objektes) mit dem gleichen Neuron der Ausgangsschicht verbunden sind. Jeder neue Gegenstand wird als neues Ausgangsneuron hinzugef�gt. (In der Nestor-Terminologie werden Neuronen als Prototypen bezeichnet.) Sollten sich die Einzugsbereiche zweier Ansichten �berlagern, sorgt die Kollisionsbehandlung des RCE-Netzwerks daf�r, da� der Einzugsbereich der Ansichten entsprechend ge�ndert wird. Dieses Modell erh�lt seine Drehungsinvarianz also durch die vorher gesammelte Vielzahl von Ansichten, von denen eine mit der aktuellen Ansicht �bereinstimmen mu�.

Die Beschreibung des Algorithmus (siehe Kasten `Stufen des Bilderkennungssystems�) macht deutlich, da� eine erhebliche Rechenleistung zur Verf�gung stehen mu�, soll eine Anwendung in Echtzeit ablaufen. Bei der Thema-Station hat man deshalb das baumartige (triadische) Netzwerk mit 16 Transputern realisiert. Leider lie� sich die uns zur Verf�gung gestellte Konfiguration nicht variieren, das hei�t, es war nicht m�glich, die Anzahl der Transputertriaden nach Erstellung der Implementation zu ver�ndern. (Nach Angaben des Herstellers erbrachte bei der OCR eine 1-Transputer-Station eine Erkennungsleistung von 20 Zeichen pro Sekunde, w�hrend eine mit 5 Transputern ausgestattete Version 90 Zeichen je Sekunde verifizierte.)

Nacheinander wurden 4 Bilder aufgenommen (Ansichten). Die y-Achse gibt die Zeit wieder, die ben�tigt wird, um das neuronale Netz mit einer Fehlerrate deutlich unter 20 % zu trainieren. Auf der x-Achse ist die Anzahl der jeweils auf dem Drehteller liegenden Objekte dargestellt.

Auf dem Drehteller befinden sich 1, 2 oder 3 Objekte. Gemessen wurde, wie lange der Erkennungsproze� dauert, angefangen bei einer bis hin zu f�nf trainierten Ansichten.

Ganz sch�n fix

Um die Leistungsf�higkeit des Systems auszuloten, habe ich die Anzahl der zu erkennenden Objekte auf dem Drehteller sowie die Anzahl gelernter Ansichten ver�ndert und die jeweiligen Lern- und Erkennungszeiten gemessen. Ersichtlich wird eine grob lineare Abh�ngigkeit der Lernzeiten von der Anzahl der gelernten Ansichten. Nicht unerwartet nimmt die Lernzeit mit der Anzahl der zu erkennenden Objekte in etwa quadratisch zu. Bei den Erkennungszeiten findet sich eine lineare Abh�ngigkeit sowohl von der Anzahl gespeicherter Ansichten als auch von der Anzahl zu unterscheidender Objekte. Bemerkenswert: alle Zeiten liegen im Sekundenbereich.

Als letztes Kriterium bleibt die Fehlertr�chtigkeit des Systems. Bei diesem Experiment habe ich bei der Auswahl der zu lernenden Ansichten mit Vorsatz keinerlei Auswahlkriterien getroffen. Mit anderen Worten, die gelernten Positionen mu�ten rein zuf�llig gelernt werden. Bei sorgf�ltiger Auswahl zu lernender Positionen l��t sich der Lernerfolg verst�ndlicherweise erh�hen. So aber werden viele �hnliche Ansichten mitgelernt, die den Lernerfolg herabsetzen. Es spricht f�r das beschriebene Lernverfahren, da� bereits nach rund 3 Ansichten (Aufnahmen) das neuronale Netz austrainiert ist und eine Fehlerquote von circa 20 % unterschreitet. Hauptfehlerquelle dieses Experiments war das Modell eines Wasserflugzeugs, welches wegen seines komplexen Umrisses gegen�ber allen anderen Objekten erheblich gr��ere Anforderungen an die Klassifizierungsf�higkeit des Systems stellte. Auch hier mu� zur Entschuldigung des Systems gesagt werden, da� an den Default-Parametern keine �nderung vorgenommen wurde, was m�glicherweise auch der Erkennung dieses komplexen Objektes zu einem besserem Ergebnis verholfen h�tte.

Vielfach offen

Wie andere Transputer-Workstations auch ist die Thema-Station in ihrem Funktionsumfang weder speziell auf die geschilderte Applikation noch allgemein auf neuronale Netze beschr�nkt. So l�uft unter anderem das Betriebssystem Helios ebenso wie ein Parallelprolog oder die Proze�simulations- und Proze�visualisierungssoftware der Firma Gepard. Im �brigen l��t sich mit dem Nestor-Entwicklungssystem eine Vielzahl eigener Anwendungen erstellen, oder man greift auf bereits bestehende kommerzielle Applikationen zur�ck, zum Beispiel auf solche zur Herzschlagkontrolle, zur Hand- beziehungsweise Unterschriftenerkennung, zur Qualit�tskontrolle oder zur Sprach- beziehungsweise Sprecherkennung.

Alles in allem: Deutlich geworden sein d�rfte, da� ein Transputersystem eine effektive Alternative zu Neurochips darstellt und sich zudem leicht erweitern und variieren l��t. Ganz sicher ist, da� mit der Kombination von Multiprozessorsystemen und neuronalen Netzen weitere hochinteressante Entwicklungen auf uns zukommen werden. (ae)

Literatur

[1] Heinz Ebert: Occam - �berall gleichzeitig, c't 7/86 S. 44-50

[2] Pressemitteilung PR/3, hema Systemknowhow, 2/90

[3] Derek Stubbs: Neurocomputing Rap. AI Expert, June 90, S. 61-63

[4] Michael Schaale: Scharf gerechnet, Nachtr�gliche Kantenverst�rkung in digitalisierten Farbbildern, c't 1/90, S. 254-262

Kasten 1

Das Nestor-Netzwerk

Das Nestor-Netzwerk zeigt einen dreischichtigen Aufbau. In der Eingangsschicht (Input-Layer) wird der Merkmalsvektor angelegt. Jeder Ausgang des Merkmalsvektors ist mit einem Eingang jedes Knotens der Zwischenschicht (Hidden-Layer) verbunden. Jeder dieser Knoten stellt eine andere Ansicht des gleichen Objektes dar. Folglich sind alle Knoten der Zwischenschicht, die verschiedene Ansichten desselben Objektes repr�sentieren, mit demselben Knoten der Ausgangsschicht verbunden. Jeder Knoten der Ausgangsschicht entspricht somit einer einzigen Klasse (dem Objekt).

Den Eigenschaftsraum (links) der Objekte `A� und `B� findet man hier in zweidimensionaler Darstellung. Im Fall realer Objekte ist der Merkmalsvektor ein hochdimensionales Gebilde. F�llt ein Merkmalsvektor f = (f₁, f₂) in das Gebiet `A�, so mu� das Ausgangsneuron (im Output-Layer) aktiv sein. Der gelernte Gewichtungsvektor w₁ = (f₁, f₂) ist im Merkmalsraum eingetragen. F�llt in Zukunft ein Merkmalsvektor innerhalb des Kreises mit dem Radius lambda₁ um f₁, f₂, erkennt das Netzwerk das Objekt `A�. Der Lernvorgang (rechts) hat ein Neuron der Zwischenschicht und ein Neuron der Ausgangsschicht erzeugt. Der Gewichtsvektor w₁ entspricht dem Merkmalsvektor und wird im Verlauf des Lernens nicht korrigiert.

Ein neuer Merkmalsvektor liegt an. Er geh�rt zum Objekt `B�. Da sich dieser Vektor im Merkmalsvektorraum au�erhalb des Kreises (Kugel) um w₁ befindet, bleibt das `A�-Neuron inaktiv. Es mu� also ein neues Neuron der Zwischenschicht und der Ausgangsschicht hinzugef�gt werden. Zugleich ist ein zweiter Gewichtungsvektor w₂ dazugelernt worden. Wie vorher auch, l��t sich ein Kreis (Kugel) im Merkmalsvektorraum konstruieren. Der Gewichtungsvektor w₂ sorgt daf�r, da� das Neuron lambda₂ der Mittelschicht nur feuert, wenn der Featurevektor im markierten Kreis des Merkmalsvektorraums um w₂ liegt.

Eine kritische Situation: Der Merkmalsvektor f f�hrt zu einem Konflikt, da er sowohl im Einzugsbereich des Zwischenschichtneurons 1 als auch in dem des -neurons 2 liegt; beide Ausgangsneuronen, sowohl f�r `A� als auch `B�, sprechen an. Die L�sung der Konfliktsituation geschieht durch eine Reduzierung des Einzugbereichs von lambda₂, weil f n�her an `B� liegt. Dieser Konfliktl�sungsstrategie �ber jeweils verbesserte Abgrenzung verdankt das Netzwerk seinen Namen: Restricted Coulomb Energy (RCE). Bei reduziertem Einzugsbereich lambda₂ feuert nur noch das Neuron `A� der Ausgangsschicht. Es war also nicht erforderlich, einen neuen Knoten im Netzwerk hinzuzuf�gen.

Nach zahlreichen Lernvorg�ngen ist das Endstadium erreicht. Viele Neuronen der Zwischenschicht mit unterschiedlichem Einzugsbereich decken den Merkmalsvektorraum der beiden Objekte `A� und `B� ab.

Jedem Kreis im Merkmalsvektorraum entspricht ein Neuron der Zwischenschicht. Da nur zwei Objekte unterschieden werden, gibt es auch nur zwei Neuronen in der Ausgangsschicht.

Kasten 2

Stufen des Bilderkennungssystems

Im Lernzustand wird dem neuronalen Netz ein Merkmalsvektor (Featurevektor) und die dazugeh�rige Klasse angeboten. Nach dem Lernen soll das Netzwerk aus dem angebotenen Merkmalsvektor die gekoppelte Klasse erkennen. Der erste Schritt besteht in der Aufnahme eines Objektes �ber eine Videokamera und der Vorverarbeitung des Bildes mit Hilfe eines Framegrabbers. Als Ergebnis erh�lt man ein S/W-Bild mit 256 Graustufen.

Im zweiten Schritt erfolgt die Binarisierung des Bildes, das hei�t, alle Graustufen unterhalb einer Schwelle werden zu wei�, alle oberhalb zu schwarz (oder umgekehrt) kodiert.

Der dritte Schritt umfa�t die Herausarbeitung der Kanten. Hier wird die Ableitung gebildet nach den Koordinaten in der Bildebene. Dort, wo eine �nderung der Helligkeit eintritt, wird ein wei�er Bildpunkt, dort, wo keine �nderung der Helligkeit vorliegt, ein schwarzer Bildpunkt gesetzt.

Zur Vektorisierung �berzieht das Programm das Objekt mit einem Polygonzug aus �quidistanten Punkten. Von jedem Punkt des Polygonzuges aus wird der Abstand zu n folgenden Punkten des Polygonzuges gemessen. Man erh�lt so m Vektoren der Dimension n. Diese Vektoren hei�en Merkmalsvektoren. Jeder Merkmalsvektor entspricht einer anderen Ansicht desselben Objekts.

Ein einfaches Beispiel: Besteht der Polygonzug aus nur 4 Punkten, erh�lt man 4 Merkmalsvektoren v₁ bis v₄. Werden alle 3 Folgepunkte eines Punktes ber�cksichtigt, dann entstammen die Merkmalsvektoren einem 3dimensionalen Vektorraum. Zusammen mit dem Einzugsbereich lambda (siehe Kasten `Das Nestor-Netzwerk�) bilden diese Merkmalsvektoren ein Gebilde aus 4 Kugeln im Merkmalsraum.

Liegt ein Merkmalsvektor innerhalb einer dieser Kugeln, wird er vom Netz als Element dieser Klasse erkannt.

Kasten 3

Thema-Konfiguration f�r Drehtellerapplikation

Hostrechner: 386/486 AMI Motherboard mit 4 MB DRAM (8 MB optional) MSDOS- und Unix-kompatibel

VGA-Adapter 1024 � 768, 512 KB DRAM

VGA-Monitor

80-MB-SCSI- oder 150-MB-ESDI-Festplatte (350, 600 MB optional)

3,5"- und 5,25"-Diskettenlaufwerk

2 unabh�ngige Spannungsversorgungen f�r PC und Transputer

Grafikkarte TG300 (32-Bit-Transputer T805 mit 25 MHz, 2 MB Hauptspeicher, 2-MB-Video-RAM; Framegrabber TF9502)

18 Transputerkarten TR8 im Einfach-Europaformat (32-Bit-Transputer T805 mit 25 MHz, 1 MB DRAM)

Der eigentliche Klassifikator besteht aus 16 Transputern, die triadisch als Baumstruktur vernetzt sind, die restlichen 3 Transputer arbeiten als Controller, Bildvorverarbeiter oder zusammen mit Framegrabber und Grafik.