An Empirical Approach For Probing the Definiteness of Kernels
  Models like support vector machines or Gaussian process regression often
require positive semi-definite kernels. These kernels may be based on distance
functions. While definiteness is proven for common distances and kernels, a
proof for a new kernel may require too much time and effort for users who
simply aim at practical usage. Furthermore, designing definite distances or
kernels may be equally intricate. Finally, models can be enabled to use
indefinite kernels. This may deteriorate the accuracy or computational cost of
the model. Hence, an efficient method to determine definiteness is required. We
propose an empirical approach. We show that sampling as well as optimization
with an evolutionary algorithm may be employed to determine definiteness. We
provide a proof-of-concept with 16 different distance measures for
permutations. Our approach allows to disprove definiteness if a respective
counter-example is found. It can also provide an estimate of how likely it is
to obtain indefinite kernel matrices. This provides a simple, efficient tool to
decide whether additional effort should be spent on designing/selecting a more
suitable kernel or algorithm.
