Explaining Rankings with Hidden Group Bonuses

Resumo Técnico: Explicando Classificações com Bônus de Grupo Ocultos

Formulação do Problema
O artigo aborda o problema de explicar classificações observadas de candidatos quando o mecanismo de pontuação subjacente envolve uma função de utilidade linear aumentada por bônus de grupo aditivos ocultos. Em muitos cenários do mundo real (por exemplo, admissão em universidades, contratações), as classificações são determinadas não apenas por atributos de pontuação observáveis (por exemplo, notas de testes), mas também por atributos sensíveis (por exemplo, gênero, status socioeconômico) que desencadeiam aumentos aditivos específicos de grupo para promover equidade ou diversidade. Esses atributos sensíveis e os valores exatos dos bônus são frequentemente não observados por auditores externos.

Os autores formalizam duas variantes deste problema de "explicação de classificação":

1. Classificação Linear com Bônus de Grupo Único (SGBLR): Dado um conjunto de dados e uma classificação-alvo, determinar se existe uma função de utilidade linear e um vetor de bônus com no máximo $k$ entradas não nulas (bônus arbitrários para itens individuais) que reproduza a classificação.
2. Classificação Linear com Bônus de $g$ Grupos ($g$-GBLR): Dado um conjunto de dados, uma classificação-alvo e um orçamento de $g$ grupos, determinar se existe uma função de utilidade linear e um conjunto de $g$ grupos disjuntos, cada um recebendo um bônus aditivo específico, que reproduza a classificação.

Metodologia
O artigo propõe uma abordagem dual combinando algoritmos geométricos e Programação Linear Inteira Mista (MILP).

1. Algoritmo Geométrico (ERMB):

   • Para o problema SGBLR, os autores utilizam o conceito de arranjos de hiperplanos. Eles definem "hiperplanos de comparação" no espaço de pesos $d$-dimensional onde duas tuplas têm pontuações iguais. Esses hiperplanos particionam o espaço de pesos em regiões, cada uma correspondendo a uma classificação linear única.
   • O algoritmo enumera essas regiões para encontrar todas as classificações lineares realizáveis. Para cada classificação realizável, ele calcula a Subsequência Comum Mais Longa (LCS) com a classificação-alvo. As tuplas que não fazem parte da LCS são identificadas como candidatas a receber o bônus aditivo.
   • Esta abordagem é estendida à variante $g$-GBLR ao aumentar o espaço de características com $g$ dimensões (uma por grupo) e empregar uma rotina de programação dinâmica de LCS orçada.
   • Complexidade: O algoritmo executa em tempo $O(n^{2d+1} \log n)$, que é polinomial para dimensões $d$ e grupos $g$ constantes, mas exponencial em $d$.

2. Formulações MILP:

   • Para abordar questões de escalabilidade inerentes à abordagem geométrica para conjuntos de dados maiores, os autores formulam o problema como um Programa Linear Inteiro Misto (MILP).
   • MILPBase: Uma formulação genérica que codifica restrições de classificação, capacidade de grupo e indicadores de pertencimento binário.
   • MILPRefined: Uma formulação aprimorada que incorpora restrições específicas de domínio para melhorar a eficiência do solucionador e a estabilidade numérica. Refinamentos chave incluem:
     • Ordenação estrita com uma pequena tolerância $\epsilon$ para evitar empates.
     • Bônus aditivos limitados para evitar dominância sobre características lineares.
     • Pesos de características não negativos (comuns em contextos de pontuação).
     • Poda de Skyline: Uma etapa de pré-processamento que identifica tuplas "dominadas" (aquelas com pontuações mais baixas em todas as características, mas mais altas na classificação) e força-as a receber um bônus, reduzindo significativamente o espaço de busca.

3. Resultados de Dureza:

   • Os autores provam que o SGBLR é NP-difícil através de uma redução do problema Max-1-in-2-SAT. Isso estabelece que a dependência exponencial na dimensão $d$ no algoritmo geométrico é inevitável (assumindo $P \neq NP$).

Principais Contribuições

• Estrutura Formal: O artigo inicia o estudo formal da aprendizagem de funções de utilidade linear com bônus de grupo aditivos ocultos para explicar classificações, distinguindo-se de trabalhos anteriores que assumem visibilidade total das características ou focam exclusivamente em restrições de equidade na seleção top-$k$.
• Soluções Algorítmicas:
  • Um algoritmo exato e construtivo (ERMB) baseado em arranjos de hiperplanos para dimensões constantes.
  • Uma estrutura escalável baseada em MILP (MILPRefined) que aproveita solucionadores modernos e heurísticas de domínio (poda de skyline) para lidar com dados do mundo real em grande escala.
• Análise de Complexidade: Estabelecimento da NP-dificuldade para o problema geral, esclarecendo os limites teóricos de soluções exatas.
• Validação Empírica: Experimentos extensivos em dados sintéticos e do mundo real (especificamente um conjunto de dados de 384.977 candidatos ao exame JEE).

Resultados Experimentais

• Escalabilidade: O algoritmo geométrico ERMB é limitado a instâncias pequenas (por exemplo, $n \le 5.000$ para dados 2D) devido à sua alta complexidade. Em contraste, as formulações MILP demonstram forte escalabilidade.
  • Para dados sintéticos, o MILPRefined lidou com sucesso com até 75.000 tuplas em 2D e até 50.000 tuplas em dimensões de até $d=17$ (para $g=1$).
  • No conjunto de dados real do JEE ($\approx 300.000$ tuplas), o MILPRefined resolveu com sucesso o problema $g$-GBLR para $g=1$ e $g=2$ dentro do tempo limite de 1800 segundos.
• Qualidade da Solução: Os métodos baseados em MILP recuperaram exatamente as estruturas de bônus ocultas e os pesos em configurações sintéticas onde a verdade fundamental era conhecida. Eles superaram significativamente as linhas de base (Regressão Ordinal, Regressão Logística e Busca Local), que exigiram muito mais tuplas para receber bônus para explicar as mesmas classificações.
• Sensibilidade: O tempo de execução dos solucionadores MILP mostrou-se sensível ao parâmetro de tamanho do grupo $k$ e à dimensionalidade $d$, com a eficácia da poda de skyline diminuindo à medida que $d$ aumenta.

Significado e Afirmações
Os autores posicionam este trabalho como uma contribuição para a ciência de dados confiável e responsável, especificamente nos domínios de auditoria algorítmica e explicabilidade.

• Auditoria: O método serve como uma ferramenta para verificar se uma classificação observada adere às restrições de equidade pretendidas. Se o método não puder encontrar uma função linear com os bônus de grupo necessários que explique a classificação, fornece evidências de que a classificação pode violar políticas de equidade.
• Interpretabilidade: Quando uma classificação pode ser explicada pelo modelo, os pesos aprendidos revelam a importância relativa dos atributos, enquanto os bônus inferidos quantificam a vantagem atribuída a grupos específicos.
• Novidade: O artigo afirma ser o primeiro a abordar a variante específica de explicação de classificação onde características sensíveis não são observadas, mas influenciam os resultados através de bônus de grupo aditivos, capturando um desafio sutil em sistemas de classificação justa que modelos lineares anteriores não abordaram.

O artigo conclui modestamente, observando que, embora sua abordagem seja eficaz para modelos lineares, estender esses métodos para funções de utilidade não lineares ou modelos de bônus multiplicativos permanece uma direção de pesquisa aberta. Eles também destacam a conexão com a dureza de aproximação, sugerindo que projetar algoritmos de aproximação eficientes para este problema pode ser teoricamente desafiador.