On The Most Discriminative Boolean Functions for Correlated Sources

Résumé technique : Sur les fonctions booléennes les plus discriminantes pour les sources corrélées

Énoncé du problème
Motivés par une conjecture d'Amari et Kobayashi concernant la maximisation de l'information de Fisher pour des sources corrélées, cet article étudie le problème d'identification des paires de fonctions booléennes $(f, g)$ qui maximisent la divergence de Kullback-Leibler (KL) entre les distributions de sortie dérivées de deux sources binaires corrélées $(X^n, Y^n)$. Plus précisément, les sources suivent soit une distribution corrélée à $\rho_0$, soit une distribution corrélée à $\rho_1$. L'objectif est de déterminer quelles fonctions $f, g: \{0,1\}^n \to \{\pm 1\}$ maximisent la divergence $D(P_{f(X^n)g(Y^n), \rho_0} \| P_{f(X^n)g(Y^n), \rho_1})$.

Ce problème généralise deux contextes connus :

1. Maximisation de l'information mutuelle : Lorsque $\rho_1 = 0$ (sources indépendantes), le problème se réduit à la maximisation de l'information mutuelle, où l'optimalité des fonctions dictatrices a été établie par Pichler, Piantanida et Matz.
2. Maximisation de l'information de Fisher : Le problème étudié par Amari et Kobayashi, qui cherche à maximiser l'information de Fisher, peut être vu comme une version locale du problème de la divergence KL où $\rho_0$ et $\rho_1$ sont infiniment proches. Amari et Kobayashi ont conjecturé que les fonctions de parité sont optimales pour tout $\rho$.

Méthodologie
Les auteurs utilisent l'analyse de Fourier sur le cube booléen comme principal outil analytique. Les éléments clés de la méthodologie sont :

• Décomposition de Fourier : Représentation des fonctions booléennes en termes de fonctions de parité $\chi_S$, où les coefficients de Fourier $\hat{f}(S)$ caractérisent le comportement de la fonction.
• Stabilité au bruit et opérateurs : Utilisation de l'opérateur de bruit $T_\rho$ et du concept de stabilité au bruit pour relier la corrélation des entrées à la corrélation des sorties.
• Fonctions de niveau-$k$ : Focalisation sur les fonctions dont les coefficients de Fourier ne sont supportés que sur des ensembles de taille $k$ (fonctions de niveau-$k$). Notez que les fonctions de niveau-1 sont les fonctions dictatrices, tandis que les fonctions de niveau-$k$ pour $k \ge 2$ incluent, sans s'y limiter, les fonctions de parité.
• Convexité et inégalités : Démonstration de bornes en utilisant la convexité jointe de la divergence KL, l'inégalité de Cauchy-Schwarz et des lemmes spécifiques concernant la convexité de la divergence par rapport aux vecteurs de poids.
• Inégalité de traitement des données (Data Processing Inequality) : Application de l'inégalité de traitement des données pour établir des résultats d'optimalité locale.

Contributions clés et résultats

1. Maximisation de la divergence KL :

   • Fonctions non biaisées : Pour les fonctions booléennes non biaisées ($\hat{f}(\emptyset) = \hat{g}(\emptyset) = 0$), les auteurs prouvent que la divergence KL est maximisée lorsque $f$ et $g$ sont des fonctions de niveau-$k$ identiques pour un certain $k$. Le $k$ optimal dépend des paramètres $\rho_0$ et $\rho_1$.
   • Fonctions identiques biaisées : Pour le cas où $f = g$ (non nécessairement non biaisées) et la corrélation est non négative ($\rho \in [0, 1)$), la divergence est également maximisée par des fonctions de niveau-$k$.
   • Optimalité locale : L'article prouve que si l'une des fonctions de la paire est une fonction de niveau-$k$, la divergence ne peut être augmentée en choisissant une seconde fonction différente ; la paire optimale consiste en deux fonctions de niveau-$k$ identiques.
   • Limites : Les auteurs notent que pour le cas général de fonctions biaisées et distinctes ($f \neq g$), ou pour des régimes de paramètres spécifiques (par exemple, $\rho_0 < \rho_1$ ou des signes opposés), l'optimalité des fonctions de niveau-$k$ n'est pas prouvée. Des exemples numériques suggèrent que pour certains paramètres, des fonctions autres que les fonctions de niveau-$k$ (telles que les fonctions de majorité) peuvent être optimales.

2. Maximisation de l'information de Fisher :

   • En exploitant la relation selon laquelle l'information de Fisher est la dérivée seconde de la divergence KL, les auteurs dérivent des résolutions partielles de la conjecture d'Amari-Kobayashi.
   • Ils prouvent que pour les fonctions non biaisées et pour les fonctions identiques dans le régime de corrélation non négative, l'information de Fisher est maximisée par des fonctions de niveau-$k$. Puisque les fonctions de parité sont un sous-ensemble des fonctions de niveau-$k$, cela fournit une résolution partielle de la conjecture selon laquelle les fonctions de parité sont optimales. Cependant, la solution optimale est une classe plus large (niveau-$k$) que les seules fonctions de parité.

3. Tests d'hypothèses distribués bayésiens :

   • L'article formule un problème de test d'hypothèse distribué bayésien à un bit, où un récepteur doit distinguer entre les corrélations $\rho_0$ et $\rho_1$ sur la base de sorties à un bit de $f(X^n)$ et $g(Y^n)$.
   • Il est prouvé que la probabilité d'erreur bayésienne est minimisée (et la probabilité de succès maximisée) par les fonctions de niveau-$k$ parmi toutes les paires de fonctions booléennes. La règle de décision optimale dépend du signe de la différence des espérances sous les deux hypothèses.

4. Version à une fonction :

   • L'article traite de la version du problème de maximisation de la divergence à une seule fonction, analogue à la conjecture de Courtade-Kumar.
   • Contrairement au cas à deux fonctions, les auteurs fournissent des contre-exemples où les fonctions de niveau-$k$ ne sont pas optimales pour le cas à une fonction (par exemple, pour $n=3$ avec des valeurs de $\rho$ spécifiques, des fonctions de majorité ou de niveau-2 surpassent les fonctions de niveau-$k$ selon les paramètres). Cela suggère que les contextes à une fonction et à deux fonctions présentent des comportements distincts.

Signification et affirmations
L'article affirme fournir une résolution partielle de la conjecture d'Amari-Kobayashi en démontrant que les fonctions de niveau-$k$ (une classe contenant les fonctions de parité) sont optimales pour maximiser l'information de Fisher et la divergence KL sous des conditions spécifiques (non-biais ou fonctions identiques dans un régime de corrélation non négative).

Les auteurs soulignent que, bien que les fonctions de niveau-$k$ soient optimales dans le cadre à deux fonctions pour les conditions qu'ils prouvent, la solution générale du problème à deux fonctions reste ouverte, particulièrement pour les fonctions biaisées et distinctes. De plus, ils mettent en évidence un comportement distinct dans le cadre à une fonction, où les fonctions de niveau-$k$ ne sont pas universellement optimales, contrastant avec l'optimalité connue des fonctions dictatrices dans le cadre de l'information mutuelle (Courtade-Kumar). Ce travail fait le pont entre l'inférence statistique distribuée et l'analyse de Fourier des fonctions booléennes, offrant de nouvelles perspectives sur la structure des compressions optimales pour les sources corrélées.