# Hidden markov model estimate p(x | y1, y2, y3, …)

I have this hidden markov model/network with four unknown variables $$y_{1:4}$$ with the discrete domain $$(0,1)$$ and four known observations $$y^{obs}_{1:4}$$ and a potential function $$\phi(x_i,x_j)$$.

$$\phi(x_i,x_j)= \begin{cases} 5,& \text{if } x_i=x_j\\ 2, & \text{otherwise} \end{cases}$$

Here's a visualization of the network At last I have this statistical information $$p(y^{obs}_i = 1 | y_i = 1) = 0.95$$ $$p(y^{obs}_i = 0 | y_i = 0) = 0.99$$

I now need to compute $$p(y_1 = 1 | y^{obs}_1=1,y^{obs}_2=0,y^{obs}_3=0,y^{obs}_4=0$$). I however have not a single clue on how to do this. I'm completely new to HMM's and online formula's don't even come close this this sort of problem. I've also tried calculating stuff with a $$\frac{1}{Z}\widetilde{P}(X,Y)$$ function stuff but I really don't understand any of it.

• Do you have a table of values for the potential function ? Anyway I would start by trying to use the joint law of the model corresponding to the following graphical representation (based on your description) : the $x_i$ linked in as the corner of a square + each of the $x_i$ linked to its observation $y_i$. – TheCG Oct 23 '19 at 16:49
• if $x_i = x_j$ then 5, else 2 – Wouter Vandenputte Oct 23 '19 at 16:51
• Then, it should be feasible if you are allowed to use a computer to get the result. I suggest: start from $p(x_1 = 1 | y_1=1,y_2=0,y_3=0,y_4=0)$, reach the joint law $p(\pmb{x},\pmb{y})$, factorize it with the HMM properties then you should end up with only computable terms. – TheCG Oct 23 '19 at 17:09

\begin{align} p(y_1=1|y_1^o = 1, y_{-1}^o = \mathbf{0} ) = \frac{ p(y_1^o=1|y_1=1) \cdot \sum_{y_2=0}^1 \sum_{y_3=0}^1 \sum_{y_4=0}^1 \prod_{i=2}^4 p(y_i^o=0|y_i) \phi_{1,y_2} \phi_{y_2,y_3} \phi_{y_3,y_4} \phi_{1,y_4}}{ \sum_{y_1=0}^1 \sum_{y_2=0}^1 \sum_{y_3=0}^1 \sum_{y_4=0}^1 p(y_1^o=1|y_i) \prod_{i=1}^4 p(y_i^o=0|y_i) \phi_{y_1,y_2} \phi_{y_2,y_3} \phi_{y_3,y_4} \phi_{y_1,y_4} } \end{align}

Derivation:

Let $$y^o = \{y_1^o,y_2^o,y_3^o,y_4^o\}$$ and $$y = \{y_1,y_2,y_3,y_4\}$$. According to the Bayes law

$$\begin{equation} p(y|y^o) = \frac{p(y^o|y)p(y)}{p(y^o)} \end{equation}$$

And the value we are looking for may be obtained from the function

$$\begin{equation} p(y_1|y^o) = \int_{y_2,y_3,y_4} \frac{p(y^o|y)p(y)}{p(y^o)} d y_1 d y_2 d y_3. \quad (M) \end{equation}$$

Now, in the Markov random fields model the joint probability of the state of the system $$y$$ is given by the product of potential functions of all maximal cliques (a clique is a subgraph of our graph, such that every node of this subgraph is connected directly to all other nodes of this subgraph). We have exactly 4 maximal cliques in our Markov model:

$$\begin{equation} \mathcal{C} = \left\{\{y_1, y_2\}, \{y_2, y_3\}, \{y_3, y_4\}, \{y_4, y_1\}\right\} \end{equation}$$

The joint probability of the Markov model is then

$$\begin{equation} p(y) = \frac{1}{Z} \prod_{\{y_i,y_j\} \in \mathcal C } \phi(y_i,y_j), \end{equation}$$

where $$Z$$ is a constant such that $$p(y)$$ sums up (across all possible values of vector $$y$$) to 1.

Probability of the vector of observations $$y^o$$ conditional of the state $$y$$ is

$$\begin{equation} p(y^o|y) = \prod_{i=1}^4 p(y_i^o|y_i) \end{equation}$$

and the unconditional probability of observations (that is the denominator) is the sum of that over all possible realisations of the state vector $$y$$ ($$\{0,0,0,0\}, \{0,0,0,1\}, ..., \{1,1,1,1\}$$) weighted by the probailities of these realisations:

\begin{align} p(y^o) & = \sum_{y_1=0}^1 \sum_{y_2=0}^1 \sum_{y_3=0}^1 \sum_{y_4=0}^1\prod_{i=1}^4 p(y_i^o|y_i) p(y) = \\ & = \sum_{y_1=0}^1 \sum_{y_2=0}^1 \sum_{y_3=0}^1 \sum_{y_4=0}^1\prod_{i=1}^4 p(y_i^o|y_i) \frac{1}{Z} \prod_{\{y_i,y_j\} \in \mathcal C } \phi(y_i,y_j). \end{align}

Once we substitute $$y_1^o = 1, y_i^o=0 \forall i>1$$ in the expression above we get the denominator of (M). The numerator is composed from the elements mentioned above:

$$\begin{equation} p(y_1^o=1|y_1=1) \cdot \sum_{y_2=0}^1 \sum_{y_3=0}^1 \sum_{y_4=0}^1\prod_{i=2}^4 p(y_i^o=0|y_i) \frac{1}{Z} \phi(1,y_2) \phi(y_2,y_3) \phi(y_3,y_4) \phi(1,y_4). \end{equation}$$

Put together these pieces give you the formula in the beginning.

I guess there's still some effort needed to wrap one's mind around all of it. All the best!