クロード・シャノンによる情報源の確率過程モデル化：マルコフ情報源のエントロピーとその意義
はじめに
クロード・シャノンが1948年の画期的な論文 "A Mathematical Theory of Communication" [1] で情報理論の体系を確立した際、彼は通信システムのモデル化において、メッセージを生成する「情報源 (Information Source)」を確率過程として定式化しました。これは、それまでの通信技術が信号波形や物理的伝送に焦点を当てていたのに対し、メッセージ自体の統計的性質に着目するという、極めて重要な視点の転換でした。情報源の正確なモデル化は、データ圧縮の理論的限界を示すソース符号化定理や、通信路容量を議論する上でのメッセージ特性の理解に不可欠となります。
シャノンは、情報源を、あるアルファベット $\mathcal{A}$ から記号の列を生成する定常的な確率過程として定義しました。特に、記憶を持たない独立同分布の情報源（零次マルコフ情報源）から、有限の記憶を持つマルコフ情報源、さらにはより一般的なエルゴード情報源へと議論を展開しました。本稿では、シャノンがどのように情報源を確率過程として捉え、特に有限次マルコフ情報源のエントロピーをどのように定義・計算したのか、その数学的詳細と学術的な意義について掘り下げて解説します。
情報源の確率過程モデル
シャノン情報理論における情報源は、アルファベット $\mathcal{A}$（有限集合とする）上の記号列 $X_1, X_2, X_3, \dots$ を生成する確率過程 ${X_t}_{t=1}^\infty$ としてモデル化されます。ここで、$X_t$ は時刻 $t$ における出力記号を表す確率変数です。最も単純なモデルは、各時刻において記号が独立に、かつ同じ確率分布 $P(a)$ で生成される独立同分布 (i.i.d.) 情報源です。
しかし、多くの実際的な情報源、例えば自然言語などは、前の記号に依存して次の記号の確率分布が変わる、すなわち記憶を持つ性質があります。シャノンはこのような情報源を扱うために、より一般的な確率過程の概念を導入しました。重要なのは、「定常性」と「エルゴード性」という性質です。
- 定常性 (Stationarity): 記号列の確率分布が時間のシフトに対して不変である性質です。すなわち、任意の $k \ge 1$ と任意の時刻 $t_1, \dots, t_k$ およびシフト $\tau$ に対して、同時確率分布が $P(X_{t_1}=x_1, \dots, X_{t_k}=x_k) = P(X_{t_1+\tau}=x_1, \dots, X_{t_k+\tau}=x_k)$ となる場合を定常情報源と呼びます。シャノンの情報源符号化定理は、基本的に定常情報源に対して定式化されています。
- エルゴード性 (Ergodicity): 時間平均がアンサンブル平均に等しくなる性質です。情報源の文脈では、十分に長い記号列を観測すれば、その記号列内での記号や記号パターンの出現頻度が、情報源の統計的な確率分布を代表するようになる性質を指します。シャノンのソース符号化定理の重要な要素である漸近等分割性 (AEP) [2] は、エルゴード情報源に対して成立します。
マルコフ情報源
定常情報源の重要なクラスとして、有限次マルコフ情報源があります。これは、ある時刻における記号の生成確率が、直前の有限個の記号のみに依存する情報源です。$m$ 次マルコフ情報源 ${X_t}$ は、任意の $t$ と任意の記号列 $x_1, \dots, x_t$ に対して、次の条件を満たします。
$P(X_t = x_t | X_{t-1}=x_{t-1}, \dots, X_1=x_1) = P(X_t = x_t | X_{t-1}=x_{t-1}, \dots, X_{t-m}=x_{t-m})$
特に、1次マルコフ情報源は $P(X_t = x_t | X_{t-1}=x_{t-1}, \dots, X_1=x_1) = P(X_t = x_t | X_{t-1}=x_{t-1})$ が成り立ちます。0次マルコフ情報源は、記憶を持たないi.i.d.情報源に他なりません。
定常なマルコフ情報源は、その状態（直前の $m$ 個の記号の列）に関する定常分布を持つ必要があります。このような情報源はエルゴード的である場合が多いですが、複数の「エルゴード的な部分」を持ち、非エルゴード的になる場合もあります（例えば、異なる状態セット間で遷移しない場合）。
マルコフ情報源のエントロピー
シャノンは情報源のエントロピーレートを、単位時間あたりに生成される平均情報量として定義しました。定常な確率過程 ${X_t}$ のエントロピーレート $H({X_t})$ は、極限として次のように定義されます。
$H({X_t}) = \lim_{n \to \infty} \frac{1}{n} H(X_1, \dots, X_n)$
ここで $H(X_1, \dots, X_n)$ は $n$ 個の記号列 $X_1, \dots, X_n$ の結合エントロピーです。条件付きエントロピーの連鎖律を用いると、これは以下と同等であることが示されます。
$H({X_t}) = \lim_{n \to \infty} H(X_n | X_{n-1}, \dots, X_1)$
直感的には、この極限は十分に長い過去の情報が与えられた場合に、次の記号が持つ不確実性の平均値を表します。
$m$ 次定常マルコフ情報源の場合、この極限は簡単に計算できます。なぜなら、任意の $n > m$ に対して、マルコフ性により $H(X_n | X_{n-1}, \dots, X_1) = H(X_n | X_{n-1}, \dots, X_{n-m})$ が成り立つためです。さらに定常性より、十分に大きな $n$ に対してこの条件付きエントロピーの値は一定の値に収束します。したがって、$m$ 次定常マルコフ情報源のエントロピーレート $H_m$ は、次のように与えられます。
$H_m = H(X_n | X_{n-1}, \dots, X_{n-m}) \quad \text{for } n > m$
この条件付きエントロピーは、直前の $m$ 個の記号列 $s = (x_{n-m}, \dots, x_{n-1})$ を状態として、状態 $s$ が与えられた下での次の記号 $x_n$ の不確実性の平均として計算できます。すなわち、状態 $s$ の定常確率分布を $P(S=s)$ とし、状態 $s$ の下で次の記号が $x$ となる遷移確率を $P(X_n=x | S=s)$ とすると、
$H_m = \sum_{s \in \mathcal{A}^m} P(S=s) H(X_n | S=s) = \sum_{s \in \mathcal{A}^m} P(s) \sum_{x \in \mathcal{A}} -P(x|s) \log_2 P(x|s)$
ここで $P(s)$ はマルコフ過程の定常分布における状態 $s=(x_{n-m}, \dots, x_{n-1})$ の確率であり、$P(x|s)$ は状態 $s$ から記号 $x$ への遷移確率です。
特に1次マルコフ情報源の場合、エントロピーレート $H_1$ は次のように計算できます。
$H_1 = \sum_{i \in \mathcal{A}} P(X_{t-1}=i) \sum_{j \in \mathcal{A}} -P(X_t=j | X_{t-1}=i) \log_2 P(X_t=j | X_{t-1}=i)$
ここで $P(X_{t-1}=i)$ は定常分布における記号 $i$ の確率、$P(X_t=j | X_{t-1}=i)$ は $i$ の後に $j$ が続く遷移確率です。
非エルゴードな定常情報源の場合、時間平均であるエントロピーレートの極限は存在するものの、単純な状態エントロピーとして計算できない場合があります。しかし、そのような情報源はエルゴード的な複数の部分に分解できるため、それぞれの部分のエントロピーレートの凸結合として扱うことが可能です。シャノンのAEPは、このような場合にも平均的な挙動の限界を示唆します。
歴史的背景と意義
シャノンが情報源を確率過程としてモデル化したことは、通信理論における抽象化のレベルを大きく引き上げました。それ以前の通信工学は、主に物理的な信号や回路の設計に注力しており、メッセージの内容そのものの統計的構造は体系的に扱われていませんでした。
シャノンは、電信システムにおけるモールス符号や、英語の単語や文字の統計的性質を分析する中で、メッセージが単純なi.i.d.過程ではないことを認識しました。特に、自然言語は強い統計的依存性（記憶）を持ちます。彼がマルコフ過程を情報源のモデルとして導入したことは、このような記憶を持つ情報源を数学的に扱い、その「情報量」や「冗長度」を定量化するための強力な枠組みを提供しました。
"A Mathematical Theory of Communication" の Part I では、情報源のモデルとして独立選択、マルコフ過程、さらに階層的なマルコフ過程（例えば、英文を文字レベルだけでなく単語レベルでも考える場合など）を提示しています [1, p. 10ff]。彼は、これらのモデルを用いて英文のエントロピーを推定する興味深い実験も行いました [1, p. 50ff]。これは、後の自然言語処理における統計的言語モデル（特にN-gramモデル）の礎となりました。
情報源を確率過程としてモデル化し、そのエントロピーレートを定義・計算可能にしたことで、シャノンは情報源符号化定理（ソース符号化定理）を定式化することが可能になりました。この定理は、平均符号長の情報源エントロピーレートへの収束を示し、可逆圧縮の理論的な限界を与えました。これは、どのような情報源であっても、その統計的性質（特にエントロピーレート）によって、どれだけ効率的に圧縮できるかが決まるという、普遍的な原理を確立したのです。
現代の情報科学における位置づけと応用
シャノンによる情報源の確率過程モデル化の考え方は、現代の情報科学の様々な分野でその影響を見ることができます。
- データ圧縮: Lempel-Ziv (LZ) アルゴリズムやPrediction by Partial Matching (PPM) のような現代的な可逆圧縮アルゴリズムは、本質的に入力データをマルコフ情報源やより複雑な確率過程と見なし、その統計的構造を利用して予測と符号化を行っています。PPMなどは、文脈（直前の記号列）に応じて予測確率を適応的に学習し、より高次のマルコフモデルに近い振る舞いをします。
- 自然言語処理: シャノンの英文のエントロピー推定の試みは、統計的言語モデルの初期の例です。N-gramモデル（これはN-1次マルコフ過程に対応します）は、長らく自然言語処理の基盤技術として利用されてきました。現代のニューラル言語モデル（例: RNN, Transformer）も、より洗練された形で単語や系列間の依存性（記憶）を学習するものであり、その根底には情報源を確率過程としてモデル化するというシャノンの考え方があります。
- 時系列分析: 株式市場のデータ、気候データ、脳波信号など、時系列データのモデリングにおいて、マルコフ過程やより複雑な確率過程（例: 隠れマルコフモデル HMM）が広く用いられています。これらのモデルは、過去のデータに基づいて将来を予測したり、データの生成メカニズムを理解したりするために不可欠です。HMMは、マルコフ過程に「隠れた状態」を導入したものであり、シャノンの情報源モデルの豊かな発展形と言えます。
- 機械学習: 強化学習におけるマルコフ決定過程 (MDP) は、環境の状態遷移をマルコフ性を持つものとしてモデル化します。また、ベイジアンネットワークやグラフィカルモデルなどの確率モデルも、変数の間の依存関係を表現する際に確率過程の概念を利用します。
結論
クロード・シャノンによる情報源の確率過程モデル化は、情報理論の基礎を築く上で極めて重要な概念でした。情報源を単なる信号発生器としてではなく、統計的な性質を持つ確率過程として捉え直すことで、彼は情報量や冗長度を定量化し、データ圧縮の普遍的な限界を示すソース符号化定理を導出することができました。特に、有限次マルコフ情報源の定式化とそのエントロピー計算は、記憶を持つ情報源の扱いを可能にし、自然言語処理やデータ圧縮といった分野に直接的な影響を与えました。
シャノンのこの貢献は、情報源の統計的構造の理解が、効率的な情報伝送と処理の鍵であることを明確に示しました。確率過程としての情報源という概念は、その後、より複雑なモデルへと発展しながらも、情報科学の多くの領域で基本的な枠組みとして受け継がれています。現代の情報技術を深く理解するためには、シャノンがどのように情報源をモデル化し、その統計的性質を分析したのかを正確に把握することが不可欠であると言えるでしょう。
参考文献
[1] Shannon, C. E. (1948). A mathematical theory of communication. Bell System Technical Journal, 27(3), 379-423. (Part I: Discrete noiseless systems) [2] Cover, T. M., & Thomas, J. A. (2006). Elements of information theory. John Wiley & Sons. (Chapter 3: Asymptotic Equipartition Property)