普遍符号化の理論的源流：シャノン情報源のエントロピーと漸近等分割性の役割
はじめに：情報源が不明な場合の符号化の課題
情報源符号化の基本定理は、離散無記憶情報源（Discrete Memoryless Source, DMS）に対して、そのエントロピーに漸近的に等しいレートでの可逆圧縮が可能であることを示しています。これは、情報源の確率分布 $P(x)$ が既知である場合に成立する理論的な限界と構成法（ハフマン符号や算術符号など）を示すものです。
しかし、実際には情報源の正確な統計的性質、すなわち確率分布 $P(x)$ が未知であるか、あるいは時間とともに変化する場合が少なくありません。このような状況において、情報源のモデルを知らなくても、漸近的にエントロピーレートに等しい圧縮率を達成できる符号化手法が求められます。これが普遍符号化（Universal Source Coding）の考え方です。
シャノン自身が「普遍符号化」という言葉を明確に定義し、現代的な意味での普遍符号化アルゴリズムを提案したわけではありません。しかし、彼の情報源理論の中核をなす概念、特にエントロピー率と漸近等分割性（Asymptotic Equipartition Property, AEP）は、情報源のモデルに依存しない、あるいは依存性が限定的な符号化手法の可能性を示唆しており、普遍符号化の理論的な源流となっています。本稿では、シャノンの情報源理論がいかに普遍符号化の基盤を提供しているかについて掘り下げていきます。
シャノン情報源のエントロピー率：不確実性の漸近的尺度
シャノンの情報理論において、離散無記憶情報源のエントロピーは、情報源から出力されるシンボルあたりの平均情報量、すなわち不確実性の尺度として定義されます。より一般的な情報源、例えば定常エルゴード情報源（Stationary Ergodic Source）に対しては、エントロピー率（Entropy Rate）という概念が導入されます。
情報源 ${X_i}{i=1}^\infty$ が生成する長さ $n$ の系列を $X_1, X_2, \dots, X_n$ とします。この系列が出現する確率を $P(x_1, \dots, x_n)$ とすると、長さ $n$ の系列のエントロピーは $H(X_1, \dots, X_n) = -\sum{x_1,\dots,x_n} P(x_1, \dots, x_n) \log_2 P(x_1, \dots, x_n)$ で定義されます。
情報源のエントロピー率は、以下のように定義されます。 $$ H(\mathcal{X}) = \lim_{n \to \infty} \frac{1}{n} H(X_1, \dots, X_n) $$ この極限は、情報源が定常であれば存在することが知られています。さらに、情報源が定常かつエルゴード的であれば、このエントロピー率は $H'(\mathcal{X}) = \lim_{n \to \infty} H(X_n | X_1, \dots, X_{n-1})$ に等しくなります。これは、過去のシンボルが与えられた下での次のシンボルの条件付きエントロピーの極限であり、情報源の「記憶」や「相関」を考慮した上での、シンボルあたりの削減不可能な不確実性、すなわち真の情報量を表します。
定常エルゴード性という条件は、情報源の統計的性質が時間的に変化せず、また長期的な平均がアンサンブル平均に一致するという性質を保証します。多くの現実的な情報源（例えば、十分に長いテキストや音声信号など）はこの性質を持つと仮定できます。シャノンの情報源理論は、このような定常エルゴード情報源を主要な対象としており、その情報源のエントロピー率 $H(\mathcal{X})$ が、可逆圧縮の理論的な下限を与えることを示しました（情報源符号化定理）。
漸近等分割性 (AEP)：ほとんどすべての系列の確率的構造
シャノン情報源理論の最も強力な結果の一つに、漸近等分割性（Asymptotic Equipartition Property, AEP）があります。これは、定常エルゴード情報源から生成される「ほとんどすべての」長い系列が、ほぼ等しい確率を持つことを主張するものです。より正確には、長さ $n$ の系列 $X_1, \dots, X_n$ について、その確率 $P(X_1, \dots, X_n)$ は、 $n$ が十分大きいとき、約 $2^{-n H(\mathcal{X})}$ に近づくという性質です。対数で表現すると、 $$ \lim_{n \to \infty} -\frac{1}{n} \log_2 P(X_1, \dots, X_n) = H(\mathcal{X}) \quad \text{in probability} $$ となります。すなわち、系列の対数確率の平均 $-\frac{1}{n} \log_2 P(X_1, \dots, X_n)$ は、系列によらず情報源のエントロピー率 $H(\mathcal{X})$ に確率収束します。
AEPの核心は、典型集合（Typical Set）の存在です。典型集合 $A_\epsilon^{(n)}$ は、長さ $n$ の系列のうち、$-\frac{1}{n} \log_2 P(x_1, \dots, x_n)$ がエントロピー率 $H(\mathcal{X})$ から $\epsilon$ 以内に収まる系列の集合として定義されます。 $$ A_\epsilon^{(n)} = \left{ (x_1, \dots, x_n) \in \mathcal{X}^n : \left| -\frac{1}{n} \log_2 P(x_1, \dots, x_n) - H(\mathcal{X}) \right| \le \epsilon \right} $$ AEPが主張するのは、以下の二点です。 1. 典型集合に含まれる系列の確率は1に近づく： $\lim_{n \to \infty} P(A_\epsilon^{(n)}) = 1$ 2. 典型集合に含まれる系列の数は、漸近的に $2^{n H(\mathcal{X})}$ 個である： $(1-\epsilon) 2^{n(H(\mathcal{X})-\epsilon)} \le |A_\epsilon^{(n)}| \le 2^{n(H(\mathcal{X})+\epsilon)}$ （十分大きい $n$ に対して）
この性質は極めて重要です。情報源が生成する系列の大部分（確率的に）が典型集合に属し、その典型集合のサイズが情報源のエントロピー率によって決まる $2^{n H(\mathcal{X})}$ 個程度である、ということを意味します。
AEPと普遍符号化への示唆
情報源符号化の目的は、長い系列を短い二進符号語に一意にマッピングすることです。AEPは、長さ $n$ の系列のうち符号化する必要があるのは実質的に典型集合に属する系列だけであり、その数は約 $2^{n H(\mathcal{X})}$ 個であることを示唆しています。この約 $2^{n H(\mathcal{X})}$ 個の系列を一意に識別するためには、少なくとも $\lceil \log_2 2^{n H(\mathcal{X})} \rceil \approx n H(\mathcal{X})$ ビットが必要です。これが情報源符号化定理の直感的な説明であり、エントロピー率が圧縮の限界であることを示しています。
ここで普遍符号化の観点からAEPを見直します。AEPは、情報源が「定常エルゴード」であるという比較的緩やかな条件の下で成立します。具体的な確率分布 $P(x_1, \dots, x_n)$ の詳細を知らなくても、系列が十分に長ければ、ほとんどの系列が典型集合に入り、その確率は $2^{-n H(\mathcal{X})}$ に近いという性質を利用できる可能性があります。
理想的な（理論的な）普遍符号化アプローチの一つは、観測された系列 $x = (x_1, \dots, x_n)$ が与えられたときに、その系列の経験的確率分布（empirical distribution）、すなわち各シンボルの出現頻度やシンボル間の遷移頻度を計算し、その経験的分布に基づいた「経験的エントロピー率」を推定することです。定常エルゴード情報源であれば、長い系列の経験的分布は、情報源の真の確率分布に収束するというエルゴード性の性質があります。したがって、経験的エントロピー率は、真のエントロピー率 $H(\mathcal{X})$ に収束します。
AEPは、経験的エントロピー率が真のエントロピー率に近づくことを示唆しています。具体的には、典型集合に属する系列 $(x_1, \dots, x_n)$ について、その経験的確率分布 $\hat{P}(a) = \frac{1}{n} \sum_{i=1}^n \mathbb{I}(x_i = a)$ から計算される経験的エントロピー $\hat{H}(X) = -\sum_a \hat{P}(a) \log_2 \hat{P}(a)$ は、DMSの場合、真のエントロピー $H(X)$ に近づきます。より複雑な情報源に対しては、経験的な条件付き確率などを用いて同様の議論が可能です。
普遍符号化アルゴリズムは、この考えに基づき、入力系列を解析してその統計的性質（経験的分布など）を推定し、その推定された統計量に基づいて符号化を行います。有名な例としては、リッペルとネーマンが提案したユニバーサルカウンティング符号（Universal Counting Code）があります。この符号は、長さ $n$ の系列を、その系列のタイプ（各シンボルの出現回数）とタイプ内のインデックスによって符号化します。タイプの数は $n$に対して多項式的に増加しますが、各タイプの系列数は指数的に増加します。AEPは、エントロピー率に近いタイプにほとんどの系列が集中することを示しており、そのタイプを効率的に符号化することで、漸近的にエントロピー率を達成できる可能性を示唆しています。
現代の普遍符号化とシャノン理論
現代の普遍符号化理論は、シャノンの基本理論の上に、より洗練された数学的ツール（大偏差理論、レート歪み理論の応用など）を用いて発展しています。例えば、LZ77やLZ78といった辞書ベースの圧縮アルゴリズムや、その派生であるLZW符号化などは、情報源の統計量を明示的に推定するのではなく、繰り返される文字列（フレーズ）を利用してデータ内の冗長性を排除します。これらのアルゴリズムは、経験的に非常に優れた圧縮性能を示し、多くの場合において任意の定常エルゴード情報源に対して漸近的にエントロピー率を達成することが理論的に証明されています。この証明においても、系列が長くなるにつれて経験的な統計量が真の統計量に近づくというAEPの精神、あるいはより強力なエルゴード性の結果が重要な役割を果たします。
また、モデルベースの普遍符号化では、ある情報源モデルのクラスを仮定し、観測データに対して最もフィットするモデルを推定しながら符号化を行います。このようなアプローチにおいても、シャノンが提示した情報源のエントロピー率という概念と、AEPに代表される「長い系列の確率的典型性」に関する洞察が、理論的な性能限界やアルゴリズム設計の指針となっています。
結論
クロード・シャノンの情報源理論、特にエントロピー率と漸近等分割性(AEP)は、情報源の統計的性質が既知である場合の符号化理論だけでなく、情報源のモデルが不明である場合のデータ圧縮、すなわち普遍符号化の理論的な基盤を築きました。AEPが明らかにした「ほとんどすべての」長い系列が持つ確率的な規則性は、情報源の具体的な確率分布を知らなくても、観測データからその統計的性質を推定し、漸近的に最適な圧縮を達成できる可能性を示唆しました。
シャノンの原論文『A Mathematical Theory of Communication』において、これらの概念は情報源の数学的なモデル化と、そのモデルに対する理想的な符号化の限界を示すために導入されましたが、その本質は、データが長くなるにつれて現れる普遍的な統計的性質にあります。この普遍性が、その後の情報圧縮技術、特に普遍符号化の発展において、理論的な洞察と証明の強力なツールとして活用されていくことになります。シャノンの理論は、現代のデータ圧縮アルゴリズムの設計や解析においても、その重要性を失っていません。