When lookout sees crackle: Anomaly detection via kernel density estimation

Título: Quando o Lookout vê "Crackle": Detecção de Anomalias via Estimativa de Densidade de Kernel

Autores: Rob J Hyndman, Sevvandi Kandanaarachchi e Katharine Turner.

---

1. Problema e Contexto

A detecção de anomalias é crucial em diversas áreas, como detecção de fraude e segurança. O algoritmo Lookout, proposto anteriormente por Kandanaarachchi e Hyndman (2022), utiliza estimativas de densidade de kernel (KDE) com largura de banda (bandwidth) baseada em homologia persistente (especificamente, os diâmetros de morte no complexo de Rips). O método identifica anomalias ajustando uma Distribuição de Pareto Generalizada (GPD) aos logaritmos negativos das menores estimativas de densidade.

No entanto, a versão original apresentava limitações teóricas e práticas:

1. Falta de Consistência Teórica: A escolha da largura de banda baseada no maior salto nos diâmetros de morte ($d^*$) não garante a consistência do estimador de densidade para distribuições com caudas pesadas (fat-tailed).
2. Robustez: O uso de escalonamento min-max e a dependência do maior salto nos diâmetros tornam o algoritmo sensível a outliers.
3. Estrutura de Correlação: A matriz de largura de banda diagonal não considera correlações entre variáveis.
4. Estabilidade do Ajuste: O ajuste da GPD fazia poucas suposições sobre a distribuição dos valores de "surprisal" (sorpresa), ignorando que as estimativas de densidade são limitadas.

2. Metodologia Proposta (Lookout V2)

Os autores propõem uma versão modificada do algoritmo baseada em fundamentos teóricos rigorosos, introduzindo três alterações principais:

A. Teoria da Largura de Banda e "Crackle"

O artigo utiliza o conceito de crackle (introduzido por Adler et al., 2014) para analisar a homologia persistente de ruído.

• Problema: Para distribuições Gaussianas, o maior diâmetro de morte ($d_{n-1}$) converge para zero. Porém, para distribuições de cauda pesada, isso não é garantido, tornando a largura de banda original inadmissível.
• Solução: Em vez de usar o maior salto ($d^*$), o novo algoritmo utiliza um quantil superior dos diâmetros de morte de Rips (denotado como $d_{\gamma(n-1)}$, onde $\gamma \in (0,1)$, tipicamente 0.98).
• Teorema: Os autores provam que $d_{\gamma(n-1)}$ converge para zero e satisfaz as condições para ser uma largura de banda admissível (garantindo consistência do KDE) para uma ampla gama de distribuições, incluindo aquelas com caudas pesadas.

B. Escalonamento Robusto Multivariado

Substitui-se o escalonamento min-max (usado na versão original) por um escalonamento e rotação robustos.

• Utiliza-se o estimador de covariância robusto de Gnanadesikan-Kettenring ortogonalizado.
• Os dados são transformados para que a matriz de covariância seja aproximadamente a identidade.
• Benefício: Isso remove correlações entre variáveis, melhora a eficiência da KDE e torna o processo robusto a outliers, ao contrário do min-max.

C. Restrição de Parâmetros na GPD

Ao ajustar a Distribuição de Pareto Generalizada (GPD) aos valores de surpresa ($-\log \hat{f}(y)$):

• O parâmetro de forma ($\xi$) é constrangido a ser não-positivo ($\xi \le 0$).
• Justificativa: Como as estimativas de densidade de kernel são limitadas superiormente, a distribuição extrema limite (via Teorema de Fisher-Tippett-Gnedenko) deve ser uma distribuição de Weibull, que possui $\xi < 0$. Essa restrição melhora a estabilidade do ajuste da GPD.

3. Contribuições Principais

1. Garantias Teóricas: Prova de consistência do estimador de densidade de kernel sob condições mais amplas, demonstrando que a escolha anterior de largura de banda falha em distribuições de cauda pesada, enquanto a nova escolha baseada em quantis é admissível.
2. Algoritmo Modificado: Apresentação do "Lookout V2" com três melhorias estruturais (escalonamento robusto, seleção de banda por quantil e restrição de parâmetros da GPD).
3. Análise de "Crackle": Adaptação da teoria de homologia persistente de ruído para justificar a escolha da largura de banda em cenários de detecção de anomalias.
4. Implementação: O algoritmo está disponível no pacote R lookout.

4. Resultados Experimentais

Os autores realizaram extensas comparações em dados simulados e reais:

• Comparação Lookout V1 vs. V2:

  • Em distribuições Gamma e Normal, a versão modificada demonstrou maior sensibilidade na detecção de anomalias, especialmente quando as anomalias estão próximas da distribuição normal ou em regiões de baixa densidade.
  • A versão V2 apresentou taxas de verdadeiros positivos (TPR) mais altas e taxas de falsos negativos (FNR) mais baixas, embora com uma ligeira tendência a mais falsos positivos em cenários muito específicos (o que é consistente com a definição de anomalia baseada em densidade baixa).
  • Em dados reais (Geysers Old Faithful e Avaliações de Vinho), o V2 identificou anomalias em regiões de baixa densidade que a versão antiga ignorava, e evitou marcar pontos próximos à nuvem principal como anomalias.

• Comparação com Outros Métodos:

  • O Lookout V2 foi comparado com métodos baseados em Teoria de Valores Extremos (HDoutliers, stray) e KDE (KDEOS, RDOS).
  • O algoritmo manteve desempenho competitivo, frequentemente superando os outros em métricas como G-mean e F-measure, especialmente em iteracões onde as anomalias se tornavam mais sutis ou em dimensões mais altas (até 20 dimensões).

5. Significado e Conclusão

O artigo representa um avanço significativo na detecção de anomalias baseada em topologia e densidade. Ao fornecer garantias teóricas para a seleção de largura de banda e corrigir fragilidades de robustez, o Lookout V2 torna-se uma ferramenta mais confiável para dados multivariados contínuos.

• Pontos Fortes: Consistência teórica, robustez a outliers, interpretação probabilística via Teoria de Valores Extremos e adaptação automática à estrutura topológica local.
• Limitações: A complexidade computacional é dominada pelo cálculo da homologia persistente de Rips (equivalente a clustering de ligação simples, $O(n \log n)$), o que pode ser um gargalo para conjuntos de dados massivos. Além disso, como a maioria dos métodos baseados em KDE, pode sofrer com a "maldição da dimensionalidade" em dimensões muito altas, embora funcione bem até ~20 dimensões.

Em suma, o trabalho transforma o Lookout de um algoritmo heurístico eficaz para uma metodologia estatisticamente fundamentada, capaz de lidar com uma gama mais ampla de distribuições de dados.