情報経路をモデル化しよう
このページはマス旅の一部です。
今回は、「情報経路のモデル化」を探ってみよう。
せっかく効率的な情報源のモデルで効率的に情報を出しても、
通信先に正確に伝わるとは限りません。
通信経路に雑音が入ることはありうることです。
１．経路モデルとは何か
入力X、出力Yをつなぐのが通信路（経路）です。
通信経路の正確さは確率を並べた行列を使って表せます。
X={{1},{0}}の入力符号列ベクトルを
Y={{1},{0}}の出力符号列ベクトルに変換する
「確率行列が経路モデル」です。
行列のi行j列の要素をp(yj|xi)
にするのです。
＜2元対称通信路＞
美しく間違えるモデルがあります。
2元対称通信路（BSC：binary symmetric channel)です。
正反対の符号に間違える確率が
p(1|0)=p(0|1)=εで、
正しく送る確率が
p(0|0)=p(1|1)=1-εと
「美しく」間違えます。
行列の対角成分が1-εですね。
εは間違える方なので、誤り率です。
状態遷移図の通信バージョンとして、
送信側を左、受信側を右にして、符号要素０，１を上下におき、
４つのノードをかきます。
そうすると、ノードを結ぶ辺が確率になります。
グラフは4点4辺の砂時計型の
対称形になり、辺（確率）も左右対称、上下対称の美しい図形になりますね。
課題：BSCをgeogebraで視覚化しよう。
タイトルは「BSCの視覚化」
E1=(-3,3)#見出しは「１」
E2=(-3,-3)#見出しは「０」
R1=(3,3)#見出しは「１」
R2=(3,-3)#見出しは「０」
v11=Vector(E1,R1) #見出しは[1-ε]で、青
v12=Vector(E1,R2) #見出しは[ε]で、赤
v22=Vector(E2,R2) #見出しは[1-ε]で、青
v21=Vector(E2,R1) #見出しは[ε]で、赤
e=slider(0.1,0.9,0.1) #εの設定
Mat={{1-e,e},{e,1-e}}
text1="BSC通信路行列は"+Mat+"" #テキストをクリックしてLaTex数式をOn
BSCの視覚化
＜消失通信路＞
記号X={0,1}の入力が、
出力で0,1以外のe(消失）に起きかわる可能性がある通信路が
消失通信路です。
たとえば、
p(1|0)=p(0|1)=0,
p(e|0)=p(e|1)=ε,
p(0|0)=p(1|1)=1-ε
だとすると、正しい通信以外は消失してしまってます。
課題：消失通信路をgeogebraで視覚化しよう。
タイトルは「BSCの視覚化」
E1=(-3,3)#見出しは「１」
E2=(-3,-3)#見出しは「０」
R1=(3,3)#見出しは「１」
R2=(3,-3)#見出しは「０」
R3=(3,0)#見出しは「e」
v11=Vector(E1,R1) #見出しは[1-ε]で、青
v13=Vector(E1,R3) #見出しは[ε]で、赤
v22=Vector(E2,R2) #見出しは[1-ε]で、青
v23=Vector(E2,R3) #見出しは[ε]で、赤
e=slider(0.1,0.9,0.1) #εの設定
#3列目をeの項とします。
Mat={{1-e,0,e},{0,1-e,e}}
text1="消失通信路行列p(Y|X)は"+Mat+"" #テキストをクリックしてLaTex数式をOn
消失情報路の視覚化
＜4元対称通信路＞
対称通信路を2元でなく4元にすることもできます。
たとえば、
符号が１増える誤りはあり得る。
ただし、要素がリング状（巡回群）に並んでいるため、３は１増やすと０として設定します。
他の誤りはなしとしましょう。
p(1|0)=p(2|1)=p(3|2)=p(0|3)=ε,
p(0|0)=p(1|1)=p(2|2)=p(3|3)=1-ε,
p(2|0)=p(3|0)=p(0|1)=p(3|1)=p(0|2)=p(1|2)=p(1|3)=p(2|3)=0,
課題：4元対称通信路をgeogebraで視覚化しよう。
タイトルは「4元対称通信路の視覚化」
E1=(-2,3)#見出しは「3」
E2=(-2,1)#見出しは「2」
E3=(-2,-1)#見出しは「1」
E4=(-2,-3)#見出しは「0」
R1=(2,3)#見出しは「3」
R2=(2,1)#見出しは「2」
R3=(2,-1)#見出しは「1」
R4=(2,-3)#見出しは「0」
v11=Vector(E1,R1) #見出しは[1-ε]
v21=Vector(E2,R1) #見出しは[ε]
v22=Vector(E2,R2) #見出しは[1-ε]
v32=Vector(E3,R2) #見出しは[ε]
v33=Vector(E3,R3) #見出しは[1-ε]
v43=Vector(E4,R3) #見出しは[ε]
v44=Vector(E4,R4) #見出しは[1-ε]
v14=Vector(E1,R4) #見出しは[ε]
e=slider(0.1,0.9,0.1) #εの設定
Mat={{1-e,e,0,0},{0,1-e,e,0},{0,0,1-e,e},{e,0,0,1-e}}
text1="4元通信路行列p(Y|X)は"+Mat+""
4元対称情報路の視覚化
２．通信路容量
＜いろいろな通信容量を求めよう＞
通信路の容量Cは相互情報量の最大値とします。
つまり、
C＝maxI(X;Y）
で定義します。
無記憶で雑音もない2元通信路、つまり、
p(1|0)=p(0|1)=0,
p(0|0)=p(1|1)=1
を考えましょう。Y=Xとなり、無記憶だとH(X|Y)=0
I(X;Y)=H(X)-h(X|Y)=H(X)はXの確率が一様p(0)=p(1)=1/2のよき最大値１だから、
C=maxI(X;Y)=1
です。
雑音のある通信路、たとえば、
p(1|0)=p(1|0)=1/2,
p(3|1)=p(2|1)=1/2
とします。
出力から入力が逆算できますからH（X|Y)=0なので、Xの確率が一様ならさっきと同じになり、
C=1
になりますね。
＜BSCの通信容量＞
１でみた2元対称通信路の容量はどうなるでしょうか。
p(1|0)=p(0|1)=ε,
p(0|0)=p(1|1)=1-ε
としていました。
I(X;Y)=H(Y)-H(Y|X)=H(Y)-Σp(x)H(Y|X=x)
=H(Y)-Σp(x)h(ε) [「h(ε)は取り違えのエントロピー（環境ノイズ）」と同じだからH(Y|X=x)=h(ε)です。
送信側が X=0を送ろうが X=1を送ろうが、
通信路が起こす「エラーの不確実性（環境ノイズ）」は常に一定だからですね。]
=H(Y)-h(ε)Σp(x) [xからすると、eは定数だからΣの外に出せます]
=H(Y)-h(ε) [ p(0)+p(1)=1だからです。]
≦1 - h(ε) [ Yは2元の確率変数なので、H(Y)の最大値は１です]
Xの確率が一様分布ならY=1の確率も
p(Y=1)=p(0)p(1|0)+p(1)p(1|1)=1/2(ε+(1-ε))=1/2
で、同様にp(Y=0)=1/2。
Xの一様分布がYの一様分布に伝播しますね。
ということは、H(Y)は１つの確率1/2=0.1(2)と同じ情報量で１で、
maxH(Y)の下限は１ですから、C≧1-h(ε)。
以上から、
C=1-h(ε)
Cはエントロピー関数h(p)を上限反転させた形になるね。
h(p)=-plog_2(p)-(1-p)log_2(1-p)のグラフ
を思い出そう。
p=1/2で最大値１、p=0,1で最小値０．p=1/2で線対称。
hは値域は0以上1以下だった。
だから、誤り率ε=1/2のときに、Cは最小値０となり、
誤り率ε=0,1のときにCの最大値１になる。
「完全な誤り」だと、
０１が逆に出力されるだけだから、
「完全に正しいと同じことになる」
というわけですね。
課題：BSCの容量の変化を誤り率の変化でどうかわるかを視覚化してみよう。
タイトル「BSCの誤り率と容量」
e = Slider(0, 1 , 0.01) #誤り率 アニメーション
px1 = Slider(0, 1, 0.01) #p(X=1)=0.5にすると、赤青のPが重なる。
px0 = 1 - px1
#p(Y=1)=p(0)p(1|0)+p(1)p(1|1)=px1 * e + px0 (1-e)
#p(Y=0)=p(0)p(0|0)+p(1)p(0|1)=px1 * (1-e)+ px0 e から、
py1 = px1 * e + px0 (1-e)
py0 = px1 * (1-e)+ px0 e
# 底2の対数関数（0のとき0を返す安全化処理）
safelog2(x) = If(x > 0, log(2, x), 0)
HY = -py1 safelog2(py1)-py0 safelog2(py0) #H(Y)
he = -e safelog2(e)-(1-e) safelog2(1-e) #h(e)取り違えのエントロピー（環境のノイズ）
Ixy = HY-he #現在の相互情報量I(X;Y)
Cc =1- he #関数のC(x)と同名だとエラーになるので、定数としてcをつけます。
P_{capacity}=(e,Cc) #上限の容量で、「赤」にする
P_{current}=(e, Ixy) #現在の相互情報量I(X;Y)で、「青」にする。
h(x)=-x safelog2(x)-(1-x) safelog2(1-x) #非表示
C(x)= 1- h(x) #表示する容量カーブは固定です。スライダーで変動しません。
I(x)= HY-h(x) #表示するIxyのカーブはeにもpx1にも影響されます。
#次をテキストボックスの設定に貼り付けて、LateX数式をオンにします。色を白にして、
#座標平面の格子が透けないようにしましょう。
#クリックしてオブジェクト一覧から変数名と同じものを選んで置き換えると、
#アニメーションに連動して数値が変わります。
\begin{array}{l}
\textbf{【BSCの通信路容量と相互情報量】} \\[0.5em]
\text{誤り率 } \epsilon = \mathbf{e} , \quad P(X=1) = \mathbf{px1} \\[0.5em]
\hline \\[0.5em]
\text{受信エントロピー } H(Y) = \mathbf{HY} \; \text{bits} \\
\text{環境ノイズ量 } h(\epsilon) = \mathbf{he} \; \text{bits} \\[0.5em]
\text{相互情報量 } I(X; Y) = H(Y) - h(\epsilon) = \mathbf{Ixy} \; \text{bits} \\[0.5em]
\mathbf{\text{通信路容量 } C = 1 - h(\epsilon) = \mathbf{C} \; \text{bits}}
\end{array}
#さっき気づいたBSCの特徴をアニメーションで確認しよう。
#Cのカーブがｘ座標x=eのみで決まりp(X=1)に関係なく固定グラフになりますね。
#テキストボックスで詳細がわかるので、意味の確認までできますね。