Forward and Backward Reachability Analysis of Closed-loop Recurrent Neural Networks via Hybrid Zonotopes

Each language version is independently generated for its own context, not a direct translation.

Stel je voor dat je een zeer slimme, maar soms onvoorspelbare robot hebt. Deze robot is een RNN (een Recurrent Neural Network). In tegenstelling tot een gewone computer die elke opdracht als een losse gebeurtenis ziet, heeft deze robot een "geheugen". Hij onthoudt wat hij gisteren deed om te beslissen wat hij vandaag moet doen. Dit is geweldig voor complexe taken, zoals het besturen van een auto of het voorspellen van het weer.

Maar hier zit het probleem: omdat deze robot zo complex is, is het heel moeilijk om te weten of hij altijd veilig blijft. Wat als hij plotseling een verkeerde beslissing neemt en tegen een muur rijdt?

De auteurs van dit paper, Yuhao Zhang en Xiangru Xu, hebben een nieuwe manier bedacht om te garanderen dat zo'n robot-geheugen veilig blijft. Ze gebruiken een wiskundig hulpmiddel dat ze een "Hybride Zonotoop" noemen.

Hier is de uitleg in simpele taal, met wat creatieve vergelijkingen:

1. Het Probleem: De "Tijdsreis" van de Robot

Stel je voor dat je de robot een opdracht geeft: "Ga naar punt A".

Voorwaartse analyse (Forward Reachability): Je wilt weten: "Als ik nu start op deze plek, waar kan de robot over 5 minuten zijn?"
Terugwaartse analyse (Backward Reachability): Je wilt weten: "Als de robot over 5 minuten in een gevaarlijke valkuil belandt, waar moet hij dan nu beginnen om daar niet in te vallen?"

Het oude probleem was dat je de robot vaak moest "ontrollen" (zoals een lange filmrol). Je keek naar elke seconde apart. Bij een lange tijdspanne werd die filmrol zo lang dat de computer er van kapot ging (te veel rekenkracht nodig).

2. De Oplossing: Het "Tweeling-Mapje" (State-Pair Sets)

In plaats van de filmrol één voor één af te rollen, maken deze onderzoekers een tweeling-kaart.
Stel je voor dat je twee foto's maakt: één van de robot nu en één van de robot over 5 minuten. Ze plakken deze twee foto's aan elkaar op een kaart.

De Magie: Ze gebruiken een wiskundige vorm (de Hybride Zonotoop) die precies kan beschrijven welke paren van "nu" en "later" mogelijk zijn.
Het Voordeel: Ze hoeven de film niet af te rollen. Ze kijken direct naar het verband tussen het begin en het einde. Dit is als het hebben van een magische bril die direct ziet welke routes veilig zijn, zonder de hele reis te hoeven maken.

3. Het Uitdaging: De "Knipperende Lichten" (ReLU Activaties)

De robot gebruikt een soort schakelaar die heet ReLU. Deze schakelaar doet soms raar: als de input negatief is, doet hij niets (0), maar als hij positief is, laat hij alles door.

Het Probleem: Als de input precies op de rand zit (net negatief of net positief), wordt het wiskundig heel lastig. De "Hybride Zonotoop" wordt dan enorm groot en complex, omdat hij alle mogelijke scenario's moet bijhouden. Het is alsof je een doos vol met duizenden losse puzzelstukjes krijgt in plaats van één nette doos.

4. De Slimme Truc: De "Driehoeks-Filter"

Om de computer niet te laten ontploffen van de rekenkracht, hebben de auteurs een slimme truc bedacht. Ze noemen dit een instelbare ontspanningsschema.

Stel je voor dat je een grote berg onzekerheid hebt. Je wilt weten welke stukjes echt belangrijk zijn en welke je mag negeren.

Ze kijken naar elke "knipperende schakelaar" (ReLU) en berekenen een score: hoe groot is het "gat" in de zekerheid? (Ze noemen dit de "driehoeks-oppervlakte").
De Regels:
- Als de schakelaar een groot gat heeft (hoog risico), houden ze de exacte, moeilijke wiskunde aan.
- Als de schakelaar een klein gat heeft (laag risico), zeggen ze: "Nou ja, dat is wel goed zo," en vervangen ze het door een simpele driehoek (een benadering).

Dit is als het sorteren van je wasmand. Je wast de dure, delicate kleding (de grote gaten) met de hand, maar de oude T-shirts (de kleine gaten) gooi je in de wasmachine. Zo bespaar je tijd, maar blijft je kleding (de veiligheid) toch schoon.

Je kunt zelf instellen hoeveel "was" je wilt doen. Meer was = veiliger maar trager. Minder was = sneller maar iets minder precies.

5. Veiligheidstest: De "Valkuil-Check"

Met deze methode kunnen ze nu twee dingen doen:

Voorspellen: "Kijk, als we hier beginnen, komen we nooit in de valkuil."
Terugzoeken: "Kijk, als we in de valkuil belanden, dan moet je niet hier beginnen."

Ze kunnen zelfs een lijst maken van gevaarlijke routes: "Als je start op punt A, en je doet X, dan beland je in gevaar." Dit helpt ingenieurs om de robot te programmeren zodat hij die routes nooit kiest.

Samenvatting

Dit paper is als het bouwen van een slimme veiligheidscontrole voor robots met geheugen.

Ze gebruiken een tweeling-kaart om het verleden en de toekomst tegelijk te bekijken (zonder alles één voor één te rekenen).
Ze gebruiken een slimme filter om de moeilijkste wiskundige problemen alleen op te lossen waar het echt nodig is, en het makkelijke werk te benaderen.
Het resultaat: Een systeem dat sneller is dan de oude methoden, maar net zo veilig (of zelfs veiliger), zodat we robots kunnen vertrouwen in gevaarlijke situaties.

Kortom: Ze hebben een manier gevonden om de "geest" van een robot te begrijpen zonder de hele geest te hoeven analyseren, zodat we zeker weten dat hij niet tegen de muur rijdt.

Each language version is independently generated for its own context, not a direct translation.

Hier is een gedetailleerde technische samenvatting van het artikel "Forward and Backward Reachability Analysis of Closed-loop Recurrent Neural Networks via Hybrid Zonotopes" in het Nederlands.

Titel: Forward and Backward Reachability Analysis of Closed-loop Recurrent Neural Networks via Hybrid Zonotopes

Auteurs: Yuhao Zhang en Xiangru Xu (University of Wisconsin-Madison)

1. Probleemstelling

Recurrente Neuronale Netwerken (RNN's) worden steeds vaker gebruikt voor het modelleren van complexe dynamische systemen en voor besturingsdoeleinden vanwege hun vermogen om temporele afhankelijkheden te modelleren via hun verborgen toestandsstructuur. Ondanks hun populariteit vormen ze een veiligheidsrisico in kritieke toepassingen vanwege problemen zoals de "exploding gradient" en hoge gevoeligheid voor inputverstoringen.

De huidige literatuur op het gebied van verificatie van RNN's heeft twee belangrijke beperkingen:

Schalbaarheid: Bestaande methoden die RNN's "unrollen" (omzetten naar grote Feedforward Neural Networks) worden onhandelbaar bij langere tijdstappen.
Beperkte richting: Bestaande bereikbaarheidsanalyses focussen voornamelijk op forward reachability (voorspellen van toekomstige toestanden). Backward reachability (het identificeren van onveilige starttoestanden die leiden tot een onveilige set) is cruciaal voor het synthetiseren van veilige besturing en het vinden van adversariële inputs, maar is in de literatuur voor gesloten-lus RNN-systemen nauwelijks onderzocht.

Het doel van dit werk is het ontwikkelen van een methode om zowel exacte als benaderde forward en backward reachable sets te berekenen voor gesloten-lus RNN-systemen (waarbij de plant en de controller beide door RNN's worden gemodelleerd) zonder het netwerk te unrollen, en dit met een instelbaar compromis tussen nauwkeurigheid en rekentijd.

2. Methodologie

De kern van de voorgestelde aanpak ligt in het gebruik van Hybride Zonotopen (HZ) en een nieuw concept genaamd State-Pair Sets.

A. Hybride Zonotopen (Hybrid Zonotopes)

Een hybride zonootop is een verzameling die zowel continue als binaire (discrete) variabelen kan modelleren, wat ideaal is voor het exacte modelleren van ReLU-activatiefuncties (die niet-lineair en stuksgewijs lineair zijn). Een HZ wordt gedefinieerd door continue generators, binaire generators en lineaire gelijkheidsbeperkingen.

B. State-Pair Sets (Toestands-paar verzamelingen)

In plaats van het RNN te unrollen, introduceert de auteurs het concept van een state-pair set $S_x(X, t)$ . Dit is de verzameling van paren $(x_1, x_t)$ , waarbij $x_1$ de initiële toestand is en $x_t$ de toestand op tijdstap $t$ , onder de voorwaarde dat ze voldoen aan de dynamica van het gesloten-lus systeem.

Door deze paren te modelleren als HZ's, wordt de relatie tussen start- en eindtoestand exact vastgehouden zonder de tijdstap-explosie die optreedt bij unrolling.
De methode gebruikt een "constrained product" operatie om de verborgen toestanden van opeenvolgende lagen en tijdstappen te koppelen.

C. Exacte Bereikbaarheid

Forward Reachable Set (FRS): Wordt berekend door de state-pair set te projecteren op de eindtoestand $x_t$ na intersectie met de initiële set $X_1$ .
Backward Reachable Set (BRS): Wordt berekend door de state-pair set te projecteren op de starttoestand $x_1$ na intersectie met de doelset (bijv. een onveilige set) $T$ .
De auteurs bewijzen dat deze sets exact kunnen worden weergegeven als HZ's door het gebruik van de grafiek van de ReLU-functie, die exact als een HZ kan worden geformuleerd.

D. Schaalbaarheidsverbetering: Tunable Relaxation Scheme

De exacte berekening leidt tot een exponentiële groei in complexiteit (aantal binaire variabelen) naarmate het aantal "onstabiele" ReLU-eenheden (waar de input het interval $[0, 0]$ overschrijdt) toeneemt. Om dit op te lossen, stellen de auteurs een instelbaar relaxatieschema voor:

Score-methode: Voor elke onstabiele ReLU-eenheid wordt een "triangle-area score" berekend. Deze score is het oppervlak van het driehoekige gebied dat ontstaat bij het vervangen van de exacte ReLU-grafiek door een convexe relaxatie (de standaard driehoek relaxatie).
Selectie: De onstabiele ReLU's worden gesorteerd op deze score.
Binary Limit ( $N_b$ ): De auteurs stellen een limiet in op het aantal binaire variabelen dat mag worden behouden. De ReLU's met de hoogste scores (grootste impact op de nauwkeurigheid) worden exact gemodelleerd, terwijl de rest wordt benaderd door de minder nauwkeurige, maar goedkopere, convexe driehoek relaxatie.
Dit creëert een expliciete trade-off: een hogere $N_b$ leidt tot nauwkeurigere resultaten (dicht bij exact), terwijl een lagere $N_b$ de rekentijd verlaagt.

E. Veiligheidsverificatie

Op basis van de berekende reachable sets wordt een voldoende voorwaarde afgeleid voor veiligheidsverificatie:

Een systeem is veilig als de forward reachable sets geen intersectie hebben met de onveilige set $O$ .
Alternatief: Als de backward reachable set van de onveilige set geen intersectie heeft met de initiële set $X_1$ .
Als verificatie faalt, kunnen de backward sets worden gebruikt om expliciete onveilige trajecten te reconstrueren.

3. Belangrijkste Bijdragen

Exacte Zonder Unrolling: De eerste methode die exacte forward en backward reachable sets berekent voor gesloten-lus RNN-systemen met ReLU-activaties, weergegeven als hybride zonotopen, zonder het netwerk te unrollen.
State-Pair Formulering: Introductie van state-pair sets en hidden-state-pair sets om de temporele en structurele afhankelijkheden van RNN's direct te modelleren binnen de HZ-framework.
Instelbare Trade-off: Een nieuw relaxatieschema dat ReLU-eenheden rangschikt op basis van een "triangle-area score". Dit stelt de gebruiker in staat om het aantal binaire variabelen te beperken, waardoor een expliciete afweging tussen computatiecomplexiteit en benaderingsnauwkeurigheid mogelijk is.
Veiligheidsverificatie en Onveilige Trajecten: Een afgeleide voorwaarde voor veiligheidsverificatie en een mechanisme om, bij schending van veiligheid, expliciete onveilige inputsequenties te identificeren via backward reachability.

4. Resultaten

De auteurs testen hun methode op twee voorbeelden:

Voorbeeld 1 (Simulatie): Een gesloten-lus RNN dat een dubbele integrator bestuurt. De resultaten tonen aan dat de grootte van de benaderde reachable sets monotoon afneemt naarmate de parameter $N_b$ (het aantal behouden binaire variabelen) toeneemt. Dit bevestigt de controleerbaarheid van de nauwkeurigheid.
Voorbeeld 2 (Massa-Veer-Dempersysteem): Een systeem met twee karretjes, gemodelleerd door een RNN-plant en een MPC-controller (die ook een RNN is).
- Er werden forward reachable sets berekend tot $T=5$ . De exacte sets (met $N_b$ gelijk aan het totale aantal onstabiele ReLU's) lagen volledig binnen de over-benaderde sets (met een lagere $N_b$ ).
- Er werd een backward reachability analyse uitgevoerd om een onveilige set te vinden. De methode slaagde erin om de set van initiële toestanden te identificeren die binnen 5 stappen de onveilige regio bereiken, en kon vervolgens de bijbehorende onveilige trajecten reconstrueren.

De implementatie in Python toonde aan dat de methode schaalbaar is en effectief werkt op standaard hardware.

5. Betekenis en Impact

Dit werk is significant omdat het een brug slaat tussen de theorie van reachability analysis en de praktische toepassing van RNN's in veiligheidskritieke besturingssystemen.

Unieke combinatie: Het is een van de eerste werken dat zowel forward als backward reachability voor gesloten-lus RNN-systemen behandelt. Backward reachability is essentieel voor het begrijpen van kwetsbaarheden en het synthetiseren van veilige besturing, maar was eerder moeilijk te berekenen voor RNN's.
Efficiëntie: Door het vermijden van unrolling en het introduceren van een gerichte relaxatie, maakt de methode verificatie mogelijk voor systemen waar eerdere methoden (zoals unrolling of star sets) te traag of te conservatief zouden zijn.
Veiligheid: Het biedt een wiskundig onderbouwde manier om te garanderen dat een AI-gestuurde controller geen onveilige toestanden zal bereiken, of om precies te weten welke startcondities dit risico met zich meebrengen.

Samenvattend biedt dit artikel een robuust, flexibel en schaalbaar raamwerk voor het verifiëren van de veiligheid van complexe dynamische systemen die bestuurd worden door Recurrente Neuronale Netwerken.