Score-based change point detection via tracking the best of infinitely many experts

Resumo Técnico: Detecção de Pontos de Mudança Baseada em Scores via Rastreamento do Melhor de Infinitos Especialistas

1. O Problema

O artigo aborda o problema da detecção de pontos de mudança online não paramétrica. O cenário envolve uma sequência de vetores aleatórios $X_1, \dots, X_T$ em um espaço euclidiano, onde a distribuição de probabilidade muda em um momento desconhecido $\tau^*$.

• Pré-mudança ($t \le \tau^*$): As observações são i.i.d. com densidade $p$.
• Pós-mudança ($t > \tau^*$): As observações são i.i.d. com uma densidade diferente $q \neq p$.
• Objetivo: Detectar o momento $\tau^*$ o mais rápido possível, sem conhecimento prévio das densidades $p$ e $q$, nem do vetor de mudança.
• Desafio: Métodos existentes frequentemente assumem modelos paramétricos (ex: mudança de média em distribuições Gaussianas) ou exigem o cálculo de integrais de alta dimensão (como a função de partição em modelos exponenciais), o que é computacionalmente proibitivo.

2. Metodologia Proposta

Os autores propõem um algoritmo que combina aprendizado online com conselho de especialistas e estimação sequencial de funções de score. A abordagem não depende de assumir uma família paramétrica fixa para $p$ e $q$, mas sim de aproximar as densidades através de uma classe de referência.

Componentes Principais:

• Modelagem via Divergência de Fisher:
  Em vez de usar a perda logarítmica negativa (que exige o cálculo da função de partição $\Phi(\theta)$, uma integral complexa), o algoritmo utiliza a Divergência de Fisher como medida de proximidade entre a densidade alvo e uma aproximação paramétrica $p_\theta$.
  A perda no tempo $t$ é definida como:
  $$\ell_t(\theta) = \frac{1}{2}\theta^\top A_t \theta - b_t^\top \theta$$
  Onde $A_t$ e $b_t$ são construídos a partir do gradiente do logaritmo da densidade (score) e do Laplaciano, permitindo estimativas não viesadas sem calcular integrais de normalização.

• Classe de Especialistas Infinita:
  O espaço de parâmetros $\theta$ é contínuo ($\mathbb{R}^d$), representando um número infinito de "especialistas" (cada $\theta$ é um especialista). O algoritmo busca rastrear o melhor especialista estático antes da mudança e o melhor especialista após a mudança.

• Algoritmo de Previsão (Fixed Share para Infinitos Especialistas):
  O núcleo do método é uma versão adaptada do algoritmo Fixed Share (Herbster & Warmuth, 1998), projetada para lidar com um número infinito de especialistas e funções de perda quadráticas.

  • O algoritmo mantém dois previsores:
    1. Média Ponderada Exponencialmente (EW): Rastreia o melhor especialista estático ao longo de todo o histórico (não se adapta bem a mudanças bruscas).
    2. Fixed Share (FS): Capaz de "trocar" de especialista, adaptando-se rapidamente a mudanças na distribuição subjacente.
  • A previsão do Fixed Share é calculada recursivamente, evitando a integração direta sobre o espaço de especialistas, utilizando uma distribuição a priori Gaussiana e propriedades de conjugação.

• Estatística de Teste:
  A detecção é baseada na diferença acumulada de perdas entre os dois previsores:
  $$\hat{S}_t = \hat{L}^{EW}_{1:t} - \hat{L}^{FS}_{1:t}$$

  • Regime Pré-mudança: Ambos os previsores performam de forma similar, mantendo $\hat{S}_t$ baixo.
  • Regime Pós-mudança: O previsores EW continua preso ao antigo regime, enquanto o FS adapta-se rapidamente. A diferença $\hat{S}_t$ cresce rapidamente.
  • Decisão: Se $\hat{S}_t$ excede um limiar $z$, um ponto de mudança é declarado.

3. Contribuições Principais

1. Algoritmo Não Paramétrico Online: Proposta de um método que não assume formas específicas para $p$ e $q$, apenas que seus scores (gradientes do log) são suaves e aproximáveis.
2. Extensão do Fixed Share para Domínio Contínuo: Desenvolvimento de uma versão do algoritmo Fixed Share para um número infinito de especialistas com perdas quadráticas, fornecendo fórmulas de fechamento (closed-form) recursivas para previsões e normalização.
3. Limites Teóricos Rigorosos: Derivação de limites de alta probabilidade (não assintóticos) para a estatística de teste:
   • Pré-mudança: Limites superiores mostrando que a estatística cresce apenas logaritmicamente (controlando falsos positivos).
   • Pós-mudança: Limites inferiores garantindo que a estatística cresça linearmente com o tempo após a mudança (garantindo detecção rápida).
4. Eficiência Computacional: O algoritmo evita o cálculo de integrais de alta dimensão, tornando-o aplicável a cenários onde métodos baseados em verossimilhança (como os de Cao et al., 2018) falham.

4. Resultados Experimentais

Os autores validaram o algoritmo (denominado Algorithm 3.1) em dados sintéticos e do mundo real, comparando-o com métodos de ponta como FLH, FALCON, KLIEP e detectores baseados em Kernel (M-statistic).

• Dados Sintéticos: Em testes de mudança de média e variância (univariados e multivariados), o algoritmo proposto demonstrou menores atrasos de detecção (Average Detection Delay - DD) e zero falsos positivos na maioria dos cenários, superando consistentemente os concorrentes.
• Detecção de Atividade Humana (WISDM): Utilizando dados de acelerômetros de smartphones, o método detectou mudanças de atividade com um atraso médio de 15.43 amostras, superando o FLH (16.29) e o FALCON (18.43), mantendo apenas 1 falso alarme.
• Detecção de Fala e Ocupação de Sala: Em dados de áudio (CENSREC) e sensores de ambiente, o algoritmo manteve desempenho superior ou competitivo, especialmente em cenários com ruído, demonstrando robustez.

5. Significado e Impacto

Este trabalho é significativo por várias razões:

• Quebra de Barreiras Paramétricas: Permite a detecção de mudanças em distribuições complexas onde a função de partição é intratável, algo que limitava o uso prático de métodos baseados em otimização online convexa anteriores.
• Fundamentação Teórica Sólida: Oferece garantias rigorosas de desempenho (limites de erro Tipo I e II) em um regime não paramétrico, algo raro na literatura de detecção online.
• Eficiência Prática: A recursividade do algoritmo permite sua aplicação em tempo real em fluxos de dados de alta dimensão, tornando-o uma ferramenta viável para monitoramento de sistemas críticos, qualidade de dados e segurança cibernética.

Em resumo, o artigo apresenta uma solução elegante e matematicamente fundamentada para o problema de detecção de mudanças, unindo a teoria de aprendizado online com estimativas de score, superando as limitações computacionais e de modelagem de abordagens anteriores.