シャノン研究ノート

クロード・シャノンによる情報量の定義とソース符号化定理：データ圧縮の理論的限界

Tags: 情報理論, シャノン, エントロピー, ソース符号化, データ圧縮, AEP, 典型的集合

シャノン研究ノートへようこそ。本日は、クロード・シャノンの情報理論における最も基本的かつ重要な概念の一つである「情報量の測度」、そしてそれに基づく「ソース符号化定理」に焦点を当てて解説いたします。これらの概念は、情報科学、特にデータ圧縮や通信の基礎を築き、現代の情報技術においても極めて重要な位置を占めております。

情報量の定義とその意味

シャノンが1948年の画期的な論文「A Mathematical Theory of Communication」で導入した「情報量」の概念は、ある事象が発生した際に受け取る驚きや不確実性の減少度合いを定量化するものです。事象 $x$ が確率 $P(x)$ で発生するとします。この事象を知ることによって得られる情報量 $I(x)$ は、次のように定義されます。

$I(x) = \log_b \frac{1}{P(x)} = -\log_b P(x)$

ここで、$b$ は対数の底であり、通常は 2 が用いられます。底が 2 の場合、情報量の単位はビット（bit）となります。底が $e$ の場合はナット（nat）、底が 10 の場合はディット（dit, hartley）となります。

なぜ対数が用いられるのでしょうか。これは、以下の直感的な性質を満たすためです。

  1. 発生確率と情報量の関係: 確率が低い（希少な）事象ほど、発生を知ったときの驚きは大きく、情報量も大きいと考えるのが自然です。$P(x)$ が小さいほど $1/P(x)$ は大きくなり、情報量 $I(x)$ も大きくなります。逆に、必ず発生する事象 ($P(x)=1$) の情報量は $\log_b(1) = 0$ となり、情報がないことと整合します。
  2. 独立な事象の情報量の加法性: 互いに独立な二つの事象 $x$ と $y$ が同時に発生する事象 $(x, y)$ の情報量は、それぞれの事象が単独で発生した時の情報量の和であると考えるのが自然です。すなわち、$I(x, y) = I(x) + I(y)$ です。独立事象の同時発生確率 $P(x, y) = P(x)P(y)$ を考慮すると、$I(x, y) = -\log_b P(x)P(y) = -(\log_b P(x) + \log_b P(y)) = -\log_b P(x) - \log_b P(y) = I(x) + I(y)$ となり、対数を用いることでこの性質が満たされます。

このように、情報量は事象の発生確率に基づいてその価値を測る基本的な単位となります。

エントロピー：情報源の不確実性の測度

情報源が生成するメッセージが、確率分布 $P(x)$ に従うシンボル $x$ の集合であるとします。この情報源が発生させる平均的な情報量、あるいは情報源に含まれる不確実性の度合いを示すのがエントロピーです。確率変数 $X$ のエントロピー $H(X)$ は、各シンボルの情報量の期待値として定義されます。

$H(X) = E[I(X)] = \sum_x P(x) I(x) = \sum_x P(x) (-\log_b P(x)) = - \sum_x P(x) \log_b P(x)$

ここでも、底 $b$ に 2 を用いた場合、単位はビット/シンボルとなります。エントロピーは、情報源が 1 シンボルあたり平均してどれだけの「情報」を含んでいるか、あるいは情報源の出力がどの程度予測困難であるかを示す測度と解釈できます。

エントロピーは以下の重要な性質を持ちます。

エントロピーは、情報源の持つ「情報量」や「不確実性」を定量的に評価するための中心的な概念です。

ソース符号化定理：可逆圧縮の理論的限界

シャノンのソース符号化定理（無記憶情報源に対する第一定理）は、データ圧縮、特に可逆圧縮（ロスレス圧縮）の理論的な限界を示すものです。この定理は、無記憶情報源からの出力を、平均符号長が最小となるように符号化する方法について述べています。

定理 (無記憶情報源に対するソース符号化定理): アルファベット $\mathcal{X}$ 上の確率分布 $P(x)$ に従う無記憶情報源 $X$ があるとします。この情報源からの長さを $N$ の系列 $X_1, X_2, \dots, X_N$ を、二進符号語の系列に可逆的に符号化することを考えます。符号語の平均長をシンボルあたりで考えた場合、以下の二つのステートメントが成り立ちます。

  1. どのような可逆符号化方式を用いても、符号語の平均長 $\bar{L}$ は情報源のエントロピー $H_2(X)$ よりも小さくなることはありません。すなわち、$\bar{L} \ge H_2(X)$。
  2. 任意の $\epsilon > 0$ に対して、情報源の出力系列を符号化する際に、シンボルあたりの平均符号長を $H_2(X) + \epsilon$ 以下にできるような符号化方式が存在します。また、この符号化方式は、符号長 $N$ を大きくするにつれて復号誤り率を任意に小さくすることができます。

この定理の第一の部分は、情報源エントロピーがデータ圧縮率の究極的な限界、すなわちシンボルあたりの最小平均ビット数であることを示しています。情報源が持っている不確実性の量（エントロピー）以下のビット数で情報を完全に表現することはできない、という直感と合致します。

定理の第二の部分は、エントロピーという理論的な限界が、実際には（系列長を十分長くすれば）いくらでも近づけることが可能であることを示しています。これは、エントロピーに基づく効率的な符号化方式が存在することを示唆しています。

証明の核心：漸近等分割性（AEP）と典型的集合

ソース符号化定理の第二の部分（達成可能性）の証明は、シャノンの情報理論における重要な概念である漸近等分割性 (Asymptotic Equipartition Property, AEP) と典型的集合 (Typical Set) に基づいています。

AEPは、無記憶情報源から生成される十分に長い系列 $X_1, \dots, X_n$ において、その同時確率 $P(X_1, \dots, X_n)$ が、高い確率で $2^{-nH(X)}$ のオーダーとなることを主張します。より厳密には、大数の法則によって、サンプル平均 $-\frac{1}{n}\log_2 P(X_1, \dots, X_n)$ が、情報源エントロピー $H_2(X)$ に確率収束することに基づいています。

$-\frac{1}{n}\log_2 P(X_1, \dots, X_n) \to H_2(X)$ as $n \to \infty$ with high probability

これは $P(X_1, \dots, X_n) \approx 2^{-nH_2(X)}$ であることを意味します。

典型的集合 $A_\epsilon^{(n)}$ とは、この性質を満たす、すなわち $-\frac{1}{n}\log_2 P(x_1, \dots, x_n)$ がエントロピー $H_2(X)$ の近くにある（例えば $|-\frac{1}{n}\log_2 P(x_1, \dots, x_n) - H_2(X)| < \epsilon$ となる）系列 $(x_1, \dots, x_n)$ の集合です。AEPによれば、十分に長い系列は非常に高い確率で典型的集合に含まれます。

重要なのは、この典型的集合に含まれる系列の数 $|A_\epsilon^{(n)}|$ です。AEPから、$|A_\epsilon^{(n)}| \approx 2^{nH_2(X)}$ のオーダーであることが示されます。正確には、$(1-\epsilon') 2^{n(H(X)-\epsilon)} \le |A_\epsilon^{(n)}| \le 2^{n(H(X)+\epsilon)}$ のように、指数部が $nH(X)$ に近い範囲に収まることが証明されます。

ソース符号化定理の達成可能性証明では、この $|A_\epsilon^{(n)}|$ という数を符号語の数として利用します。長い系列 $(x_1, \dots, x_n)$ が典型的集合に属する場合、それらを区別するために必要な符号語の数は $|A_\epsilon^{(n)}|$ 個あれば十分です。各系列に $\lceil \log_2 |A_\epsilon^{(n)}| \rceil$ ビット程度の符号語を割り当てれば良いことになります。$|A_\epsilon^{(n)}| \approx 2^{nH_2(X)}$ なので、これに必要なビット数は約 $nH_2(X)$ ビットとなります。系列長 $n$ で割ると、シンボルあたり約 $H_2(X)$ ビットとなり、エントロピーに近づけることができるわけです。非典型的集合に属する系列は出現確率が非常に低いため、例えば一つの特別な符号語でまとめて表現し、後処理で対応するか、あるいは非常に長い系列長では無視できるほどの確率であることを利用します。

この典型的集合の概念は、シャノンの情報理論における多くの定理の証明基盤となっており、確率論における大偏差理論とも関連が深いものです。

歴史的背景と現代における意義

シャノンが情報理論を構築した当時、データ圧縮は主に特定のデータに対する経験的な手法（例えば、モールス符号のような頻度に応じた符号長割り当て）に依存していました。シャノンのエントロピーとソース符号化定理は、情報源のもつ情報量そのものを定量化し、どのような情報源に対しても普遍的に成り立つ圧縮の理論的な限界を初めて明確に示しました。これは、その後のデータ圧縮アルゴリズム開発における明確な目標を与えたものです。

現代では、シャノンの理論は様々な圧縮技術の基盤となっています。ハフマン符号は、各シンボルに対しては最適ではありませんが、シンボルのブロック長を長くすればエントロピーに近づく符号化が可能であることを示し、ソース符号化定理の構成的な証明の一つとも見なせます。算術符号のようなより洗練された手法は、より高い圧縮率を実現し、現代の多くのロスレス圧縮フォーマット（PNG, FLAC, ZIPなどに含まれるDeflateアルゴリズムの一部）で利用されています。Lempel-Ziv符号化のような辞書ベースの圧縮手法は、無記憶情報源だけでなく、より一般的な情報源に対しても高い圧縮率を実現しますが、その理論的性能解析においてもエントロピーや関連概念が用いられます。

ソース符号化定理は、単にデータ圧縮の限界を示すだけでなく、情報源のもつ本質的な「情報量」をエントロピーとして定義することの妥当性を、通信やストレージという応用的な観点から裏付けていると言えます。

結論

クロード・シャノンが定義した情報量とエントロピー、そしてソース符号化定理は、情報科学の基礎をなす極めて重要な概念です。エントロピーは情報源の不確実性を定量化し、ソース符号化定理は可逆データ圧縮の理論的な限界がそのエントロピーであることを示しました。特に、漸近等分割性（AEP）と典型的集合の概念は、この定理の達成可能性を理解する上で不可欠であり、情報理論における強力な数学的手法を示しています。

これらの理論は、発表から70年以上が経過した現在でもその価値を失っておらず、データ圧縮だけでなく、統計学、機械学習、複雑系など、幅広い分野における情報の本質を探求する上で不可欠な基礎知識であり続けています。シャノンの洞察は、情報という抽象的な概念に厳密な数学的構造を与え、その後の技術発展に計り知れない影響を与えました。