Model interpretability through the lens of computational complexity

Abstract

El área de interpretabilidad o explicabilidad en inteligencia artificial busca estudiar y diseñar modelos que los seres humanos podamos comprender, y por tanto confiar en ellos y manejarlos eficazmente. A pesar de frecuentes afirmaciones diciendo que algunas clases de modelos son más interpretables que otras -- e.g., ``los modelos lineales son más interpretables que las redes neuronales profundas'' -- aún no existe una noción bien fundamentada de interpretabilidad que permita comparar formalmente diferentes clases de modelos. Tomamos un paso hacia una tal noción estudiando si las creencias populares sobre interpretabilidad pueden respaldarse desde la complejidad computacional. Nos enfocamos en preguntas de explicabilidad locales y post-hoc que, intuitivamente, intentan explicar por qué una entrada particular es clasificada de una cierta forma por un modelo dado. En pocas palabras, decimos que una clase C1 de modelos es más interpretable que otra clase C2, si la complejidad computacional de responder preguntas de explicabilidad post-hoc sobre modelos en C2 es superior que para modelos en C1. En este trabajo probamos que esta noción provee una buena contraparte teórica a las creencias actuales sobre interpretabilidad de modelos; en particular, mostramos que bajo nuestra definición y asumiendo hipótesis comunes de complejidad (tales como P =/= NP), tanto los modelos lineales como los modelos basados en árboles son más interpretables que las redes neuronales. Nuestro análisis de complejidad, sin embargo, no es capaz de diferenciar claramente entre modelos lineales y modelos basados en árboles, obteniendo diferentes resultados dependiendo del tipo particular de explicación post-hoc considerada. Aplicando un análisis de complejidad más fino, basado en complejidad parametrizada, podemos probar un resultado teórico sugiriendo que las redes neuronales con menos capas son más interpretables que las más profundas. Finalmente mostramos cómo el análisis teórico realizado permite aplicarse a problemas relacionados a la detección de sesgo, concluyendo también que estos problemas son más difíciles sobre redes neuronales que sobre modelos lineales o basados en árboles.