東京大学 情報理工学系研究科 電子情報学専攻 2016年8月実施 専門 第5問

标签：

• Tokyo-University
• Entropy
• Huffman-Coding
• Conditional-Entropy

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

あるモデル $M$ が情報源 $S$ として働き、下記の表の $a_n$（ただし、$n=0,\ldots,15$）を出力したとする。このとき、以下の問いに答えよ。ただし、$\log_2 3=1.6,\ \log_2 5=2.3$ とせよ。

(1) $M$ が明らかとなっていないとき、$S$ の各事象は独立に出力されたと考えることにする。与えられた表から推定される $S$ の平均情報量を有効数字 $2$ 桁で示せ。

(2) $S$ の情報源符号化を考える。平均符号長が $2.2$ [bit] 未満となる $S$ の符号化規則を設計せよ。

次に、$M$ が以下であると推定されたとする。モデル $M$ は、$n\ge2$ に対し、

$$a_n=\alpha a_{n-1}+\beta a_{n-2}+b_n$$

で $a_n$ を生成する。ここで、$b_n$ は情報源 $T$ が生成したもので、与えられた表を出力したときの $T$ の平均情報量は $1.0$ であったことがわかっている。$\alpha$ および $\beta$ は整数の定数であり、$\alpha+\beta=1$ を満たすとする。

(3) 適切と思われる $\alpha$ および $\beta$ の例を一つ挙げよ。またそのときの $T$ の出力した事象の種類とそれぞれの出現確率を示せ。

(4) このようにモデル $M$ が明らかとなったときに、与えられた表の情報を伝達するのに必要な符号長を求めよ。ただし、$a_1,a_0$ は $S$ が独立に出力したものと考え、(2) の符号化規則を用いよ。

(5) ある情報源 $X$ に対して、その平均情報量を $I(X)$ で表す。一般に、複数の情報源 $X_1,\ldots,X_n$ からの外部入力があり、情報源 $Y$ として働くモデルがあるとき、$I(Y)$ は $\sum_{i=1}^{n}I(X_i)$ になるとは限らない。その要因として考えられるものを $3$ 通り述べよ。

$n$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$a_n$	2	5	3	4	4	3	3	4	2	3	1	4	2	5	3	4

Kai

(1)

$1,2,3,4,5$ の出現回数はそれぞれ $1,3,5,5,2$ なので、

$$\begin{aligned} H(S)&=-\sum_{k=1}^{5}p_k\log_2p_k\\ &=4-\frac{3\log_2 3+10\log_2 5+2}{16}\\ &\simeq2.1375\simeq\boxed{2.1\ \text{bit}}. \end{aligned}$$

(2)

ハフマン符号の一例を示す。

出力	出現確率	符号
$1$	$1/16$	000
$2$	$3/16$	01
$3$	$5/16$	10
$4$	$5/16$	11
$5$	$2/16$	001

$$\boxed{\overline L=\frac{3(1+2)+2(3+5+5)}{16} =\frac{35}{16}=2.1875<2.2\ \text{bit}}.$$

(3)

$$\boxed{\alpha=0,\qquad\beta=1}$$

とすれば、$b_n=a_n-a_{n-2}$ は

$$(1,-1,1,-1,-1,1,-1,-1,-1,1,1,1,1,-1)$$

となる。$+1,-1$ が各 $7$ 回現れるので、

$$\boxed{P_T(+1)=P_T(-1)=\frac12},\qquad H(T)=1\ \text{bit}.$$

(4)

$a_0=2$ は $2$ bit、$a_1=5$ は $3$ bit である。残りの $14$ 個は、$b_n=+1,-1$ をそれぞれ 0,1 とすれば $1$ 個につき $1$ bit で送れる。

$$\boxed{L=2+3+14=19\ \text{bit}}.$$

(5)

1. 入力間の依存性。 入力が相関をもつと、結合エントロピーは各入力のエントロピーの和より小さい。例えば $X_2=X_1$ なら、二つを知っても情報量は倍にならない。
2. モデルによる情報の消失。 異なる入力を同じ出力に写す多対一の変換では、入力を出力から復元できず、情報量が減る。例えば入力を常に $0$ に写す場合である。
3. モデル内部の新たな乱数。 外部入力以外の独立な雑音・乱数が出力に加わると、外部入力の情報量の和に含まれない不確実性が生じる。