Uncovering Discrimination Clusters: Quantifying and Explaining Systematic Fairness Violations

Resumo Técnico: Uncovering Discrimination Clusters

1. O Problema

A justiça em sistemas de decisão algorítmica é frequentemente definida sob a ótica da justiça individual, que exige que indivíduos semelhantes recebam resultados semelhantes. Uma violação clássica ocorre quando dois inputs que diferem apenas em atributos protegidos (como raça ou gênero) produzem resultados significativamente diferentes.

No entanto, os autores argumentam que essa definição binária (justo/ injusto) é insuficiente porque:

• Foca em violações isoladas (pares de indivíduos) e ignora padrões sistemáticos de discriminação.
• Não captura a arbitrariedade em larga escala, onde pequenas perturbações em atributos protegidos levam a múltiplos resultados distintos para um mesmo grupo de indivíduos semelhantes.
• As ferramentas atuais de verificação formal (exaustivas) têm dificuldade de escalar para propriedades complexas, enquanto métodos de teste aleatório muitas vezes falham em detectar violações em regiões de "baixo sinal" ou platôs de justiça.

O objetivo é ir além da detecção de pares discriminatórios (2-discriminantes) para identificar agrupamentos de discriminação (discrimination clusters), onde um único input base, variando apenas os atributos protegidos, gera $k$ resultados distintos (com $k > 2$).

2. Metodologia: O Framework HYFAIR

O paper apresenta o HYFAIR, uma técnica híbrida que combina análise simbólica formal e busca aleatória para detectar, quantificar e explicar clusters de discriminação. O fluxo de trabalho divide-se em três fases principais:

A. Definição do Problema ($k$-Discriminante)

• Um modelo é definido como $k$-discriminante se, para um conjunto de $K$ inputs que compartilham os mesmos atributos não protegidos, mas diferem nos atributos protegidos, o modelo produzir $k$ resultados distintos (onde $2 \le k \le K$).
• Isso generaliza a justiça individual: se um modelo não é 2-fair, ele é trivialmente $k$-fair para todo $k \ge 2$. O foco é encontrar o $k$ máximo de discriminação.

B. Fase de Busca (Verificação + Busca Aleatória)
O HYFAIR opera em um ciclo iterativo:

1. Certificação Formal (2-Fairness): Utiliza Programação Linear Inteira Mista (MILP) e solvers SMT para verificar a justiça individual. Diferente de abordagens puramente baseadas em SMT (como o FAIRIFY), o uso de MILP permite encontrar contraexemplos (instâncias discriminatórias) mais rapidamente e em regiões diversas do espaço de entrada.
2. Expansão para $k$-Discriminação: Uma vez encontrado um contraexemplo (uma instância 2-discriminante), o sistema inicia uma busca aleatória local ao redor desse "seed".
   • Utiliza Simulated Annealing (SA) e variações com vizinhos mais próximos (SA+KNN) para explorar o espaço de entrada.
   • O objetivo é maximizar o número de clusters distintos ($k$) encontrados ao perturbar os atributos protegidos.
   • O solver formal é usado periodicamente para gerar novas sementes, ajudando a escapar de platôs locais onde a busca aleatória poderia estagnar.

C. Fase de Depuração e Explicação (Debugging)
Para entender por que esses clusters ocorrem:

1. Geração de Vizinhos: Gera amostras vizinhas aos inputs que exibem a máxima discriminação ($k$-discriminante).
2. Aprendizado de Máquina Explicável (XAI): Treina uma Árvore de Decisão sobre esses dados, rotulando-os como "alta discriminação" vs. "baixa discriminação".
3. Extração de Regras: A árvore de decisão gera predicados lógicos (regras if-then) que descrevem as condições dos atributos não protegidos sob as quais o modelo se torna arbitrário em relação aos atributos protegidos.
4. Mitigação: Essas regras são usadas para:
   • Criar "guardrails" (barreiras) que rejeitam consultas que caem nessas regiões de alto risco.
   • Fine-tuning do modelo (re-treinamento) usando os casos discriminatórios identificados.

3. Contribuições Principais

1. Novo Conceito de Justiça: Introdução da noção de $k$-discriminante, que quantifica a arbitrariedade sistemática em clusters de resultados, indo além da verificação binária de pares.
2. Abordagem Híbrida (HYFAIR): Integração de solvers MILP (para certificação e geração de sementes) com busca aleatória (Simulated Annealing) para escalar a detecção de violações complexas.
3. Método de Explicação Inovador: Um framework que utiliza árvores de decisão para explicar a raiz de clusters de discriminação, identificando condições comuns em atributos não protegidos que levam a resultados arbitrários.
4. Estratégias de Mitigação: Demonstração prática de como usar as explicações para reduzir a discriminação via regras de guarda e re-treinamento.

4. Resultados Experimentais

Os autores avaliaram o HYFAIR em 20 benchmarks de DNNs (usando conjuntos de dados como Adult Census Income e Bank Marketing), comparando com o estado da arte (FAIRIFY, LIME, etc.):

• RQ1 (Eficiência na Detecção 2-Fair): O HYFAIR superou o FAIRIFY em 85% dos casos, encontrando mais instâncias discriminatórias individuais (IDs) em menos tempo. O uso de MILP mostrou-se superior ao SMT puro para encontrar contraexemplos em regiões de fronteira.
• RQ2 (Busca de $k$-Discriminação): O algoritmo de Simulated Annealing (SA) foi o mais eficaz, identificando instâncias com o máximo de clusters ($k$) em 94% dos casos, superando buscas aleatórias simples (RW) e variantes com KNN.
• RQ3 (Qualidade da Explicação): Comparado ao LIME, o HYFAIR forneceu explicações mais robustas e concisas. As regras extraídas cobriram um volume maior do espaço de entrada e mostraram maior estabilidade (robustez) quando os atributos eram perturbados.
• RQ4 (Mitigação): A aplicação de regras de decisão como guardrails reduziu a taxa de sucesso na reprodução de bugs de justiça de 87,7% para 36,3% no benchmark AC2. O re-treinamento com os dados identificados também reduziu significativamente o número de instâncias discriminatórias, embora tenha havido um trade-off leve na acurácia geral (redução de até 2%).

5. Significado e Impacto

Este trabalho é significativo porque muda o paradigma da verificação de justiça de uma busca por "erros isolados" para a caracterização de padrões sistemáticos de arbitrariedade.

• Visão Sistêmica: Revela que alguns modelos não apenas discriminam ocasionalmente, mas operam de forma altamente inconsistente para grupos inteiros baseados em atributos protegidos.
• Ação Prática: Fornece não apenas a detecção, mas a explicação causal (através de regras lógicas) e caminhos para mitigação, permitindo que desenvolvedores de software entendam onde e por que o modelo falha.
• Limitações: O método ainda lida com atributos protegidos de forma isolada (não considera interseccionalidade complexa) e pode gerar contrafatuais pouco realistas, embora o uso de GANs seja sugerido como melhoria futura.

Em suma, o HYFAIR oferece uma ferramenta poderosa para auditar sistemas de IA de alto risco, quantificando a gravidade da discriminação e fornecendo insights acionáveis para corrigir vieses estruturais em redes neurais profundas.