HIIT Kumpula Seminar: Three ways to divide order graph in parallel algorithms for Bayesian network structure learning

Abstract: Some dynamic programming algorithms for Bayesian network structure learning problem operate on a search graph, i.e. order graph, which is a Hasse-diagram for the set of variables in the problem (Malone et al., AAAI-11). In particular, two parallel algorithms by Tamada et al. (JMLR-2011) and Nikolova et al. (JPDC-2013) have been earlier presented in the literature. The former divides the order graph based on super combinations while the latter uses hypercubes for the division during the search. The presentation reviews these two methods for dividing the order graph. In addition, a third method is outlined based on using first-k subcombinations introduced in the author's Master's thesis.

Presenter: Niklas Jahnsson submitted his Master's thesis about using first-k subcombinations in dividing a single layer of the order graph in an external memory frontier breadth-first branch and bound search algorithm for Bayesian network structure learning. He works as a Java developer in a team specialising to electronic foreign exchange offering of Nordea Markets in Copenhagen.