On The Most Discriminative Boolean Functions for Correlated Sources

Technische Samenvatting: Over de meest discriminerende Booleaanse functies voor gecorreleerde bronnen

Probleemstelling
Gesterkt door een conjectuur van Amari en Kobayashi met betrekking tot de maximalisatie van de Fisher-informatie voor gecorreleerde bronnen, onderzoekt dit artikel het probleem van het identificeren van paren Booleaanse functies $(f, g)$ die de Kullback-Leibler (KL) divergentie maximaliseren tussen de output-distributies afgeleid van twee gecorreleerde binaire bronnen $(X^n, Y^n)$. Specifiek volgen de bronnen ofwel een $\rho_0$-gecorreleerde distributie ofwel een $\rho_1$-gecorreleerde distributie. Het doel is om te bepalen welke functies $f, g: \{0,1\}^n \to \{\pm 1\}$ de divergentie $D(P_{f(X^n)g(Y^n), \rho_0} \| P_{f(X^n)g(Y^n), \rho_1})$ maximaliseren.

Dit probleem generaliseert twee bekende situaties:

1. Maximalisatie van wederzijdse informatie: Wanneer $\rho_1 = 0$ (onafhankelijke bronnen), reduceert het probleem zich tot het maximaliseren van de wederzijdse informatie, waarbij de optimaliteit van dictator-functies werd vastgesteld door Pichler, Piantàida en Matz.
2. Maximalisatie van Fisher-informatie: Het probleem dat door Amari en Kobayashi werd bestudeerd, dat de Fisher-informatie tracht te maximaliseren, kan worden beschouwd als een lokale versie van het KL-divergentieprobleem waarbij $\rho_0$ en $\rho_1$ infinitesimaal dicht bij elkaar liggen. Amari en Kobayashi suggereerden dat pariteit-functies optimaal zijn voor alle $\rho$.

Methodologie
De auteurs maken gebruik van Fourier-analyse op de Booleaanse kubus als het primaire analytische instrument. Belangrijke elementen van de methodologie zijn:

• Fourier-expansie: Het representeren van Booleaanse functies in termen van pariteit-functies $\chi_S$, waarbij de Fourier-coëfficiënten $\hat{f}(S)$ het gedrag van de functie karakteriseren.
• Ruis-stabiliteit en Operatoren: Het gebruik van de ruis-operator $T_\rho$ en het concept van ruis-stabiliteit om de correlatie van inputs te relateren aan de correlatie van outputs.
• Level-$k$ Functies: Het focussen op functies waarvan de Fourier-coëfficiënten alleen ondersteund worden op verzamelingen van grootte $k$ (level-$k$ functies). Merk op dat level-1 functies dictator-functies zijn, terwijl level-$k$ functies voor $k \ge 2$ onder meer pariteit-functies omvatten.
• Convexiteit en Ongelijkheid: Het bewijzen van grenzen met behulp van de gezamenlijke convexiteit van de KL-divergentie, de Cauchy-Schwarz-ongelijkheid en specifieke lemma's met betrekking tot de convexiteit van divergentie ten opzichte van gewichtsvectoren.
• Dataverwerkingsongelijkheid: Het toepassen van de dataverwerkingsongelijkheid om lokale optimaliteitsresultaten vast te stellen.

Kernbijdragen en Resultaten

1. KL-divergentie Maximalisatie:

   • Onbevooroordeelde Functies: Voor onbevooroordeelde Booleaanse functies ($\hat{f}(\emptyset) = \hat{g}(\emptyset) = 0$) bewijzen de auteurs dat de KL-divergentie wordt gemaximaliseerd wanneer $f$ en $g$ identieke level-$k$ functies zijn voor een bepaalde $k$. De optimale $k$ hangt af van de parameters $\rho_0$ en $\rho_1$.
   • Bevooroordeelde Identieke Functies: Voor het geval waar $f = g$ (niet noodzakelijkerwijs onbevooroordeeld) en de correlatie niet-negatief is ($\rho \in [0, 1)$), wordt de divergentie eveneens gemaximaliseerd door level-$k$ functies.
   • Lokale Optimaliteit: Het artikel bewijst dat als één functie in het paar een level-$k$ functie is, de divergentie niet kan worden vergroot door een andere tweede functie te kiezen; het optimale paar bestaat uit twee identieke level-$k$ functies.
   • Beperkingen: De auteurs merken op dat voor het algemene geval van bevooroordeelde, verschillende functies ($f \neq g$), of voor specifieke parameterregimes (bijv. $\rho_0 < \rho_1$ of tegengestelde tekens), de optimaliteit van level-$k$ functies niet bewezen is. Numerieke voorbeelden suggereren dat voor bepaalde parameters functies die niet level-$k$ zijn (zoals meerderheidsfuncties) optimaal kunnen zijn.

2. Fisher-informatie Maximalisatie:

   • Door gebruik te maken van de relatie dat Fisher-informatie de tweede afgeleide van de KL-divergentie is, leiden de auteurs partiële oplossingen af voor de Amari-Kobayashi conjectuur.
   • Zij bewijzen dat voor onbevooroordeelde functies en voor identieke functies in het regime van niet-negatieve correlatie, de Fisher-informatie wordt gemaximaliseerd door level-$k$ functies. Aangezien pariteit-functies een deelverzameling zijn van level-$k$ functies, biedt dit een partiële oplossing voor de conjectuur dat pariteit-functies optimaal zijn. Echter, de optimale oplossing is een bredere klasse (level-$k$) dan enkel pariteit-functies.

3. Bayesiaanse Gedistribueerde Hypothesetests:

   • Het artikel formuleert een Bayesiaans één-bit gedistribueerd hypothesetests-probleem waarbij een ontvanger de correlaties $\rho_0$ en $\rho_1$ moet onderscheiden op basis van één-bit outputs van $f(X^n)$ en $g(Y^n)$.
   • Er wordt bewezen dat de Bayes-foutkans wordt geminimaliseerd (en de correcte waarschijnlijkheid wordt gemaximaliseerd) door level-$k$ functies onder alle paren Booleaanse functies. De optimale beslisregel hangt af van het teken van het verschil in verwachtingen onder de twee hypothesen.

4. Eén-functie Versie:

   • Het artikel bespreekt de één-functie versie van het divergentie-maximalisatieprobleem, analoog aan de Courtade-Kumar conjectuur.
   • In tegenstelling tot de twee-functie setting, bieden de auteurs tegenvoorbeelden waarbij level-$k$ functies niet optimaal zijn voor de één-functie case (bijv. voor $n=3$ met specifieke $\rho$ waarden, presteren meerderheidsfuncties of level-2 functies beter dan level-$k$ functies afhankelijk van de parameters). Dit suggereert dat de één-functie en twee-functie settings verschillend gedrag vertonen.

Betekenis en Claims
Het artikel claimt een partiële oplossing te bieden voor de Amari-Kobayashi conjectuur door aan te tonen dat level-$k$ functies (een klasse die pariteit-functies bevat) optimaal zijn voor het maximaliseren van de Fisher-informatie en de KL-divergentie onder specifieke condities (onbevooroordeeldheid of identieke functies in het regime van niet-negatieve correlatie).

De auteurs benadrukken dat hoewel level-$k$ functies optimaal zijn in de twee-functie setting voor de condities die zij bewijzen, de algemene oplossing voor het twee-functie probleem open blijft, met name voor bevooroordeelde, verschillende functies. Verder wijzen zij op een duidelijk verschillend gedrag in de één-functie setting, waar level-$k$ functies niet universeel optimaal zijn, wat contrasteert met de bekende optimaliteit van dictator-functies in de wederzijdse informatie (Courtade-Kumar) setting. Het werk overbrugt gedistribueerde statistische inferentie en de Fourier-analyse van Booleaanse functies, en biedt nieuwe inzichten in de structuur van optimale compressies voor gecorreleerde bronnen.