シャノン研究ノート - クロード・シャノンによる情報源の冗長度：定義、計算、そして言語分析への応用

クロード・シャノンによる情報源の冗長度：定義、計算、そして言語分析への応用

Tags: 情報理論, エントロピー, 冗長度, 情報源符号化, 言語分析, シャノン

クロード・シャノンによる情報源の冗長度：定義、計算、そして言語分析への応用

クロード・シャノンの画期的な論文『A Mathematical Theory of Communication』において導入された情報理論の概念は、通信、データ圧縮、そして後の計算科学や統計学の基盤を築きました。その中でも、情報源の「冗長度」（Redundancy）という概念は、情報源が持つ統計的構造を理解し、効率的な符号化や分析を行う上で極めて重要な役割を果たします。本稿では、シャノンが定義した情報源の冗長度に焦点を当て、その数学的な定義、様々な情報源モデルにおける計算方法、そしてシャノン自身が行った言語分析への応用について掘り下げて解説します。

冗長度の定義とその意義

情報源のエントロピー $H$ は、その情報源が生成する記号列に含まれる不確実性、あるいは平均情報量を定量化する尺度です。エントロピーが高いほど、次に現れる記号の予測が難しく、情報源に含まれる情報量が多いと言えます。

アルファベット $\mathcal{X}$ 上の情報源を考えます。アルファベットのサイズを $|\mathcal{X}|$ とします。この情報源が全く構造を持たず、各記号が独立かつ一様に出現する場合、そのエントロピーは最大となり、その値は $\log_2 |\mathcal{X}|$ エントロピー単位（ビット/記号）となります。これは、各記号が出現確率 $1/|\mathcal{X}|$ で生成される無記憶情報源のエントロピーに等しくなります。

シャノンは、実際の情報源、特に自然言語のような情報源は、記号の出現確率が一様ではなかったり、記号間に統計的な依存関係があったりするため、そのエントロピーは最大エントロピーよりも小さくなることに注目しました。この最大エントロピーと実際のエントロピーとの差、あるいは最大エントロピーに対する実際のエントロピーの小ささを捉える概念が「冗長度」です。

情報源の持つ構造（例えば、記号間の相関や出現確率の偏り）によって、実際のエントロピー $H$ は最大エントロピー $H_{max} = \log_2 |\mathcal{X}|$ よりも小さくなります ($H \le H_{max}$)。このエントロピーの減少分こそが、情報源が持つ「冗長性」に起因すると考えられます。

シャノンは冗長度に関連するいくつかの尺度を定義しました。

絶対冗長度 (Absolute Redundancy): 情報源の絶対冗長度 $R$ は、その情報源の最大エントロピー $H_{max}$ と実際のエントロピー $H$ の差として定義されます。 $R = H_{max} - H = \log_2 |\mathcal{X}| - H$ この値は、情報源の構造によって「失われた」情報量、あるいは符号化において圧縮可能な情報量の目安を示します。単位はエントロピーと同じ（ビット/記号）です。
相対冗長度 (Relative Redundancy): 情報源の相対冗長度 $\bar{R}$ は、絶対冗長度を最大エントロピーで割ったものとして定義されます。 $\bar{R} = \frac{R}{H_{max}} = \frac{\log_2 |\mathcal{X}| - H}{\log_2 |\mathcal{X}|} = 1 - \frac{H}{\log_2 |\mathcal{X}|}$ この値は0から1の間の無次元量で、情報源が潜在的な情報量（最大エントロピー）に対してどれだけ冗長であるかを示します。$\bar{R}=0$ の場合、情報源は完全にランダム（最大エントロピー）であり、$\bar{R}=1$ の場合、情報源は完全に決定論的（エントロピーゼロ）であることを意味します。

冗長度は、情報源符号化（データ圧縮）の観点から非常に重要です。情報源符号化定理によれば、可逆圧縮の限界は情報源のエントロピー $H$ に等しくなります。つまり、記号あたり平均 $H$ ビットで符号化することが理論的に可能です。最大エントロピー $H_{max}$ に対してエントロピー $H$ が小さいということは、情報源が冗長であり、$H_{max} - H$ ビット/記号の冗長度があることを意味します。この冗長度こそが、データ圧縮によって削減できる量に相当します。冗長度が高い情報源ほど、より効率的に圧縮することが可能になります。

異なる情報源モデルにおけるエントロピーと冗長度

情報源のエントロピー $H$ は、情報源モデルに依存して計算されます。

離散無記憶情報源 (Discrete Memoryless Source, DMS): 各記号の生成が互いに独立であり、過去の記号に依存しない情報源です。アルファベット $\mathcal{X}$ の各記号 $x \in \mathcal{X}$ が確率 $p(x)$ で出現する場合、エントロピーは以下で与えられます。 $H(X) = -\sum_{x \in \mathcal{X}} p(x) \log_2 p(x)$ この場合、冗長度は $R = \log_2 |\mathcal{X}| - H(X)$ となります。
マルコフ情報源 (Markov Source): 次に生成される記号の確率が、直前の $k$ 個の記号（状態）にのみ依存する情報源です（$k$次マルコフ源）。定常なエルゴード的マルコフ源のエントロピー率（記号あたりの平均エントロピー）は、条件付きエントロピーを用いて以下のように定義されます。 $H(\mathcal{S}) = -\sum_{s_{k} \in \mathcal{X}^{k}} p(s_{k}) \sum_{x \in \mathcal{X}} p(x|s_{k}) \log_2 p(x|s_{k})$ ここで $s_{k}$ は長さ $k$ の記号列（状態）を表し、$p(s_k)$ はその状態の定常確率、$p(x|s_k)$ は状態 $s_k$ の次に記号 $x$ が出現する条件付き確率です。一般に、マルコフ源のエントロピー率は、同じアルファベットサイズを持つ無記憶源のエントロピーよりも小さくなります。この場合、冗長度は $R = \log_2 |\mathcal{X}| - H(\mathcal{S})$ となります。情報源の依存関係が強くなる（$k$が大きくなる）ほど、通常エントロピー率は低下し、冗長度は増加します。

より一般的な定常エルゴード情報源に対しては、漸近等分割性（AEP）により、記号列の長さを無限大にしたときのエントロピー率 $H(\mathcal{S}) = \lim_{n \to \infty} \frac{1}{n} H(X_1, \dots, X_n)$ が存在します。冗長度は常に $R = \log_2 |\mathcal{X}| - H(\mathcal{S})$ で定義されます。

冗長度が高いということは、情報源が持つ統計的構造が強い、すなわち予測可能性が高いことを意味します。これは、過去の記号列から次に現れる記号をある程度の確度で予測できるということです。

言語分析への応用と予測実験

シャノンは、情報源の冗長度という概念を用いて、特に英語のような自然言語の情報量を定量的に分析しました。彼は言語を、統計的な構造を持つ確率過程と見なし、そのエントロピー率を推定しようと試みました。言語が持つ統計的な構造（単語の出現頻度、文法、構文など）は、まさにその言語の冗長性に寄与します。

シャノンは英語のエントロピー率を推定するために、有名な「予測実験」を行いました。この実験は、人間が言語の統計的構造をどれだけ内的に学習しているかを利用するものです。実験では、被験者にある英文の一部を見せ、次に続く文字を予測させます。被験者が正しく予測できなかった場合に「情報」が発生したと考え、その頻度から英語の1文字あたりの平均エントロピーを推定しました。

具体的には、長い英文を用意し、最初の数文字だけを見せ、次にくる文字を被験者に予測させます。被験者は可能な文字を順番に挙げ、正解するまで続けます。例えば、"there is no place like ..." という文で、"there is no place like " まで見せた後に続く文字を予測させます。被験者が最初に 'h'、次に 'o'、そして 'm' と予測して初めて正解する場合、これは3回目の試行で正解したことになります。もし被験者が最適に予測しようと試みていると仮定すると、これは真の確率分布に基づいた予測の難しさを示唆します。

シャノンは、このような実験を通じて、英語の1文字あたりのエントロピー率がおよそ 1.0 から 1.5 ビット/文字程度であると推定しました。これは、26文字のアルファベット（大文字・小文字を区別しない場合）が完全にランダムに出現するときの最大エントロピー $\log_2 26 \approx 4.7$ ビット/文字と比較して非常に小さい値です。

この推定値に基づくと、英語の相対冗長度は以下のようになります。 $\bar{R}{English} = 1 - \frac{H{English}}{H_{max}} \approx 1 - \frac{1.0 \sim 1.5}{4.7} \approx 1 - (0.21 \sim 0.32) \approx 0.68 \sim 0.79$

これは、英語が約 70〜80% 程度の冗長度を持っていることを示唆します。この高い冗長度は、言語が持つ重要な特性に繋がります。

誤り訂正: 冗長度があることで、通信路ノイズや入力ミスによって一部の文字が失われたり間違ったりしても、文脈から元のメッセージを復元したり、誤りを検出したりすることが可能になります。例えば、"recei_e" という単語を見たとき、多くの人は真ん中の文字が "v" であると推測できます。これは英語の統計的構造（つまり冗長度）によるものです。
圧縮: 冗長度が高いということは、情報源が持つ統計的なパターンを利用してデータを圧縮できる余地が大きいことを意味します。英語テキストの圧縮率は、その冗長度に大きく依存します。
暗号解読: 冗長度は、言語を用いた暗号システムの脆弱性にも関連します。平文（例：英語）の統計的な偏りや構造（冗長性）を利用して、暗号文から元の平文を推定する手がかりを得ることができます。シャノンは、暗号システムの安全性を評価する上で、平文の冗長度と鍵空間の大きさがどのように関わるかを分析しました（「Communication Theory of Secrecy Systems」にて）。

シャノンの予測実験は、人間の認知能力と情報理論の概念を結びつけ、言語の統計的性質を明らかにする先駆的な研究でした。彼は異なる情報源モデル（0次近似：文字の出現頻度のみ考慮、1次近似：二連文字の頻度考慮、等）を用いて英語のエントロピー率を段階的に推定し、モデルの複雑さを増すにつれてエントロピー率が低下することを示しました。これは、言語が単なる文字のランダムな羅列ではなく、階層的な統計構造を持つことを裏付けています。

現代の情報科学における冗長度概念の意義

情報源の冗長度という概念は、現代の情報科学においてもその重要性を失っていません。

データ圧縮: JPEG、MP3、ZIPなどの現代的なデータ圧縮アルゴリズムは、様々な情報源（画像、音声、テキストなど）が持つ冗長性を効果的に削減することによって高い圧縮率を実現しています。情報源のエントロピーは、これらの圧縮技術の性能評価における理論的なベンチマークとなります。
自然言語処理: 自然言語の統計的モデリングは、音声認識、機械翻訳、テキスト生成などの分野で不可欠です。言語モデルの質は、言語のエントロピー率をどれだけ正確に捉えられるかに依存します。冗長度は、言語モデルの評価尺度の一つともなり得ます。
生物情報学: DNAやタンパク質の配列解析においても、配列内に存在する統計的なパターン（冗長性）を分析することが、機能的なモチーフの発見や進化的なプロセスの理解に繋がります。
異常検出: システムやデータの冗長度が予期せず変化することは、異常や不正行為の兆候である可能性があります。例えば、ネットワークトラフィックの冗長度を監視することで、異常なパターンを検出する手法があります。

結論

クロード・シャノンによって導入された情報源の冗長度という概念は、情報源が持つ統計的構造と、それに基づく予測可能性や圧縮可能性を定量的に捉えるための強力なツールです。最大エントロピーと実際のエントロピーの差として定義される冗長度は、データ圧縮の理論的限界を示すだけでなく、言語のような複雑な情報源の性質を理解するための鍵となります。

シャノン自身が行った英語の冗長度分析と予測実験は、情報理論の枠組みが単なる通信システムだけでなく、人間の認知や文化的な産物である言語の分析にも適用可能であることを示しました。冗長度概念は、現代の情報科学におけるデータ圧縮、自然言語処理、生物情報学など、多岐にわたる分野の研究開発において、今なお基礎的かつ重要な役割を果たし続けています。シャノンのこの洞察は、情報源の効率的な処理と深い理解に向けた探求の出発点と言えるでしょう。