Kernel Polytope Faces Pursuit

Tom Diethe*, Zakria Hussain

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

Abstract

Polytope Faces Pursuit (PFP) is a greedy algorithm that approximates the sparse solutions recovered by l(1) regularised least-squares (Lasso) [4,10] in a similar vein to (Orthogonal) Matching Pursuit (OMP) [16]. The algorithm is based on the geometry of the polar polytope where at each step a basis function is chosen by finding the maximal vertex using a. path-following method. The algorithmic complexity is of a similar order to OMP whilst being able to solve problems known to be hard for (O)MP. Matching Pursuit was extended to build kernel-based solutions to machine learning problems, resulting in the sparse regression algorithm, Kernel Matching, Pursuit (KMP) [17]. We develop a new algorithm to build sparse kernel-based solutions using PFP, which we call Kernel Polytope Faces Pursuit (KPFP). We show the usefulness of this algorithm by providing a generalisation error bound [7] that takes into account a natural regression loss and experimental results on several benchmark datasets.

Original languageEnglish
Title of host publicationMACHINE LEARNING AND KNOWLEDGE DISCOVERY IN DATABASES, PT I
EditorsW Buntine, M Grobelnik, D Mladenic, J ShaweTaylor
Place of PublicationBERLIN
PublisherSpringer Berlin Heidelberg
Pages290-301
Number of pages12
ISBN (Print)978-3-642-04179-2
Publication statusPublished - 2009
EventJoint European Conference on Machine Learning (ECML)/European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD) - Bled, Slovenia
Duration: 7 Sep 200911 Sep 2009

Publication series

NameLecture Notes in Artificial Intelligence
PublisherSPRINGER-VERLAG BERLIN
Volume5781
ISSN (Print)0302-9743

Conference

ConferenceJoint European Conference on Machine Learning (ECML)/European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD)
CountrySlovenia
Period7/09/0911/09/09

Keywords

  • Polytope Faces Pursuit
  • Orthogonal Matching Pursuit
  • Pseudo-dimension
  • Sample Compression Bounds
  • Regression
  • Kernel methods
  • VAPNIK-CHERVONENKIS DIMENSION

Cite this

Diethe, T., & Hussain, Z. (2009). Kernel Polytope Faces Pursuit. In W. Buntine, M. Grobelnik, D. Mladenic, & J. ShaweTaylor (Eds.), MACHINE LEARNING AND KNOWLEDGE DISCOVERY IN DATABASES, PT I (pp. 290-301). (Lecture Notes in Artificial Intelligence; Vol. 5781). Springer Berlin Heidelberg.