1
$\begingroup$

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

Markov 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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – TheCG Oct 23 '19 at 16:49
  • $\begingroup$ if $x_i = x_j$ then 5, else 2 $\endgroup$ – Wouter Vandenputte Oct 23 '19 at 16:51
  • $\begingroup$ 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. $\endgroup$ – TheCG Oct 23 '19 at 17:09
2
+50
$\begingroup$

The answer :

\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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.