Convolution kernels on discrete structures

作者：David Haussler · 年份：1999 · 被引用次数：1088 · 研究领域：Advanced Numerical Analysis Techniques、Image and Signal Denoising Methods

We introduce a new method of constructing kernels on sets whose elements are discrete structures like strings, trees and graphs. The method can be applied iteratively to build a kernel on a infinite set from kernels involving generators of the set. The family of kernels generated generalizes the family of radial basis kernels. It can also be used to define kernels in the form of joint Gibbs probability distributions. Kernels can be built from hidden Markov random fields, generalized regular expressions, pair-HMMs, or ANOVA decompositions. Uses of the method lead to open problems involving the theory of infinitely divisible positive definite functions. Fundamentals of this theory and the theory of reproducing kernel Hilbert spaces are reviewed and applied in establishing the validity of the method. 1 Introduction Many problems in statistics and pattern recognition demand that discrete structures likes strings, trees, and graphs be classified or clustered based on similarity. To do th...