RNTI

MODULAD
Approximation des explications probabilistes via la minimisation super-modulaire
In EGC 2024, vol. RNTI-E-40, pp.361-368
Résumé
Calculer une explication abductive d'une instance vise à expliquer la prédiction faite. Cependant, vu nos limitations cognitives, les explications abductives sont parfois de trop grande taille pour être interprétables. Lorsque cela se produit, nous devons réduire la taille des explications tout en déterminant toujours la classe prédite avec une probabilité élevée. Dans ce travail, nous montrons que calculer de telles « explications probabilistes » est NP-difficile, même pour la classe restreinte des arbres de décision. Afin de contourner le problème, nous étudions dans ce travail l'approximation des explications probabilistes sous l'angle de la super-modularité. Nous examinons à la fois les approches de descente gloutonne (GD) et d'ascension gloutonne (GA) pour la minimisation supermodulaire, dont les garanties d'approximation dépendent de la courbure de la fonction d'erreur « non normalisée » qui évalue la précision de l'explication. Basés sur diverses expériences visant à expliquer les prédictions des arbres de décision, nous montrons que nos algorithmes gloutons offrent une alternative efficace à la méthode exacte basé sur un encodage SAT. Cet article est un résumé du papier (en anglais) (Bounia et Koriche, 2023).