シャノンの第一定理: 情報理論入門 5 - コンピュータフリーク

情報源記号をひとつひとつ符号化するのではなく、複数の情報源記号をまとめて符号化するとより効率的に符号化ができます。ひとつひとつ符号化する場合は平均符号長の下界と達成できる値に開きがありましたが、複数の情報源記号をまとめて符号化する場合は下界に任意に近づく符号長を達成できます。この綺麗な定理をシャノンの第一定理、またの名を情報源符号化定理といい、情報理論の最も重要な理論の一つに数えられています。

問題設定

情報源記号を $\mathcal{X}$ とし、符号アルファベットを $\Sigma = \{0, 1\}$ とします。

情報源からは記号 $x \in \mathcal{X}$ が確率 $p(x)$ で生じるとします。

前章では、各情報源記号 $x \in \mathcal{X}$ に対して符号語 $f(x) \in \Sigma^*$ を割り当てましたが、本章では、$n$ 個の情報源記号に対して符号語を割り当てる方式 $f\colon \mathcal{X}^n \to \Sigma^*$ を考えます。たとえば、$n = 3$ で情報源から生成された記号列が $AABABBAAB \cdots$ のとき、$f(AAB)f(ABB)f(AAB) \cdots$ というように符号化されます。各記号は i.i.d で生成されるとし、記号列の確率も $p$ という記号を用います。たとえば $p(ABB) = p(A)p(B)^2$ を表します。

瞬時符号 $f\colon \mathcal{X}^n \to \Sigma^*$ であって、平均符号長 $\mathbb{E}_{(x_1, \cdots, x_n) \sim p}[|f(x_1 x_2 \cdots x_n)|]$ が小さいものを構築するのが目的です。

拡大情報源のエントロピー

$n$ 個の情報源記号をまとめて符号化するとき、$\mathcal{X}^n$ という $|\mathcal{X}|^n$ 個の情報源記号がある情報源を符号化していると考えることもできます。このように、$n$ 個の記号をまとめて一つの記号と考えた情報源を$n$ 次拡大情報源とよびます。

情報源からの系列が i.i.d. であるとき、拡大情報源のエントロピーはもとの情報源の $n$ 倍であることが示せます。

定理: 拡大情報源のエントロピー

情報源からの系列が i.i.d. であるとき、$n$ 次拡大情報源のエントロピーは $$H(\mathcal{X}^n, p) = nH(\mathcal{X}, p)$$ となる。

証明

$$\begin{align*}H(\mathcal{X}^n, p) &\overset{\text{(a)}}{=} – \sum_{x_1 \in \mathcal{X}} \cdots \sum_{x_n \in \mathcal{X}} p(x_1 \cdots x_n) \log p(x_1 \cdots x_n) \\ &\overset{\text{(b)}}{=} – \sum_{x_1 \in \mathcal{X}} \cdots \sum_{x_n \in \mathcal{X}} p(x_1 \cdots x_n) \log p(x_1) \cdots p(x_n) \\ &\overset{\text{(c)}}{=} -\sum_{x_1 \in \mathcal{X}} \cdots \sum_{x_n \in \mathcal{X}} p(x_1 \cdots x_n) \sum_{i = 1}^n \log p(x_i) \\ &= – \sum_{i = 1}^n\sum_{x_1 \in \mathcal{X}} \cdots \sum_{x_n \in \mathcal{X}} p(x_1 \cdots x_n) \log p(x_i) \\ &\overset{\text{(d)}}{=} – \sum_{i = 1}^n \sum_{x_i \in \mathcal{X}} p(x_i) \log p(x_i) \\ &\overset{\text{(e)}}{=} \sum_{i = 1}^n H(\mathcal{X}, p) \\ &= nH(\mathcal{X}, p) \end{align*}$$ ただし、(a) はエントロピーの定義より、(b) は i.i.d. であることより、(c) は $\log$ 関数の性質より, (d) は確率分布の周辺化より、(e) はエントロピーの定義より従う。

シャノンの第一定理

いよいよ、シャノンの第一定理を証明します。この定理は、情報源記号をまとめて符号化することで、一記号あたりの平均符号長がエントロピーに任意に近づけることができることを示しています。$n$ 記号まとめて符号化するとき、一つの符号 $f(x_1 \cdots x_n)$ に $n$ 記号分の情報が込められているので、送信する符号アルファベットは一記号あたり $\frac{1}{n} |f(x_1 \cdots x_n)|$ であることに注意してください。

定理: シャノンの第一定理

瞬時符号 $f\colon \mathcal{X}^n \to \Sigma^*$ の一記号あたりの平均符号長は $$\mathbb{E}_{(x_1, \cdots, x_n) \sim p}[\frac{1}{n} |f(x_1 x_2 \cdots x_n)|] \ge H(\mathcal{X}, p)$$ を満たす。逆に、任意の $\varepsilon > 0$ に対して、正整数 $n \in \mathbb{Z}_+$ および瞬時符号 $f\colon \mathcal{X}^n \to \Sigma^*$ が存在して、$$\mathbb{E}_{(x_1, \cdots, x_n) \sim p}[\frac{1}{n} |f(x_1 x_2 \cdots x_n)|] \le H(\mathcal{X}, p) + \varepsilon$$ とできる。

証明

平均符号長の限界定理を拡大情報源 $\mathcal{X}^n$ に適用すると、任意の瞬時符号 $f\colon \mathcal{X}^n \to \Sigma^*$ に対して、$$\begin{align*}\mathbb{E}_{(x_1, \cdots, x_n) \sim p}[\frac{1}{n} |f(x_1 x_2 \cdots x_n)|] &= \frac{1}{n} \mathbb{E}_{(x_1, \cdots, x_n) \sim p}[|f(x_1 x_2 \cdots x_n)|]\\ &\ge \frac{1}{n} H(\mathcal{X}^n, p) \\ &= H(\mathcal{X}, p)\end{align*}$$ となる。

一方、$n = \text{ceil}\left(\frac{1}{\varepsilon}\right)$ とし、$n$ 次拡大情報源に対してシャノン・ファノ符号 $f$ を構築すると、$$\begin{align*}\mathbb{E}_{(x_1, \cdots, x_n) \sim p}[\frac{1}{n} |f(x_1 x_2 \cdots x_n)|] &= \frac{1}{n} \mathbb{E}_{(x_1, \cdots, x_n) \sim p}[|f(x_1 x_2 \cdots x_n)|] \\ &\le \frac{1}{n} \left(H(\mathcal{X}^n, p) + 1\right) \\ &= \frac{1}{n} \left(nH(\mathcal{X}, p) + 1\right) \\ &= H(\mathcal{X}, p) + \frac{1}{n} \\ &\le H(\mathcal{X}, p) + \varepsilon \end{align*}$$