Abstract

The time taken by an algorithm to make predictions is of critical importance as machine learning transitions to becoming a service available on the cloud. Algorithms that are efficient at prediction can service more calls and utilize fewer cloud resources and thereby generate more revenue. They can also be used in real time applications where predictions need to be made in micro/milliseconds.

Non-linear SVMs have defined the state-of-the-art on multiple benchmark tasks. Unfortunately, they are slow at prediction with costs that are linear in the number of training points. This reduces the attractiveness of non-linear SVMs trained on large amounts of data in cloud scenarios.

In this talk, we develop LDKL —an efficient non-linear SVM classifier with prediction costs that grow logarithmically with the number of training points. We generalize Localized Multiple Kernel Learning so as to learn a deep primal feature embedding which is high dimensional and sparse. Primal based classification decouples prediction costs from the number of support vectors and our tree-structured features efficiently encode non-linearities while speeding up prediction exponentially over the state-of-the-art. We develop routines for optimizing over the space of tree-structured features and efficiently scale to problems with millions of training points. Experiments on benchmark data sets reveal that LDKL can reduce prediction costs by more than three orders of magnitude over RBF -SVMs in some cases. Furthermore, LDKL leads to better classification accuracies as compared to leading methods for speeding up non-linear SVM prediction.