logo

Hidden Markov Chain 📂Probability Theory

Hidden Markov Chain

Buildup

20190218_114748.png

Imagine a machine that produces certain items at fixed intervals as shown in the figure above. If green represents the normal quality goods 11 and red represents defective goods that need to be discarded 00, then the record so far would be (1,0,1)\left( 1, 0 , 1 \right). The actual visible results like this are referred to as Signal.

20190218_111057.png However, the probability of producing a defective item varies depending on whether the machine is normal or broken. When normal ++, the defect rate is only 11 %, but when broken −-, the defect rate skyrockets to 44 %. If we express this as a conditional probability, it will be 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}

The diagram would look as follows.

20190218_111611.png

Let’s assume that the probability of the machine breaking down each time it produces an item is as the diagram above 10%10 \%. This is a Markov chain, and the state space of the stochastic process {Xj}j=0n\left\{ X_{j} \right\}_{j = 0}^{n} is {+,−}\left\{ + , - \right\}, and our interest is the probability that the machine is normal after the jjth production p(Xj=+)p \left( X_{j} = + \right). Of course, we’ll assume that the machine is normal initially, represented as p(X0=+)=1p(X0=−)=0\begin{matrix} p(X_{0} = +) = 1 \\ p(X_{0} = - ) = 0 \end{matrix}.

If the machine is left broken, it will continue to produce many defective items. The question is how we can know this. Of course, a manager can quickly find out whether the machine is broken or not by inspecting it once, but if there are an enormous number of machines in a large factory, even such inspections can be a very burdensome task. Realistically, we have no choice but to guess which machine has a problem based on the items produced.

Definition

When the Markov chain (cause) is hidden and only the resulting signal (effect) is known, it is called Hidden Markov Chain {Xj}j=0n\left\{ X_{j} \right\}_{j=0}^{n}.

Example

(1)

Now let’s calculate the probability p(Xn=x∣S(n)=s(n))\displaystyle p \left( X_{n} = x \mid S_{(n)} = s_{(n)} \right) given the signal s(n)=(s1,s2,⋯ ,sn)s_{(n)} = ( s_{1} , s_{2} , \cdots , s_{n} ).

If we say 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*} that is, if we know Fn(x)F_{n} (x), we can know p(Xn=x∣S(n)=s(n))\displaystyle p \left( X_{n} = x \mid S_{(n)} = s_{(n)} \right) without considering the conditional probability. (1)(1) sns_{n} is independent of s(n−1)s_{(n-1)}, and (2)(2) {Xj}j=1n\left\{ X_{j} \right\}_{j=1}^{n} is a Markov chain, so 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*} To summarize, we get the following. 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 Then, as an example in this post, let’s calculate p(X3=+∣S(3)=(1,0,1))\displaystyle p \left( X_{3} = + \mid S_{(3)} = (1,0,1) \right) under the assumptions mentioned. In other words, compute the probability that the machine is normal in that situation.

In the Markov chain, the transition probabilities of states are p++=0.9p+−=0.1p−+=0p–=1\begin{matrix} p_{++} = 0.9 & p_{+-} = 0.1 \\ p_{-+} = 0 & p_{–} = 1 \end{matrix} For each state, 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} Initially, assuming that the machine is normal, F1(+)=p(1∣+)=0.99F1(−)=p(0∣+)=0.01 F_{1} (+) = p( 1 \mid + ) = 0.99 \\ F_{1} (-) = p (0 \mid + ) = 0.01 since 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 since 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 Therefore, 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

Logically, if the defect rate is not that high but one out of three is defective, we can guess that the probability of the machine being normal is significantly decreased. The calculation results show that the probability of the machine being normal barely exceeds 60%60 \%.