Random Projections for Linear Support Vector Machines
Let X be a data matrix of rank \rho, whose rows represent n points in d-dimensional space. The linear support vector machine constructs a hyperplane separator that maximizes the 1-norm soft margin. We develop a new oblivious dimension reduction technique which is precomputed and can be applied to any input matrix X. We prove that, with high probability, the margin and minimum enclosing ball in the feature space are preserved to within \epsilon-relative error, ensuring comparable generalization as in the original space in the case of classification. For regression, we show that the margin is preserved to \epsilon-relative error with high probability. We present extensive experiments with real and synthetic data to support our theory.
Code (0)
등록된 구현이 없습니다.
Tasks
Dimensionality ReductionGeneral ClassificationregressionSimilar Papers 제목 키워드 기반
Coding for Random Projections
The method of random projections has become very popular for large-scale applications in statistical learning, information retrieval, bio-informatics and other applications. Using a well-designed coding scheme for the pr…
Information RetrievalQuantizationRetrievalSupport vector machines and Radon's theorem
A support vector machine (SVM) is an algorithm that finds a hyperplane which optimally separates labeled data points in $\mathbb{R}^n$ into positive and negative classes. The data points on the margin of this separating …
Learning with Recursive Perceptual Representations
Linear Support Vector Machines (SVMs) have become very popular in vision as part of state-of-the-art object recognition and other classification tasks but require high dimensional feature spaces for good performance. Dee…
Image ClassificationObject RecognitionRandomized Kernel Methods for Least-Squares Support Vector Machines
The least-squares support vector machine is a frequently used kernel method for non-linear regression and classification tasks. Here we discuss several approximation algorithms for the least-squares support vector machin…
ClassificationGeneral ClassificationMulti-class ClassificationregressionEnhanced Expressive Power and Fast Training of Neural Networks by Random Projections
Random projections are able to perform dimension reduction efficiently for datasets with nonlinear low-dimensional structures. One well-known example is that random matrices embed sparse vectors into a low-dimensional su…
compressed sensingDimensionality Reduction