Direct Graphical Models
v.1.5.2

In the Chain demo we considered chainstructured graph, one of the simplest types of dependency where we could take advantage of the graphical structure to allow efficient inference. In this demo, we consider more complex problem involving treestructured graphical model. In particular, we consider the case where the arcs in the graph can be arbitrary, as long as there is one, and only one, path between any pair of nodes. For such graphs we can still perform efficient inference by applying generalizations of the methods designed for chainstructured models. This example copies the idea from the Water Turbidity Problem
In order to run this demo, please execute "Demo 1D.exe" tree command
We build a tree, consisting of 100 nodes with each having 4 states. Function buildTree() returns a random treestructured graph, filled with initial node and edge potentials. The tree is build such that there is one, and only one, path between any pair of nodes and therefore does not have loops. Nodes with only arc is called a leaf. Function srand(0) assures that the graph structure remains the same during multiple execution of the demo:
Next, we separate all the nodes into 3 types and assigne them the following labels:
After the tree was created, its nodes had potentials \((\frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4})^\top\). Now, we substitute the potentials of the source nodes with the potential \((0.9, 0.09, 0.009, 0.001)^\top\), returned with function getNodePot():
The edge potential matrix is represented here as a transition matrix:
from\to  st.0  st.1  st.2  st.3 

st.0  0.9890  0.0099  0.0010  0.0001 
st.1  0.1309  0.8618  0.0066  0.0007 
st.2  0.0420  0.0841  0.8682  0.0057 
st.3  0.0667  0.0333  0.1667  0.7333 
e.g. a probability of switching from state 3 to state 1 is 0.0333. The edge potential is returned with function getEdgePot().
After the tree was created, its edges had symmetric potentials: \(\frac{1}{2}edgePot^\top+\frac{1}{2}edgePot\). Now, we have to reinitialize the edge potentials with the original nonsymmetrical \(edgePot\): set them in the direction from the source nodes to the tap nodes DirectGraphicalModels::CGraph::setArc(size_t src, size_t dst, const Mat& edgePot):
The number of all possible configurations for our tree is equal to \(4^{100}\approx 1.61\times 10^{60}\), and it is not feasible to calculate joint probabilities for all of these configurations. Nevertheless, DGM has an efficient framework for exact inference in treestructured graphs DirectGraphicalModels::CInferTree, which is based on the sumproduct algorithm:
Please note, that in case of a single source, its marginal probability is equal to the initial probability.