Font Size:

Respecting Markov Equivalence in Computing Posterior Probabilities of Causal Graphical Features

Last modified: 2010-07-04

#### Abstract

There have been many efforts to identify causal graphical features such as directed edges between random variables from observational data. Recently, Tian et al. proposed a new dynamic programming algorithm which computes marginalized posterior probabilities of directed edge features over all the possible structures in O(

*n*3^{n}) time when the number of parents per node is bounded by a constant, where*n*is the number of variables of interest. However the main drawback of this approach is that deciding a single appropriate threshold for the existence of the directed edge feature is difficult due to the scale difference of the posterior probabilities between the directed edges forming*v-*structures and the directed edges not forming*v*-structures. We claim that computing posterior probabilities of both adjacencies and*v*-structures is necessary and more effective for discovering causal graphical features, since it allows us to find a single appropriate decision threshold for the existence of the feature that we are testing. For efficient computation, we provide a novel dynamic programming algorithm which computes the posterior probabilities of all of*n*(*n*– 1)/2 adjacency and*n*(*n*–1 choose 2)*v*-structure features in O(*n*^{3}* 3^{n}) time.#### Keywords

graphical models; learning; Markov equivalence

Full Text:
PDF