🤖 machine learning

EM-NeSy: Expectation Maximization for Neurosymbolic Learning

Dit artikel introduceert EM-NeSy, een nieuw neurosymbolisch leerframework dat het Expectation-Maximization-algoritme benut om schaalbare en efficiënte training mogelijk te maken zonder dat het symbolische onderdeel differentieerbaar hoeft te zijn, waardoor zowel exacte als benaderende redenering wordt ondersteund.

Oorspronkelijke auteurs: Annegret Seibt, Luc De Raedt, Giuseppe Marra

Gepubliceerd 2026-06-15

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Annegret Seibt, Luc De Raedt, Giuseppe Marra

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Plaatje: Een Robot Leren Denken en Redeneren

Stel je voor dat je een robot probeert twee dingen tegelijk te leren:

Perceptie: Hoe hij naar een wazige foto kijkt en raadt wat de objecten zijn (zoals het herkennen van een handgeschreven cijfer). Dit wordt gedaan door een Neuraal Netwerk (het "neurale" deel).
Redeneren: Hoe hij controleert of die objecten volgens een set regels wel logisch bij elkaar passen (zoals controleren of een Sudoku-puzzel klopt). Dit wordt gedaan door Symbolische Logica (het "symbolische" deel).

Huidige methoden proberen deze twee onderdelen tegelijkertijd te leren door ze met een "draad" met elkaar te verbinden, zodat de robot van zijn fouten kan leren. Echter, deze draad heeft een probleem: als het logische deel te complex is of een methode gebruikt die niet goed samenwerkt met wiskunde (zoals willekeurige bemonstering/sampling), breekt de "draad". De robot kan niet leren omdat hij niet de exacte richting kan berekenen om zijn fouten te herstellen.

EM-NESY is een nieuwe manier om de robot te onderwijzen die deze "draad" volledig verwijdert. In plaats van de twee onderdelen constant met elkaar te laten praten tijdens het leerproces, laat het ze om de beurt aan de beurt komen.

De Analogie: De Kunstcriticus en de Leerling

Om te begrijpen hoe EM-NESY werkt, stel je een Leerling-Artiest (het Neurale Netwerk) en een Strenge Kunstcriticus (de Symbolische Logica) voor.

De Oude Manier (End-to-End Learning)

Bij de oude methode schildert de Leerling een schilderij, en de Criticus roept onmiddellijk: "Dat is fout!" De Criticus probeert vervolgens uit te leggen precies welke penseelstreek fout was en hoe deze te verbeteren.

Het Probleem: Als de regels van de Criticus te ingewikkeld zijn (zoals een complexe Sudoku-puzzel) of als de Criticus een methode gebruikt die moeilijk stap-voor-stap uit te leggen is (zoals willekeurig gokken), loopt de Criticus vast. De Criticus kan niet uitleggen welke specifieke penseelstreken aangepast moeten worden. De Leerling raakt in de war en kan zich niet verbeteren.

De Nieuwe Manier (EM-NESY)

EM-NESY verandert de workflow in twee duidelijke stappen, als een repetitieproces:

Stap 1: De Recensie van de Criticus (De "Expectation" Stap)
De Leerling schildert een beeld op basis van zijn huidige vaardigheidsniveau. De Criticus bekijkt het schilderij en het juiste antwoord (het label).
In plaats van te proberen uit te leggen hoe de penseelstreken verbeterd moeten worden, maakt de Criticus simpelweg een lijst met correcties op.

Voorbeeld: "Je dacht dat dit cijfer een 3 was, maar gegeven de regels van Sudoku is het eigenlijk 70% waarschijnlijk een 5 en 30% waarschijnlijk een 6."
Kernpunt: De Criticus doet dit met elke methode die hij wil. Hij kan complexe wiskunde gebruiken, willekeurig gokken, of strikte logica. Het maakt niet uit of hij zijn redenering stap-voor-stap kan uitleggen; hij hoeft alleen de uiteindelijke lijst met kansen (de "posterior") te produceren.

Stap 2: De Oefening van de Leerling (De "Maximization" Stap)
De Criticus overhandigt de lijst met correcties aan de Leerling. De Leerling kijkt naar zijn oorspronkelijke gok en de correcties van de Criticus.

De Leerling denkt: "Ik gokte een 3. De Criticus zegt dat het een 5 of een 6 had moeten zijn. Ik moet mijn brein aanpassen zodat een 5 of een 6 de volgende keer waarschijnlijker is."
De Leerling past zijn eigen interne instellingen aan (de neurale parameters) om overeen te komen met de lijst van de Criticus.
Kernpunt: De Criticus is in deze stap niet betrokken. De lijst van de Criticus wordt behandeld als een vaststaand feit. De Leerling hoeft alleen maar te leren hoe hij zijn eigen schilderstijl kan veranderen.

Waarom is dit een grote doorbraak?

1. Het ontgrendelt "onleerbare" logica
Sommige logische problemen zijn zo moeilijk dat je het exacte antwoord niet kunt berekenen, of de methode om het antwoord te vinden is "niet-differentieerbaar" (wiskundig rommelig).

Analogie: Stel je voor dat de Criticus een methode gebruikt waarbij hij met dobbelstenen gooit om het antwoord te vinden. In de oude methode kon je de Leerling niet onderwijzen, omdat je de dobbelsteenworp niet kon terugleiden naar de penseelstreken.
Met EM-NESY: De Criticus gooit de dobbelstenen, krijgt een resultaat en schrijft dit op. De Leerling leert simpelweg van het resultaat. Het rommelige deel van het dobbelstenen gooien is volledig verborgen voor het leerproces.

2. Het is sneller en gebruikt minder geheugen
De paper laat zien dat wanneer de logica eenvoudig genoeg is om exact berekend te worden, deze nieuwe methode net zo nauwkeurig is als de oude methode, maar veel sneller.

Analogie: Het is alsof je beseft dat je niet de hele geschiedenis van het universum opnieuw hoeft te berekenen elke keer dat je een fout maakt. Je hebt alleen het definitieve oordeel nodig. Dit bespaart een enorme hoeveelheid computergeheugen en tijd, waardoor de robot veel grotere puzzels kan oplossen (zoals Sudoku-grids met 100 cijfers) die de oude systemen zouden laten crashen.

3. Het werkt met elke "Criticus"
Omdat de Criticus niet wiskundig "glad" of differentieerbaar hoeft te zijn, kun je elke bestaande logische engine erin pluggen, zelfs de engines die voorheen te moeilijk te gebruiken waren met neurale netwerken.

Wat de experimenten lieten zien

De auteurs testten dit op drie soorten puzzels:

Handgeschreven cijfers optellen: Ze lieten zien dat EM-NESY enorme sommen (100 cijfers) kon afhandelen die andere methoden niet eens konden voltooien, terwijl het minder geheugen gebruikte.
Visuele Sudoku: Ze lieten zien dat het kon leren van puzzels waar de regels strikt waren, zelfs wanneer er benaderende methoden (zoals willekeurige bemonstering) werden gebruikt om het logische deel op te lossen.
Padvinden op een kaart: Ze lieten zien dat het kon leren om het kortste pad op een raster te vinden, een taak waar andere methoden moeite mee hadden omdat de logica te complex was om te differentiëren.

De Kernboodschap

Het artikel stelt EM-NESY voor, een framework dat neurosymbolisch leren behandelt als een spel van "warm en koud" dat om de beurt wordt gespeeld.

Beurt 1: De logische engine (de Criticus) bepaalt wat de juiste antwoorden horen te zijn, met behulp van de middelen die hij tot zijn beschikking heeft.
Beurt 2: De neurale engine (de Leerling) past zijn brein aan om bij die antwoorden te passen.

Deze eenvoudige wisseling zorgt ervoor dat AI kan leren van complexe, rommelige of benaderende logica, zonder dat de logica wiskundig perfect of differentieerbaar hoeft te zijn. Het maakt het bouwen van AI die zowel kan "zien" als "denken" veel flexibeler en schaalbaarder.

Technische Samenvatting: EM-NESY: Expectation Maximization voor Neurosymbolisch Leren

Probleemstelling

Neurosymbolische (NeSy) modellen beogen de perceptuele sterktes van neurale netwerken te integreren met de redeneerkracht van symbolische logica. Hoewel state-of-the-art NeSy-modellen doorgaans streven naar end-to-end training door gradiënten te backpropageren door zowel neurale als symbolische componenten, kampt deze aanpak met aanzienlijke uitdagingen wanneer de symbolische component afhankelijk is van benaderde inferentie.

Exacte probabilistische inferentie is vaak #P-hard en computationeel onuitvoerbaar voor complexe taken. Bijgevolg maken veel systemen gebruik van benaderde inferentiemethoden (bijv. sampling, belief propagation of linear-programming relaxaties). Deze methoden introduceren echter differentiabiliteitsproblemen:

Niet-differentiabiliteit: Technieken zoals sampling zijn inherent niet-differentieerbaar, wat gespecialiseerde gradiëntschatters (bijv. REINFORCE) of reparameterisatie-trucs vereist.
Computationele overhead: Zelfs theoretisch differentieerbare iteratieve methoden (bijv. belief propagation) worden in de praktijk onpraktisch om doorheen te differentiëren vanwege de enorme computationele graaf die nodig is om door alle iteraties heen te backpropageren.

Huidige oplossingen vereisen vaak inferentie-specifieke modificaties om differentiabiliteit te waarborgen, wat de flexibiliteit en schaalbaarheid van NeSy-systemen beperkt.

Methodologie: EM-NeSy

De auteurs stellen EM-NeSy voor, een leerkader dat probabilistisch NeSy-leren beschouwt als een instantie van het Expectation-Maximization (EM) algoritme. Deze formulering ontkoppelt het symbolische inferentieproces van de gradiëntberekening, waardoor elk inferentie-engine (exact of benaderd, differentieerbaar of niet) kan worden gebruikt.

Het Raamwerk

Het NeSy-model wordt behandeld als een latent variabelenmodel waarbij:

$X$ : Subsymbolische input (bijv. afbeeldingen).
$Z$ : Latente symbolische variabelen (neuraal voorspeld).
$Y$ : Doelstelling symbolische output (bijv. de geldigheid van een Sudoku-raster).
$\theta$ : Parameters van het neurale netwerk.

Het leerproces wisselt af tussen twee stappen:

E-stap (Expectation):
De symbolische component berekent de posterieure distributie van de latente variabelen $Z$ , geconditioneerd op de geobserveerde label $Y$ en input $X$ :
$p(z|y, x, \theta) = \frac{p_{Ne}(z|x, \theta)p_{Sy}(y|z)}{p(y|x, \theta)}$
Hier is $p_{Ne}$ de neurale prior en $p_{Sy}$ de symbolische likelihood. Cruciaal is dat deze stap fungeert als een "probabilistische corrector", die zachte of harde labels voor $Z$ abduceert op basis van achtergrondkennis. Deze stap kan worden uitgevoerd door elke symbolische inferentie-engine (exact, benaderd, sampling-gebaseerd) zonder dat hiervoor differentiabiliteit vereist is.
M-stap (Maximization):
De neurale parameters $\theta$ worden bijgewerkt door de cross-entropie te minimaliseren tussen de neurale prior $p_{Ne}(z|x, \theta)$ en de posterieure $\ell(z)$ berekend in de E-stap:
$L_{EM-NeSy}(\theta) = -\sum_{z \in R(Z)} \ell(z) \log p_{Ne}(z|x, \theta)$
Gradiënten worden alleen door de neurale component teruggepropageerd, waarbij de posterieure $\ell(z)$ als een constante wordt behandeld. Dit elimineert de noodzaak om door het symbolische inferentieproces te differentiëren.

Theoretische Equivalentie

Het artikel bewijst dat onder exacte inferentie, de door EM-NeSy berekende gradiënten wiskundig equivalent zijn aan die van standaard end-to-end differentiële NeSy-leren (Theorem 3.1). EM-NeSy herstelt dus de standaard setting wanneer exacte inferentie haalbaar is, maar biedt een duidelijk voordeel wanneer dit niet het geval is.

Varianten en Uitbreidingen

Hard EM: Gebruikt Maximum A Posteriori (MAP) toewijzingen in plaats van zachte posterieuren.
Multi-M EM: Voert meerdere M-stappen (gradiëntupdates) uit voor één enkele E-stap om convergentie te versnellen zonder de dure posterieure opnieuw te berekenen.
Benaderde Inferentie: Het raamwerk ondersteunt van nature sampling-gebaseerde methoden (bijv. Rejection Sampling, ABC Sampling) en iteratieve algoritmen (bijv. Belief Propagation) zonder aanpassingen.

Belangrijkste Bijdragen

Herformulering van NeSy-leren: De auteurs hebben NeSy-leren geherformuleerd binnen het EM-raamwerk, wat het gebruik van geavanceerde EM-varianten (Generalized EM, Stochastic EM, Hard EM) mogelijk maakt voor verbeterde flexibiliteit.
Differentiabiliteitsvrije Integratie: Er is een algemeen raamwerk voorgesteld dat elke probabilistische inferentie-engine integreert in een NeSy-model zonder dat de symbolische inferentieprocedure differentieerbaar hoeft te zijn.
Schaalbaarheid en Efficiëntie: De aanpak toont aan dat NeSy-leren kan schalen naar taken waarbij exacte inferentie onuitvoerbaar is of waarbij het differentiëren door iteratieve solvers computationeel onhaalbaar is.

Experimentele Resultaten

De auteurs hebben EM-NeSy geëvalueerd op drie benchmarks: MNISTAdd (optelling van handgeschreven cijfers), Visual Sudoku, en Warcraft path-planning.

Exacte Inferentie (MNISTAdd): EM-NeSy behaalde een nauwkeurigheid vergelijkbaar met standaard end-to-end differentiële NeSy (BP-std) en DeepStochLog. Het presteerde echter aanzienlijk beter in schaalbaarheid en efficiëntie. Terwijl DeepStochLog niet kon schalen naar 15 cijfers vanwege limieten in kenniscompilatie, schaalde EM-NeSy naar 100 cijfers. Het verminderde ook het piekgeheugengebruik van ~90 GB naar ~35 GB en verkortte de trainingstijd.
Benaderde/Niet-Differentiabele Inferentie:
- Visual Sudoku: Standaard differentiële methoden (Scallop, SL) liepen vast op 9x9-roosters. EM-NeSy, gebruikmakend van Approximate Bayesian Computation (ABC) sampling, behaalde een concurrerende nauwkeurigheid (53,3%) met minimale trainingstijd (8,24 min), terwijl andere methoden niet toepasbaar waren.
- Warcraft Path-Planning: EM-NeSy met ABC sampling behaalde state-of-the-art nauwkeurigheid (98,80% op 12x12, 69,60% op 30x30) met aanzienlijk snellere trainingstijden vergeleken met I-MLE en EXAL.
Geobserveerde Beperkingen: De prestaties van EM-NeSy hangen af van de kwaliteit van de benaderde posterieure. Hard EM (MAP) vertoonde bias op MNISTAdd, en loopy belief propagation faalde op 9x9 Sudoku vanwege de factor graph-structuur. ABC sampling vertoonde een hoge variantie op grotere instanties, maar bleef effectief in kleinere settings.

Betekenis en Claims

Het artikel claimt dat EM-NeSy een verenigd leerkader biedt dat het modelontwerp aanzienlijk vereenvoudigt door de noodzaak voor inferentie-specifieke differentiabiliteitsmodificaties weg te nemen. Door NeSy-leren als een EM-probleem te behandelen, stelt de aanpak het volgende mogelijk:

Het gebruik van elke symbolische inferentie-engine, inclus\n bij complexe, combinatorische restricties (zoals padplanning of Sudoku) waar exacte inferentie onhaalbaar is of differentiabele benaderingen moeilijk te construeren zijn.
Het herstellen van standaard end-to-end leren onder exacte inferentie, terwijl het een superieure computationele efficiëntie en geheugenschaalbaarheid biedt.
Het mogelijk maken van NeSy-systemen om taken aan te pakken die complexe, combinatorische restricties bevatten (zoals padplanning of Sudoku) waar exacte inferentie onhaalbaar is of waar differentiabele benaderingen moeilijk te construeren zijn.

De auteurs concluderen dat hoewel EM-NeSy het probleem van het selecteren van effectieve benaderingen niet oplost (wat taakafhankelijk blijft), het de barrière van differentiabiliteit wegneemt, waardoor meer schaalbare en flexibele neurosymbolische systemen mogelijk worden.