エントロピーレート(確率過程におけるエントロピーの増加の割合)
情報理論でエントロピーといえば確率変数が持つ情報量の期待値のこと。例えば
P(x1) = 1/2, P(x2) = 1/4, P(x3) = 1/4
という分布があったらエントロピーは
1/2 * lg2 + 1/4 * lg4 + 1/4 * lg4 = 1/2 * 1 + 1/4 * 2 + 1/4 * 2 = 3/2 = 1.5
なので平均1.5ビットでこの分布から生成されたデータを表現できる。
では確率変数の列を表現するには平均何ビット必要だろうか。言い換えると確率変数の列にデータを追加するには平均何ビット必要だろうか。これはエントロピーレートという概念で説明できる。
実はエントロピーレートをよくわかっていなかったのだけど、最近になって理解したのでメモしておく。
エントロピーレートとは確率変数列に確率変数を１つ追加したときに増える情報量の期待値のこと。
まず前提として確率過程として、定常過程を扱う。定常過程というのは確率過程のどの部分を切り出しても分布が同じ確率過程のこと。例えばP(X1, X2, X3, X4, X5)という確率過程があったとして、これが定常過程ならP(X1, X2)の分布とP(X4, X5)は同じになるしP(X1)とP(X3)の分布も同じになる。
確率変数XのエントロピーがH(X)のとき、単純に考えるとエントロピーレートはH(X)のような気がする。つまり先程の例だと平均1.5ビットで確率変数が表現されていたのでデータが一つ増えたら平均1.5ビット増えるんじゃないの、という予想。
しかし実際は過去の確率変数の情報によって現時点での確率変数が取りうる値が限られてくることがあるためH(X)よりも情報量は小さい。例えばランチにピザかパスタを半々の確率で食べる人が3人いたとする。この人たちがある日何を食べたかの情報は
P(ピザ) = 1/2, P(パスタ) = 1/2 H(X) = 1/2 * lg2 + 1/2 * lg2 = 1
なので1ビットで表現できる。この人たちの一週間のランチは例えば
A氏：ピザ、ピザ、パスタ、パスタ、ピザ、ピザ、パスタ B氏：ピザ、パスタ、パスタ、ピザ、ピザ、パスタ、パスタ C氏：パスタ、ピザ、パスタ、ピザ、パスタ、ピザ、パスタ
のようなものになり、それぞれ7ビットあれば表現できる。
ここでC氏に注目する。パスタとピザが交互に並んでいるのがわかる。実は彼は同じ物を２日続けて食べない主義だったのだ。ということは最初の日に何を食べたかを知っていれば充分ということになる。つまりC氏のランチの情報を表現するには1ビットあれば充分ということになる。
ここでランチ情報を4週間分に伸ばしてみる。するとA氏、B氏のランチ情報は28ビット必要なのに対して、C氏のランチ情報は最初の日に何を食べたかだけわかれば良いので1ビットのままになる。言い換えるとA氏、B氏のエントロピーレートが1ビットなのに対してC氏のエントロピーレートは0ビットなのでデータが増えても必要なビットは変わらないということ。
ある特定の日だけ見た場合には半々の確率でピザかパスタを食べている3人だが、1週間という期間で見た場合には、前日に何を食べたかが次の日に何を食べるかに影響するC氏は他の二人よりも情報量が小さくなる。
確率変数が直前の確率変数にしか依存しない確率過程をマルコフ過程という。C氏のランチはマルコフ過程と言える。定常なマルコフ過程は確率分布Pと遷移行列Mで表現できる。A,B,C３人のランチは
A,B氏
P(ピザ) = 1/2, P(パスタ) = 1/2
M = ( (1/2, 1/2),
(1/2, 1/2) )
C氏
P(ピザ) = 1/2 P(パスタ) = 1/2
M = ( (0, 1),
(1, 0 ) )
Σ_ij P(i) * M(i,j) * lgM(i,j)
で計算できる。
A,B氏 1/2 * 1/2 * lg2 + 1/2 * 1/2 * lg2 + # i = ピザ 1/2 * 1/2 * lg2 + 1/2 * 1/2 * lg2 # i = パスタ = 1/4 + 1/4 + 1/4 + 1/4 = 1ビット C氏 1/2 * 0 * lg0 + 1/2 * 1 * lg1 + # i = ピザ 1/2 * 1 * lg1 + 1/2 * 0 * lg0 # i = パスタ = 0 + 0 + 0 + 0 = 0ビット
今回はマルコフ過程の場合を例に出して説明したが、エントロピーレートはある時点での分布だけでなく、確率変数の遷移に関する情報も加味してエントロピーの増加の割合を表現する概念だよ、という話。
最初は分布が同じだったらエントロピーレートはエントロピーと同じなんじゃないの、と思って混乱していたのだがよく考えたら遷移に関する情報があるので全く違ったということに気づいた。めでたしめでたし。
今回の話題を含め、情報理論については以下の本がとても詳しいのでオススメ。
