Random Projections for Linear Support Vector Machines

Introduction

In the above formulation, the unknown lagrange multipliers $\{\alpha_{i}\}_{i=1}^{n}$ are constrained to lie inside the “box constraint” $[0,C]^{n}$, where $C$ is part of the input. In order to measure the out-of-sample performance of the SVM classifier, we can use the VC-dimension of fat-separators. Assuming that the data lie in a ball of radius $B$, and that the hypothesis set consists of hyperplanes of width $\gamma$ (corresponding to the margin), then the $VC$-dimension of this hypothesis set is $O(B^{2}/\gamma^{2})$ . Now, given the in-sample error, we can obtain a bound for the out-of-sample error, which is monotonic in the VC-dimension .

Analogous to the 1-norm soft margin formulation for SVM classification, we have a similar formulation for regression called the linear $\varepsilon$-insensitive loss SVM . The dual problem for $\varepsilon$-insensitive loss SVM regression is formulated as:

Here, $\{\alpha\}_{i=1}^{n}$ are the Lagrange multipliers and they lie in the interval $[-C,C]^{n}.$

1.2 SVM Regression

2 Dimension Reduction

For regression, the SVM optimization problem becomes

The pratical intent of using linear SVM after random projections is to reduce computational complexity of training SVM and memory. For large-scale datasets, that are too big to fit into memory (see Section 4.1.3 for details), random projections serve as a possible way to estimate out-of-sample error. Random projections reduce the computational complexity of training SVM which is evident from the experiments described in Section 4.

3 Our Contribution

Our main theorem will be stated in terms of the randomized Hadamard Transform, but similar statements can be obtained for the other three transforms.

4 Prior work

Blum05 showed relative error margin preservation for linearly separable data by angle preservation between points when using random orthogonal matrix, standard gaussian matrix and the random sign matrix. We show relative-error margin preservation for non-separable data and use methods that improve running time to compute random projections. \citeNShi12 establish the conditions under which margins are preserved after random projection and show that error free margins are preserved for both binary and multi-class problems if these conditions are met. They discuss the theory of margin and angle preservation after random projections using Gaussian matrices. They show that margin preservation is closely related to acute angle preservation and inner product preservation. Smaller acute angle leads to better preservation of the angle and the inner product. When the angle is well preserved, the margin is well-preserved too. There are two main differences between their result and ours. They show margin preservation to within additive error, whereas we give margin preservation to within relative error. This is a big difference especially when the margin is small. Moreover, they analyze only the separable case. We analyze the general non-separable dual problem and give a result in terms of the norm of the weight vector. For the separable case, the norm of the weight vector directly relates to the margin. For the non-separable case, one has to analyze the actual quadratic program, and our result essentially claims that the solution in the transformed space will have comparably regularized weights as the solution in the original space.

Shi09 used hash kernels which approximately preserved inner product to design a biased approximation of the kernel matrix. The hash kernels can be computed in the number of non-zero terms of a data matrix similar to the method of \citeNClark12, \citeNMeng13 and \citeNNN13 that we employed. \citeNShi09 used random sign matrices to compute random projections which typically increase the number of non-zero terms of the data matrix. However, the method of \citeNClark12, \citeNMeng13 and \citeNNN13 takes advantage of input sparsity. \citeNShi09 showed that their generalization bounds on the hash kernel and the original kernel differed by the inverse of the product of the margin and number of datapoints. For smaller margins, this difference will be high. Our generalization bounds are independent of the original margin and hold for arbitrarily small margins.

Zhang12 developed algorithms to accurately recover the optimal solution to the original SVM optimization problem using a Gaussian random projection. They compute the dual solution provided that the data matrix has low rank. This is different from our work since we analyze the ratio of radius of the minimum enclosing ball to the margin using random projections and do not try to recover the solution.

Finally, it is worth noting that random projection techniques have been applied extensively in the compressed sensing literature, and our theorems have the same flavor to a number of results in that area. However, to the best of our knowledge, the compressed sensing literature has not investigated the 1-norm soft-margin SVM optimization problem.

Random Projection Matrices

More recently, faster methods of constructing random projections have been developed, using, for example, the Fast Hadamard Transform – FHT for short. The Hadamard-Walsh matrix for any $d$ that is a power of two is defined as

Geometry of SVM is preserved under Random Projection

We now state and prove our main result, namely that solving the SVM optimization problem in the projected space results in comparable margin and data radius as in the original space. The following lemma will be crucial in our proof.

The proof of this result is a simple application of Theorem 3.1(i) of \citeNZouzi11.

The proof of this result follows from Theorem 1 of \citeNMeng13.

The proof of this result follows from Corollary 6 of \citeNZhang12.

Lemma 3.7 does not have the log factors as in Lemma 3.1, but Gaussian projections are slower since they require full matrix-matrix multiplications.

We now proceed to bound the second term in the right-hand side of the above equation. Towards that end, we bound the difference:

Combining eqns. (17), (18), and (19), we get

(of Theorem 1.1) The proof of Theorem 1.1 follows by combining Theorem 3.9, Lemma 3.1, and Theorem 3.11. The failure probability is at most $2\delta$, by a simple application of the union bound.

Experiments

In our experimental evaluations, we implemented random projections using four different methods: RG, RS, FHT, and CW (see Section 2 for definitions) in MATLAB version 7.13.0.564 (R2011b). We ran the algorithms using the same values of $r$ (the dimension of the projected feature space) for all algorithms, but we varied $r$ across different datasets. We used LIBLINEAR and LIBSVM as our linear SVM solver with default settings. In all cases, we ran our experiments on the original full data (referred to as “full” in the results), as well as on the projected data. For large-scale datasets, we use LIBLINEAR which is a faster SVM solver than LIBSVM, while for medium-scale datasets we use LIBSVM. We partitioned the data randomly for ten-fold cross-validation in order to estimate out-of-sample error. We repeated this partitioning ten times to get ten ten-fold cross-validation experiments. In the case where the dataset is already available in the form of a training and test-set, we do not perform ten-fold cross validation and use the given training and test set instead. In order to estimate the effect of the randomness in the construction of the random projection matrices, we repeated our cross-validation experiments ten times using ten different random projection matrices for all datasets. For classification experiments, we report in-sample error ($\epsilon_{in}$), out-of-sample error ($\epsilon_{out}$), the time to compute random projections ($t_{rp}$), the total time needed to both compute random projections and run SVMs on the lower-dimensional problem ($t_{run}$), and the margin ($\gamma$). For regression experiments, we report the margin, the combined running-time of random projections and SVM, mean-squared error $(mse)$ and the squared correlation-coefficient $(\beta)$ of $\epsilon_{in}$. All results are averaged over the ten cross-validation experiments and the ten choices of random projection matrices. For each of the aforementioned quantities, we report both its mean value $\mu$ and its standard deviation $\sigma$.

We describe experimental evaluations on three real-world datasets, namely a collection of document-term matrices (the TechTC-300 dataset ), a subset of the Reuters Corpus dataset (RCV1 Dataset ) and a population genetics dataset (the joint Human Genome Diversity Panel or HGDP and the HapMap Phase 3 data ) and also on three synthetic datasets. The synthetic datasets, a subset of the RCV1 dataset and the TechTC-300 dataset correspond to binary classification tasks while the joint HapMap-HGDP dataset and a subset of the RCV1 dataset correspond to multi-class classification tasks; our algorithms perform well in multi-class classification as well. For the multi-class experiments of Section 4.1.3, we do not report a margin. We use LIBLINEAR as our SVM solver for Hapmap-HGDP In \citeNPBMD13, the experiments on Hapmap-HGDP dataset were done using LIBSVM’s one-against-one multi-class classification method. LIBLINEAR does not have the one-against-one method implemented in the package. So we use the Crammer and Singer method . and the RCV1 datasets, while for the remaining datasets we use LIBSVM as our solver. For multi-class experiments, we use the method of Crammer and Singer implemented in LIBLINEAR.

1.2 The TechTC-300 dataset

We set the parameter $C$ to 500 in LIBSVM for all 295 document-term matrices and set $r$ to $128$, $256$, and $512$. We use a lower value of C than for the other data sets for computational reasons: larger $C$ is less efficient. We note that our classification accuracy is slightly worse (on the full data) than the accuracy presented in Section 4.4 of \citeNDavid04, because we did not fine-tune the SVM parameters as they did, since that is not the focus of this study. For every dataset and every value of $r$ we tried, the in-sample error on the projected data matched the in-sample error on the full data. We thus focus on $\epsilon_{out}$, the margin $\gamma$, the time needed to compute random projections $t_{rp}$, and the total running time $t_{run}$. We report our results averaged over 295 data matrices. Table 4.1.2 shows the behavior of these parameters for different choices of $r$. As expected, $\epsilon_{out}$ and the margin $\gamma$ improve as $r$ increases, and they are nearly identical for all four random projection methods. The time needed to compute random projections is smallest for CW, followed by RG, RS and FHT. As a matter of fact, $t_{rp}$ for CW is ten to 20 times faster than RG, RS and FHT for different values of $r$. This is predicted by the theory in \citeNClark12, since CW is optimized to take advantage of input sparsity. However, this advantage is lost when SVMs are applied on the dimensionally-reduced data. Indeed, the combined running time $t_{run}$ is fastest for RG, followed by FHT, RS and CW. In all cases, the total running time is smaller than the SVM running time on full dataset. For example, in the case of RG or FHT, setting $r=512$ achieves a running time $t_{run}$ which is about twice as fast as running SVMs on the full dataset; $\epsilon_{out}$ increases by less than $4\%$.

1.3 The HapMap-HGDP dataset

Predicting ancestry of individuals using a set of genetic markers is a well-studied classification problem. We use a population genetics dataset from the Human Genome Diversity Panel (HGDP) and the HapMap Phase 3 dataset (see \citeNPasch10 for details), in order to classify individuals into broad geographic regions, as well as into (finer-scale) populations. We study a total of 2,250 individuals from approximately 50 populations and five broad geographic regions (Asia, Africa, Europe, the Americas, and Oceania). The features in this dataset correspond to $492,516$ Single Nucleotide Polymorphisms (SNPs), which are well-known biallelic loci of genetic variation across the human genome. Each entry in the resulting $2,250\times 492,516$ matrix is set to $+1$ (homozygotic in one allele), $-1$ (homozygotic in the other allele), or $0$ (heterozygotic), depending on the genotype of the respective SNP for a particular sample. Missing entries were filled in with $-1$, $+1$, or $0$, with probability 1/3. Each sample has a known population and region of origin, which constitute its label.

1.4 The RCV1 dataset

The RCV1 dataset The RCV1 dataset is available publicly at http://www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets and contains a training-set and a test-set of predesignated size. is a benchmark dataset on text categorization. We use the RCV1 dataset for both binary and multi-class classification tasks. The RCV1 binary classification dataset had one training set containing 20,242 data-points and 47,236 features. We generate ten different test-sets each containing 20,000 points and 47,236 features from the available test-set for the binary classification task. The RCV1 binary classification dataset contains CCAT and ECAT as the positive classes and GCAT and MCAT as the negative classes. Instances in both positive and negative classes are absent. The RCV1 multi-class dataset had one training set 15,564 training points with 47,236 features and ten different test-sets each containing 16,000 data points and 47,236 features were generated from the available test-set. There are 53 classes in the RCV1 multi-class dataset. We set $r$ to $2048$, $4096$ and $8192$. We use LIBLINEAR as our SVM solver. We use the L2-regularized L2-loss support vector classification in the primal mode with default settings for binary classification and the method of Crammer and Singer for multi-class classification. We set $C=10$ for both multi-class classification and binary classification. The RCV1 dataset is very sparse with 0.16% non-zero entries in the binary-class dataset and 0.14% non-zero entries in the multi-class dataset.

Tables 4.1.4 and 4.1.4 show the results for RCV1 binary and multi class datasets.$t_{svm}$ denotes the SVM-training time on the projected data. For both binary and multi-class tasks, we observe that $\epsilon_{out}$ is close to that of full dataset and $\epsilon_{out}$ decreases with increase in number of projections. The SVM training time is smaller than that of full dataset for CW method only. For the other methods like FHT, RS and RG, the number of non-zeros in the projected data increases which increases the SVM training time. This is evident from Figure 4 which shows the ratio of number of non-zeros of projected data and full data. For all methods except CW, the number of non-zeros increases with increase in value of $r$. This follows from the theory predicted in \citeNClark12, since CW method takes advantage of input sparsity. The combined running time is smaller than that of full-dataset for CW method. The margin of the projected data is close to that of full data for RCV1 binary class dataset.

2 PCA vs Random Projections

Our goal is to evaluate if the data matrix represented by a small number of principal components can give the same or better performance than random projections when combined with SVMs, in terms of both running time and out-of-sample error. Note that the number of random projections is always greater than the rank of the matrix. For PCA we retain a number of principal components that is less than or equal to the rank of the matrix in order to compare its performance to random projections.

We used the TechTC300 dataset for experimental evaluation and used MATLAB’s SVD solver in “econ” mode to compute PCA. We kept $k$ equal to 32, 64, and $\rho$ (where $\rho$ is the rank of the matrix) principal components. The results corresponding to a number of principal components equal to the rank of the data matrices are referred to as “full-rank”, while “full” refers to the results on the full-dimensional dataset. We ran PCA experiments on 294 datasets with $k=64$, since one of them had rank less than 64. For $k=32$, we used the entire set of 295 TechTC300 matrices. $t_{pca}$ denotes the time to compute PCA on the dataset and we set $C=500$ and $C=1$ in our experiments. The out-of-sample error for PCA is equal to or sometimes slightly better compared to the error on the full-dimensional datasets. Even though a smaller number of principal components achieve better out-of-sample error when compared to random projections, the combined running time of SVMs and PCA is typically higher than that of random projections. The combined running time of SVMs and PCA is sensitive to the value of C, while the running time for random projections and SVM do not vary greatly, like PCA, by change of $C$. We repeated all experiments on TechTC-300 using $C=1$ and noticed the same pattern in the results as we did for $C=500$. RG and FHT are faster than the remaining two methods. Random projections are therefore a faster and more stable method than PCA. However, PCA appears to perform better than random projections when the number of components is equal to the rank of the matrix. Table 4.2 shows the results of PCA experiments; note that the standard deviation of $t_{run}$ for $C=500$ is quite high because of the varied running times of SVMs on the various TechTC300 matrices.

For a comparison of PCA to random projections, we consider the case of $r=512$ and the random gaussian matrix and randomized Hadamard Transform (see Table 4.1.2 for $C=500$), which has the best combined running time for random projections and SVMs. The combined running time of SVMs and “full-rank” PCA is smaller than that of RG (FHT) and SVMs by 0.19 (0.16) seconds, while the out-of-sample error of the former is only $4\%$ better. However, the time needed to compute PCA is 1.73 seconds, while random projections take negligible time to be computed; applying SVMs on the dimensionally-reduced matrix is the bottleneck of the computation. If PCA retains only 32 or 64 principal components, the running time of our method is smaller by factors of 30 and 5 respectively.

For $C=1$ and $r=512$, SVMs and “full-rank” PCA is smaller than that of RG (FHT) and SVMs by 0.43 (0.15) seconds, while the out-of-sample error of the former is again $4\%$ better. For $C=1$, if PCA retains only 32 or 64 principal components, the running time of our method is smaller by a few seconds.

These clearly show the advantage of using random projections over PCA, especially when a small number of principal components is desired. The PCA feature matrix is sensitive to the value of $C$. For a higher value of $C$, SVM takes a longer time to train the inseparable data of the PCA feature matrix.

3 Experiments on SVM regression

We describe experimental evaluations on real world datasets, namely Yalefaces dataset and a gene expression dataset (NCI60 ). We convert the multi-label classification tasks into a regression problem. We use LIBSVM with default settings and use $C=1$ in all our experiments. The general observations from our experiments are as follows: (i) the combined runtime of random projections and SVM is smaller than the runtime of SVM on full dataset, (ii) the margin increases with an increase in the number of projections.

The Yalefaces dataset consists of 165 grayscale images of 15 individuals. There were eleven images per subject, one per different facial expression (happy, sad, etc) or configuration (center-light, left-light, etc). The dataset has 165 datapoints and 4,096 features with 15 classes. The classes were used as the labels for regression. We set the value of $r$ to 256, 512, and 1024. $t_{run}$ for SVM and random projections is approximately 9, 7 and 4 times smaller than that of full-dataset. The margin increases as the number of random projections increases. The mean-squared in-sample error decreases with an increase in the number of random projections.

3.2 NCI60 Dataset

The NCI60 dataset consists of 1375 gene expression profiles of 60 human cancer cell lines. The dataset contains 1375 features and 60 datapoints with ten classes. The features contain the log-ratio of the expression levels. The classes were used as labels for regression. We set the value of $r$ to 128, 256, and 512. The running time of the four methods are nearly the same. The squared correlation-coefficient is very close to one and is not influenced by the number of projections, $r$. The mean squared $\epsilon_{in}$ remains the same for all values of $r$.

Conclusions and open problems

We present theoretical and empirical results indicating that random projections are a useful dimensionality reduction technique for SVM classification and regression problems that handle sparse or dense data in high-dimensional feature spaces. Our theory predicts that the dimensionality of the projected space (denoted by $r$) has to grow essentially linearly (up to logarithmic factors) in $\rho$ (the rank of the data matrix) in order to achieve relative error approximations to the margin and the radius of the minimum ball enclosing the data. Such relative-error approximations imply excellent generalization performance. However, our experiments show that considerably smaller values for $r$ results in classification that is essentially as accurate as running SVMs on all available features, despite the fact that the matrices have full numerical rank. This seems to imply that our theoretical results can be improved. We implemented and tested random projection methods that work well on dense matrices (the RS and FHT methods of Section 2), as well as a very recent random projection method that works well with sparse matrices (the CW method of Section 2). We also experimented with different SVM solvers for lage and medium-scale datasets. As expected, FHT, RG and RS work well on dense data while CW is an excellent choice for sparse data, as indicated by the SVM classification experiments. For large-scale sparse data, CW is the method of choice as the other methods outweigh the benefits of performing random projections. For SVM regression experiments, the combined running times using the four methods are the same for dense datasets. The mean squared error and the squared correlation-coefficient of $\epsilon_{in}$ of the projected data are non-zero as opposed to the SVM classification experiments. Finally, we compare random projections with a popular method of dimensionality reduction, namely PCA and see that the combined running time of random projection and SVM is faster than that of SVM and PCA, with a slightly worse out-of-sample error. All our experiments are on matrices of approximately low-rank, while the theory holds for matrices of exactly low-rank. It is not known if the theory extends to matrices of approximately low rank. This is an open problem and needs further investigation.

References