= 27d567bc2d48d9f40e9ccc20ea370b15)
paper-machine comments on [LINK] If correlation doesn’t imply causation, then what does? - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (23)
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.