Dynamic programming, tree-width and computation on graphical models
Stuart Geman, Brian Lucena · 2002
Computing on graphical models is a field of diverse interest today, due to the general applicability of these models. This thesis begins by giving background on the generalized Dynamic Programming (DP) method of performing inference computations (Chapter 1). We then (in Chapter 2) demonstrate explicity equivalences between different methods of computation and the importance of a parameter called tree-width. We go on to prove a novel method of bounding the tree-width of a graph by using maximum cardinality search. This gives a lower bound on the computational complexity of a graph with respect to standard methods. This bound can be quite weak or quite good. We provide experimental results demonstrating both cases. Chapter 3 is concerned with Coarse-to-Fine Dynamic Programming (CFDP), a method which can be faster than the standard methods, but requires special conditions. We prove theorems giving the complexity of CFDP for problems that meet certain criteria. These theoretical results are borne out with applications to specific problems.