Post-detection inference for sequential changepoint localization

Título: Inferência Pós-Detecção para Localização de Mudanças Sequenciais

1. O Problema

O artigo aborda um desafio fundamental e pouco explorado na análise de mudanças sequenciais: realizar inferência estatística válida após a detecção de uma mudança.

• Contexto: Dados $X_1, X_2, \dots$ chegam sequencialmente. Em um tempo desconhecido $T$ (o ponto de mudança), a distribuição dos dados muda de $F_0$ (pré-mudança) para $F_1$ (pós-mudança).
• O Cenário: Um algoritmo de detecção sequencial $\mathcal{A}$ (uma "caixa preta") monitora os dados e gera um tempo de parada $\tau$ quando suspeita que uma mudança ocorreu.
• A Lacuna: Quando o algoritmo dispara um alarme em $\tau$, sabemos que uma mudança pode ter ocorrido antes de $\tau$, mas não sabemos quando exatamente ($T$). A literatura tradicional foca em detectar a mudança o mais rápido possível, mas carece de métodos para construir conjuntos de confiança para $T$ após a detecção, especialmente sem assumir modelos paramétricos específicos ou depender de propriedades assintóticas.
• Desafio Teórico: O artigo demonstra que é impossível garantir uma cobertura incondicional (ou seja, $P(T \in C) \ge 1-\alpha$) para qualquer algoritmo com tempo médio de execução finito (ARL finito), pois o algoritmo pode disparar um alarme falso ($\tau < T$). Portanto, o objetivo é garantir uma cobertura condicional:
  $$P(T \in C \mid \tau \ge T) \ge 1 - \alpha$$
  Ou seja, o conjunto de confiança deve cobrir o verdadeiro ponto de mudança dado que o algoritmo parou após a mudança ocorrer.

2. Metodologia

Os autores propõem um framework geral e não paramétrico baseado na inversão de testes de hipóteses utilizando e-processos (e-processes) e simulação.

A. Estrutura Geral (Método Universal)

1. Teste de Hipótese: Para cada candidato $t \in \{1, \dots, \tau\}$, testa-se a hipótese nula $H_{0,t}$: "A mudança ocorreu em $t$".
2. Estatística de Teste ($M_t$):
   • Utiliza-se e-processos (ferramentas de inferência válida a qualquer tempo) para acumular evidências.
   • Define-se um processo e-processo "para frente" ($R^{(t)}_n$) que acumula evidência contra $H_{0,t}$ na direção da distribuição pós-mudança.
   • Define-se um processo e-processo "para trás" ($S^{(t)}_n$) que acumula evidência contra $H_{0,t}$ na direção da distribuição pré-mudança.
   • A estatística final $M_t$ é o máximo dessas evidências acumuladas em janelas válidas antes e depois de $t$.
3. Limiar (Threshold):
   • Para garantir o nível de significância condicional, o limiar depende da probabilidade de o algoritmo ter parado após o tempo $t$ sob a hipótese de nenhuma mudança ($P_{F_0}(\tau \ge t)$).
   • Como essa probabilidade é desconhecida, o método utiliza um estimador não enviesado $r_t$ obtido via simulação de Monte Carlo (gerando sequências apenas da distribuição pré-mudança $F_0$ e rodando o algoritmo $\mathcal{A}$).
4. Construção do Conjunto: O conjunto de confiança $C$ contém todos os $t$ onde a estatística $M_t$ não excede o limiar ajustado por $r_t$.

B. Extensões

• Classes Compostas Pré-Mudança: Quando $F_0$ não é conhecida, mas pertence a uma classe $P_0$, o método assume a existência de uma Distribuição Menos Favorável (LFD) (Huber) que maximiza o tempo de parada, permitindo a construção de limites válidos.
• Métodos Adaptativos (Paramétricos): Para cenários paramétricos (distribuições conhecidas ou classes paramétricas), os autores propõem um método baseado em simulação que calcula quantis exatos da distribuição da estatística de teste, permitindo dependência entre observações e conjuntos de confiança mais estreitos.

3. Principais Contribuições

1. Primeiro Framework Geral: Apresenta o primeiro método geral, não paramétrico e teoricamente fundamentado para localização de mudanças sequenciais pós-detecção.
2. Agnóstico ao Algoritmo: O método funciona como um "wrapper" (envoltório) para qualquer algoritmo de detecção sequencial existente (desde CUSUM clássico até pipelines complexos de Machine Learning), sem exigir conhecimento interno do algoritmo.
3. Validade Não Assintótica: As garantias de cobertura são válidas para amostras finitas, diferentemente de trabalhos anteriores que dependem de limites assintóticos ($T \to \infty$).
4. Inferência de Parâmetros: O framework permite derivar conjuntos de confiança para os parâmetros desconhecidos das distribuições pré e pós-mudança ($\theta_0, \theta_1$) a partir do conjunto de confiança de $T$.
5. Tratamento de Dependência: Enquanto o método universal assume independência, a versão adaptativa baseada em simulação lida com dados dependentes (ex: cadeias de Markov).

4. Resultados Experimentais

Os autores validaram o método através de extensas simulações e um caso de uso real:

• Cenários Testados:
  • Mudança de média Gaussiana (pré e pós conhecidos).
  • Classes compostas paramétricas (pré e/ou pós desconhecidos).
  • Cenários não paramétricos (distribuições Sub-Gaussianas).
  • Cenários robustos (modelo de contaminação de Huber).
  • Dados dependentes (Cadeias de Markov).
  • Dados Reais: Localização de mudança de sentimento em textos (dataset SST-2), simulando uma transição de reviews positivos para negativos.
• Desempenho:
  • Cobertura: Os conjuntos de confiança atingiram consistentemente a cobertura condicional alvo (ex: 90% ou 95%), sendo ligeiramente conservadores (cobertura real > alvo), o que é desejável para garantir segurança.
  • Tamanho: Os conjuntos têm tamanhos razoáveis. O método adaptativo (paramétrico) tende a produzir conjuntos mais estreitos que o método universal, mas com custo computacional maior.
  • Comparação: Ao comparar com o método de Wu (2007) [42], o método proposto superou significativamente em termos de cobertura, enquanto o método anterior mostrou subcobertura (falha em cobrir o verdadeiro $T$ com a frequência prometida) devido às suas aproximações assintóticas.

5. Significância e Conclusão

Este trabalho preenche uma lacuna crítica na literatura de análise de mudanças. Até então, a detecção de mudanças era bem estudada, mas a localização (determinar quando exatamente a mudança ocorreu com garantias estatísticas) era negligenciada ou restrita a cenários muito específicos.

• Impacto Prático: Permite que analistas de dados e engenheiros de ML não apenas saibam que algo mudou, mas possam quantificar a incerteza sobre quando isso aconteceu, essencial para auditoria, diagnóstico de falhas e monitoramento em tempo real.
• Flexibilidade: A capacidade de funcionar como uma "caixa preta" sobre qualquer detector existente torna a metodologia imediatamente aplicável em indústrias que utilizam algoritmos complexos e heurísticos, sem necessidade de reformular todo o pipeline de detecção.

Em resumo, o artigo estabelece um novo padrão para inferência pós-detecção, oferecendo garantias rigorosas, não assintóticas e amplamente aplicáveis.