nips nips2012 nips2012-260 nips2012-260-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Mark Herbster, Stephen Pasteris, Fabio Vitale
Abstract: 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, but requires time linear in the size of the tree, and is therefore 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-productlike 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 allocation problem in a multi-task setting. 1
[1] David Barber. Bayesian Reasoning and Machine Learning. Cambridge University Press, 2012.
[2] Christopher M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006.
[3] Frank R. Kschischang, Brenden J. Frey, and Hans Andrea Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47(2):498–519, 2001.
[4] Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119–139, 1997.
[5] Judea Pearl. Reverend Bayes on inference engines: A distributed hierarchical approach. In Proc. Natl. Conf. on AI, pages 133–136, 1982.
[6] Arthur L. Delcher, Adam J. Grove, Simon Kasif, and Judea Pearl. Logarithmic-time updates and queries in probabilistic networks. J. Artif. Int. Res., 4:37–59, February 1996.
[7] Theodoros Evgeniou, Charles A. Micchelli, and Massimiliano Pontil. Learning multiple tasks with kernel methods. Journal of Machine Learning Research, 6:615–637, 2005.
[8] Jacob Abernethy, Peter L. Bartlett, and Alexander Rakhlin. Multitask learning with expert advice. In COLT, pages 484–498, 2007.
[9] Mark Herbster, Massimiliano Pontil, and Lisa Wainer. Online learning over graphs. In ICML, pages 305–312. ACM, 2005.
[10] Mark Herbster, Guy Lever, and Massimiliano Pontil. Online prediction on large diameter graphs. In NIPS, pages 649–656. MIT Press, 2008.
[11] Nicol` Cesa-Bianchi, Claudio Gentile, and Fabio Vitale. Fast and optimal prediction on a o labeled tree. In COLT, 2009. 9