UMass Machine Learning and Friends Lunch | Main / Adaptive Bayesian Inference

Motivated by stochastic systems in which observed evidence and conditional dependencies between states of the network change over time, and certain quantities of interest (marginal distributions, likelihood estimates etc.) must be updated, we study the problem of "adaptive inference" in factor graphs. For tree-structured inputs, I will describe an algorithm for adaptive inference that handles a broad range of changes to the input graph and is able to maintain marginal distributions, MAP estimates, and data likelihoods in all expected logarithmic time. At a high level, our algorithm works by choosing an elimination order and storing the resulting partial marginalizations in a way that guarantees that a marginal queries and updates to the input tree can be handled in O(log n) time. In general graphs, our algorithm can be extended handle arbitrary edge insertions and deletions. The running time is still logarithmic in n, but we incur exponential dependence in the running time on a property of the graph we call "cut size". I will also discuss some preliminary work on applying this algorithm to determining sidechain conformations in protein structures.