Do you know if there’s an efficient algorithm for determining when two subsets of a DAG are d-separated given another? The naive algorithm seems to be a bit slow.
Amusing name, linear time algorithm. Also amusingly I happen to have direct line of sight on the author while writing this post :).
In some sense, we know a priori that d-separation has to be linear time because it is a slightly fancy graph traversal. If you don’t like Bayes Ball, you can use the moralization algorithm due to Lauritzen (described here:
see slide titled “alternative equivalent separation”), which is slightly harder to follow for an unaided human, but which has a very simple implementation (which reduces to a simple DFS traversal of an undirected graph you construct).
Details? Content? Eliezer doesn’t even define d-separation, for starters.
Do you know if there’s an efficient algorithm for determining when two subsets of a DAG are d-separated given another? The naive algorithm seems to be a bit slow.
http://www.gatsby.ucl.ac.uk/~zoubin/course05/BayesBall.pdf
Amusing name, linear time algorithm. Also amusingly I happen to have direct line of sight on the author while writing this post :).
In some sense, we know a priori that d-separation has to be linear time because it is a slightly fancy graph traversal. If you don’t like Bayes Ball, you can use the moralization algorithm due to Lauritzen (described here:
http://www.stats.ox.ac.uk/~steffen/teaching/grad/graphicalmodels.pdf
see slide titled “alternative equivalent separation”), which is slightly harder to follow for an unaided human, but which has a very simple implementation (which reduces to a simple DFS traversal of an undirected graph you construct).
edit: fixed links, hopefully.
Yeah, sadly both links are broken for me.
Link is broken for me.