Fairness of Classifiers in the Presence of Constraints between Features

1. Declaração do Problema

O artigo aborda uma lacuna crítica na definição e avaliação da justiça em classificadores de Aprendizado de Máquina: a presença de restrições lógicas entre características.

• Contexto: Definições padrão de justiça (por exemplo, Justiça através da Desatenção) frequentemente assumem que uma decisão é justa se não depender de características protegidas (por exemplo, gênero, raça).
• O Problema: Em cenários do mundo real, as características raramente são independentes. Restrições existem devido a:
  • Codificação: por exemplo, codificação one-hot onde exatamente uma característica booleana deve ser verdadeira.
  • Lógica do mundo real: por exemplo, "Se uma pessoa está de licença-maternidade, ela deve ser do sexo feminino e empregada."
• A Consequência: Ignorar essas restrições pode levar a falsos positivos (considerar um classificador justo como injusto) ou falsos negativos (considerar um classificador injusto como justo).
  • Exemplo: Um modelo pode parecer depender do gênero porque a saída do modelo muda quando o gênero é invertido, mas se a restrição implicar que inverter o gênero também força uma mudança em outra característica (como status de emprego), a decisão pode, na verdade, ser independente do gênero no espaço de características válido.
• Objetivo: Definir formalmente a justiça na presença de restrições ($C$) e analisar a complexidade computacional de verificar essas definições.

2. Metodologia e Conceitos Principais

Os autores utilizam Explicações Abdutivas (AXp) e Implicantes Primos (PI) dentro de um espaço de características restrito.

Definições Chave

• Espaço de Características ($F$): O produto cartesiano dos domínios das características.
• Restrições ($C$): Um conjunto de regras lógicas que restringem instâncias válidas. O espaço válido é $F[C]$.
• Características Protegidas ($P$) vs. Características Não Protegidas ($N$): $P$ contém atributos sensíveis (por exemplo, gênero); $N$ contém os demais.
• Explicação Abdutiva (AXp): Um subconjunto de características $S$ tal que fixar os valores de $S$ aos presentes na instância $x$ garante a saída do classificador $\kappa(x)$, considerando apenas instâncias em $F[C]$.
• Explicação de Implicante Primo (PI-explicação): Uma AXp que não é estritamente subsumida por outra AXp. Em espaços restritos, a subsumção é definida pela implicação lógica dentro de $F[C]$, e não apenas pela inclusão de conjuntos.
• PI-explicação Justa: Uma PI-explicação que não contém nenhuma característica protegida ($S \cap P = \emptyset$).

Definições Propostas de Justiça

O artigo propõe três definições distintas para a justiça de um classificador $\kappa$:

1. Justiça através da Desatenção Restrita (FTU):

   • Para todo $x, y \in F[C]$, se $x_N = y_N$ (características não protegidas são idênticas), então $\kappa(x) = \kappa(y)$.
   • Isso garante que a decisão depende apenas de características não protegidas dentro do espaço válido.

2. Justiça Existencial:

   • Para toda decisão $\kappa(x) = c$, existe pelo menos uma PI-explicação justa.
   • Significado: Há alguma razão válida para a decisão que não depende de características protegidas.

3. Justiça Universal:

   • Para toda decisão $\kappa(x) = c$, todas as PI-explicações são justas.
   • Significado: Toda razão mínima para a decisão evita características protegidas.

Análise Teórica

Os autores analisam as relações entre essas definições sob diferentes cenários de restrição:

• Restrições entre $P$ e $N$: Ignorá-las pode alterar drasticamente as avaliações de justiça. Uma decisão pode ser universalmente justa em $F[C]$, mas parecer injusta em $F$ sem restrições, ou vice-versa.
• Restrições apenas dentro de $P$: Se as restrições existirem apenas entre características protegidas, a existência de uma PI-explicação justa é preservada de espaços sem restrições para espaços restritos (Proposição 1).
• Restrições apenas dentro de $N$: A existência de uma PI-explicação justa é independente dessas restrições (Proposição 2). No entanto, restrições dentro de $N$ podem criar PI-explicações injustas que não existiam no espaço sem restrições (Exemplo 7).

Condições Especiais para Equivalência

O artigo identifica condições onde as definições complexas (Existencial/Universal) se simplificam para a FTU Restrita, mais fácil de verificar:

• Restrições Leves: Se nenhuma atribuição parcial de uma característica protegida subsumir estritamente a atribuição de todas as características não protegidas, então a FTU Restrita implica Justiça Existencial.
• Classificadores Desembaralhados: Um classificador é "desembaralhado" se o conjunto de características não protegidas $N$ for uma AXp fraca não estritamente subsumida por qualquer AXp injusta. Isso garante Justiça Existencial.

3. Contribuições Principais

1. Formalização da Justiça com Restrições: O artigo vai além da definição padrão de "desatenção", integrando restrições lógicas diretamente na definição de explicações (PI-explicações).
2. Demonstração do Impacto das Restrições: Através de múltiplos exemplos (por exemplo, licença-maternidade, agências de adoção), os autores provam que ignorar restrições leva a avaliações de justiça incorretas.
3. Hierarquia de Definições de Justiça: O artigo estabelece as relações lógicas entre FTU Restrita, Justiça Existencial e Justiça Universal.
   • Universal $\implies$ Existencial $\implies$ FTU Restrita.
   • As implicações reversas geralmente não se sustentam, a menos que condições específicas (como "restrições leves" ou "sem restrições entre P e N") sejam atendidas.
4. Análise de Complexidade: Os autores mapeiam a complexidade computacional de verificar essas noções de justiça dentro da Hierarquia Polinomial.

4. Resultados e Análise de Complexidade

O artigo fornece uma análise rigorosa de complexidade para testar essas definições de justiça:

Insight Chave de Complexidade:

• Testar FTU Restrita é computacionalmente viável (coNP-completo) e pode ser tratado por solucionadores SAT padrão.
• Testar Justiça Existencial/Universal é significativamente mais difícil ($\Pi^P_3$ ou $\Pi^P_4$), exigindo solucionadores de Fórmulas Booleanas Quantificadas (QBF).
• Implicação Prática: Os autores propõem usar verificações de "Restrições Leves" ou "Desembaralhados" (que são $\Pi^P_2$) como condições suficientes para garantir Justiça Existencial, permitindo o uso de solucionadores SAT mais simples em vez de solucionadores QBF.

5. Significado e Conclusão

• Fundamento Teórico: O artigo estabelece que a justiça não pode ser avaliada no vácuo; a estrutura lógica do espaço de características (restrições) altera fundamentalmente a definição de uma "razão" para uma decisão.
• Orientação Prática: Adverte os praticantes de que ferramentas padrão de justiça (que frequentemente ignoram restrições) podem produzir resultados enganosos.
• Compromisso: Existe um trade-off entre a rigorosidade da definição de justiça e a tratabilidade computacional.
  • Justiça Universal é a mais rigorosa, mas a mais difícil de verificar.
  • FTU Restrita é a mais fácil de verificar, mas pode perder casos onde uma decisão depende tecnicamente de características protegidas via restrições.
• Direções Futuras: Os autores sugerem estender essa estrutura lógica para lidar com correlações estatísticas e explorar a "escolha de características protegidas" usando grafos causais (Justiça através de Independência Causal - FTCI).

Em resumo, este artigo argumenta que a justiça é dependente do contexto das restrições de características. Ele fornece uma estrutura formal para definir justiça por meio de explicações de implicantes primos e oferece um roteiro para verificar essas definições, equilibrando rigor teórico com viabilidade computacional.