Inference of Bayesian networks made fast and easy using an extended depth-first search algorithm

June 27, 2017, University of Electro-Communications
Inference of Bayesian networks made fast and easy using an extended depth-first search algorithm
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 Electro-Communications

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 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 depth-first search (DFS) algorithm based on this principle. The DFS algorithm was based on two components: depth-first search and dynamic clique maintenance to scan and eliminate nodes and identify new cliques, respectively. However this method is time-consuming and leads to problems such as finding the same clique twice.

Here, Chao Li and Maomi Ueno at the University of Electro-Communications 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 , which greatly reduces the size of the search tree.

To validate the EDFS algorithm, the researchers randomly compared networks from a well-known 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 state-of-the-art Ottosen and Vomlel (DFS) algorithm in two orthogonal directions: (1) reduction of the overhead cost, and (2) reduction of the size of the space," conclude the authors. Time-efficient analysis of Bayesian networks can lead to quick deduction of vast amounts of data.

Explore further: Idiopathic pulmonary fibrosis algorithm performs poorly

More information: Chao Li et al. An extended depth-first search algorithm for optimal triangulation of Bayesian networks, International Journal of Approximate Reasoning (2016). DOI: 10.1016/j.ijar.2016.09.012

Related Stories

Idiopathic pulmonary fibrosis algorithm performs poorly

June 14, 2017

(HealthDay)—The traditional idiopathic pulmonary fibrosis (IPF) algorithm performs poorly, with positive predictive value of 42.2 percent and sensitivity of 55.6 percent, according to a study published in the June 1 issue ...

Better search engine results thanks to new method

May 12, 2016

How does Google decide which search results to display? Doctoral candidate Anne Schuth developed a new method by which dozens or even hundreds of search algorithms can be compared with each other simultaneously. This means ...

Improvements to a decision-making algorithm

December 27, 2016

In fields such as engineering, economics or finance, highly complex decisions must be made, often incorporating multiple, at times contradictory, objectives. Highly specialised computer algorithms can help find the best possible ...

Recommended for you

Nanoscale Lamb wave-driven motors in nonliquid environments

March 19, 2019

Light driven movement is challenging in nonliquid environments as micro-sized objects can experience strong dry adhesion to contact surfaces and resist movement. In a recent study, Jinsheng Lu and co-workers at the College ...

OSIRIS-REx reveals asteroid Bennu has big surprises

March 19, 2019

A NASA spacecraft that will return a sample of a near-Earth asteroid named Bennu to Earth in 2023 made the first-ever close-up observations of particle plumes erupting from an asteroid's surface. Bennu also revealed itself ...

The powerful meteor that no one saw (except satellites)

March 19, 2019

At precisely 11:48 am on December 18, 2018, a large space rock heading straight for Earth at a speed of 19 miles per second exploded into a vast ball of fire as it entered the atmosphere, 15.9 miles above the Bering Sea.

Levitating objects with light

March 19, 2019

Researchers at Caltech have designed a way to levitate and propel objects using only light, by creating specific nanoscale patterning on the objects' surfaces.


Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.