@inproceedings{096f414a3e8141529d78a542e06735c9,

title = "Kernel Polytope Faces Pursuit",

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.",

keywords = "Polytope Faces Pursuit, Orthogonal Matching Pursuit, Pseudo-dimension, Sample Compression Bounds, Regression, Kernel methods, VAPNIK-CHERVONENKIS DIMENSION",

author = "Tom Diethe and Zakria Hussain",

year = "2009",

language = "English",

isbn = "978-3-642-04179-2",

series = "Lecture Notes in Artificial Intelligence",

publisher = "Springer Berlin Heidelberg",

pages = "290--301",

editor = "W Buntine and M Grobelnik and D Mladenic and J ShaweTaylor",

booktitle = "MACHINE LEARNING AND KNOWLEDGE DISCOVERY IN DATABASES, PT I",

address = "Germany",

note = "Joint European Conference on Machine Learning (ECML)/European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD) ; Conference date: 07-09-2009 Through 11-09-2009",

}