Seeing a tree graphical model as a Markov model

Question

I have been doing an exercise task and I encountered an issue. Let's imagine that we have a graphical model(binary tree) as in the image below. To every vertex a rv $X_v$ is assigned which obtains values [0,1,2,3,4]. Let's furthermore say that for every vertex v of the tree, the CPD(conditional probability distribution) $\theta_v = p(X_v|x_{parent(v)})$ is a categorical distribution, and is given. We also have $ β = {x_l: l ∈ L(T)}$ being an assignment to all leaves of T.

I want to calculate p($\beta$|T, $\Theta$). In order to do this efficiently I believe I should use the Forward algorithm. But in order to do it, I somehow need to "convert" this model to a Markov model, i.e. somehow make the transition matrix(A) and emissions matrix(B). I believe I should somehow use the CPDs for this but I don't know how.

Answer 1

I think you want to see your graphical model as an hidden Markov model where at each vertex there is an variable belonging to the hidden process and the leave variables belong to the observed process.

The graphical representation of the tree you mention is missing from your message, but it is important to mention that the Markov property in the tree restricts the possible structure, notably:

• The successive layers form a top-down a Markov chain
• The components of a layer are independent given the previous layer
• The conditioning of a component of a layer reduces to its parents only

These properties are well described in this article. The corresponding graphical model can be represented this way (image from the same article):

The observed variables are in black circles and the hidden in white circles. Note that there can possibly be observed variables associated to every hidden variables, not only to at the leave layer.

Now that we have define the structure, it is indeed possible to adapt the forward algorithm for which we can still get an analytical expression for Markov trees (as in the case of Markov chains). Now this article and this article are a good source to reconstruct the forward algorithm.

Define $\pmb{X}$ as the hidden process and $\pmb{Y}$ as the observed process. We consider a Markov tree structure, with $N-1$ layer, where $V^n,n\in\{0, \dots, N-1\}$ denotes the set of hidden vertices at layer $n$. At layer $V^{N-1}$ there are only one hidden variable $\pmb{X}_v$, called the root node. $\forall n\in\{0, \dots, N-1\}, \forall v \in V^{n}$, $v^-$ refers to the father vertices of $v$ and $v^+$ to one of the son vertices of $v$. Let $A$ be the transition matrix ($A[x_{v^-},x_v]=p(x_v|x_{v^-})$ for all vertices $v$) and B be the emission matrix ($B[x_v,y_v]=p(y_v|x_v)$ for all vertices $v$).

Here are the step of the forward algorithm in a Markov tree with observations associated only the the hidden random variables located a the leave layer only ($n=0$):

• for $n=0$, \begin{equation} \alpha_0(x_v)=\sum_{x_{v^-}}A[x_{v^-},x_v]B[x_v,y_v] \end{equation}
• for $1\leq n<N-1$, where $V^+$ is the set of sons of $v$; \begin{equation} \alpha_n(x_v)=\sum_{x_{v^-}}A[x_{v^-},x_v]\prod_{v^+\in V^{+}}\alpha(x_{v^+}) \end{equation}
• for $n=N-1$, \begin{equation} \alpha_{N-1}(x_v)=p(x_v)\prod_{v^+\in V^{+}}\alpha(x_{v^+}) \end{equation}

You can compare with the forward algorithm expression we have in the case of Markov chains (eg wikipedia).