Name
Abstract | ||
|---|---|---|
Let X be a data matrix of rank ρ, 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 that 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 ε-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 ε-relative error with high probability. We present extensive experiments with real and synthetic data to support our theory. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1145/2641760 | TKDD |
Keywords | Field | DocType |
algorithms,experimentation,dimensionality reduction,general,optimization,theory,classification,design methodology,support vector machines | Row,Feature vector,Dimensionality reduction,Matrix (mathematics),Support vector machine,Synthetic data,Artificial intelligence,Hyperplane,Margin classifier,Machine learning,Mathematics | Journal |
Volume | Issue | ISSN |
8 | 4 | 1556-4681 |
Citations | PageRank | References |
15 | 0.64 | 24 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Saurabh Paul | 1 | 54 | 3.23 |
| Christos Boutsidis | 2 | 610 | 33.37 |
| Malik Magdon-Ismail | 3 | 914 | 104.34 |
| Petros Drineas | 4 | 2165 | 201.55 |