💻 computer science

Verification of Neural Networks (Lecture Notes)

Dit artikel presenteert collegeaantekeningen die een theoretische inleiding bieden tot verificatie van neurale netwerken, waarbij architecturen zoals feed-forward netwerken, RNN's en transformers worden behandeld naast specificatietalen en algoritmische technieken.

Oorspronkelijke auteurs: Benedikt Bollig

Gepubliceerd 2026-04-29

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Benedikt Bollig

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 ongelooflijk complexe, black-box machine hebt gebouwd die katten op foto's kan herkennen, talen kan vertalen of een auto kan besturen. Je weet dat het de meeste van de tijd goed werkt, maar je weet niet waarom het zijn beslissingen neemt, en je bent bang dat het plotseling kan besluiten dat een stopbord een maximumsnelheidsbord is omdat een vogel voor de camera vloog.

Deze lezingenreeks van Benedikt Bollig is als een gids voor wiskundige detectives die proberen uit te zoeken of deze "black-box" machines (neuronale netwerken) veilig en betrouwbaar zijn. In plaats van ze alleen te testen met een miljoen foto's, vraagt de auteur: Kunnen we wiskundig bewijzen dat deze machine nooit een specifieke fout zal maken?

Hier is een uiteenzetting van de reis van het artikel, met gebruikmaking van eenvoudige analogieën:

1. Het Doel: Bewijzen dat de Machine "Goed" is

Het artikel begint met de stelling dat hoewel we deze machines kunnen trainen, we formele garanties nodig hebben. Het is als het bouwen van een brug: je rijdt niet gewoon een paar auto's eroverheen om te zien of hij het houdt; je berekent de fysica om te bewijzen dat hij niet zal instorten.

De Uitdaging: Neuronale netwerken zijn "ondoorzichtig". Ze bestaan uit lagen wiskunde die moeilijk te interpreteren zijn.
De Oplossing: De auteur stelt een "Specificatietaal" voor. Denk hierbij aan het schrijven van een strikt regelboek in een taal die de machine begrijpt. Bijvoorbeeld: "Als je een hond ziet, moet je 'hond' zeggen, zelfs als ik een klein beetje ruis aan de foto toevoeg."

2. De Eenvoudige Machines: Feed-Forward Netwerken

Eerst bekijkt het artikel het eenvoudigste type netwerk (Feed-Forward). Stel je een fabrieksassemblagelijn voor waar een pakket van het ene station naar het volgende beweegt, op elke stop wordt verwerkt, maar nooit teruggaat.

Het Goede Nieuws: Voor deze eenvoudige netwerken bewijst de auteur dat we het verificatieprobleem kunnen oplossen.
De Magische Truc: De auteur laat zien dat we het volledige gedrag van het netwerk kunnen vertalen naar een enorm wiskundig raadsel (Lineaire Reële Aritmetiek). Als we het raadsel kunnen oplossen, weten we dat het netwerk veilig is.
De Haken en Ogen: Hoewel we het kunnen oplossen, kan het erg lang duren als het netwerk enorm is (zoals het proberen op te lossen van een Sudoku met een miljard vakjes). Voor veel praktische regels zijn er echter kortere wegen die het snel genoeg maken om bruikbaar te zijn.

3. De Lussen Machines: Recurrente Netwerken (RNN's)

Vervolgens bekijkt het artikel netwerken die sequenties verwerken, zoals het lezen van een zin woord voor woord. Deze zijn als een robot die onthoudt wat het net heeft gelezen om het volgende woord te begrijpen.

Het Slechte Nieuws: De auteur bewijst dat voor deze lussen-machines verificatie onmogelijk is in het algemene geval.
De Analogie: Het is als vragen: "Zal deze robot ooit vastlopen in een oneindige lus?" De wiskunde toont aan dat voor deze specifieke soorten machines er geen algoritme bestaat dat voor elk mogelijk scenario een "Ja" of "Nee" antwoord kan geven. Het is een fundamentele limiet van de logica, niet alleen een gebrek aan rekenkracht.
Waarom? De auteur laat zien dat deze machines krachtig genoeg zijn om "Probabilistische Eindige Automaten" te simuleren, waarvan bekend is dat ze volledig niet te verifiëren zijn.

4. De Moderne Reuzen: Transformers en Attention

Tot slot bekijkt het artikel de "Transformers" die moderne AI aandrijven (zoals degene waarmee je nu praat). Deze gebruiken een mechanisme genaamd Attention.

De Analogie: Stel je een student voor die een lang essay leest. Een standaard lezer leest woord voor woord. Een "Attention"-mechanisme is als een student die direct naar elk deel van het essay kan springen om te zien hoe het samenhangt met de huidige zin. Ze kunnen de hele pagina tegelijk bekijken om te beslissen welk woord als volgende komt.
De Huidige Stand van Zaken: Het artikel legt uit hoe deze machines zijn opgebouwd (lagen van "Attention Heads" en "Feed-Forward" lagen).
Het Mysterie: De auteur geeft toe dat hoewel we begrijpen hoe ze werken, we nog niet weten of we ze kunnen verifiëren.
- Sommige eenvoudige versies van deze machines (alleen Encoder) kunnen dingen doen zoals het vinden van het grootste getal in een lijst of controleren of een zin gesorteerd is.
- Omdat de volledige architectie echter zo krachtig is (het kan theoretisch een Turing-machine simuleren, het krachtigste computermodel), blijft de grote vraag: Is er een manier om wiskundig te bewijzen dat deze complexe machines veilig zijn? Het artikel stelt dat dit een open onderzoeksprobleem is.

Samenvatting van het "Detectivewerk"

Eenvoudige Netwerken: We hebben een kaart en een kompas. We kunnen bewijzen dat ze veilig zijn, hoewel de reis lang kan zijn.
Lussen Netwerken: We hebben een muur geraakt. De wiskunde zegt dat we niet kunnen bewijzen dat ze in alle gevallen veilig zijn.
Transformers: We staan aan de rand van een nieuw continent. We weten dat ze krachtig zijn, maar we hebben de kaart nog niet uitgewerkt. Het artikel suggereert dat het vinden van een manier om ze te verifiëren de volgende grote uitdaging is voor wetenschappers.

Het artikel belooft niet om de machines te repareren of je te vertellen hoe je ze vandaag in ziekenhuizen of zelfrijdende auto's kunt gebruiken. In plaats daarvan trekt het een duidelijke lijn in het zand: "Dit is wat we wiskundig kunnen bewijzen, dit is wat onmogelijk is, en hier moeten we nieuwe wiskunde uitvinden."

Op basis van de collegeaantekeningen van Benedikt Bollig volgt hier een gedetailleerde technische samenvatting van het paper "Verification of Neural Networks".

1. Probleemstelling

Het paper adresseert de uitdaging om formele garanties te bieden voor neurale netwerken (NN's), die steeds vaker worden ingezet in veiligheidskritieke systemen (bijvoorbeeld autonome voertuigen, medische diagnostiek). In tegenstelling tot traditionele software zijn NN's "black-box"-modellen die zijn getraind op data, waardoor hun gedrag ondoorzichtig is en moeilijk te verifiëren met standaardtesten.

Het kernprobleem is verificatie: bepalen of een neurale netwerk voldoet aan een specifieke wiskundige specificatie (bijvoorbeeld robuustheid, eerlijkheid, functionele correctheid) voor alle mogelijke invoer binnen een gedefinieerd domein. Het paper onderzoekt de theoretische grenzen van deze verificatie, met name gericht op:

Beslisbaarheid: Kunnen we op een algoritmische manier bepalen of een specificatie geldt?
Complexiteit: Wat zijn de rekenkosten van verificatie?
Expressiviteit: Hoe beïnvloeden verschillende architecturen (Feed-Forward, Recurrent, Transformers) en activatiefuncties deze eigenschappen?

2. Methodologie

De auteur hanteert een theoretisch informatica-approach, waarbij de volgende elementen worden gecombineerd:

Formele Logica: Het gebruik van Lineaire Reële Aritmetiek (LRA) en de uitbreiding daarvan tot Neurale Netwerk Logica (NNL) om specificaties te definiëren.
Automatentheorie: Het gebruik van Büchi-automata (die werken op oneindige woorden) om reële getallen te modelleren en arithmetische theorieën te beslissen.
Reducties: Het bewijzen van onbeslisbaarheid of hardheid door bekende onbeslisbare problemen (zoals de leegte van Probabilistische Eindige Automata of het Gewijzigde Post Correspondentie Probleem) te reduceren tot neurale netwerkverificatieproblemen.
Architecturale Analyse: Systematische analyse van Feed-Forward Neurale Netwerken (FFNN's), Recurrente Neurale Netwerken (RNN's) en Transformers (Attention-mechanismen).

3. Belangrijkste Bijdragen en Resultaten

A. Feed-Forward Neurale Netwerken (FFNN's)

Specificatietaal (NNL): De auteur definieert Neurale Netwerk Logica (NNL), een uitbreiding van LRA die een predikaat $N(x) = y$ bevat dat de invoer-uitvoerrelatie van een netwerk voorstelt.
Beslisbaarheid voor ReLU:
- Stelling: Het vervullingsprobleem voor NNL met ReLU-activatiefuncties ( $\text{SAT}(\text{NNL}[\text{ReLU}])$ ) is beslisbaar.
- Methode: Het bewijs vertaalt het neurale netwerk naar een equivalent LRA-formule. Omdat LRA beslisbaar is (via automatentheoretische technieken), is NN-verificatie ook beslisbaar voor ReLU-netwerken.
Complexiteit:
- Het existentiële fragment van NNL met ReLU ( $\exists\text{NNL}[\text{ReLU}]$ ) is NP-compleet.
- Het universele fragment is coNP-compleet.
- Hardheid: Zelfs beperkte "bereikbaarheids"-problemen (controleren of een netwerk een specifieke staat kan bereiken vanuit een specifieke invoer) zijn NP-hard, bewezen via reductie vanuit 3SAT.
Verder dan ReLU:
- Voor netwerken die activatiefuncties zoals sigmoid ( $\sigma$ ), tanh, of NLReLU gebruiken, wordt het verificatieprobleem equivalent aan de Eerste Orde Theorie van het Reële Exponentiële Veld (REF).
- Status: De beslisbaarheid van REF (Tarski's exponentiële functieprobleem) is momenteel onbekend, wat impliceert dat verificatie voor deze algemene netwerken een open probleem is.

B. Recurrente Neurale Netwerken (RNN's)

Onbeslisbaarheid:
- Stelling: Het leegteprobleem voor RNN's (bepalen of er een invoerreeks bestaat die het netwerk als positief classificeert) is onbeslisbaar.
- Bewijsstrategie:
  1. Aantonen dat (ReLU, sigmoid)-RNN's Probabilistische Eindige Automata (PFAs) kunnen simuleren.
  2. Steunen op het bekende resultaat dat het leegteprobleem voor PFAs (specifiek, controleren of de acceptatiekans gelijk is aan of hoger dan een drempelwaarde) onbeslisbaar is (gereduceerd vanuit het Gewijzigde Post Correspondentie Probleem).
- Implicatie: Aangezien het basisleegteprobleem onbeslisbaar is, zijn de meeste niet-triviale verificatietaken voor RNN's ook onbeslisbaar.

C. Attention en Transformers

Architectuur: Het paper formaliseert de Transformer-architectuur, inclusief attention-heads, multi-head-lagen, encoders en decoders.
Expressiviteit:
- Er wordt aangetoond dat Transformers complexe functies kunnen berekenen (bijvoorbeeld het vinden van het maximum in een reeks, het herkennen van gesorteerde reeksen, en het herkennen van goed gevormde haakjesreeksen) met behulp van Encoder-Only-architecturen.
- Het paper demonstreert hoe specifieke Transformers kunnen worden geconstrueerd om deze taken uit te voeren met attention-mechanismen (bijvoorbeeld avg-argmax attention) en feed-forward-lagen.
Verificatiestatus:
- Vanwege de Turing-compleetheid van algemene Transformer-architecturen (ze kunnen Turing-machines simuleren) is algemene verificatie waarschijnlijk onbeslisbaar.
- Het paper benadrukt dat hoewel specifieke, beperkte fragmenten misschien beslisbaar zijn, algemene positieve beslisbaarheidsresultaten voor Transformers een open onderzoeksgebied blijven.

4. Betekenis en Implicaties

Theoretische Grenzen: Het werk trekt een duidelijke lijn tussen wat theoretisch verifieerbaar is en wat niet. Het stelt vast dat terwijl eenvoudige ReLU-netwerken beslisbaar zijn (zij het NP-hard), het toevoegen van recurrentie (RNN's) of complexe niet-lineariteiten (Exponentiële/Transcendente functies) het probleem in het domein van onbeslisbaarheid of onbekende beslisbaarheid duwt.
Formele Specificatie: Het biedt een rigoureus logisch kader (NNL) om eigenschappen zoals robuustheid (kleine invoerveranderingen veranderen de uitvoer niet), eerlijkheid (gevoelige kenmerken negeren) en functionele equivalentie uit te drukken, en gaat hiermee voorbij aan ad-hoc testen.
Richting voor Beoefenaars:
- Voor FFNN's is verificatie mogelijk maar rekenkundig duur; beoefenaars moeten zich richten op existentiële fragmenten of SMT-oplossers gebruiken.
- Voor RNN's en Transformers is exacte verificatie in het algemene geval theoretisch onmogelijk. Dit suggereert dat verificatie voor deze modellen moet vertrouwen op abstracties, benaderingen of beperkte subklassen van de architectuur.
Toekomstige Onderzoeksrichtingen: Het paper identificeert de verificatie van Transformers en de beslisbaarheid van het Reële Exponentiële Veld als kritieke open problemen. Het suggereert dat toekomstig werk zich moet richten op het identificeren van specifieke architecturale beperkingen die beslisbaarheid herstellen terwijl de bruikbaarheid behouden blijft.

Samenvattende Conclusie

Bolligs collegeaantekeningen bieden een fundamentele theoretische analyse van neurale netwerkverificatie. De centrale boodschap is dat verificatie beslisbaar is voor feed-forward netwerken met ReLU-activaties (reducerbaar tot Lineaire Reële Aritmetiek), maar onbeslisbaar wordt voor recurrente netwerken en open blijft voor netwerken met transcendentale activatiefuncties of algemene Transformers. Dit onderstreept de noodzaak om gespecialiseerde, benaderende verificatietools te ontwikkelen voor moderne deep learning-architecturen, in plaats van te vertrouwen op algemene exacte verificatie.