Efficient Hyperkernel Learning using Second-Order Cone Programming

Ivor W. Tsang, James T. Kwok

Abstract: The kernel function plays a central role in kernel methods. Most existing methods can only adapt the kernel parameters or the kernel matrix based on empirical data. Recently, Ong introduced the method of hyperkernels which can be used to learn the kernel function directly in an inductive setting. However, the associated optimization problem is a semidefinite program (SDP), which is very computationally expensive even with the recent advances in interior point methods. In this paper, we show that this learning problem can be equivalently reformulated as a second-order cone program (SOCP), which can then be solved more efficiently than SDPs. Comparison is also made with the kernel matrix learning method proposed by Lanckriet et al. Experimental results on both classification and regression problems, withtoy and real-world data sets, show that our proposed SOCP formulation has significant speedup over the original SDP formulation. Moreover, it yields better generalization than Lanckriet et al's method, with a speed that is comparable or sometimes even faster than their quadratically constrained quadratic program (QCQP) formulation.

IEEE Transactions on Neural Networks, 17(1):48-58, Jan 2006.

Pdf: http://www.cs.ust.hk/~jamesk/papers/tnn06.pdf

Back to James Kwok's home page.