On The Most Discriminative Boolean Functions for Correlated Sources

技術要約：相関のある情報源に対する最も識別力の高いブール関数について

問題提起
本論文は、相関のある情報源におけるフィッシャー情報の最大化に関する阿万里（Amari）と小林の予想に基づき、2つの相関のあるバイナリ情報源 $(X^n, Y^n)$ から導出される出力分布間のカルバック・ライブラー（KL）ダイバージェンスを最大化するブール関数 $(f, g)$ のペアを特定する問題を調査するものである。具体的には、これらのソースは $\rho_0$-相関分布または $\rho_1$-相関分布に従うものとする。目的は、 $f, g: \{0,1\}^n \to \{\pm 1\}$ という関数が、 $D(P_{f(X^n)g(Y^n), \rho_0} \| P_{f(X^n)g(Y^n), \rho_1})$ を最大化する関数を決定することである。

この問題は、既知の2つの設定を一般化したものである：

1. 相互情報量最大化： $\rho_1 = 0$ （独立なソース）の場合、この問題は相互情報量の最大化へと帰着し、ディクテーター（独裁者）関数の最適性が Pichler, Piantida, および Matz によって確立されている。
2. フィッシャー情報量最大化： 阿万里と小林が研究したフィッシャー情報量を最大化する問題は、$\rho_0$ と $\rho_1$ が極めて近い場合の KL ダイバージェンス問題の局所的なバージョンと見なすことができる。阿万里と小林は、すべての $\rho$ に対してパリティ関数が最適であると予想している。

手法
著者らは、主要な解析手法としてブール立方体上のフーリエ解析を用いている。手法の鍵となる要素は以下の通りである：

• フーリエ展開： ブール関数をパリティ関数 $\chi_S$ を用いて表現し、フーリエ係数 $\hat{f}(S)$ によって関数の振る舞いを特徴付ける。
• ノイズ安定性とオペレーター： ノイズオペレータ $T_\rho$ とノイズ安定性の概念を利用して、入力の相関と出力の相関を関連付ける。
• レベル-$k$ 関数： フーリエ係数がサイズ $k$ の集合上にのみサポートされている関数（レベル-$k$ 関数）に焦点を当てる。なお、レベル-1 関数はディクテーター関数であり、レベル $k \ge 2$ のレベル-$k$ 関数にはパリティ関数が含まれるが、それだけに限定されない。
• 凸性と不等式： KL ダイバージェンスの結合凸性、コーシー＝シュワルツの不等式、および重みベクトルに関するダイバージェンスの凸性に関する特定の補題を用いて、境界の証明を行う。
• データ処理不等式： 局所的な最適性の結果を確立するために、データ処理不等式を適用する。

主な貢献と結果

1. KL ダイバージェンスの最大化：

   • 非バイアス関数： 非バイアスなブール関数（$\hat{f}(\emptyset) = \hat{g}(\emptyset) = 0$）の場合、KL ダイバージェンスは、$f$ と $g$ がある $k$ に対して同一のレベル-$k$ 関数であるときに最大化されることを証明している。最適な $k$ はパラメータ $\rho_0$ および $\rho_1$ に依存する。
   • バイアスのある同一関数： $f = g$ の場合（必ずしも非バイアスではない）かつ相関が非負（$\rho \in [0, 1)$）の場合、ダイバージェンスはレベル-$k$ 関数によっても最大化される。
   • 局所的最適性： 片方の関数がレベル-$k$ 関数であれば、もう一方の関数を別の関数に変更してもダイバージェンスを増大させることはできないことを証明している。すなわち、最適なペアは2つの同一なレベル-$k$ 関数からなる。
   • 限界： 著者らは、一般的なケース（バイアスがあり、かつ $f \neq g$ である場合）、または特定のパラメータ領域（例：$\rho_0 < \rho_1$ または符号が異なる場合）において、レベル-$k$ 関数の最適性は証明されていないことを指摘している。数値例は、特定のパラメータにおいて、レベル-$k$ 以外の関数（マジョリティ関数など）が最適となる可能性を示唆している。

2. フィッシャー情報量の最大化：

   • KL ダイバージェンスの二階微分としてのフィッシャー情報量の関係を利用し、阿万里・小林予想に対する部分的な解決策を導出している。
   • 非バイアス関数および同一関数（非負相関領域）の場合において、フィッシャー情報はレベル-$k$ 関数によって最大化されることを証明している。パリティ関数はレベル-$k$ 関数のサブセットであるため、これはパリティ関数が最適であるという予想に対する部分的な解決となる。ただし、最適な解はパリティ関数よりも広いクラス（レベル-$k$）である。

3. ベイズ分散仮説検定：

   • 本論文は、受信者が $f(X^n)$ と $g(Y^n)$ からの1ビット出力に基づき、$\rho_0$ と $\rho_1$ の相関を区別しなければならない、ベイズ的な1ビット分散仮説検定問題を定式化している。
   • すべてのブール関数のペアの中で、レベル-$k$ 関数によってベイズ誤り確率が最小化され（かつ正解確率が最大化される）ことが証明されている。最適な決定則は、2つの仮説下における期待値の差の符号に依存する。

4. 1関数バージョン：

   • 本論文では、Courtade-Kumar の予想に類似した、ダイバージェンス最大化問題の1関数バージョンについても論じている。
   • 2関数設定とは異なり、レベル-$k$ 関数が最適ではない反例（例：特定の $\rho$ 値を持つ $n=3$ の場合、マジョリティ関数やレベル-2 関数がレベル-$k$ 関数よりも優れた性能を示す）を提示している。これは、1関数設定と2関数設定が異なる挙動を示すことを示唆している。

意義と主張
本論文は、非バイアス性または同一関数（非負相関）という特定の条件下において、レベル-$k$ 関数（パリティ関数を含むクラス）がフィッシャー情報量を最大化するために最適であることを示すことで、阿万里・小林予想の部分的な解決を提供すると主張している。

著者らは、レベル-$k$ 関数は証明された条件下での2関数設定において最適であるが、一般的な2関数問題の解は、バイアスのある異なる関数については依然として未解決であることを強調している。さらに、レベル-$k$ 関数が、相互情報量（Courtade-Kumar）の設定におけるディクテーター関数の最適性に類似した挙動を示す一方で、1関数設定では普遍的に最適ではないという、異なる挙動についても強調している。本研究は、分散統計推論とブール関数のフーリエ解析を橋渡しし、相関のある情報源に対する最適な圧縮の構造に関する新たな知見を提供している。