Polynomial-Time Algorithm for Learning Optimal BFS-Consistent Dynamic Bayesian Networks

Dynamic Bayesian networks (DBN) are powerful probabilistic representations that model stochastic processes. They consist of a prior network, representing the distribution over the initial variables, and a set of transition networks, representing the transition distribution between variables over tim...

Full description

Saved in:
Bibliographic Details
Published in:Entropy (Basel, Switzerland) Switzerland), 2018-04, Vol.20 (4), p.274
Main Authors: Sousa, Margarida, Carvalho, Alexandra
Format: Article
Language:English
Subjects:
Algorithms
Bayesian analysis
Complexity
Computer simulation
dynamic Bayesian networks
Machine learning
Markov processes
optimum branching
Polynomials
Random variables
score-based learning
Stochastic processes
theoretical-information scores
Transportation networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Dynamic Bayesian networks (DBN) are powerful probabilistic representations that model stochastic processes. They consist of a prior network, representing the distribution over the initial variables, and a set of transition networks, representing the transition distribution between variables over time. It was shown that learning complex transition networks, considering both intra- and inter-slice connections, is NP-hard. Therefore, the community has searched for the largest subclass of DBNs for which there is an efficient learning algorithm. We introduce a new polynomial-time algorithm for learning optimal DBNs consistent with a breadth-first search (BFS) order, named bcDBN. The proposed algorithm considers the set of networks such that each transition network has a bounded in-degree, allowing for p edges from past time slices (inter-slice connections) and k edges from the current time slice (intra-slice connections) consistent with the BFS order induced by the optimal tree-augmented network (tDBN). This approach increases exponentially, in the number of variables, the search space of the state-of-the-art tDBN algorithm. Concerning worst-case time complexity, given a Markov lag m, a set of n random variables ranging over r values, and a set of observations of N individuals over T time steps, the bcDBN algorithm is linear in N, T and m; polynomial in n and r; and exponential in p and k. We assess the bcDBN algorithm on simulated data against tDBN, revealing that it performs well throughout different experiments.
ISSN:1099-4300
1099-4300
DOI:10.3390/e20040274