🤖 machine learning

Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization

Dit artikel toont aan dat zelfs minimale overparametrizatie in drempelcircuits en log-nauwkeurige Transformers exacte en benaderende certificering exponentieel moeilijk kan maken, een theoretische barrière die empirisch wordt bevestigd door de moeilijkheid om fouten te detecteren in getrainde modellen die binaire optelling uitvoeren.

Oorspronkelijke auteurs: Artur Back de Luca, Kimon Fountoulakis

Gepubliceerd 2026-05-25

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Artur Back de Luca, Kimon Fountoulakis

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 leraar bent die wil verifiëren dat een student een specifieke wiskunderegel echt heeft geleerd, zoals "hoe je twee getallen optelt". Je hebt een lijst met voorbeelden (invoer-uitvoerparen) en je wilt 100% zeker weten dat de student niet gewoon gokt of een trucje volgt.

Dit artikel stelt een fundamentele vraag: Hoeveel voorbeelden moet je aan een student laten zien om te bewijzen dat ze de exacte regel kennen, en niet slechts een zeer vergelijkbare?

De auteurs, Artur Back de Luca en Kimon Fountoulakis, ontdekten een verrassende en enigszins eng waarheid: Zelfs een kleine, bijna onzichtbare verandering in het "brein" van de student (het model) kan het onmogelijk maken om te bewijzen dat ze correct zijn, ongeacht hoeveel voorbeelden je hen laat zien.

Hier is de uiteenzetting van hun bevindingen met behulp van eenvoudige analogieën:

1. Het "Impostor"-probleem

Stel je voor dat je een perfecte student hebt die de regel voor het optellen van getallen kent. Je wilt bewijzen dat zij de enige zijn die het weten.

Het makkelijke scenario: Als de student de enige in de kamer is, heb je misschien slechts 5 of 10 voorbeelden nodig om te bewijzen dat ze de regel kennen.
Het moeilijke scenario: Stel je nu voor dat je 1.000 "impostors" de kamer binnenhaalt. Deze impostors zijn bijna perfect. Ze krijgen het antwoord 99,9% van de tijd goed. Het enige moment waarop ze het fout hebben, is op een zeer specifieke, verborgen set getallen (zoals getallen die beginnen met het cijfer '7').

Het artikel toont aan dat als je slechts één extra "neuron" (een klein beetje extra hersenkracht) aan een model toevoegt, je miljoenen van deze impostors kunt creëren. Elke impostor is het met de perfecte student over bijna alles eens, maar ze zijn het allemaal oneens over een andere, kleine, verborgen set getallen.

2. De "Naaald in de hooiberg"-analogie

Om te bewijzen dat de student de echte is en geen impostor, moet je het specifieke getal vinden waar ze het oneens over zijn.

Als je 1.000 impostors hebt, en elke één verbergt hun fout in een ander, klein hoekje van het universum der getallen, moet je elk hoekje controleren om zeker te zijn.
Het artikel bewijst dat als je slechts één extra poort aan een circuit toevoegt (of één extra "attention head" aan een Transformer-AI), het aantal van deze verborgen hoekjes explodeert.
Het resultaat: Om alle impostors te vangen, moet je misschien miljarden voorbeelden controleren. Als je slechts enkele duizenden controleert (een "polynoom" aantal), zul je de impostors waarschijnlijk missen, en zal de student je test doorstaan, zelfs al zijn ze eigenlijk fout.

3. De twee hoofdpersonages

De auteurs testten dit op twee soorten "studenten":

Circuits: Denk hierbij aan eenvoudige, stijve logische machines (zoals een rekenmachine). Ze ontdekten dat het toevoegen van slechts één extra schakelaar aan een circuit met een diepte van 2 of meer het exponentieel moeilijker maakt om het antwoord te certificeren.
Transformers: Dit zijn de krachtige AI-modellen achter tools zoals chatbots. De auteurs toonden aan dat het toevoegen van slechts één extra attention head (een kleine architecturale aanpassing) en een paar extra getallen aan het geheugen van het model het onmogelijk maakt om het met een redelijk aantal voorbeelden te certificeren.

4. De "Bijna perfect"-valstrik

Je zou kunnen denken: "Oké, maar wat als we gewoon accepteren dat de student een paar fouten maakt? Wat als we zeggen: 'Als ze 99% goed hebben, is dat goed genoeg'?"
Het artikel zegt: Wees voorzichtig.

Absolute fouten: Als je zegt: "Je mag maximaal 10 fouten maken in totaal", verstoppen de impostors zich nog steeds. Je hebt nog steeds miljarden voorbeelden nodig om die 10 fouten te vinden, omdat ze verspreid liggen over miljarden mogelijkheden.
Relatieve fouten: Als je zegt: "Je mag 1% fouten maken", kunnen de impostors miljoenen fouten verstoppen, zolang die 1% maar klein genoeg is. Het model kan in absolute termen enorm fout zijn, maar toch je "99% nauwkeurigheid"-test doorstaan.

5. Het realiteitsexperiment

Om te bewijzen dat dit niet alleen wiskundetheorie is, bouwden ze deze modellen daadwerkelijk:

Het circuit-experiment: Ze bouwden een circuit dat getallen optelt en creëerden vervolgens duizenden "gebroken" versies die alleen falen op specifieke invoer. Ze toonden aan dat zelfs met een enorm aantal testvoorbeelden, veel van deze gebroken circuits er nog steeds perfect uitzagen.
Het Transformer-experiment: Ze trainden AI-modellen om getallen op te tellen. Zelfs nadat ze ze hadden getraind totdat ze strenge validatietests doorstonden (99,9% goed), ontdekten ze dat sommige modellen nog steeds verborgen fouten hadden. Toen ze probeerden deze modellen te "auditeren" met willekeurige voorbeelden, bleven de modellen de test doorstaan, ook al waren ze niet echt perfect.

De conclusie

Het artikel concludeert dat certificering extreem fragiel is.
Als je wilt garanderen dat een AI of een circuit precies doet wat je denkt dat het doet, kun je niet vertrouwen op gemiddelde prestaties. Als het model zelfs een klein beetje "extra capaciteit" heeft (overparametrering), kan het een exponentieel aantal manieren verstoppen om fout te zijn.

Om echt zeker te zijn, moet je het model misschien testen op een aantal voorbeelden dat zo groot is dat het in de praktijk onmogelijk wordt. Het is als proberen te bewijzen dat een goochelaar niet bedriegt door ze een paar keer een truc te laten uitvoeren; als ze een geheim extra kaartje in hun mouw hebben, zul je het misschien nooit zien, tenzij je elk kaartje in het deck controleert.

Technische Samenvatting: Certificering uit Voorbeelden is Moeilijk voor Netwerken en Transformers onder Minimale Overparametrering

Probleemstelling

Naarmate state-of-the-art neurale netwerken steeds vaker worden ingezet voor redenerings- en algoritmische taken, wordt het waarborgen van hun exacte correctie cruciaal. Een hoge gemiddelde nauwkeurigheid maskeert vaak inconsistente gedragingen, waardoor het moeilijk is om fouten te detecteren die afwijken van de beoogde redeneerlogica. Dit artikel behandelt het probleem van exacte certificering: het bepalen van het minimumaantal gelabelde input-output voorbeelden dat nodig is om een doelhypothese $f^*$ binnen een hypotheseklasse $\mathcal{H}$ uniek te identificeren, zodanig dat geen enkele andere hypothese in $\mathcal{H}$ overeenkomt met $f^*$ op het volledige domein.

De centrale vraag is hoe gevoelig deze certificeringscomplexiteit is voor de omvang van de omringende hypotheseklasse. Specifiek onderzoeken de auteurs of een minimale uitbreiding van de hypotheseklasse (bijvoorbeeld het toevoegen van één poort of een constant aantal parameters) certificering exponentieel moeilijker kan maken, zelfs voor doelen die eerder eenvoudig te certificeren waren.

Methodologie

Het artikel hanteert een theoretisch raamwerk geworteld in teachingscomplexiteit en schakelcomplexiteit, aangevuld met empirische validatie op taken voor binaire optelling.

Theoretisch Raamwerk

Definitie van Certificaatgrootte: De auteurs definiëren de certificaatgrootte, $\text{cert}(f^*, \mathcal{H})$ , als de minimale grootte van een gelabeld steekproef $S$ zodat de versieruimte $V_S^{\mathcal{H}}$ (de verzameling hypotheses in $\mathcal{H}$ die consistent zijn met $S$ ) uitsluitend $f^*$ bevat.
Principe van Disjuncte Oneensheid: De kern van de bewijsstrategie berust op het construeren van een verzameling "misleidende" hypotheses. Voor een doel $f^*$ $f^{*}$ construeren de auteurs een familie van hypotheses $\{g_\pi\}$ ${g_{π}}$ die overal overeenkomen met $f^*$ $f^{*}$ , behalve op specifieke, paarsgewijs disjuncte "triggerblokken" $B_\pi$ $B_{π}$ .
- Als een hypotheseklasse een dergelijke familie van misleiders bevat waarbij de oneensheidsverzamelingen disjunct zijn, moet elk exact certificaat ten minste één voorbeeld bevatten uit elke oneensheidsverzameling.
- Bijgevolg is de certificaatgrootte ondergrens door het aantal van deze disjuncte blokken.
Analyse van Overparametrering: De auteurs analyseren hoe het toevoegen van minimale capaciteit (bijvoorbeeld één extra poort in netwerken, één extra attention-head en een constante embedding-breedte in Transformers) het mogelijk maakt om deze exponentiële families van misleiders te construeren voor elk doel in de oorspronkelijke, kleinere klasse.

Empirische Analyse

De auteurs vullen de theorie aan met twee experimenten op herkenning van binaire optelling:

Geconstrueerde Netwerken: Zij realiseren de theoretische constructie van misleiders voor drempelnetwerken ( $TC_0$ ) die optelling herkennen. Zij genereren een verzameling van $2^n$ onjuiste netwerken, waarbij elk verschilt van het doel op een verschillend blok van inputs, en meten hoeveel ervan overleven bij uniforme steekproeven van certificaatkandidaten.
Getrainde Transformers: Zij trainen encoder-only Transformers op 10-bits optelling. Na selectie van modellen die strenge validatiecontroles doorstaan (99,9% nauwkeurigheid), evalueren zij deze op een grote, vastgehouden testset. Zij analyseren het "overleven" van deze onvolmaakte modellen (misleiders) wanneer zij worden blootgesteld aan uniform gesampelde certificaatkandidaten, en testen of residuale fouten kunnen worden gedetecteerd met steekproeven van polynomiale grootte.

Belangrijkste Bijdragen en Resultaten

1. Exponentiële Moeilijkheid door Minimale Overparametrering

De primaire theoretische bijdrage is het aantonen dat certificering zeer gevoelig is voor de omvang van de hypotheseklasse.

Drempelnetwerken ( $TC_0$ ): Voor netwerken met diepte $d \ge 2$ , dwingt het toevoegen van één extra drempelpoort (het verhogen van het poortbudget van $s$ naar $s+1$ ) de certificaatgrootte voor elk doel in de oorspronkelijke klasse $TC_{d,s}$ om exponentieel te worden in de inputdimensie $n$ . Specifiek geldt: $\text{cert}(f^*, TC_{d,s+1}) \ge 2^{\Omega(n)}$ .
Transformers: Voor log-nauwkeurige Transformers met hard attention met middeling (AHAT), creëert het toevoegen van één attention-head in de laatste laag en zes auxiliaire embedding/residuaal-coördinaten een uitgebreide klasse waarin certificering exponentieel moeilijk wordt. Zelfs als een doel $f^*$ een certificaatgrootte van polynomiale grootte heeft in de kleinere architectuur, vereist het een exponentieel aantal voorbeelden om het te certificeren tegen de iets grotere architectuur.
Niet-Vacuïteit: De auteurs bewijzen dat deze ondergrenzen niet vacu zijn. Zij tonen aan dat de kleinere klassen ( $TC_{d,s}$ en standaard Transformers) doelen bevatten met certificaatgroottes van polynomiale grootte (specifiek $O(\log |\mathcal{H}|)$ ), maar dat dezezelfde doelen exponentieel moeilijk te certificeren worden zodra de klasse minimaal wordt uitgebreid.

2. Moeilijkheid van Benaderende Certificering

Het artikel breidt deze resultaten uit tot benaderende certificering:

Absolute Fouttolerantie: Als de certificering slechts een polynomiaal aantal fouten toestaat ( $R = \text{poly}(n)$ ), blijft de certificaatgrootte exponentieel ( $2^{\Omega(n)}$ ).
Relatieve Fouttolerantie: Als de certificering een constante relatieve fout toestaat ( $\epsilon$ ), kan de certificaatgrootte klein zijn (polynomiaal in $1/\epsilon$ ). Dit gaat echter ten koste van het toestaan van exponentieel veel absolute fouten. De auteurs tonen aan dat garanties voor constante relatieve fout exponentieel veel fouten kunnen verbergen, terwijl garanties voor polynomiale absolute fout nog steeds exponentiële certificaten vereisen.

3. Empirische Validatie

Netwerkexperimenten: De geconstrueerde $TC_0$ -misleiders bevestigden de theoretische barrière. Zelfs met certificaatkandidaten van polynomiale grootte bleven bijna alle geconstrueerde misleiders consistent met de gesampelde labels, wat exponentiële steekproeven vereiste om ze uit te sluiten.
Transformerexperimenten: Onder 150 getrainde modellen die uitgebreide validatie doorstonden, hadden er 63 residuale fouten op de vastgehouden testset. De analyse toonde aan dat zelfs met een gerichte subset van voorbeelden met veel fouten, uniform gesampelde certificaatkandidaten van polynomiale grootte faalden om alle niet-exacte hypotheses uit te sluiten. Onvolmaakte modellen konden ontsnappen aan detectie door grote, uniform gesampelde kandidaten.

Betekenis en Claims

Het artikel claimt een kwantitatieve vorm van certificeringsmoeilijkheid te bieden voor exact leren. De betekenis ligt in de volgende beweringen:

Gevoeligheid voor Modelcapaciteit: Certificering is niet louter een eigenschap van de doelfunctie, maar is kritiek afhankelijk van de "omgevende" hypotheseklasse. Een minimale toename in modelcapaciteit (constante overhead) kan de moeilijkheid van het verifiëren van de correctie van een model fundamenteel veranderen.
Beperkingen van Passieve Certificering: In passieve settings (waarbij voorbeelden worden gesampeld zonder het model te bevragen) zijn datasets van polynomiale grootte ontoereikend om te certificeren dat een model de beoogde berekening heeft geleerd als de hypotheseklasse lichtjes overgeparametreerd is.
Onderscheid ten opzichte van Leerbaarheid: De resultaten benadrukken een kloof tussen leerbaarheid en certificering. Hoewel een functie leerbaar kan zijn (of een klein certificaat heeft in een beperkte klasse), kan het certificeren ervan tegen een iets grotere klasse onuitvoerbaar zijn.
Implicaties voor Redeneringsmodellen: Voor modellen die worden ingezet op algoritmische taken (zoals optelling), garandeert een hoge validatienauwkeurigheid geen exactheid. Het artikel suggereert dat zonder sterkere protocollen (bijvoorbeeld actief leren of specifieke queries), grote uniform gesampelde datasets kunnen falen in het detecteren van subtiele, gestructureerde inconsistenties in redeneringsmodellen.

De auteurs concluderen dat, hoewel exacte certificering een fundamentele uitdaging is, de barrière niet slechts een uitzondering in het slechtst mogelijke geval is, maar een structureel gevolg van minimale overparametrering in klassen die relevant zijn voor moderne redeningstaken. Zij suggereren dat toekomstig werk actief certificeringsprotocollen moet onderzoeken om deze passieve barrières mogelijk te overwinnen.