第11回 マルコフ情報源

阿坂先生
今回はマルコフ情報源をもう少し深く勉強していこう。マルコフ情報源からエントロピーを求めるのが今回の目標じゃ。

桂香助教
マルコフ情報源では状態遷移図（シャノン遷移図）を使うことで視覚的に記憶のある情報源を理解できるわ。今回は2重マルコフ情報源を例に状態遷移図を考えてみるわね。

麦わら君
2重マルコフ情報源は、これから出る情報は２つ前までの情報の影響を受ける情報源でしたね。２つ前よりさらに前の状態はこれからの情報に影響を与えないってことですね。

桂香助教
ここで条件付き確率を考えるわ。なぜ条件付き確率かというと2つ前までの情報を条件として、これから何が出るかの確率Pを以下のように定義できるからね。

条件付き確率 ⇒ P(これから出る情報 | 2つ前の情報, １つ前の情報）

麦わら君
条件付き確率の使い道はこんなところにもあるんですね。2重マルコフ情報源これから出る情報は直近の過去の２つの情報が影響していて、それより前の情報は影響しない。つまり、これから出る情報は2つ前の情報と１つ前の情報の条件付き確率になるんですね。

阿坂先生
記憶のない情報源は条件付き確率にしても過去の影響がないから
P(これから出る情報 | 2つ前の情報, １つ前の情報）を考えても結局
P(これから出る情報）になる。過去は無意味じゃからな。

麦わら君
記憶のない情報源はいわゆる独立というやつですか？

桂香助教
そうね。情報の前後は無関係だから記憶のない情報源は独立ね。でも、今回の2重マルコフ情報源の場合は前後が関係しているから独立ではないのよ。

阿坂先生
条件付き確率を踏まえて、2重マルコフ情報源において、出力が０か１の二択の情報源を考えてみよう。すべての場合における条件つき確率を書き出すると以下となる情報源を考える。

P(0|00) =0.1, P(1|00)=0.9
P(0|01) =0.7, P(1|01)=0.3
P(0|11) =0.2, P(1|11)=0.8
P(0|10) =0.4, P(1|10)=0.6　　　　　　（１）

桂香助教
ここで、２つ前までの情報がこれから出る情報に影響を与えるから、例えばP(0|10)は

P(0|10) =P(これから出る情報が0 | 2つ前の情報が１, １つ前の情報が０）

であって、「2つ前の情報が１」で「1つ前の情報が０」の場合における「これから0が出る確率」よ。

阿坂先生
(1)式を見て分かるように条件付き確率の条件の部分によって、これから出る情報が１か0かの確率が変わるので、P(X|YZ)のZYの部分は状態と呼ぶこととする。状態によりこれから出る情報の確率が変化するということじゃな。

麦わら君
過去の情報がこれから出る情報に影響しているってことですね。

桂香助教

情報は次から次への出てくるから、0か１かを出力されるたびに状態は別な状態に移行するわ。（もちろん、同じ状態になることもあるけど。）例えば、今の状態が00であって１が出力されるとすると次の状態は01になるわ。未来のこれから出る情報Xは０か１よ。

麦わら君
時間が経って、情報が１つずつシフトするということですね。時間が経つとこれから出る情報は1つ前の情報になって、１つの前の情報は2つ前の情報になる。2つ前の情報は3つ前の情報になるけど2重マルコフ情報源だから3つ前の情報は無視できるということか。

阿坂先生
そうじゃ。これを遷移という。例えば、状態11が０を出力して推移すると状態10になるということじゃ。

桂香助教
上記のように情報を０と１の羅列で書いていくと2重マルコフ情報源であることがパッと見では分からない。そこで図を使って記述するのが状態遷移図（シャノン線図）よ。言葉は難しく聞こえるかもしれないけど、やっているはとっても簡単だから。まずは状態遷移図を示すわね。

黒丸に囲まれたのが状態よ。最初に状態00に注目してみるわ。状態00から0（青色）が出力される確率は条件付き確率P(0|00)から0.1（茶色）になるわよね。そして、状態は00から00に遷移する。これが状態遷移図の左上の矢印。状態00から1（青色）が出力される確率は条件付き確率P(1|00)から0.9（茶色）になるわよね。そして、状態は00から01に遷移する。これが状態00から伸びるもう１つの矢印。

麦わら君
なるほど。状態遷移図は今の状態から次の状態へどう遷移したかを表す図なんですね。矢印についているA/Bについて、A（青色）は何が出力されるか、B（茶色）はその出力確率を表しているんですね。

阿坂先生
そのとおりじゃ。状態遷移図は、（１）の８個の条件付き確率を図で表したものになる。このほうが直感的にも視覚的にも理解できるじゃろ。出力の羅列では状態が把握しにくいからのぉ。

麦わら君
はい。すっきりと見やすくなりました。

阿坂先生
さて、この状態じゃが00、01・・・と呼んでも良いのじゃが、一般化して状態をs1、s2・・・と置くことにしよう。要は状態に番号を振っておきたいんじゃ。そうすると状態遷移図と条件付き確率は以下となる。

麦わら君
はい。これは単純な置き換えですね。

桂香助教
こうやって置き換えておくと2重マルコフ情報源は単純マルコフ情報源のように扱えるわ。単純マルコフ情報源とは１つ前の情報の影響しか受けない情報源だったわね。言い換えれば1重マルコフ情報源とも言える。

阿坂先生
さて、情報をずーーと出力されていくものとして、状態がどんどん変化していくとき、どの状態になるのが一番多いか、一番少ないかということを考えてみよう。

麦わら君
s1についてはs1へ向かう矢印の確率が小さいのでs1となる確率は少なそう。s3については自分に戻る矢印の確率が大きいので一旦s3になったらしばらくはs3の状態に留まっていそうだね。

桂香助教
あくまでも確率なので出力を十分に増やしてから、各状態にいる確率を求めるわ。十分に出力されたときの各状態にいる確率分布を定常分布というわ。ここで、定常分布のときのs1,s2,s3,s4の状態の確率をw1,w2,w3,w4として、このw1,w2,w3,w4を求めてみる。

阿坂先生
まず、wの関係式じゃが

w1+w2+w3+w4=1        (2)

となるな。

麦わら君
これは大丈夫です。この連立方程式を解くにはあと式が3本必要ですが・・・

桂香助教
あと4本作れるわよ。状態s１に着目したときs1になる確率はw1だよね。s1に向けて推移する2つの状態を考える。確率w1になるということは「確率w1で存在する状態s1が０を出力して状態s1に遷移する確率」と「確率w4で存在する状態s4が1を出力して状態s1に遷移する確率」の和がw1になるのは大丈夫？

麦わら君
こうですか？w1になる確率は「自分の状態s1が再びs1になる確率」と「w4からs1に推移する確率」の和になる。

w1＝0.1w1+0.4w4         (3)

阿坂先生
そうじゃ。同様に

w2=0.9w1+0.6w4
w3=0.3w2+0.8w3
w4=0.2w3+0.7w2          (4)

となる。これを解けば定常分布w1,w2,w3,w4が分かる。つまり、どの状態にいる可能性が高いか低いかが計算できるわけじゃ。ちなみに式が5本あるけど(3)と(4)式を全部足すと(2)式になる。

麦わら君
解けました。かなりめんどくさいですが・・・

w1=8/71,     w2=18/71,    w3=27/31,     w4=18/71

です。これになんの意味があるのですか？

阿坂先生
ここから本題になるのじゃ。この情報源のエントロピーを求めてみよう。ちょっと復習しよう。０と１が半々の確率で出力される記憶のない情報源（出てくる情報が以前に出力された情報と無関係）を考えてこの情報源から出力される情報のエントロピーは？

麦わら君
エントロピーの復習ですね。確率0.5なので０と１との情報の量の期待値を計算すれば良いのでした。公式はエントロピーHの公式は

H＝-∑P×log(P)

でしたね。これに数値を入れて計算すると

H＝-0.5×log(0.5)-0.5×log(0.5)=1

になります。

桂香助教
そのとおりよ。じゃあ今回の2重マルコフ情報源のエントロピーは１より大きくなるそれとも小さくなる？

麦わら君
それくらいはわかりますよ。確率半々ならH=１でこれが最大。今回は出力される情報は過去の情報に影響されるのでこれは予測可能とも言える。なのでエントロピーは１よりも小さくなります。

桂香助教
正解！じゃあ、どうやってエントロピーを計算したら良いの？

麦わら君
うぅ。

阿坂先生
難しく考える必要はないぞぃ。マルコフ情報源のエントロピーの計算は簡単じゃ。まず、各状態のエントロピーを計算する。

麦わら君
はい。各状態における次に出力される情報のエントロピーは計算できますね。

状態s1のとき、H1＝-0.1×log(0.1)-0.9×log(0.9)=0.47
状態s2のとき、H1＝-0.7×log(0.7)-0.3×log(0.3)=0.88
状態s3のとき、H1＝-0.2×log(0.2)-0.8×log(0.8)=0.72
状態s4のとき、H1＝-0.4×log(0.4)-0.6×log(0.6)=0.97

となります。

阿坂先生
ここでエントロピーとは何かをもう一度考えてみるのじゃ。

麦わら君
情報の量の期待値ですね。

桂香助教
既に各状態でのエントロピーは計算し終わったわ。そうしたら各状態がどれだけの確率で存在するかが分かれば、各状態のエントロピーの期待値の確率を求めればいいんじゃない？

麦わら君
ちょっと混乱しますが、エントロピーは期待値ですが、その４つの状態の期待値のさらに期待値を求めれば良いですか？

阿坂先生
ここはじっくり考えて欲しい。それぞれ状態が発生する確率が得られれば、各状態のエントロピーが計算できているので、各状態のエントロピーの期待値を求めればよいことになる。

麦わら君
ところで各状態の確率はどうやって求めているんですか？

桂香助教
それは既に求めているじゃん！　w1,w2,w3,w4　だよ。

麦わら君
あっそうか！じゃあエントロピーHは

H=w1H1+w2H2+w3H3+w4H4
   =8/71×0.47+18/71×0.88+27/71×0.72+18/71×0.97=0.80

たしかに１よりも小さくなりました！

阿坂先生
これがこの2重マルコフ情報源の出力される情報のエントロピーじゃよ。