PatentDe  


Dokumentenidentifikation DE60206194T2 14.06.2006
EP-Veröffentlichungsnummer 0001451773
Titel VERFAHREN UND SCHALTUNGEN ZUM VIRTUELLEN VERGRÖSSERN DER ANZAHL VON PROTOTYPEN IN ARTIFIZIELLEN NEURONALEN NETZWERKEN
Anmelder International Business Machines Corp., Armonk, N.Y., US
Erfinder IMBERT DE TREMIOLLES, Ghislain, F- 06570 Saint Paul, FR;
TANNHOF, Pascal, F-77300 Fontainebleau, FR
Vertreter Teufel, F., Dipl.-Phys., Pat.-Anw., 70569 Stuttgart
DE-Aktenzeichen 60206194
Vertragsstaaten AT, BE, BG, CH, CY, CZ, DE, DK, EE, ES, FI, FR, GB, GR, IE, IT, LI, LU, MC, NL, PT, SE, SK, TR
Sprache des Dokument EN
EP-Anmeldetag 11.07.2002
EP-Aktenzeichen 027584093
WO-Anmeldetag 11.07.2002
PCT-Aktenzeichen PCT/EP02/08473
WO-Veröffentlichungsnummer 0003012737
WO-Veröffentlichungsdatum 13.02.2003
EP-Offenlegungsdatum 01.09.2004
EP date of grant 14.09.2005
Veröffentlichungstag im Patentblatt 14.06.2006
IPC-Hauptklasse G06N 3/00(2006.01)A, F, I, 20051017, B, H, EP

Beschreibung[de]
GEBIET DER ERFINDUNG

Die vorliegende Erfindung betrifft künstliche neuronale Netzwerke und insbesondere ein Verfahren und Schaltungen zum virtuellen Erhöhen der Anzahl von Prototypen, die in einem künstlichen neuronalen Netzwerk (KNN) verarbeitet werden können, das auf einem Eingangsraum-Abbild beruht. Im Ergebnis dessen wird ein verbessertes KNN beschrieben, das im Vergleich zu einem konventionellen KNN in der Weise über erweitere Fähigkeiten verfügt, dass es einen Satz von Eingangsmustern mit Prototypen vergleichen kann, deren Anzahl höher ist als die Anzahl von Neuronen, die physikalisch in dem KNN vorhanden sind. Das verbesserte KNN kann mit einem konventionellen KNN, das nur über eine begrenzte Anzahl von Neuronen verfügt, ohne enorme Erweiterung der erforderlichen Hardware eine unbegrenzte Anzahl von Prototypen verarbeiten und ist somit für fortgeschrittene Echtzeitanwendungen umfassend geeignet.

HINTERGRUND DER ERFINDUNG

Zur Charakterisierung von Eingangsdaten wird heutzutage in der Datenverarbeitung eine Vielzahl von Erkennungs-, Vorhersage- und Berechnungsaufgaben durchgeführt, bei denen Referenzdatenbanken eingesetzt werden. Je nach Art des zu lösenden Problems enthalten diese Referenzdatenbanken Muster, bei denen es sich um Unterabbildungen, Untersignale und Untergruppen von Daten und Kombinationen davon handelt. Die in diesen Referenzdatenbanken gespeicherten Muster werden im Weiteren als Prototypen bezeichnet. Wie dem Fachmann bekannt ist, werden sie im Allgemeinen durch einen Vektor dargestellt, d. h. durch eine Anordnung in einem n-dimensionalen Raum. Bekannte Verfahren zur Charakterisierung neuer (unbekannter) Muster, im Weiteren als Eingangsmuster bezeichnet, bei denen Referenzdatenbanken eingesetzt werden, basieren auf Eingangsraum-Abbildungsalgorithmen wie K-Nearest-Neighbor oder Region of Influence (ROI). Das Grundprinzip dieser Algorithmen besteht in der Berechnung des Abstandes zwischen dem Eingangsmuster und jedem der gespeicherten Prototypen, um in Abhängigkeit von vordefinierten Schwellenwerten oder auch ohne Schwellenwerte den/die Prototypen mit dem geringsten Abstand herauszufinden. Das auf die IBM Corp. übertragene US-Patent 5,621,863 beschreibt auf derartigen Eingangsraum-Abbildungsalgorithmen beruhende künstliche neuronale Netzwerke, die innovative Elementarprozessoren eines neuen Typs umfassen, welche als ZISC-Neuronen bezeichnet werden (ZISC ist ein eingetragenes Warenzeichen der IBM Corp.). Eine wesentliche Eigenschaft der ZISC-Neuronen besteht in ihrer Fähigkeit, im Parallelbetrieb zu arbeiten, d. h. wenn ein Eingangsmuster zum KNN gelangt, berechnen alle ZISC-Neuronen gleichzeitig den Abstand zwischen dem Eingangsmuster und seinen gespeicherten Prototypen. Auf diese Weise ist, anders als die Antwortzeit einer Softwareemulation eines derartigen Prozesses, die linear von der Anzahl der Prototypen abhängt, die Antwortzeit des ZISC-KNN hinsichtlich der Gesamtheit des Abstandsauswertungsprozesses ungeachtet der Anzahl der Prototypen konstant.

1 stellt die Hardware dar, die zur Veranschaulichung des Hauptprinzips des Verfahrens zur Abstandsauswertung eingesetzt wird, wie es gegenwärtig in einem ZISC-KNN praktiziert wird. In 1 ist die Architektur eines neuronalen Systems 100 abgebildet, das einen Hostcomputer 110, z. B. einen Personalcomputer, und ein konventionelles ZISC-KNN 120 einschließlich einer Menge von Neuronen 130-1 bis 130-n (die im Weiteren allgemein mit 130 bezeichnet sind) umfasst. Physikalisch kann das KNN aus einer Leiterplatte mit einigen darauf angebrachten ZISC-Chips bestehen, z. B. dem Chip ZISC036, die jeweils 36 Neuronen umfassen. Jedes Neuron, z. B. 130-1, ist zur Vereinfachung auf zwei wesentliche Elemente reduziert: auf einen Prototypspeicher 140-1 zur Speicherung eines Prototyps, wenn das Neuron in der Lernphase einen Eingangsvektor aufgenommen hat, und auf einen Abstandsauswerter 150-1. Der Eingangsdatenbus 160 legt sequenziell den Satz von Komponenten eines Eingangsmusters parallel an alle Neuronen 130 des KNN 120 an und der Ausgangsdatenbus 170 überträgt die Ergebnisse des Abstandsauswertungsprozesses, typischerweise Abstand und Kategorie (andere oder detailliertere Parameter wären ebenfalls denkbar), an den Host 110. Gemäß dem Ansatz im oben erwähnten US-Patent 5,621,863 wird das Eingangsmuster, wenn es über den Datenbus 160 zu jedem Neuron 130 übertragen wurde, im Abstandsauswerter 150 mit dem im Neuron gespeicherten Prototyp verglichen, sodass das Ergebnis im Allgemeinen aus einem Wertepaar besteht: einem Abstand und der Kategorie. Zur Vereinfachung ist das Kategorieregister in 1 nicht dargestellt, es wird als im Abstandsauswerter 150 enthalten angesehen. Wie aus 1 hervorgeht, ist die Architektur des ZISC-KNN so ausgeführt, dass in allen Neuronen, die das KNN bilden, alle Abstandsauswertungen gleichzeitig durchgeführt werden.

Es liegt auf der Hand, dass das in 1 abgebildete konventionelle KNN auf die Speicherung einer festen Anzahl von Prototypen beschränkt ist, die durch die Anzahl n der Neuronen bestimmt ist. In diesem Fall beträgt die Anzahl p der Neuronen p <= n. Jedoch können moderne Echtzeitanwendungen in Abhängigkeit von mehreren Faktoren wie der Anzahl m der Prototypkomponenten und der erforderlichen Genauigkeit des KNN durchaus einige wenige bis zu mehreren hunderttausend ZISC-Neuronen nutzen. Dabei ist zu berücksichtigen, dass es nicht immer realistisch ist, so viele Neuronen zu verwenden wie erforderlich wären. Die in den zurückliegenden Jahren erreichte enorme Zunahme des Integrationsniveaus, die die Integration von Millionen von Transistoren in einem einzigen Halbleiter erlaubt, bietet die Möglichkeit, tatsächlich mehrere hundert Neuronen in einen Siliziumchip einzubetten, was es andererseits erlaubt, mehrere tausend Neuronen auf einer großen Leiterplatte zu integrieren. Als Folge würde der Aufbau eines KNN, das physikalisch aus mehreren hunderttausend Neuronen zusammengesetzt ist, sehr komplex und kostspielig werden.

Es besteht daher die dringende Notwendigkeit, ein ZISC-KNN zu realisieren, das ohne komplexe und somit kostspielige Hardware so viele Prototypen wie erforderlich verarbeiten kann, um den Anforderungen heutiger und zukünftiger Echtzeitanwendungen gerecht zu werden. Es besteht dementsprechend ein Hauptziel des Verfahrens und der Schaltungen gemäß der vorliegenden Erfindung darin, die oben genannten Beschränkungen und Unzulänglichkeiten des konventionellen KNN nach 1 zu beseitigen.

ÜBERBLICK ÜBER DIE ERFINDUNG

Eine Hauptaufgabe der vorliegenden Erfindung besteht daher darin, ein Verfahren und Schaltungen zum virtuellen Erhöhen der Anzahl von Prototypen bereitzustellen, die in einem konventionellen künstlichen neuronalen Netzwerk (KNN) verarbeitet werden können, das auf einem Eingangsraum-Abbild beruht.

Eine weitere Aufgabe der vorliegenden Erfindung besteht darin, ein Verfahren und Schaltungen zur Verarbeitung von Prototypen in einem konventionellen KNN bereitzustellen, deren Anzahl viel höher sein kann als die Anzahl der in dem KNN physikalisch vorhandenen Neuronen.

Außerdem besteht eine weitere Aufgabe der Erfindung darin, ein verbessertes KNN bereitzustellen, das zur Verarbeitung von Prototypen, deren Anzahl völlig unabhängig von der Anzahl der Neuronen ist, um ein konventionelles KNN herum angeordnet ist.

Darüber hinaus besteht eine weitere Aufgabe der Erfindung darin, ein Verfahren und Schaltungen zur virtuellen Erhöhung der Anzahl von Prototypen bereitzustellen, die in einem konventionellen KNN ohne wesentlich komplexere KNN-Hardware verarbeitet werden können.

Schließlich besteht eine weitere Aufgabe der Erfindung darin, ein Verfahren und Schaltungen zur virtuellen Erhöhung der Anzahl von Prototypen bereitzustellen, die in einem konventionellen KNN zu sehr niedrigen Kosten verarbeitet werden können.

Die Erfüllung dieser und anderer damit zusammenhängender Aufgaben wird durch das verbesserte KNN und das Verfahren gemäß der vorliegenden Erfindung erreicht.

Zuerst wird ein verbessertes KNN für den Vergleich einer Menge von q Eingangsmustern mit p Prototypen beschrieben, bei dem ein aus n Neuronen zusammengesetztes KNN verwendet wird, in dem während der Erkennungs-/Klassifizierungsphase die Anzahl von Prototypen größer ist als die Anzahl von Neuronen (p > n), sowie für die Erzeugung der Ergebnisse daraus, wobei das verbesserte KNN Folgendes umfasst:

  • – ein aus einer Menge von n Neuronen gebildetes KNN, wobei jedes Neuron über einen Prototypspeicher zur Speicherung eines Prototyps und einen Auswerter zur Erzeugung eines lokalen Auswertungsergebnisses verfügt, das auf dem Vergleich zwischen dem an das KNN übergebenen Eingangsmuster und dem im Neuron gespeicherten Prototyp basiert, sodass das KNN k (k >= 1) globale Ergebnisse erzeugt, deren Anzahl den während der Erkennungs-/Klassifizierungsphase spezifizierten k Parametern entspricht;
  • – mindestens 3 Datenbanken: eine erste Datenbank zur Speicherung der n Prototypen, die auf s Sektoren von bis zu n Prototypen verteilt sind, eine zweite Datenbank zur Speicherung der q Eingangsmuster (oder Abfragen), die an das KNN übergeben werden sollen, und eine dritte Datenbank zur Speicherung der q × k Werte;
  • – Vergleichs- und Aktualisierungsmittel, die für den Vergleich der bei der Auswertung erhaltenen Ergebnisse mit den zuvor für dasselbe Eingangsmuster ermittelten Ergebnissen eines früheren Sektors (oder mit den bei der Initialisierung bereits vorhandenen Ergebnissen) konfiguriert sind, wobei entsprechend einem vordefinierten Kriterium und auf der Grundlage dieses Vergleichs die zuvor gespeicherten Ergebnisse aktualisiert oder nicht aktualisiert werden; und
  • – für den Transport ausgelegte Datenbusmittel: Transport der Prototypdaten zum Prototypspeicher, Transport der Eingangsmusterdaten zum Abstandsauswerter und Transport der Ergebnisdaten vom Auswerter zur dritten Datenbank.

Es wird auch ein Verfahren zur Erhöhung der Anzahl von Prototypen beschrieben, die in einem künstlichen neuronalen Netzwerk (KNN) verarbeitet werden sollen, das über eine begrenzte Anzahl von Neuronen verfügt, wobei das Verfahren die folgenden Schritte umfasst:

  • a) Bereitstellen eines KNN, das aus einer Menge von n Neuronen gebildet wird, wobei jedes Neuron über einen Prototypspeicher zur Speicherung eines Prototyps verfügt sowie über einen Auswerter zur Erzeugung des lokalen Ergebnisses einer Auswertung, die auf dem Vergleich zwischen dem an das KNN übergebenen Eingangsmuster und dem im Neuron gespeicherten Prototyp beruht, sodass das KNN k (k >= 1) globale Ergebnisse erzeugt, deren Anzahl den während der Erkennungs-/Klassifizierungsphase spezifizierten k Parametern entspricht;
  • b) Bereitstellen einer ersten Datenbank, die die zu verarbeitenden p Prototypen enthält, in der die Anzahl p der Prototypen größer ist als die Anzahl n der Neuronen, und die die p Prototypen auf s Sektoren aufteilt, wobei jeder Sektor bis zu n Prototypen enthält;
  • c) Bereitstellen einer zweiten Datenbank, die die q Eingangsmuster (oder Abfragen) enthält, die an das KNN übergeben werden sollen;
  • d) Bereitstellen einer dritten Datenbank, die die q × k Werte der Auswertung speichern kann;
  • e) Laden eines Sektors i (i = 1 bis s) von Prototypen, die im Prototypspeicher der n Neuronen verarbeitet werden sollen;
  • f) Übergeben eines Eingangsmusters des Ranges j (j = 1 bis q) an das KNN zur Auswertung;
  • g) Vergleichen der Ergebnisse mit den für ein Eingangsmuster desselben Ranges erhaltenen Ergebnissen, die zuvor gespeichert wurden (oder mit dem bei der Initialisierung gespeicherten Wert) und – abhängig von dem Vergleich – Speicherung oder keine Speicherung der Ergebnisse an dem entsprechenden Speicherplatz in der dritten Datenbank;
  • h) Wiederholen der Schritte f) und g), bis alle Eingangsmuster an das KNN übergeben wurden;
  • i) Wiederholen der Schritte e) bis h), bis alle Sektoren geladen wurden, sodass am Ende des Auswertungsprozesses die Endergebnisse in der dritten Datenbank enthalten sind.

Die neuartigen Merkmale, die als charakteristisch für die Erfindung angesehen werden, sind in den beiliegenden Ansprüchen dargelegt. Die Erfindung selbst jedoch sowie auch deren andere Aufgaben und Vorteile sind möglicherweise am besten verständlich anhand der folgenden detaillierten Beschreibung einer dargestellten bevorzugten Ausführungsart, die in Verbindung mit den beigefügten Zeichnungen zu lesen ist.

KURZBESCHREIBUNG DER ZEICHNUNGEN

1 zeigt schematisch die Architektur eines neuronalen Systems, das aus einem konventionellen KNN mit ZISC-Neuronen besteht und von einem Hostcomputer gesteuert wird, wobei in jedem Neuron der Abstand zwischen dem an das KNN übergebenen Eingangsmuster und dem im Neuron als Standard gespeicherten Prototyp berechnet wird.

2 zeigt die Architektur des neuronalen Systems nach 1, die zur Implementierung eines verbesserten KNN gemäß der vorliegenden Erfindung modifiziert wurde, wobei in dem verbesserten KNN die Anzahl p von Prototypen, die verarbeitet werden können, größer ist als die Anzahl n von ZISC-Neuronen, die in dem KNN physikalisch vorhanden sind.

3a zeigt ein Ablaufdiagramm, in dem die Hauptschritte des Verfahrens gemäß der vorliegenden Erfindung zusammengefasst sind.

3b zeigt eine Variante des Ablaufdiagramms aus 3a.

Die 4a bis 4k zeigen ein detailliertes Beispiel zur Veranschaulichung des Verfahrens gemäß der vorliegenden Erfindung.

BESCHREIBUNG EINER BEVORZUGTEN AUSFÜHRUNGSART

Das durch die Erfindung gelöste Problem besteht in der Verarbeitung einer Anzahl p von Prototypen in einem konventionellen KNN aus n physikalischen Neuronen, bei dem p größer als n ist, sogar um mehrere Größenordnungen. Entsprechend einem Hauptmerkmal der vorliegenden Erfindung werden die Komponenten aller zu verarbeitenden Prototypen in einem Speicher abgelegt, typischerweise in einem Schreib-/Lese-Speicher, wodurch sie eine erste Datenbank bilden. Die in der ersten Datenbank gespeicherten Komponentenwerte können jederzeit ausgelesen werden, um die Komponentenwerte beliebiger Neuronen des KNN wiederherzustellen, wann immer das gewünscht ist. In gleicher Weise werden alle auszuwertenden q Eingangsmuster in einem anderen Speicher, typischerweise einem Schreib-/Lese-Speicher abgelegt, um eine zweite Datenbank zu bilden. Schließlich werden die Ergebnisse des Prozesses der Abstandsauswertung und, allgemeiner, die Ergebnisse der Erkennungsphase (d. h. nicht wie üblich nur auf die Abstands- und Kategoriewerte beschränkt, sondern auch jeder beliebige angegebene Parameter) auch in einem Schreib-/Lese-Speicher abgelegt, um eine dritte Datenbank zu bilden. Im Verlauf des Prozesses der Abstandsauswertung handelt es sich bei den Ergebnissen um „Zwischenergebnisse", die am Ende des Prozesses zu „Endergebnissen" werden. In Abhängigkeit von der jeweiligen Anwendung sind diese Schreib-/Lese-Speicher entweder Teil des RAM im Host 110 oder als unabhängige Speichereinheiten implementiert.

2 zeigt die Architektur des neuronalen Systems nach 1, die zur Implementierung eines verbesserten KNN gemäß der vorliegenden Erfindung modifiziert wurde, wobei in dem verbesserten KNN die Anzahl von Prototypen, die an der Erkennungsphase beteiligt sind, größer ist als die Anzahl von ZISC-Neuronen, die in dem konventionellen KNN 120 physikalisch vorhanden sind. Zur Bezeichnung identischer (entsprechender) Teile werden in den verschiedenen Zeichnungen dieselben Bezugsnummern (mit hoch gestellten Strichen) verwendet.

In 2 besteht die neuartige Architektur des neuronalen Systems, die die Ziffer 200 trägt, aus dem Hostcomputer 110 und dem verbesserten ZISC-KNN, das jetzt mit 120' bezeichnet ist. Das verbesserte KNN 120' umfasst noch das konventionelle KNN 120 aus 1, eine Schnittstellenschaltung 210, einen Datenbankblock 220, der aus drei Datenbanken 222, 224 und 226 besteht, und schließlich eine Vergleichs- und Aktualisierungsschaltung 230. Die Rolle der Schnittstellenschaltung 210 besteht im Empfang der Daten aus dem Hostcomputer 110 zu deren richtiger Verteilung auf die drei Datenbanken im Datenbankblock 220 und umgekehrt in der Übertragung des Inhaltes der Datenbanken in den Hostcomputer 110. Wie aus 2 ersichtlich ist, umfasst der Datenbankblock 220 drei Datenbanken. Die erste Datenbank 222 enthält die Prototypen, die zweite Datenbank 224 enthält die Eingangsmuster und die dritte Datenbank 226 enthält die Ergebnisse des Prozesses der Abstandsauswertung. Die erste Datenbank 222, die auch als Prototypdatenbank bezeichnet wird, ist in s Unterdatenbanken oder Sektoren 222-1 bis 222-s aufgeteilt, wobei jeder Sektor zur Speicherung von bis zu n Prototypen ausgelegt ist. Im Ergebnis dessen enthält jeder Sektor mit Ausnahme des letzten (sofern vorhanden) n Prototypen, während der letzte Sektor die verbleibenden Prototypen enthält. Die erste Datenbank 222 enthält p × m Werte (wenn sie vollständig gefüllt ist, enthält sie n × s × m Werte). Die zweite Datenbank 224 wird auch Abfragedatenbank genannt, weil die Eingangsmuster, die an das verbesserte KNN 120' übergeben werden sollen, in der Literatur oft als Abfragen bezeichnet werden. Die zweite Datenbank 224 enthält somit q × m Werte. Schließlich enthält die auch als Ergebnisdatenbank bezeichnete dritte Datenbank 226 die Zwischenergebnisse aus dem Prozess der Abstandsauswertung, der in der Erkennungs-/Klassifizierungsphase durchgeführt wird, und am Ende dieses Prozesses enthält die Datenbank die endgültigen Abstände DIST und die zugehörigen Kategorien CAT. Sind die Ergebnisse auf die Parameter Abstand und Kategorie beschränkt, enthält die dritte Datenbank somit 2 × q Werte. Weil man auch andere spezifizierte Parameter vorsehen könnte, enthält die dritte Datenbank 226 k × q Werte, wenn k verschiedene spezifizierte Parameter vorhanden sind. Die Vergleichs- und Aktualisierungsschaltung 230 vergleicht die globalen Ergebnisse, die durch das KNN für jede Abfrage (Übergabe der Eingangsmuster) erzeugt wurden, mit den Ergebnissen, die zuvor in der dritten Datenbank 226 gespeichert wurden, und aktualisiert sie im Bedarfsfall. Der Adresscontroller 240 arbeitet mit der Schnittstellenschaltung 210 zusammen, um zur Auswahl der richtigen Daten entsprechende Adressen an die drei Datenbanken zu senden. Zu beachten ist bei der speziellen Implementierung des Datenbankblocks 220 im Hostcomputer 110, dass die Funktion des Adresscontrollers 240 durch den Hostcomputer 110 selbst erfüllt wird.

Das Verfahren der vorliegenden Erfindung wird nun in Verbindung mit 3a beschrieben, die ein Ablaufdiagramm mit der Bezeichnung 300 zeigt, welches den Algorithmus an der Basis des Verfahrens gemäß der vorliegenden Erfindung veranschaulicht. Es werden zwei Laufvariablen verwendet, i (Unterdatenbank- oder Sektorenindex), die zwischen 1 und der Sektorenanzahl s variiert, und j (Abfrageindex), die zwischen 1 und der Anzahl q der Eingangsmuster (d. h. der Abfragen) variiert, die übergeben werden sollen. Der Prozess wird in Kasten 301 gestartet. In Kasten 302 werden die erste Laufvariable i auf den Wert 1 gesetzt und die endgültigen Abstands- und Kategoriewerte für alle q Eingangsmuster initialisiert, zum Beispiel auf den maximalen Abstandswert (Max) bzw. auf null. Zu beachten ist, dass es sich bei Max um den Maximalwert handelt, der codiert werden kann. Wie aus Kasten 303 ersichtlich ist, werden die im aktuellen Sektor gespeicherten Komponenten aller Prototypen in die n Neuronen des KNN 120 geladen und die zweite Laufvariable j wird auf 1 gesetzt. Das neuronale System 200 ist bereit für die erste Abfrage. In Kasten 304 wird eine Abfrage an das KNN übergeben; der Abstand dist und die zugehörige Kategorie cat, die als Standard für diese Abfrage bestimmt werden, sind Zwischenergebnisse. Der berechnete Abstand dist wird in Kasten 305 mit DIST (j) verglichen. Bei dist < DIST(j) werden DIST (j) und CAT(j) aktualisiert, d. h. in Kasten 306 sind DIST (j) = dist und CAT (j) = cat. Bei dist >= DIST(j) oder wenn in Kasten 306 eine Aktualisierung stattfand, wird in Kasten 307 eine neuer Test (j = q?) durchgeführt, um festzustellen, ob dies die letzte Abfrage ist, die verarbeitet wurde, oder nicht. Wenn nicht, d. h. bei j < q wird die Variable j in Kasten 308 erhöht, d. h. j = j + 1, und es wird eine neue Abfrage übergeben, wie in Kasten 304 dargestellt. Ist im Gegensatz dazu j = q, bedeutet dies, dass alle Abfragen für diesen Sektor i verarbeitet wurden und nun ein anderer Sektor (falls vorhanden) in den Prozess einbezogen werden muss. Zu diesem Zweck wird die Variable i in Kasten 309 erhöht (i = i + 1). In Kasten 310 wird ein neuer Test durchgeführt, um zu bestimmen, ob die Variable i ihren Endwert, d. h. ob i = s, erreicht hat oder nicht. Bei Ja (Y) stoppt der Prozess in Kasten 311, d. h. es sind keine weiteren Sektoren zu verarbeiten. Am Ende des Prozesses der Abstandsauswertung (Erkennungsphase) handelt es sich bei den in der Datenbank 226 gespeicherten Werten um die oben erwähnten Endergebnisse. Die Endergebnisse (der kleinste Abstand DIST und die zugehörige Kategorie CAT) werden dann dem Hostcomputer 110 zur Verfügung gestellt. Wenn nicht (N), wird der Prozess durch die Rückkehr zu Kasten 303 fortgesetzt.

3b zeigt eine Variante des anhand von 3a beschriebenen Verfahrens. In diesem Fall sind, wie jetzt in Kasten 302' ersichtlich wird, die in Kasten 302 (3a) durchgeführten Initialisierungen des Abstandes (DIST) und der Kategorie (CAT) nicht mehr nötig. Andererseits ist jetzt ein in Kasten 312 durchgeführter zusätzlicher Schritt erforderlich, um zu testen, ob i = 1 ist oder nicht (erster Sektor). Wenn nicht, wird der Prozess mit dem in Kasten 305 durchgeführten Test fortgesetzt, andernfalls springt der Prozess direkt zu Kasten 306.

Zu beachten ist, dass in dem Beispiel oben die Ergebnisse lediglich aus einem Abstand und einer Kategorie bestehen, aber die oben aufgeführten Gedankengänge können in verallgemeinerter Form auch auf zahlreichere Abstände (oder Kategorien) und/oder andere spezifizierte Parameter (z. B. Schwellenwerte, ...) angewendet werden.

Das in 3a dargestellte Verfahren gemäß der vorliegenden Erfindung wird nun anhand der 4a bis 4k erläutert.

In den 4a bis 4k sind nur der Datenbankblock 220 und das konventionelle KNN 120 des verbesserten KNN 120' wiedergegeben. In Übereinstimmung mit 2 ist das KNN 120 auf drei Neuronen beschränkt (n = 3). Der besseren Veranschaulichung wegen wird eine Anwendung angenommen, bei der fünf Prototypen (p = 5) mit jeweils drei Komponenten (m = 3) erforderlich sind und dass vier Eingangsmuster (q = 4) klassifiziert werden müssen. Wie aus den 4a bis 4k ersichtlich ist, wird der Inhalt der drei Datenbanken (222, 224 und 226) bei jedem der Haupt-Verarbeitungsschritte angezeigt und die aktiven Teile/Busse des verbesserten KNN 120' werden in fetten Linien dargestellt.

Gemäß 4a sind drei Prototypen B1 (5, 9, 12), B2 (13, 9, 9) und B3 (2, 19, 3) und zwei Prototypen B4 (14, 3, 7) und B5 (11, 6, 13) jeweils in dem mit 222-1 und 222-2 bezeichneten ersten bzw. zweiten Sektor der Prototypdatenbank 222 an bestimmten Speicherplätzen der Datenbank gespeichert. Wie aus 4a ersichtlich ist, sind vier Eingangsmuster A1 (5, 19, 9), A2 (7, 3, 12), A3 (18, 4, 3) und A4 (11, 6, 13) an vier Speicherplätzen (224-1 bis 224-4) der Abfragedatenbank 224 gespeichert. In dieser bevorzugten Ausführungsart werden die globalen Ergebnisse des Prozesses der Abstandsauswertung, die durch das KNN bei jedem übergebenen Eingangsmuster ermittelt werden, d. h. Abstand und Kategorie, in der Ergebnisdatenbank 226 an zwei Positionen (obere bzw. untere) auf vier Speicherplätzen (226-1 bis 226-4) abgelegt. In der Ergebnisdatenbank 226 existiert die gleiche Anzahl an Speicherplätzen (226-1 bis 226-4) wie in der Abfragedatenbank 224 (224-1 bis 224-4). Bei der Initialisierung ist der Inhalt der oberen Position, d. h. die Kategorie, für jeden Speicherplatz der Ergebnisdatenbank 226 irrelevant, während der Maximalabstand Max in der unteren Position des Speicherplatzes abgelegt wird. Wie oben erwähnt ist das Kategorieregister in 4a als Teil des Abstandsauswerters dargestellt.

Gemäß 4b werden die Komponenten der Prototypen B1–B3 des ersten Speichersektors (222-1) über den Bus 160'' in den Prototypspeicher ihres entsprechenden Neurons geladen. Zu beachten ist, dass zur besseren Veranschaulichung die zu jedem Prototyp gehörige Kategorie dem Rang des Prototyps entspricht. Mit anderen Worten: Die Kategorie des Prototyps B1 ist 1.

Gemäß 4c wird das erste Eingangsmuster A1 (erste Abfrage) über den Bus 160' dem KNN 120 übergeben und es werden die Abstände berechnet. In diesem Fall wird die Norm L1 verwendet (siehe das oben erwähnte US-Patent hinsichtlich der Details des Berechnungsverfahrens), Die drei ermittelten Abstände, d. h. 9, 14 und 13 für die Neuronen 130-1, 130-2 und 130-3, sind lokale Ergebnisse. Der Wert des kleinsten ermittelten Abstandes beträgt 9, was dem ersten Prototyp entspricht. Die Werte für diesen Abstand und die zugehörige Kategorie, d. h. 9 bzw. 1, sind globale Ergebnisse, die die Reaktion des KNN 120 auf die Übergabe des ersten Eingangsmusters wiedergeben und die über den Bus 170 an ihren entsprechenden Positionen auf dem Speicherplatz 226-1 abgelegt werden.

Gemäß 4d wird ein identischer Prozess auf das Eingangsmuster A2 angewendet und die Werte für den kleinsten Abstand und die Kategorie, d. h. 8 bzw. 1, werden an ihren entsprechenden Positionen auf dem Speicherplatz 226-2 abgelegt.

Gemäß Bild 4e wird der Prozess mit der Übergabe des Eingangsmusters A3 fortgesetzt. Der kleinste durch den Prototyp B2 ermittelte Abstand beträgt 16 und die Kategorie ist somit 2 (der Rang von B2). Diese Werte werden an ihren entsprechenden Positionen auf dem Speicherplatz 226-3 abgelegt.

Gemäß 4f wird der Prozess mit der Übergabe des letzten Eingangsmusters A4 fortgesetzt. Der kleinste Abstand (d. h. 9) wird durch den Prototyp B2 ermittelt und somit erhält die Kategorie den Wert 2. Diese Werte werden an ihren entsprechenden Positionen auf dem Speicherplatz 226-4 abgelegt.

In diesem Prozessstadium sind alle Prototypen des ersten Sektors verarbeitet worden und der Prozess wird mit den Prototypen des zweiten Sektors fortgesetzt. Zu beachten ist, dass, weil – wie bereits zuvor erwähnt – Max den maximal in dem neuronalen System 200 codierbaren Abstand darstellt, alle Abstände, die notwendigerweise kleiner als dieser oder gleich diesem Wert sind, den Max-Wert bei jeder Abfrage auf der Abstandsposition an dem entsprechenden Speicherplatz in der Ergebnisdatenbank 226 überschreiben.

Gemäß 4g wird der zweite Sektor 222-2, der die Prototypen B4 und B5 enthält, über den Bus 160'' in die ersten beiden Neuronen des KNN geladen. Zu beachten ist, dass in den betreffenden Kategorieregistern die Kategorien jeweils entsprechend geändert worden sind.

Nun beginnt eine neue Übergabe der Eingangsmuster A1 bis A4 an das KNN 120, um sie angesichts des neuen Satzes von Prototypen zu verarbeiten.

Gemäß 4h wird das Eingangsmuster A1 übergeben und die Abstände werden mithilfe der gespeicherten Prototypen B4 und B5 berechnet. Weil diese Abstände größer als die zuvor ermittelten Abstände sind, wird an Speicherplatz 226-1 keine Änderung vorgenommen.

Gemäß 4i führt die Übergabe des Eingangsmusters A2 zu keinerlei Änderung an Speicherplatz 226-2, weil der ermittelte Abstand, d. h. 8, gleich dem zuvor gespeicherten Abstand ist.

Gemäß 4j führt die Übergabe des Eingangsmusters A3 zu einem Abstandswert von 9, der niedriger ist als der zuvor an Speicherplatz 226-3 gespeicherte Wert von 16, welcher somit überschrieben wird. Im Ergebnis dessen beträgt der neue Abstandswert 9 und die neue Kategorie ist 4.

Gemäß 4k führt die Übergabe des Eingangsmusters A4 zu einem Abstandswert von 0, der niedriger ist als der zuvor an Speicherplatz 226-4 gespeicherte Wert von 9, welcher somit überschrieben wird. Im Ergebnis dessen beträgt der neue Abstandswert 0 und die neue Kategorie ist 5.

Das neuronale System 200 ist somit in der Lage, fünf Prototypen zu speichern, dann mit Unterstützung durch ein aus drei Neuronen gebildetes KNN vier Eingangsmuster A1 bis A4 mit diesen fünf Prototypen zu vergleichen, wobei dies lediglich um den Preis des Ladens der Prototypen in zwei Schritten geschieht. Außerdem zeigt die obige Beschreibung deutlich, dass entsprechend einem weiteren Hauptmerkmal der vorliegenden Erfindung die Anzahl q (q = 4) der Abfragen völlig unabhängig von der Anzahl n (n = 3) der Neuronen und von der Anzahl p (p = 5) der Prototypen ist. Daraus folgt, dass die Anzahl verarbeiteter Prototypen viel größer als die Anzahl von Neuronen sein kann. In der Bildverarbeitung sind Experimente durchgeführt worden und haben gezeigt, dass mehr als 106 Prototypen und eine ähnliche Zahl von Abfragen mit einem KNN verarbeitet werden konnten, das aus lediglich 103 physikalischen Neuronen bestand. In diesem Fall betrug die Anzahl s von Sektoren 103.

Obwohl die Beschreibung der bevorzugten Ausführungsart auf ZISC-Neuronen beruht, versteht es sich dennoch, dass die Erfindung mit jedem Elementarprozessor eingesetzt werden kann, der im Einzelbefehls- und Mehrfachdatenmodus arbeitet.


Anspruch[de]
  1. Verbessertes künstliches neuronales Netzwerk, im Weiteren KNN (120') genannt, zum Vergleich einer Menge von q Eingangsmustern mit p Prototypen unter Einsatz eines aus n Neuronen (130) gebildeten ANN, in dem während der Erkennungs-/Klassifizierungsphase die Anzahl von Prototypen größer ist als die Anzahl von n Neuronen und das verbesserte Netzwerk Folgendes umfasst:

    – ein KNN (120), gebildet aus einer Menge von n Neuronen, wobei jedes Neuron über einen Prototypspeicher (140) zur Speicherung eines Prototyps und einen Auswerter (150) verfügt, um auf der Grundlage des Vergleichs zwischen dem an das KNN übergebenen Eingangsmuster und dem im Neuron gespeicherten Prototyp das lokale Ergebnis einer Auswertung zu erzeugen, sodass das KNN während der Erkennungs-/Klassifizierungsphase entsprechend den k spezifizierten Parametern k globale Ergebnisse erzeugt, wobei k gleich oder größer als eins ist;

    – mindestens drei Datenbanken (222, 224, 226): eine erste Datenbank (222) zur Speicherung von p Prototypen, die auf s Sektoren von bis zu n Prototypen verteilt sind, eine zweite Datenbank (224) zur Speicherung der q Eingangsmuster, die an das KNN übergeben werden sollen, und eine dritte Datenbank (226) zur Speicherung von q mal k Werten;

    – Vergleichs- und Aktualisierungsmittel (230), die für den Vergleich der bei der Auswertung erhaltenen Ergebnisse mit den zuvor für dasselbe Eingangsmuster ermittelten Ergebnissen eines früheren Sektors oder mit den bei der Initialisierung bereits vorhandenen Ergebnissen konfiguriert sind, wobei entsprechend einem vordefinierten Kriterium und auf der Grundlage dieses Vergleichs die zuvor gespeicherten Ergebnisse aktualisiert oder nicht aktualisiert werden; und

    – für den Transport ausgelegte Datenbusmittel (160', 160''): Transport der Prototypdaten zum Prototypspeicher (140), Transport der Eingangsmuster zum Auswerter (150) und Transport der Ergebnisdaten vom Auswerter (150) zur dritten Datenbank.
  2. Verbessertes KNN nach Anspruch 1, bei dem die erste, zweite und dritte Datenbank (222, 224, 226) aus Schreib-/Lese-Speichern bestehen.
  3. Verbessertes KNN nach Anspruch 2, bei dem es sich bei der ersten, zweiten und dritten Datenbank (222, 224, 226) um voneinander unabhängige Einheiten handelt.
  4. Verbessertes KNN nach Anspruch 1, das weiter einen Computer (110) umfasst und dadurch ein neuronales System bildet.
  5. Verbessertes KNN nach Anspruch 4, bei dem die erste, zweite und dritte Datenbank (222, 224, 226) einen Teil des RAM-Speichers des Computers bilden.
  6. Verbessertes KNN nach Anspruch 5, das weiter Folgendes umfasst:

    – einen Datenbankblock, der die erste, zweite und dritte Datenbank (222, 224, 226) enthält; und

    – Schnittstellenmittel (210), die für den Datentransfer zwischen dem Computer (110) und dem Datenbankblock ausgelegt sind, um entweder direkt oder indirekt über einen Adresscontroller die Steuersignale zur korrekten Adressierung der Datenbanken und des KNN zu erzeugen.
  7. Verbessertes KNN nach Anspruch 1, bei dem die spezifizierten Parameter einen Abstand umfassen.
  8. Verbessertes KNN nach Anspruch 7, bei dem der Auswerter in jedem Neuron ein Abstandsauswerter ist, der für die Berechnung des Abstandes zwischen dem an das KNN übergebenen Eingabemuster und dem im Neuron gespeicherten Prototyp ausgelegt ist.
  9. Verbessertes KNN nach Anspruch 8, bei dem das vordefinierte Kriterium die Bestimmung des kleinsten Abstandes ist.
  10. Verbessertes KNN nach Anspruch 8, bei dem die spezifizierten Parameter weiter die Kategorie umfassen und bei dem der Auswerter ein Kategorieregister zur Speicherung der zu dem Prototyp gehörigen Kategorie umfasst.
  11. Verfahren zur Erhöhung der Anzahl von Prototypen, die in einem KNN mit einer begrenzten Anzahl von Neuronen verarbeitet werden soll, das die folgenden Schritte umfasst:

    a) Bereitstellung eines KNN (120), gebildet aus einer Menge von n Neuronen (130), wobei jedes Neuron über einen Prototypspeicher (140) zur Speicherung eines Prototyps und einen Auswerter (150) verfügt, um auf der Grundlage des Vergleichs zwischen dem an das KNN übergebenen Eingangsmuster und dem im Neuron gespeicherten Prototyp das lokale Ergebnis einer Auswertung zu erzeugen, sodass das KNN während der Erkennungs-/Klassifizierungsphase entsprechend den k spezifizierten Parametern k globale Ergebnisse erzeugt, wobei k gleich oder größer als eins ist;

    b) Bereitstellung einer ersten Datenbank (222), die die zu verarbeitenden p Prototypen enthält, in der die Anzahl p der Prototypen größer ist als die Anzahl n der Neuronen und die die p Prototypen auf s Sektoren verteilt und jeder Sektor bis n Prototypen enthält;

    c) Bereitstellung einer zweiten Datenbank (224), die die q Eingangsmuster enthält, die dem KNN übergeben werden sollen;

    d) Bereitstellung einer dritten Datenbank, die die q mal k Werte aus der Auswertung speichern kann;

    e) Laden eines Sektors i von Prototypen, die im Prototypspeicher (140) der n Neuronen (130) verarbeitet werden sollen, wobei i von 1 bis s variiert;

    f) Übergeben eines Eingangsmusters mit dem Rang j an das KNN zur Auswertung, wobei j von 1 bis q variiert;

    g) Vergleichen der für ein Eingangsmuster erhaltenen Ergebnisse mit den zuvor für ein Eingangsmuster desselben Ranges gespeicherten Ergebnissen oder mit den bei der Initialisierung gespeicherten Werten, und je nach Ausgang des Vergleichs Speicherung oder keine Speicherung der Ergebnisse an dem entsprechenden Speicherplatz in der dritten Datenbank (226);

    h) Wiederholen der Schritte f) und g), bis alle Eingangsmuster an das KNN übergeben wurden;

    i) Wiederholen der Schritte e) bis h), bis alle Sektoren geladen wurden, sodass am Ende des Auswertungsprozesses die Endergebnisse in der Datenbank (226) enthalten sind.
  12. Verfahren nach Anspruch 11, bei dem die spezifizierten Parameter einen Abstand und eine Kategorie umfassen und die vordefinierten Kriterien die Bestimmung des kleinsten Abstandes umfassen, sodass die Endergebnisse für jedes Eingangsmuster aus dem kleinsten Abstand und der zugehörigen Kategorie bestehen.
Es folgen 15 Blatt Zeichnungen






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com