Kernels and Distances for Structured DataThomas Gaertner, John W. Lloyd, Peter A. Flach, Kernels and Distances for Structured Data. Machine Learning, 57(3). ISSN 0885-6125, pp. 205–232. December 2004. PDF, 236 Kbytes.
This paper brings together two strands of machine learning of increasing importance: kernel methods and highly structured data. We propose a general method for constructing a kernel following the syntactic structure of the data, as defined by its type signature in a higher-order logic. Our main theoretical result is the positive definiteness of any kernel thus defined. We report encouraging experimental results on a range of real-world data sets. By converting our kernel to a distance pseudo-metric for 1-nearest neighbour, we were able to improve the best accuracy from the literature on the Diterpene data set by more than 10%.