シャノン研究ノート - クロード・シャノンによる離散情報源のエントロピー率：定義、性質、そしてソース符号化への意義

クロード・シャノンによる離散情報源のエントロピー率：定義、性質、そしてソース符号化への意義

Tags: 情報理論, エントロピー, ソース符号化, 確率過程, 定常性, エルゴード性

はじめに：情報源の「レート」を測る必要性

クロード・シャノンの情報理論の基礎は、情報を定量的に扱う枠組みを提供したことにあります。その中心概念の一つが「エントロピー」であり、これは離散的な確率変数が持つ不確実性、あるいは情報量を測る尺度として導入されました。しかし、通信やデータ貯蔵において我々が扱うのは、単一の確率変数ではなく、時系列にわたる一連のシンボル列、すなわち確率過程によって生成される情報源です。このような情報源が単位時間あたりに生成する情報の「レート」を測るためには、単なるエントロピーの概念を拡張する必要があります。

シャノンは、その記念碑的な論文 "A Mathematical Theory of Communication" において、この情報源のレートを定量化するために「エントロピー率（Entropy Rate）」の概念を定式化しました。これは、ある情報源から得られるシンボル系列の平均的な情報量を単位シンボルあたり、あるいは単位時間あたりで定義するものです。エントロピー率は、その情報源を可逆的に圧縮（符号化）する際の理論的な最小レートを示す量であり、情報源符号化理論の根幹をなす概念です。

本記事では、シャノンが導入した離散情報源のエントロピー率について、その厳密な定義、数学的な性質、そして情報源符号化、特にソース符号化定理におけるその意義を詳細に掘り下げていきます。ターゲット読者である情報科学分野の研究者の皆様が、情報源の統計的性質と情報量の関係性について深い理解を得られることを目指します。

離散情報源の確率モデルとエントロピー率の定義

シャノンは、情報源から出力されるシンボル列を、時間的にインデックス付けされた離散的な確率変数系列、すなわち離散時間確率過程としてモデル化しました。情報源は、アルファベット $\mathcal{A}$ から取られるシンボル $X_1, X_2, X_3, \dots$ を出力します。ここで、各 $X_i$ は確率変数であり、系列全体 ${X_i}_{i=1}^\infty$ は確率過程を構成します。

情報源のエントロピー率を定義するために、シャノンは長さ $n$ のシンボル列 $X_1, X_2, \dots, X_n$ に着目しました。この長さ $n$ のブロックに対する結合エントロピー $H(X_1, \dots, X_n)$ は、次のように定義されます。

$$ H(X_1, \dots, X_n) = -\sum_{x_1 \in \mathcal{A}} \dots \sum_{x_n \in \mathcal{A}} P(x_1, \dots, x_n) \log_b P(x_1, \dots, x_n) $$

ここで $P(x_1, \dots, x_n)$ は特定の系列 $x_1, \dots, x_n$ が出現する結合確率であり、$\log_b$ の底 $b$ は情報の単位（ビットやナットなど）を決定します。通常は $b=2$ でビット単位を用います。

シャノンは、長さ $n$ のブロックあたりの平均エントロピー $H(X_1, \dots, X_n)/n$ を考え、情報源のエントロピー率を、この値の $n \to \infty$ における極限として定義しました。

定義1 (エントロピー率 $H$): 離散時間確率過程 ${X_i}_{i=1}^\infty$ によって生成される情報源のエントロピー率 $H$ は、もし極限が存在するならば、次で与えられます。

$$ H = \lim_{n \to \infty} \frac{1}{n} H(X_1, \dots, X_n) $$

この定義は直感的です。長いブロックを考えることで、情報源におけるシンボル間の相関や構造が考慮され、単位シンボルあたりに真に固有な不確実性の平均値が抽出されると考えられます。

しかし、この極限が常に存在するとは限りません。シャノンは、情報源が特定の統計的性質、特に定常性とエルゴード性を持つ場合に、エントロピー率がより扱いやすい形で定義でき、かつ存在することを示唆しました。

定義2 (定常性): 確率過程 ${X_i}{i=1}^\infty$ が定常であるとは、任意の $k \ge 1$ および任意の時間シフト $\tau$ に対して、結合確率分布がシフト invariance を持つこと、すなわち $P(X{i_1}, \dots, X_{i_k}) = P(X_{i_1+\tau}, \dots, X_{i_k+\tau})$ がすべての $i_1, \dots, i_k$ について成り立つことをいいます。

定常情報源の場合、長さ $n$ のブロックエントロピー $H(X_1, \dots, X_n)$ は $H_n$ と書かれることがあります。シャノンは定常情報源に対して、別の、しばしばより有用なエントロピー率の定義も提示しました。

定義3 (エントロピー率 $H'$): 定常情報源 ${X_i}_{i=1}^\infty$ のエントロピー率 $H'$ は、条件付きエントロピーの極限として定義されます。

$$ H' = \lim_{n \to \infty} H(X_n | X_1, \dots, X_{n-1}) $$

ここで $H(X_n | X_1, \dots, X_{n-1}) = H(X_1, \dots, X_n) - H(X_1, \dots, X_{n-1})$ です。定常性により $H(X_1, \dots, X_n) \le n H(X_1)$ および $H(X_n | X_1, \dots, X_{n-1}) \ge 0$ が成り立ちます。また、条件付きエントロピーの系列 $H(X_n | X_1, \dots, X_{n-1})$ は $n$ に関して単調非増加であることが示されます。非増加で下に有界（0で下界）であるため、この極限 $H'$ は常に存在します。

シャノンは、定常情報源に対して、先の二つの定義によるエントロピー率が等しいこと、$H=H'$ であることを示しました。これは、長さ $n$ のブロックあたりの平均エントロピーの極限と、過去のシンボル全てが与えられた下での次のシンボルの不確実性の極限が一致するという、重要な結果です。

主要な性質とエルゴード性

エントロピー率の概念が特に強力になるのは、情報源が定常であるだけでなく、エルゴード性も持つ場合です。

定義4 (エルゴード性): 定常確率過程 ${X_i}_{i=1}^\infty$ がエルゴードであるとは、長い時間平均が集合平均に一致する、という性質を大まかに表現します。より厳密には、時間シフトに対して不変なイベントの確率が0または1であることなどを指します。情報理論においては、特定のシンボル系列の出現頻度が、系列長を無限大にしたときにその系列の確率に収束するという意味合いで使われることが多いです。

エルゴード性を持つ定常情報源は、定常エルゴード情報源 (Stationary Ergodic Source) と呼ばれます。多くの実際の情報源（例えば、十分に長い自然言語のテキスト、特定の通信システムからの出力など）は、理想化されたモデルとして定常エルゴード情報源と見なすことができます。

定常エルゴード情報源に対しては、エントロピー率は特に重要な意味を持ちます。シャノンの漸近等分割性（Asymptotic Equipartition Property, AEP）が成り立ち、長さ $n$ の系列のうち、確率的に「典型的な」系列が約 $2^{nH}$ 個存在し、他の系列は無視できる確率しか持たないことが示されます。ここで $H$ はエントロピー率です。

AEPは、エントロピー率が情報源が生成する「本質的に異なる」系列の数（またはその対数）を単位シンボルあたりで定量化していることを示唆します。この性質は、情報源符号化定理の証明において核心的な役割を果たします。

特定の情報源クラスに対するエントロピー率は具体的に計算できます。例えば：

記憶のない情報源 (Memoryless Source): 各シンボル $X_i$ が独立同分布 (i.i.d.) である場合、情報源は定常であり、エルゴード性も満たします。この場合、エントロピー率は単に各シンボルのエントロピーに等しくなります。 $H = H(X_1) = -\sum_{x \in \mathcal{A}} P(x) \log_b P(x)$。ここで $P(x)$ は任意の $X_i$ が $x$ という値を取る確率です。
マルコフ情報源 (Markov Source): 各シンボル $X_n$ が、その直前の $k$ 個のシンボル $X_{n-k}, \dots, X_{n-1}$ にのみ依存する（$k$次のマルコフ鎖を形成する）場合、適切な条件下で定常かつエルゴードになり得ます。この場合のエントロピー率 $H$ は、直前の $k$ 個のシンボルが与えられた下での現在のシンボルの条件付きエントロピーの期待値として計算されます。 $H = -\sum_{x_1, \dots, x_k} P(x_1, \dots, x_k) \sum_{x_{k+1}} P(x_{k+1} | x_1, \dots, x_k) \log_b P(x_{k+1} | x_1, \dots, x_k)$ 特に1次の定常エルゴードマルコフ情報源の場合、$H = \sum_{s \in \mathcal{A}} P(X_i=s) H(X_{i+1} | X_i=s)$ となります。

ソース符号化への意義：シャノンのソース符号化定理

情報源エントロピー率の最も重要な意義は、シャノンのソース符号化定理 (Source Coding Theorem) と密接に関連している点です。この定理は、可逆的なデータ圧縮（情報源符号化）における基本的な限界を確立します。

シャノンのソース符号化定理 (可逆圧縮): シンボルアルファベット $\mathcal{A}$ を持つ定常エルゴード情報源のエントロピー率を $H$ とする。任意の $\epsilon > 0$ に対して、十分大きな $n$ を選ぶと、長さ $n$ の出力系列を平均して $nH(1+\epsilon)$ ビットで符号化できるブロック符号が存在する。逆に、情報源を平均して $nH(1-\epsilon)$ ビットで符号化するどんなブロック符号も、系列長 $n$ を無限大にしたときに復号誤り確率が0に収束することはない。

この定理は、エントロピー率 $H$ が、情報源を理想的に圧縮した場合の単位シンボルあたりの最小平均符号長であることを確立しています。言い換えれば、$H$ は情報源の「真の情報レート」であり、それ未満のレートでは忠実な復元（すなわち可逆圧縮）は原理的に不可能であるという限界を示しています。

ソース符号化定理は、理論的にはエントロピー率に arbitrarily close に圧縮できる可能性を示唆しますが、そのための効率的な符号構成法（例：ハフマン符号、算術符号など）は、定理の証明そのものとは区別される実用的な課題です。しかし、これらの符号化手法も、情報源の統計的性質（特にシンボルの出現確率や相関）を利用することで、理論的な限界であるエントロピー率に近づこうと設計されます。

歴史的背景と現代における位置づけ

シャノンが情報源のエントロピー率を定式化した背景には、通信における情報量の概念を確立するという彼の主要な目的がありました。情報を信号として送受信する際、情報源からどのようなレートで情報が生成されるかを定量的に把握することは、チャネルの容量との比較において不可欠です。エントロピー率は「情報源の容量」と見なすこともできます。

シャノンの仕事以前にも、マルコフ過程などの統計的モデルは研究されていましたが、それらが生成する「情報」の量を普遍的な尺度で測る枠組みは存在しませんでした。シャノンは、確率過程を情報源として捉え、エントロピーという概念を時間的な相関を持つ系列に拡張することで、この尺度を提供しました。特に、彼が言語の統計的性質を分析するためにエントロピー率を用いた研究（"Prediction and Entropy of Printed English" など）は、情報源モデルとしての確率過程の応用例としても先駆的です。

現代の情報科学において、離散情報源のエントロピー率および関連概念は、以下のような様々な分野で応用されています。

データ圧縮: ZIP, Gzip, JPEG-LS など、可逆圧縮アルゴリズムの性能評価や理論的限界の理解に不可欠です。より複雑な情報源モデル（例：文脈依存モデル）に基づく符号化も、エントロピー率の概念に深く根ざしています。
統計モデリング: 時系列データやシーケンスデータのモデリングにおいて、モデルがデータのエントロピー率をどの程度捉えているかは、モデルの性能を評価する指標の一つとなります。例えば、言語モデルにおいて、Perplexity（エントロピー率から導出される尺度）はモデルの予測能力を示す重要な指標です。
機械学習: 系列データ（テキスト、音声、DNA配列など）を扱う機械学習モデル（RNN, Transformerなど）は、実質的に情報源の統計構造を学習し、データのエントロピー率を下げる（予測精度を上げる）ことを目指しています。
情報理論の拡張: 条件付きエントロピー率、相互情報量率など、より複雑な情報源間、あるいは情報源とチャネル間の関係性を記述する概念へと発展しています。

情報源のエントロピー率は、情報源の持つ「真の情報量」を単位あたりで測る普遍的な尺度として、情報理論の基礎であり続け、現代の情報技術においてもその重要性は増しています。

結論：情報源の究極的な圧縮限界としてのエントロピー率

クロード・シャノンが導入した離散情報源のエントロピー率は、情報源が生成するシンボル系列の統計的性質から導かれる、単位シンボルあたりの平均的な情報量を定義する概念です。定常エルゴード情報源に対して、エントロピー率は長さ $n$ のブロックエントロピーを $n$ で割った値の極限、あるいは過去のシンボルが与えられた下での次のシンボルの条件付きエントロピーの極限として厳密に定義され、両者は一致します。

このエントロピー率は、シャノンのソース符号化定理によって、その情報源を可逆的に圧縮する際の理論的な最小平均符号長として確立されました。これは、情報源が持つ本質的な情報量を定量的に示す指標であり、どのような符号化手法を用いても、エントロピー率を下回る圧縮は不可能であることを意味します。

シャノンのこの貢献は、情報源の統計的性質を情報量という観点から捉え直し、データ圧縮という工学的課題に理論的な限界を与えるという点で画期的でした。情報源エントロピー率の概念は、それ自体が情報理論の基礎であると同時に、現代のデータ圧縮、統計モデリング、機械学習など、情報を扱う多くの分野における理論的基盤の一つとなっています。情報科学の研究者にとって、情報源のエントロピー率に関する深い理解は、これらの分野における研究を進める上で不可欠であるといえるでしょう。