Linear complexity hyperparameter tuning of the quadratic kernel for support vector classification

The SVM classifier often uses radial basis kernel because it has just one tunable hyperparameter, unlike polynomial kernel that has three. However, the polynomial kernel is separable and may speed up the SVM training and test, although with high degrees it is still slow because it requires many monomials. On the contrary, low degree (e.g. quadratic) polynomial kernels keep the number of monomials low even with high-dimensional inputs, being faster and extending the applicability of SVM to large scale datasets. We prove experimentally that quadratic polynomial kernel with just one hyperparameter achieves performance similar to radial basis kernel. We propose a method named increasing quadratic estimation, IQE, that calculates the hyperparameter value using only the training data, without SVM training. The proposed IQE achieves state-of-the-art performance and is very fast, because its complexity is linear on the training set size and dimensionality. The experimental work, performed on a collection of 120 classification datasets, proves that IQE: 1) outperforms and is faster than quadratic kernel without tuning; 2) is similar to radial basis and quadratic kernels tuned using grid search, being one or two orders of magnitude faster; and 3) outperforms genetic, Bayesian and particle swarm optimization, being between three and five orders of magnitude faster. Code is available from https://osf.io/nz96q Open Science Framework (OSF).

Palabras clave: Support Vector Machine, Classification, Quadratic kernel, Hyperparameter tuning