相互情報量(mutual information)とは、離散的な確率変数 $X,Y$ について、組 $(X,Y)$ の分布と周辺分布の積との Kullback–Leibler ダイバージェンス $I(X;Y)=D(p_{XY}\|p_X\otimes p_Y)$ で定まる量で、一方を知ることで他方の不確かさが平均してどれだけ減るかを測る。値が有限個なら $I(X;Y)=H(X)-H(X\mid Y)=H(X)+H(Y)-H(X,Y)$ で対称であり、$0\le I(X;Y)\le\min\{H(X),H(Y)\}$、$0$ になるのは独立のときに限る。Markov 連鎖 $X\to Y\to Z$ では $I(X;Z)\le I(X;Y)$(データ処理不等式)が成り立ち、通信路を固定すると入力の分布について凹で、その最大値が通信路容量である。
前提知識: エントロピー, Kullback–Leiblerダイバージェンス, 独立性(確率論)
さいころの目 $X$ を知りたいとき、「偶数か奇数か」という答え $Y$ を教えてもらうと、残る可能性は 6 通りから 3 通りに減る。不確かさの減り方を対数で測ると $\log6-\log3=\log2$、すなわち 1 bit であり、これが $X$ と $Y$ の 相互情報量 である。相互情報量 $I(X;Y)$ は、一方を知ることで他方の不確かさが平均してどれだけ減るか、言い換えれば 2 つの確率変数がどれだけの情報を共有しているかを測る量である。$X,Y$ が独立なら $0$、一方が他方で決まるなら決まる側のエントロピーに等しい。雑音のある通信路でどれだけ送れるかという問いの答え(通信路容量)は、相互情報量の最大値で与えられる。
この記事では、相互情報量を Kullback–Leibler ダイバージェンスとして定義し、エントロピーによる表示、独立との同値、ダイバージェンスの平均としての表示と凹凸性、連鎖律、データ処理不等式を証明する。最後に通信路容量を述べ、条件をつけると相互情報量が増えることもある、といった誤りやすい点を反例で確かめる。
以下、確率変数は有限集合または可算集合に値をとり、$\log$ は自然対数、$0\log0:=0$ とする。$p(x):=P(X=x)$、$p(x,y):=P(X=x,Y=y)$ などと書き、$p(x)>0$ のとき $p(y\mid x):=p(x,y)/p(x)$ とする。$X=x$ のもとでの $Y$ の条件付き分布 $(p(y\mid x))_y$ を $p_{Y\mid x}$ と書く。分布の Kullback–Leibler ダイバージェンス $D(\cdot\|\cdot)$ は Kullback–Leiblerダイバージェンス の定義のとおりとする。
$X,Y$ の 相互情報量(mutual information)を
$$
I(X;Y):=D\bigl(p_{XY}\,\big\|\,p_X\otimes p_Y\bigr)=\sum_{(x,y):\,p(x,y)>0}p(x,y)\log\frac{p(x,y)}{p(x)p(y)}\in[0,\infty]
$$
で定める。ここで $p_{XY}$ は組 $(X,Y)$ の分布、$p_X\otimes p_Y$ は $(x,y)\mapsto p(x)p(y)$ で定まる分布である。bit 単位の値は $I(X;Y)/\log2$ である。
$p(x,y)>0$ なら $p(x)p(y)>0$ なので、$D$ の定義の「$\infty$ とする場合」は起こらず、上の和の形になる。値が $0$ 以上であることは Kullback–Leiblerダイバージェンス の定理「非負性(Gibbs の不等式)」による。組の分布 $p_{XY}$ と、同じ周辺分布をもつ独立な場合の分布 $p_X\otimes p_Y$ との違いを測るので、相互情報量は「独立からのずれ」の大きさである。値が有限個なら、エントロピー でエントロピーの式により定めた $I(X;Y)$ と一致する(thm-mi-basic の 1)。
使える条件:
$H(X)$、$H(X,Y)$、$H(Y\mid X)$ は エントロピー の定義「エントロピー」「同時・条件付きエントロピーと相互情報量」のとおりとする($H(Y\mid X)=\sum_{x:\,p(x)>0}p(x)H(p_{Y\mid x})$)。
$X,Y$ を有限集合に値をとる確率変数とする。
1。 $p(x,y)>0$ の項について $\log\frac{p(x,y)}{p(x)p(y)}=-\log p(x)-\log p(y)+\log p(x,y)$ であり、これに $p(x,y)$ を掛けて足す(有限和)。$\sum_{x,y}p(x,y)(-\log p(x))=H(X)$ などにより $I(X;Y)=H(X)+H(Y)-H(X,Y)$ である。エントロピー の定理「連鎖律と劣加法性」の 1(連鎖律)$H(X,Y)=H(Y)+H(X\mid Y)=H(X)+H(Y\mid X)$ を代入すると残りの 2 式を得る。最初の式は $X$ と $Y$ について対称である。
2。 $I(X;Y)=D(p_{XY}\|p_X\otimes p_Y)$ と Gibbs の不等式の等号条件により、$I(X;Y)=0$ は $p(x,y)=p(x)p(y)$ がすべての $(x,y)$ で成り立つこと、すなわち独立と同値である。この議論は和が有限であることを使わない。
3。 1 により $H(X)-I(X;Y)=H(X\mid Y)=\sum_{y:\,p(y)>0}p(y)H(p_{X\mid y})\ge0$ である。等号は、$p(y)>0$ となるすべての $y$ で $H(p_{X\mid y})=0$、すなわち(エントロピー の定理「エントロピーの範囲」の左の等号の条件により)$p_{X\mid y}$ が 1 点に集中するときに限る。$H(Y)$ についても同様である。$Y=X$ なら $p_{X\mid x}$ は $x$ に集中するので $I(X;X)=H(X)$ である。$\square$
1 の式は、$H(X,Y)$ を 3 つの部分 $H(X\mid Y)$、$I(X;Y)$、$H(Y\mid X)$ に分けたものと読める(Mac03 §8.1、式 (8.8)(p. 139)と図 8.1(p. 140))。
| 量 | 意味 | 式 |
|---|---|---|
| $H(X,Y)$ | 組の不確かさ | $H(X\mid Y)+I(X;Y)+H(Y\mid X)$ |
| $H(X)$ | $X$ の不確かさ | $H(X\mid Y)+I(X;Y)$ |
| $H(X\mid Y)$ | $Y$ を知っても残る $X$ の不確かさ | $H(X)-I(X;Y)$ |
| $I(X;Y)$ | 共有される情報 | $H(X)+H(Y)-H(X,Y)$ |
$X$ を公平なさいころの目、$Y$ を $X$ が偶数なら $0$、奇数なら $1$ とする。$Y$ は $X$ で決まるので $H(Y\mid X)=0$、$I(X;Y)=H(Y)=\log2$(1 bit)である。$X$ の側から見ると $H(X)=\log6$、$Y=y$ のもとで $X$ は 3 個の値に一様なので $H(X\mid Y)=\log3$ で、$\log6-\log3=\log2$ と一致する。$X$ は $Y$ で決まらないので、thm-mi-basic の 3 のとおり $I(X;Y)< H(X)$ である。
$X,Y\in\{0,1\}$ で $p(0,0)=\frac12$、$p(0,1)=\frac14$、$p(1,0)=0$、$p(1,1)=\frac14$ とする。周辺分布は $p_X=(\frac34,\frac14)$、$p_Y=(\frac12,\frac12)$ で、bit 単位で $H(X)\approx0.811278$、$H(Y)=1$、$H(X,Y)=1.5$ なので、$I(X;Y)\approx0.311278$ bit である。定義の和で直接計算しても $\frac12\log_2\frac{1/2}{3/8}+\frac14\log_2\frac{1/4}{3/8}+\frac14\log_2\frac{1/4}{1/8}\approx0.311278$ になる。
$0\le\varepsilon\le1$ とし、$X\in\{0,1\}$ を $P(X=1)=a$ で選び、$Y$ を確率 $1-\varepsilon$ で $X$、確率 $\varepsilon$ で $1-X$ とする。$h(t):=-t\log t-(1-t)\log(1-t)$ とおくと、$X=x$ のもとで $Y$ の分布は $(1-\varepsilon,\varepsilon)$ の並べ替えなので $H(Y\mid X)=h(\varepsilon)$ で、$P(Y=1)=a(1-\varepsilon)+(1-a)\varepsilon$ だから
$$
I(X;Y)=h\bigl(a(1-\varepsilon)+(1-a)\varepsilon\bigr)-h(\varepsilon)
$$
である。$\varepsilon=0.1$ では、$a=0.2$ で $h(0.26)-h(0.1)\approx0.247974$ nat、$a=\frac12$ で $\log2-h(0.1)\approx0.368064$ nat である。
以下この節では $\mathcal X,\mathcal Y$ を有限集合とし、$W(y\mid x)\ge0$、$\sum_yW(y\mid x)=1$(各 $x\in\mathcal X$)を満たす $W$(通信路)を固定する。$\mathcal X$ 上の分布 $p$ に対し、$P(X=x,Y=y)=p(x)W(y\mid x)$ となる $(X,Y)$ の相互情報量を $I(p,W)$ と書き、出力の分布を $(pW)(y):=\sum_xp(x)W(y\mid x)$、$W(\cdot\mid x)$ を $W_x$ と書く。$p(x)>0$ なら $p_{Y\mid x}=W_x$、$p_Y=pW$ である。
$\mathcal Y$ 上の任意の確率分布 $r$ について
$$
\sum_{x:\,p(x)>0}p(x)\,D(W_x\|r)=I(p,W)+D(pW\|r)
$$
である(両辺は $[0,\infty]$ の値)。とくに $I(p,W)=\sum_{x:\,p(x)>0}p(x)D(W_x\|pW)$ であり、$I(p,W)$ は左辺を $r$ について最小にした値で、最小は $r=pW$ でだけ達成される。
$(pW)(y)>0=r(y)$ となる $y$ があれば、$p(x)W(y\mid x)>0$ となる $x$ があり、$D(W_x\|r)=\infty$ なので左辺は $\infty$、右辺も $D(pW\|r)=\infty$ により $\infty$ である。そうでないとき、$p(x)W(y\mid x)>0$ なら $(pW)(y)>0$、$r(y)>0$ で
$$
\log\frac{W(y\mid x)}{r(y)}=\log\frac{p(x)W(y\mid x)}{p(x)\,(pW)(y)}+\log\frac{(pW)(y)}{r(y)}
$$
である。$p(x)W(y\mid x)$ を掛けて足す(有限和)と、左辺は $\sum_xp(x)D(W_x\|r)$、右辺の第 1 項は $I(p,W)$、第 2 項は $y$ ごとにまとめて $D(pW\|r)$ になる。$r=pW$ とおけば第 2 の主張を得る。$D(pW\|r)\ge0$ で、等号は $r=pW$ のときに限る(Gibbs の不等式)ので最後の主張を得る。$\square$
$D(W_x\|pW)$ は、入力 $x$ を送ったときの出力の分布が、平均の出力の分布からどれだけずれるかを測る。相互情報量はそのずれの平均である。
1。 $\lambda\in\{0,1\}$ なら等号なので $0< \lambda< 1$ とし、$p:=\lambda p_1+(1-\lambda)p_2$、$r:=pW$ とおく。$p_1(x)>0$ または $p_2(x)>0$ なら $p(x)>0$ で、$W(y\mid x)>0$ なら $r(y)\ge p(x)W(y\mid x)>0$ なので $D(W_x\|r)< \infty$ である。thm-mi-average を $p$ と $r=pW$ に、また $p_1,p_2$ と同じ $r$ に使うと
$$
I(p,W)=\sum_xp(x)D(W_x\|r)=\lambda\sum_xp_1(x)D(W_x\|r)+(1-\lambda)\sum_xp_2(x)D(W_x\|r)\ge\lambda I(p_1,W)+(1-\lambda)I(p_2,W)
$$
である(和は $p_1(x)>0$ または $p_2(x)>0$ の $x$ にわたる有限和。最後の不等号は $\sum_xp_j(x)D(W_x\|r)=I(p_j,W)+D(p_jW\|r)\ge I(p_j,W)$)。
2。 $P_W(x,y):=p(x)W(y\mid x)$、$Q_W(x,y):=p(x)(pW)(y)$ とおくと $I(p,W)=D(P_W\|Q_W)$ であり、$P_W$ と $Q_W$ はどちらも $W$ について 1 次式なので、$W=\lambda W_1+(1-\lambda)W_2$ のとき $P_W=\lambda P_{W_1}+(1-\lambda)P_{W_2}$、$Q_W=\lambda Q_{W_1}+(1-\lambda)Q_{W_2}$ である。Kullback–Leiblerダイバージェンス の定理「同時凸性」から主張を得る。$\square$
この節の確率変数はすべて有限集合に値をとる。
$p(z)>0$ となる $z$ について、条件付き確率 $P(\cdot\mid Z=z)$ のもとで計算した $X,Y$ の相互情報量を $I(X;Y\mid Z=z)$ とし、
$$
I(X;Y\mid Z):=\sum_{z:\,p(z)>0}p(z)\,I(X;Y\mid Z=z)
$$
を $Z$ が与えられたときの $X,Y$ の 条件付き相互情報量 という。
$P(\cdot\mid Z=z)$ のもとでの $X$ の条件付きエントロピーを平均すると、thm-mi-basic の 1 を各 $z$ で使って $I(X;Y\mid Z)=H(X\mid Z)-H(X\mid Y,Z)$ となる。ここで $H(X\mid Y,Z)$ は組 $(Y,Z)$ が与えられたときの条件付きエントロピーである($P(\cdot\mid Z=z)$ のもとで $Y=y$ を条件にした $X$ の分布は、$P$ のもとで $(Y,Z)=(y,z)$ を条件にした分布と同じであり、$\sum_zp(z)\sum_yp(y\mid z)H(p_{X\mid(y,z)})=H(X\mid Y,Z)$)。
$I\bigl(X;(Y,Z)\bigr)=I(X;Z)+I(X;Y\mid Z)$ である。
thm-mi-basic の 1 を $X$ と $(Y,Z)$、$X$ と $Z$ に使うと $I(X;(Y,Z))=H(X)-H(X\mid Y,Z)$、$I(X;Z)=H(X)-H(X\mid Z)$ である。上の式 $I(X;Y\mid Z)=H(X\mid Z)-H(X\mid Y,Z)$ を足せばよい。$\square$
$X,Y,Z$ が この順に Markov 連鎖をなす($X\to Y\to Z$ と書く)とは、$p(y)>0$ となるすべての $y$ と、すべての $x,z$ について
$$
P(X=x,Z=z\mid Y=y)=P(X=x\mid Y=y)\,P(Z=z\mid Y=y)
$$
が成り立つこと、すなわち $Y$ が与えられたとき $X$ と $Z$ が条件付き独立であることをいう。
thm-mi-basic の 2 を各 $P(\cdot\mid Y=y)$ に使うと、$X\to Y\to Z$ は $I(X;Z\mid Y)=0$ と同値である。定義は $X$ と $Z$ について対称なので、$X\to Y\to Z$ なら $Z\to Y\to X$ でもある。$Z=g(Y)$ なら、$Y=y$ のもとで $Z$ は定数 $g(y)$ なので $X\to Y\to Z$ である。
$X\to Y\to Z$ なら $I(X;Z)\le I(X;Y)$ であり、等号は $I(X;Y\mid Z)=0$ のときに限る。
$(Y,Z)$ と $(Z,Y)$ は値が 1 対 1 に対応するので、$I(X;(Y,Z))=I(X;(Z,Y))$ である(定義の和が並べ替わるだけ)。thm-mi-chain を 2 通りに使うと
$$
I(X;Z)+I(X;Y\mid Z)=I\bigl(X;(Y,Z)\bigr)=I(X;Y)+I(X;Z\mid Y)=I(X;Y)
$$
である(最後は Markov 連鎖の仮定 $I(X;Z\mid Y)=0$)。$I(X;Y\mid Z)\ge0$ なので $I(X;Z)\le I(X;Y)$ で、等号は $I(X;Y\mid Z)=0$ のときに限る。$\square$
関数 $f,g$ について $I\bigl(X;g(Y)\bigr)\le I(X;Y)$、$I\bigl(f(X);g(Y)\bigr)\le I(X;Y)$ である。
$X\to Y\to g(Y)$ なので、thm-mi-dpi から 1 つ目を得る。2 つ目は、1 つ目と対称性 $I(U;V)=I(V;U)$ を使って $I(f(X);g(Y))\le I(X;g(Y))\le I(X;Y)$ とする(はじめの不等号は 1 つ目を $(g(Y),X)$ の組に使ったもの)。$\square$
観測 $Y$ を加工して $Z$ を作っても、元の $X$ について $Y$ 以上の情報は得られない、というのがデータ処理不等式の意味である(Mac03 §8.3 の演習 8.9(p. 141)、解答は p. 144)。Kullback–Leibler ダイバージェンスの側のデータ処理不等式(Kullback–Leiblerダイバージェンス の定理「データ処理不等式」)は、2 つの分布を同じ写像で粗く見ると見分けにくくなることを述べ、こちらと対をなす。
通信路 $W$ の 通信路容量 を $C(W):=\max_pI(p,W)$ で定める($p$ は $\mathcal X$ 上の確率分布全体を動く。Mac03 式 (9.10)(p. 150))。$I(p,W)$ は $p$ の連続関数で、確率分布の全体は有界閉集合なので最大値がある。cor-mi-concave の 1 により $p\mapsto I(p,W)$ は凹なので、局所的な最大は全体の最大である。ex-mi-bsc の 2 値対称通信路では、$h(t)\le\log2$ で等号は $t=\frac12$ のときなので $C=\log2-h(\varepsilon)$($a=\frac12$ で達成)である。
無記憶な通信路を $n$ 回使うとき、容量 $C$ 未満の速さならいくらでも小さな誤りの確率で送れ(Shannon の通信路符号化定理。Mac03 §9.6(p. 152)の言明と §10.1(p. 162)以降の証明。この記事では証明しない)、$C$ を超える速さでは誤りの確率は $0$ に近づかない(逆の定理。情報理論 で Fano の不等式とデータ処理の考え方を使って証明している)。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| Markov 連鎖 $X\to Y\to Z$(thm-mi-dpi) | $X,Y$ を独立な公平な硬貨、$Z:=X$ | $I(X;Z)=\log2> 0=I(X;Y)$ |
| 独立(thm-mi-basic の 2 の等号) | 公平な硬貨 $X$ と $Y:=X$ | $I(X;Y)=\log2> 0$ |
| $X$ が $Y$ で決まる(thm-mi-basic の 3 の等号) | ex-mi-die の $X$(目)と $Y$(偶奇) | $I(X;Y)=\log2< \log6=H(X)$ |
| 値が有限個(エントロピーによる表示) | $H(X)=\infty$ となる $X$ と、$X$ と独立で同じ分布の $Y$ | $I(X;Y)=0$ だが、$H(X)+H(Y)-H(X,Y)$ は $\infty+\infty-\infty$ で定まらない |
1 行目:$Y=y$ のもとで $X$ は公平な硬貨のままで、$Z=X$ なので $X$ と $Z$ は条件付き独立でない($P(X=0,Z=1\mid Y=y)=0\ne\frac14$)。$I(X;Z)=I(X;X)=H(X)=\log2$(thm-mi-basic の 3)、$I(X;Y)=0$(独立)。$Z$ は $Y$ を経ずに $X$ から作られている。
2 行目:thm-mi-basic の 3 により $I(X;X)=H(X)=\log2$。
3 行目:ex-mi-die の計算のとおり。$Y=0$ のもとで $X$ は $2,4,6$ に一様で、1 点に集中しない。
4 行目:$H(X)=\infty$ となる分布は エントロピー の反例の表 1 行目にある。独立なので $p_{XY}=p_X\otimes p_Y$ で $I(X;Y)=0$ である。一方 $H(X,Y)\ge H(X)=\infty$(組の分布は $(x,y)\mapsto p(x)p(y)$ で、各項 $-p(x)p(y)\log(p(x)p(y))\ge-p(x)p(y)\log p(x)$ を $y$ について足すと $-p(x)\log p(x)$)なので、3 つのエントロピーがどれも $\infty$ である。def-mi-main の定義は値が可算個でも意味をもつ。$\square$
以下、$X,Y$ を独立な公平な硬貨(値 $0,1$)とし、$Z:=X+Y\bmod2$ とする。$(X,Z)$ も $(Y,Z)$ も $\{0,1\}^2$ 上で一様なので、$X,Y,Z$ のどの 2 つも独立である。
| 誤り | 正しくは | 例 |
|---|---|---|
| 条件をつけると相互情報量は減る($I(X;Y\mid Z)\le I(X;Y)$) | 減るとも増えるとも限らない。減るのは Markov 連鎖などの場合 | $I(X;Y)=0$ だが $I(X;Y\mid Z)=\log2$ |
| 対ごとに独立なら、2 つ合わせても情報はない | $I(Z;X)=I(Z;Y)=0$ でも $I(Z;(X,Y))$ は正になりうる | $I(Z;(X,Y))=H(Z)=\log2$ |
| 無相関なら相互情報量は $0$ | 相互情報量が $0$ なのは独立のときに限る | $X$ を $\{-1,0,1\}$ 上の一様分布、$Y:=X^2$ とすると共分散は $0$ だが $I(X;Y)=H(Y)=h(\frac13)\approx0.636514$ nat |
| $I(X;Y)$ も Kullback–Leibler ダイバージェンスと同じく非対称 | $I(X;Y)=I(Y;X)$ | thm-mi-basic の 1 |
1 行目:$Z=z$ のもとで $X$ は一様で $Y=X+z\bmod2$ は $X$ で決まるので、$I(X;Y\mid Z=z)=H(X\mid Z=z)=\log2$ である。2 行目:$Z$ は $(X,Y)$ で決まるので thm-mi-basic の 3 により $I(Z;(X,Y))=H(Z)$。3 行目:$E[X]=E[X^3]=0$ なので $\mathrm{Cov}(X,Y)=E[X^3]-E[X]E[X^2]=0$、$Y$ は $X$ で決まり $P(Y=1)=\frac23$ である。2 行目の例は、独立性(確率論) の例「反例:対ごとに独立だが互いに独立でない事象」と同じ形である。
$(X,Y)$ を、平均 $0$・分散 $1$・相関係数 $\rho$($|\rho|< 1$)の 2 次元正規分布(多変量正規分布)とすると
$$
I(X;Y)=-\frac12\log(1-\rho^2)
$$
である。$\rho=0$ で $0$、$|\rho|\to1$ で $\infty$ に発散し、$\rho=0.6$ では約 $0.223144$ nat である。
同時密度は $f(x,y)=\frac1{2\pi\sqrt{1-\rho^2}}\exp\bigl(-\frac{x^2-2\rho xy+y^2}{2(1-\rho^2)}\bigr)$、周辺密度の積は $\frac1{2\pi}\exp\bigl(-\frac{x^2+y^2}2\bigr)$ なので、$\log\frac{f(x,y)}{f_X(x)f_Y(y)}=-\frac12\log(1-\rho^2)-\frac{x^2-2\rho xy+y^2}{2(1-\rho^2)}+\frac{x^2+y^2}2$ である。$E[X^2]=E[Y^2]=1$、$E[XY]=\rho$ より $E[X^2-2\rho XY+Y^2]=2(1-\rho^2)$ なので、期待値は $-\frac12\log(1-\rho^2)-1+1$ である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する