Anomaly detection using surprisals

Este artigo propõe um quadro unificado para deteção de anomalias que define estas como observações com baixa probabilidade sob um modelo, calculando uma pontuação baseada na probabilidade da sua "surprisal" (negativo do logaritmo da densidade generalizada) e estimando essa probabilidade através de métodos empíricos ou de valores extremos, demonstrando eficácia mesmo sob especificação incorreta do modelo.

O essencial

Imagine que você é um detetive tentando encontrar um intruso em uma festa lotada. Normalmente, os métodos de detecção de anomalias (ou "outliers") são como vigias que só olham para as portas de saída ou para quem está gritando no canto mais escuro da sala. Eles ignoram alguém que está quieto, vestido de forma estranha, mas parado no meio da multidão, ou alguém que está em um "vazio" entre dois grupos de pessoas conversando.

Este artigo, escrito por Rob J Hyndman e David T Frazier, propõe uma nova maneira de fazer essa detecção, baseada em uma ideia chamada "Surprisal" (que poderíamos traduzir como "Fator de Surpresa").

Aqui está a explicação passo a passo, usando analogias do dia a dia:

1. O Conceito Central: A Medida da "Surpresa"

Em vez de medir apenas o quão longe alguém está do centro da festa (como fazem os métodos tradicionais), os autores propõem medir o quão improvável é a presença daquela pessoa, dado o modelo da festa.

• A Analogia: Imagine que você tem um mapa mental de como a festa deveria ser.
  • Se alguém está dançando no meio da pista (onde a maioria está), a "surpresa" é baixa. É normal.
  • Se alguém está no fundo da sala, mas ainda dentro do padrão de comportamento, a surpresa é média.
  • Se alguém está em um lugar onde ninguém costuma estar (um "buraco" entre os grupos, ou um lugar onde a música não chega), a "surpresa" é altíssima.

O "Surprisal" é apenas um número que calcula essa improbabilidade. Quanto maior o número, mais "surpreendente" (e potencialmente anômala) é a observação.

2. O Grande Truque: Transformar o Caos em uma Linha

O problema com dados complexos (como multidões em 3D, ou dados com muitas variáveis) é que é difícil desenhar um mapa de "onde está o perigo".

• A Solução: Os autores dizem: "Esqueça a forma da festa. Vamos apenas olhar para o nível de surpresa de cada pessoa."
• A Metáfora: Imagine que você pega todas as pessoas da festa e as coloca em uma única fila, ordenadas do "menos surpreendente" (o mais comum) para o "mais surpreendente" (o mais estranho).
  • Agora, em vez de analisar um mapa complexo, você só precisa olhar para a ponta da fila.
  • A pergunta muda de "Onde essa pessoa está no espaço?" para "O quão longe ela está no topo da lista de surpresas?".

Isso transforma um problema matemático muito difícil (multidimensional) em um problema simples (unidimensional).

3. O Que Acontece Quando o Mapa Está Errado? (A Robustez)

Aqui está a parte mais brilhante do artigo. Normalmente, se o seu mapa da festa estiver errado (por exemplo, você achava que todos dançavam samba, mas na verdade todos estavam dançando rock), você não conseguiria encontrar os intrusos.

• O Problema Tradicional: Se você usa um modelo errado, seus cálculos de "quem é estranho" ficam totalmente errados.
• A Solução dos Autores: Eles mostram que, mesmo que seu mapa inicial esteja um pouco errado, você pode usar duas técnicas para corrigir a lista de surpresas:
  1. O Método Empírico (Olhar para a própria fila): Em vez de confiar na teoria de como a fila deveria ser, você simplesmente conta quantas pessoas na fila real têm um nível de surpresa igual ou maior que o da pessoa que você está analisando. É como dizer: "Não importa o que o mapa diz, olhe quantas pessoas aqui são mais estranhas que você".
  2. O Método GPD (Adivinhar o topo da montanha): Se a fila for muito longa e você não tiver dados suficientes para ver o topo, eles usam uma ferramenta estatística (Teoria de Valores Extremos) para prever como é a "ponta" da fila, mesmo que você não tenha visto ninguém tão extremo assim ainda.

A Lição: É melhor errar assumindo que a "montanha de surpresas" é mais alta e íngreme do que assumir que é baixa. Se você assumir que a anomalia é mais rara do que ela realmente é, você ainda a pega. Se assumir que é comum, você a perde.

4. Exemplos Reais da Vida

Os autores testaram isso com dois exemplos fascinantes:

• Mortalidade na França: Eles analisaram dados de mortes ao longo de 200 anos. O modelo "normal" previa uma certa taxa de morte. Quando usaram o "Fator de Surpresa", conseguiram identificar automaticamente anos de guerras e epidemias (como a Gripe Espanhola de 1918 ou a Guerra Franco-Prussiana). O sistema percebeu que, naqueles anos, a "surpresa" de morrer era altíssima, mesmo que o modelo estatístico não soubesse exatamente o que era uma guerra.
• Críquete (Beisequete): Eles analisaram jogadores de críquete. A maioria dos jogadores é eliminada (faz "out") em certo número de vezes. O sistema encontrou um jogador (Jimmy Anderson) que parecia "estranho". Ele não era um jogador ruim, mas era um "especialista em defesa" que ficava na mesa por muito tempo sem ser eliminado. O modelo tradicional diria que ele é apenas um jogador com uma média alta, mas o modelo de "surpresa" viu que a probabilidade dele ficar tanto tempo sem ser eliminado, dado o modelo, era tão baixa que era uma anomalia estatística.

Resumo em uma Frase

Este artigo ensina que, para encontrar o "estranho" em qualquer grupo de dados, não precisamos de um mapa perfeito do mundo. Basta calcular o quão "surpreendente" cada coisa é, ordenar essas surpresas e olhar para o topo da lista. Mesmo que nossa teoria inicial esteja errada, se olharmos para a lista real de surpresas, ainda conseguiremos encontrar os intrusos.

É como se dissessem: "Não importa se você conhece a música da festa; basta olhar para quem está cantando fora de tom."

Resumo técnico

Resumo Técnico: Detecção de Anomalias usando Surprisais

1. O Problema

Os métodos tradicionais de detecção de anomalias frequentemente dependem de regras ad hoc, assumem distribuições estatísticas fortes que podem não se aplicar na prática ou focam excessivamente em eventos de cauda (outliers extremos). Uma lacuna crítica identificada pelos autores é a incapacidade desses métodos de detectar anomalias "inliers" — observações que ocorrem em regiões de baixa densidade entre modos de uma distribuição (por exemplo, em distribuições multimodais), mas que não estão necessariamente nas caudas extremas. Além disso, muitos métodos baseados em distância falham em lidar com distribuições assimétricas ou de cauda pesada.

O objetivo do artigo é propor um framework unificado que defina uma anomalia como uma observação com probabilidade anormalmente baixa sob um modelo (possivelmente mal especificado), permitindo a detecção de anomalias em qualquer parte da distribuição, não apenas nas caudas.

2. Metodologia Proposta

A abordagem central baseia-se no conceito de surprisal (surpresa), definido como o logaritmo negativo da densidade generalizada de probabilidade.

• Definição de Surprisal: Para uma observação $y_i$ e uma função de densidade generalizada $f$, o surprisal é $s_i = -\log f(y_i)$.
  • Valores altos de $s_i$ indicam baixa densidade (observações "surpreendentes" ou potenciais anomalias).
  • Valores baixos indicam alta densidade (observações típicas).
• Transformação do Problema: O método converte o problema de detecção de anomalias em dados multivariados (ou em espaços complexos) para o problema univariado de estimar a cauda superior da distribuição de surprisais $G(s)$.
• Pontuação de Anomalia: A pontuação de anomalia $p_i$ é definida como a probabilidade de observar um surprisal tão grande quanto ou maior que o observado: $p_i = \Pr(S \ge s_i)$. Uma observação é classificada como anomalia se $p_i < \alpha$.

O artigo propõe três abordagens para estimar essas probabilidades de cauda, sendo as duas últimas robustas a erros de especificação do modelo:

1. Baseada no Modelo Assumido: Usa a distribuição $F$ diretamente (sensível a erros de especificação).
2. Estimador Empírico: Usa a função de distribuição empírica dos valores de surprisal observados.
3. Estimador de Teoria de Valores Extremos (GPD): Ajusta uma Distribuição de Pareto Generalizada (GPD) aos maiores valores de surprisal para estimar as probabilidades de cauda.

3. Contribuições Chave e Resultados Teóricos

A. Robustez à Especificação do Modelo
O principal avanço teórico é demonstrar que é possível usar um modelo de densidade incorreto (mal especificado) para calcular os surprisais, desde que a ordenação das regiões de baixa densidade seja preservada.

• Condição para o Método Empírico: O artigo estabelece que o estimador empírico é preciso se houver uma transformação estritamente crescente entre os surprisais do modelo ajustado e os da distribuição verdadeira na cauda superior (Assunção 2.1). Isso significa que o modelo não precisa ter a forma correta da cauda, apenas identificar corretamente onde estão as regiões de baixa densidade.
• Garantias de Confiança: São derivadas garantias de confiança de amostra finita para o método empírico usando a desigualdade de Dvoretzky–Kiefer–Wolfowitz.

B. Teoria de Valores Extremos para Surprisais
O artigo estende a teoria de valores extremos para a distribuição de surprisais sob três condições de cauda:

1. Sub-Gaussiana: (Densidades limitadas) $\rightarrow$ Convergência para distribuição de Weibull reversa.
2. Sub-Exponencial: (Densidades como a Normal) $\rightarrow$ Convergência para distribuição de Gumbel.
3. Polinomial: (Densidades como a Student-t) $\rightarrow$ Convergência para distribuição de Fréchet.

• Conclusão Teórica: Sob qualquer uma dessas condições, o máximo dos surprisais converge para uma distribuição de valores extremos generalizada. Isso justifica o uso da GPD para modelar a cauda dos surprisais, mesmo que a distribuição original $F$ esteja mal especificada.
• Implicação Prática: É mais seguro assumir caudas mais pesadas do que as reais (subestimar a leveza da cauda) do que o contrário. Assumir um modelo de cauda pesada para dados leves ainda produz resultados consistentes, enquanto assumir cauda leve para dados pesados leva a convergência lenta e detecção imprecisa.

C. Aplicações a Distribuições Condicionais
O framework é estendido para cenários de regressão e séries temporais, onde os dados são condicionados a variáveis explicativas ($X$). O método calcula o surprisal condicional $S = -\log f(Z|X)$, permitindo a detecção de anomalias que podem surgir de valores atípicos em $Z$, em $X$, ou de uma combinação de ambos que o modelo condicional não captura bem.

4. Resultados Empíricos e Aplicações

Simulações:

• Normal vs. t-Student: Mesmo usando uma distribuição $t(4)$ incorreta para dados gerados por uma Normal, e vice-versa, os métodos empírico e GPD forneceram estimativas de cauda precisas. O método baseado apenas no modelo assumido falhou, mas os métodos de correção de cauda (empírico e GPD) funcionaram bem.
• Gamma Bivariada vs. Normal: Em dados bivariados Gamma, o uso de uma distribuição Normal incorreta para calcular os surprisais resultou em estimativas precisas quando corrigidas pelo GPD, desde que a ordem das caudas fosse preservada. O uso de uma referência com cauda mais pesada (Student-t) funcionou melhor do que uma com cauda mais leve (Normal).

Aplicações do Mundo Real:

1. Taxas de Mortalidade Francesas (1816-1999):
   • O método detectou anomalias históricas significativas que coincidem com eventos reais: surtos de cólera (1832, 1849), Guerra Franco-Prussiana (1870), Comuna de Paris (1871), Primeira Guerra Mundial (1914-1918), Gripe Espanhola (1918) e Segunda Guerra Mundial (1940).
   • O filtro de "pelo menos três faixas etárias anômalas no mesmo ano" reduziu falsos positivos, isolando eventos de grande escala.
2. Críquete Teste (Não Eliminados - "Not Outs"):
   • Analisou-se a proporção de innings onde jogadores não foram eliminados.
   • O modelo identificou o jogador Jimmy Anderson como uma anomalia. Embora ele não fosse um batedor de elite, sua alta taxa de "não eliminados" (114 em 265 innings) era estatisticamente improvável dado o modelo binomial ajustado, revelando seu estilo defensivo único que permitia longas permanências na batata.

5. Significado e Conclusão

O artigo apresenta uma mudança de paradigma na detecção de anomalias:

• Separação de Modelagem e Estimativa: Separa a especificação de um modelo de trabalho (para calcular densidades) da estimativa das probabilidades de cauda (via empírico ou GPD).
• Robustez: O método é eficaz mesmo sob especificação substancialmente incorreta do modelo, desde que a ordem das regiões de baixa densidade seja mantida.
• Generalidade: Funciona para dados univariados, multivariados, discretos, contínuos e mistos, superando as limitações de métodos baseados em distância.
• Interpretabilidade: Fornece uma medida única e baseada em modelo de "improbabilidade" (surprisal) que é intuitiva e teoricamente fundamentada.

Os autores disponibilizaram o pacote R weird para implementação prática, facilitando a adoção deste framework em diversas áreas, desde estatística até ciência de dados aplicada.