Deriving kernels from probabilistic models on discrete objects
Several learning methods using kernel functions ([1]) have been developed and shown to be highly efficient for tasks such as classification, regression, density estimation or clustering. One important feature of these methods is there modularity: they can be applied to any kind of object (e.g., images, sound, microarray data, protein sequences...) as soon as a kernel function has been defined for these objects. Kernels for real-valued vectors, such as polynomial or radial basis function kernels, have been known for a long time and successfully used in many applications where objects are naturally represented as vectors, e.g., images or microarray data. More recently new kernels have been developed for discrete objects such as sequences or trees, which naturally arise in computational biology or in natural language processing ([2, 3, 4]). These kernels open new analysis opportunities in these data-rich fields and are promised a bright future if they are confirmed to outperform “classical” analysis methods. We have developed a general method to derive a kernel K(x, y) from a probabilistic distribution p(x) for discrete objects (x, y) ∈ X 2 such as fixed-length strings or trees. This kernel interpolates between two natural kernels (see [3]), the diagonal kernel :