Resumen de Novel mathematical optimization Models for Group counterfactual Analysis

Jasone Ramírez Ayerbe

• español

  La inteligencia artificial y los algoritmos de aprendizaje automático son a menudo criticados por su falta de transparencia, siendo percibidos como “cajas negras” [Rudin, 2019].

  Esta opacidad es especialmente indeseable en la toma de decisiones de alto riesgo, que llevan aparejadas decisiones críticas para los ciudadanos como la asignación de beneficios so-ciales, la concesión de préstamos, el diagnóstico médico o decisiones relacionadas con pro-cedimientos legales [Azizi et al., 2018; Baesens et al., 2003; Zeng et al., 2022, 2017], con el peligro de producir resultados injustos para grupos en riesgo de sufrir discriminación [Besse et al., 2022; Miron et al., 2020, 2021]. La importancia de esta cuestión ha sido reconocida tanto por la industria como por las autoridades gubernamentales, incluida la Comisión Europea [European Commission, 2020; Goodman and Flaxman, 2017; Hupont et al., 2023]. En res-puesta a esta necesidad, la Inteligencia Artificial Explicable (XAI) [Du et al., 2019; Goethals et al., 2022; Jung et al., 2020; Molnar et al., 2020; Rudin et al., 2022; Zhang et al., 2019] ha experimentado un notable auge, y ha crecido sustancialmente la producción de trabajos que desarrollan nuevos métodos para abordar estos retos.

  En la Inteligencia Artificial Explicable, los modelos de clasificación supervisada buscan un buen equilibrio entre precisión de predicción e interpretabilidad. Una vez que el clasificador ha sido entrenado, sería conveniente tener procedimientos para identificar cómo deberían mo-dificarse las características de las instancias para ser clasificadas en la clase “buena”, por ejem-plo, para ser clasificados como un buen pagador para un préstamo, o una persona sana para una prueba médica, o un profesional adecuado en un proceso de selección de personal, o un acusado clasificado como no reincidente. En esta tesis se estudian dichas soluciones modifica-das, llamadas explicaciones contrafácticas, [Martens and Provost, 2014; Wachter et al., 2017]. Véase Artelt and Hammer [2019]; Guidotti [2022]; Karimi et al. [2022a]; Sokol and Flach [2019]; Stepin et al. [2021]; Verma et al. [2022] para revisiones bibliográficas recientes sobre Análisis Contrafáctico, y Browne and Swift [2020]; Freiesleben [2022]; Karimi et al. [2022a] para problemas relacionados que han aparecido en la literatura con nombres diferentes, como clasificación inversa o perturbaciones maliciosas.

  En esta tesis se estudian diferentes aspectos del problema de encontrar soluciones con-trafácticas usando problemas de optimización. Más concretamente, se aborda el Análisis Con-trafáctico Grupal, donde, en lugar de considerar una única instancia a la que se le asigna una sola explicación, consideramos un grupo de instancias para ser perturbadas y calculamos un conjunto de explicaciones para todas ellas. También estudiamos el problema cuando se tienen datos complejos y aplicamos el estudio más allá de la clasificación supervisada. A continua-ción, presentamos y motivamos los problemas abordados.

  El capítulo introductorio de esta tesis se basa en el trabajo de Carrizosa et al. [2024b]. Pre-sentamos el problema de Análisis Contrafáctico Grupal, proporcionando un análisis riguroso sobre los elementos que definen este problema. También se identifican vínculos con proble-mas clásicos en la literatura de Análisis de Localización Continua y Discreta, como el de la mediana, el del centro, o el problema de la suma mínima de distancias al cuadrado, y desta-camos los elementos novedosos, como las restricciones para garantizar que la probabilidad de ser clasificado en la clase positiva sea lo suficientemente alta.

  El Capítulo 2 se basa en tres trabajos diferentes, a saber, Carrizosa et al. [2024a], Carri-zosa et al. [2024b], y Lodi and Ramírez-Ayerbe [2024]. En este capítulo, presentamos varios nuevos modelos de optimización que cubren todas las reglas de asignación posibles entre con-trafácticos e instancias en el Análisis Contrafáctico Grupal. Primero, se presenta un modelo de asignación “one-for-one”, donde se incluyen diferentes restricciones que vinculan las explica-ciones, como la imposición de dispersión (sparsity) global o restricciones de distancia entre las explicaciones contrafácticas. En segundo lugar, se formulan e ilustran modelos de optimización para reglas de múltiple asignación, a saber, “many-for-one”, “one-for-all” y “one-for-many”. Para este último, también se estudia una versión dispersa, donde se incluye un nivel adicional de interpretabilidad. Resolvemos el problema de minimizar el número de explicaciones con-trafácticas necesarias para explicar un grupo de instancias. También se impone un número máximo de características que pueden cambiarse para todas las instancias que están vinculadas al mismo contrafáctico. Por lo tanto, no solo se detectan los contrafácticos representativos, sino también las características clave que necesitan cambiar en cada grupo. Se introduce un nuevo marco de generación de columnas diseñado para abordar eficazmente este problema, que, como se demuestra, tiene buenas propiedades de escalabilidad, rendimiento computacional y calidad de las soluciones. Los modelos se detallan para clasificadores lineales y bosques aleatorios, si bien el enfoque es válido para cualquier clasificador basado en puntuaciones (scores).

  El Capítulo 3 se basa en el trabajo de Carrizosa et al. [2023c]. En este capítulo, nos cen-tramos en la naturaleza de los datos, específicamente desarrollamos un nuevo modelo de opti-mización matemática para datos funcionales, cuando se utiliza la regla de asignación “one-for-one”. El objetivo es identificar las muestras del conjunto de datos a partir del cual se construye la explicación contrafáctica, y cómo se deben combinar para que la instancia individual y su contrafáctico estén lo más cerca posible. Desarrollamos un modelo flexible que permite: in-corporar varias medidas de distancia, incluida la popular distancia de deformación dinámica del tiempo (DTW); utilizar clasificadores basados en puntuaciones, específicamente bosques aleatorios; y lograr dos tipos de dispersión, en términos del número de atributos perturbados y en el número de muestras utilizadas para crear el contrafáctico.

  El Capítulo 4 se basa en el trabajo de Bogetoft et al. [2024], donde se aplican las ideas del análisis contrafáctico más allá de problemas de clasificación. En este capítulo, extende-mos el análisis contrafácticos al análisis envolvente de datos (DEA). El DEA se utiliza como una herramienta para comparar el rendimiento de una entidad o empresa con el de un grupo de éstas y mediante esta comparación asociar una eficiencia. Específicamente, para establecer el rendimiento de las mejores prácticas y evaluar qué tan eficientemente opera una empresa en comparación con este estándar, el DEA emplea programación lineal o entera mixta para modelar la correlación entre diversos inputs y outputs de la empresa. Definimos contrafácti-cos o “targets” en DEA como combinaciones alternativas de inputs y outputs que están cerca de los inputs y outputs originales de la empresa y que conducen a una eficiencia superior. Este problema se formula como un modelo de optimización binivel, que transformamos en uno de un solo nivel, utilizando las condiciones de optimalidad del problema DEA. Con nues-tra metodología, somos capaces de incluir varias formas de medir la proximidad y también tenemos la flexibilidad de elegir diferentes niveles de eficiencia deseados. Así, ampliamos la literatura existen sobre “targets” en benchmarking.

  Finalmente, las conclusiones y el trabajo futuro se discuten brevemente en el Capítulo 5.

• English

  In Explainable Artificial Intelligence, Supervised Classification models are sought to have a good trade-off between prediction accuracy and interpretability. Once the classifier has been trained, it would be convenient to have procedures to identify how records should be changed in their features to be classified in the "good" class, e.g., to be classified as a good payer for a loan or a healthy person for a medical condition. Such modified solutions, the so-called counterfactual explanations, are addressed in this thesis.

  This dissertation is devoted to extending the study of counterfactual analysis across different dimensions. Specially, we delve into group analysis, where, instead of considering a single instance to whom a single explanation is assigned, we consider a group of instances to be perturbed and calculate a tuple of explanations for all of them. We also take into account complex data and expand the study beyond Supervised Classification.

  In the Introduction, we introduce the Group Counterfactual Analysis problem, providing a critical discussion on the ingredients defining this problem.

  In Chapter 2, we present several novel optimization models for Group Counterfactual Analysis, covering all possible allocation rules between counterfactuals and instances. First, a one-for-one allocation model is presented, where different linking constraints are included, such as imposing global sparsity. Second, optimization models for multiple allocation rules, namely, many-for-one, one-for-all, and one-for-many are formulated and illustrated. For the latter one, another sparse version is also studied. We solve the problem of minimizing the number of counterfactual explanations needed to cover a group of instances, imposing a maximum number of features that can be changed for all the instances that are linked to the same counterfactual. A novel column generation framework is introduced to solve this problem. All the models are valid for score-based classifiers, and detailed for linear classifiers and additive tree models.

  In Chapter 3, we focus on the nature of the data, specifically we develop a novel mathematical optimization model for functional data, when the one-for-one allocation rule is used. The goal is to identify the samples of the dataset from which the counterfactual explanation is made of, as well as how they are combined so that the individual instance and its counterfactual are as close as possible. We develop a model that is flexible enough to: incorporate several distance measures, including the popular Dynamic Time Warping distance; be used for score-based classifiers, specifically detailing it for additive tree models; and achieve two types of sparsity, namely in terms of the number of features perturbed and the number of samples used to create the counterfactual.

  In Chapter 4 we apply the concept of Counterfactual Analysis beyond classification. Particularly, we extend it to Data Envelopment Analysis (DEA). DEA is used as a benchmarking tool to compare the performance of an entity or firm to that of a group of other firms, and by comparison associate its efficiency. Specifically, to establish the best practice performance and assess how efficiently a firm operates compared to this standard, DEA employs linear or mixed integer programming to model the correlation between various inputs and outputs of the firm. We define DEA counterfactuals or targets as alternative combinations of inputs and outputs that are close to the original inputs and outputs of the firm and lead to desired improvements in its efficiency. This problem is formulated as a bilevel optimization model, that we transform it to a single level one, by utilizing the optimality conditions of the DEA problem.

  Finally, conclusions and future work are briefly discussed in Chapter 5.