Junction tree algorithm for DBN

A naïve approach to do inference on dynamic Bayesian network (DBN) is to unroll DBN for desired number of timesteps and treat it as a static BN. The problems with this are

• Typically the number of timesteps are unknown, and one may use a time window with a fixed length or do some kind of segmentation.
• Space requirement is high
• Dynamic filtering requires rebuilding the entire time history of the process on every timestep. (?)

Understanding the 2TBN (2 time-slice Bayes net) junction tree algorithm implementation

First of all, a junction tree is a clique tree that satisfies the junction tree property. A clique tree comes from the definition of a clique graph. A clique graph of G is a graph where the set of nodes is precisely the set of maximal cliques in G. And if the clique graph is also a tree, it is a clique tree. The junction tree property means that all the maximal cliques containing the same node v must form a connected subtree.

This is one of the algorithm in Kevin Murphy's Bayesian Network Toolbox. The file name is jtree_2TBN_inf_engine.m.

In the constructor of jtree_2TBN_inf_engine, it creates two jtree_engines. It creates one engine just for slice 1. And another engine for 1.5 slice. The 0.5 slice means the interface nodes from the previous slice. Interface nodes are nodes with children in the next slice. In the case of one-level AHMM, the interface nodes include \(G_t, S_t, F_t^G\). So in this case, the interface algorithm (Murphy, 2002) is the same as the frontier algorithm (Zweig, 1996). In the frontier algorithm, the frontier is the full set of hidden nodes.  It also always makes the interface nodes a clique.

One-level AHMM

Resources: http://ttic.uchicago.edu/~kgimpel/papers/jt-dbn.pdf

Computational complexity

http://courses.csail.mit.edu/6.006/fall11/lectures/lecture23.pdf

NP = {decision problems with solutions that can be "checked" polynomial time}

• It is based on the nondeterministic model where an algorithm makes guesses and then says YES or NO.
• Examples: Tetris

NP-hard = "as hard as" every problem in NP

NP-complete = NP \(\cap\) NP-hard

• Tetris is also NP-complete
• Other examples: knapsack, 3-Partition (given n integers, can you divide them into triples of equal sum?), traveling salesman problem, longest common subsequence of k strings, minesweeper, Sudoku, most puzzles, SAT, 3-coloring a given graph, find largest clique in a give graph

Graphical model

Graphical model is a method of using graphs (nodes and edges) to represent dependence or independence relationships among the random variables.

Approximate inference in Bayesian networks
Gibbs sampling

Matlab style guide

Here are some Matlab style guide combined from various sources. I added some changes based on personal preferences and consistency.

1. Kevin Murphy's style guide
2. http://www.datatool.com/downloads/matlab_style_guidelines.pdf

 Names

• Capitalize constants.
• Use camel back notation for vairables, as in hiddenMarkovModel. CamelBack always starts with a lower case letter, and then uses an upper case letter for each new word. Acronyms, such as GaussianHMM, also follow this convention, so would be written as gaussianHmm.
• Names of functions should be written in lower case. 
• It is clearest to have the function and its m-file names the same. Using lower case avoids potential filename problems in mixed operating system environments. 
• To improve readability, underscore may be used.
• Prefix variables denoting a number of elements with the letter n as in nValue for the number of values. 
• Suffix variables storing indices with Ndx as in dataNdx

Comments

• There is a convention that the first comment line after the function header will be searched by the lookfor command. Also, the first contiguous block of comments after the function header will be returned by the help and doc commands. 
• http://stackoverflow.com/questions/3840657/matlab-m-file-help-formatting

Git submodules

When you clone a git repository with submodules, you should add the --recursive option.

git clone --recursive git://github.com/foo/bar.git

If you forget to do that during the cloning, you can update the submodules by

git submodule update --init

init adds the submodule repository URLs to .git/config, and update checks out a specific commit, rather than the tip of a branch.