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

O artigo apresenta o GALACTIC, o primeiro framework unificado que gera explicações contrafactuais locais e globais para agrupamento de séries temporais não supervisionado, utilizando otimização sensível a clusters e um algoritmo guloso baseado em MDL para produzir perturbações esparsas e resumos interpretáveis das transições entre clusters.

O essencial

Imagine que você tem uma pilha gigante de músicas (dados de séries temporais) e um algoritmo inteligente que as organiza em caixas (clusters) baseadas no ritmo, no estilo ou no humor. O algoritmo faz um ótimo trabalho: ele coloca todas as músicas de rock na "Caixa A", jazz na "Caixa B" e pop na "Caixa C".

Mas aqui está o problema: ninguém sabe por que. O algoritmo é uma "caixa preta". Se você pegar uma música que está na Caixa A e perguntar: "Por que esta música não está na Caixa B?", o algoritmo não consegue responder. Ele apenas diz: "É rock".

Isso é frustrante. Você quer saber: "O que eu precisaria mudar nesta música para que ela fosse considerada Jazz?" Seria mudar o ritmo? A melodia? O instrumento?

É aqui que entra o GALACTIC.

O que é o GALACTIC?

O GALACTIC é um novo sistema que funciona como um "Detetive de Mudanças" para essas caixas de música. Ele responde a duas perguntas fundamentais de forma simples e inteligente:

1. Local (Para uma única música): "O que eu mudo exatamente nesta música para ela entrar na outra caixa?"
2. Global (Para todas as músicas): "Quais são as regras gerais de mudança que explicam por que as músicas saem de uma caixa e vão para outra?"

Como ele funciona? (Analogias Simples)

1. O Detetive Local: "O Cirurgião Preciso"

Imagine que você quer transformar uma música de Rock em Jazz.

• Os métodos antigos eram como um cirurgião desajeitado: eles cortavam pedaços aleatórios da música, mudavam o volume, trocavam instrumentos de forma caótica, até que a música "parecesse" Jazz. O resultado era uma bagunça que não fazia sentido musical.
• O GALACTIC age como um cirurgião de precisão. Ele olha para a música e diz: "Espere! A parte que define que isso é Rock é o refrão. A parte que define Jazz é o solo de saxofone. Se eu mudar apenas o refrão para um estilo mais suave e adicionar um saxofone no meio, a música vira Jazz."

Ele faz isso identificando os "momentos decisivos" (segmentos temporais) da música. Ele não mexe no que não precisa. Ele é econômico, muda o mínimo possível e mantém a estrutura original da música intacta, apenas ajustando o que é crucial para a mudança de "caixa".

2. O Resumidor Global: "O Curador de Museu"

Agora, imagine que você tem 1.000 músicas na Caixa Rock e quer saber o que elas precisam mudar para virar Jazz.

• Se você perguntar ao GALACTIC para cada uma das 1.000 músicas individualmente, ele vai te dar 1.000 respostas diferentes. Isso é cansativo e confuso.
• O GALACTIC usa uma técnica inteligente chamada MDL (Princípio da Menor Descrição). Pense nisso como um curador de museu que precisa criar um guia turístico.
  • Em vez de listar 1.000 regras diferentes, o curador olha para todas as mudanças e diz: "Na verdade, a maioria das músicas de Rock precisa apenas de duas coisas para virar Jazz: suavizar o ritmo e adicionar um instrumento de sopro."
  • Ele cria um resumo curto e inteligente que explica a transição para quase todas as músicas, sem precisar repetir a mesma coisa mil vezes. Ele escolhe as explicações que contam a história completa com o menor número de palavras possível.

Por que isso é revolucionário?

O artigo mostra que o GALACTIC é melhor do que os métodos atuais porque:

1. Não é "Cego": Ele entende que séries temporais (como música, batimentos cardíacos ou preços de ações) têm uma estrutura. Ele não quebra essa estrutura ao fazer as mudanças.
2. É "Econômico": Ele faz as mudanças mais simples possíveis. Se você só precisa mudar 3 segundos de uma música de 3 minutos, ele não vai mudar os 3 minutos todos.
3. É "Inteligente" na Escala: Ele consegue pegar milhares de explicações individuais e condensá-las em um único resumo fácil de entender, sem perder a essência do problema.

Em resumo

O GALACTIC é como ter um tradutor e um editor de texto para dados complexos.

• Se você tem um dado estranho, ele diz: "Mude apenas este pequeno detalhe aqui e ele se encaixará perfeitamente no grupo que você deseja."
• Se você quer entender o grupo todo, ele diz: "Aqui estão as 3 regras principais que governam a diferença entre esses grupos."

Isso transforma dados opacos e confusos em insights acionáveis, permitindo que médicos, financeiros ou cientistas entendam não apenas o que aconteceu, mas como poderiam mudar o futuro.

Resumo técnico

Resumo Técnico: GALACTIC

1. O Problema

A agrupamento (clustering) de séries temporais é uma ferramenta fundamental para descoberta de padrões em domínios como finanças, neurociência e infraestrutura crítica. No entanto, os resultados desses algoritmos são frequentemente "caixas-pretas" opacas.

• Limitações Atuais: Os métodos existentes de explicabilidade focam em atribuição de características (feature attribution) ou metadados, falhando em identificar as transições temporais necessárias para mover uma instância de um cluster para outro.
• Falta de Explicações Contratuais (Counterfactuals): Embora as Explicações Contratuais (CEs) existam para classificação supervisionada, elas não foram adaptadas eficazmente para o cenário não supervisionado de clustering. Além disso, os métodos atuais muitas vezes ignoram a coerência temporal, alteram estruturas características da série ou não conseguem generalizar de explicações locais (por instância) para um resumo global (por cluster) conciso e não redundante.

2. Metodologia: O Framework GALACTIC

O GALACTIC é um framework unificado e agnóstico ao modelo de clustering, projetado para gerar explicações contratuais tanto no nível local (instância) quanto global (cluster).

A. Abordagem Local (Nível de Instância)

• Objetivo: Encontrar a perturbação mínima necessária para alterar a atribuição de um cluster de origem ($k$) para um cluster alvo ($k'$).
• Mecanismo de Otimização:
  • Utiliza um surrogato probabilístico (classificador treinado para imitar o algoritmo de clustering) para tornar o problema diferenciável.
  • Emprega uma busca de gradiente guiada por importância temporal. Antes da otimização, o sistema identifica segmentos temporais discriminativos através de análise de permutação em subgrupos.
  • Restrição Estrutural: Um "máscara de importância" é aplicada diretamente ao gradiente durante a otimização. Isso força o algoritmo a modificar apenas os segmentos críticos (que definem a identidade do cluster), preservando a estrutura global da série e garantindo que a explicação seja esparsa e semanticamente relevante.
• Estratégia de Alvo: O sistema seleciona o cluster alvo como a segunda maior probabilidade no surrogato ("second possible"), garantindo um caminho de transição eficiente na topologia latente.

B. Abordagem Global (Nível de Cluster)

• Objetivo: Selecionar um conjunto pequeno e não redundante de perturbações que explique as transições para a maior parte da população de um cluster, evitando a sobrecarga cognitiva de milhares de explicações locais.
• Formulação via MDL (Minimum Description Length):
  • O problema de seleção é reformulado como um problema de seleção de modelo baseado no princípio MDL.
  • O objetivo minimiza a soma do comprimento do código do modelo (complexidade das perturbações selecionadas) e do comprimento do código dos dados (instâncias não cobertas/explicadas).
  • Isso resolve automaticamente o trade-off entre cobertura (quantas instâncias são explicadas) e complexidade (quantas regras/perturbações são necessárias), sem necessidade de ajuste manual de hiperparâmetros.
• Propriedades Teóricas e Algoritmo:
  • O artigo prova que a função objetivo MDL é supermodular, o que implica que a redução do MDL é uma função submodular monotônica.
  • Essa propriedade permite o uso de um algoritmo de seleção gananciosa (greedy) com garantias de aproximação de $(1 - 1/e)$.
  • Refinamento Hierárquico: Para escalabilidade em grandes conjuntos de dados, o método utiliza uma abordagem hierárquica: primeiro seleciona perturbações representativas em subgrupos (baseados em padrões temporais internos) e depois refina a seleção no nível do cluster global.

3. Principais Contribuições

1. Formulação do Problema: Primeira formalização unificada de explicabilidade contratual para clustering de séries temporais, cobrindo níveis locais e globais de forma agnóstica ao algoritmo de clustering.
2. Contratuais Locais com Restrições Estruturais: Introdução de uma otimização de gradiente que utiliza máscaras de importância baseadas em subgrupos para garantir que as perturbações sejam esparsas, preservem a forma da série e atuem apenas em regiões discriminativas.
3. Resumos Globais via MDL: Proposta de um objetivo de seleção de modelo baseado em MDL para identificar o conjunto ótimo de perturbações globais, eliminando a necessidade de sintonia de pesos para trade-offs multi-objetivo.
4. Garantias Teóricas: Prova da submodularidade do objetivo MDL, permitindo algoritmos eficientes com garantias de aproximação teórica.
5. Refinamento Hierárquico Adaptativo: Um mecanismo escalável que adapta o número de explicações globais à densidade e complexidade interna dos subgrupos do cluster.

4. Resultados Experimentais

O GALACTIC foi avaliado no UCR Time-Series Archive (30 conjuntos de dados diversos) e comparado com state-of-the-art (baselines como TSEvo, Glacier, k-NN e adaptações de GLOBE-CE).

• Desempenho Local (GALACTIC-L):
  • Produziu explicações significativamente mais esparsas (menos segmentos e pontos de tempo alterados) do que os baselines.
  • Mantém custos de "virada" (flipping cost) baixos, indicando perturbações mínimas.
  • É ordens de magnitude mais rápido que métodos evolutivos (como TSEvo) e mais eficiente que métodos baseados em gradiente sem restrições estruturais.
• Desempenho Global (GALACTIC-G):
  • Gerou resumos globais mais concisos e com maior cobertura da população do cluster em comparação com métodos de agregação ou busca aleatória.
  • A abordagem baseada em MDL conseguiu identificar padrões de transição que maximizavam a explicabilidade com o menor custo computacional.
  • A variante hierárquica demonstrou excelente escalabilidade, mantendo alta qualidade de explicação mesmo em grandes volumes de dados.

5. Significado e Impacto

O trabalho GALACTIC preenche uma lacuna crítica na inteligência artificial explicável (XAI) para séries temporais não supervisionadas.

• Ação e Decisão: Transforma clusters de "artefatos descritivos" em ferramentas de suporte à decisão, mostrando aos usuários não apenas por que uma série pertence a um grupo, mas como ela deve evoluir para mudar de comportamento (ex: mudar de um padrão de consumo normal para um de fraude).
• Interpretabilidade Estrutural: Ao preservar a estrutura temporal e focar em regiões discriminativas, as explicações são mais confiáveis para especialistas humanos do que alterações aleatórias ou globais.
• Escalabilidade Teórica: A aplicação do princípio MDL e a prova de submodularidade oferecem um caminho teoricamente sólido para resumir grandes espaços de dados complexos em conjuntos de regras acionáveis e não redundantes.

Em suma, o GALACTIC estabelece um novo padrão para a interpretabilidade de clustering de séries temporais, combinando rigor matemático com eficiência prática.