On The Most Discriminative Boolean Functions for Correlated Sources

Resumen Técnico: Sobre las Funciones Booleanas Más Discriminativas para Fuentes Correlacionadas

Planteamiento del Problema
Motivado por una conjetura de Amari y Kobayashi respecto a la maximización de la información de Fisher para fuentes correlacionadas, este artículo investiga el problema de identificar pares de funciones booleanas $(f, g)$ que maximizan la divergencia de Kullback-Leibler (KL) entre distribuciones de salida derivadas de dos fuentes binarias correlacionadas $(X^n, Y^n)$. Específicamente, las fuentes siguen una distribución con correlación $\rho_0$ o una distribución con correlación $\rho_1$. El objetivo es determinar qué funciones $f, g: \{0,1\}^n \to \{\pm 1\}$ maximizan la divergencia $D(P_{f(X^n)g(Y^n), \rho_0} \| P_{f(X^n)g(Y^n), \rho_1})$.

Este problema generaliza dos entornos conocidos:

1. Maximización de la Información Mutua: Cuando $\rho_1 = 0$ (fuentes independientes), el problema se reduce a maximizar la información mutua, donde la optimalidad de las funciones dictadoras fue establecida por Pichler, Piantànda y Matz.
2. Maximización de la Información de Fisher: El problema estudiado por Amari y Kobayashi, que busca maximizar la información de Fisher, puede verse como una versión local del problema de la divergencia KL donde $\rho_0$ y $\rho_1$ están infinitesimalmente cerca. Amari y Kobayashi conjeturaron que las funciones paridad son óptimas para todo $\rho$.

Metodología
Los autores emplean el análisis de Fourier en el cubo booleano como la principal herramienta analítica. Los elementos clave de la metodología incluyen:

• Expansión de Fourier: Representar las funciones booleanas en términos de funciones de paridad $\chi_S$, donde los coeficientes de Fourier $\hat{f}(S)$ caracterizan el comportamiento de la función.
• Estabilidad de Ruido y Operadores: Utilizar el operador de ruido $T_\rho$ y el concepto de estabilidad de ruido para relacionar la correlación de las entradas con la correlación de las salidas.
• Funciones de Nivel-$k$: Centrarse en funciones cuyos coeficientes de Fourier están soportados solo en conjuntos de tamaño $k$ (funciones de nivel-$k$). Nótese que las funciones de nivel-1 son funciones dictadoras, mientras que las funciones de nivel-$k$ para $k \ge 2$ incluyen, pero no se limitan a, las funciones paridad.
• Convexidad e Desigualdades: Demostrar cotas utilizando la convexidad conjunta de la divergencia KL, la desigualdad de Cauchy-Schwarz y lemas específicos sobre la convexidad de la divergencia con respecto a vectores de peso.
• Desigualdad del Procesamiento de Datos: Aplicar la desigualdad del procesamiento de datos para establecer resultados de optimalidad local.

Contribuciones Clave y Resultados

1. Maximización de la Divergencia KL:

   • Funciones No Sesgadas: Para funciones booleanas no sesgadas ($\hat{f}(\emptyset) = \hat{g}(\emptyset) = 0$), los autores demuestran que la divergencia KL se maximiza cuando $f$ y $g$ son funciones de nivel-$k$ idénticas para algún $k$. El $k$ óptimo depende de los parámetros $\rho_0$ y $\rho_1$.
   • Funciones Idénticas Sesgadas: Para el caso donde $f = g$ (no necesariamente no sesgadas) y la correlación es no negativa ($\rho \in [0, 1)$), la divergencia también es maximizada por funciones de nivel-$k$.
   • Optimalidad Local: El artículo demuestra que si una función en el par es una función de nivel-$k$, la divergencia no puede aumentarse eligiendo una segunda función diferente; el par óptimo consiste en dos funciones de nivel-$k$ idénticas.
   • Limitaciones: Los autores señalan que para el caso general de funciones sesgadas y distintas ($f \neq g$), o para regímenes de parámetros específicos (por ejemplo, $\rho_0 < \rho_1$ o signos opuestos), no se ha probado la optimalidad de las funciones de nivel-$k$. Ejemplos numéricos sugieren que, para ciertos parámetros, otras funciones además de las de nivel-$k$ (como las funciones mayoría) pueden ser óptimas.

2. Maximización de la Información de Fisher:

   • Aprovechando la relación de que la información de Fisher es la segunda derivada de la divergencia KL, los autores derivan resoluciones parciales a la conjetura de Amari-Kobayashi.
   • Demuestran que para funciones no sesgadas y para funciones idénticas en el régimen de correlación no negativa, la información de Fisher es maximizada por funciones de nivel-$k$. Dado que las funciones paridad son un subconjunto de las funciones de nivel-$k$, esto proporciona una resolución parcial a la conjetura de que las funciones paridad son óptimas. Sin embargo, la solución óptima es una clase más amplia (nivel-$k$) que solo las funciones paridad.

3. Prueba de Hipótesis Distribuida Bayesiana:

   • El artículo formula un problema bayesiano de prueba de hipótesis distribuida de un bit donde un receptor debe distinguir entre las correlaciones $\rho_0$ y $\rho_1$ basándose en salidas de un bit de $f(X^n)$ y $g(Y^n)$.
   • Se demuestra que la probabilidad de error de Bayes se minimiza (y la probabilidad correcta se maximiza) mediante funciones de nivel-$k$ entre todos los pares de funciones booleanas. La regla de decisión óptima depende del signo de la diferencia en las expectativas bajo las dos hipótesis.

4. Versión de Una Función:

   • El artículo discute la versión de un solo objeto del problema de maximización de la divergencia, análoga a la conjetura de Courtade-Kumar.
   • A diferencia del escenario de dos funciones, los autores proporcionan contraejemplos donde las funciones de nivel-$k$ no son óptimas para el caso de una sola función (por ejemplo, para $n=3$ con valores de $\rho$ específicos, las funciones mayoría o las funciones de nivel-2 superan a las funciones de nivel-$k$ dependiendo de los parámetros). Esto sugiere que los escenarios de una función y de dos funciones exhiben comportamientos distintos.

Significancia y Reivindicaciones
El artículo afirma proporcionar una resolución parcial a la conjetura de Amari-Kobayashi al demostrar que las funciones de nivel-$k$ (una clase que contiene a las funciones paridad) son óptimas para maximizar la información de Fisher y la divergencia KL bajo condiciones específicas (no sesgo o funciones idénticas en correlación no negativa).

Los autores enfatizan que, si bien las funciones de nivel-$k$ son óptimas en el escenario de dos funciones para las condiciones probadas, la solución general para el problema de dos funciones sigue abierta, particularmente para funciones sesgadas y distintas. Además, destacan un comportamiento distinto en el escenario de una sola función, donde las funciones de nivel-$k$ no son universalmente óptimas, contrastando con la conocida optimalidad de las funciones dictadoras en el entorno de la información mutua (Courtade-Kumar). Este trabajo une la inferencia estadística distribuida y el análisis de Fourier de funciones booleanas, ofreciendo nuevas perspectivas sobre la estructura de las compresiones óptimas para fuentes correlacionadas.