logo

ヒドゥン・マルコフ連鎖 📂確率論

ヒドゥン・マルコフ連鎖

ビルドアップ

20190218_114748.png

上の図のように、一定の時間ごとに何かを生産する機械を想像してみよう。緑が正常な良品11で、赤が廃棄すべき不良品00であるとすると、今までの記録は(1,0,1)\left( 1, 0 , 1 \right)になるだろう。このように実際に目に見える結果をシグナルsignalと呼ぶ。

20190218_111057.png ただし、不良品が出る確率は機械が正常か故障かによって異なるとしよう。正常++の時は不良率が11 %しかないが、故障−-の時は不良率が44 %に急上昇する。これを条件付き確率で表せば p(1∣+)=0.99p(0∣+)=0.01p(1∣−)=0.96p(0∣−)=0.04\begin{matrix} p ( 1 \mid + ) = 0.99 & p ( 0 \mid + ) = 0.01 \\ p ( 1 \mid - ) = 0.96 & p ( 0 \mid - ) = 0.04 \end{matrix}

になるだろう。図式で表すと次のようになる。

20190218_111611.png

機械が一回物を生産するごとに故障する確率は上の図式と同じく10%10 \%としよう。これはマルコフ連鎖であり、確率過程{Xj}j=0n\left\{ X_{j} \right\}_{j = 0}^{n}の状態空間は{+,−}\left\{ + , - \right\}であり、私たちの関心事はjj回目の生産を終えた時に機械が正常である確率p(Xj=+)p \left( X_{j} = + \right)になる。もちろん最初は機械が正常だと仮定することになるが、これはp(X0=+)=1p(X0=−)=0\begin{matrix} p(X_{0} = +) = 1 \\ p(X_{0} = - ) = 0 \end{matrix}で表される。

機械が故障した状態で放置されれば、続けて多くの不良品を生み出すことになる。問題はこれをどうやって知るかということだ。もちろん管理者が一度機械を分解してみれば、機械が故障しているかどうかはすぐに分かるかもしれないが、大きな工場に膨大な数の機械がある場合、このような点検さえも非常に面倒な仕事になる。現実的には、生産された物を見てどの機械に問題があるかを推測するしかないのだ。

定義

このようにマルコフ連鎖（原因）が隠れていて、その結果のシグナル（結果）だけが分かるとき、それを隠れマルコフ連鎖{Xj}j=0n\left\{ X_{j} \right\}_{j=0}^{n}と呼ぶ。

例

(1)

では、シグナルs(n)=(s1,s2,⋯ ,sn)s_{(n)} = ( s_{1} , s_{2} , \cdots , s_{n} )が与えられたときの確率p(Xn=x∣S(n)=s(n))\displaystyle p \left( X_{n} = x \mid S_{(n)} = s_{(n)} \right)を計算してみよう。

Fn(x):=p(Xn=x,S(n)=s(n))\displaystyle F_{n} (x):= p \left( X_{n} = x , S_{(n)} = s_{(n)} \right)と言えば p(Xn=x∣S(n)=s(n))=p(Xn=x,S(n)=s(n))p(S(n)=s(n))=Fn(x)∑yFn(y) \begin{align*} & p \left( X_{n} = x \mid S_{(n)} = s_{(n)} \right) \\ =& {{ p \left( X_{n} = x , S_{(n)} = s_{(n)} \right) } \over { p \left( S_{(n)} = s_{(n)} \right) }} \\ =& {{ F_{n} (x) } \over { \sum_{y} F_{n} (y) }} \end{align*} つまり、Fn(x)F_{n} (x)を知れば、条件付き確率を考えることなくp(Xn=x∣S(n)=s(n))\displaystyle p \left( X_{n} = x \mid S_{(n)} = s_{(n)} \right)を知ることができる。(1)(1)sns_{n}はs(n−1)s_{(n-1)}と独立であり、(2)(2){Xj}j=1n\left\{ X_{j} \right\}_{j=1}^{n}はマルコフ連鎖であるため Fn(x)=p(Xn=x,S(n)=s(n))=p(Xn=x,S(n−1)=s(n−1),Sn=sn)=∑yp(Xn=x,Xn−1=y,S(n−1)=s(n−1),Sn=sn)=∑yp(Xn−1=y,S(n−1)=s(n−1))p(Xn=x,Xn−1=y,S(n−1)=s(n−1),Sn=sn)p(Xn−1=y,S(n−1)=s(n−1))=∑yFn−1(y)p(Xn=x,Sn=sn∣Xn−1=y,S(n−1)=s(n−1))=(1)∑yFn−1(y)p(Xn=x,Sn=sn∣Xn−1=y)=∑yFn−1(y)p(Sn=sn,Xn=x,Xn−1=y)p(Xn−1=y)=∑yFn−1(y)p(Xn=x,Xn−1=y)p(Xn−1=y)p(Sn=sn,Xn−1=y,Xn=x)p(Xn=x,Xn−1=y)=∑yFn−1(y)p(Xn=x∣Xn−1=y)p(Sn=sn∣Xn=x,Xn−1=y)=(2)∑yFn−1(y)p(Xn=x∣Xn−1=y)p(Sn=sn∣Xn=x)=∑yFn−1(y)pyxp(sn∣x) \begin{align*} F_{n} (x) =& p \left( X_{n} = x , S_{(n)} = s_{(n)} \right) \\ =& p \left( X_{n} = x , S_{(n-1)} = s_{(n-1)} , S_{n} = s_{n} \right) \\ =& \sum_{y} p \left( X_{n} = x , X_{n-1} = y , S_{(n-1)} = s_{(n-1)} , S_{n} = s_{n} \right) \\ =& \sum_{y} p \left( X_{n-1} = y , S_{(n-1)} = s_{(n-1)} \right) {{ p \left( X_{n} = x , X_{n-1} = y , S_{(n-1)} = s_{(n-1)} , S_{n} = s_{n} \right)} \over { p \left( X_{n-1} = y , S_{(n-1)} = s_{(n-1)} \right) }} \\ =& \sum_{y} F_{n-1} ( y ) p \left( X_{n} = x , S_{n} = s_{n} \mid X_{n-1} = y , S_{(n-1)} = s_{(n-1)} \right) \\ &\overset{(1)}{=}& \sum_{y} F_{n-1} ( y ) p \left( X_{n} = x , S_{n} = s_{n} \mid X_{n-1} = y \right) \\ =& \sum_{y} F_{n-1} ( y ) {{ p \left( S_{n} = s_{n} , X_{n} = x , X_{n-1} = y \right) } \over { p ( X_{n-1} = y ) }} \\ =& \sum_{y} F_{n-1} ( y ) {{ p ( X_{n} = x , X_{n-1} = y ) } \over { p ( X_{n-1} = y ) }} {{ p \left( S_{n} = s_{n} , X_{n-1} = y , X_{n} = x \right) } \over { p ( X_{n} = x , X_{n-1} = y ) }} \\ =& \sum_{y} F_{n-1} ( y ) p \left( X_{n} = x \mid X_{n-1} = y \right) p \left( S_{n} = s_{n} \mid X_{n} = x , X_{n-1} = y \right) \\ &\overset{(2)}{=}& \sum_{y} F_{n-1} ( y ) p \left( X_{n} = x \mid X_{n-1} = y \right) p \left( S_{n} = s_{n} \mid X_{n} = x \right) \\ =& \sum_{y} F_{n-1} ( y ) p_{yx} p \left( s_{n} \mid x \right) \end{align*} まとめると、次のようになる。 Fn(x)=p(sn∣x)∑yFn−1(y)pyx F_{n} (x) = p \left( s_{n} \mid x \right) \sum_{y} F_{n-1} ( y ) p_{yx}

(2)

20190218_114748.png それでは、このポストで言及された仮定の下でp(X3=+∣S(3)=(1,0,1))\displaystyle p \left( X_{3} = + \mid S_{(3)} = (1,0,1) \right)を計算してみよう。つまり、その状況で機械が正常である確率を計算しよう。

マルコフ連鎖で、状態の遷移確率は p++=0.9p+−=0.1p−+=0p–=1\begin{matrix} p_{++} = 0.9 & p_{+-} = 0.1 \\ p_{-+} = 0 & p_{–} = 1 \end{matrix} 各状態で p(1∣+)=0.99p(0∣+)=0.01p(1∣−)=0.96p(0∣−)=0.04\begin{matrix} p ( 1 \mid + ) = 0.99 & p ( 0 \mid + ) = 0.01 \\ p ( 1 \mid - ) = 0.96 & p ( 0 \mid - ) = 0.04 \end{matrix} 最初は機械が正常だと仮定するので F1(+)=p(1∣+)=0.99F1(−)=p(0∣+)=0.01 F_{1} (+) = p( 1 \mid + ) = 0.99 \\ F_{1} (-) = p (0 \mid + ) = 0.01 s2=0s_{2} = 0なので F2(+)=p(0∣+)[F1(+)p+++F1(−)p−+]=0.01×[0.99×0.9+0]=0.00891F2(−)=p(0∣−)[F1(+)p+−+F1(−)p–]=0.04×[0.99×0.1+0.01×1]=0.00436 F_{2} ( + ) = p ( 0 \mid + ) \left[ F_{1} ( + ) p_{++} + F_{1} ( - ) p_{-+} \right] = 0.01 \times [ 0.99 \times 0.9 + 0 ] = 0.00891 \\ F_{2} ( - ) = p ( 0 \mid - ) \left[ F_{1} ( + ) p_{+-} + F_{1} ( - ) p_{–} \right] = 0.04 \times [ 0.99 \times 0.1 + 0.01 \times 1 ] = 0.00436 s3=1s_{3} = 1なので F3(+)=p(1∣+)[F2(+)p+++F2(−)p−+]=0.99×[.00891×0.9+0])=0.00793881F3(−)=p(1∣−)[F2(+)p+−+F2(−)p–]=0.94×[.00891×0.1+.00436×1]=0.00493594 F_{3} ( + ) = p ( 1 \mid + ) \left[ F_{2} ( + ) p_{++} + F_{2} ( - ) p_{-+} \right] = 0.99 \times [ .00891 \times 0.9 + 0 ]) = 0.00793881 \\ F_{3} ( - ) = p ( 1 \mid - ) \left[ F_{2} ( + ) p_{+-} + F_{2} ( - ) p_{–} \right] = 0.94 \times [ .00891 \times 0.1 + .00436 \times 1 ] = 0.00493594 したがって p(X3=+∣S(3)=(1,0,1))=F3(+)F3(+)+F3(−)=0.007938810.01287475=0.6166⋯\displaystyle p \left( X_{3} = + \mid S_{(3)} = (1,0,1) \right) = {{ F_{3} ( + ) } \over { F_{3} ( + ) + F_{3} ( - ) }} = {{ 0.00793881 } \over { 0.01287475 }} = 0.6166 \cdots

常識的に考えても、不良率がそんなに高くないのに三つ中一つが不良品だったら、機械が正常である可能性は著しく低いと推測できる。計算結果、機械が正常である確率は60%60 \%をかろうじて超える程度である。