🤖 machine learning

EM-NeSy: Expectation Maximization for Neurosymbolic Learning

Dieses Paper stellt EM-NeSy vor, ein neuartiges neurosymbolisches Lernframework, das den Expectation-Maximization-Algorithmus nutzt, um ein skalierbares und effizientes Training zu ermöglichen, ohne dass die symbolische Komponente differenzierbar sein muss, wodurch sowohl exakte als auch approximative Schlussfolgerungen unterstützt werden.

Ursprüngliche Autoren: Annegret Seibt, Luc De Raedt, Giuseppe Marra

Veröffentlicht 2026-06-15

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Annegret Seibt, Luc De Raedt, Giuseppe Marra

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

Das große Ganze: Einem Roboter das Denken und Schlussfolgern beibringen

Stellen Sie sich vor, Sie versuchen, einem Roboter zwei Dinge gleichzeitig beizubringen:

Wahrnehmung: Wie er ein verschwommenes Foto betrachtet und errät, welche Objekte darauf zu sehen sind (wie das Erkennen einer handgeschriebenen Zahl). Dies geschieht durch ein Neuronales Netz (der „neuronale“ Teil).
Schlussfolgerung (Reasoning): Wie er prüft, ob diese Objekte gemäß einem Satz von Regeln zusammen Sinn ergeben (wie die Prüfung, ob ein Sudoku-Rätsel gültig ist). Dies geschieht durch Symbolische Logik (der „symbolische“ Teil).

Aktuelle Methoden versuchen, diese beiden Teile gleichzeitig zu lehren, indem sie sie mit einem „Kabel“ verbinden, das es dem Roboter ermöglicht, aus seinen Fehlern zu lernen. Dieses Kabel hat jedoch ein Problem: Wenn der Logikteil zu komplex ist oder eine Methode verwendet, die nicht gut mit der Mathematik harmoniert (wie zufälliges Sampling), bricht das „Kabel“. Der Roboter kann nicht lernen, weil er nicht die exakte Richtung berechnen kann, um seine Fehler zu korrigieren.

EM-NESY ist ein neuer Weg, dem Roboter dies beizubringen, der dieses „Kabel“ vollständig entfernt. Anstatt zu versuchen, die beiden Teile während des Lernprozesses ständig miteinander kommunizieren zu lassen, erlaubt es ihnen, sich abzuwechseln.

Die Analogie: Der Kunstkritiker und der Lehrling

Um zu verstehen, wie EM-NESY funktioniert, stellen Sie sich einen Lehrlings-Künstler (das Neuronale Netz) und einen strengen Kunstkritiker (die Symbolische Logik) vor.

Der alte Weg (End-to-End-Lernen)

Bei der alten Methode malt der Lehrling ein Bild, und der Kritiker schreit sofort: „Das ist falsch!“ Der Kritiker versucht dann zu erklären, genau welcher Pinselstrich falsch war und wie man ihn korrigiert.

Das Problem: Wenn die Regeln des Kritikers zu kompliziert sind (wie ein komplexes Sudoku-Rätsel) oder wenn der Kritiker eine Methode verwendet, die schwer Schritt für Schritt zu erklären ist (wie das zufällige Raten), bleibt der Kritiker stecken. Er kann keine spezifischen Anweisungen geben, wie die Pinselstriche zu korrigieren sind. Der Lehrling ist verwirrt und kann sich nicht verbessern.

Der neue Weg (EM-NESY)

EM-NESY ändert den Arbeitsablauf in zwei deutliche Schritte, wie einen Probenprozess:

Schritt 1: Die Rezension des Kritikers (Der „Expectation“-Schritt)
Der Lehrling malt ein Bild basierend auf seinem aktuellen Können. Der Kritiker betrachtet das Bild und die richtige Antwort (das Label).
Anstatt zu versuchen zu erklären, wie die Pinselstriche zu korrigieren sind, schreibt der Kritiker einfach eine Liste von Korrekturen auf.

Beispiel: „Du dachtest, diese Ziffer sei eine 3, aber unter Berücksichtigung der Regeln von Sudoku ist es eigentlich zu 70 % wahrscheinlich eine 5 und zu 30 % wahrscheinlich eine 6.“
Kernpunkt: Der Kritiker macht dies mit jeder beliebigen Methode. Er kann komplexe Mathematik, zufälliges Raten oder strikte Logik verwenden. Es spielt keine Rolle, ob er seine Argumentation Schritt für Schritt erklären kann; er muss nur die endgültige Liste der Wahrscheinlichkeiten (die „Posterior“-Verteilung) produzieren.

Schritt 2: Das Üben des Lehrlings (Der „Maximization“-Schritt)
Der Kritiker übergibt die Liste der Korrekturen an den Lehrling. Der Lehrling betrachtet seine ursprüngliche Vermutung und die Korrekturen des Kritikers.

Der Lehrling denkt: „Ich habe eine 3 vermutet. Der Kritiker sagt, ich hätte eine 5 oder 6 vermuten sollen. Ich muss mein Gehirn so anpassen, dass eine 5 oder 6 beim nächsten Mal wahrscheinlicher wird.“
Der Lehrling aktualisiert seine eigenen internen Einstellungen (die neuronalen Parameter), um der Liste des Kritikers zu entsprechen.
Kernpunkt: Der Kritiker ist in diesem Schritt nicht beteiligt. Die Liste des Kritikers wird als feststehende Tatsache behandelt. Der Lehrling muss nur lernen, wie er seinen eigenen Malstil anpasst.

Warum ist das eine große Sache?

1. Es schaltet „unlernbare“ Logik frei
Einige Logikprobleme sind so schwer, dass man die exakte Antwort nicht berechnen kann oder die Methode zur Findung der Antwort „nicht differenzierbar“ (mathematisch unordentlich) ist.

Analogie: Stellen Sie sich vor, der Kritiker nutzt eine Methode, bei der er Würfel wirft, um die Antwort zu finden. Im alten Weg hätten Sie den Lehrling nicht unterrichten können, weil Sie den Würfelwurf nicht auf die einzelnen Pinselstriche zurückverfolgen konnten.
Mit EM-NESY: Der Kritiker würfelt, erhält ein Ergebnis und schreibt es auf. Der Lehrling lernt einfach aus dem Ergebnis. Der unordentliche Würfelwurf-Teil ist vor dem Lernprozess komplett verborgen.

2. Es ist schneller und verbraucht weniger Speicher
Das Paper zeigt, dass, wenn die Logik einfach genug ist, um exakt berechnet zu werden, diese neue Methode genauso genau ist wie die alte Methode, aber viel schneller.

Analogie: Es ist, als würde man erkennen, dass man nicht die gesamte Geschichte des Universums neu berechnen muss, jedes Mal wenn man einen Fehler macht. Man braucht nur das endgültige Urteil. Dies spart eine enorme Menge an Computer-Speicher und Zeit, was es dem Roboter ermöglicht, viel größere Rätsel zu lösen (wie Sudoku-Gitter mit 100 Ziffern), die die alten Systeme zum Absturz gebracht hätten.

3. Es funktioniert mit jedem „Kritiker“
Da der Kritiker nicht mathematisch „glatt“ oder differenzierbar sein muss, können Sie jede bestehende Logik-Engine einsetzen, selbst jene, die zuvor zu schwierig für die Verwendung mit neuronalen Netzen waren.

Was die Experimente zeigten

Die Autoren testeten dies an drei Arten von Rätseln:

Händisches Schreiben von Zahlen: Sie zeigten, dass EM-NESY riesige Summen (100 Ziffern) bewältigen konnte, die andere Methoden nicht einmal beenden konnten, während es weniger Speicher verbrauchte.
Visuelles Sudoku: Sie zeigten, dass es von Rätseln lernen konnte, bei denen die Regeln streng waren, selbst wenn Näherungsverfahren (wie zufälliges Sampling) zur Lösung des Logikteils verwendet wurden.
Pfadfindung auf einer Karte: Sie zeigten, dass es lernen konnte, den kürzesten Pfad auf einem Gitter zu finden – eine Aufgabe, bei der andere Methoden Schwierigkeiten hatten, weil die Logik zu komplex war, um differenzierbar zu sein.

Das Fazっon

Das Paper schlägt EM-NESY vor, ein Framework, das Neurosymbolisches Lernen als ein Spiel von „Heiß und Kalt“ behandelt, das abwechselnd gespielt wird.

Zug 1: Die Logik-Engine (Kritiker) findet heraus, was die korrekten Antworten hätten sein sollen, und zwar mit den Werkzeugen, die sie hat.
Zug 2: Die neuronale Engine (Lehrling) passt ihr Gehirn an diese Antworten an.

Dieser einfache Wechsel ermöglicht es der KI, aus komplexer, unordentlicher oder approximativer Logik zu lernen, ohne die Logik mathematisch perfekt oder differenzierbar machen zu müssen. Dies macht den Aufbau von KI, die sowohl „sehen“ als auch „denken“ kann, wesentlich flexibler und skalierbarer.

Technisches Resümee: EM-NESY: Expectation-Maximization für neurosymbolisches Lernen

Problemstellung

Neurosymbolische (NeSy) Modelle zielen darauf ab, die perzeptiven Stärken neuronaler Netze mit den Argumentationsfähigkeiten symbolischer Logik zu integrieren. Während hochmoderne NeSy-Modelle typischerweise ein End-to-End-Training durch Backpropagation durch sowohl neuronale als auch symbolische Komponenten anstreben, stößt dieser Ansatz auf erhebliche Herausforderungen, wenn die symbolische Komponente auf approximativer Inferenz basiert.

Exakte probabilistische Inferenz ist oft #P-hart und rechnerisch unpraktikabel für komplexe Aufgaben. Infolgeddessen greifen viele Systeme auf Methoden der approximativen Inferenz zurück (z. B. Sampling, Belief Propagation oder Lineare-Programmierung-Relaxationen). Diese Methoden führen jedoch zu Differenzierbarkeitsproblemen:

Nicht-Differenzierbarkeit: Techniken wie Sampling sind inhärent nicht differenzierbar und erfordern spezialisierte Gradientenschätzer (z. B. REINFORCE) oder Reparametrisierungstricks.
Rechenaufwand: Selbst theoretisch differenzierbare iterative Methoden (z. B. Belief Propagation) werden in der Praxis aufgrund des massiven Rechengraph-Aufwands, der erforderlich ist, um durch alle Iterationen zu backpropagieren, unpraktikabel.

Derzeitige Lösungen erfordern oft inferenzspezifische Modifikationen, um Differenzierbarkeit zu gewährleisten, was die Flexibilität und Skalierbarkeit von NeSy-Systemen einschränkt.

Methodik: EM-NeSy

Die Autoren schlagen EM-NeSy vor, ein Lernframework, das das probabilistische NeSy-Lernen als Instanz des Expectation-Maximization (EM) Algorithmus betrachtet. Diese Formulierung entkoppelt den symbolischen Inferenzprozess von der Gradientenberechnung, wodurch die Verwendung jeder beliebigen Inferenz-Engine (exakt oder approximativ, differenzierbar oder nicht differenzierbar) ermöglicht wird.

Das Framework

Das NeSy-Modell wird als latentes Variablenmodell behandelt, bei dem:

$X$ : Subsymbolischer Input (z. B. Bilder).
$Z$ : Latente symbolische Variablen (neuronal vorhergesagt).
$Y$ : Ziel-symbolische Ausgabe (z. B. die Gültigkeit eines Sudoku-Gitters).
$\theta$ : Parameter des neuronalen Netzes.

Der Lernprozess wechselt zwischen zwei Schritten:

E-Schritt (Expectation):
Die symbolische Komponente berechnet die Posterior-Verteilung der latenten Variablen $Z$ , bedingt auf der beobachteten Beschriftung $Y$ und dem Input $X$ :
$p(z|y, x, \theta) = \frac{p_{Ne}(z|x, \theta)p_{Sy}(y|z)}{p(y|x, \theta)}$
Hierbei ist $p_{Ne}$ der neuronale Prior und $p_{Sy}$ die symbolische Likelihood. Entscheidend ist, dass dieser Schritt als „probabilistischer Korrektor“ fungiert, der weiche oder harte Labels für $Z$ basierend auf Hintergrundwissen abduziert. Dieser Schritt kann durch jede beliebige symbolische Inferenz-Engine (exakt, approximativ, sampling-basiert) durchgeführt werden, ohne dass Differenzierbarkeit erforderlich ist.
M-Schritt (Maximization):
Die neuronalen Parameter $\theta$ werden aktualisiert, indem die Kreuzentropxie zwischen dem neuronalen Prior $p_{Ne}(z|x, \theta)$ und dem im E-Schritt berechneten Posterior $\ell(z)$ minimiert wird:
$L_{EM-NeSy}(\theta) = -\sum_{z \in R(Z)} \ell(z) \log p_{Ne}(z|x, \theta)$
Gradienten werden nur durch die neuronale Komponente zurückpropagiert, wobei der Posterior $\ell(z)$ als Konstante behandelt wird. Dies eliminiert die Notwendigkeit, durch den symbolischen Inferenzprozess zu differenzieren.

Theoretische Äquivalenz

Die Autoren beweisen, dass unter exakter Inferenz die durch EM-NeSy berechneten Gradienten mathematisch äquivalent zu denen eines Standard-End-to-End-differenzierbaren NeSy-Lernens sind (Theorem 3.1). Somit stellt EM-NeSy den Standardfall wieder her, wenn exakte Inferenz machbar ist, bietet jedoch einen deutlichen Vorteil, wenn dies nicht der Fall ist.

Varianten und Erweiterungen

Hard EM: Verwendet Maximum-A-Posteriori (MAP)-Zuweisungen anstelle von weichen Posterioren.
Multi-M EM: Führt mehrere M-Schritte (Gradienten-Updates) für einen einzigen E-Schritt durch, um die Konvergenz zu beschleunigen, ohne den teuren Posterior neu berechnen zu müssen.
Approximative Inferenz: Das Framework unterstützt nativ sampling-basierte Methoden (z. B. Rejection Sampling, ABC Sampling) sowie iterative Algorithmen (z. B. Belief Propagation) ohne Modifikation.

Wichtigste Beiträge

Umformulierung des NeSy-Lernens: Die Autoren fassen das NeSy-Lernen innerhalb des EM-Frameworks neu zusammen, was die Nutzung fortgeschrittener EM-Varianten (Generalized EM, Stochastic EM, Hard EM) zur verbesserten Flexibilität ermöglicht.
Differenzierbarkeitsfreie Integration: Es wird ein allgemeines Framework vorgeschlagen, das jede probabilistische Inferenz-Engine in ein NeSy-Modell integriert, ohne dass der symbolische Inferenzprozess differenzierbar sein muss.
Skalierbarkeit und Effizienz: Der Ansatz zeigt, dass NeSy-Lernen Aufgaben skalieren kann, bei denen exakte Inferenz unpraktikabel ist oder bei denen die Differenzierung durch iterative Solver rechentechnisch prohibitiv wäre.

Experimentelle Ergebnisse

Die Autoren evaluierten EM-NeSy auf drei Benchmarks: MNISTAdd (Addition von handgeschriebenen Ziffern), Visual Sudoku und Warcraft Path-Planning.

Exakte Inferenz (MNISTAdd): EM-NeSy erreichte eine Genauigkeit vergleichbar mit dem Standard-End-to-End-differenzierbaren NeSy (BP-std) und DeepStochLog. Es übertraf sie jedoch signifikant in Bezug auf Skalierbarkeit und Effizienz. Während DeepStochLog aufgrund von Wissenskompilations-Limits nicht auf 15 Ziffern skalieren konnte, skalierte EM-NeSy auf 100 Ziffern. Es reduzierte zudem den Spitzenarbeitsspeicher von ~90 GB auf ~35 GB und verkürzte die Trainingszeit.
Approximative/Nicht-differenzierbare Inferenz:
- Visual Sudoku: Standardmäßige differenzierbare Methoden (Scallop, SL) brachen bei 9x9-Gittern zeitlich ab (Timeout). EM-NeSy, unter Verwendung von Approximate Bayesian Computation (ABC) Sampling, erreichte eine konkurrenzfähige Genauigkeit (53,3 %) bei minimaler Trainingszeit (8,24 Min.), während andere Methoden unanwendbar waren.
- Warcraft Path-Planning: EM-NeSy mit ABC-Sampling erreichte State-of-the-Art-Genauigkeiten (98,80 % bei 12x12, 69,60 % bei 30x30) mit deutlich schnelleren Trainingszeiten im Vergleich zu I-MLE und EXAL.
Beobachtete Limitationen: Die Leistung von EM-NeSy hängt von der Qualität des approximativen Posteriors ab. Hard EM (MAP) zeigte Bias bei MNISTAdd, und Loopy Belief Propagation versagte bei 9x9 Sudoku aufgrund der Struktur des Faktorgraphen. ABC-Sampling zeigte eine hohe Varianz bei größeren Instanzen, blieb aber in kleineren Settings effektiv.

Bedeutung und Ansprüche

Das Paper behauptet, dass EM-NeSy ein vereinheitlichtes Lernframework bereitstellt, das das Modelldesign erheblich vereinfacht, indem es die Notwendigkeit für inferenzspezifische Differenzierbarkeits-Modifikationen eliminiert. Durch die Behandlung des NeSy-Lernens als EM-Problem ermöglicht der Ansatz:

Die Verwendung jeder beliebigen symbolischen Inferenz-Engine, einschließlich spezialisierter, optimierter oder nicht-differenzierbarer Solver.
Die Wiederherstellung des Standard-End-to-End-Lernens unter exakter Inferenz bei gleichzeitiger Überlegenheit in der Recheneffizienz und Speicherskalierbarkeit.
Die Ermöglichung von NeSy-Systemen für Aufgaben mit komplexen, kombinatorischen Constraints (wie Pfadplanung oder Sudoku), bei denen exakte Inferenz unpraktikabel oder differenzierbare Approximationen schwierig zu konstruieren sind.

Die Autoren kommen zu dem Schluss, dass EM-Neisy zwar das Problem der Auswahl effektiver Approximationen nicht löst (welches weiterhin aufgabenabhängig bleibt), aber die Barriere der Differenzierbarkeit entfernt und somit skalbarere und flexiblere neurosymbolische Systeme ermöglicht.