18.7.1 情報量と平均情報量 (エントロピー)

計算機の中ではすべての情報がビット列で表現されています． しかし符号化の仕方は決して 1 通りではありません．この節では「どのような符号化をすれば効率良く情報を記録できるか」という問題に焦点を当ててみたいと思います．
たとえば，出席簿の記録を考えてみます． 仮に出席ないし欠席のみを表現したいのであれば，次の対応表のようにして 1 ビットを使えば十分です．

出席と欠席に加えて遅刻や早退の記録も残すなら， たとえば次のように 2 ビットのビット列で表現する方法があります．

この符号を使って n 回の出欠を記録すると， 2n ビットのデータが作られます． 仮に 5 回の授業に出席したとすると 1 が 10 個並んだビット列になりますし， 13 回出席したとすると 1 が 26 個並びます．
さて，この符号化は最適な符号化なのでしょうか？この議論をするには，出席・欠席・遅刻・早退の発生する頻度を考えないといけません．仮にあなたの出席情報 を 2 進符号化するとしましょう．もしもあなたが熱心な学生で常に授業に出席しているならば， 出席を表す符号を短くして他を表す符号を長くすれば，最終的には情報を保持するのに必要なビット数を削れそうな気がしますね． もしあなたが不真面目な学生なら欠席を表す符号を短いビットで表すようにすれば，やはりビット数を削れます．逆に出席・遅刻・欠席・早退がほとんど均等な割合で起こる場合，ビット列の表現を細工しても最終的にはメリットが得られない気がします．
この議論を感覚的ではなく定量的に行うために必要なのが，以下で説明する情報量と平均情報量の概念です．

情報量

世の中には様々な情報があります．たとえば上の例で挙げた出席状況もそうですし，他にも天気が晴れか雨かといったことも情報の一種です．しかし個々の情報が示す内容に踏み込んでいては，情報を定量的に扱うことはとてもできません．そこで私たちは次のように割り切って「情報」を定義します： 情報とは，起こりうる事象の中からどの事象が起こったかを絞り込むものである．
たとえば上の出席簿の例では，起こりうる状況が出席・遅刻・早退・欠席の 4 つであり，たとえば「出席した」「遅刻した」などといった事象そのものが情報になります．また「出席ではなかった」ということも選択肢を 4 つから 3 つに絞り込むわけですから，今の定義のもとでは情報となります．別の例としては，たとえばサイコロの目があります．サイコロの目は 1, 2, …, 6 のいずれかですから「2 の目が出た」「偶数の目が出た」といったものは全て情報になります．
さて，これから情報量を定義するためにサイコロの例を考えてみましょう．「サイコロの目が 2 であった」という情報は「サイコロの目が偶数である」「サイコロの目は 3 で割って 2 余る」という情報を合わせたものと等価です．ですので情報量を I で表せば

I(サイコロの目が 2)  = I(サイコロの目が偶数) + I(サイコロの目は 3 で割って 2 余る)

という式が成り立つべきです．
より一般に n, k を共に自然数とするとき，nk 個の事象を n 個の事象からなる k 個のグループに分けておけば「どの事象が起きた」という情報は「どのグループの事象が起きた」「このグループの中でどの事象が起きた」という 2 つの情報に等価になります．よって，自然数 m に対し m 個の同様に確からしい事象それぞれが持つ情報量を I(m) と書けば

I(nk) = I(n) + I(k)

という式が自然に要請されます．この要請を情報量の加法性と言います．加法性を満たす関数の例としては log があります．さらに「同様に確からしい 2 つの事象の一方が起きるときの情報量を 1 とする」という基準を取り，「何通りの事象が起こりうるか」の代わりに事象が起きる確率で情報量を測るようにすれば，確率 p で起こる事象の情報量を -log₂p で定義するとうまく行くことが分かります．そこで以下，この I(p) = -log₂p が確率 p で起きる事象の持つ情報量だと定め，情報量の単位を bit と呼びます．
ちなみに，今の定義が恣意的に思える人のために技術的な補足をしておきます．最初に，加法性から I(1) = 0 が従うことに気をつけておきましょう．連続極限に移行するときのことを考えて I を正の実数全体で定義し，かつ加法性と微分可能性を課します．するとまず

( I(x+hx) –  I(x) ) / (hx) = I(1+h) / (hx)

となります． I(1) = 0 だから I(1+h)/h の h->0 での極限値は I'(1) です．これを c とすれば I'(x) = c/x と分かります．この両辺を積分すれば I(x) = c log x + d という形になることが分かります．そして加法性から来る条件 I(1) = 0 と規格化条件 I(1/2) = 1 を合わせることで I(x) = -log₂x と決定されます．

平均情報量 (エントロピー)

予め複数の事象 P₁, …, P_n が与えられ，そして事象 P_i が起きる確率 p_i が分かっているとしましょう．このとき事象 P_i の情報量は -log₂p_i ですから，これに p_i をかけて全ての i について足し合わせることで，事象 P₁, …, P_n の平均の情報量が得られます．これを平均情報量またはエントロピーといいます:

H = －∑p_ilog₂p_i

先ほどの出席簿の場合，欠席，遅刻，早退，出席が全て等確率，つまり p_i = 1/4 であったとすると， －4×(1/4)log₂(1/4) = －log₂2^-2 = 2 なので平均情報量は 2 となります．一方，等確率でない場合の平均情報量は等確率の場合よりも小さくなります．今度は，欠席，遅刻，早退，出席の確率が， それぞれ 1/2, 1/4, 1/8, 1/8 であるとしましょう．すると平均情報量は，次のように 1.75 bit となります．

H = ( (－(1/2)log₂(1/2)) + (－(1/4)log₂(1/4)) + 2×(－(1/8)log₂(1/8)) ) = 1.75

この平均情報量が意味するところは，この出席簿において，1 回の記録が持つ情報が平均すると 1.75 bit 分の情報だということです．もっと言えば，今は 1 回につき 2 bit を使って情報を記録していますが，実際の情報量は 2 bit に満たないということです．それでは 4 通りの情報を 2 bit 未満で符号化することは可能なのでしょうか? 今の場合は次のような符号化を行なえば，平均符号長 1.75 を達成できます．

1/2×1 bit + 1/4×2 bit + 1/8×3 bit + 1/8×3 bit = 1.75 bit
理論的には平均情報量が平均符号長の下限を与えることが証明できますが，平均符号長がぴったり平均情報量であるような符号化の方法が常に存在するとは限りません．最も短い符号を得る方法は Huffman 符号化という方法で，これは 18.7.2 圧縮アルゴリズム で説明します．また，出席簿やサイコロを振ることのように同じ試行を多数回繰り返す場合は，平均情報量にいくらでも近い平均符号長での符号化が実現できます．この事実は Shannon によって示されました．