Kernel Polytope Faces Pursuit
published: Oct. 20, 2009, recorded: September 2009, views: 2849
Report a problem or upload filesIf you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Polytope Faces Pursuit (PFP) is a greedy algorithm that approximates the sparse solutions recovered by 1 regularised least-squares (Lasso) [4, 10] in a similar vein to (Orthogonal) Matching Pursuit (OMP) . 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) . 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  that takes into account a natural regression loss and experimental results on several benchmark datasets.
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !