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.
Fast and optimal prediction on a labeled tree / N. Cesa-Bianchi, C. Gentile, F. Vitale - In: COLT 2009 : proceedings of the 22nd Annual Conference on Learning Theory, Montréal, Canada, June 18-21, 2009 / / [a cura di] A. Klivans, S. Dasgupta. - Madison : Omnipress, 2009. - ISBN 9780982252918. - pp. 145-156 (( Intervento presentato al 22. convegno Annual Conference on Learning Theory tenutosi a Montreal, Canada nel 2009.
Fast and optimal prediction on a labeled tree
N. Cesa-BianchiPrimo
;
2009
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.File | Dimensione | Formato | |
---|---|---|---|
treeopt-colt.pdf
accesso aperto
Tipologia:
Publisher's version/PDF
Dimensione
306.43 kB
Formato
Adobe PDF
|
306.43 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.