Bedeutung (und Beweis) von "RNN kann jeden Algorithmus approximieren"

Kürzlich habe ich gelesen, dass ein wiederkehrendes neuronales Netzwerk jeden Algorithmus approximieren kann.

Meine Frage lautet also: Was bedeutet das genau und können Sie mir einen Hinweis geben, wo dies bewiesen ist?

Hintergrund

Wir müssen zuerst einige Konzepte aus der Berechnungstheorie durchgehen. Ein Algorithmus ist eine Prozedur zum Berechnen einer Funktion. Bei gegebener Eingabe muss der Algorithmus die korrekte Ausgabe in einer endlichen Anzahl von Schritten erzeugen und dann beenden. Zu sagen, dass eine Funktion berechenbar ist, bedeutet, dass ein Algorithmus zur Berechnung vorhanden ist. Unter der unendlichen Menge aller Funktionen sind die meisten nicht berechenbar. Turingmaschinen sind ein mathematisches Modell, das den Begriff der Berechnung formalisiert. Es gibt andere gleichwertige Modelle, aber Turing-Maschinen sind das Standard-Referenzmodell. Nach der Church-Turing-TheseJeder Algorithmus kann von einer Turing-Maschine implementiert werden, und alle berechenbaren Funktionen können auf diese Weise berechnet werden. Eine bestimmte Instanz einer Turing-Maschine berechnet nur eine bestimmte Funktion. Es gibt jedoch eine spezielle Klasse von Turingmaschinen, die als universelle Turingmaschinen bezeichnet werden und mit denen jede andere Turingmaschine für jede Eingabe simuliert werden kann. Sie tun dies, indem sie eine Beschreibung der zu simulierenden Maschine (und ihrer Eingabe) als Teil ihrer eigenen Eingabe nehmen. Jede bestimmte Instanz einer Universal Turing-Maschine kann daher eine beliebige berechenbare Funktion berechnen (dh einen beliebigen Algorithmus implementieren). Jedes System, das diese Fähigkeit teilt, wird als vollständig bezeichnet. Ein Weg, um zu beweisen, dass ein System vollständig ist, besteht darin, zu zeigen, dass es eine universelle Turing-Maschine simulieren kann. Es hat sich gezeigt, dass viele Systeme vollständig sind (z. B. die meisten Programmiersprachen, bestimmte zellulare Automaten und die Quantenmechanik ).

Wiederkehrende neuronale Netze

Das folgende Papier zeigt, dass es für jede berechenbare Funktion ein endliches rekurrentes neuronales Netzwerk (RNN) gibt, das es berechnen kann. Darüber hinaus gibt es endliche RNNs, die vollständig sind und daher jeden Algorithmus implementieren können.

Siegelmann und Sontag (1992) . Zur Rechenleistung neuronaler Netze

Sie verwenden Netzwerke mit einer begrenzten Anzahl von wiederkehrenden verbundenen Einheiten, die zu jedem Zeitpunkt externe Eingaben erhalten. Der Zustand jeder Einheit wird durch eine gewichtete Summe ihrer Eingänge (plus einer Vorspannung) angegeben, die durch eine nichtlineare Aktivierungsfunktion laufen. Die Aktivierungsfunktion ist eine gesättigte lineare Funktion, die eine stückweise lineare Approximation eines Sigmoid darstellt. Die Gewichte und Vorspannungen sind festgelegt, sodass kein Lernen stattfindet.

Das Netzwerk führt eine Zuordnung von einer binären Eingabesequenz zu einer binären Ausgabesequenz durch. Das Netzwerk verfügt über zwei externe Eingänge, die allen Einheiten zugeführt werden: eine Datenleitung und eine Validierungsleitung. Die Datenzeile enthält die Eingabesequenz von Nullen und Einsen und Nullen, nachdem die Eingabesequenz beendet ist. Die Validierungszeile teilt dem Netzwerk mit, wann die Eingabesequenz stattfindet. Es enthält eins für die Dauer der Eingabesequenz und dann null, nachdem es beendet wurde. Eine Einheit wird als "Ausgabeeinheit" betrachtet. Es gibt Nullen für eine willkürliche Verzögerung aus, dann die Ausgabesequenz von Nullen und Einsen und dann Null, nachdem die Ausgabesequenz beendet ist. Eine andere Einheit wird als "Validierungseinheit" angesehen, die uns mitteilt, wann die Ausgabesequenz abläuft.

Obwohl diese RNNs binäre Eingabesequenzen auf binäre Ausgabesequenzen abbilden, sind wir möglicherweise an Funktionen interessiert, die für verschiedene andere mathematische Objekte definiert sind (andere Arten von Zahlen, Vektoren, Bildern, Graphen usw.). Für jede berechenbare Funktion können diese anderen Objekttypen jedoch als Binärsequenzen codiert werden (siehe z. B. hier für eine Beschreibung der Codierung anderer Objekte unter Verwendung natürlicher Zahlen, die wiederum binär dargestellt werden können).

Ergebnis

Sie zeigen, dass es für jede berechenbare Funktion eine endliche RNN (der oben beschriebenen Form) gibt, die sie berechnen kann. Sie tun dies, indem sie zeigen, dass es möglich ist, eine RNN zu verwenden, um einen Pushdown-Automaten mit zwei Stapeln explizit zu simulieren. Dies ist ein weiteres Modell, das einer Turing-Maschine rechnerisch entspricht. Jede berechenbare Funktion kann von einer Turingmaschine berechnet werden. Jede Turingmaschine kann durch einen Pushdown-Automaten mit zwei Stapeln simuliert werden. Jeder Pushdown-Automat mit zwei Stapeln kann von einer RNN simuliert werden. Daher kann jede berechenbare Funktion von einer RNN berechnet werden. Da einige Turing-Maschinen universell sind, sind die RNNs, die sie simulieren, vollständig und können daher jeden Algorithmus implementieren. Insbesondere zeigen sie, dass es Turing-komplette RNNs mit 1058 oder weniger Einheiten gibt.

Andere Konsequenzen

Eine interessante Konsequenz der Simulationsergebnisse ist, dass bestimmte Fragen zum Verhalten von RNNs nicht entschieden werden können. Dies bedeutet, dass es keinen Algorithmus gibt, der sie für beliebige RNNs beantworten kann (obwohl sie im Fall bestimmter RNNs möglicherweise beantwortbar sind ). Zum Beispiel ist die Frage, ob eine gegebene Einheit jemals den Wert 0 annimmt, unentscheidbar. Wenn man diese Frage allgemein beantworten könnte, wäre es möglich, das Stillstandsproblem für Turing-Maschinen zu lösen , das nicht zu entscheiden ist.

Rechenleistung

In der obigen Abhandlung sind alle Netzwerkparameter und -zustände rationale Zahlen. Dies ist wichtig, da es die Leistung der RNNs einschränkt und die resultierenden Netzwerke realistischer macht. Der Grund dafür ist, dass die Rationen berechenbare Zahlen sind , was bedeutet, dass es einen Algorithmus gibt, mit dem sie mit beliebiger Genauigkeit berechnet werden können. Die meisten reellen Zahlen sind nicht berechenbar und daher nicht zugänglich - selbst die leistungsstärkste Turing-Maschine kann sie nicht darstellen, und viele Menschen bezweifeln, dass sie sogar in der physischen Welt dargestellt werden könnten. Wenn wir auf digitalen Computern mit "reellen Zahlen" arbeiten, greifen wir auf eine noch kleinere Teilmenge zu (z. B. 64-Bit- Gleitkommazahlen ). Die Darstellung beliebiger reeller Zahlen würde unendliche Informationen erfordern.

Das Papier besagt, dass der Netzwerkzugriff auf reale Zahlen die Rechenleistung über Turing-Maschinen hinaus noch weiter steigern würde. Siegelmann hat eine Reihe anderer Artikel verfasst, die sich mit dieser "Super-Turing" -Fähigkeit befassen. Es ist jedoch wichtig anzumerken, dass dies mathematische Modelle sind und die Ergebnisse nicht bedeuten, dass eine solche Maschine tatsächlich in der physischen Welt existieren könnte. Es gibt gute Gründe zu der Annahme, dass dies nicht möglich ist, obwohl dies eine offene Frage ist.

Ich denke, das ist was du suchst. Dieser Typ hat bewiesen, dass ein mehrschichtiges oder sogar ein einschichtiges Feedforward-Netzwerk jede Funktion annähern kann, vorausgesetzt, das Netz verfügt über genügend versteckte Einheiten.

Hornik, K. (1991). Approximationsfähigkeiten von mehrschichtigen Feedforward-Netzwerken. Neuronale Netze, 4 (2), 251–257.