Inference of Bayesian networks made fast and easy using an extended depthfirst Source: University of ElectroCommunications
Connected vertices form a triangulated Bayesian network (a) and cliques of each triangle form the nodes of its corresponding junction tree (b). Credit: University of ElectroCommunications
A Bayesian network is a directed acyclic graph (DAG) or a probabilistic graphical model used by statisticians. Vertices of this model represent different variables. Any connections between variables indicate a conditional dependency and a lack of connections implies a lack of it.
Traditionally, Bayesian networks are used for modelling and inference of large amounts of information using algorithms. One such common algorithm is the junction tree algorithm that uses the method of triangulation: The DAG is simplified into triangles, based on the connections (regardless of direction) and subsequently cliques making up each triangle act as junctions or "nodes" of a hierarchical tree. Ottosen and Vomlel first proposed the depthfirst search (DFS) algorithm based on this principle. The DFS algorithm was based on two components: depthfirst search and dynamic clique maintenance to scan and eliminate nodes and identify new cliques, respectively. However this method is timeconsuming and leads to problems such as finding the same clique twice.
Here, Chao Li and Maomi Ueno at the University of ElectroCommunications in Tokyo have further refined this algorithm and created a new extended depth first algorithm (EDFS). Based on their algorithm, only cliques with new edges introduced are selected, thus making clique selection very specific. Their second improvement to the algorithm is "pivot clique pruning". This is a sophisticated method of eliminating orders or variables from the network, which greatly reduces the size of the search tree.
To validate the EDFS algorithm, the researchers randomly compared networks from a wellknown database with the DFS algorithm. They found that the total running times and time for depth first search and dynamic clique maintenance were less compared to the DFS algorithm.
"The new EDFS algorithm improves the stateoftheart Ottosen and Vomlel (DFS) algorithm in two orthogonal directions: (1) reduction of the overhead cost, and (2) reduction of the size of the search space," conclude the authors. Timeefficient analysis of Bayesian networks can lead to quick deduction of vast amounts of data.

