Håstadのスイッチング補題

回路計算量の理論における重要な結果の一つである Håstadのスイッチング補題 を紹介します. 簡潔にいうとこの補題は, 99%の変数をランダムに固定することによってDNFの決定木が小さくなることを主張する結果です. 応用としてparity関数に対する$\mathrm{AC}^0$回路 (非有界fan-inをもつ定数段回路のクラス)に対するタイトな下界を証明できます. 証明の本質には決定木が深くなるようなDNFの部分代入は短い長さで記述できる (従ってそのような部分代入の個数は相対的に少ない) というアイデアを使っています.

スイッチング補題は海外の大学に講義資料があり, 本記事もそれらを参考にしました:

• lecture note by O’Donnell … 長いがかなり丁寧.
• lecture note by Jonathan Katz … 証明は短く簡潔. O’Donellの証明の要約
• lecture note by Lovett … 証明はしていないがさまざまな帰結をFourier analysisの視点から紹介

1. 準備

CNF, DNF, 決定木など必要な概念を定義していきます.　ここでは$n$変数の論理関数といえば$\{0,1\}^n \to \{0,1\}$を意味し, true/falseをそれぞれ1/0で表します.

定義1.1 (CNF, DNF).

• 論理変数$\mathrm{x}$に対して, $\mathrm{x}$と$\overline{\mathrm{x}}$をリテラル (literal) と呼ぶ.
• 複数のリテラルを$\lor$で繋げたもの $\ell_1 \lor \dots \lor \ell_w$ を節 (clause) と呼ぶ. 同様に, 複数のリテラルを$\land$で繋げたもの $\ell_1 \land \dots \land \ell_w$ を項 (term) と呼ぶ. このとき, 繋げたリテラルの個数$w$を幅 (width) と呼ぶ.
• 複数の節 $C_1, \dots, C_m$ を $\land$ で繋げた論理式の表現形式を連言標準形 (CNF) と呼ぶ. 同様に, 複数の項 $T_1,\dots,T_m$ を $\lor$ で繋げたものを選言標準形 (DNF) と呼ぶ. この記事ではそれぞれをCNF, DNFと呼ぶことにする.
• 特に, 全ての節 (項) の幅が$w$以下であるCNF (DNF) を$w$-CNF (DNF)という.

ド・モルガンの法則より, CNFの否定をとるとDNFになります. 従って, 本記事ではCNFとDNFはDNFに焦点をあてて説明しますが, 否定をとることによってCNFに変換しても同じことが成り立ちます.

図1. 3-DNFの例

CNFやDNFはあくまでも論理式のフォーマットの一つです. $n$変数の論理式は全部で$2^{2^n}$個あるので, その全てを表現しようとすると$2^n$ビット必要となりますが, 項が$m$個の$w$-DNFは$O(mw\log n)$ビットで表現できるので, $m$と$w$が小さいときのDNFは論理式のコンパクトな表現になっています. 逆に, 任意の論理関数は$2^n$個の項をもつ$n$-DNFで表現できます.

図2. 真理値表からDNFへの変換

定義1.2 (決定木).

次の性質を持つ二分木を決定木 (deceision tree) という:

• 葉には0または1のラベルがついていて, 葉以外の頂点はどれかの変数でラベル付けされている.
• 葉以外の各頂点から子に向かう二本の辺には0または1のラベルがついている.

決定木による計算では, 根から開始して入力に応じて葉に向かって遷移していき, たどり着いた葉のラベルを出力する. 遷移の規則は次のようにして定める: 現在いる頂点のラベルの変数$x_i$に対し $x_i=b \in \{0,1\}$ならばラベル$b$の辺に沿って子に遷移する.

論理関数 $f\colon \{0,1\}^n\to\{0,1\}$と等価な決定木の中での最小の深さを$f$の決定木複雑性と呼び, $\mathsf{DT}(f)$で表す.

図3. 決定木の例.

決定木複雑性が小さい回路は幅の小さいDNFで表現できます.

観察1.3 (決定木$\Rightarrow$DNF).

論理関数$f$が$\mathsf{DT}(f) \le w$を満たすならば, $f$は$w$-DNFで表現できる.

図4. 各1の葉に対し, そこに至るパスに対応する割り当てを1にする項を作る. これらの項をORでつなげればよい.

同様に, 否定を考えることによって, 幅の小さいCNFも構成できます.

任意の$n$-変数の論理関数$f$は全ての変数の割り当てを列挙することによって深さ$n$の決定木で表現できます. これを$f$の自明な決定木と呼ぶことにします. 自明な決定木は深さ$n$の完全平衡二分木です.

2. Håstadのスイッチング補題

Håstadのスイッチング補題は, 幅の小さいDNFの変数をいくつかランダムに選んでランダムに0または1を代入すると決定木複雑性が小さくなるということを主張します. 結果をフォーマルに述べるために, ランダム制限という概念を以下で定義します.

定義2.1 (制限).

パラメータ$n,s\in\mathbb{N}$に対し, $n$変数の$s$-制限 (または部分割り当て) とは関数$\alpha\colon [n] \to \{0,1,\star\}$であって, $s$個の$i\in[n]$に対して$\alpha(i) = \star$を満たすものである. $s$-制限全体の集合を$\mathcal{R}_s$とする (ここでは$n$は固定して考える. $\mathcal{R}$はrestrictionの略). $\mathcal{R}_s$から一様ランダムに選ばれた制限をランダム$s$-制限と呼ぶ.

$s$-制限$\alpha$は部分的に変数に代入を行う操作 ($\alpha(i)=0$ならば$x_i\leftarrow 0$, $\alpha(j)=1$ならば$x_j\leftarrow 1$) として捉える. 変数$x_1,\dots,x_n$をもつ論理関数 $f\colon \{0,1\}^n \to \{0,1\}$ に対してこの部分的な代入操作を行なって得られる$s$変数論理関数を$f|_\alpha$とする.

$s$-制限とは$s$変数関数にするという操作です. ランダム$s$-制限とは, ランダムに$n-s$個の変数を選んで$0$または$1$をランダムに代入するという操作です.

図5. $1$-制限の例.

定理2.2 (スイッチング補題 [Håstad, 1986]).

$w$-DNFで表現される論理関数 $f \colon \{0,1\}^n \to \{0,1\}$ に対するランダム$s$-制限$\alpha$は以下を満たす:
$$\begin{align*} \Pr_\alpha\left[ \mathsf{DT}(f|_\alpha) > d \right] \le \left(\frac{4w s}{n-s} \right)^d \end{align*}$$

冒頭にも述べたとおり, Håstadのスイッチング補題とは幅の小さいDNFの変数をランダムにいくつか選んでランダムに代入操作を施すと, 得られる関数は浅い決定木で表現できるという結果です.

応用の一つとしてparity関数のAC0回路下界の証明にあります. AC0回路とは, 定数段でfan-in (各素子の入次数) が非有界なものです. parity関数とは入力の中の$1$の個数の偶奇を出力する関数です. 

図6. AC0回路のイメージ. 途中の$\neg$素子は省略.

スイッチング補題および観察1.3より, ランダムな制約を考えるとDNFをCNFに変換することができます. これをAC0回路の最下段に適用すると, $\lor$と$\land$の切り替えの回数を一つだけ減らせます. これを定数回だけ繰り返すとAC0回路は最終的には定数関数になってしまいます. 一方でparity関数は$s>0$である限り, どのような$s$-制限を考えても定数関数になりません. この差異によって回路下界を証明するという算段です. 詳細は省略します.

3. スイッチング補題の証明

3.1. 証明の方針

$w$-DNF $f$ の$s$-制限$\beta \in \mathcal{R}_s$ が $\mathsf{DT}(f|_\beta)>d$ を満たすとき, $\beta$はbadであると呼びます. badな$s$-制限の集合を$\mathcal{B}$とし, $|\mathcal{B}|$が小さいことを証明していきます. そのために, DNFのbadな制限は簡潔な記述を持つことを証明します.

フォーマルに述べると, サイズの小さいある集合$\Omega$に対して単射$\varphi \colon \mathcal{B} \to \Omega$を構成することで$|\mathcal{B}|\le |\Omega|$を示します. さらに, $|\Omega| \le \left(\frac{10sw}{n}\right)^d\cdot |\mathcal{R}_s|$ となることを示せたとすると, 所望の確率は

$$\begin{align*} \Pr_\beta\left[ \mathsf{DT}(f|_\beta) > d \right] \le \frac{|\mathcal{B}|}{|\mathcal{R}_s|} \le  \frac{|\Omega|}{|\mathcal{R}_s|} \le \left(\frac{10sw}{n}\right)^d. \end{align*}$$

となり, 主張を得ます.

3.2. 準備

$w$-DNF $f$の各項が順序づけられており, $f=T_1 \lor T_2 \lor \dots T_m$とします. さらに, 各項$T_i$に含まれるリテラルも変数の番号によるデフォルトの順序があるとします. 例えば$T_1=x_1\lor \overline{x_3} \lor x_5$ならば$x_1,x_3,x_5$という順があります.

badの$s$-制限$\beta$に対して$f|_\beta$もまた$w$-DNFであり, これを

$$\begin{align*} f|_\beta = T_{i_1} \lor \dots \lor T_{i_\ell} \end{align*}$$
とします. ここで, $\beta$によって$T_i\equiv 1$となる項が存在すると$f|_\beta\equiv 1$となってしまいbadであることに矛盾してしまいます. 同様に「全ての項が0に固定されてしまう」こともありません. 従って上記のような形で$f|_\beta$を表現できます.

図7. canonicalな決定木の構成.

$f|_\beta$の項$T_{i_1},\dots,T_{i_\ell}$の幅がそれぞれ$d_1,\dots,d_\ell$とします. このとき, canonicalな決定木$\mathcal{T}$を以下で定義します: 先頭の項$T_{i_1}$を$d_1$変数の論理関数とみなしたとき, その自明な決定木を$\mathcal{T}_1$とします. $T_{i_1}$は項なので, 充足割り当てはただ一つしか存在しません. 従ってこの決定木$\mathcal{T}_1$はただ一つの$1$の葉を持っています. この唯一の葉を$\mathcal{T}$における$1$の葉とします. 残りの$2^{d_1}-1$個の$0$の葉に対して, これを根として$T_{i_2}, T_{i_3},\dots$の順で同様の操作を続けていきます. ただし, 固定された変数はそれ以降の項でも固定します. 例えば$\mathcal{T}_1$のある葉において$x_1=0$と固定されている場合は, その葉に続けて構成していく$\mathcal{T}_2,\mathcal{T}_3,\dots$においても常に$x_1=0$として扱います. なお, この固定によって途中で$T_{i_j}$の値が0に固定されてしまった場合はそのままスルーして$T_{i_{j+1}}$に移動します. これは, 例えば$T_{i_1},T_{i_2}$での操作によって$x_1$から$x_5$までの変数が全て固定されていたときに$T_{i_3}$に含まれる変数が$x_2,x_3,x_5$であった場合などに起こりえます.

図8. canonicalな決定木上の長いパス$P$.

部分割り当て$\beta$がbadであるため, このように構成されたcanonicalな決定木$\mathcal{T}$の深さは$d$を超えます. 従って根を始点として子に伝っていく長さ$d$のパスが一つ以上存在します. そのようなパスの中で割り当てが辞書順最小のものを$P$とします. ここで, canonicalな決定木はその構成から, 代入される変数の順番は固定長のパスの中ではどのパスを選んでも同じになります (固定の仕方によっては途中で$1$の葉に行き着く可能性もあるので, パス長は固定して考える). 従って長さ$d$のパスが固定する変数はどれも同じ変数を選ぶため, 辞書順最小な割り当てを持つパス$P$が一意に定まります.

このパス$P$が経由する項を順番に$T_{i_1},\dots,T_{i_k}$とします. パス$P$はちょうど$d$個の変数の値を固定するため, 最後の行$T_{i_k}$は部分的に値が固定される可能性があります.

3.3. badな制限のencoding

図9. badな制限の記述

3.2で定義されたパス$P$が経由する項を$T_{i_1},\dots,T_{i_k}$とします. badな$s$-制限$\beta$の部分割り当てを次のように拡張して得られる$(s-d)$-制限を$\gamma$とします: 制限$\beta$からスタートします. まず, 項$T_{i_1}$に対して$T_{i_1}\equiv 1$となる唯一の割り当て ($T_{i_1}$は項なのでそのような割り当ては一意に存在する) を$\beta$に追加して得られる$(s-d_1)$-制限を$\beta_1$とします. 同様の操作を続いて$T_{i_2},T_{i_3},\dots$に適用していき, $d$個の変数を固定した段階で得られる$(s-d)$-制限を$\gamma$とします (ちょうど$d$個の変数を固定するので, 最後の行はいくつかの変数が未固定になりえます).

図10. $\mathsf{info}$の例. 元の項の何番目の変数に何を代入したかという情報を保持している.

$j$回目の繰り返しにおいて$T_{i_j}$の何番目の変数に何を代入したか, という情報を$j=1$から$k$まで記述した情報$\mathsf{info}$と表すことにします.

各行$T_{i_j}$に含まれるリテラルにはデフォルトの順序がついているので, $\mathsf{info}$の情報を見ると$\beta$と$\gamma$の差分がわかります.

$\Omega$を, $\beta$を動かしたときにありうる$(\gamma, \mathsf{info})$全体の集合とし, 単射$\varphi\colon \mathcal{B}\to \Omega$を
$$\begin{align*} \varphi \colon \beta \mapsto (\gamma,\mathsf{info}) \end{align*}$$
とします. この写像が実際に単射となっていることを確認します. つまり, $(\gamma,\mathsf{info})$から元の$s$-制限$\beta$が復元できることを確認します. この復元操作では, $\beta$を知らず$(\gamma,\mathsf{info})$のみを知っている状態なので, canonicalな決定木$\mathcal{T}$や$\beta$によって固定されない項$T_{i_1},T_{i_2},\dots$や辞書順最小のパス$P$は分からないことに注意してください. なお, 関数$f$はわかっているので$f$の情報 ($T_1,\dots,T_m$) も用いてよいです.

3.4. $(f,\gamma,\mathsf{info})$から$\beta$の復元

方針としては, $\gamma$は$\beta$に追加していくつかの変数に代入を施して得られる部分割り当てです. この「追加して固定した変数は何か」がわかれば$\beta$を復元できます. そこで$\gamma$と$\beta$の違いに着目していきます.

では, 両者の差分はどこに現れるでしょうか? $\beta$はbadな割り当てなので, $f|_\beta$の全ての項は未固定もしくは$0$に固定されます. 一方で$\gamma$は$f|_\beta$の項を先頭から順に$1$になるよう固定することで構成されています.

図11. 復元アルゴリズム.

$w$-DNF $f$のcanonicalな決定木を考えます. ここで考える$f$のcanonicalな決定木とは, 項$T_1,T_2,\dots$の順番で部分木を繋げていき, 各部分木では対応する項に含まれる変数をそのデフォルトの順序で固定していくという決定木です. 決定木を$(s-d)$-制限$\gamma$に沿って辿っていきます. 部分木を通過する際にその部分木の葉のラベルが$0$か$1$かで場合分けをします. 

1. 葉のラベルが$0$のとき

そのまま次の部分木に移動して同様に辿っていきます.

2. 葉のラベルが$1$のとき

この部分木において, $\beta$と$\gamma$の差分が現れています. この差分は$\mathsf{info}$によって取得し, 全てのラベル$0$の葉に対して再び辿っていきます. 具体的には, $\mathsf{info}$の先頭の情報 「$j_1$番目の変数に$b_1$を代入, $j_2$番目の変数に$b_2$を代入, ...」に対し, 項$T_i$の$j_1$番目, $j_2$番目, ... の変数への代入操作を$\gamma$から除去します. さらに, $\mathsf{info}$から先頭の情報を削除します. そして, 部分木の$0$の葉を全て列挙し, それぞれの葉について同様に$\gamma$に沿って部分木を辿っていきます. (復元アルゴリズムの効率性は考慮していません).

これを繰り返し, $\gamma$の全ての部分割り当てを追跡したときのパスを考えます. ケース2での列挙により, 多くのパスが列挙されることになりますが, その中で割り当ての辞書順最小のパスを再び先頭から同じ方法で$\gamma$に基づいて辿ることで, $\gamma$で固定したが$\beta$で固定しなかった変数が全てわかり, $\beta$の情報を復元することができます.

3.5. 記述長

最後に, $\gamma,\mathsf{info}$の記述長を考えます. $\gamma$は$s-d$-制限なので, ありうる$\gamma$の総数は$|\mathcal{R}_{s-d}| = \binom{n}{s-d}\cdot 2^{n-s+d}$です. 次にありうる$\mathsf{info}$の総数を考えます. $\mathsf{info}$では「$i$番目の変数に$b_i$を代入する」という情報を$d$個含んでおり, $1\le i \le w$のため, ありうる$\mathsf{info}$の総数は高々$(2w)^d$となります.

一方で, $s$-制限の個数は全部で$\binom{n}{s}\cdot 2^{n-s}$個なので, 求める確率は

$$\begin{align*} \Pr_\alpha[\mathsf{DT}(f|_\alpha)>d] &\le \frac{(2w)^d\cdot \binom{n}{s-d}\cdot 2^{n-s+d}}{\binom{n}{s}\cdot 2^{n-s}} \\ &\le \left(\frac{4w s}{n-s} \right)^d \end{align*}$$

となり, 主張を得ます.

KLダイバージェンスの優モジュラ性と確率集中不等式

「エントロピーは劣モジュラ性をもつ」という事実は界隈の中ではとても有名で, エントロピーを最大化するということはある意味で多様性を大きくするということとみなせることから, この事実は劣モジュラ関数最大化の応用の一つとなりえます (この問題はNP困難ですが). 相互情報量の非負性とみなせるという説明がされることもありますが, 本記事ではこの事実をKLダイバージェンスの優モジュラ性の観点からと捉えます. この観点の利点として, Chernoff boundが導出できます. そもそも相互情報量はKLダイバージェンスの形で表すことができ, KLダイバージェンスは常に非負であることがJensenの不等式から簡単に示せるので, 突き詰めるとJensenにいきつきます. 凸って偉い.

注1. エントロピーはKLダイバージェンスの符号を逆にして定数を足した値なので, エントロピーの劣モジュラ性はKLダイバージェンスの優モジュラ性から直ちに従います. この意味でちょっとだけ一般化していると言えます.

注2. 実は優モジュラ性はChernoff boundの証明においては少しオーバーキルで, 実は優加法性から導出できます.

1. エントロピーと劣モジュラ性

---

定義1.1 (エントロピー).

有限集合$\Omega$上に値をとる確率変数$X$のエントロピー$\mathrm{H}(X)$とは
$$\begin{align*} \mathrm{H}(X) = \sum_{x\in \Omega}\Pr[X=x]\log\frac{1}{\Pr[X=x]} \end{align*}$$
によって定義される値である.

総和の各項$\log\frac{1}{\Pr[X=x]}$は事象“$X=x$"の情報量と呼ばれる値です. logの底は文脈によってまちまちですがここでは自然対数を考えることとします (底を2とするのがスタンダードですが, 文脈によっては自然対数を考えた方が便利なことがあります). 事象の確率が小さいほどその情報量は大きい値になっており, 直感的にはその事象が起きたときのびっくり具合を意味する値になっています. エントロピーとは情報量の期待値として定義されます.

定義1.2 (劣モジュラ性).

有限集合$V$に対し, 部分集合族上の関数 $f\colon 2^V \to \mathbb{R}$ が以下の条件を満たすとき劣モジュラ性をもつという:
$$\begin{align*} {}^{\forall}I,J \subseteq V,\,f(I\cup J)+f(I\cap J) \le f(I) + f(J). \end{align*}$$
上記の不等号を$\ge$に置き換えたときの性質を満たすとき, $f$は優モジュラ性をもつという.

言い換えれば, $-f$が劣モジュラ性をもつならば$f$は優モジュラ性をもつと定義します.

命題1.3 (エントロピーの劣モジュラ性).

自然数$n\in\mathbb{N}$に対し$\Omega^n$上に値をとる確率変数$X=(X_1,\dots,X_n)$を考え, 集合$I \subseteq [n]$に対し$X_I=(X_i)_{i\in I}$を$I$への射影とする. このとき, 関数$I \mapsto \mathrm{H}(X_I)$は劣モジュラ性をもつ.

2. KLダイバージェンスと優モジュラ性

---

有限集合$\Omega$上に値をとる二つの確率変数$X,Y$を考えそれぞれの周辺分布を$\mu_X,\mu_Y$とします. ここで, $\mu_X\colon \Omega\to [0,1]$は関数$\mu_X(x)=\Pr[X=x]$によって定まる関数です. 確率変数$X$の台 (support) を$\mathsf{supp}(X) =  \{x\in \Omega \colon \mu_X(x) > 0 \}$で定めます.

定義2.1 (KLダイバージェンス).

$\mathsf{supp}(X)\subseteq \mathsf{supp}(Y)$を満たす二つの確率変数$X,Y$のKLダイバージェンスとは以下で定義される量である:

$$\begin{align*} \mathrm{KL}(X||Y) &= \sum_{a \in \Omega} \Pr[X=a] \log\frac{\Pr[X=a]}{\Pr[Y=a]} \\ &= \mathbb{E}_{a \sim X}\left[ \log\frac{\mu_X(a)}{\mu_Y(a)} \right] \end{align*}$$
ただし, $0\log 0=0$として扱う.

(分子と分母がどっちかどっちか分からなくなるときがありますが, 私はfrac{}{}と同じ順番と覚えています)

KLダイバージェンスとはそれぞれの確率変数の分布から定まるので, $X$と$Y$が独立かどうかによって値が変化することはありません. エントロピーとKLダイバージェンスの間にはつぎの関係がなりたちます (簡単な計算から確認できます):

命題2.2 (エントロピーとKLダイバージェンス).

確率変数$U$を$\Omega$上の一様分布に従う確率分布とする. $\Omega$上に値をとる任意の確率変数$X$のエントロピー$\mathrm{H}(X)$は,
$$\begin{align*} \mathrm{H}(X) = \mathrm{H}(U) - \mathrm{KL}(X || U). \end{align*}$$

なお, 一様分布ならば$U=a$という事象は全て同じ情報量$\log|\Omega|$を持つので, $\mathrm{H}(U)=\log|\Omega|$です. 従って, エントロピーは一様分布からのKLダイバージェンスの符号を変えて並行移動したものと捉えることができます. ここで符号を変えたことで劣モジュラ性と優モジュラ性が入れ替わります.

命題2.3 (KLダイバージェンスの優モジュラ性).

二つのベクトル値確率変数$X=(X_1,\dots,X_n), Y=(Y_1,\dots,Y_n)$および$I\subseteq [n]$に対し, $\mathrm{KL}(I) \colon 2^{[n]} \to \mathbb{R}$を
$$\begin{align} \mathrm{KL}(I) = \mathrm{KL}(X_I || Y_I) \end{align}$$

と定める. 確率変数$Y_1,\dots,Y_n$が独立ならば, 関数$\mathrm{KL}(\cdot)$は優モジュラ性をもつ.

ここで, 確率変数$Y_1,\dots,Y_n$が独立であるとは, 任意の$y_1,\dots,y_n \in \Omega$に対して
$$\begin{align*} \Pr\left[ {}^\forall i\in[n],\,Y_i = y_i \right] = \prod_{i\in [n]}\Pr[Y_i=y_i] \end{align*}$$
が成り立つことを言います.

$\Omega^n$上の一様分布$U=(U_1,\dots,U_n)$を考えると$U_1,\dots,U_n$は独立かつそれぞれの$U_i$は$\Omega$上一様ランダムです. 従って$Y=U$としてKLダイバージェンスの優モジュラ性(命題2.3)を適用すると, $I \mapsto \mathrm{KL}(X_I || U_I)$は優モジュラ性をもちます. ところで, エントロピーとKLダイバージェンスの関係 (命題2.2) より
$$\begin{align*} \mathrm{H}(X_I) = \mathrm{H}(U_I) - \mathrm{KL}(X_I || U_I) \end{align*}$$
が成りたつため, $I \mapsto \mathrm{H}(X_I)$は劣モジュラ性を満たします (-1倍して並行移動しているだけなので). これは命題1.3を導出します.

ちなみに, 関数$\mathrm{KL}(I)$は単調性をもちます:
$$\begin{align*} {}^{\forall} I \subseteq J\subseteq[n],\, \mathrm{KL}(I) \le \mathrm{KL}(J). \end{align*}$$

この事実は射影関数$(x_j)_{j \in J} \mapsto (x_i)_{i\in I}$に対してKLダイバージェンスのデータ処理不等式を適用することで得られます.

3. KLダイバージェンスの優モジュラ性とChernoff bound

---

実はやることは以前の記事で紹介した, KLダイバージェンスに基づくChernoff boundの証明と全く同じです. 式変形の一部の不等式を優モジュラ性として解釈できることを説明します.

定理3.1 (Chernoff bound).

実数値をとる独立な確率変数$Y_1,\dots,Y_n$に対し, $\mu=\frac{1}{n}\sum_{i\in[n]}Y_i$とすると,
$$\begin{align} & \Pr\left[\frac{1}{n} \sum_{i\in[n]} Y_i \ge \mu + \varepsilon \right] \le \exp\left( - n \mathrm{KL}(\mu+\varepsilon||\mu)\right),\\ & \Pr\left[\frac{1}{n} \sum_{i\in[n]} Y_i \le \mu - \varepsilon \right] \le \exp\left( - n \mathrm{KL}(\mu-\varepsilon||\mu)\right). \end{align}$$

ただし, $p,q\in[0,1]$に対し$\mathrm{KL}(p||q)=\mathrm{KL}(\mathrm{Ber}(p)||\mathrm{Ber}(q)) = p\log\frac{p}{q} + (1-p)\log\frac{1-p}{1-q}$はBernoulli試行のKLダイバージェンスである.

二つの確率変数$X=(X_i)_{i\in[n]}, Y=(Y_i)_{i\in[n]}$に対し, (1)の定まる関数$\mathrm{KL}(I)$を考えます. $Y_1,\dots,Y_n$が独立ならばこの関数は優モジュラ性をもつ, すなわち

$$\begin{align*} {}^{\forall} I,J\subseteq [n],\,\mathrm{KL}(I\cup J) + \mathrm{KL}(I \cap J) \ge \mathrm{KL}(I) + \mathrm{KL}(J) \end{align*}$$
を満たします. 特に$I\cap J=\emptyset$のときは$\mathrm{KL}(I\cup J) \ge \mathrm{KL}(I) + \mathrm{KL}(J)$なので, 特に優加法性

$$\begin{align} \mathrm{KL}([n]) \ge \sum_{i \in [n]} \mathrm{KL}(i) \end{align}$$
を満たします (ここでは$\mathrm{KL}(\{i\})$を$\mathrm{KL}(i)$と略記しています).

定理3.1の証明に戻ります. ここでは(2)式のみを示しますが, (3)式も同様に示せます. 事象$\mathcal{E}$を$\mathcal{E}=\left\{\frac{1}{n}\sum_{i \in [n]} Y_i \geq \mu+\varepsilon\right\}$とし, $X=Y|_E$とします. つまり, $Y|_E$とは, $\mathcal{E}$を満たす$(y_1,\dots,y_n)\in\Omega^n$に対し

$$\begin{align*} \Pr[Y|_\mathcal{E} = (y_1,\dots,y_n)] = \Pr[Y=(y_1,\dots,y_n)|\mathcal{E}] = \frac{\Pr[Y=(y_1,\dots,y_n)]}{\Pr[\mathcal{E}]} \end{align*}$$
によって定まる確率変数です.

$X',Y'$を, 一様ランダムに選ばれた$i\sim[n]$に対し$X'=X_i$, $Y'=Y_i$と定義される確率変数とします. 簡単な計算から$\log\frac{1}{\Pr[E]}=\mathrm{KL}(X||Y)=\mathrm{KL}([n])$が示せます. 実際,
$$\begin{align*} \mathrm{KL}(X||Y) &= \mathbb{E}_{a \sim X} \left[ \log\frac{\Pr[X=a]}{\Pr[Y=a]} \right] \\ &= \mathbb{E}_a \left[ \log\frac{\Pr[Y=a|\mathcal{E}] }{\Pr[Y=a]}  \right] \\ &= \log\frac{1}{\Pr[\mathcal{E}]} \end{align*}$$

従って, (4)より
$$\begin{align*} \log\frac{1}{\Pr[E]} &= \mathrm{KL}(I) \\ &\geq \sum_{i \in [n]} \mathrm{KL}(i) \\ &= n\mathbb{E}_{i\sim[n]}\left[ \mathrm{KL}(Y_i||X_i)\right] \\ &\geq n D(Y'||X'). \end{align*}$$
ここで, 以前の記事の議論より$D(Y'||X')\geq \mathrm{KL}(\mu+t||\mu)$となり, (2)式を得ます.

4. むすびに

---

KLダイバージェンスの優モジュラ性からエントロピーの劣モジュラ性とChernoff boundが導出できることを解説しました. KLダイバージェンスの優モジュラ性は条件付きKLダイバージェンスを考えることによって証明できますが, 今回の記事では省いています.

KLダイバージェンスの一般化としてf-ダイバージェンスという概念が知られていますが, 命題2.3が成り立つようなf-ダイバージェンスを優モジュラf-ダイバージェンスと言い, これに基づいた集中不等式が証明されています (cf. [Masiha, Gohari, Yassaee, 2023]).

離散凸の文脈では劣モジュラ関数はある意味で凸な関数と見做されているため, この観点でいうとKLダイバージェンスは凹関数となります. 一方でKLダイバージェンス$\mathrm{KL}(\mu || \nu)$を二つの分布を受け取って実数値を返す関数とみなすと, $\mathrm{KL}\colon \Delta^2\to\mathbb{R}$ となります ($\Delta$は確率単体). このとき$\mathrm{KL}(\cdot)$は凸関数となります. KLの凸性はものすごく重要です.

付録. 優モジュラ性の証明

---

ここではKLダイバージェンスの優モジュラ性 (命題2.3) を証明します. 準備として条件付きKLダイバージェンスの概念を導入します.

定義A.1 (条件付きKLダイバージェンス)

二つの確率変数のペア$(X_1,X_2), (Y_1,Y_2)$に対し, 条件付きKLダイバージェンスを以下で定義する:
$$\begin{align*} \mathrm{KL}(X_1|X_2||Y_1||Y_2) = \mathbb{E}_{x\sim X_2}\left[ \mathrm{KL}(X_1|_{X_2=x} || Y_1|_{Y_2=x}) \right]. \end{align*}$$

条件付きKLダイバージェンスの重要な二つの性質を導入します.

補題A.2 (Chain rule).

$$\begin{align*} \mathrm{KL}((X_1,X_2) || (Y_1,Y_2)) = \mathrm{KL}(X_2||Y_2) + \mathrm{KL}(X_1|X_2 || Y_1|Y_2) \end{align*}$$

証明.

気合いで計算して証明します. $\mu,\nu$をそれぞれ$(X_1,X_2)$, $(Y_1,Y_2)$の分布とし, $\mu_i,\nu_i$をそれぞれ$X_i,Y_i$の周辺分布とします. このとき

$$\begin{align*} &\mathrm{KL}((X_1,X_2)||(Y_1,Y_2)) - \mathrm{KL}(X_2||Y_2) \\ &= \mathbb{E}_{(a,b)\sim\mu}\left[\log\frac{\mu(a,b)}{\nu(a,b)}\right] - \mathbb{E}_{b\sim\mu_2}\left[\log\frac{\mu_2(b)}{\nu_2(b)}\right] \\ &= \mathbb{E}_{(a,b)\sim\mu}\left[\log\frac{\mu(a,b)}{\nu(a,b)}\right] - \mathbb{E}_{(a,b)\sim\mu}\left[\log\frac{\mu_2(b)}{\nu_2(b)}\right] \\ &= \mathbb{E}_{(a,b)\sim \mu}\left[ \log\frac{\mu(a,b)/\mu_2(b)}{\nu(a,b)/\nu_2(b)}\right] \\ &= \mathbb{E}_{(a,b)\sim \mu} \left[\log\frac{\Pr[X_1=a|X_2=b]}{\Pr[Y_1=a|Y_2=b]}\right] \\ &=\mathbb{E}_{b\sim X_2}\left[\mathbb{E}_{a\sim X_1}\left[ \log\frac{\Pr[X_1=a|X_2=b]}{\Pr[Y_1=a|Y_2=b]} \middle| X_2=b\right]\right] \\ &= \mathrm{KL}(X_1|X_2||Y_1||Y_2). \end{align*}$$

(証明終).

補題A.3 (conditioning increases KL).

二つの確率変数$Y_1$と$Y_2$が独立ならば

$$\begin{align*} \mathrm{KL}(X_1|X_2||Y_1|Y_2)\geq \mathrm{KL}(X_1||Y_1). \end{align*}$$

証明.

KLダイバージェンスを関数$\mathrm{KL}\colon \Delta^2\to \mathbb{R}$とみなしたとき, 凸性を持つことから, Jensenの不等式より

$$\begin{align*} \mathrm{KL}(X_1|X_2||Y_1|Y_2)&=\mathbb{E}_{x\sim X_2}[\mathrm{KL}(X_1|_{X_2=x}||Y_1|_{Y_2=x})] \\ &\geq \mathrm{KL}(\mathbb{E}_x[X_1|X_2=x]||\mathbb{E}_x[Y_1|Y_2=x]) & & \text{(Jensen)}\\ &=\mathrm{KL}(X_1||Y_1) \end{align*}$$

なお, 最後の等号において$Y_1$と$Y_2$の独立性を使っています.

(証明終)

実は, 二つの確率変数$X_1,X_2$の相互情報量を$I(X_1;X_2)$とすると, $\mathrm{KL}(X_1|X_2||Y_1|Y_2) - \mathrm{KL}(X_1||Y_1) = I(X_1;X_2)$が成り立ちます (計算で確認できます). 相互情報量$I(X_1;X_2)$とは,
$$\begin{align*} I(X_1;X_2) = \mathrm{KL}(\mu||\mu_1 \otimes \mu_2) \end{align*}$$
で定義される値です. つまり$(X_1,X_2)$がどれだけ直積分布から離れているかを測る量であり, $\mathrm{KL}$の非負性から常に非負です.

以上で優モジュラ性の証明の準備がおわりました.

命題2.3の証明.

任意の$I,J\subseteq[n]$に対し, chain rule (補題A.2) より

$$\begin{align} \mathrm{KL}(I\cup J) - \mathrm{KL}(I) = \mathrm{KL}(X_{I\cup J}|X_I || Y_{I\cup J}|Y_I) = \mathrm{KL}(X_{J\setminus I}|X_I || Y_{J\setminus I}|Y_I) \end{align}$$

最後の等号では, $X_I$が与えられたとき, $X_{I\cup J}$のランダムネスは$X_{J\setminus I}$にあることを用いています. 同様に

$$\begin{align} \mathrm{KL}(J)-\mathrm{KL}(I\cap J) = \mathrm{KL}(X_J|X_{I\cap J}||Y_J|Y_{I\cap J})=\mathrm{KL}(X_{J\setminus I}|X_{I\cap J}||Y_{J\setminus I}|Y_{I\cap J}). \end{align}$$
補題A.3より, $(5)\ge (6)$となるので主張を得ます.