情報発生をモデル化しよう
このページはマス旅の一部です。
今回は、「情報源のモデルとそこから発生する情報量」を探ってみよう。
ただ、今回のテーマは古典をたずねることなので、情報は文字に限定します。
１．情報発生のモデル
情報発生のモデル
情報源から出るi番目とか時刻iとかの要素siのあつまりを「（情報源）アルファベット」と呼びます。
アルファベットがS＝{s1,s2,...,sm}とし、要素（元）s1～smは英数字に限る必要はありません。
＜記憶のあるなし＞
コイン投げも情報源です。結果は裏か表かわからないのでこれを確率変数Xといいます。
表を1,裏を0とするとX={0,1}とかけます。
要素が2元だから、2元アルファベットS={0,1}となるね。
「コイン投げという情報源」から5回続けて出る結果はどうなるでしょうか？
たとえば、結果はXだから、i回目の結果をXiとかけますね。
実際に投げた結果をxi(0,1のどちらかの具体のこと）とすれば、
X1=x1,X2=x2,X3=x3,X4=x4,X5=x5
とかけます。
つまり、「0,0,1,0,1」とか、「1,1,1,1,0」とか、0か1に枝分かれする可能性のうち、
具体的にたどった経路、確率過程を記号で表せます。
この同時確率（「時間的な同時」ではなくて、「論理的同時」です）は、
p(x1,x2,x3,x4,x5)=p(x1)p(x2)p(x3)p(x4)p(x5)=(1/2)^5
です。
前に出た目は、次に出る目に何も影響を与えません。
受け取る側から見れば、記憶をもたないように見えます。
だから、これを、記憶のない情報源、「定常無記憶情報源」といいます。
「定常」というのは、いつも変わらない、時間シフトをしても結果が同じというものです。
コイン投げを2回するときの同時確率は、いつ観察してもいっしょです。
たとえば、
p(X1=x1,X2=x2)=p(X3=x1,X4=x2)=p(X9=x1,X10=x2)
それとは真逆の情報源があります。記憶のある情報源ですね。
コトバのように意味のあるまとまりでは、決まったつながりで生まれます。
「過去の有限個の記号発生が次の記号発生に影響する情報源」を
「マルコフ（Markov)情報源」といいますね。
条件付き確率の再登場です。
「コイン投げの2元アルファベットS={0,1}」に、次のようなマルコフ性あるとしましょう。
p(1|0)=a、p(0|1)=bすれば、
余事象の確率はp(0|0)=1-a, p(1|1)=1-b
こうすると、コイン投げの情報源は回を重なるごとに変化します。
a,bを動かすと、この情報源はいろんな過程をたどっていきますね。
＜状態遷移図＞
記憶されるアルファベットや組み合わせを「状態」と呼びましょう。
さっきのコイン投げのマルコフ情報源では、依存するのは１変数でしたから、状態「０」と状態「１」の２つをかきます。
状態の値や記号を〇の中にかきます。そこから、→で遷移のルールをラベルつきで追加するのです。
p(1|0)=aは、0から１行きの矢印になり、ラベルが「行先/確率」＝1/aです。
p(0|0)=1-aは、0から0に戻る曲線矢印になり、ラベルは0/1-aですね。
p(1|1)=1-bは、1から1に戻る曲線矢印になり、ラベルは1/1-bです。
p(0|1)=bは、１から0行きの矢印になり、ラベルは0/bですね。
肝心の初回の結果X1の確率は決まってませんでした。
もしも、このマルコフ情報源が定常的にしたかったらどうすればよいでしょうか。
p(X1=0)=w, p(X1=1)=1-wとおき、
p(Xn=0)=w, p(Xn=1)=1-wとすると、
目はいろいろ変わるけど、確率は一定になるシステムになりますね。
p(X2=0)=p(X1X2=00)+p(X1X2=10)
=p(0)p(0|0)+p(1)p(0|1)
=w(1-a)+(1-w)b
=wです。
wの1次方程式でw(1-a-b-1)=-b
だから、w=b/(a+b)
と解ｗが出ました。
このとき、
p(X2=1)=p(1)p(1|1)+p(0)p(1|0)
=(1-w)(1-b)+wa
=(1-b/(a+b))(1-b) + ab/(a+b)
=[( (a+b) -b )(1-b)+ab ] /(a+b)
=( a -ab +ab )/(a+b)
=a/(a+b)
=[(a+b)-b]/(a+b)
=1-w
整合的ですね。
つまり、初期値w=b/(a+b)とすると、いつでも
p(0)=b/(a+b), p(1)=a/(a+b)となる
のですね。
マルコフ情報源でも定常になるということです。
この例は2元アルファベットで未知数がw1個でした。
n元アルファベットでも、p(Xi|Xj)をn*n個さだめて、
定常確率を未知数としてp(X1=xi)=wiとΣwi=1を使うことで、n本の方程式から
定常確率wiを決めることができるでしょう。
課題：geogebraで状態遷移図をかこう。
タイトルは「状態遷移図」
#図形オブジェクト
Node0 = (-2, 0) #非表示
Node1 = (2, 0) #非表示
C0 = Circle(Node0, 0.6) #ラベルなし青
C1 = Circle(Node1, 0.6) #ラベルなし赤
Arrow01 = Vector((-1.4, 0.2), (1.4, 0.2)) #ラベルなし青
Arrow10 = Vector((1.4, -0.2), (-1.4, -0.2))#ラベルなし赤
#ラベルなし青
Loop0 = Arc(Circle((-3.0, 0), 0.4), (-2.6, 0.4), (-2.6, -0.4))
#ラベルなし赤
Loop1 = Arc(Circle((3.0, 0), 0.4), (2.6, -0.4), (2.6, 0.4))
#テキストオブジェクト
#太字で中サイズにそろえましょう。
Text_0 = Text("0", (-2.1, -0.15))
Text_1 = Text("1", (1.9, -0.15))
Text_a = Text("1 / a", (0, 0.4))
Text_b = Text("0 / b", (0, -0.6))
Text_1a = Text("0 / 1-a", (-5, 0))
Text_1b = Text("1 / 1-b", (3.6, 0))
#ループに矢印が欲しくなりますね。
その場合は、次の行を数式ビューに1行ずつ入れましょう。
A=Point(Loop0)
B=Point(C0)
C=Point(Loop1)
D=Point(C1)
v=Vector(C,D) #色は赤
w=Vector(A,B) #色は青
#A,B,C,Dをつかんで、ループから状態円に矢先が向かうように調整し、
その後、非表示にします。
状態遷移図
2．情報源全体のエントロピー
＜エントロピーレート＞
情報源Xから出力が確率変数X1,X2,...,Xnとなるとき、
この確率変数数列の同時エントロピーを考えましょう。
系列の長さｎを増やしたときの同時エントロピー/nの極限H（X)があるとき、
H(X)をエントロピーレートいいます。
１変数のときの同時エントロピーは
もとのエントロピーにはみ出した条件つきエントロピーを加算するだけでした。
H（AB)＝H(A)+H(B|A)
ということは、
H(X1X2...Xn)=H(X1X2...Xn-1)+H(Xn|X1X2...Xn-1)と
H(X1X2...Xn)=H(X1)+H(X2|X1)+H(X3|X1X2)+H(X4|X1X2X3)+.....+H(Xn|X1X2...Xn-1)
が成り立つことは容易に推理できますね。
無記憶情報源の場合は条件つきエントロピーは無条件のエントロピーと同じで、毎回のエントロピーが同じです。
H(X1X2...Xn)=H(X1)+H(X2)+H(X3)+H(X4)+.....+H(Xn)で、
H(X1)=H(X2)=H(X3)=H(X4)=.....=H(Xn)となるので、
H(X1X2...Xn)=nH(X1)です。
同時エントロピーは長さｎに比例しますね。
エントロピーレートはH(X)=lim1/n(nH(X1)=H(X1)になります。
定常マルコフ情報源の場合はどうでしょう。
１つ前にだけ依存するとしましょう。
すると、
H(Xn|X1X2...Xn-1)=H(Xn|Xn-1)となるので、
H(X1X2...Xn)=H(X1)+H(X2|X1)+H(X3|X1X2)+H(X4|X1X2X3)+.....+H(Xn|X1X2...Xn-1)
＝H(X1)+H(X2|X1)+H(X3|X2)+H(X4|X3)+.....+H(Xn|Xn-1)
ですね。
また、
定常性からH(X2|X1)＝H(X3|X2)＝H(X4|X3)＝.....＝H(Xn|Xn-1)
が言えます。
だから、
同時エントロピーはH(X1X2...Xn)=H(X1)+(n-1)H(X2|X1)
となるので、
H(X)=H(X1X2...Xn)/n
=H(X1)/n+(n-1)/nH(X2|X1)
→H(X2|X1)
が
nを∞にしたときの極限値、エントロピーレートH(X)ですね。
同時エントロピーと条件つきエントロピーの関係を求めたときのことを思い出そう。
H(AB)=-Σ_i[p(ai)log_2(p(ai)]
-Σ_ip(ai)Σ_j [p(bj|ai)log_2(p(bj|ai))]
つまり、
H(AB)=H(A)+H(B|A)
でしたね。
つまり、H(B|A)=-Σ_ip(ai)Σ_j [p(bj|ai)log_2(p(bj|ai))]＝-ΣΣp(ai∧bj)log_2(p(bj|ai))
さっきやった「コイン投げの2元アルファベットの定常情報源」
S={0,1},p(1|0)=a、p(0|0)=1-a、p(0|1)=b,p(1|1)=1-b,p(0)=b/(a+b),p(0)=a/(a+b)
のエントロピーレートを求めてみよう。
H(X)=-Σ_iΣ_j [p(bj|ai)p(ai)log_2(p(bj|ai))]
=-p(0)Σp(bj|0)log_2 p(bj|0) - p(1)Σp(bj|1)log_2 p(bj|1)
=p(0)( - (1-a)log_2(p(1-a)) -a log_2 (a)) + p(1)( - blog_2(b) - (1-b) log_2(1-b) )
=b/(a+b)*H(a)+a/(a+b)*H(b)
=[H(a) b + H(b) a]/(a + b)
「エントロピーレートは、
エントロピー関数H(a)、H(b)の積和によって、
情報源全体のエントロピーを表している」
と言えますね。
たとえば、a = 0.3, b = 0.1 ならば、
定常確率はp(0)=0.1/(0.1+0.3)=1/4, p(1)=3/4。
だから、
H（X）=1/4*H(0.3)+3/4*H(0.1)=1/4*0.8813+3/4*0.4690
=0.5721ビット。
これが「情報源全体のエントロピー（エントロピーレート）」です。
ちなみに、定常確率が存在しうる情報源をエルゴード情報源といいます。
非エルゴード情報源とは、
周期性があったり１つ状態から抜け出せなくなったり、
入り込めない状態があるようなものです。
課題：geogebraでH(X)をa,bの関数として変化を調べるにはどうしたらよいですか。
タイトルは「定常マルコフ情報源の全体エントロピー」
立体図形を選んでアプレットを作ります。
# 二進エントロピー関数の定義（底2の対数）で非表示
H(p) = -p * log(2, p) - (1 - p) * log(2, 1 - p)
# エントロピーレートの2変数関数 H_X(x, y) [x=a, y=b]
# 3Dビューで 0 < x < 1, 0 < y < 1 の範囲で曲面が表示されます。
H_X(x, y) = (y * H(x) + x * H(y)) / (x + y)
#全体メニューで表示＞グラフィックスビューをオフにして、
#グラフィックス２をオンにしましょう。
#グラフィックス２の画面をクリックして選択したあとで、
#数式ビューに1行ずつ入力しましょう。
# 1. スライダーaの設定 # デフォルト値 a=0.3,b=0.1
a =Slider(0.01, 0.99, 0.01) #アニメーション
b =Slider(0, 1, 0.1)
# 2. 1変数関数としてのエントロピーレート f(x) [x=b]
f(x) = (x * H(a) + a * H(x)) / (a + x)
P = (b, f(b))
h=H_X(a,b)
Pab=(a,b,h)
#それぞれのグラフの式をテキストで貼り付けるといいですね。
"H_X(x, y) = \frac{y * H(x) + x * H(y)}{x + y}"
"f(x) = \frac{x * H(a) + a * H(x)} {a + x}"
自動的なaの変動にあわせて、ｆのグラフが動きます。
さらに、bを手動で動かすことで、全体エントロピーへのa,bの寄与を
感じよう。
特に、a = 0.5, b = 0.5のとき（完全無記憶ランダム状態）でエントロピーが最大値1ビットになり、
a, bが極端な値（0や1付近）でエントロピーが減少します。