Timezone: »

 
Poster
Online Sum-Product Computation
Mark Herbster · Fabio Vitale · Stephen Pasteris

Tue Dec 04 07:00 PM -- 12:00 AM (PST) @ Harrah’s Special Events Center 2nd Floor
in Poster Session »

We consider the problem of performing efficient sum-product computations in an online setting over a tree. A natural application of our methods is to compute the marginal distribution at a vertex in a tree-structured Markov random field. Belief propagation can be used to solve this problem. However, belief propagation requires time linear in the size of the tree. This is too slow in an online setting where we are continuously receiving new data and computing individual marginals. With our method we aim to update the data and compute marginals in time that is no more than logarithmic in the size of the tree, and is often significantly less. We accomplish this via a hierarchical covering structure that caches previous local sum-product computations. Our contribution is three-fold: we i) give a linear time algorithm to find an optimal hierarchical cover of a tree; ii) give a sum-product-like algorithm to efficiently compute marginals with respect to this cover; and iii) apply i'' andii'' to find an efficient algorithm with a regret bound for the online {\em allocation} problem in a multi-task setting.

[ PDF] 

Author Information

Mark Herbster (University College London)
Fabio Vitale (University of Lille)
Stephen Pasteris (UCL)

More from the Same Authors