Fast and Optimal Prediction on a Labeled Tree
Abstract
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.
Cite
Text
Cesa-Bianchi et al. "Fast and Optimal Prediction on a Labeled Tree." Annual Conference on Computational Learning Theory, 2009.Markdown
[Cesa-Bianchi et al. "Fast and Optimal Prediction on a Labeled Tree." Annual Conference on Computational Learning Theory, 2009.](https://mlanthology.org/colt/2009/cesabianchi2009colt-fast/)BibTeX
@inproceedings{cesabianchi2009colt-fast,
title = {{Fast and Optimal Prediction on a Labeled Tree}},
author = {Cesa-Bianchi, Nicolò and Gentile, Claudio and Vitale, Fabio},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2009},
url = {https://mlanthology.org/colt/2009/cesabianchi2009colt-fast/}
}