Riepilogo Tecnico: Attribuzione Ancorata ai Vincoli per Politiche Neurali di Ottimizzazione Combinatoria

Enunciato del Problema

Le politiche neurali per l'Ottimizzazione Combinatoria (CO) sono sempre più efficaci nella risoluzione di problemi di instradamento e schedulazione, tuttavia i loro processi decisionali rimangono opachi. I metodi standard di Intelligenza Artificiale Spiegabile (XAI), come l'attribuzione delle caratteristiche basata sul gradiente (ad esempio, Integrated Gradients, DeepLIFT), falliscono nel dominio della CO perché operano a livello di caratteristica piuttosto che a livello di vincolo. I problemi CO sono definiti da famiglie di vincoli (ad esempio, capacità, finestre temporali, precedenze), che spesso si estendono su più tensori di caratteristiche di rango variabile. Di conseguenza, i tensori di caratteristiche ad alto rango possono accumulare una massa di gradiente eccessiva anche quando non rappresentano il vincolo vincolante che guida una decisione, portando ad attribuzioni disallineate.

Gli spiegatori specifici per la CO esistenti spesso si basano su controfattuali non vincolati che violano la fattibilità del problema (ad esempio, domanda negativa o finestre temporali invertite) o prendono di mira modelli surrogati statici piuttosto che il processo di decodifica autoregressiva delle politiche neurali. Manca un metodo che decomponga le decisioni neurali CO per famiglie di vincoli fornendo al contempo garanzie formali di fattibilità.

Metodologia: Attribuzione Ancorata ai Vincoli (CAX)

Il documento propone CAX, un quadro che comprende tre primitive che collegano le spiegazioni neurali alla struttura di ottimizzazione sottostante:

1. Attribuzione $\Lambda$

Questo metodo scompone il gradiente decisionale di una politica per famiglia di vincoli piuttosto che per singole caratteristiche. Per una decisione $a_t$ al passo $t$, l'attribuzione alla famiglia di vincoli $c_k$ è calcolata come:
$$\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|$$
Qui, $\lambda^*_k$ rappresenta il moltiplicatore di Lagrange (valore duale) dal rilassamento di Programmazione Lineare (LP) del problema, aggregato per famiglia. Questa scalatura garantisce che l'attribuzione rifletta la "pressione vincolante" del vincolo. Il quadro supporta tre backend per la stima di $\lambda^*$:

• LP: Valori duali dal rilassamento LP.
• Subgrad: Ascesa del subgradiente di Lagrange su un sottoproblema rilassato.
• Proxy: Ponderazione uniforme ($\lambda_k=1$), equivalente a un gradiente partizionato per vincoli $\times$ caratteristica.

2. Sottogruppo Sufficiente di Bonferroni-PAC

Per determinare l'insieme minimo di nodi necessario per preservare la decisione argmax della politica, il metodo adatta l'approccio di Koriche et al. per i decoder CO. Cerca il sottoinsieme più piccolo $S$ tale che la probabilità che la politica mantenga la sua decisione sotto perturbazioni gaussiane sia almeno $1-\epsilon$.

• Un algoritmo greedy attraversa l'ordinamento dell'attribuzione per trovare il più piccolo $k$ in cui il tasso di preservazione empirico supera $1-\epsilon$.
• Per controllare il tasso di errore familiare su query adattive (fino a $k_{max}$), viene applicata una correzione di Bonferroni al limite di Hoeffding. Ciò produce una dimensione del campione $M_{bonf}$ che garantisce un limite $(1-\delta)$-PAC lungo l'ordinamento greedy.

3. Controfattuali Certificati CSP (CF)

A differenza dei controfattuali standard in stile Wachter che minimizzano le norme di perturbazione senza garanzie di fattibilità, CAX impone un certificato di fattibilità combinatoria.

• Processo: Un campionatore genera perturbazioni per invertire la decisione argmax. I candidati subiscono prima controlli aritmetici (ad esempio, limiti di campo).
• Certificazione: Il miglior candidato è verificato contro un modello di decisione-fattibilità di Programmazione a Vincoli (CP) (implementato tramite CP-SAT).
• Segnale di Adjudicazione: La famiglia che trasporta la maggiore massa $L_1$ in una perturbazione di inversione certificata CSP funge da segnale di verità fondamentale per la sensibilità locale della politica. Questo segnale è invariante rispetto alle norme di perturbazione ($L_1, L_2, L_\infty$) e alla normalizzazione dimensionale.

Contributi Chiave

1. Decomposizione a Livello di Vincolo: CAX è il primo metodo a decomporre le decisioni delle politiche neurali CO per famiglie di vincoli utilizzando i duali del rilassamento LP, correggendo le problematiche di errata classificazione intrinseche nell'attribuzione a livello di caratteristica.
2. Controfattuali Certificati di Fattibilità: Introduce un processo di generazione di controfattuali che aderisce strettamente ai vincoli del problema tramite modelli di decisione-fattibilità CSP, distinguendosi dai metodi XAI non vincolati.
3. Sottogruppi Sufficienti PAC: Fornisce un limite corretto da Bonferroni e controllato da Hoeffding sulla dimensione dei sottoinsiemi di spiegazione sufficienti per le politiche neurali CO.
4. Adjudicazione Empirica: Il quadro utilizza il segnale derivato dai CF per validare i backend di attribuzione, dimostrando che i duali LP salvano l'accuratezza dell'attribuzione quando i ranghi dei tensori di caratteristiche e i vincoli vincolanti sono disallineati.

Risultati Sperimentali

Il quadro è stato valutato su tre distinti problemi CO: Instradamento Veicolare con Capacità e Finestre Temporali (CVRPTW), Problema di Orientamento (OP) e Problema di Schedulazione Flessibile per Job-Shop (FJSP).

• Accordo con il Segnale CF:
  • CVRPTW: L'attribuzione $\Lambda$ ancorata a LP ha corrisposto al segnale derivato dai CF nel 96,5% dei casi ($n_{cert}=344$), superando significativamente il gradiente proxy (75,0%). La differenza (+0,215) è stata statisticamente significativa (McNemar $p \le 10^{-14}$).
  • OP: L'attribuzione ancorata a LP ha raggiunto un accordo del 77,2% ($n_{cert}=281$) contro il 35,2% per il proxy (differenza +0,420, $p \le 10^{-14}$).
  • FJSP: In questo regime "allineato al rango" in cui i tensori ad alta massa corrispondono alle famiglie vincolanti, sia i backend LP che proxy hanno raggiunto un accordo del 100% su tutti i 59 flip certificati, confermando la previsione teorica secondo cui i duali LP non aggiungono informazioni extra quando i ranghi sono allineati.
• Tassi di Fattibilità: I controfattuali certificati CSP hanno mantenuto un'alta fattibilità. Il solo filtraggio aritmetico ha superato il 100% dei vincitori, mentre una linea di base non vincolata abbinata ha superato solo il 19,3% dei candidati.
• Sottogruppi PAC: Su CVRPTW, i sottogruppi PAC corretti da Bonferroni hanno mediato 5,0 nodi per passo ($M=70, \epsilon=\delta=0,2$).

Significato e Affermazioni

Il documento afferma che CAX fornisce un approccio rigoroso e fondato sui vincoli per spiegare le politiche neurali CO. Il suo significato principale risiede nel dimostrare che i duali LP sono necessari per un'attribuzione accurata solo quando i ranghi dei tensori di caratteristiche sono disallineati con la famiglia di vincoli vincolante. Quando sono allineati, metodi più semplici sono sufficienti; quando sono disallineati, i metodi a livello di caratteristica falliscono e i metodi ancorati a LP recuperano il corretto segnale a livello di vincolo.

Il quadro è modesto nel suo ambito: richiede solo un modello di fattibilità (implementato qui come CSP) e opera come strumento di analisi post-hoc. Non afferma di risolvere l'ottimizzazione completa del reticolo dei sottoinsiemi (i sottoinsiemi PAC ottimali esatti rimangono un problema aperto) ma fornisce un limite conservativo e certificato tramite ordinamento greedy. Il lavoro stabilisce un nuovo benchmark per la valutazione dell'XAI nella CO utilizzando controfattuali certificati CSP come segnale di adjudicazione, andando oltre l'importanza euristica delle caratteristiche verso la validità basata sui vincoli.