Exact Inference in Graphical Models: is There More to it?
Julian McAuley, Tibério S. Caetano · arXiv (Cornell University) · 2009
In general, the Junction-Tree Algorithm is ‘the solution ’ to exact inference in graphical models. It has running time O(AN C) where ◮ A is the number of nodes ◮ N is the domain size for each node ◮ C is the size of the maximal cliques in the triangulated graph nodes maximal cliques factors Factor Graphs O(AN C) can be pretty bad, since triangulating the graph often increases its maximal clique size. Instead, people often resort to inference in loopy factor-graphs, whose running time is O(AN F), where F is the size of the factors. However, this is generally inexact. nodes maximal cliques factors Some Examples ◮ models for pose reconstruction, e.g. [Sigal and Black, 2006] ◮ pairwise factors allow for some ‘elasticity’ of the joints ◮ maximal cliques of size threeSome Examples ◮ models with loops, e.g. [Coughlan and Ferreira, 2002] ◮ after triangulation, maximal cliques have size three ◮ loopy belief-propagation can be shown to converge to the correct solutionSome Examples ◮ skip-chain CRFs, e.g. [Sutton and McCallum, 2006,