Einführung
Dies ist der erste Beitrag in einer Reihe von Beiträgen, die sich mit der Implementierung von künstlichen neuronalen Netzen (ANN) beschäftigen. Der Artikel soll dem Leser helfen, ein Gefühl für die grundlegenden Konzepte zu bekommen, bevor er zu den folgenden algorithmischen Implementierungen übergeht.

Es werden keine Vorkenntnisse vorausgesetzt, obwohl im Interesse der Kürze nicht alle Begriffe in diesem Artikel erklärt werden. Stattdessen werden Hyperlinks zu Wikipedia und anderen Quellen angegeben, wo zusätzliche Lektüre erforderlich sein könnte.

Das Thema ist groß. ANNs haben eine Vielzahl von Anwendungen und können für überwachtes, unbeaufsichtigtes, halbüberwachtes und verstärkendes Lernen eingesetzt werden. Und das, bevor man zu den problemspezifischen Architekturen innerhalb dieser Kategorien kommt. Aber irgendwo müssen wir ja anfangen, und um den Bereich einzugrenzen, beginnen wir mit der Anwendung von ANNs auf ein einfaches Problem.

Das XOr-Problem
Das XOr-Problem oder „Exklusiv-oder“-Problem ist ein klassisches Problem der ANN-Forschung. Es ist das Problem der Verwendung eines neuronalen Netzes zur Vorhersage der Ausgaben von XOr-Logikgattern bei zwei binären Eingaben. Eine XOr-Funktion sollte einen wahren Wert zurückgeben, wenn die beiden Eingaben nicht gleich sind, und einen falschen Wert, wenn sie gleich sind. Alle möglichen Eingaben und vorhergesagten Ausgaben sind in Abbildung 1 dargestellt.

XOr ist ein Klassifizierungsproblem und eines, bei dem die erwarteten Ausgaben im Voraus bekannt sind. Oberflächlich betrachtet scheint XOr ein sehr einfaches Problem zu sein, aber Minksy und Papert (1969) haben gezeigt, dass dies ein großes Problem für neuronale Netzwerkarchitekturen der 1960er Jahre war, die als Perceptrons bekannt sind.

Perceptrons
Wie alle ANNs besteht das Perceptron aus einem Netzwerk von Einheiten, die biologischen Neuronen ähneln. Eine Einheit kann eine Eingabe von anderen Einheiten erhalten. Dabei nimmt sie die Summe aller empfangenen Werte und entscheidet, ob sie ein Signal an andere Einheiten, mit denen sie verbunden ist, weiterleitet. Dies wird als Aktivierung bezeichnet. Die Aktivierungsfunktion reduziert die Summe der Eingangswerte auf eine 1 oder eine 0 (oder einen Wert, der sehr nahe an einer 1 oder 0 liegt), um die Aktivierung oder das Fehlen einer solchen darzustellen. Eine andere Art von Einheit, die so genannte Bias-Einheit, ist immer aktiv und sendet in der Regel eine fest kodierte 1 an alle Einheiten, mit denen sie verbunden ist.

Perceptrons umfassen eine einzige Schicht von Eingabeeinheiten – einschließlich einer Bias-Einheit – und eine einzige Ausgabeeinheit (siehe Abbildung 2). Eine Bias-Einheit ist hier durch einen gestrichelten Kreis dargestellt, während andere Einheiten als blaue Kreise dargestellt sind. Es gibt zwei Nicht-Bias-Eingangseinheiten, die die beiden binären Eingangswerte für XOr darstellen. Es kann eine beliebige Anzahl von Eingabeeinheiten enthalten sein.

Das Perzeptron ist eine Art von Feed-Forward-Netzwerk, was bedeutet, dass der Prozess der Erzeugung einer Ausgabe – bekannt als Vorwärtspropagation – in eine Richtung von der Eingabeschicht zur Ausgabeschicht fließt. Es gibt keine Verbindungen zwischen den Einheiten in der Eingabeschicht. Stattdessen sind alle Einheiten in der Eingabeschicht direkt mit der Ausgabeeinheit verbunden.

Eine vereinfachte Erklärung des Vorwärtspropagationsprozesses ist, dass die Eingabewerte X1 und X2, zusammen mit dem Bias-Wert 1, mit ihren jeweiligen Gewichten W0..W2 multipliziert und zur Ausgabeeinheit analysiert werden. Die Ausgabeeinheit nimmt die Summe dieser Werte und wendet eine Aktivierungsfunktion an – typischerweise die Heavside-Stufenfunktion -, um den resultierenden Wert in eine 0 oder 1 umzuwandeln und so die Eingabewerte als 0 oder 1 zu klassifizieren.

Es ist die Einstellung der Gewichtsvariablen, die dem Autor des Netzes die Kontrolle über den Prozess der Umwandlung von Eingabewerten in einen Ausgabewert gibt. Die Gewichte bestimmen, wo die Klassifizierungslinie, also die Linie, die die Datenpunkte in Klassifizierungsgruppen trennt, gezogen wird. Wenn alle Datenpunkte auf einer Seite einer Klassifizierungslinie der Klasse 0 zugeordnet werden, werden alle anderen als 1 klassifiziert.

Eine Einschränkung dieser Architektur ist, dass sie nur in der Lage ist, Datenpunkte mit einer einzigen Linie zu trennen. Das ist unglücklich, weil die XOr-Eingänge nicht linear trennbar sind. Dies wird besonders deutlich, wenn man die XOr-Eingangswerte in ein Diagramm einträgt. Wie in Abbildung 3 zu sehen ist, gibt es keine Möglichkeit, die Vorhersagen 1 und 0 mit einer einzigen Klassifizierungslinie zu trennen.

Multilayer Perceptrons
Die Lösung für dieses Problem besteht darin, über die einschichtige Architektur hinauszugehen, indem eine zusätzliche Schicht von Einheiten ohne direkten Zugang zur Außenwelt hinzugefügt wird, die so genannte versteckte Schicht. Bei dieser Art von Architektur – in Abbildung 4 dargestellt – handelt es sich um ein weiteres Feed-Forward-Netz, das als mehrschichtiges Perzeptron (MLP) bekannt ist.

Es ist erwähnenswert, dass ein MLP eine beliebige Anzahl von Einheiten in seiner Eingabe-, versteckten und Ausgabeschicht haben kann. Es kann auch eine beliebige Anzahl von versteckten Schichten geben. Die hier verwendete Architektur wurde speziell für das XOr-Problem entwickelt.

Ähnlich wie beim klassischen Perzeptron beginnt die Vorwärtspropagation damit, dass die Eingabewerte und die Bias-Einheit aus der Eingabeschicht mit ihren jeweiligen Gewichten multipliziert werden, allerdings gibt es in diesem Fall ein Gewicht für jede Kombination aus Eingabe (einschließlich der Bias-Einheit der Eingabeschicht) und versteckter Einheit (ohne die Bias-Einheit der versteckten Schicht). Die Produkte aus den Werten der Eingabeschicht und ihren jeweiligen Gewichten werden als Eingabe für die nicht vorgespannten Einheiten in der verborgenen Schicht analysiert. Jede versteckte Einheit ohne Vorspannung ruft eine Aktivierungsfunktion auf – im Falle des XOr-Problems in der Regel die klassische Sigmoidfunktion -, um die Summe ihrer Eingabewerte auf einen Wert zwischen 0 und 1 zu reduzieren (in der Regel einen Wert, der sehr nahe an 0 oder 1 liegt). Die Ausgänge der einzelnen Einheiten der versteckten Schicht, einschließlich der Bias-Einheit, werden dann mit einer anderen Gruppe von entsprechenden Gewichten multipliziert und an eine Ausgabeeinheit weitergeleitet. Die Ausgabeeinheit analysiert ebenfalls die Summe ihrer Eingabewerte durch eine Aktivierungsfunktion – auch hier ist die Sigmoidfunktion geeignet – um einen Ausgabewert zwischen 0 und 1 zu erhalten. Dies ist die vorhergesagte Ausgabe.

Diese Architektur ist zwar komplexer als die des klassischen Perzeptron-Netzwerks, kann aber eine nichtlineare Trennung erreichen. Mit dem richtigen Satz von Gewichtungswerten kann es also die notwendige Trennung liefern, um die XOr-Eingaben genau zu klassifizieren.

Backpropagation
Das Problem ist natürlich, wie man einen Satz von Gewichtungswerten finden kann, der sicherstellt, dass das Netz die erwartete Ausgabe produziert. In der Praxis wäre der Versuch, manuell einen akzeptablen Satz von Gewichten für ein MLP-Netz zu finden, eine unglaublich mühsame Aufgabe. In der Tat ist sie NP-komplett (Blum und Rivest, 1992). Glücklicherweise ist es jedoch möglich, durch einen als Backpropagation bekannten Prozess automatisch einen guten Satz von Gewichtungswerten zu erlernen. Dies wurde erstmals von Rumelhart et al. (1985) für das XOr-Problem nachgewiesen.

Der Backpropagation-Algorithmus beginnt mit dem Vergleich des tatsächlichen Wertes, der durch den Vorwärtspropagationsprozess ausgegeben wird, mit dem erwarteten Wert und bewegt sich dann rückwärts durch das Netzwerk, wobei jedes der Gewichte leicht in eine Richtung angepasst wird, die die Größe des Fehlers um einen kleinen Grad reduziert. Sowohl die Vorwärts- als auch die Rückwärtspropagation werden für jede Eingabekombination tausende Male wiederholt, bis das Netz die erwartete Ausgabe der möglichen Eingaben mit Hilfe der Vorwärtspropagation genau vorhersagen kann.

Für das xOr-Problem stehen 100 % der möglichen Datenbeispiele zur Verfügung, die im Trainingsprozess verwendet werden. Wir können daher davon ausgehen, dass das trainierte Netzwerk in seinen Vorhersagen 100% genau ist, und es besteht keine Notwendigkeit, sich mit Problemen wie Verzerrung und Varianz im resultierenden Modell zu befassen.

Abschluss
In diesem Beitrag wurde das klassische ANN XOr-Problem untersucht. Das Problem selbst wurde ausführlich beschrieben, ebenso wie die Tatsache, dass die Eingaben für XOr nicht linear in ihre korrekten Klassifikationskategorien trennbar sind. Eine nichtlineare Lösung – mit einer MLP-Architektur – wurde auf hohem Niveau untersucht, zusammen mit dem Vorwärtspropagationsalgorithmus, der verwendet wird, um einen Ausgabewert aus dem Netzwerk zu generieren, und dem Backpropagationsalgorithmus, der verwendet wird, um das Netzwerk zu trainieren.

Der nächste Beitrag in dieser Serie wird eine Java-Implementierung der hier beschriebenen MLP-Architektur vorstellen, einschließlich aller Komponenten, die erforderlich sind, um das Netzwerk zu trainieren, damit es als logisches Gatter für XOr fungiert.

Blum, A. Rivest, R. L. (1992). Das Training eines neuronalen Netzes mit 3 Knoten ist NP-komplett. Neural Networks, 5(1), 117-127.