Learning Kernel Perceptrons on Noisy Data Using Random Projections Export

@incollection{Stempfel:2007, abstract = {In this paper, we address the issue of learning nonlinearly separable concepts with a kernel classifier in the situation where the data at hand are altered by a uniform classification noise. Our proposed approach relies on the combination of the technique of random or deterministic projections with a classification noise tolerant perceptron learning algorithm that assumes distributions defined over finite-dimensional spaces. Provided a sufficient separation margin characterizes the problem, this strategy makes it possible to envision the learning from a noisy distribution in any separable Hilbert space, regardless of its dimension; learning with any appropriate Mercer kernel is therefore possible. We prove that the required sample complexity and running time of our algorithm is polynomial in the classical PAC learning parameters. Numerical simulations on toy datasets and on data from the UCI repository support the validity of our approach.}, author = {Stempfel, Guillaume and Ralaivola, Liva}, citeulike-article-id = {5890104}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-75225-7_27}, citeulike-linkout-1 = {http://www.springerlink.com/content/p748160543364182}, doi = {10.1007/978-3-540-75225-7_27}, journal = {Algorithmic Learning Theory}, keywords = {kernel-trick, perceptron-learning-rule, phd}, pages = {328--342}, posted-at = {2009-10-05 13:02:40}, priority = {3}, title = {Learning Kernel Perceptrons on Noisy Data Using Random Projections}, url = {http://dx.doi.org/10.1007/978-3-540-75225-7_27}, year = {2007} }

TY - CHAP ID - Stempfel:2007 L3 - citeulike-article-id:5890104 N2 - In this paper, we address the issue of learning nonlinearly separable concepts with a kernel classifier in the situation where the data at hand are altered by a uniform classification noise. Our proposed approach relies on the combination of the technique of random or deterministic projections with a classification noise tolerant perceptron learning algorithm that assumes distributions defined over finite-dimensional spaces. Provided a sufficient separation margin characterizes the problem, this strategy makes it possible to envision the learning from a noisy distribution in any separable Hilbert space, regardless of its dimension; learning with any appropriate Mercer kernel is therefore possible. We prove that the required sample complexity and running time of our algorithm is polynomial in the classical PAC learning parameters. Numerical simulations on toy datasets and on data from the UCI repository support the validity of our approach. JF - Algorithmic Learning Theory EP - 342 TI - Learning Kernel Perceptrons on Noisy Data Using Random Projections SP - 328 KW - kernel-trick KW - perceptron-learning-rule KW - phd AU - Stempfel, Guillaume AU - Ralaivola, Liva PY - 2007/// UR - http://dx.doi.org/10.1007/978-3-540-75225-7_27 ER -