Timezone: »
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'' and
ii'' to find an efficient algorithm with a regret bound for the online {\em allocation} problem in a multi-task setting.
Author Information
Mark Herbster (University College London)
Fabio Vitale (University of Lille)
Stephen Pasteris (UCL)
More from the Same Authors
-
2021 Poster: Improved Regret Bounds for Tracking Experts with Memory »
James Robinson · Mark Herbster -
2021 Poster: A Gang of Adversarial Bandits »
Mark Herbster · Stephen Pasteris · Fabio Vitale · Massimiliano Pontil -
2020 Poster: Online Matrix Completion with Side Information »
Mark Herbster · Stephen Pasteris · Lisa Tse -
2020 Poster: Online Multitask Learning with Long-Term Memory »
Mark Herbster · Stephen Pasteris · Lisa Tse -
2019 Poster: Online Prediction of Switching Graph Labelings with Cluster Specialists »
Mark Herbster · James Robinson -
2016 Poster: Mistake Bounds for Binary Matrix Completion »
Mark Herbster · Stephen Pasteris · Massimiliano Pontil -
2015 Poster: Online Prediction at the Limit of Zero Temperature »
Mark Herbster · Stephen Pasteris · Shaona Ghosh -
2012 Poster: A Linear Time Active Learning Algorithm for Link Classification »
Nicolò Cesa-Bianchi · Claudio Gentile · Fabio Vitale · Giovanni Zappella -
2011 Poster: See the Tree Through the Lines: The Shazoo Algorithm »
Fabio Vitale · Nicolò Cesa-Bianchi · Claudio Gentile · Giovanni Zappella -
2011 Spotlight: See the Tree Through the Lines: The Shazoo Algorithm »
Fabio Vitale · Nicolò Cesa-Bianchi · Claudio Gentile · Giovanni Zappella -
2008 Poster: Fast Prediction on a Tree »
Mark Herbster · Massimiliano Pontil · Sergio Rojas Galeano -
2008 Oral: Fast Prediction on a Tree »
Mark Herbster · Massimiliano Pontil · Sergio Rojas Galeano -
2008 Poster: On-Line Prediction on Large Diameter Graphs »
Mark Herbster · Massimiliano Pontil · Guy Lever -
2007 Poster: On higher-order perceptron algorithms »
Claudio Gentile · Fabio Vitale · Cristian Brotto -
2006 Poster: Prediction on a Graph with a Perceptron »
Mark Herbster · Massimiliano Pontil -
2006 Spotlight: Prediction on a Graph with a Perceptron »
Mark Herbster · Massimiliano Pontil