d-separation is a test for conditional independence in probability distributions that can be factorized using DAGs. It is a purely graphical test that uses the underlying graph and makes no reference to the actual distribution parameters. See for a formal definition.
The implementation is based on the conceptually simple linear time algorithm presented in . Refer to , for a couple of alternative algorithms.
Algorithm for testing d-separation in DAGs.
Algorithm for testing d-separation in DAGs.
d-separation is a test for conditional independence in probability distributions that can be factorized using DAGs. It is a purely graphical test that uses the underlying graph and makes no reference to the actual distribution parameters. See for a formal definition.
The implementation is based on the conceptually simple linear time algorithm presented in . Refer to , for a couple of alternative algorithms.
>>>
>>> # HMM graph with five states and observation nodes
... g = nx.DiGraph()
>>> g.add_edges_from(
... [
... ("S1", "S2"),
... ("S2", "S3"),
... ("S3", "S4"),
... ("S4", "S5"),
... ("S1", "O1"),
... ("S2", "O2"),
... ("S3", "O3"),
... ("S4", "O4"),
... ("S5", "O5"),
... ]
... )
>>>
>>> # states/obs before 'S3' are d-separated from states/obs after 'S3'
... nx.d_separated(g, {"S1", "S2", "O1", "O2"}, {"S4", "S5", "O4", "O5"}, {"S3"})
True
<Unimplemented 'footnote' '.. [1] Pearl, J. (2009). Causality. Cambridge: Cambridge University Press.'>
<Unimplemented 'footnote' '.. [2] Darwiche, A. (2009). Modeling and reasoning with Bayesian networks. \n Cambridge: Cambridge University Press.'>
<Unimplemented 'footnote' '.. [3] Shachter, R. D. (1998).\n Bayes-ball: rational pastime (for determining irrelevance and requisite\n information in belief networks and influence diagrams).\n In , Proceedings of the Fourteenth Conference on Uncertainty in Artificial\n Intelligence (pp. 480–487).\n San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.'>
<Unimplemented 'footnote' '.. [4] Koller, D., & Friedman, N. (2009).\n Probabilistic graphical models: principles and techniques. The MIT Press.'>
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them