Timezone: »
We analyse matching pursuit for kernel principal components analysis by proving that the sparse subspace it produces is a sample compression scheme. We show that this bound is tighter than the KPCA bound of ShaweTaylor et al swck05 and highly predictive of the size of the subspace needed to capture most of the variance in the data. We analyse a second matching pursuit algorithm called kernel matching pursuit (KMP) which does not correspond to a sample compression scheme. However, we give a novel bound that views the choice of subspace of the KMP algorithm as a compression scheme and hence provide a VC bound to upper bound its future loss. Finally we describe how the same bound can be applied to other matching pursuit related algorithms.
Author Information
Zakria Hussain (University College London)
John ShaweTaylor (UCL)
John ShaweTaylor has contributed to fields ranging from graph theory through cryptography to statistical learning theory and its applications. However, his main contributions have been in the development of the analysis and subsequent algorithmic definition of principled machine learning algorithms founded in statistical learning theory. This work has helped to drive a fundamental rebirth in the field of machine learning with the introduction of kernel methods and support vector machines, driving the mapping of these approaches onto novel domains including work in computer vision, document classification, and applications in biology and medicine focussed on brain scan, immunity and proteome analysis. He has published over 300 papers and two books that have together attracted over 60000 citations. He has also been instrumental in assembling a series of influential European Networks of Excellence. The scientific coordination of these projects has influenced a generation of researchers and promoted the widespread uptake of machine learning in both science and industry that we are currently witnessing.
More from the Same Authors

2021 : Progress in SelfCertified Neural Networks »
Maria PerezOrtiz · Omar Rivasplata · Emilio ParradoHernández · Benjamin Guedj · John ShaweTaylor 
2020 Poster: PACBayes Analysis Beyond the Usual Bounds »
Omar Rivasplata · Ilja Kuzborskij · Csaba Szepesvari · John ShaweTaylor 
2018 Poster: PACBayes bounds for stable algorithms with instancedependent priors »
Omar Rivasplata · Emilio ParradoHernandez · John ShaweTaylor · Shiliang Sun · Csaba Szepesvari 
2018 Poster: Empirical Risk Minimization Under Fairness Constraints »
Michele Donini · Luca Oneto · Shai BenDavid · John ShaweTaylor · Massimiliano Pontil 
2018 Tutorial: Statistical Learning Theory: a Hitchhiker's Guide »
John ShaweTaylor · Omar Rivasplata 
2017 : John ShaweTaylor  Distribution Dependent Priors for Stable Learning »
John ShaweTaylor 
2017 : An Efficient Method to Impose Fairness in Linear Models »
Massimiliano Pontil · John ShaweTaylor 
2017 Workshop: Workshop on Prioritising Online Content »
John ShaweTaylor · Massimiliano Pontil · Nicolò CesaBianchi · Emine Yilmaz · Chris Watkins · Sebastian Riedel · Marko Grobelnik 
2017 Workshop: From 'What If?' To 'What Next?' : Causal Inference and Machine Learning for Intelligent Decision Making »
Ricardo Silva · Panagiotis Toulis · John ShaweTaylor · Alexander Volfovsky · Thorsten Joachims · Lihong Li · Nathan Kallus · Adith Swaminathan 
2016 Workshop: "What If?" Inference and Learning of Hypothetical and Counterfactual Interventions in Complex Systems »
Ricardo Silva · John ShaweTaylor · Adith Swaminathan · Thorsten Joachims 
2014 Poster: Multilabel Structured Output Learning with Random Spanning Trees of MaxMargin Markov Networks »
Mario Marchand · Hongyu Su · Emilie Morvant · Juho Rousu · John ShaweTaylor 
2012 Workshop: MultiTradeoffs in Machine Learning »
Yevgeny Seldin · Guy Lever · John ShaweTaylor · Nicolò CesaBianchi · Yacov Crammer · Francois Laviolette · Gabor Lugosi · Peter Bartlett 
2011 Workshop: New Frontiers in Model Order Selection »
Yevgeny Seldin · Yacov Crammer · Nicolò CesaBianchi · Francois Laviolette · John ShaweTaylor 
2011 Poster: PACBayesian Analysis of Contextual Bandits »
Yevgeny Seldin · Peter Auer · Francois Laviolette · John ShaweTaylor · Ronald Ortner 
2010 Talk: Opening Remarks and Awards »
Richard Zemel · Terrence Sejnowski · John ShaweTaylor 
2009 Workshop: Grammar Induction, Representation of Language and Language Learning »
Alex Clark · Dorota Glowacka · John ShaweTaylor · Yee Whye Teh · Chris J Watkins 
2008 Workshop: Learning from Multiple Sources »
David R Hardoon · Gayle Leen · Samuel Kaski · John ShaweTaylor 
2008 Workshop: New Challanges in Theoretical Machine Learning: Data Dependent Concept Spaces »
MariaFlorina F Balcan · Shai BenDavid · Avrim Blum · Kristiaan Pelckmans · John ShaweTaylor 
2007 Workshop: Music, Brain and Cognition. Part 1: Learning the Structure of Music and Its Effects On the Brain »
David R Hardoon · Eduardo ReckMiranda · John ShaweTaylor 
2007 Poster: Variational Inference for Diffusion Processes »
Cedric Archambeau · Manfred Opper · Yuan Shen · Dan Cornford · John ShaweTaylor 
2006 Workshop: Dynamical Systems, Stochastic Processes and Bayesian Inference »
Manfred Opper · Cedric Archambeau · John ShaweTaylor 
2006 Poster: Tighter PACBayes Bounds »
Amiran Ambroladze · Emilio ParradoHernandez · John ShaweTaylor