Generalized Priority-Aware Shapley Value

Aquí se presenta un resumen técnico detallado del artículo "Generalized Priority-Aware Shapley Value" (GPASV).

Enunciado del Problema

Los valores de Shapley y sus extensiones conscientes de la prioridad son herramientas estándar para atribuir valor a los contribuyentes en el aprendizaje automático (por ejemplo, puntos de datos, características o componentes del modelo). Sin embargo, los métodos existentes conscientes de la prioridad, como el Valor de Shapley Consciente de la Prioridad (PASV), dependen de supuestos restrictivos que a menudo fallan en las aplicaciones modernas de IA/ML:

1. Restricciones Binarias y Acíclicas: PASV requiere que las relaciones de prioridad por pares se codifiquen como un Grafo Dirigido Acíclico (DAG). Esto prohíbe los ciclos (por ejemplo, $A \succ B \succ C \succ A$) y trata la prioridad como una restricción rígida y binaria. Los datos del mundo real, como las preferencias humanas agregadas (ciclos de Condorcet) o las comparaciones multicriterio, exhiben frecuentemente estructuras cíclicas.
2. Pérdida de Magnitud: PASV descarta la fuerza de la evidencia de prioridad. En escenarios como conteos de victorias en torneos, log-odds de Bradley-Terry o calificaciones ELO, la magnitud de la preferencia importa, pero los métodos basados en DAG solo capturan la existencia de una precedencia.
3. Ataques de Copiadores: Los valores de Shapley estándar son vulnerables a "ataques de copiadores" donde un contribuyente que copia a otro recibe el mismo crédito. Aunque PASV aborda esto mediante prioridades rígidas, no puede manejar la naturaleza matizada, ponderada o cíclica de la precedencia en el mundo real.

Metodología: Valor de Shapley Consciente de la Prioridad Generalizado (GPASV)

Los autores proponen GPASV, un Valor de Orden Aleatorio (ROV) definido sobre grafos dirigidos ponderados arbitrarios que maneja simultáneamente estructuras cíclicas, prioridades por pares ponderadas y prioridades individuales "suaves".

1. Definición Central
A diferencia de PASV, que restringe las permutaciones a aquellas consistentes con un DAG, GPASV define una distribución de probabilidad $p(\lambda, \omega)$ sobre todo el conjunto de permutaciones $\Pi$.

• Prioridad por Pares ($\omega$): Representada por un grafo dirigido ponderado donde $\omega_{ij} \ge 0$ codifica la fuerza con la que el jugador $i$ debería preceder a $j$. Se permiten ciclos.
• Prioridad Suave ($\lambda$): Pesos individuales que representan confianza, costo o riesgo de cumplimiento.
• Penalización por Violación: Para una permutación $\pi$, el costo total de violación $V_\omega(\pi)$ es la suma de los pesos de todos los pares donde se viola la precedencia.
• Formulación de la Distribución: La distribución combina una penalización estilo Gibbs por violaciones con un mecanismo de prioridad suave por etapas:
  $$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]$$
  Aquí, $\beta$ es un parámetro de temperatura que controla la estrictud de la prioridad por pares. Cuando $\beta \to \infty$, el método recupera PASV en DAGs; cuando $\beta = 0$, se reduce a una distribución Plackett-Luce.

2. Caracterización Axiomática
El artículo establece GPASV mediante un conjunto de axiomas que generalizan los de PASV:

• GSCF (Factorización Generalizada de Elección de Estado): Asegura que la distribución siga una forma canónica por etapas compatible con el esquema de muestreo.
• GWP (Proporcionalidad Generalizada de Pesos): Los log-odds de elegir al jugador $i$ sobre $j$ en cualquier etapa dependen de sus pesos suaves $\lambda$ y sus costos de violación relativos.
• PVF (Factorización de Violación por Pares): Cuando los pesos suaves son uniformes, la distribución se reduce a la forma Gibbs que penaliza las violaciones totales.
  Los autores demuestran que GPASV es el único ROV que satisface estos axiomas.

3. Marco Computacional
Calcular GPASV es desafiante debido a la distribución no uniforme sobre las permutaciones. Los autores desarrollan:

• Muestreo: Una cadena Metropolis-Hastings (MH) de intercambio adyacente con una razón de aceptación local que cancela la mayoría de los términos globales, haciéndola eficiente.
• Inicialización: Una inicialización voraz por etapas (Algoritmo 2) que muestrea jugadores hacia atrás desde la posición $n$ para mitigar el problema de "arranque en frío" en grafos cíclicos donde no existe una extensión lineal válida.
• Aceleración:
  • Almacenamiento en Caché de Utilidad: Reutilización de evaluaciones $U(S)$ para subconjuntos repetidos.
  • SNIS (Muestreo por Importancia Auto-Normalizado): Reutilización de muestras de permutación a través de diferentes configuraciones de temperatura ($\beta$) o escalas de prioridad suave ($\lambda$) durante el "barrido de prioridad".
  • Estimación Asistida por Sustitutos: Uso de sustitutos basados en regresión (lineales o cuadráticos) para reducir la varianza, aunque los autores notan que esto incurre en mayores costos de memoria para GPASV en comparación con PASV debido a la incapacidad de anular los términos de interacción para las aristas del DAG.

Resultados Clave y Validación Empírica

1. Simulaciones

• Tiempo de Mezcla: La inicialización voraz acelera significativamente la mezcla de la cadena MH en comparación con la inicialización aleatoria, particularmente en grafos densos o cíclicos.
• Precisión: La estimación directa de Monte Carlo converge como se espera. Los métodos asistidos por sustitutos mejoran la precisión pero introducen una sobrecarga sustancial de tiempo de ejecución y memoria, especialmente para sustitutos cuadráticos, que no pueden explotar la dispersión del DAG.
• Barrido de Prioridad: Una herramienta de diagnóstico donde se varían las prioridades suaves ($\lambda$). Los autores encuentran que bajo GPASV, el impacto de las prioridades suaves es substantivamente mayor que bajo PASV. Debido a que GPASV "suaviza" las restricciones rígidas, las prioridades suaves individuales pueden remodelar la valoración de manera más efectiva, mientras que las restricciones rígidas del DAG de PASV limitan su influencia.

2. Aplicación: Valoración de Ensembles de LLM
El método se aplica para valorar 20 Modelos de Lenguaje Grande (LLM) utilizando:

• Utilidad: Rendimiento en MT-Bench (agregado y juzgado por un LLM).
• Prioridad por Pares: Un grafo cíclico y ponderado derivado de preferencias humanas de Chatbot Arena.
• Prioridad Suave: Una preferencia por modelos de código abierto sobre APIs propietarias de pago.

Hallazgos:

• Valoración No Única: La valoración no es un único número "correcto". Diferentes equilibrios entre preferencias por pares ($\beta$) y prioridades suaves ($\alpha$) producen clasificaciones sustancialmente diferentes.
• Dominio de la Prioridad Suave: En barridos conjuntos, la prioridad suave a nivel de nodo (preferencia por código abierto) tiende a dominar la prioridad del grafo a nivel de arista. Por ejemplo, aumentar la prioridad suave para modelos de código abierto puede elevarlos a los primeros puestos incluso cuando el grafo de preferencia por pares favorece a los modelos de pago.
• Hubs del Grafo: Cuando se priorizan solo las preferencias por pares ($\beta$), la valoración se concentra en "hubs" específicos del grafo de preferencia (por ejemplo, GPT-4), en lugar de distribuir el valor a través de una categoría de modelos.

Significado y Afirmaciones

El artículo afirma que GPASV es una extensión principista y expresiva de las variantes existentes de Shapley. Su significado principal radica en:

1. Manejo de la Complejidad del Mundo Real: Es el primer método que maneja simultáneamente prioridades por pares cíclicas y ponderadas y prioridades individuales suaves, abarcando a Shapley clásico, PSV, WSV y PASV como casos especiales.
2. Transparencia en las Compensaciones: Los autores argumentan que la valoración consciente de la prioridad "no es una operación de un solo botón". GPASV expone la compensación entre diferentes fuentes de información de prioridad (por ejemplo, grafos de preferencia humana vs. restricciones de implementación) como una entrada explícita y barrible.
3. Necesidad Diagnóstica: El diagnóstico de "barrido de prioridad" revela que las prioridades suaves tienen un impacto mucho mayor bajo GPASV de lo que se pensaba anteriormente bajo PASV, lo que sugiere que los metadatos relacionados con prioridades suaves (confianza, costo, riesgo) son mucho más consecuentes para la valoración de lo que se reconocía previamente.

El artículo concluye que, aunque GPASV introduce desafíos computacionales, su capacidad para modelar estructuras cíclicas y ponderadas lo hace esencial para aplicaciones como la evaluación de LLM donde se violan los supuestos estándar de DAG.