Resumo Técnico: Agrupamento Não Enviesado para Representação de Atributos Consciente de Equidade

1. Definição do Problema

O artigo aborda a questão do agrupamento de atributos (ou bucketization), uma etapa comum de pré-processamento onde atributos contínuos brutos são discretizados em intervalos antes do compartilhamento de conjuntos de dados ou do treinamento de modelos. Embora o agrupamento seja usado para preservação de privacidade e redução de ruído, os autores argumentam que os métodos de agrupamento padrão (como o agrupamento de tamanho igual ou de frequência igual) podem inadvertidamente introduzir ou amplificar o viés contra grupos demográficos específicos.

O problema central é formulado como a busca por um $k$-agrupamento (particionamento de um atributo em $k$ baldes/compartimentos) que satisfaça a paridade de grupo.

• Agrupamento Não Enviesado: Um agrupamento é não enviesado se a proporção de cada grupo demográfico dentro de cada balde for igual à proporção global desse grupo em todo o conjunto de dados.
• Objetivo: O objetivo principal (Problema 1) é encontrar um agrupamento não enviesado que minimize o desvio de um agrupamento inicial de tamanho igual (especificamente, minimizando a diferença entre o tamanho máximo e mínimo dos baldes).
• Agrupamento $\epsilon$-Enviesado: Reconhecendo que um agrupamento perfeitamente não enviesado pode não existir ou pode acarretar um alto "preço da equidade" (desvio significativo dos tamanhos iguais), os autores introduzem um problema relaxado: encontrar um agrupamento onde a disparidade de grupo em qualquer balde seja de no máximo $\epsilon$.

2. Metodologia

O artigo propõe um conjunto de algoritmos adaptados para diferentes restrições e tamanhos de conjuntos de dados.

2.1 Solução Exata para Agrupamento Não Enviesado (Tamanho Igual)

Para o caso específico de encontrar um agrupamento não enviesado que minimize o desvio de tamanho em relação a uma linha de base de tamanho igual, os autores desenvolvem uma abordagem de Programação Dinâmica (DP).

• Candidatos de Fronteira: O algoritmo primeiro identifica um conjunto de "candidatos de fronteira". Um índice $i$ é um candidato se a proporção cumulativa de um grupo específico até $i$ corresponder à proporção global desse grupo. Os autores provam (Teorema 1) que qualquer agrupamento não enviesado ideal deve extrair suas fronteiras exclusivamente deste conjunto.
• Formulação de DP: O algoritmo utiliza uma função recursiva $OPT(j, \kappa)$ para particionar os primeiros $j$ candidatos de fronteira em $\kappa$ baldes não enviesados, rastreando a largura máxima e mínima dos baldes para minimizar sua diferença.
• Complexidade: O algoritmo executa em tempo $O(n \log n + m^2 k)$ e espaço $O(mk)$, onde $n$ é o tamanho do conjunto de dados, $m$ é o número de candidatos de fronteira e $k$ é o número de baldes.

2.2 Soluções para Agrupamento $\epsilon$-Enviesado

Como o conceito de candidato de fronteira não se estende ao cenário relaxado de $\epsilon$-enviesado, e a abordagem exata de DP para este cenário possui complexidade de tempo quadrática ($O(n^2 k)$), os autores propõem uma abordagem de dois passos escalável na prática:

1. Divisão e Conquista (D&C):

   • Este algoritmo particiona recursivamente os dados em dois "super baldes" para encontrar uma solução $\epsilon$-enviesada válida rapidamente.
   • Ele começa com uma fronteira de ponto médio e expande iterativamente o raio de busca até que uma divisão $\epsilon$-enviesada seja encontrada.
   • Teorema 4 prova que, se um agrupamento $\epsilon$-enviesado válido existir, o D&C o encontrará.
   • Complexidade: $O(n \log k)$ (quase linear), tornando-o altamente escalável.

2. Busca Local (LS):

   • Para encontrar o agrupamento $\epsilon$-enviesado ótimo (minimizando o desvio de tamanho), o LS usa a solução do D&C como um limite superior.
   • Ele define uma janela de busca ao redor das fronteiras do agrupamento inicial de tamanho igual, restringida pelo valor do objetivo da solução do D&C.
   • Ele verifica exaustivamente as combinações dentro desta janela para encontrar uma solução com um valor de objetivo menor.
   • Complexidade: $O(n \log n + (w_{dnc})^{k-1})$, onde $w_{dnc}$ é o valor do objetivo da solução do D&C. Embora teoricamente exponencial em $k$, os autores observam que é eficiente na prática, pois casos adversos com $w_{dnc}$ grande são raros.

3. Principais Contribuições

• Formulação do Problema: O artigo define formalmente o problema de Agrupamento Não Enviesado e o problema relaxado de Agrupamento $\epsilon$-Enviesado, destacando a lacuna na literatura em relação à equidade na etapa de preparação de dados.
• Garantias Teóricas:
  • Prova de que as fronteiras do agrupamento não enviesado ideal devem pertencer a um conjunto específico de candidatos.
  • Prova de que o algoritmo D&C é completo (ele encontra uma solução se uma existir).
• Suíte Algorítmica:
  • Um algoritmo de DP exato para agrupamento não enviesado de tamanho igual.
  • Um algoritmo de D&C escalável para encontrar soluções $\epsilon$-enviesadas válidas em tempo quase linear.
  • Um algoritmo de Busca Local (LS) que utiliza o D&C para encontrar soluções $\epsilon$-enviesadas ótimas de forma eficiente.
• Aplicabilidade Geral: Ao contrário da solução de DP para agrupamento não enviesado, os algoritmos D&C e LS são gerais e não restritos ao agrupamento de tamanho igual; eles podem atuar como etapas de pós-processamento para qualquer método de bucketização de caixa-preta.

4. Resultados Experimentais

Os autores avaliaram seus algoritmos em conjuntos de dados do mundo real (German Credit, COMPAS) e conjuntos de dados sintéticos.

• Impacto na Equidade: Experimentos demonstraram que o agrupamento padrão sem consciência de equidade introduz viés mensurável. Aplicar o agrupamento $\epsilon$-enviesado reduziu significativamente as métricas de injustiça de grupo (Impacto Disparate, Diferença de Paridade Estatística, Diferença de Oportunidade Igual) em modelos subsequentes (Regressão Logística e SVM).
• Preço da Equidade: Reduzir o viés pela metade resultou em melhorias substanciais nas métricas de equidade enquanto mantinha ou melhorava ligeiramente a precisão do modelo. O "preço da equidade" (desvio dos tamanhos iguais dos baldes) foi considerado negligenciável em muitos casos.
• Equidade Individual: O estudo observou que, embora a equidade de grupo tenha melhorado significamente, a equidade individual (medida pela consistência) permaneceu amplamente estável, sugerindo que o agrupamento não enviesado não prejudica a equidade ao nível individual.
• Escalabilidade: Os algoritmos D&C e LS demonstraram alta eficiência em grandes conjuntos de dados, enquanto a solução de DP de tempo quadrático foi limitada a configurações menores.
• Integração: Combinar o agrupamento $\epsilon$-enviesado com técnicas de FairML subsequentes (Exponentiated Gradient) mostrou que a preparação de dados pode complementar as intervenções ao nível do modelo, embora o ganho marginal fosse menor quando os dados já haviam sido pré-processados para equidade.

5. Significância e Alegações

O artigo posiciona o agrupamento não enviesado como um componente necessário, embora insuficiente, de um pipeline de análise de dados responsável.

• Papel Complementar: Os autores afirmam explicitamente que o agrupamento não enviesado não substitui as técnicas de FairML (como o treinamento de modelos justos), mas serve como uma etapa crítica de pré-processamento para evitar a propagação de viés antes que o treinamento do modelo comece.
• Relevância Prática: O trabalho argumenta que o viés introduzido durante a preparação dos dados é uma fonte tangível de injustiça subsequente. Ao abordar isso precocemente, os praticantes podem reduzir significativamente a carga sobre as intervenções de equidade posteriores.
• Alegações Modestas: Os autores são cuidadosos ao notar que, embora seus métodos reduzam o viesso e melhorem as métricas de equidade, eles não garantem a equidade em todas as tarefas subsequentes. A eficácia depende da distribuição específica dos dados e do limiar $\epsilon$ escolhido. O artigo enfatiza que alcançar resultados justos requer o acoplamento da preparação de dados consciente de equidade com o desenvolvimento de algoritmos justos.