Timezone: »
Poster
Fast Prediction on a Tree
Mark Herbster · Massimiliano Pontil · Sergio Rojas Galeano
Given an $n$-vertex weighted tree with structural diameter $S$ and a subset of $m$ vertices, we present a technique to compute a corresponding $m \times m$ Gram matrix of the pseudoinverse of the graph Laplacian in $O(n+ m^2 + m S)$ time. We discuss the application of this technique to fast label prediction on a generic graph. We approximate the graph with a spanning tree and then we predict with the kernel perceptron. We address the approximation of the graph with either a minimum spanning tree or a shortest path tree. The fast computation of the pseudoinverse enables us to address prediction problems on large graphs. To this end we present experiments on two web-spam classification tasks, one of which includes a graph with 400,000 nodes and more than 10,000,000 edges. The results indicate that the accuracy of our technique is competitive with previous methods using the full graph information.
Author Information
Mark Herbster (University College London)
Massimiliano Pontil (IIT & UCL)
Sergio Rojas Galeano
Related Events (a corresponding poster, oral, or spotlight)
-
2008 Oral: Fast Prediction on a Tree »
Wed. Dec 10th 12:20 -- 12:40 AM Room
More from the Same Authors
-
2021 Poster: Improved Regret Bounds for Tracking Experts with Memory »
James Robinson · Mark Herbster -
2021 Poster: A Gang of Adversarial Bandits »
Mark Herbster · Stephen Pasteris · Fabio Vitale · Massimiliano Pontil -
2020 Poster: Online Matrix Completion with Side Information »
Mark Herbster · Stephen Pasteris · Lisa Tse -
2020 Poster: Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits »
Arya Akhavan · Massimiliano Pontil · Alexandre Tsybakov -
2020 Poster: The Advantage of Conditional Meta-Learning for Biased Regularization and Fine Tuning »
Giulia Denevi · Massimiliano Pontil · Carlo Ciliberto -
2020 Poster: Estimating weighted areas under the ROC curve »
Andreas Maurer · Massimiliano Pontil -
2020 Poster: Online Multitask Learning with Long-Term Memory »
Mark Herbster · Stephen Pasteris · Lisa Tse -
2019 Poster: Online Prediction of Switching Graph Labelings with Cluster Specialists »
Mark Herbster · James Robinson -
2019 Poster: Online-Within-Online Meta-Learning »
Giulia Denevi · Dimitris Stamos · Carlo Ciliberto · Massimiliano Pontil -
2019 Poster: Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm »
Giulia Luise · Saverio Salzo · Massimiliano Pontil · Carlo Ciliberto -
2019 Spotlight: Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm »
Giulia Luise · Saverio Salzo · Massimiliano Pontil · Carlo Ciliberto -
2018 Poster: Bilevel learning of the Group Lasso structure »
Jordan Frecon · Saverio Salzo · Massimiliano Pontil -
2018 Poster: Learning To Learn Around A Common Mean »
Giulia Denevi · Carlo Ciliberto · Dimitris Stamos · Massimiliano Pontil -
2018 Spotlight: Bilevel learning of the Group Lasso structure »
Jordan Frecon · Saverio Salzo · Massimiliano Pontil -
2017 : An Efficient Method to Impose Fairness in Linear Models »
Massimiliano Pontil · John Shawe-Taylor -
2017 Workshop: Workshop on Prioritising Online Content »
John Shawe-Taylor · Massimiliano Pontil · Nicolò Cesa-Bianchi · Emine Yilmaz · Chris Watkins · Sebastian Riedel · Marko Grobelnik -
2017 Poster: Consistent Multitask Learning with Nonlinear Output Relations »
Carlo Ciliberto · Alessandro Rudi · Lorenzo Rosasco · Massimiliano Pontil -
2016 Poster: Mistake Bounds for Binary Matrix Completion »
Mark Herbster · Stephen Pasteris · Massimiliano Pontil -
2015 : The Benefit of Multitask Representation Learning »
Massimiliano Pontil -
2015 Poster: Online Prediction at the Limit of Zero Temperature »
Mark Herbster · Stephen Pasteris · Shaona Ghosh -
2014 Poster: Spectral k-Support Norm Regularization »
Andrew McDonald · Massimiliano Pontil · Dimitris Stamos -
2013 Workshop: New Directions in Transfer and Multi-Task: Learning Across Domains and Tasks »
Urun Dogan · Marius Kloft · Tatiana Tommasi · Francesco Orabona · Massimiliano Pontil · Sinno Jialin Pan · Shai Ben-David · Arthur Gretton · Fei Sha · Marco Signoretto · Rajhans Samdani · Yun-Qian Miao · Mohammad Gheshlaghi azar · Ruth Urner · Christoph Lampert · Jonathan How -
2013 Poster: A New Convex Relaxation for Tensor Completion »
Bernardino Romera-Paredes · Massimiliano Pontil -
2012 Poster: Online Sum-Product Computation »
Mark Herbster · Fabio Vitale · Stephen Pasteris -
2012 Poster: Optimal kernel choice for large-scale two-sample tests »
Arthur Gretton · Bharath Sriperumbudur · Dino Sejdinovic · Heiko Strathmann · Sivaraman Balakrishnan · Massimiliano Pontil · Kenji Fukumizu -
2010 Spotlight: A Family of Penalty Functions for Structured Sparsity »
Charles A Micchelli · Jean M Morales · Massimiliano Pontil -
2010 Poster: A Family of Penalty Functions for Structured Sparsity »
Charles A Micchelli · Jean M Morales · Massimiliano Pontil -
2008 Poster: On-Line Prediction on Large Diameter Graphs »
Mark Herbster · Massimiliano Pontil · Guy Lever -
2007 Spotlight: A Spectral Regularization Framework for Multi-Task Structure Learning »
Andreas Argyriou · Charles A. Micchelli · Massimiliano Pontil · Yiming Ying -
2007 Poster: A Spectral Regularization Framework for Multi-Task Structure Learning »
Andreas Argyriou · Charles A. Micchelli · Massimiliano Pontil · Yiming Ying -
2006 Poster: Prediction on a Graph with a Perceptron »
Mark Herbster · Massimiliano Pontil -
2006 Spotlight: Prediction on a Graph with a Perceptron »
Mark Herbster · Massimiliano Pontil -
2006 Poster: Multi-Task Feature Learning »
Andreas Argyriou · Theos Evgeniou · Massimiliano Pontil