平均符号長の下限(エントロピー, Kullback-Leiblerダイバージェンス)

符号長(\(l(x^n)\))がShannon情報量(\(-\log_2{P(x^n)}\))と等しい場合(確率\(P(x^n)\)に基づく符号化(P-based coding))

$$\begin{array}{rcl} \mathcal{l}(x^n) &=& -\log_2{P(x^n)} \\ -\mathcal{l}(x^n) &=&\log_2{P(x^n)}\\ 2^{-\mathcal{l}(x^n)} &=&2^{\log_2{P(x^n)}}\\ &=&P(x^n)\\ P(x^n) &=&2^{-\mathcal{l}(x^n)}\\ \displaystyle \sum_{x^n \in \chi^n}P(x^n) &\leq& 1&\quad\dotso P(x^n)は確率質量凾数なので総和は1,\;P(x^n)を劣確率凾数とするケースを考える場合は総和は1以下\\ \displaystyle \sum_{x^n \in \chi^n}2^{-\mathcal{l}(x^n)}&\leq&1&\quad\dotso 2^{-\mathcal{l}(x^n)}=P(x^n)なのでやはり総和は1,\;P(x^n)を劣確率凾数とするケースを考える場合は総和は1以下\\ \end{array}$$ 劣確率凾数は \(P(x)\geq0\) の条件は確率(質量)凾数と同じで，\(\sum P(x) \leq 1\)となる凾数．

符号長の期待値とその下限

$$\begin{array}{rcl} E^{n}_{P}\left[\mathcal{l}(X^n)\right]&\geq&H_n(P)&\quad\dotso 符号長の期待値・平均符号長の下限\\ H_n(P)&\overset{\mathrm{def}}{=}& E^{n}_{P}\left[-\log_2{P(X^n)}\right]&\quad\dotso 確率P(x^n)に基づく符号化の長さであることが条件\,\mathcal{l}(X^n)=-\log_2{P(X^n)}\\ \end{array}$$ \(H_n(P)\)をエントロピー(entropy)と呼ぶ．

確率Pで発生しているデータ系列を確率Qに基づく符号化した場合の平均符号長

$$\begin{array}{rcl} \displaystyle \log_2{P(x^n)}-\log_2{P(x^n)} &=&\displaystyle \log_2{Q(x^n)}-\log_2{Q(x^n)}\\ \displaystyle -\log_2{Q(x^n)}&=&-\log_2{P(x^n)}+\log_2{P(x^n)}-\log_2{Q(x^n)}\\ &=&\displaystyle -\log_2{P(x^n)}+\log_2{\frac{P(x^n)}{Q(x^n)}}\\ \displaystyle E^{n}_{P}\left[-\log_2{Q(X^n)}\right] &=&\displaystyle E^{n}_{P}\left[-\log_2{P(X^n)}\right]+E^{n}_{P}\left[\log_2{\frac{P(X^n)}{Q(X^n)}}\right]\\ &=&\displaystyle H_n(P)+D_n(P\parallel Q)\\ D_n(P\parallel Q)&\overset{\mathrm{def}}{=}&E^{n}_{P}\left[\log_2{\frac{P(X^n)}{Q(X^n)}}\right]\\ \end{array}$$ \(D_n(P\parallel Q)\)をKullback-Leiblerダイバージェンス(Kullback-Leibler divergence)と呼ぶ．

χ^n上の確率質量凾数P(x^n)から求める符号長(符号長の期待値, 平均符号長)

\(\chi^n\)上の確率質量凾数\(P(x^n)\)から求める符号長

$$\begin{array}{rl} I(x^n)=\lceil -\log_2{P(x^n)} \rceil &\quad\dotso \chi^n上の確率質量凾数P(x^n)から求める符号長(I:\chi^n \rightarrow \mathbb{R}^{+})\\ \end{array}$$

符号長の期待値

$$\begin{array}{rl} E\left[\mathcal{l}(x^n)\right]=\displaystyle \sum_{x^n\in \chi^n} \mathcal{l}(x^n)P(x^n)&\quad\dotso符号長の期待値, 平均符号長(average\;codeword\;length)\\ \end{array}$$

例:\(\chi=\{0,1\},\;n=2\)

\(y_1\)	\(y_2\)	\(x^2\) \(=y_1y_2\)	\(P(x^2)\)	\(-\log_2{P(x^2)}\) Shannon情報量	\(I(x^2)=\lceil -\log_2{P(x^2)}\rceil\) \(\chi^2\)上の確率質量凾数\(P(x^2)\)から求める符号長	\(\pi(x^2)\)	\(\mathcal{l}(x^2)\) \(=|\pi(x^2)|\)	\(\pi'(x^2)\)	\(\mathcal{l}'(x^2)\) \(=|\pi'(x^2)|\)	\(\pi''(x^2)\)	\(\mathcal{l}''(x^2)\) \(=|\pi''(x^2)|\)
0	0	00	\(\frac{1}{8}\)	\(-\log_2{\frac{1}{8}}=3\)	\(\lceil -\log_2{\frac{1}{8}}\rceil=3\)	000	3	1	1	00	2
0	1	01	\(\frac{1}{8}\)	\(-\log_2{\frac{1}{8}}=3\)	\(\lceil -\log_2{\frac{1}{8}}\rceil=3\)	001	3	01	2	01	2
1	0	10	\(\frac{1}{4}\)	\(-\log_2{\frac{1}{4}}=2\)	\(\lceil -\log_2{\frac{1}{4}}\rceil=2\)	01	2	001	3	10	2
1	1	11	\(\frac{1}{2}\)	\(-\log_2{\frac{1}{2}}=1\)	\(\lceil -\log_2{\frac{1}{2}}\rceil=1\)	1	1	000	3	11	2

上記例で\(\mathcal{l}(x^2)\)が\(I\)と等しい符号化(\(\pi\))の平均符号長

$$\begin{array}{rcl} \displaystyle E\left[\mathcal{l}(x^2)\right] &=&\displaystyle \sum_{x^2\in \chi^2} \mathcal{l}(x^2)P(x^2)\\ &=&\displaystyle 3\times\frac{1}{8}+3\times\frac{1}{8}+2\times\frac{1}{4}+1\times\frac{1}{2}\\ &=&\displaystyle \frac{3+3+4+4}{8} = \frac{14}{8}\\ &=&\displaystyle 1+\frac{3}{4}=1.75\\ \end{array}$$

上記例で\(\mathcal{l}'(x^2)\)が\(I\)と等しくない符号化(\(\pi'\))の平均符号長

$$\begin{array}{rcl} \displaystyle E\left[\mathcal{l}'(x^2)\right] &=&\displaystyle \sum_{x^2\in \chi^2} \mathcal{l}'(x^2)P(x^2)\\ &=&\displaystyle 1\times\frac{1}{8}+2\times\frac{1}{8}+3\times\frac{1}{4}+3\times\frac{1}{2}\\ &=&\displaystyle \frac{1+2+6+12}{8} = \frac{21}{8}\\ &=&\displaystyle 2+\frac{5}{8}=2.625\\ \end{array}$$

上記例で\(\mathcal{l}(x^n)=2\)と常に一定となる符号化(\(\pi''\))の平均符号長

$$\begin{array}{rcl} \displaystyle E\left[\mathcal{l}''(x^2)\right] &=&\displaystyle \sum_{x^2\in \chi^2} \mathcal{l}''(x^2)P(x^2)\\ &=&\displaystyle 2\times\frac{1}{8}+2\times\frac{1}{8}+2\times\frac{1}{4}+2\times\frac{1}{2}\\ &=&\displaystyle 2\times\left(\frac{1}{8}+\frac{1}{8}+\frac{1}{4}+\frac{1}{2}\right)\\ &=&\displaystyle 2\times 1 \\ &=&\displaystyle 2\\ \end{array}$$