Local Shapley: Model-Induced Locality and Optimal Reuse in Data Valuation

Each language version is independently generated for its own context, not a direct translation.

Imagina que tienes un equipo de cocina gigante (el conjunto de datos) y quieres hacer un pastel increíble (el modelo de inteligencia artificial). Ahora, imagina que un cliente te pregunta: "¿Quién de todos los cocineros merecía el mayor pago por hacer este pastel tan delicioso?".

Esta es la pregunta que intenta responder el Valor de Shapley en el mundo de los datos. Es una forma matemática justa de decir: "¿Qué tan importante fue cada dato individual para el resultado final?".

El problema es que, si tienes 100 cocineros, calcular exactamente cuánto contribuyó cada uno es una pesadilla. Tendrías que probar millones de combinaciones de equipos (¿qué pasa si solo usamos a los 5 primeros? ¿Y si quitamos al tercero?). Hacer esto para un equipo grande es computacionalmente imposible; tomaría años.

Aquí es donde entra el nuevo método llamado Local Shapley (y sus algoritmos LSMR y LSMR-A) presentado en este artículo.

La Gran Idea: "No necesitas a todos para cocinar este pastel"

Los autores se dieron cuenta de algo obvio pero que nadie había aprovechado: No todos los cocineros influyen en cada pastel.

Si estás haciendo un pastel de chocolate, los datos sobre "cómo hornear pan" no importan mucho.
Si estás clasificando una foto de un gato, los datos de "cómo se ve un perro" no cambian tu decisión.

En el lenguaje de la inteligencia artificial, esto se llama localidad inducida por el modelo. Dependiendo de la arquitectura del modelo (como un árbol de decisión, una red neuronal o un vecino cercano), cada predicción solo depende de un pequeño grupo de datos (llamado "conjunto de soporte").

La Analogía del "Mapa de la Cocina"

Imagina que el modelo es un mapa de la cocina:

El Viejo Método (Global): Para saber quién merece el pago, el viejo método revisa todas las combinaciones posibles de cocineros en toda la cocina, incluso a los que están en el almacén de limpieza y nunca tocan el horno. Es un desperdicio de tiempo.
El Nuevo Método (Local Shapley): El nuevo método mira el mapa y dice: "Para este pastel específico, solo necesitamos a los 5 cocineros que están junto al horno. Ignorémos al resto".

¿Cómo lo hacen tan rápido? (LSMR y LSMR-A)

Aquí es donde la magia ocurre. Incluso si te quedas solo con los 5 cocineros relevantes, calcular sus contribuciones sigue siendo complicado si tienes miles de pasteles (pruebas) diferentes.

Los autores proponen dos trucos inteligentes:

1. LSMR: El "Jefe de Cocina" que evita el doble trabajo

Imagina que tienes 1000 pasteles diferentes. Muchos de ellos usan al mismo grupo de 5 cocineros.

El error común: Calcular el pago para el pastel #1, luego borrar todo y volver a calcularlo para el pastel #2, aunque usaron a los mismos 5 cocineros.
La solución LSMR: El algoritmo actúa como un jefe de cocina muy organizado. Dice: "¡Espera! Ya calculamos la contribución de este grupo de 5 cocineros para el pastel #1. ¡No lo volvamos a hacer! Simplemente copiamos ese resultado y lo aplicamos al pastel #2".
Resultado: En lugar de entrenar el modelo millones de veces, lo entrenan solo una vez por cada grupo único de cocineros. Esto reduce el trabajo de millones de operaciones a unas pocas cientos.

2. LSMR-A: El "Muestreo Inteligente"

¿Qué pasa si el grupo de cocineros es tan grande que incluso contar sus combinaciones es difícil?

El error común: Lanzar dados al azar para elegir grupos de cocineros, y a veces elegir grupos que no tienen sentido o repetir los mismos grupos una y otra vez.
La solución LSMR-A: Es como un muestreo inteligente. Si el algoritmo "lanza los dados" y elige un grupo de cocineros que ya usó para otro pastel, en lugar de volver a cocinar, dice: "¡Genial! Ya tengo los resultados de este grupo. Los uso para todos los pasteles que necesitan a estos cocineros".
Beneficio: Ahorra tiempo y, además, al compartir los resultados, el cálculo se vuelve más estable y preciso (menos "ruido" o errores aleatorios).

¿Por qué es importante esto?

Ahorro de tiempo y dinero: En lugar de tardar días o semanas en valorar los datos, ahora se puede hacer en minutos u horas.
Justicia real: Al enfocarse solo en los datos que realmente importan para esa predicción específica, la valoración es más precisa y justa.
Escalabilidad: Permite valorar datos en sistemas gigantes (como redes sociales o bancos) donde antes era imposible hacerlo.

En resumen

Este papel nos dice que para saber cuánto vale un dato, no necesitamos mirar todo el universo de datos. Solo necesitamos mirar quién está en la mesa de trabajo para esa tarea específica.

Al usar LSMR, organizamos la cocina para que nadie haga el mismo trabajo dos veces. Y con LSMR-A, usamos un muestreo inteligente que aprovecha cada resultado que ya tenemos. Es como pasar de intentar resolver un rompecabezas de un millón de piezas mirando una por una, a usar un mapa que te dice exactamente dónde encajan las piezas y compartir las piezas ya ensambladas con tus vecinos.

¡Es una forma más inteligente, rápida y justa de entender el valor de los datos!

Each language version is independently generated for its own context, not a direct translation.

Resumen Técnico: Local Shapley

1. El Problema

La valoración de datos (data valuation) busca cuantificar la contribución de cada punto de entrenamiento al rendimiento de un modelo. El valor de Shapley es el estándar de oro para esta tarea debido a sus garantías de equidad, pero su cálculo exacto es #P-difícil. La complejidad surge de la necesidad de evaluar $2^{|D|}$ coaliciones (subconjuntos) de datos, lo que requiere reentrenar el modelo un número exponencial de veces.

Las aceleraciones existentes (como el muestreo de Monte Carlo o métodos basados en gradientes) siguen operando sobre el espacio global de coaliciones, asumiendo implícitamente que cualquier punto de entrenamiento podría influir en cualquier punto de prueba. Esta suposición es pesimista y ignora una propiedad estructural clave de los predictores modernos: la localidad inducida por el modelo. Para un punto de prueba dado, solo un subconjunto pequeño de datos de entrenamiento participa realmente en la ruta computacional que determina la predicción (por ejemplo, los vecinos más cercanos en KNN, las hojas en árboles de decisión o el campo receptivo en GNNs).

El problema central es cómo aprovechar esta localidad estructural para reducir drásticamente el costo computacional sin sacrificar la fidelidad de la valoración, y cómo eliminar la redundancia masiva en los cálculos de reentrenamiento.

2. Metodología

Los autores proponen un marco teórico y algorítmico basado en la localidad inducida por el modelo y la reutilización óptima de subconjuntos.

Definición de Conjuntos de Soporte ( $N(t)$ ):
Se formaliza la localidad definiendo un conjunto de soporte $N(t) \subseteq D$ para cada punto de prueba $t$ . Este conjunto contiene solo las instancias de entrenamiento que influyen en la predicción de $t$ a través de la arquitectura del modelo (ej. soporte en SVM, vecinos en KNN).
- Se define una utilidad proyectada $v^N_t(S) = v_t(S \cap N(t))$ .
- Se demuestra que si la localidad es exacta, el valor de Shapley local coincide con el global. Si es aproximada, el error está acotado por la influencia agregada de los puntos fuera del soporte.
Complejidad Intrínseca y Límite Inferior:
Se prueba que la complejidad real no depende del número total de coaliciones, sino del número de subconjuntos distintos que influyen en al menos una valoración. Esto establece un límite inferior de teoría de la información sobre el número mínimo de reentrenamientos necesarios.
Algoritmo Exacto: LSMR (Local Shapley via Model Reuse):
Para calcular el valor exacto, proponen LSMR, un algoritmo centrado en subconjuntos que elimina dos tipos de redundancia:
1. Redundancia Intra-soporte: En lugar de calcular contribuciones marginales por jugador, se evalúa cada subconjunto único una sola vez y se distribuye su utilidad a todos los jugadores del soporte mediante una fórmula de ponderación cerrada.
2. Redundancia Inter-soporte: Utilizan un grafo bipartito de mapeo de soportes y una regla de programación basada en pivotes. Cada subconjunto único tiene un "evaluador canónico" (el primer punto de prueba en un orden global que lo contiene). Solo ese punto entrena el modelo; los demás reutilizan el resultado.
- Resultado: LSMR entrena cada subconjunto distinto exactamente una vez, alcanzando el límite inferior teórico.
Estimador Aproximado: LSMR-A:
Para soportes grandes donde la enumeración exacta sigue siendo costosa, proponen LSMR-A, un estimador de Monte Carlo consciente de la reutilización.
- Muestrea permutaciones pero aplica la regla de pivoteo para asegurar que cada subconjunto muestreado se entrena como máximo una vez a través de todos los puntos de prueba.
- Garantías: El estimador es insesgado, tiene concentración exponencial (el error decae exponencialmente con el número de muestras) y reduce la varianza al amortizar la aleatoriedad en regiones de soporte superpuestas.

3. Contribuciones Clave

Abstracción de Localidad Estructural: Formalizan la localidad no como una heurística geométrica (solo KNN), sino como una propiedad de la ruta computacional del modelo, aplicable a KNN, SVM, Árboles de Decisión y GNNs.
Límite Inferior de Complejidad: Establecen que el costo mínimo de reentrenamiento está gobernado por el número de subconjuntos distintos inducidos por los soportes, no por el tamaño total del conjunto de datos.
Algoritmos Óptimos (LSMR y LSMR-A): Desarrollan algoritmos que alcanzan este límite inferior (LSMR) o desacoplan la complejidad de muestreo de la de reentrenamiento (LSMR-A), eliminando redundancias tanto intra como inter-soporte.
Reducción de Varianza: Demuestran teóricamente y empíricamente que la reutilización estructural reduce la varianza del estimador, especialmente bajo cambios de distribución (distribution shift), al evitar muestrear puntos irrelevantes.

4. Resultados Experimentales

Los autores evaluaron el marco en cuatro familias de modelos (KNN ponderado, SVM con kernel RBF, Árboles de Decisión y GNNs) y diversos conjuntos de datos (MNIST, Iris, Breast Cancer, Cora).

Fidelidad (RQ1): El valor de Shapley local se correlaciona fuertemente con el global (Pearson $r$ entre 0.53 y 0.84). La correlación es más alta en modelos con localidad exacta (KNN) y aceptable en aproximada (GNN).
Utilidad en Selección de Datos (RQ2): La valoración basada en Local Shapley es igual o superior a los métodos globales para tareas de selección de datos (pruning). En KNN, seleccionar solo el 10% de los datos con LSMR-A alcanza la precisión del 20-25% con métodos globales.
Eficiencia Computacional (RQ3):
- LSMR-A reduce el número de reentrenamientos en más de 3 órdenes de magnitud comparado con Monte Carlo Global en KNN.
- En GNN y SVM, logra aceleraciones de más de 10x.
- La escalabilidad es superior: mientras los métodos globales crecen exponencialmente o linealmente con el tamaño de los datos, el costo de LSMR-A se estabiliza o crece sublinealmente debido a la reutilización de subconjuntos.
Sensibilidad al Tamaño del Soporte (RQ4): Aumentar el tamaño del soporte mejora la fidelidad hasta un punto de saturación, pero LSMR-A mantiene una ventaja de velocidad masiva incluso con soportes grandes gracias a la reutilización.
Alineación del Modelo (RQ5): La localidad debe alinearse con la arquitectura del modelo evaluado. Usar un soporte definido por una arquitectura diferente (ej. usar vecinos KNN para evaluar un GNN) degrada significativamente la precisión, demostrando que la localidad es intrínseca a la arquitectura.

5. Significado e Impacto

Este trabajo transforma la valoración de datos de un problema de enumeración combinatoria exhaustiva a un problema de gestión de datos estructurados.

Teóricamente: Establece que la complejidad real de la valoración de Shapley es mucho menor de lo que se creía, gobernada por la estructura del modelo y no por el tamaño del dataset.
Prácticamente: Hace factible la valoración de datos a gran escala para modelos modernos (como GNNs y Deep Learning), donde los métodos anteriores eran computacionalmente prohibitivos.
Eficiencia: Al desacoplar el muestreo estadístico del costo de reentrenamiento, permite obtener estimaciones precisas y de baja varianza con una fracción mínima de recursos computacionales.

En resumen, "Local Shapley" demuestra que explotar la localidad inducida por el modelo y la reutilización óptima de subconjuntos permite lograr una valoración de datos escalable, eficiente y teóricamente óptima.