On one-shot kernels: explicit feature maps and properties

Kernels have been a common tool of machine learning
and computer vision applications for modeling nonlinearities
and/or the design of robust similarity measures
between objects. Arguably, the class of positive semidefinite
(psd) kernels, widely known as Mercer’s Kernels,
constitutes one of the most well-studied cases. For every
psd kernel there exists an associated feature map to an arbitrary
dimensional Hilbert space H, the so-called feature
space. The main reason behind psd kernels’ popularity is
the fact that classification/regression techniques (such as
Support Vector Machines (SVMs)) and component analysis
algorithms (such as Kernel Principal Component Analysis
(KPCA)) can be devised in H, without an explicit definition
of the feature map, only by using the kernel (the
so-called kernel trick). Recently, due to the development
of very efficient solutions for large scale linear SVMs and
for incremental linear component analysis, the research towards
finding feature map approximations for classes of
kernels has attracted significant interest. In this paper, we
attempt the derivation of explicit feature maps of a recently
proposed class of kernels, the so-called one-shot similarity
kernels. We show that for this class of kernels either there
exists an explicit representation in feature space or the kernel
can be expressed in such a form that allows for exact incremental
learning. We theoretically explore the properties
of these kernels and show how these kernels can be used for
the development of robust visual tracking, recognition and
deformable fitting algorithms.

Access to full text restricted pending copyright check.