シャノンの情報源符号化定理

情報理論において、シャノンの情報源符号化定理（シャノンのじょうほうげんふごうかていり、英語: Shannon's source coding theorem, noiseless coding theorem）は、データ圧縮の可能な限界と情報量（シャノンエントロピー）の操作上の意味を確立する定理である。1948年のクロード・シャノンの論文『通信の数学的理論』で発表された。シャノンの第二基本定理（通信路符号化定理）に対してシャノンの第一基本定理とも言う。

情報源符号化定理によれば、（独立同分布(iid)の確率変数のデータの列の長さが無限大に近づくにつれて）、符号化率（記号1つ当たりの平均符号長）が情報源のシャノンエントロピーよりも小さいデータを、情報が失われることが事実上確実ではないように圧縮することは不可能である。しかし、損失の可能性が無視できる場合、符号化率を任意にシャノンエントロピーに近づけることは可能である。

シンボルコードの情報源符号化定理は、入力語（確率変数と見なされる）のエントロピーとターゲットアルファベットの大きさの関数として、符号語の可能な期待される長さに上限と下限を設定する。

提示

情報源符号化とは、情報源の記号（の列）からアルファベット記号（通常はビット）の列への写像である。情報源の記号は二進数ビットから正確に復元できる（可逆圧縮）か、何らかの歪みを伴って復元される（非可逆圧縮）。これが、データ圧縮の背後にあるコンセプトである。

情報源符号化定理

情報源符号化定理(Shannon 1948)^[1]は以下のように非形式的に提示されている(MacKay 2003, pg. 81,^[2] Cover:Chapter 5^[3])。

情報量 $H (X)$ を持つ $N$ 個の独立同分布の確率変数は、 $N \to \infty$ のとき、無視できるほどの情報損失のリスクをもって $N H (X)$ ビット以上に圧縮できる。しかし、 $N H (X)$ ビット以下に圧縮されたとき、情報が失われることは事実上確実である。

シンボルコードの情報源符号化定理

$Σ 1, Σ 2$ を2つの有限のアルファベットとし、 $Σ * 1$ と $Σ * 2$ をそれぞれのアルファベットからの全ての有限語の集合とする。

$X$ を $Σ 1$ の値をとる確率変数とし、 $f$ を $Σ * 1$ から $Σ * 2$ への一意復号可能な符号とする（ここで、 $|Σ 2 | = a$ ）。 $S$ を単語長 $f (X)$ で与えられる確率変数とする。

$f$ が $X$ の最小単語長さという意味で最適であるとき、

{\frac {H(X)}{\log _{2}a}}\leq \mathbb {E} S<{\frac {H(X)}{\log _{2}a}}+1

である。(Shannon 1948)

証明

情報源符号化定理の証明

$X$ が独立同分布(iid)な情報源であるとき、その時系列 $X 1, ..., X n$ は、離散値の場合はエントロピー $H (X)$ 　、連続値の場合は差分エントロピーで独立同分布となる。情報源符号化定理によれば、情報源のエントロピーより大きい任意のレートの任意の $ε > 0$ に対して、十分に大きい $n$ と、情報源 $X 1: n$ の独立同分布な $n$ 個の複写をとり、これを $n (H (X) + ε)$ この二進数ビットに写像するエンコーダがあり、それは、少なくとも $1 - ε$ の確率で、情報源記号 $X 1: n$ が二進数ビットから復元できる。

達成可能性の証明。いくつかの $ε > 0$ を修正し、

p(x_{1},\ldots ,x_{n})=\Pr \left[X_{1}=x_{1},\cdots ,X_{n}=x_{n}\right].

とする。典型集合（英語版） $A ε n$ は、以下のように定義される。

A_{n}^{\varepsilon }=\left\{(x_{1},\cdots ,x_{n})\ :\ \left|-{\frac {1}{n}}\log p(x_{1},\cdots ,x_{n})-H_{n}(X)\right|<\varepsilon \right\}

漸近的等分配性（英語版）(AEP)が示すところによると、十分に大きい $n$ に対して、情報源によって生成された列が典型集合 $A ε n$ に含まれる確率は 1 に近づく。特に、十分に大きい $n$ に対しては、 $P((X_{1},X_{2},\cdots ,X_{n})\in A_{n}^{\varepsilon })$ は任意に 1 に近く、具体的には $1-\varepsilon$ より大きくすることができる。

典型集合の定義は、典型集合にある列が以下を満足することを意味する。

2^{-n(H(X)+\varepsilon )}\leq p\left(x_{1},\cdots ,x_{n}\right)\leq 2^{-n(H(X)-\varepsilon )}

注意:

$A ε n$ から導かれる列 $(X_{1},X_{2},\cdots X_{n})$ の確率は $1 - ε$ より大きい。
$p(x_{1},x_{2},\cdots x_{n})$ の左側（下限）からは $\left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )}$ となる。
$p(x_{1},x_{2},\cdots x_{n})$ の右側（上限）および全体集合 $A ε n$ の全確率に対する下限からは $\left|A_{n}^{\varepsilon }\right|\geq (1-\varepsilon )2^{n(H(X)-\varepsilon )}$ となる。

よって、 $\left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )},n.(H(X)+\varepsilon )$ ビットはこの集合の任意の文字列を指すのに十分である。

エンコードアルゴリズム : エンコーダは、入力列が典型集合内にあるかどうかをチェックする。そうであれば、典型集合内の入力列のインデックスを出力する。そうでなければ、エンコーダは任意の $n (H (X) + ε)$ 桁の数を出力する。入力列が典型集合内にある限り（少なくとも $1 - ε$ の確率で）、エンコーダは何の誤りも生じない。従って、エンコーダの誤りの確率の上限は $ε$ である。

逆の証明。その逆は、 $A ε n$ より小さいサイズの集合が 1 から離れる確率の集合をカバーすることを示すことで証明できる。

シンボルコードの情報源符号化定理の証明

$1 \leq i \leq n$ について、 $s i$ をそれぞれ可能な $x i$ の語長とする。 $q_{i}=a^{-s_{i}}/C$ と定義する。ここで、 $C$ は $q 1 + ... + q n = 1$ となるように選択される。

{\begin{aligned}H(X)&=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}\\&\leq -\sum _{i=1}^{n}p_{i}\log _{2}q_{i}\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\sum _{i=1}^{n}p_{i}\log _{2}C\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\log _{2}C\\&\leq -\sum _{i=1}^{n}-s_{i}p_{i}\log _{2}a\\&\leq \mathbb {E} S\log _{2}a\\\end{aligned}}

ここで、2行目はギブスの不等式に、5行目はクラフトの不等式による。

C=\sum _{i=1}^{n}a^{-s_{i}}\leq 1

よって $log C \leq 0$ である。

2行目の不等式について、

s_{i}=\lceil -\log _{a}p_{i}\rceil

とすると、

-\log _{a}p_{i}\leq s_{i}<-\log _{a}p_{i}+1

であり

a^{-s_{i}}\leq p_{i}

であり

\sum a^{-s_{i}}\leq \sum p_{i}=1

よって、クラフトの不等式には、これらの語長を持つ接頭辞のない符号が存在する。従って、最小の $S$ は以下を満たす。

{\begin{aligned}\mathbb {E} S&=\sum p_{i}s_{i}\\&<\sum p_{i}\left(-\log _{a}p_{i}+1\right)\\&=\sum -p_{i}{\frac {\log _{2}p_{i}}{\log _{2}a}}+1\\&={\frac {H(X)}{\log _{2}a}}+1\\\end{aligned}}

非定常独立系への拡張

離散時間非定常独立情報源のための固定レート可逆情報源符号化

典型集合 $A ε n$ を

A_{n}^{\varepsilon }=\left\{x_{1}^{n}\ :\ \left|-{\frac {1}{n}}\log p\left(X_{1},\cdots ,X_{n}\right)-{\overline {H_{n}}}(X)\right|<\varepsilon \right\}

と定義する。

次に、与えられた $δ > 0$ に対して、 $n$ が十分に大きい場合、 $Pr(A ε n) > 1 - δ$ である。あとは、典型集合の列をエンコードするだけであり。情報源符号化の通常の方法は、この集合の濃度が $2^{n({\overline {H_{n}}}(X)+\varepsilon )}$ であることを示す。従って、 $1 - δ$ より大きい確率で符号化するには、平均して $H n (X) + ε$ ビットで十分である。ここで、 $n$ を大きくすることによって、 $ε$ と $δ$ を任意に小さくすることができる。

脚注

^ C.E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, vol. 27, pp. 379–423, 623-656, July, October, 1948
^ David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
^ Cover, Thomas M. (2006). “Chapter 5: Data Compression”. Elements of Information Theory. John Wiley & Sons. ISBN 0-471-24195-4

[Shannon-1] C.E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, vol. 27, pp. 379–423, 623-656, July, October, 1948

[MacKay-2] David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1

[Cover-3] Cover, Thomas M. (2006). “Chapter 5: Data Compression”. Elements of Information Theory. John Wiley & Sons. ISBN 0-471-24195-4

[1]

[2]

[3]

提示