Résumé Technique : Apprentissage de l'ensemble de règles parsimonieux à haute couverture discriminative (CDPR)

1. Définition du Problème

L'article traite d'une limitation critique de l'apprentissage automatique interprétable actuel : le problème « haute précision-basse couverture ». Bien que les algorithmes actuels de pointe (SOTA) pour l'apprentissage de règles (par exemple, IDS, RIPPER, DefragTrees) atteignent souvent une précision prédictive élevée, ils échouent fréquemment à couvrir une partie significative de l'espace d'entrée. Une faible couverture signifie que pour une grande fraction de points de données, le modèle repose sur une règle par défaut à la logique inconnue, ce qui compromet la transparence et l'explicabilité requises dans des domaines critiques comme la santé et la finance.

Les auteurs définissent le problème d'apprentissage de l'ensemble de règles parsimonieux à haute couverture discriminative (CDPR). L'objectif est d'apprendre un ensemble de règles $S$ qui maximise simultanément la couverture (la fraction de l'ensemble de données couverte par les règles) tout en satisfaisant des contraintes de qualité strictes concernant :

• Le pouvoir discriminatif : Précision minimale de la règle ($\alpha$).
• La parsimonie : Largeur maximale de la règle ($\delta$) et taille maximale de l'ensemble de règles ($\gamma$).
• L'interprétabilité : Taux de chevauchement maximal ($\beta$) entre deux règles quelconques pour assurer une redondance minimale.

Formellement, le problème (CDPRL) est défini comme :
$$\text{maximiser}_{S \subseteq B_{\alpha,\delta}} \text{couverture}(S)$$
$$sous réserve de : \text{taille-règle}(S) \le \gamma, \quad \text{taux-chevauchement}(r_i, r_j) \le \beta$$
où $B_{\alpha,\delta}$ est l'ensemble des règles candidates avec une précision $\ge \alpha$ et une largeur $\le \delta$. Les auteurs notent que les solveurs existants ne peuvent pas traiter cela directement car la contrainte de taux de chevauchement n'est ni un matroid ni une contrainte de sac à dos (knapsack).

2. Méthodologie

L'article propose deux algorithmes fondés sur la maximisation submodulaire pour résoudre le problème CDPR.

2.1 Algorithme de Règles de Graphe (GRA)

Le GRA est conçu pour résoudre le problème CDPRL en le transformant en un problème d'optimisation submodulaire sur une structure de graphe.

• Construction du Graphe de Chevauchement : Un graphe orienté $G=(V, E)$ est construit où les sommets représentent les règles candidates dans $B_{\alpha,\delta}$. Une arête orientée $(r_i, r_j)$ existe si le taux de chevauchement entre $r_i$ et $r_j$ dépasse le seuil $\beta$.
• Processus de Sélection : L'algorithme sélectionne de manière itérative le sommet (la règle) ayant la couverture la plus élevée dans le graphe, l'ajoute à l'ensemble de règles $S$, et supprime le sommet sélectionné ainsi que tous les sommets connectés à lui par une arête orientée (pour satisfaire la contrainte de chevauchement). Cela continue jusqu'à ce que l'ensemble de règles atteigne la taille $\gamma$ ou que le graphe soit vide.
• Garantie Théorique : Les auteurs prouvent que le GRA fournit une garantie d'approximation de $(1 - (1 - \frac{1-\beta}{\gamma(1+d\beta)})^\gamma)$, où $d$ est le degré entrant minimal des nœuds sélectionnés.
• Complexité : Le temps d'exécution est quadratique par rapport à la taille de l'ensemble candidat $|B_{\alpha,\delta}|$.

2.2 Algorithme Glouton (GDY)

Pour remédier au coût computationnel du GRA, les auteurs introduisent une variante relaxée appelée CDPRL-MO (Mean Overlap / Chevauchement Moyen).

• Objectif Relaxé : Au lieu d'imposer strictement un taux de chevauchement $\le \beta$ pour chaque paire, le GDY optimise une fonction $g(S)$ qui équilibre la couverture et la minimisation du chevauchement moyen à travers l'ensemble.
• Submodularité : Les auteurs prouvent que la fonction objectif $g(S)$ est une fonction submodulaire non monotone.
• Algorithme : Le GDY emploie un algorithme d'approximation glouton conçu pour la maximisation submodulaire non monotone avec des contraintes de cardinalité.
• Garantie Théorique : Le GDY atteint une garantie d'approximation de $1/4$.
• Complexité : Le temps d'exécution est presque linéaire en $|B_{\alpha,\delta}|$, ce qui le rend nettement plus rapide que le GRA pour les grands ensembles candidats.

3. Contributions Clés

1. Formulation du Problème : L'article introduit le CDPR comme une nouvelle formulation de problème qui cible explicitement le compromis haute précision-basse couverture, un fossé que les auteurs identifient comme non traité dans la littérature antérieure.
2. Algorithmes Nouveaux :
   • GRA : Un algorithme basé sur les graphes avec des garanties d'approximation prouvables pour le problème strict de CDPR.
   • GDY : Un algorithme glouton computationnellement efficace pour la variante relaxée CDPRL-MO.
3. Analyse Théorique : Les auteurs fournissent des preuves formelles pour les garanties d'approximation des deux algorithmes, établissant leur validité théorique dans le cadre de l'optimisation submodulaire.
4. Validation Empirique : Des expériences approfondies sur 12 jeux de données (10 jeux de données UCI et 2 jeux de données sur la maladie d'Alzheimer) démontrent l'efficacité des méthodes proposées.

4. Résultats Expérimentaux

Les auteurs ont évalué GRA et GDY par rapport aux bases de référence SOTA (IDS, DefragTrees, RIPPER) et aux modèles boîtes noires standards (Random Forest, Régression Logistique).

• Couverture : L'amélioration la plus significative a été observée dans les taux de couverture. Le GRA a atteint un taux de couverture moyen de 97 %, et le GDY a atteint 91 %. En revanche, la meilleure base de référence suivante (IDS) n'a atteint que 35 %, et RIPPER 31 %. Cela représente une amélioration de 2,5 fois de la couverture moyenne par rapport au meilleur algorithme d'apprentissage de règles existant.
• Précision (Pouvoir Discriminatif) : Le GRA a atteint une précision moyenne de l'ensemble de règles (RSA) de 0,85, surpassant IDS (0,82), DefragTrees (0,76) et RIPPER (0,80). La performance du GRA était compétitive avec Random Forest (RF), égalant ou surpassant RF dans 7 cas sur 12.
• Parsimonie : Les deux algorithmes, GRA et GDY, ont maintenu de faibles largeurs de règles (largeur maximale moyenne de 4) et des tailles d'ensemble de règles raisonnables (taille moyenne de 7 règles), comparables à IDS et RIPPER, et nettement meilleures que DefragTrees (largeur maximale moyenne de 10).
• Étude de Cas (Maladie d'Alzheimer) : Dans une application spécifique de conception de tests neurocognitifs pour le dépistage de la maladie d'Alzheimer, GRA et GDY ont réussi à générer des ensembles de règles qui ont réduit le nombre de caractéristiques requises d'au moins 18 % par rapport à DefragTrees, tout en maintenant une précision et une couverture élevées (>70 %).

5. Signification et Revendications

L'article affirme que le CDPR représente la première tentative d'établir une approche qui optimise simultanément la haute couverture, le pouvoir discriminatif et la parsimonie dans l'apprentissage de règles.

Les auteurs soulignent que, bien que l'interprétabilité soit souvent définie simplement par la complexité du modèle (moins de règles), la véritable interprétabilité dans les applications critiques exige que le modèle puisse expliquer les décisions pour la vaste majorité des entrées (haute couverture). En résolvant le problème haute précision-basse couverture, les méthodes proposées (GRA et GDY) permettent le déploiement de modèles interprétables dans des domaines où la transparence et la fidélité sont primordiales, tels que la santé et la justice pénale, sans sacrifier la performance prédictive. Ce travail suggère que la maximisation submodulaire est un cadre viable et efficace pour l'apprentissage d'ensembles de règles de haute qualité, offrant une voie vers des systèmes d'IA plus dignes de confiance.