Resumen Técnico: Atribución Anclada a Restricciones para Políticas Neurales de Optimización Combinatoria

Enunciado del Problema

Las políticas neuronales para la Optimización Combinatoria (OC) son cada vez más efectivas para resolver problemas de enrutamiento y programación, pero sus procesos de toma de decisiones siguen siendo opacos. Los métodos estándar de Inteligencia Artificial Explicable (XAI), como la atribución de características basada en gradientes (por ejemplo, Gradientes Integrados, DeepLIFT), fallan en el dominio de la OC porque operan a nivel de características en lugar de a nivel de restricciones. Los problemas de OC se definen por familias de restricciones (por ejemplo, capacidad, ventanas de tiempo, precedencia), que a menudo abarcan múltiples tensores de características de rangos variables. En consecuencia, los tensores de características de alto rango pueden acumular una masa de gradiente excesiva incluso cuando no representan la restricción vinculante que impulsa una decisión, lo que conduce a atribuciones desalineadas.

Los explicadores específicos de OC existentes a menudo dependen de contrafactuales no restringidos que violan la factibilidad del problema (por ejemplo, demanda negativa o ventanas de tiempo invertidas) o se dirigen a modelos sustitutos estáticos en lugar del proceso de decodificación autoregresiva de las políticas neuronales. Existe una falta de métodos que descompongan las decisiones de OC neuronales por familias de restricciones mientras proporcionan garantías formales de factibilidad.

Metodología: Atribución Anclada a Restricciones (CAX)

El artículo propone CAX, un marco que comprende tres primitivas que vinculan las explicaciones neuronales con la estructura de optimización subyacente:

1. Atribución $\Lambda$

Este método descompone el gradiente de decisión de una política por familia de restricciones en lugar de por características individuales. Para una decisión $a_t$ en el paso $t$, la atribución a la familia de restricciones $c_k$ se calcula 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|$$
Aquí, $\lambda^*_k$ representa el multiplicador de Lagrange (valor dual) de la relajación de Programación Lineal (LP) del problema, agregado por familia. Este escalado asegura que la atribución refleje la "presión vinculante" de la restricción. El marco admite tres backends para estimar $\lambda^*$:

• LP: Valores duales de la relajación LP.
• Subgrad: Ascenso de subgradiente de Lagrange en un subproblema relajado.
• Proxy: Ponderación uniforme ($\lambda_k=1$), equivalente a un gradiente particionado por restricciones $\times$ característica.

2. Subconjunto Suficiente Bonferroni-PAC

Para determinar el conjunto mínimo de nodos requerido para preservar la decisión argmax de la política, el método adapta el enfoque de Koriche et al. para decodificadores de OC. Busca el subconjunto más pequeño $S$ tal que la probabilidad de que la política mantenga su decisión bajo perturbaciones gaussianas sea al menos $1-\epsilon$.

• Un algoritmo codicioso recorre el orden de atribución para encontrar el $k$ más pequeño donde la tasa de preservación empírica supera $1-\epsilon$.
• Para controlar la tasa de error familiar a través de consultas adaptativas (hasta $k_{max}$), se aplica una corrección de Bonferroni al límite de Hoeffding. Esto produce un tamaño de muestra $M_{bonf}$ que garantiza un límite $(1-\delta)$-PAC a lo largo del orden codicioso.

3. Contrafactuales Certificados por CSP (CF)

A diferencia de los contrafactuales estándar al estilo de Wachter que minimizan las normas de perturbación sin garantías de factibilidad, CAX impone un certificado de factibilidad combinatoria.

• Proceso: Un muestreador genera perturbaciones para invertir la decisión argmax. Los candidatos primero pasan por verificaciones aritméticas (por ejemplo, límites de campo).
• Certificación: El mejor candidato se verifica contra un modelo de decisión-factibilidad de Programación por Restricciones (CP) (implementado mediante CP-SAT).
• Señal de Adjudicación: La familia que transporta la mayor masa $L_1$ en una perturbación de inversión certificada por CSP sirve como una señal de verdad fundamental para la sensibilidad local de la política. Esta señal es invariante a las normas de perturbación ($L_1, L_2, L_\infty$) y a la normalización de dimensiones.

Contribuciones Clave

1. Descomposición a Nivel de Restricciones: CAX es el primer método que descompone las decisiones de políticas neuronales de OC por familias de restricciones utilizando duales de relajación LP, corrigiendo los problemas de clasificación incorrecta inherentes a la atribución a nivel de características.
2. Contrafactuales Certificados de Factibilidad: Introduce un proceso de generación de contrafactuales que se adhiere estrictamente a las restricciones del problema mediante modelos de decisión-factibilidad de CSP, distinguiéndose de los métodos XAI no restringidos.
3. Subconjuntos Suficientes PAC: Proporciona un límite corregido por Bonferroni y controlado por Hoeffding sobre el tamaño de los subconjuntos de explicación suficientes para políticas neuronales de OC.
4. Adjudicación Empírica: El marco utiliza la señal derivada de CF para validar los backends de atribución, demostrando que los duales LP recuperan la precisión de la atribución cuando los rangos de tensores de características y las restricciones vinculantes están desalineados.

Resultados Experimentales

El marco se evaluó en tres problemas de OC distintos: Enrutamiento de Vehículos con Capacidad y Ventanas de Tiempo (CVRPTW), Problema de Orientación (OP) y Problema de Programación Flexible de Tareas de Taller (FJSP).

• Acuerdo con la Señal CF:
  • CVRPTW: La atribución $\Lambda$ anclada a LP coincidió con la señal derivada de CF en el 96.5% de los casos ($n_{cert}=344$), superando significativamente al gradiente proxy (75.0%). La diferencia (+0.215) fue estadísticamente significativa (McNemar $p \le 10^{-14}$).
  • OP: La atribución anclada a LP logró un acuerdo del 77.2% ($n_{cert}=281$) frente al 35.2% para el proxy (diferencia +0.420, $p \le 10^{-14}$).
  • FJSP: En este régimen "alineado por rangos" donde los tensores de alta masa coinciden con las familias vinculantes, tanto los backends LP como proxy lograron un acuerdo del 100% en las 59 inversiones certificadas, confirmando la predicción teórica de que los duales LP no agregan información adicional cuando los rangos están alineados.
• Tasas de Factibilidad: Los contrafactuales certificados por CSP mantuvieron una alta factibilidad. El filtrado aritmético por sí solo aprobó el 100% de los ganadores, mientras que una línea base no restringida coincidente aprobó solo el 19.3% de los candidatos.
• Subconjuntos PAC: En CVRPTW, los subconjuntos PAC corregidos por Bonferroni promediaron 5.0 nodos por paso ($M=70, \epsilon=\delta=0.2$).

Significado y Afirmaciones

El artículo afirma que CAX proporciona un enfoque riguroso y fundamentado en restricciones para explicar políticas neuronales de OC. Su significado principal radica en demostrar que los duales LP son necesarios para una atribución precisa solo cuando los rangos de tensores de características están desalineados con la familia de restricciones vinculante. Cuando están alineados, métodos más simples son suficientes; cuando están desalineados, los métodos a nivel de características fallan y los métodos anclados a LP recuperan la señal correcta a nivel de restricciones.

El marco es modesto en su alcance: requiere solo un modelo de factibilidad (implementado aquí como CSP) y opera como una herramienta de análisis post-hoc. No afirma resolver la optimización completa del retículo de subconjuntos (los subconjuntos óptimos PAC exactos siguen siendo un problema abierto), pero proporciona un límite conservador y certificado mediante un ordenamiento codicioso. El trabajo establece una nueva referencia para evaluar XAI en OC mediante el uso de contrafactuales certificados por CSP como señal de adjudicación, avanzando más allá de la importancia heurística de las características hacia la validez basada en restricciones.