Generalized Priority-Aware Shapley Value

Declaração do Problema

Valores de Shapley e suas extensões conscientes de prioridade são ferramentas padrão para atribuir valor a contribuidores em aprendizado de máquina (por exemplo, pontos de dados, características ou componentes de modelos). No entanto, os métodos existentes conscientes de prioridade, como o Valor de Shapley Consciente de Prioridade (PASV), dependem de suposições restritivas que frequentemente falham em aplicações modernas de IA/ML:

1. Restrições Binárias e Acíclicas: O PASV exige que relações de prioridade pareadas sejam codificadas como um Grafo Direcionado Acíclico (DAG). Isso proíbe ciclos (por exemplo, $A \succ B \succ C \succ A$) e trata a prioridade como uma restrição rígida e binária. Dados do mundo real, como preferências humanas agregadas (ciclos de Condorcet) ou comparações multicritério, frequentemente exibem estruturas cíclicas.
2. Perda de Magnitude: O PASV descarta a força da evidência de prioridade. Em cenários como contagens de vitórias em torneios, log-odds de Bradley-Terry ou classificações ELO, a magnitude da preferência importa, mas métodos baseados em DAG capturam apenas a existência de uma precedência.
3. Ataques de Copiador: Os valores de Shapley padrão são vulneráveis a "ataques de copiador", onde um contribuidor que copia outro recebe crédito igual. Embora o PASV aborde isso por meio de prioridades rígidas, ele não consegue lidar com a natureza matizada, ponderada ou cíclica da precedência do mundo real.

Metodologia: Valor de Shapley Consciente de Prioridade Generalizado (GPASV)

Os autores propõem o GPASV, um Valor de Ordem Aleatória (ROV) definido em grafos direcionados ponderados arbitrários que lida simultaneamente com estruturas cíclicas, prioridades pareadas ponderadas e prioridades individuais "suaves".

1. Definição Central
Diferentemente do PASV, que restringe permutações àquelas consistentes com um DAG, o GPASV define uma distribuição de probabilidade $p(\lambda, \omega)$ sobre todo o conjunto de permutações $\Pi$.

• Prioridade Pareada ($\omega$): Representada por um grafo direcionado ponderado onde $\omega_{ij} \ge 0$ codifica a força com que o jogador $i$ deve preceder $j$. Ciclos são permitidos.
• Prioridade Suave ($\lambda$): Pesos individuais representando confiança, custo ou risco de conformidade.
• Penalidade de Violação: Para uma permutação $\pi$, o custo total de violação $V_\omega(\pi)$ é a soma dos pesos de todos os pares onde a precedência é violada.
• Formulação da Distribuição: A distribuição combina uma penalidade estilo Gibbs para violações com um mecanismo de prioridade suave etapa por etapa:
  $$p(\lambda, \omega)(\pi) \propto \prod_{t=1}^n \left[ \frac{\lambda_{\pi_t} \exp\{-\beta \cdot V_\omega(\pi_t; S_t)\}}{\sum_{k \in S_t} \lambda_k \exp\{-\beta \cdot V_\omega(k; S_t)\}} \cdot \sum_{k \in S_t} \exp\{-\beta \cdot V_\omega(k; S_t)\} \right]$$
  Aqui, $\beta$ é um parâmetro de temperatura que controla a rigidez da prioridade pareada. À medida que $\beta \to \infty$, o método recupera o PASV em DAGs; quando $\beta = 0$, reduz-se a uma distribuição Plackett-Luce.

2. Caracterização Axiomática
O artigo estabelece o GPASV por meio de um conjunto de axiomas que generalizam os do PASV:

• GSCF (Fatorização Generalizada de Escolha de Estado): Garante que a distribuição siga uma forma canônica etapa por etapa compatível com o esquema de amostragem.
• GWP (Proporcionalidade Generalizada de Pesos): Os log-odds de escolher o jogador $i$ sobre $j$ em qualquer estágio dependem de seus pesos suaves $\lambda$ e de seus custos relativos de violação.
• PVF (Fatorização de Violação Pareada): Quando os pesos suaves são uniformes, a distribuição reduz-se à forma Gibbs penalizando violações totais.
  Os autores provam que o GPASV é o único ROV que satisfaz esses axiomas.

3. Framework Computacional
Calcular o GPASV é desafiador devido à distribuição não uniforme sobre permutações. Os autores desenvolvem:

• Amostragem: Uma cadeia Metropolis-Hastings (MH) de troca adjacente com uma taxa de aceitação local que cancela a maioria dos termos globais, tornando-a eficiente.
• Inicialização: Uma inicialização gananciosa etapa por etapa (Algoritmo 2) que amostra jogadores de trás para frente, da posição $n$, para mitigar o problema de "início frio" em grafos cíclicos onde nenhuma extensão linear válida existe.
• Aceleração:
  • Cache de Utilidade: Reutilização de avaliações $U(S)$ para subconjuntos repetidos.
  • SNIS (Amostragem por Importância Auto-Normalizada): Reutilização de amostras de permutação entre diferentes configurações de temperatura ($\beta$) ou escalas de prioridade suave ($\lambda$) durante a "varredura de prioridade".
  • Estimativa Assistida por Surrogato: Uso de surrogatos baseados em regressão (lineares ou quadráticos) para reduzir a variância, embora os autores observem que isso incorre em custos de memória mais altos para o GPASV em comparação com o PASV devido à incapacidade de zerar termos de interação para arestas de DAG.

Resultados Principais e Validação Empírica

1. Simulações

• Tempo de Mistura: A inicialização gananciosa acelera significativamente a mistura da cadeia MH em comparação com a inicialização aleatória, particularmente em grafos densos ou cíclicos.
• Precisão: A estimativa direta de Monte Carlo converge conforme o esperado. Métodos assistidos por surrogato melhoram a precisão, mas introduzem sobrecarga substancial de tempo de execução e memória, especialmente para surrogatos quadráticos, que não podem explorar a esparsidade do DAG.
• Varredura de Prioridade: Uma ferramenta de diagnóstico onde as prioridades suaves ($\lambda$) são variadas. Os autores encontram que, sob o GPASV, o impacto das prioridades suaves é substancialmente maior do que sob o PASV. Como o GPASV "suaviza" restrições rígidas, prioridades suaves individuais podem remodelar a valoração de forma mais eficaz, enquanto as restrições rígidas de DAG do PASV limitam sua influência.

2. Aplicação: Valoração de Ensemble de LLM
O método é aplicado para valorar 20 Modelos de Linguagem Grandes (LLMs) usando:

• Utilidade: Desempenho no MT-Bench (agregado e julgado por um LLM).
• Prioridade Pareada: Um grafo cíclico e ponderado derivado de preferências humanas do Chatbot Arena.
• Prioridade Suave: Uma preferência por modelos de código aberto em relação a APIs proprietárias pagas.

Descobertas:

• Valoração Não Única: A valoração não é um único número "correto". Diferentes equilíbrios entre preferências pareadas ($\beta$) e prioridades suaves ($\alpha$) produzem classificações substancialmente diferentes.
• Domínio da Prioridade Suave: Em varreduras conjuntas, a prioridade suave no nível do nó (preferência por código aberto) tende a dominar a prioridade do grafo no nível da aresta. Por exemplo, aumentar a prioridade suave para modelos de código aberto pode elevá-los aos primeiros lugares, mesmo quando o grafo de preferência pareada favorece modelos pagos.
• Hubs do Grafo: Ao priorizar apenas preferências pareadas ($\beta$), a valoração concentra-se em "hubs" específicos no grafo de preferência (por exemplo, GPT-4), em vez de distribuir o valor por uma categoria de modelos.

Significado e Alegações

O artigo alega que o GPASV é uma extensão principial e expressiva das variantes de Shapley existentes. Seu significado principal reside em:

1. Lidar com Complexidade do Mundo Real: É o primeiro método a lidar simultaneamente com prioridades pareadas cíclicas e ponderadas e prioridades individuais suaves, cobrindo Shapley clássico, PSV, WSV e PASV como casos especiais.
2. Transparência em Trade-offs: Os autores argumentam que a valoração consciente de prioridade "não é uma operação de um botão". O GPASV expõe o trade-off entre diferentes fontes de informações de prioridade (por exemplo, grafos de preferência humana vs. restrições de implantação) como uma entrada explícita e varredível.
3. Necessidade Diagnóstica: O diagnóstico de "varredura de prioridade" revela que as prioridades suaves têm um impacto muito maior sob o GPASV do que se pensava anteriormente sob o PASV, sugerindo que metadados relacionados a prioridades suaves (confiança, custo, risco) são muito mais consequentes para a valoração do que anteriormente reconhecido.

O artigo conclui que, embora o GPASV introduza desafios computacionais, sua capacidade de modelar estruturas cíclicas e ponderadas o torna essencial para aplicações como avaliação de LLM, onde as suposições padrão de DAG são violadas.