Direct Graphical Models  v.1.5.2
Chain

In this demo we consider more complex problem involving the chain of nodes. Such a problem is common in Markov chains and hidden Markov models These models may incorporate large graphs, what prevents from using brute-force exact decoding and inference algorithms. Nevertheless, we can take an advantage of the conditional independence properties induced by the chain structure and use polynomial-time exact message-passing inference algorithm. This example copies the idea from the Computer Science Graduate Careers

In order to run this demo, please execute "Demo 1D.exe" chain command

## Building The Markov Chain

We build a chain, consisting of 60 nodes, which represents 60 years. Every node has 7 states and the first, initial node will have the potential: $$(0.3, 0.6, 0.1, 0, 0, 0, 0)^\top$$, whereas all other nodes are initiated with uniform distribution: $$(\frac{1}{7}, \frac{1}{7}, \frac{1}{7}, \frac{1}{7}, \frac{1}{7}, \frac{1}{7}, \frac{1}{7})^\top$$. We connect all nodes into a chain with undirected arcs:

using namespace DirectGraphicalModels;
const byte nStates = 7; // {grad scool, industry, video games, industry (with PhD), academia, video games (with PhD), deceased}
const size_t nNodes = 60; // sixty years
CGraph *graph = new CGraph(nStates);
Mat nodePot = getNodePot();
nodePot.setTo(1.0f / nStates); // uniform distribution
for (size_t i = 1; i < nNodes; i++)
Mat edgePot = getEdgePot();
for (size_t i = 0; i < nNodes - 1; i++)

The edge potential matrix is represented here as a transition matrix:

from\tost.0st.1st.2st.3st.4st.5st.6
st.0 0.080.900.010 0 0 0.01
st.1 0.030.950.010 0 0 0.01
st.2 0.060.060.750.050.050.020.01
st.3 0 0 0 0.300.600.090.01
st.4 0 0 0 0.020.950.020.01
st.5 0 0 0 0.010.010.970.01
st.6 0 0 0 0 0 0 1

e.g. a probability of switching from state 3 at year i to state 5 at year i + 1 is 0.09. The node and edge potentials are returned with functions getNodePot() and getEdgePot() respectively.

## Inference

The number of all possible configurations for our chain is equal to $$7^{60}\approx 5.08\times 10^{50}$$, and it is not feasible to calculate joint probabilities for all of these configurations. Nevertheless, DGM has exact inference method for chains DirectGraphicalModels::CInferChain, which is based on a message-passing algorithm with the total cost of evaluating the marginals of $$O(nNodes\cdot nStates^2)$$:

using namespace DirectGraphicalModels;
CInfer *inferer = new CInferChain(graph);
inferer->infer();

## Results

Finally, we depict the results of inference. Please note, that the marginal probability for the first node is equal to the initial probability: