シャノン研究ノート

クロード・シャノンによる情報源の分類とそのエントロピー：離散無記憶源、マルコフ源、定常源の分析

Tags: 情報理論, 情報源, エントロピー, マルコフ過程, 定常過程

はじめに：情報源のモデル化の重要性

情報理論は、情報がどのように測定され、通信され、蓄積されるかを探求する学問分野です。その基礎には、情報源（Source）の概念があります。情報源とは、メッセージやデータを生成する主体を指します。シャノンは、その画期的な論文「A Mathematical Theory of Communication」において、様々な種類の情報源を数学的にモデル化し、それぞれが持つ情報の不確実性を定量化する方法を示しました。

情報源を適切にモデル化することは、データ圧縮（ソース符号化）や通信路符号化の限界を理解し、効率的なシステムを設計するために不可欠です。情報源の統計的な特性を捉えることで、その情報源が発生させるメッセージ系列がどれだけ「圧縮可能」であるか、あるいはその生成プロセスがどれだけ「予測不可能」であるかを測ることができます。本記事では、シャノンが定義した主要な情報源モデル、特に離散無記憶情報源、離散マルコフ情報源、そしてより一般的な定常情報源に焦点を当て、それぞれの数学的な定義、特性、そしてエントロピー率という概念を中心に解説いたします。

離散無記憶情報源 (Discrete Memoryless Source, DMS)

最も単純な情報源モデルの一つが、離散無記憶情報源（DMS）です。これは、情報源が生成する各シンボルが、過去に生成されたシンボルとは独立に、ある固定された確率分布に従って発生すると仮定するモデルです。

定義

離散無記憶情報源は、アルファベット $\mathcal{X} = {x_1, x_2, \dots, x_k}$ 上で定義されます。各シンボル $x_i \in \mathcal{X}$ は、固定された確率 $P(X = x_i) = p_i$ で独立に発生します。ここで、$p_i \ge 0$ かつ $\sum_{i=1}^k p_i = 1$ です。情報源によって生成されるメッセージ系列は、独立同分布 (i.i.d.) な確率変数 $X_1, X_2, \dots, X_n, \dots$ の列として記述されます。すなわち、$P(X_1=x_{i_1}, X_2=x_{i_2}, \dots, X_n=x_{i_n}) = P(X_1=x_{i_1}) P(X_2=x_{i_2}) \dots P(X_n=x_{i_n}) = p_{i_1} p_{i_2} \dots p_{i_n}$ となります。

エントロピー

DMSの情報量を測る尺度として、エントロピーが用いられます。1つのシンボル $X$ のエントロピー $H(X)$ は、次のように定義されます。

$H(X) = - \sum_{i=1}^k p_i \log_b p_i$

ここで、$b$ は対数の底であり、通常は2が用いられます（単位はビット）。このエントロピーは、情報源が生成する1つのシンボルあたりの平均情報量、あるいは不確実性を表します。DMSの場合、各シンボルは独立であるため、長さ $n$ の系列 $X_1, \dots, X_n$ の結合エントロピー $H(X_1, \dots, X_n)$ は、$n$ 倍のシンボルエントロピーに等しくなります。

$H(X_1, \dots, X_n) = \sum_{j=1}^n H(X_j) = n H(X)$

DMSのエントロピー率は、長さ $n$ の系列の結合エントロピーを $n$ で割って $n \to \infty$ とした場合の極限として定義されます。

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

DMSの場合は、$H(\mathcal{S}) = H(X)$ となります。このエントロピー率 $H(X)$ が、ソース符号化定理によって保証される、可逆圧縮（損失なし圧縮）における1シンボルあたりの理論的な最小平均符号長となります。

離散マルコフ情報源 (Discrete Markov Source)

DMSではシンボルの発生が完全に独立であると仮定しましたが、現実の情報源（例えば、言語やテキスト）では、あるシンボルの発生確率はその直前のシンボル（あるいはそれ以前の複数のシンボル）に依存することが一般的です。離散マルコフ情報源は、このような記憶を持つ情報源をモデル化する枠組みを提供します。

定義

離散マルコフ情報源は、有限状態を持つマルコフ連鎖によって記述される情報源です。ここでは最も単純な、有限の状態を持つエルゴード的な1次マルコフ情報源を考えます。

アルファベット $\mathcal{X}$ 上で定義され、状態空間 $\mathcal{S} = {s_1, s_2, \dots, s_m}$ を持ちます。ただし、情報源によって生成されるシンボル $X_i$ は、その時点の状態 $S_i$ に依存します。簡単のため、シンボルと状態が一致すると考え、$S_i \in \mathcal{X}$ とします。

1次マルコフ情報源は、次の状態（またはシンボル）の確率が直前の状態（またはシンボル）のみに依存するという性質を持ちます。

$P(X_n = x_j | X_{n-1} = x_i, X_{n-2} = x_{i_{n-2}}, \dots) = P(X_n = x_j | X_{n-1} = x_i)$

この条件付き確率は遷移確率と呼ばれ、$p_{ij} = P(X_n = x_j | X_{n-1} = x_i)$ と表されます。遷移確率は時間によって変化しない（時間的に一様である）と仮定します。

情報源の初期状態に関する確率分布 $P(X_1=x_i)$ と、遷移確率行列 $P = [p_{ij}]$ によって、マルコフ情報源の統計的性質が完全に記述されます。定常マルコフ情報源の場合、初期状態分布は定常分布 $\pi = [\pi_1, \dots, \pi_k]$（ただし $\pi P = \pi$ かつ $\sum \pi_i = 1$）に設定されます。この場合、$P(X_n = x_i) = \pi_i$ となり、1シンボルあたりの周辺確率は時間によらず一定になります。

エントロピー率

マルコフ情報源の場合、シンボルは独立ではないため、DMSのように単一シンボルのエントロピーが情報源全体のエントロピー率を表すわけではありません。代わりに、系列が長くなるにつれて平均的にどれだけの不確実性が存在するかの極限を考えます。

マルコフ情報源のエントロピー率は、条件付きエントロピーを用いて定義されます。系列 $X_1, X_2, \dots$ に対して、エントロピー率は次で与えられます。

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

マルコフ情報源の場合、この極限は存在し、エルゴード的なマルコフ連鎖であれば、1次の条件付きエントロピーの期待値として計算できます。

$H(\mathcal{S}) = H(X_n | X_{n-1})$ for large $n$

より正確には、定常マルコフ情報源の場合、定常分布 $\pi = [\pi_1, \dots, \pi_k]$ を用いて次のように計算できます。

$H(\mathcal{S}) = \sum_{i=1}^k \pi_i H(X_n | X_{n-1} = x_i) = \sum_{i=1}^k \pi_i \left( - \sum_{j=1}^k p_{ij} \log_b p_{ij} \right)$

これは、各状態 $x_i$ にいるときに次に発生するシンボル $x_j$ の条件付きエントロピー $H(X_n | X_{n-1} = x_i)$ を、その状態の定常確率 $\pi_i$ で重み付け平均したものです。このエントロピー率は、マルコフ情報源に対するソース符号化の理論限界となります。

定常情報源 (Stationary Source)

離散無記憶情報源や離散マルコフ情報源は、より一般的な確率過程としての情報源の特殊なケースです。シャノンはさらに広いクラスとして定常情報源を定義し、そのエントロピー率の概念を導入しました。

定義

離散時間確率過程 ${X_n}_{n=\dots, -1, 0, 1, \dots}$ が定常であるとは、任意の整数 $m$ と任意の正の整数 $k$ に対して、同時確率分布が時間シフトに関して不変であること定義されます。すなわち、任意のアルファベット上のシンボル列 $x_1, \dots, x_k$ に対して、次が成り立ちます。

$P(X_1=x_1, \dots, X_k=x_k) = P(X_{1+m}=x_1, \dots, X_{k+m}=x_k)$

直感的には、情報源の統計的な性質が時間の経過によらず一定であるということです。DMSや定常分布を持つマルコフ情報源は、定常情報源の例です。

エントロピー率

一般的な定常情報源に対しても、エントロピー率 $H(\mathcal{S})$ が定義されます。これは、長さ $n$ の系列のエントロピー $H(X_1, \dots, X_n)$ を $n$ で割ったものの極限として定義されます。

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

この極限は、定常情報源の場合に存在することが知られています。さらに、このエントロピー率は次の条件付きエントロピーの極限とも等しくなります。

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

これは、過去の無限長の系列が与えられたときの、現在のシンボルの条件付きエントロピーの極限を意味します。直感的には、過去の情報によってどれだけ現在の不確実性が解消されるか、という度合いを示しています。過去の情報によって完全に予測可能な情報源（例えば、確定的な周期系列を生成する情報源）のエントロピー率はゼロとなります。

情報源モデル間の関係と歴史的意義

DMS、マルコフ情報源、定常情報源は、情報源が持つ「記憶」や「構造」の度合いに応じて階層をなすモデルと見なすことができます。DMSは最も単純で記憶を持たないモデルであり、マルコフ情報源は有限の過去のシンボルに依存する（有限の記憶を持つ）モデルです。定常情報源は、時間的な統計的性質の不変性という性質を持つ、より広範な確率過程のクラスです。

シャノンがこれらの情報源モデルを導入したことは、情報理論の発展において極めて重要な意義を持ちました。特に、言語のような複雑な情報源の統計的性質を捉え、そのエントロピーを推定しようとする試みは、情報理論が単なる通信工学の枠を超え、統計学や言語学、さらには後の計算機科学といった分野に影響を与える端緒となりました。シャノンは、英文のエントロピーを推定するために、マルコフモデルや人間の予測能力を用いた実験を行うなど、理論と実証を結びつける先駆的な研究も行いました。

これらのモデルに対するエントロピー率の定義は、情報源符号化定理の基礎を確立しました。エントロピー率は、可逆圧縮の理論的な限界を示し、ハフマン符号や算術符号といった後の効率的な圧縮アルゴリズム開発の指針となりました。

現代の情報科学における位置づけと応用

シャノンが導入した情報源モデルとそのエントロピー率の概念は、現代の情報科学においてもその重要性を失っていません。

これらの応用分野では、シャノンの基本的な情報源モデルを出発点としつつ、より複雑で現実の情報源の性質を捉えるための発展的なモデルが研究されています。しかし、情報源のもつ不確実性を定量化し、その生成プロセスを統計的に理解するという根本的な考え方は、シャノンの初期の研究から受け継がれています。

結論

クロード・シャノンが「A Mathematical Theory of Communication」で体系的に導入した様々な情報源モデル、特に離散無記憶情報源、マルコフ情報源、そして定常情報源は、情報理論の基礎を築きました。これらのモデルは、情報源が生成するメッセージの統計的な構造や記憶の度合いを数学的に捉えるための強力な枠組みを提供します。

各情報源モデルに対して定義されるエントロピー率は、その情報源が持つ不確実性や、可逆圧縮の理論的な限界を示す基本的な尺度となります。DMSにおける単一シンボルのエントロピー、マルコフ情報源における条件付きエントロピーに基づくエントロピー率、そして一般的な定常情報源における極限としてのエントロピー率は、情報源の特性に応じて情報量を定量化する方法を示しています。

シャノンのこれらの概念は、その後の情報理論の研究はもちろんのこと、データ圧縮、統計モデリング、機械学習、自然言語処理など、現代の情報科学の多くの分野における理論的な基盤として、今なお活発に利用され、発展しています。情報源の正確なモデル化とエントロピーの理解は、効率的な情報システムを設計し、情報の持つ可能性を最大限に引き出すために、今後も不可欠な研究課題であり続けるでしょう。

参考文献（示唆）

本記事で述べた情報源モデルとエントロピー率の定義や性質に関する詳細な数学的記述は、クロード・シャノンの原論文「A Mathematical Theory of Communication」の第 III 部「SOURCE CONSIDERATION」や、情報理論に関する標準的な教科書（例えば、Thomas M. Cover and Joy A. Thomas, "Elements of Information Theory"）に詳しく記述されています。特に、定常情報源に対するエントロピー率の存在証明や、エルゴード性との関連については、より高度な確率論やエルゴード理論の知識が必要となります。