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.