Im Schneegestöber der Irreführungen
Gibt es denn keine soliden Studien zur Mächtigkeit von KNN? Doch. Aber sie sind schwierig zwischen all den argumentativen Täuschkörpern zu finden. Fündig wird man im Umfeld der Nachvollziehbarkeitsforschung für KNN (verification and interpretation). Die Quellenapparate dieser teils sehr speziellen Studien führen dann zu allgemeineren Beweisen. Ich präsentiere eine kleine Auswahl aus den Dutzenden, teils schwer verdaulichen, wissenschaftlichen Studien, die ich durchgearbeitet habe.
Reale und realisierbare KNNs arbeiten mit beschränkter Präzision bei der Zahlendarstellung der Gewichte – wie erwähnt, sogar mit sehr beschränkter Präzision wie Mini-FLOATs (16 Bit breit) oder µ-FLOATs (8 Bit). Aussagen zur realisierbaren Mächtigkeit von KNN müssen dem Rechnung tragen.
Wir fangen mit zwei aufeinander aufbauenden Arbeiten an, die gut in die Beweismethoden einführen. In der ersten Stufe(öffnet im neuen Fenster) wird mit relativ einfachen Mitteln die Äquivalenz zwischen FF-KNNs mit ReLU- oder Threshold-Aktivierungsfunktionen und (deterministischen) endlichen Automaten nachgewiesen – unter anderem durch die wechselseitige Konstruktion, ein Verfahren, wie ein FA in ein solches KNN abgebildet werden kann und umgekehrt.
Die zweite Stufe(öffnet im neuen Fenster) der Beweisführung generalisiert die Ergebnisse auf nichtdeterministische endliche Automaten (NFA) und weitere Aktivierungsfunktionen. NFA sind genauso mächtig wie deterministische FA(öffnet im neuen Fenster) – sie sind aber eine bessere Beschreibung für KNN, weil sie die parallelisierte Berechnung der Wahrscheinlichkeiten abbilden können.
Bemerkenswert ist allerdings, dass in den Validierungsexperimenten wieder die inhärente Fehlerträchtigkeit von KNN sichtbar wird: Sobald die zu simulierenden NFA etwas komplexer werden, schleichen sich bei dem konstruierten KNN Abweichungen im Verhalten ein. Wir werden bei der Betrachtung der praktischen Grenzen darauf zurückkommen.
Eine weitere Studie anderer Autoren(öffnet im neuen Fenster) befasst sich mit rekurrenten KNN (RNN) samt Gated Recurrent Unit (GRU) – also KNN mit Rückkopplungsschleifen und GRUs. Bei endlicher Präzision für KNN- und GRU-Berechnungen wird auch hier nur die Mächtigkeit eines (deterministischen) endlichen Automaten erreicht.
Also nichts Neues seit Minskys Äquivalenzbeweis zwischen RNN und FA?
Doch: Mit LSTM (Long Short Term Memory) kann gezählt werden, und das geht etwas über endliche Automaten und reguläre Sprachen hinaus – aber die Studie ist IMHO schwer verdaulich, weswegen ich sie auslasse. Stattdessen empfehle ich eine recht zugängliche und aktuellere, aber dennoch anspruchsvolle Arbeit(öffnet im neuen Fenster): Sie untersucht Language Models (LM) mit Chain-of-Thought (CoT) und Transformern. Gleich am Anfang werden in einer Grafik die Kernaussagen zur resultierenden Mächtigkeit zusammengefasst, säuberlich getrennt zwischen fixer und unendlicher Rechenpräzision.
Kurz: Bei fixer Rechenpräzision erreichen sie die Mächtigkeit probabilistischer endlicher Automaten (Probabilistic Finite State Automata – PFSA)(öffnet im neuen Fenster) und können damit probabilistisch-reguläre Sprachen erkennen oder generieren. Diese sind aber immer noch eine echte Teilmenge der kontextfreien Sprachen. PFSAs sind damit zwar etwas mächtiger als endliche Automaten, aber immer noch weniger mächtig als Stackautomaten ᐸ Lineare Automaten ᐸ Turingmaschinen.
- Anzeige Hier geht es zu Künstliche Intelligenz: Wissensverarbeitung bei Amazon Wenn Sie auf diesen Link klicken und darüber einkaufen, erhält Golem eine kleine Provision. Dies ändert nichts am Preis der Artikel.