東京大学 工学系研究科 電気系工学専攻 2017年度サンプル 問題3 情報理論

标签：

• 东京大学
• 二元对称信道
• 条件熵
• 互信息
• KL 散度
• 信道容量

Author

祭音Myyura (Based on donguri0912's answer refined with GPT 6 Astra)

Description

入力信号を $A=\{0,1\}$、出力信号を $B=\{0,1\}$ とする二元対称通信路 $\Gamma$ を考える。入力の確率分布は $P_A(0)=p$、$P_A(1)=1-p$ であり、どちらの値を入力しても確率 $q$ で信号が反転する。対数の底はすべて $2$ とする。

(1) $\Gamma$ の通信路線図を示せ。

(2) 出力の確率分布 $P_B$ を $p,q$ で表せ。

(3) エントロピー $H(B)$ と条件付きエントロピー $H(A\mid B)$ を $p,q$ で表せ。

(4) $(p,q)=(0.25,0)$ と $(0.25,0.25)$ のそれぞれについて $H(A\mid B)$ と相互情報量 $I(A;B)$ を求めよ。両者を比較し、この通信路における $I(A;B)$ の意味を述べよ。

次に、無記憶通信路 $\Gamma_1$ と $\Gamma_2$ をカスケード接続する。$\Gamma_1$ の入力を $X=\{x_1,x_2\}$、出力を $Y=\{y_1,y_2\}$ とし、$\Gamma_2$ の入力を $Y$、出力を $Z=\{z_1,z_2\}$ とする。同時確率を $P(x,y)$、条件付き確率を $P(x\mid y)$ と記す。

(5) 次式が成り立つことを示せ。

$$H(X\mid Z)-H(X\mid Y) =\sum_{i=1}^{2}\sum_{j=1}^{2}P(y_i,z_j) \sum_{k=1}^{2}P(x_k\mid y_i) \left\{\log P(x_k\mid y_i)-\log P(x_k\mid z_j)\right\}.$$

(6) $H(X\mid Z)\ge H(X\mid Y)$ を示し、これに基づいて相互情報量 $I(X;Z)$ の意味を述べよ。

(7) $P_X(x_1)=s$、$P_X(x_2)=1-s$ とし、$\Gamma_1,\Gamma_2$ のどちらも確率 $r$ で信号が反転する通信路とする。全体の通信路容量 $C_{12}$ を最大にする $r$ と、そのときの $C_{12}$ を求めよ。

题目描述

考虑输入、输出均为 $\{0,1\}$ 的二元对称信道 $\Gamma$。输入为 $0$、$1$ 的概率分别为 $p$、$1-p$，任一输入都以概率 $q$ 翻转。所有对数以 $2$ 为底。

(1) 画出信道转移图。

(2) 用 $p,q$ 表示输出分布 $P_B$。

(3) 用 $p,q$ 表示 $H(B)$ 和 $H(A\mid B)$。

(4) 分别计算 $(p,q)=(0.25,0)$ 与 $(0.25,0.25)$ 时的 $H(A\mid B)$ 和 $I(A;B)$，比较结果并解释互信息的含义。

再考虑两个无记忆信道的串联 $X\to Y\to Z$，其中 $X=\{x_1,x_2\}$、$Y=\{y_1,y_2\}$、$Z=\{z_1,z_2\}$。$P(x,y)$ 表示联合概率，$P(x\mid y)$ 表示条件概率。

(5) 证明上述日文题面中给出的条件熵之差公式。

(6) 证明 $H(X\mid Z)\ge H(X\mid Y)$，并据此说明 $I(X;Z)$ 的意义。

(7) 令 $P_X(x_1)=s$、$P_X(x_2)=1-s$，两个信道均以概率 $r$ 翻转信号。求使串联信道容量 $C_{12}$ 最大的 $r$ 及最大容量。

Kai

以下、二項エントロピー関数を

$$h(u)=-u\log_2u-(1-u)\log_2(1-u),\qquad h(0)=h(1)=0$$

と定義する。エントロピーの単位は bit である。

(1)

同じ値への遷移確率は $1-q$、反転する遷移確率は $q$ である。

(2)

全確率の公式より、

$$\boxed{P_B(0)=p(1-q)+(1-p)q=p+q-2pq},$$

$$\boxed{P_B(1)=pq+(1-p)(1-q)=1-p-q+2pq}.$$

(3)

$b=p+q-2pq$ とおく。各入力に対する出力の条件付きエントロピーは $h(q)$ なので、

$$H(A,B)=H(A)+H(B\mid A)=h(p)+h(q).$$

したがって、

$$\boxed{H(B)=h(b)},\qquad \boxed{H(A\mid B)=h(p)+h(q)-h(b)}.$$

(4)

相互情報量は

$$I(A;B)=H(B)-H(B\mid A)=h(p+q-2pq)-h(q)$$

である。よって次の値を得る。

$(p,q)$	$H(A\mid B)$ [bit]	$I(A;B)$ [bit]
$(1/4,0)$	$0$	$h(1/4)\simeq0.811278$
$(1/4,1/4)$	$2h(1/4)-h(3/8)\simeq0.668122$	$h(3/8)-h(1/4)\simeq0.143156$

$I(A;B)=H(A)-H(A\mid B)$ は、出力の観測によって解消される入力の不確かさを表す。$q=0$ なら入力を完全に復元できるが、$q=1/4$ では反転によって入力の不確かさが残り、得られる情報量が小さくなる。

(5)

カスケード接続より $X\to Y\to Z$ はマルコフ連鎖であり、

$$P(x,y,z)=P(y,z)P(x\mid y)$$

が成り立つ。したがって、求める式の右辺は

$$\begin{aligned} &\sum_{x,y,z}P(x,y,z)\log P(x\mid y) -\sum_{x,y,z}P(x,y,z)\log P(x\mid z)\\ &=\sum_{x,y}P(x,y)\log P(x\mid y) -\sum_{x,z}P(x,z)\log P(x\mid z)\\ &=-H(X\mid Y)+H(X\mid Z). \end{aligned}$$

これが示すべき等式である。確率が $0$ の項は極限によって $0$ と扱う。

(6)

(5) の内側の和は KL ダイバージェンスであるから、

$$H(X\mid Z)-H(X\mid Y) =\sum_{y,z}P(y,z) D_{\mathrm{KL}}\!\left(P_{X\mid Y=y}\,\middle\|\,P_{X\mid Z=z}\right) \ge0.$$

よって

$$\boxed{I(X;Z)=H(X)-H(X\mid Z)\le H(X)-H(X\mid Y)=I(X;Y)}.$$

$I(X;Z)$ は最終出力 $Z$ から得られる入力 $X$ の情報量である。後段の通信路を通すことで、前段出力 $Y$ に含まれていた $X$ の情報量が増えることはない。等号となる場合もある。

(7)

最終出力が入力から反転するのは、二つの通信路のうち一方だけで反転した場合である。その確率は

$$\rho=r(1-r)+(1-r)r=2r(1-r).$$

したがって全体は反転確率 $\rho$ の二元対称通信路となり、

$$I(X;Z)=h\bigl(\rho+s(1-2\rho)\bigr)-h(\rho) \le1-h(\rho).$$

上限は $s=1/2$ で達成されるので、

$$C_{12}=1-h\bigl(2r(1-r)\bigr).$$

$0\le r\le1$ において $0\le\rho\le1/2$ である。$h(\rho)=0$ となるのは $\rho=0$、すなわち $r=0,1$ の場合に限る。よって

$$\boxed{r=0\ \text{または}\ r=1,\qquad \max C_{12}=1\ \text{bit/記号}}.$$

$r=1$ の場合も、確実な反転が二回起こるため最終出力は元の入力に一致する。

Reference

• 東京大学 電気系工学専攻：試験科目・サンプル問題の案内
• 2017年度サンプル問題の公開保存版：問題3、日本語 PDF 9ページ
• donguri0912：東大院電気系の過去問解説・2017年問題3（問5・6）