TY - GEN
T1 - Respecting Markov equivalence in computing posterior probabilities of causal graphical features
AU - Yong Kang, Eun
AU - Shpitser, Ilya
AU - Eskin, Eleazar
PY - 2010
Y1 - 2010
N2 - 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(n3n) 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(2n-1) v-structure features in O(n33n) time.
AB - 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(n3n) 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(2n-1) v-structure features in O(n33n) time.
UR - http://www.scopus.com/inward/record.url?scp=77958543971&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77958543971&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:77958543971
SN - 9781577354659
T3 - Proceedings of the National Conference on Artificial Intelligence
SP - 1175
EP - 1180
BT - AAAI-10 / IAAI-10 - Proceedings of the 24th AAAI Conference on Artificial Intelligence and the 22nd Innovative Applications of Artificial Intelligence Conference
PB - AI Access Foundation
T2 - 24th AAAI Conference on Artificial Intelligence and the 22nd Innovative Applications of Artificial Intelligence Conference, AAAI-10 / IAAI-10
Y2 - 11 July 2010 through 15 July 2010
ER -