Más allá de Shapley: algoritmos eficientes para calcular los Shapley Values asimétricos

Resumen

Abordamos el problema de la explicabilidad en modelos de aprendizaje automático mediante métodos de feature attribution. En particular, consideramos una variante de los Shapley values conocida como Asymmetric Shapley Values (ASV), que permite incorporar conocimiento causal en explicaciones model-agnostic mediante el uso de un grafo causal. Mostramos que, en ciertos contextos en los que el cálculo de SHAP es #P-hard, el cálculo exacto de ASV puede realizarse polinomial. Para extender este resultado algorítmico, introducimos una noción de clases de equivalencia sobre los ordenamientos topológicos del grafo causal subyacente, lo cual resulta útil para reducir el tiempo de cómputo de ASV. En particular, presentamos un algoritmo en tiempo polinomial (en el número de clases de equivalencia) para calcularlo cuando el grafo causal es un árbol dirigido enraizado. Finalmente, desarrollamos un algoritmo para aproximar ASV en DAGs causales arbitrarios, basado en un procedimiento que muestrea ordenamientos topológicos uniformemente al azar. Para implementar este mecanismo de muestreo consideramos algoritmos conocidos así como alternativas más simples. Nuestros resultados experimentales demuestran la viabilidad práctica del enfoque propuesto en estructuras causales realistas.