Resumo Técnico: Atribuição Ancorada em Restrições para Políticas Neurais de OC

Declaração do Problema

Políticas neurais para Otimização Combinatória (OC) são cada vez mais eficazes na resolução de problemas de roteamento e agendamento, mas seus processos de tomada de decisão permanecem opacos. Métodos padrão de Inteligência Artificial Explicável (XAI), como atribuição de características baseada em gradientes (por exemplo, Gradientes Integrados, DeepLIFT), falham no domínio da OC porque operam no nível de características em vez do nível de restrições. Problemas de OC são definidos por famílias de restrições (por exemplo, capacidade, janelas de tempo, precedência), que frequentemente abrangem múltiplos tensores de características de diferentes ranks. Consequentemente, tensores de características de alto rank podem acumular massa de gradiente excessiva mesmo quando não representam a restrição vinculante que impulsiona uma decisão, levando a atribuições desalinhadas.

Explicadores específicos de OC existentes frequentemente dependem de contrafactuais não restritos que violam a viabilidade do problema (por exemplo, demanda negativa ou janelas de tempo invertidas) ou visam modelos substitutos estáticos em vez do processo de decodificação autoregressiva de políticas neurais. Há uma falta de métodos que decomponham decisões neurais de OC por famílias de restrições enquanto fornecem garantias formais de viabilidade.

Metodologia: Atribuição Ancorada em Restrições (CAX)

O artigo propõe o CAX, um framework composto por três primitivas que vinculam explicações neurais à estrutura de otimização subjacente:

1. Atribuição $\Lambda$

Este método decompõe o gradiente de decisão de uma política por família de restrições em vez de características individuais. Para uma decisão $a_t$ no passo $t$, a atribuição à família de restrições $c_k$ é calculada como:
$$\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|$$
Aqui, $\lambda^*_k$ representa o multiplicador de Lagrange (valor dual) do relaxamento de Programação Linear (PL) do problema, agregado por família. Essa escala garante que a atribuição reflita a "pressão vinculante" da restrição. O framework suporta três backends para estimar $\lambda^*$:

• PL: Valores duais do relaxamento de PL.
• Subgrad: Ascensão de subgradiente de Lagrange em um subproblema relaxado.
• Proxy: Ponderação uniforme ($\lambda_k=1$), equivalente a um gradiente particionado por restrição $\times$ característica.

2. Subconjunto Suficiente Bonferroni-PAC

Para determinar o conjunto mínimo de nós necessário para preservar a decisão de argmax da política, o método adapta a abordagem de Koriche et al. para decodificadores de OC. Busca-se o menor subconjunto $S$ tal que a probabilidade da política manter sua decisão sob perturbações gaussianas seja de pelo menos $1-\epsilon$.

• Um algoritmo ganancioso percorre a ordenação de atribuição para encontrar o menor $k$ onde a taxa de preservação empírica excede $1-\epsilon$.
• Para controlar a taxa de erro familiar em consultas adaptativas (até $k_{max}$), uma correção de Bonferroni é aplicada ao limite de Hoeffding. Isso gera um tamanho de amostra $M_{bonf}$ que garante um limite $(1-\delta)$-PAC ao longo da ordenação gananciosa.

3. Contrafactuais CSP-Certificados (CF)

Ao contrário de contrafactuais padrão no estilo Wachter que minimizam normas de perturbação sem garantias de viabilidade, o CAX impõe um certificado de viabilidade combinatória.

• Processo: Um amostrador gera perturbações para inverter a decisão de argmax. Candidatos passam primeiro por verificações aritméticas (por exemplo, limites de campo).
• Certificação: O melhor candidato é verificado contra um modelo de decisão-viabilidade de Programação por Restrições (CP) (implementado via CP-SAT).
• Sinal de Julgamento: A família que carrega a maior massa $L_1$ em uma perturbação de inversão certificada por CSP serve como um sinal de verdade fundamental para a sensibilidade local da política. Este sinal é invariante a normas de perturbação ($L_1, L_2, L_\infty$) e normalização de dimensão.

Contribuições Principais

1. Decomposição no Nível de Restrições: O CAX é o primeiro método a decompor decisões de políticas neurais de OC por famílias de restrições usando duais de relaxamento de PL, corrigindo problemas de classificação incorreta inerentes à atribuição no nível de características.
2. Contrafactuais Certificados de Viabilidade: Introduz um processo de geração de contrafactuais que adere estritamente às restrições do problema por meio de modelos de decisão-viabilidade de CSP, distinguindo-se de métodos de XAI não restritos.
3. Subconjuntos Suficientes PAC: Fornece um limite corrigido por Bonferroni e controlado por Hoeffding sobre o tamanho de subconjuntos de explicação suficientes para políticas neurais de OC.
4. Julgamento Empírico: O framework utiliza o sinal derivado de CF para validar backends de atribuição, demonstrando que duais de PL salvam a precisão da atribuição quando os ranks de tensores de características e as restrições vinculantes estão desalinhados.

Resultados Experimentais

O framework foi avaliado em três problemas distintos de OC: Roteamento de Veículos com Capacidade e Janelas de Tempo (CVRPTW), Problema de Orientação (OP) e Problema de Agendamento de Job-Shop Flexível (FJSP).

• Concordância com o Sinal CF:
  • CVRPTW: A atribuição $\Lambda$ ancorada em PL correspondeu ao sinal derivado de CF em 96,5% dos casos ($n_{cert}=344$), superando significativamente o gradiente proxy (75,0%). A diferença (+0,215) foi estatisticamente significativa (McNemar $p \le 10^{-14}$).
  • OP: A atribuição ancorada em PL alcançou 77,2% de concordância ($n_{cert}=281$) versus 35,2% para o proxy (diferença de +0,420, $p \le 10^{-14}$).
  • FJSP: Neste regime "alinhado por rank" onde tensores de alta massa correspondem a famílias vinculantes, tanto os backends de PL quanto de proxy alcançaram 100% de concordância em todas as 59 inversões certificadas, confirmando a previsão teórica de que duais de PL não adicionam informações extras quando os ranks estão alinhados.
• Taxas de Viabilidade: Os contrafactuais certificados por CSP mantiveram alta viabilidade. A filtragem aritmética sozinha aprovou 100% dos vencedores, enquanto uma linha de base não restrita correspondente aprovou apenas 19,3% dos candidatos.
• Subconjuntos PAC: No CVRPTW, subconjuntos PAC corrigidos por Bonferroni tiveram uma média de 5,0 nós por passo ($M=70, \epsilon=\delta=0,2$).

Significado e Alegações

O artigo alega que o CAX fornece uma abordagem rigorosa e fundamentada em restrições para explicar políticas neurais de OC. Seu significado principal reside em demonstrar que duais de PL são necessários para atribuição precisa apenas quando os ranks de tensores de características estão desalinhados com a família de restrição vinculante. Quando eles se alinham, métodos mais simples bastam; quando se desalinharem, métodos no nível de características falham, e métodos ancorados em PL recuperam o sinal correto no nível de restrição.

O framework é modesto em seu escopo: requer apenas um modelo de viabilidade (implementado aqui como CSP) e opera como uma ferramenta de análise post-hoc. Não alega resolver a otimização completa do reticulado de subconjuntos (subconjuntos PAC ótimos exatos permanecem um problema aberto), mas fornece um limite conservador e certificado via ordenação gananciosa. O trabalho estabelece um novo benchmark para avaliar XAI em OC usando contrafactuais certificados por CSP como sinal de julgamento, indo além da importância heurística de características para validade baseada em restrições.