4 ms·
by complexity of inference do you mean the complexity of learning the structure of a model ? because inference on an existing PGM is linear in the number of edg
by wvbeaaoo 10y ago
by complexity of inference do you mean the complexity of learning the structure of a model ? because inference on an existing PGM is linear in the number of edges with belief-propagation isn't it ?
- mamp 10y agoIt's linear in singly connected networks, not for multiply connected graphs. However NP-hard is the worst case as I mentioned (p288 Koller & Friedman)
- wvbeaaoo 10y agoby multiply connected graphs do you mean graphs with cycles ?
- mamp 10y agoYes, although in directed acyclic graphs the 'cycles' manifest as multiple paths to a node.
- wvbeaaoo 10y agocycles can be handled in two ways: if you are happy with approximate solutions, loopy BP can give that (still linear, but may take longer and there's parameter tuning), for exact solutions you can rewrite the graph to "carry" dependencies (latest paper by Frey)
- Xcelerate 10y agoCould you link to that paper? And does it have anything to do with the junction tree algorithm?
- wvbeaaoo 10y agohttp://www.psi.toronto.edu/~psi/pubs2/1999%20and%20before/134.pdf http://www.psi.toronto.edu/~psi/pubs2/1999%20and%20before/13... I don't know about junction trees but it probably connects as junction trees are a generalization of factor graphs
- Xcelerate 10y agoThanks!
- wvbeaaoo 10y agothe Christopher Bishop chapter on graphical models has a good section on junction trees IIRC