💻 computer science

Query Languages for Machine-Learning Models

Diese Arbeit untersucht die Anwendung der Prädikatenlogik erster Ordnung mit Summation (FO(SUM)) und ihrer rekursiven Erweiterung IFP(SUM) als Abfragesprachen für neuronale Netze, die als gewichtete Graphen dargestellt sind, wobei illustrative Beispiele präsentiert und deren Ausdrucksstärke sowie Komplexität analysiert werden.

Ursprüngliche Autoren: Martin Grohe

Veröffentlicht 2026-01-15

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Martin Grohe

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie besitzen eine riesige, komplexe Maschine für maschinelles Lernen, wie etwa ein neuronales Netz. Für einen Informatiker ist dies ein „gewichteter Graph“ – ein Geflecht aus Knoten (Neuronen), die durch Linien (Kanten) verbunden sind, wobei jeder Linie eine bestimmte Zahl (ein Gewicht) zugeordnet ist.

Der Autor dieser Arbeit, Martin Grohe, stellt eine einfache, aber tiefgreifende Frage: Wie können wir Fragen an diese Maschinen stellen?

Normalerweise füttern wir ein neuronales Netz einfach mit Daten und erhalten eine Antwort. Aber was, wenn wir fragen wollen: „Wie viele Verbindungen hat dieses Netzwerk?“ oder „Wenn ich diesen spezifischen Draht entferne, ändert sich dann das Ergebnis?“ oder sogar: „Was ist die gesamte Fläche unter der Kurve des Outputs dieses Netzwerks?“

Um diese Fragen zu beantworten, schlägt das Paper zwei spezielle „Sprachen“ (Logiken) vor, die speziell dafür entwickelt wurden, mit diesen gewichteten Maschinen zu kommunizieren. Betrachten Sie diese Sprachen als eine Art Fernbedienung für neuronale Netze.

Hier ist eine Aufschlüsselung der beiden Sprachen und dessen, was sie leisten können, unter Verwendung einfacher Analogien:

1. Die erste Sprache: FO(SUM)

Die „Zähl- und Addier-Fernbedienung“

Betrachten Sie FO(SUM) als einen sehr intelligenten Taschenrechner, der in der Lage ist, das Netzwerk zu betrachten und zwei Hauptaufgaben auszuführen:

Umhersehen: Es kann prüfen, ob eine Verbindung existiert (wie die Frage: „Gibt es einen Draht zwischen Knoten A und Knoten B?“).
Dinge aufsummieren: Es besitzt eine spezielle „Sum“-Taste. Es kann eine Gruppe von Dingen finden (wie alle Dreiecke in einem Netzwerk) und deren Gewichte zusammenzählen.

Was es kann:

Zählen: Es kann Ihnen genau sagen, wie viele Kanten (Drähte) oder Dreiecke im Netzwerk existieren.
Das Beste finden: Es kann das „leichteste“ oder „schwerste“ Dreieck im Netzwerk finden.
Einfache Netzwerke simulieren: Wenn das neuronale Netz flach ist (nicht sehr tief), kann diese Sprache tatsächlich den Output des Netzwerks für einen bestimmten Input berechnen. Es ist wie die Simulation einer kurzen Domino-Kette.
„Nutzlose“ Drähte finden: Es kann Drähte identifizieren, die, falls man sie entfernt, das Endergebnis nicht verändern würden.

Der Haken (Die Einschränkung):
FO(SUM) ist wie eine Person, die immer nur eine kleine Nachbarschaft zur Zeit betrachten kann. Es hat Schwierigkeiten mit tiefen Netzwerken. Wenn das neuronale Netz viele Schichten hat (eine sehr lange Domino-Kette), verliert sich diese Sprache. Sie kann das Endergebnis eines sehr tiefen Netzwerks nicht ohne Weiteres berechnen, da ihr die Möglichkeit fehlt, während des Prozesses zu „schleifen“ oder Schritte zu „speichern“, während sie tiefer geht.

2. Die zweite Sprache: IFP(SUM)

Die „Rekursive“ Fernbedienung

Um tiefe Netzwerke zu bewältigen, benötigen wir ein mächtigeres Werkzeug. Hier kommt IFP(SUM) ins Spiel.

Dies ist im Grunde die erste Sprache mit einer „Loop“-Taste. In der Informatik nennt man dies einen „Fixpunkt-Operator“. Er ermöglicht der Sprache zu sagen: „Führe diese Berechnung fort, indem du das Ergebnis des letzten Schritts als Input für den nächsten Schritt verwendest, bis du das Ende erreichst.“

Was es kann:

Jede Tiefe bewältigen: Da es Schleifen bilden kann, kann es die Berechnung eines neuronalen Netzes unabhängig von dessen Tiefe oder Komplexität simulieren. Es kann das Signal vom allerersten Input bis zum finalen Output verfolgen.
Komplexe Mathematik: Es kann die schweren Rechenarbeiten leisten, die erforderlich sind, um die Funktion des Netzwerks zu evaluieren.

Der Haken (Die Einschränkung):
Obwohl IFP(SUM) mächtig ist, hat es eine Geschwindigkeitsbegrenzung.

Das „Explosions-Problem“: Wenn man nicht vorsichtig ist, können die Zahlen, die es berechnet, astronomisch groß werden (wie das wiederholte Quadrieren einer Zahl). Um dies zu beheben, führt das Paper eine „sichere“ Version namens sIFP(SUM) ein, die verhindert, dass die Zahlen zu schnell wachsen, um sicherzustellen, dass die Berechnung in einer angemessenen Zeit abgeschlossen wird.
Nicht alles ist möglich: Selbst mit dieser mächtigen Fernbedienung gibt es Fragen, die es nicht beantworten kann. Zum Beispiel die Frage: „Gibt es irgendeinen Input, der dazu führt, dass dieses Netzwerk einen Output ungleich Null liefert?“ – dies ist eine Frage, die selbst für diese Sprache zu schwer ist, um sie effizient zu lösen, obwohl ein Mensch sie theoretisch mit genügend Zeit lösen könnte.

Das große Ganze: „Modell-agnostische“ Fragen

Das Paper diskutiert auch eine spezielle Art von Frage, die als „Modell-agnostisch“ bezeichnet wird.

Stellen Sie sich vor, Sie haben zwei verschiedene neuronale Netze, Netzwerk A und Netzwerk B. Sie sind unterschiedlich aufgebaut (unterschiedliche Anzahl an Neuronen, unterschiedliche Drähte), aber beide erfüllen exakt dieselbe Aufgabe (sie liefern für jeden Input das gleiche Ergebnis).

Eine Modell-agnostische Frage ist eine, bei der die Antwort nur von der Aufgabe abhängt, die das Netzwerk erfüllt, und nicht davon, wie es gebaut ist.
- Beispiel: „Gibt dieses Netzwerk für jeden Input den Wert Null aus?“ (Dies gilt sowohl für A als auch für B, wenn sie dieselbe Aufgabe erfüllen).
Eine Nicht-agnostische Frage hängt von der spezifischen Verdrahtung ab.
- Beispiel: „Wie viele Drähte hat dieses Netzwerk?“ (Netzwerk A könnte 100 haben, Netzwerk B vielleicht 50, selbst wenn sie dieselbe Aufgabe erfüllen).

Die überraschende Erkenntnis:
Das Paper offenbart eine enttäuschende, aber wichtige Wahrheit:

FO(SUM) (die einfache Sprache) ist schlecht darin, Modell-agnostische Fragen über allgemeine Netzwerke zu stellen. Es kann nur triviale Dinge fragen (wie „Ist das Netzwerk leer?“). Es kann nicht sagen, ob ein Netzwerk „immer Null“ ist, es sei denn, das Netzwerk ist sehr flach.
IFP(SUM) (die mächtige Sprache) ist besser, aber selbst es hat Grenzen. Es gibt Fragen darüber, was ein Netzwerk tut, die so komplex sind, dass selbst diese mächtige Sprache sie nicht effizient beantworten kann.

Zusammenfassung

Bei diesem Paper geht es darum, ein Wörterbuch und eine Grammatik zu erstellen, um mit neuronalen Netzen zu kommunizieren.

FO(SUM) ist ein Basis-Wörterbuch, das gut zum Zählen und für einfache Summen geeignet ist, aber sich in tiefen Netzwerken verliert.
IFP(SUM) ist ein Wörterbuch mit einer „Loop“-Funktion, das tiefe Netzwerke bewältigen kann, aber es hat Geschwindigkeitsbegrenzungen und kann dennoch nicht jede Frage beantworten, die man über die Funktion eines Netzwerks stellen kann.

Der Autor kommt zu dem Schluss, dass wir zwar Fortschritte bei der Erstellung dieser Sprachen gemacht haben, es aber immer noch viele Geheimnisse darüber gibt, wie viel wir einem neuronalen Netz tatsächlich über seine eigenen inneren Abläufe „fragen“ können.

Technisches Resümee: Abfragesprachen für maschinelle Lernmodelle

Problemstellung

Die Arbeit befasst sich mit der Herausforderung, maschinelle Lernmodelle (ML-Modelle), insbesondere neuronale Netze, formal zu analysieren und abzufragen. Diese sind inhärent „hybride Modelle“, die diskrete Strukturen (Graph-Topologie) mit kontinuierlichen numerischen Komponenten (Gewichte und Biases) kombinieren. Während die endliche Modelltheorie (Finite Model Theory) erfolgreich relationale Datenbanken und diskrete computationale Probleme analysiert hat, mangelt es Standardlogiken an den Mechanismen zur Handhabung der numerischen Aggregation und Arithmetik, die zur Beschreibung des Verhaltens gewichteter Strukturen wie neuronaler Netze erforderlich sind.

Bestehende Ansätze zur ML-Analyse verlassen sich oft auf feste, generische Erklärungsmethoden (z. B. Kontrafaktuale für spezifische Eingaben) oder behandeln Modelle als Black Boxes. Der Autor plädiert für eine Perspektive, die in der Datenbanktheorie und der endlichen Modelltheorie verwurzelt ist, und schlägt vor, ML-Modelle als Datenstrukturen zu betrachten, die flexiblen, logischen Abfragen unterliegen. Dies ermöglicht die Untersuchung sowohl lokaler Komponentenfunktionalität als auch globaler semantischer Eigenschaften (z. B. Robustheit, Korrektheit oder Integrale über den Funktionsraum), ohne auf spezifische Eingabewertierungen beschränkt zu sein.

Methodik

Die Arbeit untersucht zwei spezifische Logiken, die für gewichtete endliche Strukturen (Strukturen mit einem endlichen Universum und Gewichtfunktionen, die auf erweiterte reelle Zahlen $\mathbb{R}_\perp$ abbilden) entwickelt wurden:

FO(SUM): Prädikatenlogik erster Ordnung, erweitert um einen Summenoperator ( $\sum$ ) und konditionale Terme. Diese Logik ermöglicht die Aggregation von Gewichten über definierbare Mengen innerhalb der Struktur.
IFP(SUM): Die rekursive Erweiterung von FO(SUM) unter Verwendung inflationärer Fixpunktoperatoren. Dies ermöglicht die Definition induktiver Prozesse, die für die Evaluierung neuronaler Netze unbeschränkter Tiefe notwendig sind.

Die Methodik umfasst:

Formalisierung Neuronaler Netwerke: Repräsentation von Feedforward Neural Networks (FNNs) als gewichtete gerichtete azyklische Graphen mit einem spezifischen Vokabular ( $\{wt, bias, \le_{in}, \le_{out}\}$ ).
Definition der Semantik: Etablierung der Semantik dieser Logiken über gewichtete Strukturen, wobei Terme Werte in $\mathbb{R}_\perp$ und Formeln Boole'sche Werte evaluieren.
Expressivitätsanalyse: Bestimmung, welche Eigenschaften von FNNs (z. B. Evaluierung, Parameterzählung, Auffinden nutzloser Kanten, Berechnung von Integralen) in diesen Logiken ausdrückbar sind.
Komplexitätsanalyse: Analyse der Datenkomplexität bei der Evaluierung dieser Abfragen, unter Berücksichtigung sowohl uniformer Schaltkreis-Komplexitätsklassen (z. B. $\mathsf{TC}^0$ ) als auch der Polynomialzeit ( $\mathsf{P}$ ).
Modell-agnostische Abfragen: Untersuchung von Abfragen, deren Ergebnisse ausschließlich von der durch das Netzwerk berechneten Funktion ( $f^N$ ) abhängen und nicht von der spezifischen Architektur oder den Gewichten, wobei zwischen „modell-agnostischen“ und „vollständig modell-agnostischen“ Eigenschaften unterschieden wird.

Zentrale Beiträge und Ergebnisse

1. Expressivität von FO(SUM)

Evaluierung mit beschränkter Tiefe: FO(SUM) kann die Evaluierung von FNNs mit beschränkter Tiefe ausdrücken. Die Logik kann den Wert eines Knotens bis zu einer festen Tiefe $d$ rekursiv über die Summation aggregierter gewichteter Eingaben und konditionale Terme zur Simulation der ReLU-Aktivierungsfunktion definieren.
Globale Eigenschaften: Die Logik kann globale Eigenschaften definieren, wie die Gesamtzahl der Gewichte, die Menge der „nutzlosen“ Kanten (Kanten, deren Entfernung die Ausgabe nicht verändert) und Integrale über die vom Netzwerk berechnete Funktion (via zylindrischer Zellzerlegung stückweise-linearer Funktionen).
Einschränkungen bei unbeschränkter Tiefe: FO(SUM) kann nicht die Evaluierungsfunktion für FNNs unbeschränkter Tiefe ausdrücken. Die Logik ist auf lokale Eigenschaften beschränkt; sie kann nicht die unbeschränkte Rekursion simulieren, die für eine allgemeine FNN-Evaluierung erforderlich ist.
Modell-agnostische Einschränkungen: Ein zentrales negatives Ergebnis (Theorem 3.14) besagt, dass jede FO(SUM)-Aussage, die modell-agnostisch ist (invariant gegenüber verschiedenen Architekturen, die dieselbe Funktion berechnen) auf der Klasse aller FNNs, trivial sein muss (entweder wahr für alle oder falsch für alle). Somit sind nicht-triviale modell-agnostische Abfragen (wie die Prüfung, ob ein Netzwerk überall Null ausgibt) für unbeschränkte Tiefe nicht in FO(SUM) ausdrückbar.
Äquivalenz bei beschränkter Tiefe: Für FNNs mit beschränkter Tiefe ( $N_d(m, 1)$ ) ist FO(SUM) jedoch überraschend leistungsfähig. Theorem 3.18 stellt fest, dass jede in der Prädikatenlogik erster Ordnung über dem geordneten Körper der reellen Zahlen, erweitert um die Funktion $f$ , ausdrückbaren Eigenschaft ( $FO(\mathbb{R}_{lin}, f)$ ) auch in FO(SUM) ausdrückbar ist. Dies wird durch die Simulation der Quantifizierung über reelle Zahlen mittels Quantifizierung über die Zellen der zylindrischen Zerlegung der Funktion erreicht.

2. Expressivität von IFP(SUM)

Unbeschränkte Tiefe: IFP(SUM) überwindet die Tiefenbeschränkung von FO(SUM) durch die Einführung von Fixpunktoperatoren. Es kann die Evaluierungsfunktion für FNNs von unbeschränkter Tiefe ausdrücken (Beispiel 4.1).
Komplexität und Skalar-Fragmente: Während die Standard-Fixpunktlogik über geordneten Strukturen die Polynomialzeit erfasst, steht IFP(SUM) über gewichteten Strukturen vor einer Komplexitätshürde: Terme können exponentiell in ihrer Größe wachsen (z. B. durch wiederholtes Quadrieren). Um dies zu adressieren, führt das Paper das Skalar-Fragment sIFP(SUM) ein, welches Multiplikationen und Divisionen unter Beteiligung von intensionalen Symbolen einschränkt.
- Theorem 4.5: Die Datenkomplexität von sIFP(SUM) liegt in P (Polynomialzeit) über rationale gewichtete Strukturen.
Expressivitätsgrenzen: Trotz der Fähigkeit, die Polynomialzeit im Blum-Shub-Smale-Modell zu erfassen, kann IFP(SUM) (und sIFP(SUM)) nicht alle polynomial-zeit berechenbaren modell-agnostischen Abfragen ausdrücken. Theorem 4.7 zeigt die Existenz einer polynomial-zeit entscheidbaren modell-agnostischen Abfrage auf $N(1, 1)$ , die selbst mit binären Gewichten nicht in IFP(SUM) ausdrückbar ist. Diese Einschränkung resultiert aus der Unfähigkeit der Logik, beliebige Berechnungen auf den numerischen Werten durchzuführen (Mangel an Variablen, die über Zahlen variieren).
Reduzierte FNNs: Das Paper führt „reduzierte FNNs“ ein (Faktorisierung durch eine bisimilaritätsähnliche Äquivalenz). Theorem 4.8 zeigt, dass für FNNs, deren reduzierte Form Gewichte mit beschränkter Bit-Größe besitzt, sIFP(SUM) alle polynomial-zeit entscheidbaren modell-agnostischen Abfragen erfasst.

3. Komplexitätsergebnisse

FO(SUM): Die Datenkomplexität der Evaluierung von FO(SUM)-Ausdrücken liegt in uniform $\mathsf{TC}^0$ (Theorem 3.9). Diese Klasse erlaubt Schwellenwertgatter und iterierte Addition, was für die erforderlichen arithmetischen Operationen ausreicht.
sIFP(SUM): Die Datenkomplexität liegt in P (Theorem 4.5).

Bedeutung und Behauptungen

Das Paper positioniert sich als eine „persönliche Perspektive“ und als ein grundlegender Schritt zur Anwendung der endlichen Modelltheorie auf ML. Seine primäre Bedeutung liegt in:

Formalisierung der ML-Abfrage: Es bietet einen rigorosen logischen Rahmen für das Abfragen der internen Semantik neuronaler Netze und bewegt sich damit weg von der Black-Box-Evaluierung hin zur strukturellen und funktionalen Analyse.
Brückenschlag zwischen Diskret und Kontinuierlich: Es demonstriert, wie Meta-Finite-Modelltheorie (die Erweiterung der endlichen Modelltheorie auf hybride Strukturen) auf neuronale Netze angewendet werden kann, die natürlich als gewichtete Graphen dargestellt werden.
Definition der Grenzen der Expressivität: Die Ergebnisse ziehen klare Grenzen zwischen dem, was logisch ausdrückbar ist und was nicht. Insbesondere wird hervorgehoben, dass während Netzwerke beschränkter Tiefe mittels FO(SUM) einer logischen Analyse zugänglich sind, die unbeschränkte Tiefe eine Komplexität einführt, die Rekursion (IFP) erfordert, aber dennoch grundlegende Barrieren hinsichtlich modell-agnostischer Eigenschaften aufweist.
Komplexitäts-Einblicke: Die Arbeit verbindet logische Expressivität mit der computationalen Komplexität und zeigt, dass selbst mit Fixpunktoperatoren das Erfassen aller polynomial-zeit modell-agnostischen Eigenschaften eine Einschränkung der numerischen Bit-Größe der Gewichte erfordert.

Der Autor schließt mit dem Hinweis, dass trotz erheblicher Fortschritte in [22, 23] viele offene Fragen bestehen, insbesondere hinsichtlich der Erweiterung der Ergebnisse auf beliebige Eingabedimensionen, der Aufhebung der Annahmen beschränkter Tiefe ohne komplexitätstheoretische Annahmen sowie der Inter-Definierbarkeit verschiedener Aggregationsoperatoren. Das Paper beansprucht nicht, das Problem der „Explainable AI“ vollständig zu lösen, bietet aber ein theoretisches Toolkit zur Definition und Analyse spezifischer Arten von Erklärungen und Verifizierungen.