Adaptive inference for graphical models
László Babai, Umut A. Acar, Özgür Sümer · 2012
Many algorithms and applications involve repeatedly solving a variation of the same statistical inference problem. Adaptive inference is a technique where the previous computations are leveraged to speed up the computations after modifying the model parameters. This approach is useful in situations where a time-consuming statistical inference procedure needs to be re-run after some minor manual changes or in situations where the model is changing over time in minor ways. For example while studying the effects of mutations on proteins, one often constructs models that change slowly as mutations are introduced. Another important application of adaptive inference is in situations where the model is being used iteratively; for example in approximate inference we may want to decompose the problem into simpler inference subproblems that are solved repeatedly and iteratively using adaptive updates. In this thesis we explore both exact inference and iterative approximate inference approaches using adaptive updates. We first present algorithms for adaptive exact inference on general graphs that can be used to efficiently compute marginals and update MAP configurations under arbitrary changes to the input factor graph and its associated elimination tree. We then apply our algorithms to approximate inference using a framework called dual decomposition. The key to our approach is a linear time preprocessing step which builds a data structure called a cluster tree that can efficiently be maintained when the underlying model is slightly modified. We demonstrate how a cluster tree can be used to compute any marginal in time that is logarithmic in the size of the input model. Moreover, our approach can also be used to update MAP configurations in time that is roughly proportional to the number of updated entries, rather than the size of the input model. This fact enables us to use our framework to speed up the convergence of dual-decomposition methods. Our technique is also amenable to parallelism, and we explore its ability to use multi-core parallelism in the context of dual-decomposition approximation methods. The research is performed in collaboration with U. A. Acar, A. T. Ihler, and R. R. Mettu.