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

情報理論において、シャノンの情報源符号化定理（またはノイズレス符号化定理）は、独立した同一分布のランダム変数を情報源とするデータの可能なデータ圧縮の統計的限界と、シャノンエントロピーの操作上の意味を確立します。

クロード・シャノンにちなんで名付けられた情報源符号化定理は、独立かつ同一分布のランダム変数（IID）データストリームの長さが無限大に近づく極限において、符号化率（1シンボルあたりの平均ビット数）が情報源のシャノンエントロピーよりも小さくなるようにデータを圧縮することは不可能であり、その場合、情報の損失がほぼ確実に発生することを示しています。しかし、損失の確率を無視できる程度に、符号化率をシャノンエントロピーに任意に近づけることは可能です。

シンボルコードのソースコーディング定理では、入力ワードのエントロピー(ランダム変数としてみなされる) とターゲットアルファベットのサイズの関数として、コードワードの予想される最小の長さに上限と下限が設定されます。

より多くの依存性を示すデータ（そのソースがIIDランダム変数ではない）の場合、オブジェクトの最小記述長を定量化するコルモゴロフ複雑度は、データ圧縮の限界を記述するのに適していることに注意してください。シャノンエントロピーは頻度の規則性のみを考慮しますが、コルモゴロフ複雑度はアルゴリズムの規則性をすべて考慮するため、一般的に後者の方が小さくなります。一方、オブジェクトが頻度の規則性のみを持つようなランダムプロセスによって生成される場合、エントロピーは高い確率で複雑度に近づきます（Shen et al. 2017）。^[1]

声明

情報源符号化とは、情報源のシンボル（のシーケンス）をアルファベットシンボル（通常はビット）のシーケンスにマッピングすることであり、情報源シンボルはアルファベットシンボルから正確に復元できる（ロスレス情報源符号化）か、ある程度の歪みを伴いながらも復元できる（ロスレス情報源符号化）ようにする。これはデータ圧縮のアプローチの一つである。

情報源符号化定理

情報理論において、情報源符号化定理（シャノン 1948）^[2]は非公式に次のように述べている（マケイ 2003、81ページ、^[3]カバー 2006、第5章^[4]）。

$エントロピーH$ $($ $X$ $)を持つ$ $N個の$ i.idランダム変数は、 $N$ $\to\infty$ のとき、情報損失のリスクがごくわずかで、 $NH$ $($ $X$ $)$ ビット以上に圧縮できます。しかし逆に、 $NH$ $($ $X$ $)$ ビット未満に圧縮された場合、情報が失われることはほぼ確実です。

長さの符号化されたシーケンスは、デコーダーがソースを知っているという仮定の下、圧縮されたメッセージを双一義的に表現します。しかし、実用的な観点から見ると、この仮定は必ずしも正しくありません。そのため、エントロピー符号化を適用する場合、送信メッセージにはソースを特徴付ける情報を含める必要があり、通常は送信メッセージの先頭に挿入されます。 $NH(X)$

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

$Σ 1 、Σ 2 が$ 2 つの有限のアルファベットを表すものとし、Σ $とします。 * 1$ そして $Σ * 2$ それぞれのアルファベットからのすべての有限単語の集合を表します。

$Xは$ $Σ1$ の値をとる確率変数であり、fは $Σ$ $から$ 一意にデコード可能なコードであるとする $。$ $* 1$ $Σ$ へ $* 2$ ここで $|Σ 2 | = a$ 。Sは $コードワード$ $f$ $($ $X$ $)$ の長さによって与えられる確率変数を表す。

$f が$ $X$ の期待語長が最小であるという意味で最適である場合、(Shannon 1948)は次の式で表される。

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

ここで、は期待値演算子を表します。 $\mathbb {E}$

証明: 情報源符号化定理

$Xが$ iid 情報源であるとすると、その時系列 $X 1, ..., X n$ は離散値の場合はエントロピー $H (X)$ 、連続値の場合は微分エントロピーを持つ iid です。情報源符号化定理は、任意の $ε > 0$ 、つまり情報源のエントロピーよりも大きい任意のレート $H (X) + ε$ に対して、十分に大きな $n$ と、情報源 $X$ $1:$ $n$ $のn iid 繰り返しを$ $n$ $($ $H$ $($ $X$ $) +$ $ε$ $)$ バイナリビットにマッピングするエンコーダが存在し、情報源シンボル $X$ $1:$ $n$ $は少なくとも1 -$ $ε$ の確率でバイナリビットから復元可能であることを述べています。

$達成可能性$ の証明。ε $> 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$ が十分に大きい場合、は1に任意に近づき、具体的にはよりも大きくなります（証明についてはAEPを参照）。 $P((X_{1},X_{2},\cdots ,X_{n})\in A_{n}^{\varepsilon })$ $1-\varepsilon$

典型集合の定義は、典型集合に含まれるシーケンスが次の条件を満たすことを意味します。

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

$A$ から抽出されるシーケンスの確率 $(X_{1},X_{2},\cdots X_{n})$ $ε n$ $1 - ε$ より大きい。
$\left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )}$ であり、これはの左辺（下限）から導かれます。 $p(x_{1},x_{2},\cdots x_{n})$
$\left|A_{n}^{\varepsilon }\right|\geq (1-\varepsilon )2^{n(H(X)-\varepsilon )}$ は、の上限と、集合 $A$ 全体の確率の下限から導かれる。 $p(x_{1},x_{2},\cdots x_{n})$ $ε n$ 。

このセット内の任意の文字列を指すにはビットで十分です。 $\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$ において、各 $x$ $i$ の語長をs $i で$ 表す。を定義する。ここで $Cは$ $q$ $1$ $+ ... +$ $q$ $n$ $= 1$ となるように選択される。すると $q_{i}=a^{-s_{i}}/C$

{\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\\&=\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 - δ$ 。ここで、典型的なセット内のシーケンスをエンコードするだけです。情報源符号化の通常の手法では、このセットの基数はより小さいことが示されています。したがって、平均すると、 $H$ $n$ $($ $X$ $) +$ $ε$ $ビットは、 1 -$ $δ を$ 超える確率でエンコードするのに十分です。ここで、 $ε$ と $δ は、$ $n を$ 大きくすることで任意に小さくすることができます。 $2^{n({\overline {H_{n}}}(X)+\varepsilon )}$

参照

参考文献

^ Shen, A.、Uspensky, VA、Vereshchagin, N. (2017). 「第7章3. 複雑性とエントロピー」. コルモゴロフ複雑性とアルゴリズム的ランダム性. アメリカ数学会. p. 226. ISBN 9781470431822。{{cite book}}: CS1 maint: multiple names: authors list (link)
^ CE Shannon、「通信の数学的理論」（Wayback Machineで2009年2月16日にアーカイブ） Bell System Technical Journal、第27巻、pp. 379–423, 623-656、1948年7月、10月
^ David JC MacKay著『情報理論、推論、学習アルゴリズム』ケンブリッジ大学出版局、2003年、 ISBN 0-521-64298-1
^ Cover, Thomas M. (2006). 「第5章データ圧縮」. 情報理論の要素. John Wiley & Sons. pp. 103– 142. ISBN 0-471-24195-4。

[Shen2017-1] Shen, A.、Uspensky, VA、Vereshchagin, N. (2017). 「第7章3. 複雑性とエントロピー」. コルモゴロフ複雑性とアルゴリズム的ランダム性. アメリカ数学会. p. 226. ISBN 9781470431822。{{cite book}}: CS1 maint: multiple names: authors list (link)

[Shannon-2] CE Shannon、「通信の数学的理論」（Wayback Machineで2009年2月16日にアーカイブ） Bell System Technical Journal、第27巻、pp. 379–423, 623-656、1948年7月、10月

[MacKay-3] David JC MacKay著『情報理論、推論、学習アルゴリズム』ケンブリッジ大学出版局、2003年、 ISBN 0-521-64298-1

[Cover-4] Cover, Thomas M. (2006). 「第5章データ圧縮」. 情報理論の要素. John Wiley & Sons. pp. 103– 142. ISBN 0-471-24195-4。