Fast probabilistic prediction for kernel SVM via enclosing balls

Nery Riquelme-Granada, Khuong An Nguyen, Zhiyuan Luo
Proceedings of the Ninth Symposium on Conformal and Probabilistic Prediction and Applications, PMLR 128:189-208, 2020.

Abstract

Support Vector Machine (SVM) is a powerful paradigm that has proven to be extremely useful for the task of classifying high-dimensional objects. It does not only perform well in learning linear classifiers, but also shows outstanding performance in capturing non-linearity through the use of kernels. In principle, SVM allows us to train “scoring” classifiers i.e. classifiers that output a prediction score. However, it can also be adapted to produce probability-type outputs through the use of the Venn-Abers framework. This allows us to obtain valuable information on the labels distribution for each test object. This procedure, however, is restricted to very small data given its inherent computational complexity. We circumvent this limitation by borrowing results from the field of computational geometry. Specifically, we make use of the concept of a coreset: a small summary of data that is constructed by discretising the input space into enclosing balls, so that each ball will be represented by only one object. Our results indicate that training Venn-Abers predictors using enclosing balls provides an average acceleration of 8 times compared to the regular Venn-Abers approach while largely retaining probability calibration. These promising results imply that we can still enjoy well-calibrated probabilistic outputs for kernel SVM even in the realm of large-scale datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v128-riquelme-granada20a, title = {Fast probabilistic prediction for kernel SVM via enclosing balls}, author = {Riquelme-Granada, Nery and Nguyen, Khuong An and Luo, Zhiyuan}, booktitle = {Proceedings of the Ninth Symposium on Conformal and Probabilistic Prediction and Applications}, pages = {189--208}, year = {2020}, editor = {Gammerman, Alexander and Vovk, Vladimir and Luo, Zhiyuan and Smirnov, Evgueni and Cherubin, Giovanni}, volume = {128}, series = {Proceedings of Machine Learning Research}, month = {09--11 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v128/riquelme-granada20a/riquelme-granada20a.pdf}, url = {https://proceedings.mlr.press/v128/riquelme-granada20a.html}, abstract = {Support Vector Machine (SVM) is a powerful paradigm that has proven to be extremely useful for the task of classifying high-dimensional objects. It does not only perform well in learning linear classifiers, but also shows outstanding performance in capturing non-linearity through the use of kernels. In principle, SVM allows us to train “scoring” classifiers i.e. classifiers that output a prediction score. However, it can also be adapted to produce probability-type outputs through the use of the Venn-Abers framework. This allows us to obtain valuable information on the labels distribution for each test object. This procedure, however, is restricted to very small data given its inherent computational complexity. We circumvent this limitation by borrowing results from the field of computational geometry. Specifically, we make use of the concept of a coreset: a small summary of data that is constructed by discretising the input space into enclosing balls, so that each ball will be represented by only one object. Our results indicate that training Venn-Abers predictors using enclosing balls provides an average acceleration of 8 times compared to the regular Venn-Abers approach while largely retaining probability calibration. These promising results imply that we can still enjoy well-calibrated probabilistic outputs for kernel SVM even in the realm of large-scale datasets.} }
Endnote
%0 Conference Paper %T Fast probabilistic prediction for kernel SVM via enclosing balls %A Nery Riquelme-Granada %A Khuong An Nguyen %A Zhiyuan Luo %B Proceedings of the Ninth Symposium on Conformal and Probabilistic Prediction and Applications %C Proceedings of Machine Learning Research %D 2020 %E Alexander Gammerman %E Vladimir Vovk %E Zhiyuan Luo %E Evgueni Smirnov %E Giovanni Cherubin %F pmlr-v128-riquelme-granada20a %I PMLR %P 189--208 %U https://proceedings.mlr.press/v128/riquelme-granada20a.html %V 128 %X Support Vector Machine (SVM) is a powerful paradigm that has proven to be extremely useful for the task of classifying high-dimensional objects. It does not only perform well in learning linear classifiers, but also shows outstanding performance in capturing non-linearity through the use of kernels. In principle, SVM allows us to train “scoring” classifiers i.e. classifiers that output a prediction score. However, it can also be adapted to produce probability-type outputs through the use of the Venn-Abers framework. This allows us to obtain valuable information on the labels distribution for each test object. This procedure, however, is restricted to very small data given its inherent computational complexity. We circumvent this limitation by borrowing results from the field of computational geometry. Specifically, we make use of the concept of a coreset: a small summary of data that is constructed by discretising the input space into enclosing balls, so that each ball will be represented by only one object. Our results indicate that training Venn-Abers predictors using enclosing balls provides an average acceleration of 8 times compared to the regular Venn-Abers approach while largely retaining probability calibration. These promising results imply that we can still enjoy well-calibrated probabilistic outputs for kernel SVM even in the realm of large-scale datasets.
APA
Riquelme-Granada, N., Nguyen, K.A. & Luo, Z.. (2020). Fast probabilistic prediction for kernel SVM via enclosing balls. Proceedings of the Ninth Symposium on Conformal and Probabilistic Prediction and Applications, in Proceedings of Machine Learning Research 128:189-208 Available from https://proceedings.mlr.press/v128/riquelme-granada20a.html.

Related Material