Nystrom Method for Approximating the GMM Kernel

2016·arXiv

Abstract

1 Introduction

The “generalized min-max” (GMM) kernel was recently proposed in [5] as an effective measure of data similarity. Consider the original (D-dim) data vector . The first step is to expand the data vector to a vector of 2D dimensions:

For example, if 1 3], then the transformed data vector becomes ˜u = [2 0 0 1 3 0]. After the transformation, the GMM similarity between two vectors is defined as

It was shown in [5], through extensive experiments on a large collection of publicly available datasets, that using the GMM kernel can often produce excellent results in classification tasks. On the other hand, it is generally nontrivial to scale nonlinear kernels for large data [1]. In a sense, it is not practically meaningful to discuss nonlinear kernels without knowing how to compute them efficiently (e.g., via hashing). [5] focused on the generalized consistent weighted sampling (GCWS).

1.1 Generalized Consistent Weighted Sampling (GCWS) and 0-bit GCWS

Algorithm 1 summarizes the “(0-bit) generalized consistent weighted sampling” (GCWS). Given two data vectors u and v, we transform them into nonnegative vectors ˜as in (1). We then apply the “(0-bit) consistent weighted sampling” (0-bit CWS) [8, 3, 4] to generate random integers: . According to the result in [4], the following approximation

is accurate in practical settings and makes the implementation convenient.

For each data vector u, we obtain k random samples We store only the lowest , based on the idea of [7]. We need to view those k integers as locations (of the nonzeros) instead of numerical values. For example, when b = 2, we should view as a vector of length 2= 3, then we code it as [1 0 0 0]; if = 0, we code it as [0 0 0 1], etc. We concatenate all k such vectors into a binary vector of length 2, which contains exactly After we have generated such new data vectors for all data points, we feed them to a linear SVM or logistic regression solver. We can, of course, also use the new data for many other tasks including clustering, regression, and near neighbor search.

Note that for linear learning methods, the storage and computational cost is largely determined by the number of nonzeros in each data vector, i.e., the k in our case. It is thus crucial not to use a too large k. For the other parameter b, we recommend to use a fairly large value if possible.

1.2 The RBF Kernel and Random Fourier Features (RFF)

The natural competitor of the GMM kernel is the RBF (radial basis function) kernel, whose definition involves a crucial tuning parameter 0. In this study, for convenience (e.g., parameter tuning), we use the following version of the RBF kernel:

Based on Bochners Theorem [11], it is known [10] that, if we sample N(0, 1) i.i.d., and let = 1, then we have

This provides an elegant mechanism for linearizing the RBF kernel and the so-called RFF method has become popular in machine learning, computer vision, and beyond.

It turns out that, for nonnegative data, one can simplify (5) by removing the random variable w, due to the following fact:

which is monotonic when 0. This creates a new nonlinear kernel called “folded RBF” (fRBF).

A major issue with the RFF method is the high variance. Typically a large number of samples (i.e., large k) would be needed in order to reach a satisfactory accuracy, as validated in [5]. Usually, “GMM-GCWS” (i.e., the GCWS algorithm for approximating the GMM kernel) requires substantially fewer samples than “RBF-RFF” (i.e., the RFF method for approximating the RBF kernel).

In this paper, we will introduce the Nystrom method [9] for approximating the GMM kernel, which we call “GMM-NYS”. We will show that GMM-NYS is also a strong competitor of RBF-RFF.

2 The Nystrom Method for Kernel Approximation

The Nystrom method [9] is a sampling scheme for kernel approximation [12]. For example, [13] applied the Nystrom method for approximating the RBF kernel, which we call “RBF-NYS”. Analogously, we propose “GMM-NYS”, which is the use of the Nystrom method for approximating the GMM kernel. This paper will show that GMM-NYS is a strong competitor of RBF-RFF.

To help interested readers repeat our experiments, here we post the matlab script for generating k samples using the Nystrom method. This piece of code contains various small tricks to make the implementation fairly efficient without hurting its readability.

Firstly, we randomly sample k data points from the (training) data matrix. Then we generate a data kernel matrix and compute its eigenvalues and eigenvectors. We then produce a new representation of given data matrix based on the eigenvalues and eigenvectors of the sampled kernel matrix. The new representation will be of exactly k dimensions (i.e., k nonzeros per data point).

In this paper, we will show that GMM-NYS is a strong competitor of RBF-RFF. This is actually not surprising. Random projection based algorithms always have (very) high variances and often do not perform as well as sampling based algorithms [6].

3 Experiments

We provide an extensive experimental study on a collection of fairly large classification datasets which are publicly available. We report the classification results for four methods: 1) GMM-GCWS, 2) GMM-NYS, 3) RBF-NYS, 4) RBF-RFF. Even though we focus on reporting classification results, we should mention that our methods generate new data presentations and can be used for (e.g.,) classification, regression, clustering. Note that, due to the discrete nature of the hashed values, GMM-GCWS can also be directly used for building hash tables and efficient near neighbor search.

3.1 Datasets

Table 1 summarizes the datasets for our experimental study. Because the Nystrom method is a sampling algorithm, we know that it will recover the original kernel result if the number of samples (k) approaches the number of training examples. Thus, it makes sense to compare the algorithms on larger datasets. Nevertheless, we still provide the experimental reuslt on SVMGuide3, a tiny dataset with merely 1, 243 training data points, merely for a sanity check.

Table 1: Public datasets and kernel SVM results. The datasets were downloaded from the UCI repository or the LIBSVM website. For the first 3 datasets (which are small enough), we report the test classification accuracies for the linear kernel, the RBF kernel (with the best in parentheses), and the GMM kernel, at the best SVM -regularization C values. For GMM and RBF, We use LIBSVM pre-computed kernel functionality. For the other datasets, we only report the linear SVM results and the best values obtained from a sub-sample of each dataset.

When using modern linear algorithms (especially online learning), the storage and computational cost are mainly determined by the number of nonzero entries per data point. In our study, after hashing (sampling), the storage and computational cost are mainly dominated by k, the number of samples. We will report the experimental results for we believe that for most practical applications, 1024 would not be so desirable (and takes too much time/space to complete the experiments). Nevertheless, for RCV1, we also report the results for , for the comparison purpose (and for our curiosity). We always use the LIBLINEAR package [2] for training linear SVMs on the original data as well as the hashed data.

3.2 Experimental Results

Figure 1 reports the test classification accuracies on SVMGuide3, for 6 different samples sizes (k) and 4 different algorithms: 1) GMM-GCWS, 2) GMM-NYS, 3) RBF-NYS, 4) RBF-RFF. Again, we should emphasize that the storage and computational cost are largely determined by the sample size k, which is also the number of nonzero entries per data vector in the transformed space.

Because the Nystrom method is based on sampling, we know that if k is large enough, the performance will approach that of the original kernel method. In particular, for this tiny dataset, since there are only 1,243 training data points, it is expected that when k = 1024, the classification results of GMM-NYS and RBF-NYS should be (close to) 100%, as validated in the upper left panel of Figure 1. It is thus more meaningful to examine the classification results for smaller k values.

Figure 1: SVMGuide3: Test classification accuracies for 6 different k values and 4 different hashing algorithms: 1) GMM-GCWS, 2) GMM-NYS, 3) RBF-NYS, 4) RBF-RFF. After the hashed data are generated, we use the LIBLINEAR package [2] for training linear SVMs for a wide range of -regularization C values (i.e., the x-axis). The classification results are averaged from 100 repetitions (at each k and C). We can see that, at the same sample size k (and when k is not too large), GMM-NYS produces substantially more accurate results than RBF-RFF.

From Figure 1, it is obvious that when k is not too large, GMM-NYS performs substantially better than RBF-RFF. Note that in order to show reliable (and smooth) curves, for this (tiny) dataset, we repeat each experiment (at each k and each C) 100 times and we report the averaged results. For other datasets, we report the averaged results from 10 repetitions.

Note that for SVMGuide3, the original classification accuracy using linear SVM is low (36.5%, see Table 1). These hashing methods produce substantially better results even when k = 32 only.

Figure 2 reports the test classification results for Letter, which also confirm that GMM-NYS produces substantially more accurate results than RBF-RFF. Again, while the original test clas-sification accuracy using linear SVM is low (61.7%, see Table 1), GMM-NYS with merely k = 32 samples already becomes more accurate.

Figure 2: Letter: Test classification accuracies for 6 different k values and 4 different algorithms.

Figure 3 reports the test classification accuracies for Covertype25k. Once again, the results confirm that GMM-NYS produces substantially more accurate results than RBF-RFF. GMM-NYS becomes more accurate than linear SVM on the original data after

Figures 4, 5, 6, 7, 8 report the test classification accuracies for SensIT, Webspam, PAMAP105, PAMAP101, Covertype, respectively. As these datasets are fairly large, we could not report nonlinear kernel (GMM and RBF) SVM results, although we can still report linear SVM results; see Table 1. Again, these figures confirm that 1) GMM-NYS is substantially more accurate than RBFRFF; and 2) GMM-NYS becomes more accurate than linear SVM once k is large enough.

Finally, Figures 9, 10, and 11 report the test classification results on the RCV1 dataset. Because the performance of RBF-RFF is so much worse than other methods, we report in Figure 9 only the results for GMM-GCWS, GMM-NYS, and RBF-NYS, for better clarity. In addition, we report the results for in Figure 11, to provide a more comprehensive comparison study. All these results confirm that GMM-NYS is a strong competitor of RBF-RFF.

Figure 3: Covertype25k: Test classification accuracies for 6 k values and 4 different algorithms.

Figure 4: SensIT: Test classification accuracies for 6 k values and 4 different algorithms.

Figure 5: Webspam: Test classification accuracies for 6 k values and 4 different algorithms

Figure 6: PAMAP105: Test classification accuracies for 6 k values and 4 different algorithms.

Figure 7: PAMAP101: Test classification accuracies for 6 k values and 4 different algorithms.

Figure 8: Covertype: Test classification accuracies for 6 k values and 4 different algorithms.

Figure 9: RCV1: Test classification accuracies for 6 k values. For better clarify we did not display the results for RBF-RFF because they are much worse than the results of other methods. See Figure 10 for the results of RBF-RFF.

Figure 10: RCV1: Test classification accuracies for 6 k values and 4 different algorithms.

Figure 11: RCV1: Test classification accuracies for and 4 different algorithms.

4 Conclusion

The recently proposed GMM kernel has proven effective as a measure of data similarity, through extensive experiments in the prior work [5]. For large-scale machine learning, it is crucial to be able to linearize nonlinear kernels. The work [5] demonstrated that the GCWS hashing method for linearizing the GMM kernel (GMM-GCWS) typically produces substantially more accurate results than the well-known random Fourier feature (RFF) approach for linearizing the RBF kernel (RBF-RFF).

In this study, we apply the general and well-known Nystrom method for approximating the GMM kernel (GMM-NYS) and we show, through extensive experiments, that the results produced by GMM-NYS are substantially more accurate than the results obtained using RBF-RFF. This phenomenon is largely expected because random projection based algorithms often have much larger variances than sampling based methods [6].

References

[1] L. Bottou, O. Chapelle, D. DeCoste, and J. Weston, editors. Large-Scale Kernel Machines. The MIT Press, Cambridge, MA, 2007.

[2] R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin. Liblinear: A library for large linear classification. Journal of Machine Learning Research, 9:1871–1874, 2008.

[3] S. Ioffe. Improved consistent sampling, weighted minhash and L1 sketching. In ICDM, pages 246–255, Sydney, AU, 2010.

[4] P. Li. 0-bit consistent weighted sampling. In KDD, Sydney, Australia, 2015.

[5] P. Li. Generalized min-max kernel and generalized consistent weighted sampling. Technical report, arXiv:1605.05721, 2016.

[6] P. Li, K. W. Church, and T. J. Hastie. Conditional random sampling: A sketch-based sampling technique for sparse data. In NIPS, pages 873–880, Vancouver, BC, Canada, 2006.

[7] P. Li, A. Shrivastava, J. Moore, and A. C. K¨onig. Hashing algorithms for large-scale learning. In NIPS, Granada, Spain, 2011.

[8] M. Manasse, F. McSherry, and K. Talwar. Consistent weighted sampling. Technical Report MSR-TR-2010-73, Microsoft Research, 2010.

[9] E. J. Nystr¨om. ¨Uber die praktische aufl¨osung von integralgleichungen mit anwendungen auf randwertaufgaben. Acta Mathematica, 54(1):185–204, 1930.

[10] A. Rahimi and B. Recht. Random features for large-scale kernel machines. In NIPS, 2007.

[11] W. Rudin. Fourier Analysis on Groups. John Wiley & Sons, New York, NY, 1990.

[12] C. K. I. Williams and M. Seeger. Using the nystr¨om method to speed up kernel machines. In NIPS, pages 682–688. 2001.

[13] T. Yang, Y.-f. Li, M. Mahdavi, R. Jin, and Z.-H. Zhou. Nystr¨om method vs random fourier features: A theoretical and empirical comparison. In NIPS, pages 476–484. 2012.

Designed for Accessibility and to further Open Science