情報理論の基礎(2)

最初に,情報理論においてもっとも基本的な概念であるエントロピー(entropy)を導入します。
エントロピーは,確率変数,あるいは,それを生成する情報源の持つ不確実性を表す尺度であると考えることができます。

Xを有限集合{\cal X}上の確率変数とします。
確率変数Xは,確率関数(probability mass function) p_{X}(x)={\mathbb P}\{ X = x \}, x \in {\cal X}を持つことにします。

今後,特に必要のない限りは,表記の簡便性のために確率関数をp_{X}(x)のような表記ではなく,p(x)のような表記で表すことにします。
したがって,p(x)p(y)はそれぞれ異なる確率変数X, Yに対する確率関数で,それぞれp_{X}(x), p_{Y}(y)の意味であるとします。

このときエントロピーは以下のように定義されます。

 

定義
離散確率変数XのエントロピーH(X)

 H(X) = - \sum_{x \in {\cal X}} p(x) \; \log p(x)={\mathbb E}[\log \frac{1}{p(X)} ]

によって定義される。

 

上記のエントロピーは,確率関数pの汎関数(functional)で
(すなわち,確率関数pから実数(後で示すように,この場合は,非負の実数)への写像),pに依存していることを強調するときはH(p)と表記するときもあります。

情報理論においては,対数\logの底はeではなくて,2にとることが多いです。これは,現代のディジタル通信においては”0″, “1”の2値で通信が行われることが多く,対数\logの底を2として定義したエントロピーは,2値で通信が行われる場合のXを定めることができる平均符号長の下限を表すことになるからです。

このブログの情報理論に関する記事では、特に断りのない限りは対数の底は2であるとします。しかしながら,対数\logの底はどのような値にとっても理論自体には全く関係がありません。
対数\logの底を2にとって定義したエントロピーの単位は“bit(ビット)”と呼ばれます。また,対数\logの底をeにとって定義したエントロピーの単位は“nat(ナット)”と呼ばれます。底をbにしたときのエントロピーをH_{b}(x)と表すことにし,b=2の場合は省略することにします。

また、表記の簡便性のために,0 \log 0 =0とします。このことは,x \rightarrow 0のときx \log x \rightarrow 0であるので(ロピタルの定理を使って示せます),連続性から正当化できます。
したがって,確率0の項を付け加えてもエントロピーは変化しないことになります。

最後にもう一度,エントロピーは確率変数Xの分布の汎関数である
ことに注意しましょう。したがって,エントロピーは,確率変数Xの実現値には依存せず,それぞれの値の実現確率にだけに依存します。

 

情報理論の基礎(1)

情報理論は,「通信」に関連して出てくる以下の2つの最も根源的な問いに答えるための理論です。

  • データは,究極的にはどこまで圧縮可能なのか? (答え: エントロピー)
  • 通信において,究極的にはどこまでの伝送速度を達成できるのか? (答え: チャネル容量)

このことから,情報理論は通信理論の一部であると考えることができます。
しかしながら, 情報理論は,統計物理(熱力学),コンピュータサイエンス(コルモゴロフ複雑性(Kolmogorov complexity)あるいはalgorithmic complexity),統計的推測(Occam’s Razor: “The simplest explanatoin is best”),確率統計(最適な仮説検定と推定)などの諸問題とも深く関連しており,広大な広がりを持った理論です。

このブログでは[1]の参考文献を参考にしながら,情報理論の基礎に関する記事をこれから書いていくことにします。

[参考文献]

[1]  T.  M. Cover and J. A. Thomas,  Elements of Information Theory, Second Edition, Wiley, 2006.