DCFO: Density-Based Counterfactuals for Outliers -- Additional Material

Résumé Technique : DCFO - Contrefactuels Basés sur la Densité pour les Valeurs Aberrantes

Énoncé du Problème
La détection des valeurs aberrantes est cruciale pour identifier des anomalies dans des domaines tels que la détection de fraude et le diagnostic de pannes système. Cependant, expliquer pourquoi un point de données spécifique est signalé comme une valeur aberrante reste un défi majeur. Bien que les explications contrefactuelles — l'identification des modifications minimales requises pour altérer la prédiction d'un modèle — soient une technique populaire en IA explicable (XAI), les méthodes existantes peinent avec les algorithmes de détection de valeurs aberrantes, en particulier le Facteur de Valeur Aberrante Local (LOF).

Le LOF quantifie le caractère aberrant basé sur la densité locale relative. Un défi fondamental dans la génération de contrefactuels pour le LOF réside dans son caractère non continu : de petites modifications d'une observation peuvent altérer brusquement son ensemble de $k$ plus proches voisins, provoquant des sauts discontinus dans le score d'aberrance. Cette discontinuité rend les méthodes d'optimisation standard basées sur le gradient inefficaces, car elles reposent sur des transitions de prédiction lisses. À l'inverse, les approches alternatives comme l'optimisation bayésienne ou les algorithmes génétiques, qui ne nécessitent pas de gradients, entraînent souvent des coûts de calcul prohibitifs dans des contextes de haute dimension ou échouent à produire des contrefactuels valides de manière cohérente. De plus, de nombreuses méthodes de contrefactuels existantes sont conçues pour des tâches de classification et ne tiennent pas compte de la nature déséquilibrée spécifique de la détection de valeurs aberrantes ni des caractéristiques souvent non actionnables présentes dans les données réelles.

Méthodologie : DCFO
Les auteurs proposent les Contrefactuels Basés sur la Densité pour les Valeurs Aberrantes (DCFO), une méthode spécifiquement conçue pour générer des explications contrefactuelles pour le LOF. L'innovation centrale de DCFO est l'exploitation de la structure interne du LOF pour permettre une optimisation efficace basée sur le gradient malgré la non-continuité sous-jacente.

1. Partitionnement par Régions : DCFO partitionne l'espace des données en régions où le score LOF se comporte de manière lisse. Une région est définie par une « clé » unique $K(x)$, qui encode l'ensemble des $k$ plus proches voisins d'un point $x$ et les $k$ plus proches voisins de chacun de ces voisins. Au sein de toute telle région $R_K$, l'ensemble des points influençant le calcul du LOF reste fixe.
2. Différentiabilité : Les auteurs démontrent qu'au sein d'une région spécifique $R_K$, la fonction de score LOF, notée $LOF_K(x)$, est continue et différentiable presque partout (en supposant une fonction de distance bien comportée comme la distance euclidienne). Cette propriété permet l'utilisation d'optimiseurs efficaces basés sur le gradient.
3. Processus d'Optimisation :
   • L'algorithme commence avec une valeur aberrante $p_i$ et calcule sa clé de région $K$.
   • Il résout un problème d'optimisation contraint pour trouver un point $x$ qui minimise la distance à $p_i$ sous la contrainte $LOF_K(x) \leq t$ (où $t$ est le seuil d'aberrance).
   • L'optimisation utilise la Programmation Séquentielle des Moindres Carrés (SLSQP).
   • Si l'optimiseur sort de la région actuelle (c'est-à-dire que la clé change), l'algorithme redémarre récursivement l'optimisation depuis le nouveau point en utilisant la clé de la nouvelle région.
   • Pour assurer la diversité, la méthode maintient une file d'attente d'exploration de points ayant franchi des frontières de régions, lui permettant de générer plusieurs contrefactuels distincts en initiant de nouvelles optimisations à partir de ces points.
4. Gestion des Contraintes :
   • Caractéristiques Non Actionnables : DCFO permet aux utilisateurs de spécifier des caractéristiques immuables (par exemple, l'âge). L'optimiseur est restreint à l'ajustement des seules variables actionnables tout en maintenant les caractéristiques non actionnables fixes.
   • Plausibilité : En ciblant des scores LOF plus faibles (qui correspondent à une densité locale plus élevée), la méthode guide naturellement les contrefactuels vers des régions réalistes et à haute densité de l'espace des caractéristiques, évitant ainsi les valeurs aberrantes implausibles.

Contributions Clés

• Première Méthode de Contrefactuels Spécifique au LOF : DCFO est la première méthode explicitement conçue pour générer des contrefactuels pour l'algorithme du Facteur de Valeur Aberrante Local.
• Innovation Algorithmique : Elle introduit une stratégie de partitionnement de l'espace qui transforme le problème LOF non différentiable en une série de sous-problèmes différentiables, permettant l'utilisation de l'optimisation basée sur le gradient.
• Gestion des Caractéristiques : La méthode intègre des mécanismes pour gérer les caractéristiques non actionnables, générer plusieurs contrefactuels diversifiés et assurer la plausibilité par le ciblage de la densité.
• Validation Empirique : Les auteurs fournissent des benchmarks étendus sur 50 jeux de données OpenML.

Résultats Expérimentaux
L'article évalue DCFO par rapport à trois concurrents : Baycon (basé sur l'optimisation bayésienne), EACE (basé sur un algorithme génétique) et une Ligne de Base (déplaçant la valeur aberrante vers l'intrus le plus proche).

• Validité : DCFO a obtenu un score de validité de 1,00 sur l'ensemble des 50 jeux de données, ce qui signifie qu'il a trouvé avec succès un contrefactuel valide pour chaque valeur aberrante. En revanche, Baycon a obtenu 0,84, EACE 0,38 et la Ligne de Base 0,88. Les auteurs notent que EACE et la Ligne de Base ont souvent échoué à produire des contrefactuels valides en raison du paysage non continu du LOF.
• Proximité : DCFO a systématiquement produit des contrefactuels plus proches des valeurs aberrantes originales que les concurrents. L'analyse statistique utilisant des diagrammes de différence critique (test de Nemenyi) a confirmé que la performance de proximité de DCFO était significativement meilleure que celle de Baycon, qui s'est classé deuxième.
• Diversité : Lors de la génération de multiples contrefactuels, DCFO a démontré une supériorité statistiquement significative en termes de diversité par rapport aux autres méthodes, offrant une gamme plus large d'alternatives actionnables.
• Caractéristiques Non Actionnables : Dans les expériences où un sous-ensemble de caractéristiques était restreint, DCFO a maintenu une validité plus élevée et une meilleure proximité que Baycon, démontrant une robustesse face aux contraintes de caractéristiques.
• Efficacité : Bien que la Ligne de Base ait été la plus rapide, l'approche basée sur le gradient de DCFO s'est révélée significativement plus efficace que les approches bayésienne (Baycon) et génétique (EACE).

Signification et Revendications
L'article revendique que DCFO comble une lacune critique en XAI pour la détection de valeurs aberrantes en rendant l'algorithme LOF, largement utilisé mais opaque, interprétable. En partitionnant l'espace des données pour gérer les discontinuités du LOF, DCFO fournit des explications actionnables, valides et diversifiées que les méthodes existantes ne peuvent pas générer de manière fiable. Les auteurs soulignent que leur méthode explique non seulement pourquoi une instance est une valeur aberrante, mais fournit également des étapes concrètes et minimales pour la corriger, facilitant ainsi les mesures préventives et renforçant la confiance dans les systèmes de détection de valeurs aberrantes. Le travail est présenté comme une étape fondamentale, avec des travaux futurs suggérés pour étendre l'approche à d'autres variantes du LOF et minimiser le nombre de caractéristiques modifiées.