Publication Date

8-27-2014

Technical Report Number

TR14-10

Subjects

Computing Methodologies, Mathematics of Computing

Abstract

In this paper we develop a dynamic programming algorithm to compute the exact posterior probabilities of ancestor relations in Bayesian networks. Previous dynamic programming (DP) algorithm by (Parviainen and Koivisto, 2011) evaluates all possible ancestor relations in time O(n3n) and space O(3n) . However, their algorithm assumes an order-modular prior over DAGs that does not respect Markov equivalence. The resulting posteriors would bias towards DAGs consistent with more linear orders. To adhere to uniform prior, we develop a new DP algorithm that computes the exact posteriors of all possible ancestor relations in time O(n5n-1) and space O(3n).

Date Available

09/01/2014

Share

COinS