シャノン研究ノート - クロード・シャノンによる確率過程としての情報源：出力系列の確率と漸近等分割性 (AEP) の関係

クロード・シャノンによる確率過程としての情報源：出力系列の確率と漸近等分割性 (AEP) の関係

Tags: 情報理論, クロード・シャノン, 情報源符号化, 漸近等分割性 (AEP), 確率過程

はじめに：情報源の確率過程モデルと情報源符号化定理の基盤

クロード・シャノンの記念碑的な論文『A Mathematical Theory of Communication』において、情報源はメッセージを生成するエンティティとして定義されました。特に、離散的なシンボルを時間的に連続して生成する情報源は、確率過程として厳密に定式化されました。この確率過程としての情報源の理解は、情報源符号化定理（Source Coding Theorem）の確立に不可欠な基盤を提供します。

情報源符号化定理は、情報を効率的に圧縮するための理論的な限界を示しますが、その証明の核心部分には、情報源が生成する「長い系列の統計的性質」に関する洞察があります。この性質は、後に「漸近等分割性 (Asymptotic Equipartition Property; AEP)」として知られるようになり、シャノン情報理論全体の様々な証明技術において中心的な役割を果たすことになります。

本記事では、シャノンが情報源をどのように確率過程としてモデル化したかを確認し、特にその出力する系列の確率が系列長に対してどのように振る舞うかに焦点を当てます。そして、この系列の確率挙動を特徴づける漸近等分割性（AEP）が、情報源のエントロピー率といかに密接に関わっているかを詳細に解説し、情報源符号化定理への示唆を議論します。

確率過程としての離散情報源

シャノンが主に扱った離散情報源は、有限または可算個のシンボル集合 $\mathcal{X}$ からシンボルを生成します。時間インデックス $i$ における出力シンボルを確率変数 $X_i$ とすると、情報源の出力は確率変数の系列 $X_1, X_2, \dots, X_n, \dots$ として表現されます。これはまさに確率過程 $(X_i)_{i \ge 1}$ です。各 $X_i$ はシンボル集合 $\mathcal{X}$ 上の値を取ります。

情報源の統計的性質は、この確率過程の結合確率分布によって記述されます。すなわち、任意の有限長の系列 $x_1, x_2, \dots, x_n$ ($x_i \in \mathcal{X}$) が生成される確率 $P(X_1=x_1, \dots, X_n=x_n)$ です。通常、この確率を $P(x_1, \dots, x_n)$ と略記します。

シャノンの理論では、情報源として特に定常性 (Stationarity) とエルゴード性 (Ergodicity) を持つ確率過程が重要です。

定常性: 確率過程の統計的性質が時間のシフトによって変化しない性質です。厳密には、任意の $k \ge 1$ と任意の時間シフト $\tau$ に対して、結合確率分布が $P(X_{i_1}, \dots, X_{i_k}) = P(X_{i_1+\tau}, \dots, X_{i_k+\tau})$ を満たす場合を指します。広義には、任意の有限系列 $x_1, \dots, x_n$ と任意時間 $\tau$ に対して $P(X_1=x_1, \dots, X_n=x_n) = P(X_{1+\tau}=x_1, \dots, X_{n+\tau}=x_n)$ を満たす厳密定常性を指すことが多いです。これにより、長い系列の統計を時間の平均として捉えることが可能になります。
エルゴード性: 時間平均がアンサンブル平均に等しくなる性質です。定常な確率過程において、エルゴード性を持つ場合、十分に長い単一の系列から確率過程の統計的性質（例えばシンボルの出現確率や結合確率）を推定することが可能になります。シャノンの情報理論において、エルゴード性を持つ情報源を仮定することで、長い系列に関する平均的な性質（エントロピー率など）を議論することが意味を持ちます。

最も単純な情報源モデルは、各シンボルが独立かつ同分布に従って生成される離散無記憶情報源 (Discrete Memoryless Source; DMS) です。この場合、$P(x_1, \dots, x_n) = \prod_{i=1}^n P(x_i)$ となります。より複雑なモデルとして、シンボル生成確率が直前のシンボル（または複数のシンボル）に依存するマルコフ情報源があります。定常かつエルゴード的なマルコフ情報源は、シャノンの研究でも重要な役割を果たしました。

系列の確率とエントロピー率

情報源が生成する長さ $n$ の特定の系列 $x_1, \dots, x_n$ の確率は $P(x_1, \dots, x_n)$ です。情報源符号化の観点からは、この確率が高い系列ほど生成されやすく、低い系列ほど生成されにくいと考えられます。効率的な符号化は、出現しやすい系列には短い符号語を、出現しにくい系列には長い符号語を割り当てることで実現されます。

ここで、情報源の不確実性を定量化するエントロピーの概念が重要になります。長さ $n$ のブロック $X_1, \dots, X_n$ のエントロピーは、その結合確率分布に対するシャノンエントロピーとして定義されます： $H(X_1, \dots, X_n) = - \sum_{(x_1, \dots, x_n) \in \mathcal{X}^n} P(x_1, \dots, x_n) \log_b P(x_1, \dots, x_n)$ ここで $b$ は対数の底であり、通常は2が用いられ、単位はビットとなります。

定常な情報源に対しては、ブロックエントロピー $H(X_1, \dots, X_n)$ は $n$ に対して漸近的に線形に増加することが知られています。すなわち、極限 $\lim_{n \to \infty} \frac{1}{n} H(X_1, \dots, X_n)$ が存在します。この極限値が情報源のエントロピー率 (Entropy Rate) $h(\mathcal{X})$ です： $h(\mathcal{X}) = \lim_{n \to \infty} \frac{1}{n} H(X_1, \dots, X_n)$

エントロピー率 $h(\mathcal{X})$ は、長い系列においてシンボルあたりに平均して含まれる不確実性の量を示します。DMSの場合、$h(\mathcal{X}) = H(X_1)$ となります。マルコフ情報源の場合、$h(\mathcal{X}) = H(X_n | X_1, \dots, X_{n-1})$ の極限として定義され、これは定常分布における状態のエントロピーに依存します。

さて、AEPは、このエントロピー率と長い系列の確率 $P(x_1, \dots, x_n)$ がどのように関連するかを示します。

漸近等分割性 (AEP) の定理

定常かつエルゴードな離散情報源 $(X_i)_{i \ge 1}$ に対して、シャノン（あるいはより厳密な数学的定式化は McMillan など）は以下の漸近等分割性 (AEP) の定理を確立しました。

定理 (AEP): 定常かつエルゴードな離散情報源 $(X_i){i \ge 1}$ とそのエントロピー率 $h(\mathcal{X})$ に対して、系列 $X_1, \dots, X_n$ の確率 $P(X_1, \dots, X_n)$ は、確率 1 (almost surely) で以下の関係を満たします： $$ \lim{n \to \infty} -\frac{1}{n} \log P(X_1, \dots, X_n) = h(\mathcal{X}) $$ これは、十分に大きな $n$ に対して、典型的な系列 $x_1, \dots, x_n$ の確率は約 $2^{-nh(\mathcal{X})}$ であることを意味します（底を2とした対数を使用する場合）。より厳密には、任意の $\epsilon > 0$ に対して、十分に大きな $n$ を取ると、以下の性質を持つ系列の集合 $A_n^*$ が存在します。

その集合に属する各系列 $x_1, \dots, x_n$ について、エントロピー率からのずれが小さい： $| -\frac{1}{n} \log P(x_1, \dots, x_n) - h(\mathcal{X}) | \le \epsilon$ これは、$2^{-n(h(\mathcal{X})+\epsilon)} \le P(x_1, \dots, x_n) \le 2^{-n(h(\mathcal{X})-\epsilon)}$ と同等です。
情報源が生成する系列がこの集合 $A_n^$ に属する確率は、1に任意に近づけることができます： $P((X_1, \dots, X_n) \in A_n^) > 1 - \epsilon$
この集合 $A_n^$ のサイズ $|A_n^|$ は、指数関数的に増加し、その増加率はエントロピー率によって決まります： $(1-\epsilon) 2^{n(h(\mathcal{X})-\epsilon)} \le |A_n^| \le 2^{n(h(\mathcal{X})+\epsilon)}$ 特に、$|A_n^| \approx 2^{nh(\mathcal{X})}$ となります。

この集合 $A_n^$ は典型的集合 (Typical Set)* と呼ばれます。AEPは、十分に長い系列について、情報源が生成する可能性のあるすべての系列（サイズ $|\mathcal{X}|^n$）の中で、そのほとんどが比較的狭い Typical Set に集中し、かつその Typical Set に属する系列はほぼ等しい確率（約 $2^{-nh(\mathcal{X})}$）で出現するという驚くべき性質を示しています。

系列の確率分布の集中

AEPが示唆するのは、長い系列の確率分布は、単純な指数関数 $2^{-nh(\mathcal{X})}$ の形で非常に狭い領域に集中するということです。直感的には、短い系列ではその確率に大きなばらつきがあり得ますが、系列が長くなるにつれて、「平均的な振る舞い」を示す系列の確率が支配的になります。この「平均的な振る舞い」とは、各シンボルやシンボル列の出現頻度が、情報源の定常分布や結合分布に近づくことによって特徴づけられます。

例えば、DMSの場合、系列 $x_1, \dots, x_n$ 中のシンボル $a \in \mathcal{X}$ の出現回数を $N(a)$ とすると、大数の法則により、十分大きな $n$ に対して $N(a)/n \approx P(a)$ となります。このとき、系列の確率は $P(x_1, \dots, x_n) = \prod_{i=1}^n P(x_i) = \prod_{a \in \mathcal{X}} P(a)^{N(a)}$ となります。 $-\frac{1}{n} \log P(x_1, \dots, x_n) = -\frac{1}{n} \sum_{a \in \mathcal{X}} N(a) \log P(a) = - \sum_{a \in \mathcal{X}} \frac{N(a)}{n} \log P(a)$ は、大数の法則により $-\sum_{a \in \mathcal{X}} P(a) \log P(a) = H(X_1) = h(\mathcal{X})$ に収束します。これはDMSに対するAEPの簡単な例です。定常エルゴード情報源に対するAEPは、エルゴード定理を用いてより一般的な確率過程に拡張されます。

Typical Set 以外の系列（非典型的系列）の確率は、Typical Set の系列に比べて非常に小さいことが、AEPの性質3（Typical Set の確率が1に近いこと）から導かれます。したがって、情報源が生成するほとんど全ての系列は Typical Set に属し、これらの系列のみを考えれば情報源の挙動をほぼ完全に捉えられることになります。

情報源符号化定理への示唆

AEPは、情報源符号化定理の理解と証明に直接的に寄与します。情報源符号化定理は、可逆圧縮（ソース符号化）において、シンボルあたりの平均符号長が情報源のエントロピー率 $h(\mathcal{X})$ 以上でなければならないことを示します。すなわち、符号長 $L(x_1, \dots, x_n)$ を持つ符号を考えたとき、平均符号長 $\frac{1}{n} E[L(X_1, \dots, X_n)]$ は $h(\mathcal{X})$ に任意に近づけることができますが、これより小さくすることはできません。

この定理の可達性（achievability）の証明において、Typical Set を利用するアプローチが強力です。サイズが約 $2^{nh(\mathcal{X})}$ である Typical Set に属する系列には、それぞれ一意のインデックスを割り当てます。このインデックスを表すのに必要なビット数は、$\lceil \log_2 |A_n^*| \rceil \approx \log_2 (2^{nh(\mathcal{X})}) = nh(\mathcal{X})$ となります。非典型的系列は出現確率が非常に小さいので、これらには固定の長い符号語を割り当てるか、無視しても平均符号長への影響は少ないと考えられます（ただし、厳密な証明では非典型的系列の扱いも重要です）。

Typical Set に属する系列を符号化することで、シンボルあたりの平均符号長はほぼ $h(\mathcal{X})$ となります。AEPにより、系列長 $n$ が大きくなるほど、生成される系列が Typical Set に属する確率は1に近づくため、この符号化スキームは非常に高い確率で成功し、平均符号長は漸近的に $h(\mathcal{X})$ に近づきます。これが、情報源符号化定理の基本的な考え方の一つです。

歴史的意義と現代への影響

シャノンがAEPの概念を最初に導入したとき、それは必ずしも「AEP」という名前で体系的に定式化されていたわけではありませんでした。しかし、『A Mathematical Theory of Communication』の中で、彼は長い系列の対数確率 $-\frac{1}{n}\log P(x_1, \dots, x_n)$ がエントロピー率に収束するという性質を事実上利用しており、これが情報源符号化定理の証明を可能にしました。AEPのより厳密な数学的証明は、後にMcMillanによって提供されました。

AEPは、単に情報源符号化定理のためだけでなく、シャノン情報理論における多くの漸近的な結果（例えば、通信路符号化定理、レート歪み理論など）の証明において中心的な役割を果たしています。それは、確率過程の長時間平均がアンサンブル平均に収束するというエルゴード性の考え方を、情報理論的な量（特に $-\frac{1}{n}\log P(X_1, \dots, X_n)$ という「情報量」の時間平均）に応用したものです。

現代の情報科学において、AEPは引き続き情報理論の教育と研究の基本概念であり続けています。また、データ圧縮アルゴリズムの設計（例えば、算術符号化は、系列の確率に基づいて符号を割り当てる点でAEPの考え方と関連が深いです）や、統計的推論、機械学習における確率モデルの分析においても、長いデータ列の尤度や情報量に関する漸近的な性質を理解する上で重要な示唆を与えています。例えば、確率モデルの学習において、観測されたデータ系列がそのモデルにとってどの程度「典型的」であるか、すなわち尤度が高いか低いかといった分析は、AEPの考え方と通じる部分があります。

結論

クロード・シャノンによる情報源の確率過程としてのモデル化は、情報理論の数学的厳密性の礎となりました。特に、情報源が生成する長い系列の確率 $P(x_1, \dots, x_n)$ の漸近的な振る舞いを記述する漸近等分割性（AEP）は、情報源のエントロピー率 $h(\mathcal{X})$ がデータ圧縮の限界を定めることの深い理由を明らかにしました。

AEPは、無限に多様に見える長い系列の世界の中で、情報源が実際に生成する系列のほとんどが、エントロピー率によってその確率が規定される比較的少数の「典型的系列」に集中するという、強力な性質を示しています。この洞察は、情報源符号化定理を可能にしただけでなく、その後の情報理論研究における様々な漸近的結果の証明手法として広く応用されることになりました。

シャノンが確率論を用いて情報源の性質を深く洞察したことは、現代の情報科学、特にデータ圧縮、統計モデリング、機械学習といった分野における確率的アプローチの重要性を先駆的に示すものであり、AEPはその中でも特に美しい数学的な成果の一つと言えるでしょう。