Towards a Fairer Non-negative Matrix Factorization

Este artigo propõe uma abordagem de fatoração de matriz não negativa (NMF) com uma formulação min-max para mitigar viés em tarefas de aprendizado de máquina, apresentando algoritmos de otimização e evidenciando, por meio de experimentos, que o aumento da equidade pode ocorrer às custas de um maior erro para alguns indivíduos, ressaltando a necessidade de adaptar a escolha do método ao contexto específico da aplicação.

O essencial

Imagine que você tem uma grande caixa de brinquedos misturados: alguns são de crianças pequenas, outros de adolescentes, e alguns são de adultos. O objetivo é criar um "resumo" ou um "mapa" que explique como todos esses brinquedos funcionam, usando apenas algumas categorias principais (como "brinquedos de montar", "brinquedos de correr", etc.).

No mundo da Inteligência Artificial, isso se chama Fatoração de Matriz Não Negativa (NMF). É uma ferramenta poderosa usada para encontrar padrões ocultos em dados, seja para entender temas em textos, diagnosticar doenças ou recomendar filmes.

O problema é que, quando fazemos esse "resumo" da maneira tradicional, a IA tende a focar apenas no que é mais comum. Se a maioria dos brinquedos forem de adultos, o resumo vai ser perfeito para adultos, mas vai fazer um "resumo" muito ruim para as crianças. As crianças ficam invisíveis ou mal representadas. Isso é injusto.

Este artigo, escrito por um grupo de pesquisadores, propõe uma maneira mais justa de fazer esse resumo. Vamos explicar como eles fazem isso usando analogias simples:

1. O Problema: A "Reunião de Vozes"

Imagine que você está em uma sala com 100 pessoas. 90 delas têm vozes muito fortes e 10 têm vozes muito fracas.

• O Método Antigo (NMF Padrão): O objetivo é fazer o som total da sala ser o mais claro possível. Como as 90 vozes fortes dominam, o "resumo" da conversa vai capturar perfeitamente o que os 90 estão dizendo. As 10 pessoas de voz fraca serão ignoradas ou distorcidas. Se você usar esse resumo para tomar decisões (como em medicina ou justiça), as pessoas de voz fraca podem sofrer consequências terríveis porque seus dados não foram bem entendidos.

2. A Solução: O "Mínimo-Máximo" (Fairer-NMF)

Os autores propõem uma nova regra para a reunião. Em vez de tentar agradar a todos ao mesmo tempo (o que favorece a maioria), a nova regra diz:

"Vamos tentar fazer o melhor possível para o grupo que está tendo o pior resultado."

É como se o líder da reunião dissesse: "Não importa se os 90 estão felizes; se as 10 pessoas de voz fraca não estiverem sendo ouvidas claramente, a reunião não foi um sucesso."

Isso é chamado de abordagem "min-max". O objetivo é minimizar o erro máximo. Se um grupo está sofrendo muito, o algoritmo ajusta o "mapa" para ajudar esse grupo, mesmo que isso signifique fazer um ajuste muito pequeno para os grupos que já estavam bem.

3. A Analogia da "Sopa de Pedras"

Pense em fazer uma sopa com pedras de tamanhos diferentes (pequenas, médias e grandes).

• NMF Padrão: Você tenta fazer a sopa ficar saborosa para a maioria das pedras. As pedras grandes (a maioria) ficam cozidas perfeitamente. As pedras pequenas (minorias) ficam cruas ou esmagadas porque o fogo foi ajustado para as grandes.
• Fairer-NMF: Você ajusta o fogo para garantir que a pedra mais difícil de cozinhar (a que está mais crua) fique no ponto certo. Isso pode fazer com que as pedras grandes fiquem um pouquinho mais cozidas do que o ideal, mas garante que ninguém fique comendo pedra crua.

4. Como eles fazem isso na prática?

Os pesquisadores criaram dois "receituários" (algoritmos) para seguir essa nova regra:

1. O Método Alternado (AM): É como um chef muito cuidadoso que prova a sopa, ajusta um ingrediente, prova de novo, ajusta outro. É muito preciso e justo, mas demora muito para cozinhar (é lento computacionalmente).
2. O Método de Atualização Multiplicativa (MU): É como um chef que usa uma régua e faz ajustes rápidos e multiplicativos. É um pouco menos preciso que o primeiro, mas é muito mais rápido. Para a maioria das situações do dia a dia, este é o melhor caminho.

5. O Resultado: Nem sempre é perfeito, mas é mais justo

Os testes mostraram que essa nova abordagem funciona muito bem em dados reais (como dados de doenças cardíacas ou textos de notícias).

• O lado bom: Grupos que antes eram ignorados agora têm seus dados representados com muito mais clareza. A "injustiça" diminui.
• O lado "chato": Às vezes, para ajudar o grupo que estava sofrendo, o erro de alguns indivíduos do grupo majoritário pode aumentar um pouquinho. É como dizer: "Para garantir que todos tenham uma cadeira confortável, talvez a cadeira do chefe fique um milímetro menos confortável do que antes."

Conclusão: O que isso significa para nós?

A mensagem principal do artigo é: Não existe uma fórmula mágica de "justiça perfeita". A justiça depende do contexto.

• Se você está criando um sistema para triagem médica, você não pode deixar nenhum grupo de pacientes ser mal diagnosticado, mesmo que isso custe um pouco de precisão para os outros.
• Os autores mostram que é possível criar ferramentas de Inteligência Artificial que olham para todos os grupos, não apenas para a maioria.

Eles nos lembram que a tecnologia deve ser uma ferramenta para incluir, não para excluir. Ao ajustar a "lente" da matemática, podemos garantir que as vozes mais fracas também sejam ouvidas no resumo final da nossa sociedade digital.

Resumo técnico

Resumo Técnico: Towards a Fairer Non-negative Matrix Factorization

1. O Problema

A Fatoração de Matriz Não-Negativa (NMF) é uma técnica amplamente utilizada em aprendizado de máquina para redução de dimensionalidade, modelagem de tópicos e extração de características. O objetivo padrão da NMF é minimizar o erro de reconstrução médio (geralmente a norma de Frobenius) entre a matriz de dados original $X$ e sua aproximação de baixo posto $WH$.

O problema central identificado pelos autores é que a minimização do erro médio tende a favorecer a maioria dos dados, ignorando subgrupos populacionais menores ou mais complexos. Em cenários desbalanceados (onde um grupo é muito maior que outro) ou quando grupos possuem complexidades intrínsecas diferentes (ex: um grupo é de posto mais alto que outro), a NMF padrão pode produzir:

• Viés de Reconstrução: Grupos minoritários ou complexos sofrem erros de reconstrução significativamente maiores.
• Injustiça Algorítmica: Se a NMF for usada como pré-processamento para tarefas downstream (como classificação médica ou justiça criminal), esses grupos desfavorecidos podem experimentar taxas de erro catastróficas, perpetuando desigualdades sociais.

A NMF padrão não leva em conta a complexidade do grupo nem o tamanho da amostra, focando apenas no erro global.

2. Metodologia Proposta: Fairer-NMF

Os autores propõem uma nova formulação chamada Fairer-NMF, baseada em uma estrutura de min-max (inspirada no "Fair PCA" de Samadi et al., 2018). O objetivo não é apenas minimizar o erro total, mas minimizar o máximo do erro de reconstrução relativo entre os diferentes grupos populacionais.

Definição Formal:
Dado um conjunto de dados dividido em $L$ grupos mutuamente exclusivos ($X_1, X_2, ..., X_L$), o problema é formulado como:

$$\min_{W, H} \max_{\ell \in \{1, \dots, L\}} \left( \frac{\|X_\ell - W_\ell H\| - E_\ell}{\|X_\ell\|} \right)$$

Onde:

• $W_\ell$ e $H$ são as matrizes de representação e dicionário, respectivamente.
• $\|X_\ell - W_\ell H\|$ é o erro de reconstrução do grupo $\ell$.
• $E_\ell$ é uma estimativa do erro de reconstrução "ótimo" para o grupo $\ell$ se ele fosse modelado isoladamente (usando uma implementação aleatória de NMF de posto $r$).
• O termo subtraído ($E_\ell$) e a normalização pelo tamanho do grupo ($\|X_\ell\|$) garantem que a métrica de "perda" (loss) reflita o quanto o grupo está sendo prejudicado por estar em um modelo conjunto em comparação com um modelo individual.

Algoritmos de Otimização:
Para resolver este problema não-convexo com restrições de não-negatividade, os autores derivam dois algoritmos:

1. Esquema de Minimização Alternada (AM - Alternating Minimization):

   • Fixa $W$ e otimiza $H$ resolvendo um problema de Programação Cônica de Segunda Ordem (SOCP) para minimizar o máximo dos erros.
   • Fixa $H$ e otimiza $W$ resolvendo um problema de Mínimos Quadrados Não-Negativos (NNLS).
   • Garante convergência monótona, mas é computacionalmente caro devido à necessidade de solvers de SOCP.

2. Esquema de Atualização Multiplicativa (MU - Multiplicative Updates):

   • Adapta o algoritmo clássico de Lee & Seung para o contexto min-max.
   • Introduz um vetor de pesos $c$ que identifica iterativamente o grupo com a maior perda atual.
   • Atualiza as matrizes $W$ e $H$ usando regras multiplicativas ponderadas por esses pesos.
   • É significativamente mais rápido que o AM, embora possa apresentar maior variância na convergência.

3. Principais Contribuições

1. Formulação de Justiça para NMF: Apresentam a primeira formulação explícita de justiça baseada em min-max para NMF, adaptando conceitos de Fair PCA para o domínio não-negativo.
2. Derivação de Algoritmos: Desenvolvem dois métodos práticos (AM e MU) para resolver a formulação proposta, lidando com as complexidades das restrições de não-negatividade.
3. Análise de Compensação (Trade-off): Demonstram empiricamente que a "justiça" nem sempre implica em menor erro absoluto para todos. Em alguns casos, a aplicação do método justo pode aumentar o erro para a maioria (ou grupos de menor complexidade) para reduzir drasticamente o erro dos grupos minoritários.
4. Validação Empírica: Fornecem uma suíte abrangente de experimentos com dados sintéticos e reais para validar a eficácia e as limitações do método.

4. Resultados Experimentais

Os autores testaram o Fairer-NMF em quatro cenários:

• Dados Sintéticos (Grupos de Rank Diferente): Em dados onde um grupo tem rank 6 e outro rank 3, a NMF padrão falha em reconstruir o grupo de rank 6 com precisão. O Fairer-NMF equilibra os erros, embora isso possa aumentar ligeiramente o erro do grupo de rank 3 em ranks baixos.
• Dados Sintéticos (Subespaços Sobrepostos): Quando grupos compartilham subespaços, a NMF padrão favorece os grupos que compartilham estrutura. O Fairer-NMF consegue tratar os grupos de forma mais equitativa.
• Dataset de Doença Cardíaca (Heart Disease): Ao separar por sexo (masculino/feminino), a NMF padrão favoreceu inadvertidamente o grupo feminino (menor erro). O Fairer-NMF reduziu a disparidade de perda entre os sexos, embora tenha aumentado o erro absoluto para o grupo que anteriormente tinha melhor desempenho.
• Dataset 20Newsgroups: Em dados de texto divididos por tópicos, a NMF padrão gerou erros desiguais (o grupo "Sale" teve o pior desempenho no modelo conjunto). O Fairer-NMF alinhou os erros de reconstrução de todos os grupos aos níveis observados quando treinados individualmente, eliminando a penalidade desproporcional.

Comparação de Algoritmos:

• O método AM é mais consistente e estável, mas extremamente lento (pode levar horas para grandes conjuntos de dados).
• O método MU é muito mais rápido (segundos), mas pode oscilar mais. Para a maioria das aplicações práticas, o MU é preferível devido à eficiência computacional.

5. Significância e Conclusão

O trabalho destaca que não existe uma definição única de justiça e que métodos "mais justos" devem ser escolhidos com base no contexto da aplicação.

• Transparência: O Fairer-NMF oferece uma ferramenta para identificar e mitigar viés em tarefas de modelagem de tópicos e extração de características.
• Custo da Justiça: Os autores enfatizam que a justiça pode ter um custo: melhorar a representação de um grupo minoritário pode degradar ligeiramente a precisão para a maioria. Em aplicações críticas (como medicina ou justiça), essa compensação deve ser analisada cuidadosamente.
• Futuro: O artigo sugere que a identificação automática dos subgrupos populacionais (quando não são conhecidos a priori) é um passo futuro necessário, possivelmente usando clustering ou análise de erro de reconstrução.

Em suma, o paper fornece uma base teórica e prática sólida para tornar a NMF mais equitativa, reconhecendo que a equidade é um objetivo contínuo e dependente do contexto, e não uma solução rígida.