On: An Introduction to Probabilistic Graphical Models ...

[wvbeaaoo]

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 → wvbeaaoo]

It'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 → mamp]

by multiply connected graphs do you mean graphs with cycles ?

[mamp → wvbeaaoo]

Yes, although in directed acyclic graphs the 'cycles' manifest as multiple paths to a node.

[wvbeaaoo → mamp]

cycles 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 → wvbeaaoo]

Could you link to that paper? And does it have anything to do with the junction tree algorithm?

[wvbeaaoo → Xcelerate]

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 → wvbeaaoo]

Thanks!

[wvbeaaoo → Xcelerate]

the Christopher Bishop chapter on graphical models has a good section on junction trees IIRC