UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Kernel Polytope Faces Pursuit

Diethe, T; Hussain, Z; (2009) Kernel Polytope Faces Pursuit. In: Buntine, W and Grobelnik, M and Mladenic, D and ShaweTaylor, J, (eds.) MACHINE LEARNING AND KNOWLEDGE DISCOVERY IN DATABASES, PT I. (pp. 290 - 301). SPRINGER-VERLAG BERLIN

Full text not available from this repository.


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.

Type: Proceedings paper
Title: Kernel Polytope Faces Pursuit
Event: Joint European Conference on Machine Learning (ECML)/European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD)
Location: Bled, SLOVENIA
Dates: 2009-09-07 - 2009-09-11
ISBN-13: 978-3-642-04179-2
Keywords: Polytope Faces Pursuit, Orthogonal Matching Pursuit, Pseudo-dimension, Sample Compression Bounds, Regression, Kernel methods, VAPNIK-CHERVONENKIS DIMENSION
URI: http://discovery.ucl.ac.uk/id/eprint/101308
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item