💻 computer science

Query Languages for Machine-Learning Models

Dit artikel onderzoekt de toepassing van eerste-orde logica met sommatie (FO(SUM)) en de recursieve uitbreiding daarvan IFP(SUM) als querytalen voor neurale netwerken gerepresenteerd als gewogen grafen, waarbij illustratieve voorbeelden worden gepresenteerd en de expressiviteit en computationele complexiteit worden geanalyseerd.

Oorspronkelijke auteurs: Martin Grohe

Gepubliceerd 2026-01-15

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Martin Grohe

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

Stel je voor dat je een enorm, complex machine learning-model hebt, zoals een neuraal netwerk. Voor een computerwetenschapper is dit een "gewogen graaf" — een web van knopen (neuronen) verbonden door lijnen (randen), waarbij aan elke lijn een specifiek getal (een gewicht) is gekoppeld.

De auteur van dit artikel, Martin Grohe, stelt een eenvoudige maar diepzinnige vraag: Hoe kunnen we vragen stellen aan deze machines?

Normaal gesproken voeren we gewoon data in een neuraal netwerk en krijgen we een antwoord. Maar wat als we willen vragen: "Hoeveel verbindingen heeft dit netwerk?" of "Als ik deze specifieke draad verwijder, verandert het antwoord dan?" of zelfs "Wat is de totale oppervlakte onder de curve van de output van dit netwerk?"

Om deze vragen te beantwoorden, stelt het artikel twee speciale "talen" (logica's) voor die specifiek zijn ontworpen om met deze gewogen machines te communiceren. Denk aan deze talen als een nieuw soort afstandsbediening voor neurale netwerken.

Hier is een overzicht van de twee talen en wat ze kunnen doen, met behulp van eenvoudige analogieën:

1. De eerste taal: FO(SUM)

De "Tellen en Optellen" afstandsbediening

Denk aan FO(SUM) als een zeer slimme rekenmachine die naar het netwerk kan kijken en twee hoofdtaken kan uitvoeren:

Om zich heen kijken: Het kan controleren of er een verbinding bestaat (zoals vragen: "Is er een draad tussen Knoop A en Knoop B?").
Dingen bij elkaar optellen: Het heeft een speciale "Som"-knop. Het kan een groep dingen vinden (zoals alle driehoeken in een netwerk) en hun gewichten bij elkaar optellen.

Wat het kan doen:

Tellen: Het kan je precies vertellen hoeveel randen (draden) of driehoeken er in het netwerk bestaan.
Het beste vinden: Het kan de "lichtste" of "zwaarste" driehoek in het netwerk vinden.
Eenvoudige netwerken simuleren: Als het neurale netwerk ondiep is (niet erg diep), kan deze taal daadwerkelijk de output van het netwerk berekenen voor een specifieke input. Het is alsoals het simuleren van een korte keten van dominostenen.
"Nutloze" draden vinden: Het kan draden identificeren die, als ze zouden worden verwijderd, het uiteindelijke resultaat niet zouden veranderen.

Het nadeel (de beperking):
FO(SUM) is als een persoon die slechts naar een kleine buurt tegelijk kan kijken. Het heeft moeite met diepe netwerken. Als het neurale netwerk veel lagen heeft (een zeer lange keten van dominostenen), raakt deze taal de weg kwijt. Het kan niet gemakkelijk het uiteindelijke resultaat van een zeer diep netwerk berekenen omdat het geen manier heeft om te "lussen" of stappen te "onthouden" terwijl het dieper gaat.

2. De tweede taal: IFP(SUM)

De "Recursieve" afstandsbediening

Om diepe netwerken aan te kunnen, hebben we een krachtiger hulpmiddel nodig. Maak kennis met IFP(SUM).

Dit is de Eerste Taal met een "Loop"-knop. In computertaal wordt dit een "fixed-point" operator genoemd. Het stelt de taal in staat om te zeggen: "Blijf deze berekening uitvoeren, waarbij het resultaat van de vorige stap de input is voor de volgende stap, totdat je het einde bereikt."

Wat het kan doen:

Elke diepte aan: Omdat het kan lussen, kan het de berekening van een neuraal netwerk simuleren, ongeacht hoe diep of complex het is. Het kan het signaal traceren van de allereerste input tot aan de uiteindelijke output.
Complexe wiskunde: Het kan het zware werk verrichten dat nodig is om de functie van het netwerk te evalueren.

Het nadeel (de beperking):
Hoewel IFP(SUM) krachtig is, heeft het een snelheidslimiet.

Het "Explosie"-probleem: Als je niet voorzichtig bent, kunnen de getallen die het berekent astronomisch groot worden (zoals een getal keer zichzelf opvolgend kwadrateren). Om dit op te lossen, introduceert het artikel een "veilige" versie genaamd sIFP(SUM), die voorkomt dat de getallen te snel groeien, zodat de berekening in een redelijke tijd wordt voltooid.
Niet alles is mogelijk: Zelfs met deze krachtige afstandsbediening zijn er enkele vragen die deze taal niet kan beantwoorden. Bijvoorbeeld de vraag: "Is er enige input die ervoor zorgt dat dit netwerk een niet-nul output geeft?" Dit is een vraag die te moeilijk is voor deze taal om efficiënt op te lossen, ook al zou een mens het theoretisch kunnen uitzoeken met genoeg tijd.

Het grote plaatje: "Model-Agnostische" vragen

Het artikel bespreekt ook een speciaal type vraag genaamd "Model-Agnostisch."

Stel je voor dat je twee verschillende neurale netwerken hebt, Netwerk A en Netwerk B. Ze zijn verschillend gebouwd (verschillende aantallen neuronen, verschillende draden), maar ze doen beide exact hetzelfde werk (ze geven voor elke input hetzelfde antwoord).

Een Model-Agnostische vraag is een vraag waarbij het antwoord alleen afhangt van de taak die het netwerk uitvoert, niet van hoe het is gebouwd.
- Voorbeeld: "Geeft dit netwerk voor elke input nul?" (Dit is waar voor zowel A als B als ze hetzelfde werk doen).
Een Niet-Agnostische vraag hangt af van de specifieke bedrading.
- Voorbeeld: "Hoeveel draden heeft dit netwerk?" (Netwerk A kan er 100 hebben, Netwerk B kan er 50 hebben, zelfs als ze hetzelfde werk doen).

De verrassende bevinding:
Het artikel onthult een teleurstellende maar belangrijke waarheid:

FO(SUM) (de eenvoudige taal) is slecht in het stellen van Model-Agnostische vragen over algemene netwerken. Het kan alleen triviale dingen vragen (zoals "Is het netwerk leeg?"). Het kan niet vertellen of een netwerk "altijd nul" is, tenzij het netwerk zeer ondiep is.
IFP(SUM) (de krachtige taal) is beter, maar zelfs het heeft grenzen. Er zijn sommige vragen over wat een netwerk doet die zo complex zijn dat zelfs deze krachtige taal ze niet efficiënt kan beantwoorden.

Samenvatting

Dit artikel gaat over het bouwen van een woordenboek en een grammatica om met neurale netwerken te praten.

FO(SUM) is een basiswoordenboek dat goed is in tellen en eenvoudige sommen, maar het raakt de weg kwijt in diepe netwerken.
IFP(SUM) is een woordenboek met een "loop"-functie dat diepe netwerken kan aan, maar het heeft snelheidslimieten en kan nog steeds niet elke vraag beantwoorden over wat een netwerk doet.

De auteur concludeert dat hoewel we vooruitgang hebben geboekt bij het creëren van deze talen, er nog steeds veel mysteries zijn over hoeveel we een neuraal netwerk echt kunnen laten onthullen over zijn eigen innerlijke werking.

Technische Samenvatting: Querytalen voor Machine-Learningmodellen

Probleemstelling

Het artikel behandelt de uitdaging van het formeel analyseren en bevragen van machine learning (ML) modellen, specifiek neurale netwerken, die inherent "hybride modellen" zijn die discrete structuren (grafiektopologie) combineren met continue numerieke componenten (gewichten en biases). Hoewel de eindige modeltheorie succesvol discrete computationele problemen en relationele databases heeft geanalyseerd, ontbreken standaardlogica's de mechanismen om de numerieke aggregatie en rekenkunde te hanteren die nodig zijn om het gedrag van gewogen structuren zoals neurale netwerken te beschrijven.

Bestaande benaderingen voor ML-analyse vertrouwen vaak op vaste, generieke uitlegmethoden (bijv. contrafeitelijken voor specifieke inputs) of behandelen modellen als zwarte dozen. De auteur pleit voor een perspectief dat geworteld is in de database-theorie en de eindige modeltheorie, waarbij wordt voorgesteld dat ML-modellen moeten worden behandeld als datastructuren die onderhevig zijn aan flexibele, logische queries. Dit maakt onderzoek mogelijk naar zowel de lokale componentfunctionaliteit als globale semantische eigenschappen (bijv. robuustheid, correctheid, of integralen over de functieruimte) zonder beperkt te zijn tot specifieke input-evaluaties.

Methodologie

Het artikel onderzoekt twee specifieke logica's ontworpen voor gewogen eindige structuren (structuren met een eindig universum en gewichtsfuncties die mappen naar uitgebreide reële getallen, $\mathbb{R}_\perp$ ):

FO(SUM): Eerste-orde logica uitgebreid met een sommatie-operator ( $\sum$ ) en conditionele termen. Deze logica maakt het mogelijk om gewichten te aggregeren over definieerbare verzamelingen binnen de structuur.
IFP(SUM): De recursieve uitbreiding van FO(SUM) met behulp van inflationaire fixed-point operatoren. Dit maakt het definiëren van inductieve processen mogelijk, wat noodzakelijk is voor het evalueren van neurale netwerken met een onbegrensde diepte.

De methodologie omvat:

Het formaliseren van Neurale Netwerken: Het representeren van Feedforward Neurale Netwerken (FNN's) als gewogen gerichte acyclische grafen met een specifieke vocabulaire ( $\{wt, bias, \le_{in}, \le_{out}\}$ ).
Het definiëren van Semantiek: Het vaststellen van de semantiek van deze logica's over gewogen structuren, waarbij termen evalueren naar waarden in $\mathbb{R}_\perp$ en formules naar Booleaanse waarden.
Expressiviteitsanalyse: Het bepalen welke eigenschappen van FNN's (bijv. evaluatie, het tellen van parameters, het vinden van nutteloze randen, het berekenen van integralen) uitgedrukt kunnen worden in deze logica's.
Complexiteitsanalyse: Het analyseren van de data-complexiteit van het evalueren van deze queries, waarbij zowel uniforme circuit-complexiteitsklassen (bijv. $\mathsf{TC}^0$ ) als polynomiale tijd ( $\mathsf{P}$ ) worden overwogen.
Model-Agnostische Queries: Het onderzoeken van queries waarvan de uitkomsten uitsluitend afhangen van de door het netwerk berekende functie ( $f^N$ ), in plaats van de specifieke architectuur of gewichten, waarbij onderscheid wordt gemaakt tussen "model-agnostische" en "volledig model-agnostische" eigenschappen.

Belangrijkste Bijdragen en Resultaten

1. Expressiviteit van FO(SUM)

Evaluatie met Begrensde Diepte: FO(SUM) kan de evaluatie van FNN's van begrensde diepte uitdrukken. De logica kan de waarde van een knoop tot een vaste diepte $d$ recursief definiëren met behulp van sommatie om gewogen inputs te aggregeren en conditionele termen om de ReLU-activatiefunctie te simuleren.
Globale Eigenschappen: De logica kan globale eigenschappen definiëren zoals het totale aantal gewichten, de verzameling van "nutteloze" randen (randen waarvan de verwijdering de output niet verandert), en integralen over de door het netwerk berekende functie (via de cilindrische celdecompositie van stuksgewijs lineaire functies).
Beperkingen op Onbegrensde Diepte: FO(SUM) kan niet de evaluatiefunctie voor FNN's van onbegrensde diepte uitdrukken. De logica is beperkt tot lokale eigenschappen; het kan niet de onbegrensde recursie simuleren die vereist is voor algemene FNN-evaluatie.
Model-Agnostische Beperkingen: Een centraal negatief resultaat (Theorem 3.14) stelt dat elke FO(SUM)-zin die model-agnostisch is (invariant onder verschillende architecturen die dezelfde functie berekenen) op de klasse van alle FNN's, triviaal moet zijn (of waar voor alle, of onwaar voor alle). Dus niet-triviale model-agnostische queries (zoals controleren of een netwerk overal nul uitvoert) zijn niet uitdrukbaar in FO(SUM) voor onbegrensde diepte.
Equivalentie bij Begrensde Diepte: Echter, voor FNN's van begrensde diepte ( $N_d(m, 1)$ ) is FO(SUM) verrassend krachtig. Theorem 3.18 stelt dat elke query die uitdrukbaar is in eerste-orde logica over het geordende veld van reële getallen uitgebreid met de functie ( $FO(\mathbb{R}_{lin}, f)$ ), ook uitdrukbaar is in FO(SUM). Dit wordt bereikt door kwantificatie over reële getallen te simuleren via kwantificatie over de cellen van de cilindrische decompositie van de functie.

2. Expressiviteit van IFP(SUM)

Onbegrensde Diepte: IFP(SUM) overwint de dieptebeperking van FO(SUM) door fixed-point operatoren te introduceren. Het kan de evaluatiefunctie voor FNN's van onbegrensde diepte uitdrukken (Example 4.1).
Complexiteit en Scalaire Fragmenten: Hoewel standaard fixed-point logica over geordende structuren polynomiale tijd vangt, staat IFP(SUM) over gewogen structuren voor een complexiteitsdrempel: termen kunnen exponentieel in grootte groeien (bijv. herhaalde kwadraten). Om dit aan te pakken, introduceert het artikel het scalaire fragment sIFP(SUM), dat vermenigvuldigingen en delingen die betrekking hebben op intentionele symbolen beperkt.
- Theorem 4.5: De data-complexiteit van sIFP(SUM) zit in P (polynomiale tijd) over rationale gewogen structuren.
Expressiviteitslimieten: Ondanks het vangen van polynomiale tijd in het Blum-Shub-Smale model, kan IFP(SUM) (en sIFP(SUM)) niet alle polynomiale-tijd berekenbare model-agnostische queries uitdrukken. Theorem 4.7 toont het bestaan aan van een polynomiale-tijd beslisbare model-agnostische query op $N(1, 1)$ die niet uitdrukbaar is in IFP(SUM), zelfs met binaire gewichten. Deze beperking komt voort uit het onvermogen van de logica om willekeurige berekeningen uit te voeren op de numerieke waarden (gebrek aan variabelen die over getallen variëren).
Gereduceerde FNN's: Het artikel introduceert "gereduceerde FNN's" (factoreren door een bisimulariteit-achtige equivalentie). Theorem 4.8 laat zien dat voor FNN's waarbij de gereduceerde vorm gewichten heeft met een begrensde bit-grootte, sIFP(SUM) alle polynomiale-tijd beslisbare model-agnostische queries vangt.

3. Complexiteitsresultaten

FO(SUM): De data-complexiteit van het evalueren van FO(SUM)-expressies zit in uniform $\mathsf{TC}^0$ (Theorem 3.9). Deze klasse staat drempelpoorten en iteratieve optelling toe, wat voldoende is voor de rekenkundige operaties die vereist zijn.
sIFP(SUM): De data-complexiteit zit in P (Theorem 4.5).

Betekenis en Claims

Het artikel positioneert zichzelf als een "persoonlijk perspectief" en een fundamentele stap in het toepassen van eindige modeltheorie op ML. De primaire betekenis ligt in:

Formaliseren van ML-Querying: Het biedt een rigoureus logisch kader voor het bevragen van de interne semantiek van neurale netwerken, waarbij men verder gaat dan black-box evaluatie naar structurele en functionele analyse.
Overbruggen van Discreet en Continu: Het demonstreert hoe meta-eindige modeltheorie (het uitbreiden van eindige modeltheorie naar hybride structuren) kan worden toegepast op neurale netwerken, die van nature worden gerepresenteerd als gewogen grafieken.
Definiëren van Grenzen van Expressiviteit: De resultaten trekken duidelijke grenzen tussen wat wel en niet logisch uitgedrukt kan worden. Met name benadrukt het dat hoewel netwerken met begrensde diepte vatbaar zijn voor logische analyse via FO(SUM), onbegrensde diepte een complexiteit introduceert die recursie (IFP) vereist, maar nog steeds fundamentele expressiviteitsbarrières ervaart met betrekking tot model-agnostische eigenschappen.
Complexiteitsinzichten: Het werk verbindt logische expressiviteit met computationele complexiteit, waarbij wordt aangetoond dat zelfs met fixed-point operatoren, het vangen van alle polynomiale-tijd model-agnostische eigenschappen een restrictie vereist op de numerieke bit-grootte van de gewichten.

De auteur concludeert dat hoewel er aanzienlijke vooruitgang is geboekt in [22, 23], veel open vragen blijven bestaan, met name met betrekking tot de uitbreiding van resultaten naar willekeurige inputdimensies, het opheffen van begrensde diepte-aannames zonder complexiteitstheoretische aannames, en de inter-definieerbaarheid van verschillende aggregatie-operatoren. Het artikel claimt niet het "explainable AI"-probleem volledig op te lossen, maar biedt een theoretisch instrumentarium voor het definiëren en analyseren van specifieke soorten verklaringen en verificaties.