Evaluando el muestreo antitético para aproximar los valores de Shapley, Banzhaf y Owen
Autores: Staudacher, Jochen; Pollmann, Tim
Idioma: Inglés
Editor: MDPI
Año: 2023
Acceso abierto
Artículo científico
Categoría
Matemáticas
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 9
Citaciones: Sin citaciones
El cálculo de los valores de Shapley para grandes juegos cooperativos es un problema NP-duro. Para aplicaciones prácticas, se utiliza ampliamente la aproximación estocástica a través del muestreo por permutación. En el contexto de las aplicaciones de aprendizaje automático del valor de Shapley, el concepto de muestreo antitético se ha vuelto popular. La idea es emplear la permutación inversa de una muestra para reducir la varianza y acelerar la convergencia del algoritmo. Estudiamos este enfoque para los valores de Shapley y Banzhaf, así como para el valor de Owen, que es un concepto de solución para juegos con precoaliciones. Combinamos muestras antitéticas con algoritmos de muestreo estratificado establecidos. Finalmente, evaluamos el rendimiento de estos algoritmos en cuatro tipos diferentes de juegos cooperativos.
Descripción
El cálculo de los valores de Shapley para grandes juegos cooperativos es un problema NP-duro. Para aplicaciones prácticas, se utiliza ampliamente la aproximación estocástica a través del muestreo por permutación. En el contexto de las aplicaciones de aprendizaje automático del valor de Shapley, el concepto de muestreo antitético se ha vuelto popular. La idea es emplear la permutación inversa de una muestra para reducir la varianza y acelerar la convergencia del algoritmo. Estudiamos este enfoque para los valores de Shapley y Banzhaf, así como para el valor de Owen, que es un concepto de solución para juegos con precoaliciones. Combinamos muestras antitéticas con algoritmos de muestreo estratificado establecidos. Finalmente, evaluamos el rendimiento de estos algoritmos en cuatro tipos diferentes de juegos cooperativos.