Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogate

Dit artikel toont aan dat het gebruik van een reeds getraind, gesparseerd (gepruned) neuronaal netwerk als surrogate, zelfs zonder finetuning, leidt tot een beter oplosbaar optimalisatiemodel met betere oplossingen binnen een tijdslimiet dan het gebruik van het oorspronkelijke, grotere netwerk.

De kern

Optimalisatie met een "Versneden" Neuraal Netwerk: Een Surrogaat binnen een Surrogaat

Stel je voor dat je een zeer complexe, maar ondoorzichtige machine hebt. Laten we deze machine een "Zwarte Doos" noemen. Deze doos neemt een input (bijvoorbeeld een foto van een hond) en geeft een output (bijvoorbeeld: "dit is een hond").

Nu wil je een probleem oplossen met deze machine. Bijvoorbeeld: "Wat is de kleinste verandering die ik aan deze foto kan maken zodat de machine denkt dat het een kat is?" (Dit heet in de vaktaal 'verificatie' of het vinden van 'tegenstanders'). Of: "Welke input geeft de hoogste score?" (Dit is 'functiemaximalisatie').

Het probleem is dat deze "Zwarte Doos" (het neurale netwerk) zo groot en ingewikkeld is dat het voor een computer bijna onmogelijk is om snel een antwoord te vinden. Het is alsof je probeert een doolhof te doorlopen terwijl je blind bent en elke wand van het doolhof duizenden blokken groot is.

Het idee: "Versnijden" in plaats van "Opnieuw leren"

De auteurs van dit paper stellen een slimme, tegenintuïtieve oplossing voor. In plaats van de hele enorme machine te gebruiken, nemen ze een versneden (gepruned) versie.

De Analogie van de Boom:
Stel je een enorme, dichte eik voor (het oorspronkelijke netwerk). Deze boom heeft duizenden takken en bladeren. Als je wilt weten welke tak de sterkste is, moet je door de hele dichte kroon klimmen. Dat kost enorm veel tijd.
De auteurs zeggen: "Laten we 90% van de takken en bladeren eraf hakken."
Je krijgt nu een kale, dunne boom. Deze kale boom is veel makkelijker te beklimmen. Je kunt snel zien welke takken er nog staan.

Het verrassende geheim:
Normaal gesproken zou je denken: "Als ik 90% van de takken weghaalt, is de boom kapot en werkt hij niet meer goed."
In de wereld van neurale netwerken is dat niet altijd waar. Als je een netwerk eerst traint (leert) en daarna versnijdt, kun je vaak nog steeds een goed resultaat krijgen, als je het netwerk daarna even opnieuw traint (finetuning).

Maar hier komt de echte verrassing van dit paper: Je hoeft dat opnieuw trainen niet eens te doen!

De "Schaal binnen een Schaal" Strategie

De auteurs gebruiken een slimme truc, die ze een "surrogaat binnen een surrogaat" noemen.

1. De Oorspronkelijke Machine (De Dichte Boom): Dit is de zware, moeilijke machine die we eigenlijk willen gebruiken.
2. Het Versnede Netwerk (De Kale Boom): Dit is een versimpelde, snellere versie van de machine.
3. De Strategie:
   • We laten de computer eerst de Kale Boom (het versnede netwerk) doorzoeken. Omdat deze klein is, gaat dit razendsnel.
   • De computer vindt een kandidaat-oplossing in de Kale Boom (bijvoorbeeld: "Probeer deze foto aan te passen").
   • Vervolgens sturen we die kandidaat-oplossing naar de Dichte Boom (de oorspronkelijke machine) om te checken of het ook daar werkt.
   • Als het werkt, hebben we een oplossing gevonden!

Het grote inzicht:
Omdat de Kale Boom zo snel is, kan de computer in dezelfde tijd (bijvoorbeeld 5 minuten) duizenden kandidaten testen. Zelfs als de Kale Boom niet perfect is (bijvoorbeeld omdat ze hem niet opnieuw hebben getraind na het versnijden), vinden ze vaak sneller een goede oplossing dan wanneer ze direct de zware Dichte Boom proberen te doorzoeken.

Het is alsof je een schat zoekt in een groot bos.

• De oude manier: Je loopt blindelings door het hele dichte bos. Je bent na een uur nog niet bij de helft.
• De nieuwe manier: Je gebruikt een drone (het versnede netwerk) om snel het bos te scannen. De drone ziet misschien niet elk detail, maar hij vindt snel gebieden waar de grond er goed uitziet. Dan loop je alleen naar die specifieke plekken om te graven. Je vindt de schat veel sneller, zelfs als de drone niet perfect is.

Waarom is dit belangrijk?

1. Snelheid: Het vinden van oplossingen voor complexe problemen gaat veel sneller.
2. Geen extra training nodig: Meestal moet je een versneden netwerk opnieuw trainen om het weer goed te laten werken. Dat kost tijd en data. Dit paper laat zien dat je die stap kunt overslaan. Een "slechte" versneden machine is soms een betere gids dan een perfect getrainde, maar zware machine.
3. Toepassingen: Dit werkt goed voor het vinden van beveiligingslekken in AI (zoals het manipuleren van verkeersborden zodat een zelfrijdende auto denkt dat het een stopbord is) en voor het vinden van de beste instellingen in complexe systemen.

Samenvattend in één zin:

Door een enorme, trage AI-machine te "versnijden" tot een kleine, snelle versie en die te gebruiken als een snelle gids, vinden we betere oplossingen voor complexe problemen veel sneller, zelfs als die kleine versie niet meer perfect werkt.

Technische samenvatting

Probleemstelling

In het domein van constraint learning worden neurale netwerken vaak gebruikt als surrogate (vervanging) voor complexe, niet-lineaire of niet-convexe constraints of objectiefuncties binnen een optimalisatiemodel. Hoewel dit krachtig is, wordt de berekeningshaalbaarheid (tractability) van het resulterende model zwaar beïnvloed door de grootte van het neurale netwerk.

• De uitdaging: Het inbedden van een groot, vooraf getraind (dicht) neurale netwerk in een Mixed-Integer Linear Programming (MILP) formulering leidt vaak tot modellen die te groot zijn om binnen een redelijke tijd opgelost te worden door standaard MILP-oplossers.
• De beperking van bestaande methoden: Traditionele aanpakken om netwerken te vereenvoudigen (zoals pruning of snoeien) vereisen vaak een finetuning-stap (hertraining) om de prestaties van het netwerk te herstellen. Dit is echter problematisch als:
  1. De trainingsdata niet beschikbaar is.
  2. Het doel is om eigenschappen van het oorspronkelijke netwerk te verifiëren (waarbij finetuning het model zou veranderen).
  3. De rekentijd voor finetuning de voordelen van een kleiner model tenietdoet.

De centrale vraag van dit paper is: Hoe kunnen we een optimalisatiemodel oplossen dat een groot, vooraf getraind neurale netwerk bevat, zonder dat netwerk opnieuw te trainen, en toch efficiënte oplossingen te vinden?

Methodologie

De auteurs stellen een nieuwe aanpak voor: het gebruik van een gesnoeid (spars) neurale netwerk als surrogate voor het oorspronkelijke dichte netwerk, zonder het gesnoeide netwerk te finetunen.

1. Netwerk Pruning (Snoeien):

   • Het oorspronkelijke dichte netwerk ($D$) wordt gesnoeid om een sparsere versie ($S$) te creëren.
   • Er wordt gebruikgemaakt van Magnitude Pruning (MP): het verwijderen van verbindingen (gewichten) met de kleinste absolute waarde.
   • Er wordt onderscheid gemaakt tussen unstructured pruning (individuele gewichten verwijderen) en structured pruning (hele neuronen of lagen verwijderen).
   • Cruciaal: Het gesnoeide netwerk wordt niet gefinetuned. Het wordt direct gebruikt in zijn "ruwe" staat na het verwijderen van gewichten.

2. Surrogaat-strategie (Surrogate within a Surrogate):

   • In plaats van het MILP-model op het dichte netwerk $D$ op te lossen, wordt het model op het gesnoeide netwerk $S$ opgelost.
   • Omdat $S$ minder variabelen en constraints heeft (door de gesnoeide verbindingen), is het MILP-probleem veel sneller oplosbaar.
   • Validatie: Zodra een kandidaat-oplossing ($x$) wordt gevonden door de solver voor het gesnoeide netwerk, wordt deze direct doorgestuurd naar het oorspronkelijke dichte netwerk $D$ om de werkelijke output te berekenen.
   • Dit proces wordt herhaald binnen een tijdslimiet.

3. Toepassingscasussen:

   • Netwerkverificatie (Network Verification): Zoeken naar adversariële perturbaties (inputs die de classificatie veranderen). Het algoritme zoekt een input die op het gesnoeide netwerk een andere classificatie geeft, en verifieert dit vervolgens op het dichte netwerk.
   • Functiemaximalisatie (Function Maximization): Het vinden van de input die de output van het neurale netwerk maximaliseert. Het algoritme verzamelt veel mogelijke oplossingen van het gesnoeide netwerk en selecteert de beste die geldig is voor het dichte netwerk.

Belangrijkste Bijdragen

1. Paradigmaverschuiving: Het paper toont aan dat een neurale netwerk met slechtere inferentie-accuraatheid (door het ontbreken van finetuning na pruning) een beter surrogate kan zijn voor optimalisatieproblemen dan een nauwkeurig gefinetuned netwerk. De snelheidswinst door de sparsiteit weegt op tegen de nauwkeurigheidsverlies.
2. Efficiëntie zonder Finetuning: De auteurs bewijzen dat het overslaan van de standaard finetuning-stap niet alleen tijd bespaart, maar vaak leidt tot het vinden van betere oplossingen binnen een tijdslimiet, vooral bij hoge pruning-rates.
3. Empirische Validatie: Uitgebreide experimenten op MNIST en Fashion-MNIST voor verificatie, en op willekeurig gegenereerde grote netwerken voor maximalisatie, tonen de superioriteit van deze methode aan.

Resultaten

De experimenten leverden de volgende inzichten op:

• Netwerkverificatie:

  • De "gesnoeide runtime" (oplossen via het sparsere netwerk) was in 70% tot 98% van de gevallen sneller dan het direct oplossen van het dichte netwerk, afhankelijk van de pruning-rate.
  • Verrassend: Het niet finetunen van het netwerk gaf vaak betere resultaten dan wel finetunen, vooral bij lagere pruning-rates. Bij zeer hoge pruning-rates (bijv. 90-95%) hielp finetunen wel iets, maar de kosten van het finetunen maakten de totale methode vaak trager dan het direct oplossen van het dichte netwerk.
  • Unstructured Magnitude Pruning bleek superieur aan Random Pruning en Structured Pruning voor dit specifieke doel.
  • Zelfs netwerken met een nauwkeurigheid die dicht bij willekeurig gissen lag (na extreme pruning), waren effectief om adversariële voorbeelden te vinden.

• Functiemaximalisatie:

  • De methode leverde consistent betere oplossingen op voor grote en complexe netwerken (met veel lineaire regio's).
  • De prestaties verbeterden met toenemende breedte van het netwerk (meer neuronen per laag), wat contrasteert met de verificatietaken waar netwerkgrootte soms een negatief effect had.
  • De beste resultaten werden behaald bij de hoogste pruning-rates (95%) voor de grootste netwerken.

Betekenis en Conclusie

Dit werk biedt een kosteneffectieve strategie voor het oplossen van optimalisatieproblemen die complexe neurale netwerken bevatten. De kernboodschap is dat voor optimalisatiedoeleinden (zoals verificatie of maximalisatie) de structuur van het netwerk (sparsiteit) belangrijker is dan de nauwkeurigheid van de inferentie.

• Praktische impact: Onderzoekers en ingenieurs kunnen nu grote, vooraf getrainde netwerken gebruiken in optimalisatiemodellen zonder de noodzaak van dure hertraining of toegang tot trainingsdata.
• Theoretisch inzicht: Het paper daagt de intuïtie uit dat een "beter" surrogate-model altijd nauwkeuriger moet zijn. In het kader van constraint learning kan een "slechter" (maar sneller oplosbaar) model leiden tot betere eindresultaten binnen een beperkte rekentijd.

Samenvattend: Door een neurale netwerk te "vervagen" (prunen) en het direct als surrogate te gebruiken zonder finetuning, kunnen we complexere optimalisatieproblemen oplossen die anders onbereikbaar zouden zijn voor huidige MILP-solvers.