Resumo Técnico: Resumos de Recurso Ótimos via Aprendizado de Árvore de Decisão Bi-Objetivo

Declaração do Problema

Sistemas de tomada de decisão automatizada em domínios críticos (por exemplo, crédito, contratação, saúde) frequentemente dependem de modelos opacos. Embora o Recurso Acionável forneça a indivíduos ações específicas para alterar resultados desfavoráveis, agregar essas ações locais para auditoria global e detecção de viés é custoso e frequentemente inconsistente. Métodos existentes para Resumos de Recurso — que particionam uma população em subgrupos e atribuem uma ação compartilhada a cada um — lutam para equilibrar múltiplos objetivos:

1. Eficácia do Recurso (Perda): A porção da população para quem a ação atribuída falha em inverter a saída do classificador.
2. Custo do Recurso: O esforço estimado necessário para executar a ação.
3. Restrições de Interpretabilidade: Número de subgrupos, comprimento da descrição do subgrupo e esparsidade da ação.

Abordagens atuais tipicamente escalarizam esses objetivos usando coeficientes arbitrários ou impõem limites, falhando em fornecer garantias de otimalidade global. Elas frequentemente produzem uma única solução, impedindo que as partes interessadas explorem o compromisso fundamental entre custo e eficácia. Além disso, muitos métodos existentes (por exemplo, CET, AReS) sofrem de tempos de execução computacionais elevados e não garantem encontrar o ótimo global.

Metodologia: SOGAR

Os autores introduzem Resumos de Recurso Acionável Ótimo e Global (SOGAR), um framework que formula o aprendizado de resumo de recurso como um problema de aprendizado de árvore de decisão ótima bi-objetivo.

Formulação Central

• Objetivo: Minimizar simultaneamente o Custo do Recurso ($C$) e a Perda do Recurso ($L$).
• Estrutura: Um resumo de recurso é representado como uma árvore de decisão rasa e paralela aos eixos. Nós internos realizam testes em características para particionar a população afetada em subgrupos disjuntos (folhas). Cada folha recebe uma única ação esparsa.
• Otimalidade: Em vez de escalarizar objetivos, o SOGAR computa a frente de Pareto completa de soluções não dominadas. Uma solução $\tau$ domina $\tau'$ se for melhor em pelo menos um objetivo e não pior no outro. Isso permite que os usuários selecionem o compromisso ideal post-hoc sem retreinamento.

Implementação Técnica

O método aproveita o framework de programação dinâmica STreeD, que garante otimalidade global para tarefas de otimização separáveis.

1. Separabilidade: Os autores provam que encontrar árvores ótimas de resumo de recurso satisfaz as condições necessárias e suficientes para separabilidade (funções de custo/transição markovianas e operadores de combinação que preservam a ordem), permitindo programação dinâmica exata.
2. Conjunto de Ações e Custo: As ações são definidas como operações de edição única ou múltipla (por exemplo, inverter valores binários, alterar categorias, deslocar bins numéricos). A função de custo utiliza o Deslocamento Percentual Máximo (MPS) para garantir invariância de escala e estimativa realista de esforço.
3. Melhorias de Eficiência:
   • Cache: Pré-computação de custo e perda para cada par ação-instância para permitir consultas $O(1)$ durante a busca na árvore.
   • Paralelização: Implementação de aceleração multithread em CPU e GPU para agregar custos e perdas em nós folha, reduzindo significativamente o tempo de execução.
   • Restrições: O framework impõe profundidade máxima da árvore, contagem máxima de folhas e esparsidade de ação para garantir interpretabilidade.

Contribuições Principais

1. Formulação Bi-Objetivo: O SOGAR é o primeiro método a definir o aprendizado de resumo de recurso como um problema de árvore de decisão ótima bi-objetivo, otimizando conjuntamente eficácia e custo sob restrições estruturais.
2. Otimalidade Global e Frente de Pareto: Ao enquadrar o problema dentro do framework STreeD, o SOGAR computa a frente de Pareto exata e completa de soluções não dominadas, evitando escalarização arbitrária e fornecendo garantias de otimalidade global.
3. Escalabilidade: A introdução de paralelização CPU/GPU e cache eficiente permite que o método resolva problemas de aprendizado de árvore NP-difíceis até a otimalidade global dentro de orçamentos de tempo razoáveis, mesmo para grandes conjuntos de dados.
4. Capacidade de Auditoria de Viés: A diversidade da frente de Pareto permite a detecção de viés em diferentes pontos de operação, revelando disparidades que métodos de solução única podem ignorar.

Resultados Experimentais

Os autores avaliaram o SOGAR em quatro conjuntos de dados tabulares (Attrition de Funcionários, Crédito Alemão, Marketing Bancário, Renda Adulta) usando três classificadores (LightGBM, XGBoost, DNN) contra cinco baselines (CET, AReS, GLOBE-CE, GLANCE, T-CREx).

• Desempenho: O SOGAR superou consistentemente todas as baselines na métrica de invalidade (soma de custo e perda) em todos os conjuntos de dados e classificadores. Alcançou o menor custo na maioria dos conjuntos de dados e valores de perda competitivos.
• Eficiência: Embora o SOGAR tenha custos computacionais mais altos que métodos heurísticos como GLOBE-CE, ele produz toda a frente de Pareto em uma única execução. Em contraste, baselines como CET e AReS frequentemente excederam o limite de tempo de 1 hora ou falharam em encontrar soluções em conjuntos de dados maiores.
• Generalização: Experimentos mostraram overfitting mínimo, com métricas de teste correspondendo estreitamente à frente de Pareto de treinamento.
• Estudos de Ablação:
  • Profundidade: Profundidade 3 ofereceu o melhor equilíbrio entre qualidade e tempo de execução; Profundidade 4 produziu ganhos marginais a um custo computacional proibitivo.
  • Esparsidade: Reduzir a esparsidade da ação ($k=2$) reduziu significativamente o tempo de execução, mas aumentou a perda, particularmente em conjuntos de dados complexos.
  • Limites de Tempo: Mesmo com limites de tempo rigorosos (por exemplo, 10–60 segundos), o SOGAR recuperou soluções que superaram as baselines, demonstrando sua capacidade "anytime" (disponível a qualquer momento).

Estudo de Caso de Auditoria de Viés

No conjunto de dados Renda Adulta, o SOGAR foi usado para auditar um classificador LightGBM quanto a viés de gênero. A análise da frente de Pareto revelou que femininos enfrentaram consistentemente maior invalidade do que masculinos em 96,4% das soluções. A disparidade foi impulsionada principalmente por maior perda de recurso para femininos em regiões de baixo custo e maior custo em regiões de alto custo. Essa descoberta destaca que métodos de solução única (que frequentemente selecionam pontos de baixa perda e alto custo) podem subestimar a verdadeira extensão do viés presente em todo o espectro de compromissos.

Significado e Alegações

O artigo afirma que o SOGAR representa um avanço significativo no campo do recurso algorítmico e da interpretabilidade ao:

• Fornecer o primeiro método a garantir otimalidade global para resumos de recurso.
• Eliminar a necessidade de ajuste arbitrário de hiperparâmetros (coeficientes de escalarização) ao expor a curva completa de compromissos.
• Permitir auditoria global robusta de classificadores, permitindo que as partes interessadas identifiquem e quantifiquem vieses que persistem através de diferentes compromissos custo-eficácia.
• Demonstrar que a otimização exata, quando combinada com aceleração de hardware moderno e cache, é uma alternativa viável a abordagens gananciosas ou estocásticas para gerar resumos de recurso acionáveis e interpretáveis.

Os autores reconhecem limitações, observando que o SOGAR incorre em custos computacionais mais altos do que métodos heurísticos e pode ter dificuldades com conjuntos de dados extremamente de alta dimensão sem seleção adicional de características. Eles enfatizam que, embora o SOGAR auxilie na auditoria, ele deve fazer parte de um conjunto de ferramentas de justiça mais amplo, em vez de um critério autônomo.