DCFO: Density-Based Counterfactuals for Outliers -- Additional Material

Resumo Técnico: DCFO - Contrafactuais Baseados em Densidade para Outliers

Declaração do Problema
A detecção de outliers é crítica para identificar anomalias em domínios como detecção de fraudes e diagnóstico de falhas de sistema. No entanto, explicar por que um ponto de dados específico é sinalizado como um outlier permanece um desafio significativo. Embora explicações contrafactuais — identificando mudanças mínimas necessárias para alterar a previsão de um modelo — sejam uma técnica popular em IA Explicável (XAI), os métodos existentes lutam com algoritmos de detecção de outliers, particularmente o Fator de Outlier Local (LOF).

O LOF quantifica a condição de outlier com base na densidade local relativa. Um desafio fundamental na geração de contrafactuais para o LOF é sua natureza não contínua: pequenas mudanças em uma observação podem alterar abruptamente seu conjunto de $k$-vizinhos mais próximos, causando saltos descontínuos na pontuação de outlier. Essa descontinuidade torna os métodos padrão de otimização baseados em gradiente ineficazes, pois eles dependem de transições suaves de previsão. Por outro lado, abordagens alternativas como otimização bayesiana ou algoritmos genéticos, que não requerem gradientes, frequentemente incorrem em custos computacionais proibitivos em configurações de alta dimensionalidade ou falham em produzir contrafactuais válidos consistentemente. Além disso, muitos métodos existentes de contrafactuais são projetados para tarefas de classificação e não levam em conta a natureza desbalanceada específica da detecção de outliers ou as características frequentemente não acionáveis presentes em dados do mundo real.

Metodologia: DCFO
Os autores propõem Contrafactuais Baseados em Densidade para Outliers (DCFO), um método especificamente projetado para gerar explicações contrafactuais para o LOF. A inovação central do DCFO é a exploração da estrutura interna do LOF para permitir otimização eficiente baseada em gradiente, apesar da não continuidade subjacente.

1. Particionamento Baseado em Regiões: O DCFO particiona o espaço de dados em regiões onde a pontuação LOF se comporta de forma suave. Uma região é definida por uma "chave" única $K(x)$, que codifica o conjunto de $k$-vizinhos mais próximos de um ponto $x$ e os $k$-vizinhos mais próximos de cada um desses vizinhos. Dentro de qualquer região $R_K$, o conjunto de pontos que influenciam o cálculo do LOF permanece fixo.
2. Diferenciabilidade: Os autores provam que, dentro de uma região específica $R_K$, a função de pontuação LOF, denotada como $LOF_K(x)$, é contínua e diferenciável em quase todos os pontos (assumindo uma função de distância bem comportada, como a distância euclidiana). Essa propriedade permite o uso de otimizadores eficientes baseados em gradiente.
3. Processo de Otimização:
   • O algoritmo começa com um outlier $p_i$ e calcula sua chave de região $K$.
   • Resolve um problema de otimização restrita para encontrar um ponto $x$ que minimize a distância a $p_i$, sujeito à restrição $LOF_K(x) \leq t$ (onde $t$ é o limiar de outlier).
   • A otimização utiliza Programação Quadrática Sequencial com Mínimos Quadrados (SLSQP).
   • Se o otimizador sair da região atual (ou seja, a chave mudar), o algoritmo reinicia recursivamente a otimização a partir do novo ponto usando a chave da nova região.
   • Para garantir diversidade, o método mantém uma fila de exploração de pontos que cruzaram limites de região, permitindo gerar múltiplos contrafactuais distintos ao iniciar novas otimizações a partir desses pontos.
4. Tratamento de Restrições:
   • Características Não Acionáveis: O DCFO permite que os usuários especifiquem características imutáveis (por exemplo, idade). O otimizador é restrito a ajustar apenas variáveis acionáveis, mantendo as características não acionáveis fixas.
   • Plausibilidade: Ao mirar pontuações LOF mais baixas (que correspondem a maior densidade local), o método direciona naturalmente os contrafactuais para regiões realistas e de alta densidade do espaço de características, evitando outliers implausíveis.

Principais Contribuições

• Primeiro Método de Contrafactuais Específico para LOF: O DCFO é o primeiro método explicitamente projetado para gerar contrafactuais para o algoritmo Fator de Outlier Local.
• Inovação Algorítmica: Introduz uma estratégia de particionamento de espaço que transforma o problema não diferenciável do LOF em uma série de subproblemas diferenciáveis, permitindo o uso de otimização baseada em gradiente.
• Tratamento de Características: O método incorpora mecanismos para lidar com características não acionáveis, gerar múltiplos contrafactuais diversos e garantir plausibilidade através do direcionamento de densidade.
• Validação Empírica: Os autores fornecem benchmarks extensos em 50 conjuntos de dados OpenML.

Resultados Experimentais
O artigo avalia o DCFO contra três concorrentes: Baycon (baseado em otimização bayesiana), EACE (baseado em algoritmo genético) e uma Linha de Base (mover o outlier para o inlier mais próximo).

• Validade: O DCFO alcançou uma pontuação de validade de 1,00 em todos os 50 conjuntos de dados, significando que encontrou com sucesso um contrafactual válido para cada outlier. Em contraste, o Baycon alcançou 0,84, o EACE 0,38 e a Linha de Base 0,88. Os autores observam que o EACE e a Linha de Base frequentemente falharam em produzir contrafactuais válidos devido à paisagem não contínua do LOF.
• Proximidade: O DCFO produziu consistentemente contrafactuais mais próximos dos outliers originais do que os concorrentes. A análise estatística usando diagramas de diferença crítica (teste de Nemenyi) confirmou que o desempenho de proximidade do DCFO foi significativamente melhor do que o do Baycon, que ficou em segundo lugar.
• Diversidade: Ao gerar múltiplos contrafactuais, o DCFO demonstrou superioridade estatisticamente significativa em diversidade em comparação com outros métodos, fornecendo uma gama mais ampla de alternativas acionáveis.
• Características Não Acionáveis: Em experimentos onde um subconjunto de características foi restrito, o DCFO manteve validade mais alta e melhor proximidade do que o Baycon, demonstrando robustez a restrições de características.
• Eficiência: Embora a Linha de Base fosse a mais rápida, a abordagem baseada em gradiente do DCFO foi significativamente mais eficiente do que as abordagens bayesiana (Baycon) e genética (EACE).

Significado e Alegações
O artigo alega que o DCFO aborda uma lacuna crítica na XAI para detecção de outliers, tornando o algoritmo LOF amplamente utilizado, mas opaco, interpretável. Ao particionar o espaço de dados para lidar com as descontinuidades do LOF, o DCFO fornece explicações acionáveis, válidas e diversas que os métodos existentes não podem gerar de forma confiável. Os autores enfatizam que seu método não apenas explica por que uma instância é um outlier, mas também fornece etapas mínimas concretas para corrigi-la, facilitando assim medidas preventivas e construindo confiança em sistemas de detecção de outliers. O trabalho é apresentado como um passo fundamental, com trabalhos futuros sugeridos para estender a abordagem a outras variantes do LOF e minimizar o número de características alteradas.