Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
Linear Space
Randomized Algorithm
Spanning Tree
Weighted Graph
Subscribe
Academic
Publications
Random Spanning Trees and the Prediction of Weighted Graphs
Random Spanning Trees and the Prediction of Weighted Graphs,Nicolò CesaBianchi,Claudio Gentile,Fabio Vitale,Giovanni Zappella
Edit
Random Spanning Trees and the Prediction of Weighted Graphs
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Nicolò CesaBianchi
,
Claudio Gentile
,
Fabio Vitale
,
Giovanni Zappella
We show that the mistake bound for predict ing the nodes of an arbitrary
weighted graph
is characterized (up to logarithmic factors) by the cutsize of a random
spanning tree
of the graph. The cutsize is induced by the unknown adversarial labeling of the graph nodes. In deriving our characterization, we obtain a simple
randomized algorithm
achieving the optimal mistake bound on any weighted graph. Our algorithm draws a ran dom
spanning tree
of the original graph and then predicts the nodes of this tree in con stant amortized time and linear space. Ex periments on realworld datasets show that our method compares well to both global (Perceptron) and local (labelpropagation) methods, while being much faster.
Conference:
International Conference on Machine Learning  ICML
, pp. 175182, 2010
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.icml2010.org
)
(
homes.dsi.unimi.it
)
(
www.informatik.unitrier.de
)
References
(20)
Many random walks are faster than one
(
Citations: 40
)
Noga Alon
,
Chen Avin
,
Michal Koucký
,
Gady Kozma
,
Zvi Lotker
,
Mark R. Tuttle
Conference:
ACM Symposium on Parallel Algorithms and Architectures  SPAA
, pp. 119128, 2008
Regularization and SemiSupervised Learning on Large Graphs
(
Citations: 124
)
Mikhail Belkin
,
Irina Matveeva
,
Partha Niyogi
Published in 2004.
Label propagation and quadratic criterion
(
Citations: 36
)
Yoshua Bengio
,
Olivier Delalleau
,
Nicolas Le Roux
Learning from Labeled and Unlabeled Data using Graph Mincuts
(
Citations: 274
)
Avrim Blum
,
Shuchi Chawla
Conference:
International Conference on Machine Learning  ICML
, pp. 1926, 2001
Fast and Optimal Prediction on a Labeled Tree
(
Citations: 6
)
Nicolò CesaBianchi
,
Claudio Gentile
,
Fabio Vitale
Conference:
Computational Learning Theory  COLT
, 2009
Sort by:
Citations
(1)
Random Spanning Trees and the Prediction of Weighted Graphs
(
Citations: 1
)
Nicolò CesaBianchi
,
Claudio Gentile
,
Fabio Vitale
,
Giovanni Zappella
Conference:
International Conference on Machine Learning  ICML
, pp. 175182, 2010