GALACTIC: Global and Local Agnostic Counterfactuals for Time-series Clustering

Ce papier présente GALACTIC, le premier cadre unifié générant des explications contrefactuelles à la fois locales et globales pour le clustering de séries temporelles non supervisé, en utilisant une optimisation ciblée au niveau des instances et une sélection de résumés globaux basée sur la longueur de description minimale (MDL) pour offrir des explications plus concises et interprétables.

L'essentiel

Imaginez que vous avez un immense coffre-fort rempli de milliers de courbes de données (comme des graphiques de température, de battements de cœur ou de cours boursiers). Un ordinateur a trié ces courbes en plusieurs groupes, disons "Groupe A", "Groupe B" et "Groupe C".

Le problème ? L'ordinateur est comme un magicien silencieux : il vous dit "Cette courbe est dans le Groupe A", mais il ne vous explique pourquoi. Et plus important encore, il ne vous dit pas ce qu'il faudrait changer dans cette courbe pour qu'elle passe dans le Groupe B. C'est comme si on vous disait "Vous êtes en retard" sans vous dire quelle heure il faut régler pour être à l'heure.

C'est là qu'intervient GALACTIC, le nouveau système présenté dans cet article. Voici comment il fonctionne, expliqué simplement avec des images du quotidien.

1. Le Détective Local (L'Explication "Pour Toi")

Imaginez que vous êtes un détective privé. Vous avez un client (une courbe de données) qui se trouve dans le "Groupe A". Il veut savoir : "Quelle petite action dois-je faire pour devenir un membre du 'Groupe B' ?"

Les anciennes méthodes étaient comme des peintres qui gâchaient tout le tableau : pour changer une couleur, ils repeignaient tout le mur, rendant le résultat bizarre et illisible.

GALACTIC, lui, est un chirurgien précis.

• L'analogie du "Masque de Sécurité" : Avant de toucher à la courbe, GALACTIC analyse le groupe et dit : "Attends, cette partie de la courbe est cruciale pour son identité, ne la touche pas ! Mais cette petite bosse ici ? C'est la clé. Si on la modifie légèrement, le groupe change."
• Le résultat : Il ne modifie que les moments précis et importants. C'est comme changer une seule note dans une mélodie pour transformer une chanson triste en une chanson joyeuse, sans toucher aux autres instruments. Cela rend l'explication très claire et facile à comprendre.

2. Le Directeur de Théâtre (L'Explication "Pour Tout le Monde")

Maintenant, imaginez que vous avez 10 000 clients dans le "Groupe A". Si vous demandez à GALACTIC de donner une explication à chacun d'eux individuellement, vous obtiendrez 10 000 petits conseils différents. C'est le chaos ! C'est comme recevoir 10 000 recettes de cuisine différentes pour faire un gâteau.

Le vrai défi est de trouver les 3 ou 4 règles générales qui expliquent comment passer du Groupe A au Groupe B pour tout le monde.

C'est ici que GALACTIC utilise une astuce brillante appelée MDL (Minimum Description Length).

• L'analogie du "Résumé Télégraphique" : Imaginez que vous devez envoyer un message à un ami pour lui expliquer comment transformer un groupe de personnes en un autre. Vous avez deux options :
  1. Lui envoyer 10 000 messages individuels (trop long, trop cher).
  2. Lui envoyer un seul résumé ultra-court qui capture l'essentiel.
• La Magie Mathématique : GALACTIC cherche le résumé le plus court possible qui explique le plus grand nombre de cas. C'est comme si vous disiez : "Pour passer du Groupe A au B, il suffit de faire monter le pic au milieu et d'aplatir la fin." Ce message court explique 90% des cas. GALACTIC prouve mathématiquement qu'il peut trouver ce résumé optimal très rapidement, sans avoir à tester des millions de combinaisons.

3. Pourquoi est-ce si important ?

Avant GALACTIC, les experts en données devaient souvent deviner ou utiliser des méthodes lourdes qui ne fonctionnaient bien que pour des cas très spécifiques (comme le classement de photos).

GALACTIC est spécial car :

1. Il est "Agnostique" : Il fonctionne avec n'importe quel système de tri, même les plus mystérieux. Il n'a pas besoin de connaître la recette secrète du tri, il observe juste les résultats.
2. Il est Économe : Il ne gaspille pas de temps à modifier des parties inutiles de la courbe.
3. Il est Global : Il ne se contente pas de résoudre un problème pour une personne, il trouve la solution pour toute la foule.

En Résumé

GALACTIC est comme un traducteur universel entre les données complexes et les humains.

• Pour vous individuellement, il vous dit : "Juste ici, changez un tout petit peu, et vous passerez dans l'autre catégorie."
• Pour le groupe, il vous dit : "Voici les 3 règles simples qui expliquent pourquoi tout le monde passe d'un groupe à l'autre."

C'est un outil qui transforme des boîtes noires opaques en cartes claires, permettant aux médecins, aux ingénieurs ou aux analystes financiers de comprendre non seulement où ils sont, mais comment ils peuvent changer de direction si nécessaire.

Résumé technique

1. Problématique et Contexte

Le regroupement (clustering) de séries temporelles est un outil fondamental pour découvrir des motifs dans des domaines variés (finance, santé, robotique, etc.). Cependant, les méthodes de clustering actuelles souffrent souvent d'un manque de transparence ("boîte noire"). Les utilisateurs ne se contentent pas d'une étiquette de cluster ; ils ont besoin de comprendre pourquoi une série appartient à un groupe spécifique et comment elle pourrait évoluer pour basculer vers un autre.

Les défis majeurs identifiés sont :

• Absence d'explicabilité pour le clustering non supervisé : La plupart des méthodes d'explication par contre-exemples (Counterfactual Explanations - CEs) sont conçues pour des tâches supervisées (classification). Elles ne s'adaptent pas bien à la nature non supervisée du clustering, où les frontières de décision ne sont pas étiquetées a priori.
• Incohérence temporelle et manque de parcimonie : Les méthodes existantes appliquent souvent des perturbations sur des segments non discriminatifs ou modifient trop de points temporels, rendant les explications difficiles à interpréter et peu réalistes.
• Défi de l'agrégation globale : Il est difficile de résumer des milliers d'explications locales (au niveau d'une instance) en un ensemble concis et non redondant de règles globales qui expliquent les transitions entre clusters pour toute une population.

2. Méthodologie : Le Framework GALACTIC

GALACTIC propose un cadre unifié, agnostique vis-à-vis de l'algorithme de clustering sous-jacent, pour générer des contre-exemples à la fois locaux (instance) et globaux (cluster).

A. Niveau Local (Explications par Instance)

Pour une série temporelle donnée $x$ appartenant au cluster $C_k$, l'objectif est de trouver une version perturbée $x_{cf}$ qui bascule vers un autre cluster $C_{k'}$ avec un coût minimal.

• Surrogat Probabiliste : Puisque les algorithmes de clustering (comme le spectral ou le DTW) sont souvent transductifs ou opaques, GALACTIC apprend un classifieur probabiliste de substitution (surrogate) $g$ pour approximer les frontières de décision.
• Optimisation Guidée par l'Importance : Au lieu de modifier n'importe quel point temporel, le framework identifie d'abord des segments discriminatifs via une analyse de permutation au niveau des sous-groupes.
  • Le temps est segmenté en intervalles contigus.
  • Une "masque d'importance" est générée pour identifier les segments critiques qui définissent l'appartenance au cluster source et ceux nécessaires pour atteindre le cluster cible.
• Contrainte Structurelle : L'optimisation (via descente de gradient) applique ce masque comme une contrainte stricte. Seuls les points temporels situés dans les segments importants sont modifiés. Cela garantit que la structure globale de la série est préservée et que les modifications sont localisées sur les régions réellement discriminantes.

B. Niveau Global (Résumé des Transitions)

Au lieu de fournir une explication pour chaque instance, GALACTIC vise à sélectionner un petit ensemble de perturbations représentatives qui expliquent les transitions pour l'ensemble du cluster.

• Génération de Candidats : Un pool de perturbations candidates est généré en utilisant des instances représentatives (prototypes) et des cas limites (critiques) du cluster, via l'algorithme MMD-Critic.
• Sélection par Longueur Minimale de Description (MDL) : Le problème de sélection est formulé comme un problème d'optimisation basé sur le principe MDL. L'objectif est de trouver le sous-ensemble de perturbations $S$ qui minimise la longueur totale de description :
  $$L(D, M) = L(M) + L(D|M)$$
  • $L(M)$ : Complexité du modèle (coût de codage des perturbations sélectionnées, favorisant la parcimonie et la proximité).
  • $L(D|M)$ : Coût des données non expliquées (pénalité pour les instances qui ne basculent pas avec les perturbations sélectionnées).
• Propriétés Théoriques et Algorithme : L'article prouve que la fonction objectif MDL est supermodulaire, ce qui implique que la réduction de la longueur de description est une fonction sous-modulaire. Cela permet d'utiliser un algorithme glouton avec des garanties d'approximation $(1 - 1/e)$, rendant la sélection efficace même pour de grands ensembles de données.
• Approche Hiérarchique : Pour une évolutivité accrue, une méthode hiérarchique est proposée : sélection au niveau des sous-groupes suivie d'une raffinement au niveau du cluster global.

3. Contributions Clés

1. Formalisation du problème : Première formulation unifiée de l'explicabilité par contre-exemples pour le clustering de séries temporelles, couvrant les niveaux local et global.
2. Contraintes Structurelles Locales : Introduction d'une optimisation de gradient contrainte par des masques d'importance temporelle, produisant des contre-exemples parcimonieux qui respectent la forme des séries.
3. Résumé Global via MDL : Proposition d'un objectif de sélection sans paramètres (basé sur MDL) pour résumer les transitions de clusters, résolvant le compromis multi-objectif (couverture vs complexité) sans ajustement manuel de poids.
4. Garanties Théoriques : Preuve de la sous-modularité de la réduction MDL, permettant des algorithmes de sélection efficaces avec des bornes de performance prouvées.
5. Évaluation Exhaustive : Validation sur 30 datasets de l'archive UCR, démontrant la supériorité par rapport aux méthodes de l'état de l'art adaptées.

4. Résultats Expérimentaux

Les expériences ont été menées sur l'archive UCR Time-Series avec des comparaisons contre des bases de référence (k-NN, TSEvo, Glacier).

• Performance Locale (GALACTIC-L) :

  • Efficacité : Taux de succès élevé pour faire basculer les instances vers le cluster cible.
  • Parcimonie : Réduction significative du nombre de segments et de points temporels modifiés par rapport aux méthodes existantes (ex: TSEvo et Glacier). Les modifications sont concentrées sur les régions critiques.
  • Coût : Coût de modification ($L_2$) plus faible, indiquant des changements plus minimaux et réalistes.
  • Vitesse : Beaucoup plus rapide que les méthodes évolutionnaires (TSEvo) et compétitive avec les méthodes basées sur le gradient.

• Performance Globale (GALACTIC-G) :

  • Couverture : Les variantes de GALACTIC (Optimale, Gloutonne, Hiérarchique) couvrent une plus grande proportion d'instances du cluster avec moins de perturbations que les méthodes adaptatives (GLOBE-CE*, Glacier-G*).
  • Interprétabilité : Les résumés globaux sont plus concis et capturent mieux la structure interne des clusters (en tenant compte des sous-groupes).
  • Efficacité Computationnelle : L'approche gloutonne hiérarchique offre un excellent compromis entre qualité de l'explication et temps de calcul, permettant de traiter des ensembles de données massifs.

5. Signification et Impact

GALACTIC comble un vide majeur dans le domaine de l'IA explicable (XAI) en étendant les contre-exemples au domaine non supervisé du clustering de séries temporelles.

• Prise de décision : Il transforme les clusters de simples artefacts descriptifs en outils d'aide à la décision en fournissant des actions concrètes (comment modifier une série pour changer de comportement).
• Robustesse et Agnosticisme : En étant agnostique vis-à-vis de l'algorithme de clustering, il est applicable à n'importe quelle méthode de regroupement existante.
• Théorie et Pratique : La combinaison d'une approche théorique rigoureuse (MDL, sous-modularité) avec une implémentation pratique efficace (masques d'importance, sélection hiérarchique) offre une nouvelle référence pour l'interprétabilité des modèles temporels complexes.

En résumé, GALACTIC fournit non seulement des explications locales précises et structurées, mais aussi une vue d'ensemble globale cohérente, permettant aux praticiens de comprendre et de manipuler les régimes comportementaux identifiés par le clustering.