Gray_Area comments on Fake Causality - Less Wrong

41 Post author: Eliezer_Yudkowsky 23 August 2007 06:12PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (86)

Sort By: Old

You are viewing a single comment's thread.

Comment author: Gray_Area 24 August 2007 10:58:43AM 1 point [-]

Robin Hanson said: "Actually, Pearl's algorithm only works for a tree of cause/effects. For non-trees it is provably hard, and it remains an open question how best to update. I actually need a good non-tree method without predictable errors for combinatorial market scoring rules."

To be even more precise, Pearl's belief propagation algorithm works for the so-called 'poly-tree graphs,' which are directed acyclic graphs without undirected cycles (e.g., cycles which show up if you drop directionality). The state of the art for exact inference in bayesian networks are various junction tree based algorithms (essentially you run an algorithm similar to belief propagation on a graph where you force cycles out by merging nodes). For large intractable networks people resort to approximating what they are interested in by sampling. Of course there are lots of approaches to this problem: bayesian network inference is a huge industry.