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)$となるので主張を得ます.