A Convex Parametrization of a New Class of Universal Kernel Functions
This work addresses a foundational limitation in kernel learning for machine learning practitioners by providing a universal kernel class that eliminates the need for manual kernel selection and parameter tuning.
The authors tackled the problem of designing a kernel class that simultaneously achieves tractability, accuracy, and scalability, which existing kernels like Gaussians and polynomials fail to do, by proposing the Tessellated Kernel (TK) class that meets all three criteria and outperforms other kernel learning algorithms and neural networks in SVM tests, with significant improvements when the training data to features ratio is high.
The accuracy and complexity of kernel learning algorithms is determined by the set of kernels over which it is able to optimize. An ideal set of kernels should: admit a linear parameterization (tractability); be dense in the set of all kernels (accuracy); and every member should be universal so that the hypothesis space is infinite-dimensional (scalability). Currently, there is no class of kernel that meets all three criteria - e.g. Gaussians are not tractable or accurate; polynomials are not scalable. We propose a new class that meet all three criteria - the Tessellated Kernel (TK) class. Specifically, the TK class: admits a linear parameterization using positive matrices; is dense in all kernels; and every element in the class is universal. This implies that the use of TK kernels for learning the kernel can obviate the need for selecting candidate kernels in algorithms such as SimpleMKL and parameters such as the bandwidth. Numerical testing on soft margin Support Vector Machine (SVM) problems show that algorithms using TK kernels outperform other kernel learning algorithms and neural networks. Furthermore, our results show that when the ratio of the number of training data to features is high, the improvement of TK over MKL increases significantly.