Fast Prediction for Large-Scale Kernel Machines

Cho-Jui Hsieh, Si Si, Inderjit S. DhillonNeurIPS 2014 · OpenReview

Introduction

Kernel machines, such as Support Vector Machines (SVM) and Kernel Ridge Regression, are highly regarded in machine learning for their ability to capture complex, non-linear patterns in data. However, they come with a major "scalability tax": to make a prediction for a single new data point, the model often has to compare that point against thousands of "support vectors" from the training set.

As datasets grow into the millions, this prediction cost becomes a dealbreaker for real-time applications. While linear models are lightning-fast, they often lack the expressiveness required to handle complex data. To bridge this gap, researchers have introduced DC-Pred++, a framework that makes kernel machine predictions orders of magnitude faster without sacrificing accuracy. By combining a "pseudo landmark" approximation technique with a divide-and-conquer strategy, DC-Pred++ achieves up to a 10,000x speedup over standard kernel SVMs while outperforming existing state-of-the-art fast prediction methods.

Core Methodology

The authors propose three main innovations bundled into the DC-Pred++ algorithm:

1. Pseudo Landmark Points Standard Nyström approximation uses a small subset of training points (landmarks) to estimate the full kernel matrix. The authors found they could bypass the traditional trade-off between speed and accuracy by adding "pseudo" landmarks. These are points where the kernel value is estimated using computationally cheap mathematical tricks (like the triangle inequality or low-degree polynomials) rather than expensive exact calculations. This significantly reduces approximation error without adding meaningful computational overhead.

Relative approximation error vs. prediction cost showing Nys-dp outperforming standard Nys.

2. Weighted K-means for Landmark Selection Usually, landmarks are chosen randomly. The authors proved theoretically that prediction error is most sensitive to points with high model weights (the actual support vectors). They developed a weighted k-means approach to ensure landmarks are placed where they matter most for the final decision boundary.

3. Divide-and-Conquer Framework To handle massive datasets, the algorithm first partitions the data into smaller local clusters using k-means. It then builds specialized, fast-prediction models for each local neighborhood. When a new test point arrives, the system quickly identifies the relevant cluster and uses the local optimized model to provide a result.

Key Insights

  • Don't Approximate Everything: A key realization is that you don't need to approximate the entire kernel matrix perfectly. You only need to be accurate in the regions where the model's weights are large, which justifies the use of weighted k-means.
  • The Power of "Good Enough": The pseudo landmark idea demonstrates that a fast, slightly noisy approximation of a landmark is often better for the model than having no landmark at all.
  • Locality Matters: By breaking the problem into clusters, kernel approximation becomes much easier because the data within a local cluster is simpler and more "linear" than the global dataset.

Performance and Results

The researchers evaluated their approach on a wide variety of standard benchmarks, ranging from small datasets to massive ones like Kddcup (nearly 5 million points) and mnist2M (1.5 million points). The performance gains are dramatic:

  • Speed: On the Covertype dataset, DC-Pred++ achieved a 10,000x speedup over a full kernel SVM.
  • Efficiency vs. Competition: Compared to LDKL (the previous state-of-the-art), DC-Pred++ was twice as fast while being significantly more accurate (95.2% vs 89.5% on Covertype).
  • Training Time: Surprisingly, the method is also very fast to train—often 10x faster than competing fast-prediction methods because the divide-and-conquer approach is highly parallelizable.
  • Regression: In ridge regression tasks, DC-Pred++ consistently yielded lower Root Mean Squared Error (RMSE) than standard Nyström or Random Kitchen Sinks for the same computational budget.
Test RMSE vs. Prediction Time on the mnist2M dataset, demonstrating DC-Pred++'s superior efficiency.

Limitations and Future Work

While the results are impressive, the paper notes a few areas for further exploration. First, performance depends on choosing the right hyperparameters, such as the number of clusters and landmarks; while the authors provide guidance, these still require tuning. Second, some of the pseudo landmark mathematics (specifically the triangle inequality version) are designed for stationary kernels (like Gaussian/RBF). While they provide a polynomial version for general kernels, it may require more testing on exotic kernel types. Finally, the authors suggest this approach could serve as a foundational building block for other complex kernel frameworks, such as Memory Efficient Kernel Approximation (MEKA).

Summary updated

Abstract

Kernel machines such as kernel SVM and kernel ridge regression usually construct high quality models; however, their use in real-world applications remains limited due to the high prediction cost. In this paper, we present two novel insights for improving the prediction efficiency of kernel machines. First, we show that by adding “pseudo landmark points” to the classical Nystr¨om kernel approximation in an elegant way, we can significantly reduce the prediction error without much additional prediction cost. Second, we provide a new theoretical analysis on bounding the error of the solution computed by using Nystr¨om kernel approximation method, and show that the error is related to the weighted kmeans objective function where the weights are given by the model computed from the original kernel. This theoretical insight suggests a new landmark point selection technique for the situation where we have knowledge of the original model. Based on these two insights, we provide a divide-and-conquer framework for improving the prediction speed. First, we divide the whole problem into smaller local subproblems to reduce the problem size. In the second phase, we develop a kernel approximation based fast prediction approach within each subproblem. We apply our algorithm to real world large-scale classification and regression datasets, and show that the proposed algorithm is consistently and significantly better than other competitors. For example, on the Covertype classification problem, in terms of prediction time, our algorithm achieves more than 10000 times speedup over the full kernel SVM, and a two-fold speedup over the state-of-the-art LDKL approach, while obtaining much higher prediction accuracy than LDKL (95.2% vs. 89.53%).
BibTeX
@inproceedings{hsieh2014fast,
  author = {Cho-Jui Hsieh and Si Si and Inderjit S. Dhillon},
  title = {{Fast Prediction for Large-Scale Kernel Machines}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=rkZtpDW_ZH},
}
Figure