Cheap Permutation Testing

Resumen Técnico: Pruebas de Permutación Económicas (Cheap Permutation Testing)

Planteamiento del Problema
Las pruebas de permutación son un pilar fundamental de la estadística no paramétrica y el aprendizaje automático, ampliamente utilizadas para probar homogeneidad (pruebas de dos muestras) e independencia. Son favorecidas por su capacidad de proporcionar un control exacto sobre los falsos positivos (error de Tipo I) en muestras finitas, así como por su optimalidad minimax cuando se combinan con estadísticas U y V. Sin embargo, las pruebas de permutación estándar sufren de costos computacionales prohibitivos. Para lograr una potencia fiable, normalmente requieren recalcular un estadístico de prueba cientos o miles de veces ($B$ permutaciones) sobre $n$ puntos de datos. Para estadísticos de prueba cuadráticos como la Máxima Discrepancia Media (MMD) o el Criterio de Independencia de Hilbert-Schmidt (HSIC), esto resulta en una complejidad de tiempo de ejecución de $\Theta(Bn^2)$, lo que las hace inviables para conjuntos de datos a gran escala.

Metodología
Los autores proponen "pruebas de permutación económicas", una estrategia para acelerar el procedimiento de prueba agrupando los puntos de datos en $s$ contenedores (bins) y permutando las etiquetas de los contenedores en lugar de los puntos de datos individuales.

1. Permutación por Contenedores (Binned Permutation): En lugar de permutar $n$ índices, el método particiona los índices $[n]$ en $s$ contenedores consecutivos de igual tamaño. El estadístico de prueba se calcula sobre las muestras formadas mediante la permutación de estos $s$ contenedores.
2. Estadísticos Suficientes: La innovación central radica en el uso de estadísticos suficientes compactos. Para estadísticos de prueba cuadráticos (incluyendo estadísticas U de homogeneidad y estadísticas V de independencia), los autores demuestran que los estadísticos de prueba permutados dependen únicamente de agregados precalculados de las funciones base sobre los contenedores.
   • Para pruebas de homogeneidad, el método precalcula $3s^2$ estadísticos suficientes (sumas de funciones base sobre pares de contenedores).
   • Para pruebas de independencia (específicamente usando permutaciones de wild bootstrap), el método precalcula $s^2/2$ estadísticos suficientes.
3. Eficiencia Algorítmica: Una vez que se calculan el estadístico de prueba inicial y los $O(s^2)$ estadísticos suficientes (tomando un tiempo de $\Theta(n^2)$), cada uno de los $B$ estadísticos permutados puede calcularse en $\Theta(s^2)$ de tiempo. Consecuentemente, el tiempo de ejecución total se convierte en $\Theta(n^2 + Bs^2)$. Si $s$ se elige como una constante o una función de crecimiento lento respecto a $n$, la carga de la permutación se vuelve insignificante comparada con el costo de evaluar un solo estadístico de prueba.

Contribuciones Clave
El artículo realiza contribuciones teóricas y prácticas:

1. Exactitud y Validez: Los autores demuestran que las pruebas de permutación económicas (Algoritmos 1 y 2) son exactas. Bajo la hipótesis nula, rechazan con una probabilidad exactamente $\alpha$ para cualquier tamaño de muestra, distribución de datos y número de permutaciones $B$, heredando la validez de muestra finita de las pruebas de permutación estándar.
2. Garantías de Potencia: El documento establece garantías cuantitativas de potencia para las pruebas económicas utilizando estadísticas U y V.
   • Homogeneidad: Se demuestra que el umbral de separación requerido para que una prueba económica logre una potencia $1-\beta$ es asintóticamente equivalente al de las pruebas de permutación estándar. Sorprendentemente, esta equivalencia se mantiene incluso cuando el número de contenedores $s$ es independiente del tamaño de la muestra $n$ (por ejemplo, si $s$ es constante), siempre que $s$ sea suficientemente grande en relación con los componentes de varianza.
   • Independencia: Se establecen garantías similares para las pruebas de independencia utilizando permutaciones de wild bootstrap sobre los contenedores. Las tasas de separación coinciden con las tasas de las pruebas estándar incluso con un número constante de contenedores.
3. Optimalidad Minimax: Los autores extienden estos resultados para establecer la optimalidad de tasa minimax de las pruebas económicas para cuatro problemas clásicos: homogeneidad discreta, homogeneidad de Hölder, independencia discreta e independencia de Hölder. Además, demuestran la optimalidad minimax para las pruebas de homogeneidad basadas en MMD y las de independencia basadas en HSIC. En todos los casos, las tasas de detección óptimas son alcanzables con un recuento de contenedores $s$ que es independiente de $n$.
4. Análisis Refinado: El trabajo mejora el análisis de potencia existente para las pruebas de permutación estándar refinando la dependencia con el número de permutaciones $B$ y el nivel de significancia $\alpha$, utilizando un método de comparación de cuantiles que produce límites más ajustados que los enfoques previos de "dos momentos".

Resultados
Los hallazgos teóricos se complementan con extensos experimentos que comparan las pruebas de permutación económicas contra las pruebas de permutación estándar y otros métodos de vanguardia (incluyendo cross-MMD/HSIC asintótico, MMD agregado y características de Fourier aleatorias).

• Homogeneidad (MMD, WMW, MMD Agregado): Los experimentos muestran que las pruebas económicas con un pequeño número de contenedores (por ejemplo, $s=32$ o $s=128$) alcanzan una potencia casi idéntica a las pruebas de permutación estándar en varios tamaños de muestra. No obstante, son consistentemente entre 100 y 900 veces más rápidas.
• Independencia (HSIC): Las pruebas de HSIC económicas con $s=64$ o $s=128$ contenedores igualan la potencia de las pruebas de wild bootstrap estándar siendo aproximadamente 15 veces más rápidas.
• Comparación con Métodos Asintóticos: Aunque los métodos asintóticos (como cross-MMD) son rápidos, sacrifican la validez de muestra finita y suelen presentar una potencia reducida. Las pruebas de permutación económicas logran los beneficios de velocidad de estos métodos asintóticos manteniendo la validez exacta de muestra finita y la mayor potencia de las pruebas de permutación estándar.
• Escalabilidad: El tiempo de ejecución de las pruebas económicas permanece esencialmente constante a medida que aumenta el tamaño de la muestra $n$ (una vez calculado el estadístico inicial de $O(n^2)$), mientras que las pruebas de permutación estándar escalan linealmente con $n$ para alcanzar el mismo nivel de potencia.

Significado
El artículo sostiene que la prueba de permutación económica ofrece un "remedio simple" al cuello de botella computacional de las pruebas no paramétricas sin sacrificar el rigor estadístico. Al desacoplar la carga de la permutación del tamaño de la muestra $n$, el método permite el uso de pruebas de permutación exactas y de optimalidad minimax en regímenes donde antes eran computacionalmente prohibitivas. Los autores enfatizan que este enfoque permite retener el control exacto de los falsos positivos y la optimalidad minimax de las pruebas de permutación estándar, ejecutándose en una fracción del tiempo, haciendo factible la realización de pruebas de hipótesis rigurosas para aplicaciones de datos a gran escala. El trabajo sugiere que, para estadísticos de prueba cuadráticos, el "costo" de la exactitud no tiene por qué ser alto, siempre que se utilicen la estructura de los estadísticos suficientes por contenedor.