Fast and optimal prediction of a labeled tree
Nicolò Cesa-Bianchi, Claudio Gentile and Fabio Vitale
In: Colt 2010, 18-21 June 2009, Montreal, Canada.
We characterize, up to constant factors, the number
of mistakes necessary and sufficient for sequentially predicting
a given tree with binary labeled nodes. We provide an
efficient algorithm achieving this number of mistakes on any tree.
Tree prediction algorithms can solve the general graph prediction
problem by representing the graph via one of its spanning trees.
In order to cope with adversarial assignments of labels over a general
graph, we advocate the use of random spanning trees, which
have the additional advantage of retaining relevant
spectral information of the original graph.