Technische Samenvatting: Constraint-Verankerde Toewijzing voor Neuronale CO-beleid

Probleemstelling

Neuronale beleidsregels voor Combinatoire Optimalisatie (CO) worden steeds effectiever in het oplossen van route- en planningsproblemen, maar hun besluitvormingsprocessen blijven ondoorzichtig. Standaardmethoden voor Verklaarbare AI (XAI), zoals op gradiënten gebaseerde kenmerktoewijzing (bijv. Integrated Gradients, DeepLIFT), falen in het CO-domein omdat ze werken op het niveau van kenmerken in plaats van op het niveau van beperkingen. CO-problemen worden gedefinieerd door families van beperkingen (bijv. capaciteit, tijdvensters, precedentie), die vaak meerdere kenmerktensors van verschillende rangen omvatten. Bijgevolg kunnen hoog-rangige kenmerktensors een overmatige gradiëntmassa accumuleren, zelfs wanneer ze niet de bindende beperking vertegenwoordigen die een beslissing drijft, wat leidt tot misgerichte toewijzingen.

Bestaande CO-specifieke uitleggers vertrouwen vaak op onbeperkte contrafactuelen die de haalbaarheid van het probleem schenden (bijv. negatieve vraag of omgekeerde tijdvensters) of richten zich op statische surrogate-modellen in plaats van het autoregressieve decoderingsproces van neuronale beleidsregels. Er ontbreekt een methode die neuronale CO-beslissingen decomposeert per beperkingenfamilie terwijl formele haalbaarheidsgaranties worden geboden.

Methodologie: Constraint-Verankerde Toewijzing (CAX)

Het artikel stelt CAX voor, een raamwerk dat drie primitieven omvat die neuronale verklaringen koppelen aan de onderliggende optimalisatiestructuur:

1. $\Lambda$-toewijzing

Deze methode decomposeert de beslissingsgradiënt van een beleid per beperkingenfamilie in plaats van per individueel kenmerk. Voor een beslissing $a_t$ op stap $t$ wordt de toewijzing aan beperkingenfamilie $c_k$ als volgt berekend:
$$\Lambda_k(t) = \lambda^*_k(x) \cdot \sum_{i \in F(c_k)} \sum_j |\nabla_{x^{(i)}_j} \log \pi_\theta(a_t | s_t) \cdot x^{(i)}_j|$$
Hier vertegenwoordigt $\lambda^*_k$ de Lagrangiaanse multiplier (dual waarde) uit de Lineaire Programmering (LP)-relaxatie van het probleem, geaggregeerd per familie. Deze schaling zorgt ervoor dat de toewijzing de "bindende druk" van de beperking weerspiegelt. Het raamwerk ondersteunt drie backends voor het schatten van $\lambda^*$:

• LP: Dual waarden uit de LP-relaxatie.
• Subgrad: Lagrangiaanse subgradiëntascentie op een gerelaxeerde deelvraag.
• Proxy: Uniforme weging ($\lambda_k=1$), equivalent aan een beperking-gepartitioneerde gradiënt $\times$ kenmerk.

2. Bonferroni-PAC Voldoende Subset

Om de minimale set knopen te bepalen die nodig is om de argmax-beslissing van het beleid te behouden, past de methode de aanpak van Koriche et al. toe voor CO-decoders. Het zoekt de kleinste subset $S$ zodat de kans dat het beleid zijn beslissing behoudt onder Gaussische verstoringen ten minste $1-\epsilon$ is.

• Een gulzig algoritme doorloopt de toewijzingsordening om de kleinste $k$ te vinden waarbij de empirische behoudsrate $1-\epsilon$ overschrijdt.
• Om het familiewijze foutpercentage te beheersen over adaptieve queries (tot $k_{max}$), wordt een Bonferroni-correctie toegepast op de Hoeffding-grens. Dit levert een steekproefgrootte $M_{bonf}$ op die een $(1-\delta)$-PAC-grens garandeert langs de gulzige ordening.

3. CSP-gecertificeerde Contrafactuelen (CF)

In tegenstelling tot standaard Wachter-stijl contrafactuelen die de norm van verstoringen minimaliseren zonder haalbaarheidsgaranties, dwingt CAX een combinatorisch haalbaarheidscertificaat af.

• Proces: Een sampler genereert verstoringen om de argmax-beslissing om te draaien. Kandidaten ondergaan eerst rekenkundige checks (bijv. veldgrenzen).
• Certificering: De beste kandidaat wordt geverifieerd tegen een Constraint Programming (CP) haalbaarheids-beslissingsmodel (geïmplementeerd via CP-SAT).
• Adjudicatiesignaal: De familie die de grootste $L_1$-massa draagt in een CSP-gecertificeerde draaiende verstoring, dient als grondwaarheidssignaal voor de lokale gevoeligheid van het beleid. Dit signaal is invariant voor verstoringnormen ($L_1, L_2, L_\infty$) en dimensienormalisatie.

Belangrijkste Bijdragen

1. Decompositie op Beperkingenniveau: CAX is de eerste methode die beslissingen van neuronale CO-beleidsregels decomposeert per beperkingenfamilie met behulp van LP-relaxatie-dualen, waardoor de misrangproblemen die inherent zijn aan toewijzing op kenmerkenniveau worden gecorrigeerd.
2. Haalbaarheidsgecertificeerde Contrafactuelen: Het introduceert een contrafactueel-generatieproces dat strikt adhereert aan probleembeperkingen via CSP-haalbaarheids-beslissingsmodellen, waardoor het zich onderscheidt van onbeperkte XAI-methoden.
3. PAC-Voldoende Subsets: Het biedt een Bonferroni-gecorrigeerde, Hoeffding-gereguleerde grens voor de grootte van voldoende uitleg-subsets voor neuronale CO-beleidsregels.
4. Empirische Adjudicatie: Het raamwerk gebruikt het CF-afgeleide signaal om toewijzingsbackends te valideren, en demonstreert dat LP-dualen de nauwkeurigheid van toewijzing redden wanneer kenmerk-rangen en bindende beperkingen niet op elkaar zijn afgestemd.

Experimentele Resultaten

Het raamwerk werd geëvalueerd op drie verschillende CO-problemen: Capacitated Vehicle Routing met Time Windows (CVRPTW), Orienteering Problem (OP) en Flexible Job-Shop Scheduling Problem (FJSP).

• Overeenstemming met CF-signaal:
  • CVRPTW: LP-verankerde $\Lambda$-toewijzing stemde in 96,5% van de gevallen overeen met het CF-afgeleide signaal ($n_{cert}=344$), wat significant beter was dan de proxy-gradiënt (75,0%). Het verschil (+0,215) was statistisch significant (McNemar $p \le 10^{-14}$).
  • OP: LP-verankerde toewijzing behaalde 77,2% overeenstemming ($n_{cert}=281$) versus 35,2% voor de proxy (+0,420 verschil, $p \le 10^{-14}$).
  • FJSP: In dit "rang-uitgelijnde" regime waarbij hoog-massige tensors overeenkomen met bindende families, behaalden zowel LP- als proxy-backends 100% overeenstemming op alle 59 gecertificeerde flips, wat de theoretische voorspelling bevestigt dat LP-dualen geen extra informatie toevoegen wanneer rangen uitgelijnd zijn.
• Haalbaarheidspercentages: De CSP-gecertificeerde contrafactuelen behielden een hoge haalbaarheid. Alleen rekenkundige filtering slaagde voor 100% van de winnaars, terwijl een gematchte onbeperkte baseline slechts 19,3% van de kandidaten slaagde.
• PAC-subsets: Op CVRPTW hadden Bonferroni-gecorrigeerde PAC-subsets gemiddeld 5,0 knopen per stap ($M=70, \epsilon=\delta=0,2$).

Betekenis en Beweringen

Het artikel beweert dat CAX een rigoureuze, op beperkingen gebaseerde aanpak biedt voor het verklaren van neuronale CO-beleidsregels. De primaire betekenis ligt in het aantonen dat LP-dualen noodzakelijk zijn voor nauwkeurige toewijzing alleen wanneer de rangen van kenmerktensors niet zijn uitgelijnd met de bindende beperkingenfamilie. Wanneer ze uitgelijnd zijn, volstaan eenvoudigere methoden; wanneer ze niet uitgelijnd zijn, falen methoden op kenmerkenniveau en herstellen LP-verankerde methoden het juiste signaal op beperkingenniveau.

Het raamwerk is bescheiden in zijn reikwijdte: het vereist slechts een haalbaarheidsmodel (hier geïmplementeerd als CSP) en fungeert als een post-hoc analyse-tool. Het claimt niet om de volledige optimalisatie van de subset-lattice op te lossen (exacte PAC-optimale subsets blijven een open probleem), maar biedt een conservatieve, gecertificeerde grens via gulzige ordening. Het werk vestigt een nieuwe benchmark voor het evalueren van XAI in CO door CSP-gecertificeerde contrafactuelen te gebruiken als adjudicatiesignaal, en gaat hiermee voorbij aan heuristische kenmerkgewicht naar validiteit op basis van beperkingen.