Exact Bayesian Learning of Ancestor Relations in Bayesian Networks
Yetian Chen, Lingjian Meng, Jin Tian
Abstract
Ancestor relations in Bayesian networks (BNs) encode long-range causal relations among random variables. In this paper, we develop dynamic programming (DP) algorithms to compute the exact posterior probabilities of ancestor relations in Bayesian networks. Previous algorithm by Parviainen and Koivisto (2011) evaluates all possible ancestor relations in time O(n3^n) and space O(3^n). 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 the uniform prior, we develop a new DP algorithm that computes the exact posteriors of all possible ancestor relations in time O(n^25^n-1) and space O(3^n). We also discuss the extension of our algorithm to computing the posteriors of s >p >t relations, i.e., a directed path from s to t via p. We apply our algorithm to a biological data set for discovering protein signaling pathways.
BibTeX
@InProceedings{pmlr-v38-chen15e,
title = {{Exact Bayesian Learning of Ancestor Relations in Bayesian Networks}},
author = {Chen, Yetian and Meng, Lingjian and Tian, Jin},
booktitle = {Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics},
pages = {174--182},
year = {2015},
editor = {Lebanon, Guy and Vishwanathan, S. V. N.},
volume = {38},
series = {Proceedings of Machine Learning Research},
address = {San Diego, California, USA},
month = {09--12 May},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v38/chen15e.pdf},
url = {https://proceedings.mlr.press/v38/chen15e.html},
abstract = {Ancestor relations in Bayesian networks (BNs) encode long-range causal relations among random variables. In this paper, we develop dynamic programming (DP) algorithms to compute the exact posterior probabilities of ancestor relations in Bayesian networks. Previous algorithm by Parviainen and Koivisto (2011) evaluates all possible ancestor relations in time O(n3^n) and space O(3^n). 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 the uniform prior, we develop a new DP algorithm that computes the exact posteriors of all possible ancestor relations in time O(n^25^n-1) and space O(3^n). We also discuss the extension of our algorithm to computing the posteriors of s >p >t relations, i.e., a directed path from s to t via p. We apply our algorithm to a biological data set for discovering protein signaling pathways.}
}