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

Il paper introduce GALACTIC, il primo framework unificato che genera spiegazioni controfattuali sia locali che globali per il clustering di serie temporali, ottimizzando le perturbazioni a livello di istanza e selezionando un riassunto non ridondante delle transizioni tra cluster tramite un obiettivo basato sulla Lunghezza Minima di Descrizione (MDL) con garanzie di approssimazione.

L'essenziale

Immagina di avere una montagna di dati temporali: ritmi cardiaci, prezzi delle azioni, movimenti di robot o suoni della voce. Per dare un senso a tutto questo caos, usiamo l'"clustering" (raggruppamento), che è come mettere in ordine una grande libreria: prendiamo libri simili e li mettiamo sullo stesso scaffale.

Il problema è che spesso questi scaffali sono "opachi". Sappiamo che un dato è finito nello scaffale "A" e non in quello "B", ma non sappiamo perché. E soprattutto, non sappiamo cosa dovremmo cambiare in quel dato per farlo spostare nello scaffale "B".

È qui che entra in gioco GALACTIC.

Cos'è GALACTIC?

GALACTIC è come un detective intelligente che lavora su due livelli per spiegare come funzionano questi raggruppamenti, senza bisogno di conoscere i segreti interni del "mago" che ha creato i gruppi (il modello di clustering).

Ecco come funziona, spiegato con due metafore semplici:

1. Il Livello Locale: "Il Consigliere Personale"

Immagina di essere un singolo dato (un libro) nello scaffale "A". Chiedi al detective: "Cosa devo cambiare in me stesso per finire nello scaffale 'B'?"

• I vecchi metodi: Ti dicevano cose come "Cambia tutto il libro" o "Cambia una pagina a caso". Risultato: il libro non ha più senso o la modifica è troppo grande.
• GALACTIC: È molto più preciso. Analizza il tuo libro e ti dice: "Non toccare la copertina o l'indice. Cambia solo due righe nel capitolo 3. Se cambi quelle due righe, diventi automaticamente un libro dello scaffale 'B'."
• Il trucco: GALACTIC sa quali parti del "tempo" (le righe del libro) sono importanti e quali no. Se ignora le parti irrilevanti, la spiegazione è breve, chiara e facile da capire.

2. Il Livello Globale: "Il Curatore della Biblioteca"

Ora, invece di guardare un solo libro, il detective deve guardare tutti i libri dello scaffale "A" e spiegare come l'intera collezione potrebbe spostarsi verso lo scaffale "B".

• Il problema: Se provi a spiegare come spostare 10.000 libri, potresti finire con 10.000 consigli diversi. È troppo confuso per un essere umano.
• La soluzione di GALACTIC: Usa un principio chiamato MDL (Minimum Description Length), che possiamo immaginare come il "Principio del Riassunto Perfetto".
  • Invece di darti 10.000 consigli, GALACTIC cerca il piccolo gruppo di regole che copre la maggior parte dei casi.
  • È come se il curatore dicesse: "Non devo spiegarti 10.000 libri. Basta che sappiate che se cambiate queste tre cose specifiche in un libro, il 90% dei libri dello scaffale 'A' diventerà automaticamente 'B'."
  • Questo riduce il caos a poche regole potenti e facili da ricordare.

Perché è speciale?

1. Non è un "Black Box": Funziona con qualsiasi metodo di raggruppamento, anche quelli più complessi e misteriosi.
2. Rispetta la forma: Se stai analizzando un battito cardiaco, GALACTIC non ti chiederà di cancellare il battito intero. Ti dirà solo di modificare un picco specifico, mantenendo la forma generale del cuore intatta.
3. Efficienza: Usa un algoritmo matematico intelligente (simile a come si risolve un puzzle) per trovare le spiegazioni più brevi e potenti, evitando di perdere tempo in consigli inutili.

In sintesi

Se il clustering è come organizzare una biblioteca, GALACTIC è il bibliotecario che ti dice esattamente:

• Per te (Locale): "Cambia solo questa parola per diventare un altro tipo di libro."
• Per tutti (Globale): "Ecco le 3 regole d'oro che trasformano intere sezioni della biblioteca."

È uno strumento che trasforma dati opachi e confusi in consigli chiari, brevi e azionabili, aiutando scienziati, medici e ingegneri a capire non solo cosa sta succedendo, ma come far cambiare le cose.

Sommario tecnico

1. Il Problema

Il clustering delle serie temporali è uno strumento fondamentale per scoprire pattern in dati non etichettati (es. finanza, neuroscienze, infrastrutture critiche). Tuttavia, i risultati del clustering sono spesso "scatole nere": gli utenti sanno a quale cluster appartiene una serie, ma non comprendono perché o come la serie dovrebbe evolvere per passare a un altro cluster.

Le sfide principali identificate dagli autori sono:

• Mancanza di spiegazioni per il clustering: I metodi esistenti di spiegabilità (XAI) si concentrano su modelli supervisionati (classificazione) o forniscono solo attributi statici, fallendo nell'identificare le transizioni temporali specifiche necessarie per cambiare cluster.
• Incoerenza temporale: Le spiegazioni controfattuali (CE) esistenti per le serie temporali spesso ignorano la struttura temporale, producendo modifiche "rumorose" o non contigue che non rispettano la forma della serie originale.
• Divario tra locale e globale: Esistono metodi per spiegare singoli istanti (locale) o intere popolazioni (globale), ma manca un quadro unificato che colmi questo divario, specialmente in contesti non supervisionati.

2. Metodologia: Il Framework GALACTIC

GALACTIC è il primo framework unificato per la spiegabilità controfattuale (locale e globale) nel clustering di serie temporali, agnostico rispetto all'algoritmo di clustering sottostante.

A. Livello Locale (Istanza singola)

L'obiettivo è trovare una perturbazione minima $\delta$ tale che una serie temporale $x$ appartenente al cluster $C_k$ venga classificata in un cluster diverso $C_{k'}$.

• Surrogato Probabilistico: Poiché molti algoritmi di clustering non hanno una funzione di mappatura esplicita, GALACTIC addestra un classificatore surrogato probabilistico $g$ per approssimare i confini decisionali del clustering.
• Ottimizzazione Guidata dall'Importanza: Invece di modificare l'intera serie, il metodo identifica segmenti temporali "discriminativi" tramite analisi di permutazione.
  • Vengono calcolate maschere di importanza basate sul cluster di origine e sul cluster target.
  • L'ottimizzazione del gradiente è vincolata da queste maschere: le modifiche sono permesse solo nelle regioni temporali critiche, preservando la struttura globale della serie.
• Obiettivo: Minimizzare il costo della perturbazione (vicinanza a $x$) massimizzando la validità (cambio di cluster) e la sparsità (poche modifiche).

B. Livello Globale (Riassunto del Cluster)

L'obiettivo è selezionare un insieme ridotto di perturbazioni rappresentative che spieghino come l'intera popolazione di un cluster possa transitare verso altri cluster.

• Generazione dei Candidati: Vengono generate perturbazioni locali per un sottoinsieme rappresentativo di istanze (prototipi e "critiche" selezionate tramite MMD-Critic) per creare un pool di candidati $\Delta_k$.
• Selezione basata su MDL (Minimum Description Length): Il problema di selezione è formulato come un'ottimizzazione del principio MDL. L'obiettivo è trovare il sottoinsieme di perturbazioni $S$ che minimizza la lunghezza totale della descrizione:
  $$L(D, M) = L(M) + L(D|M)$$
  Dove $L(M)$ è la complessità del modello (numero e complessità delle perturbazioni) e $L(D|M)$ è la lunghezza dei dati non spiegati (istanze che non cambiano cluster con le perturbazioni selezionate).
• Proprietà Teoriche: Gli autori dimostrano che la funzione obiettivo MDL è supermodulare, rendendo la riduzione della descrizione una funzione sottomodulare. Questo permette di utilizzare un algoritmo greedy con una garanzia di approssimazione di $(1 - 1/e)$.
• Varianti Algoritmiche:
  • Optimal: Ricerca esaustiva (per piccoli dataset).
  • Greedy: Selezione iterativa efficiente.
  • Gerarchico: Selezione a livello di sottogruppo seguita da raffinamento a livello di cluster, ideale per dataset massivi.

3. Contributi Chiave

1. Formulazione del Problema: Definizione formale della spiegabilità controfattuale per il clustering di serie temporali a livello locale e globale in un setting agnostico.
2. Vincoli Strutturali Locali: Introduzione di un'ottimizzazione del gradiente vincolata che utilizza maschere di importanza temporale per produrre controfattuali sparsi e che preservano la forma della serie.
3. Riassunti Globali tramite MDL: Proposta di un obiettivo di selezione senza parametri basato sul principio MDL per risolvere il trade-off multi-obiettivo (copertura vs. complessità) e garantire la non ridondanza.
4. Garanzie Teoriche: Dimostrazione della sottomodularità dell'obiettivo MDL, permettendo strategie greedy con limiti di approssimazione provati.
5. Raffinamento Gerarchico Adattivo: Un meccanismo scalabile che adatta il numero di spiegazioni globali alla densità interna e alla complessità dei sottogruppi del cluster.

4. Risultati Sperimentali

Il framework è stato valutato su 30 dataset dell'UCR Time-Series Archive.

• Valutazione Locale (GALACTIC-L):
  • Supera i baselines dello stato dell'arte (k-NN, TSEvo, Glacier) in termini di sparsità (meno segmenti modificati) e costo di inversione (minore distanza dalla serie originale).
  • Mantiene un'elevata efficacia (tasso di successo nel cambio di cluster).
  • È significativamente più veloce dei metodi evolutivi (TSEvo) e più preciso dei metodi basati su gradienti non vincolati (Glacier).
• Valutazione Globale (GALACTIC-G):
  • Genera riassunti globali più concisi e con una copertura maggiore rispetto alle varianti adattate di GLOBE-CE e Glacier.
  • L'approccio basato su MDL seleziona perturbazioni che massimizzano la copertura della popolazione minimizzando il numero di modifiche necessarie.
  • Le varianti gerarchiche offrono un ottimo compromesso tra qualità e tempo di esecuzione su dataset di grandi dimensioni.

5. Significato e Impatto

GALACTIC rappresenta un passo avanti significativo nell'XAI per l'apprendimento non supervisionato.

• Trasparenza Decisionale: Trasforma i cluster da semplici etichette descrittive a strumenti decisionali, permettendo agli utenti di capire come modificare un comportamento temporale per raggiungere un obiettivo desiderato.
• Agnosticismo: Non dipende dall'algoritmo di clustering specifico (es. k-means, DBSCAN, spectral), rendendolo applicabile a qualsiasi pipeline esistente.
• Interpretabilità Temporale: A differenza dei metodi precedenti che trattano le serie temporali come vettori piatti, GALACTIC rispetta la natura temporale e strutturale dei dati, fornendo spiegazioni che hanno senso fisico e temporale.
• Efficienza Scalabile: La formulazione sottomodulare garantisce che il framework sia scalabile anche per dataset complessi e ad alta dimensionalità.

In sintesi, GALACTIC colma il divario tra la scoperta di pattern non supervisionati e la necessità umana di comprendere e agire su tali pattern, fornendo spiegazioni controfattuali sia per singoli casi che per intere popolazioni di dati temporali.