Kernels and Distances for Structured Data
Machine LearningPublished 31 August 2004Open access
Thomas Gärtner, John W. Lloyd, Peter Flach
Citations161
SJR quartileQ1
SJR score1.15
SNIP2.14
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
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, and the main theoretical result is the positive definiteness of any kernel thus defined.
Abstract
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%.
Keywords
Computer Science
The Nature of Statistical Learning Theory
39,279 Citations1995Vladimir Vapnik
Cambridge University Press eBooksAn Introduction to Support Vector Machines and Other Kernel-based Learning Methods
13,883 Citations2000Nello Cristianini, John Shawe‐Taylor
A training algorithm for optimal margin classifiers
11,594 Citations1992Bernhard E. Boser, Isabelle Guyon +1 more
A training algorithm that maximizes the margin between the training patterns and the decision boundary is presented, applicable to a wide variety of the classification functions, including Perceptrons, polynomials, and Radial Basis Functions.
The MIT Press eBooksLearning with Kernels
9,548 Citations2001Bernhard Schölkopf, Alexander J. Smola
Learning with Kernels provides an introduction to SVMs and related kernel methods that provide all of the concepts necessary to enable a reader equipped with some basic mathematical knowledge to enter the world of machine learning using theoretically well-founded yet easy-to-use kernel algorithms.
International Conference on Neural Information ProcessingAdvances in kernel methods: support vector learning
5,815 Citations1999Bernhard Schölkopf, Christopher J. C. Burges +1 more
Support vector machines for dynamic reconstruction of a chaotic system, Klaus-Robert Muller et al pairwise classification and support vector machines, Ulrich Kressel.
Transactions of the American Mathematical SocietyTheory of reproducing kernels
5,435 Citations1950N. Aronszajn
Journal of the American Statistical AssociationSpline Models for Observational Data.
5,025 Citations1991Hans‐Georg Müller, Grace Wahba
IEEE Transactions on Neural NetworksAn introduction to kernel-based learning algorithms
3,490 Citations2001K. Müller, S. Mika +3 more
This paper provides an introduction to support vector machines, kernel Fisher discriminant analysis, and kernel principal component analysis, as examples for successful kernel-based learning methods.
Artificial IntelligenceSolving the multiple instance problem with axis-parallel rectangles
2,886 Citations1997Thomas G. Dietterich, Richard H. Lathrop +1 more
Three kinds of algorithms that learn axis-parallel rectangles to solve the multiple instance problem are described and compared, giving 89% correct predictions on a musk odor prediction task.
Journal of Symbolic LogicA formulation of the simple theory of types
1,893 Citations1940Alonzo Church
A formulation of the simple theory oftypes which incorporates certain features of the calculus of λ-conversion into the theory of types, and has certain advantages from the point of view of type theory.
Lecture notes in computer scienceA Generalized Representer Theorem
1,587 Citations2001Bernhard Schölkopf, Ralf Herbrich +1 more
The result shows that a wide range of problems have optimal solutions that live in the finite dimensional span of the training examples mapped into feature space, thus enabling us to carry out kernel algorithms independent of the (potentially infinite) dimensionality of the feature space.
Machine LearningLearning Logical Definitions from Relations
1,425 Citations1990J. R. Quinlan
FOIL is a system that learns Horn clauses from data expressed as relations, but extends them to a first-order formalism, which has been applied successfully to several tasks taken from the machine learning literature.
Support Vector Machines for Multiple-Instance Learning
1,384 Citations2002Stuart Andrews, Ioannis Tsochantaridis +1 more
The proposed extensions of the Support Vector Machine learning approach lead to mixed integer quadratic programs that can be solved heuristic ally and a generalization of SVMs makes a state-of-the-art classification technique, including non-linear classification via kernels, available to an area that up to now has been largely dominated by special purpose methods.
Journal of Machine Learning ResearchSupport vector clustering
1,356 Citations2002Asa Ben‐Hur, D. Horn +2 more
A novel clustering method using the approach of support vector machines, where data points are mapped by means of a Gaussian kernel to a high dimensional feature space, where the minimal enclosing sphere is searched for.
Advances in Computational MathematicsRegularization Networks and Support Vector Machines
1,223 Citations2000Theodoros Evgeniou, Massimiliano Pontil +1 more
Both formulations of regularization and Support Vector Machines are reviewed in the context of Vapnik's theory of statistical learning which provides a general foundation for the learning problem, combining functional analysis and statistics.
Machine LearningRobust Classification for Imprecise Environments
1,206 Citations2001Foster Provost, Tom Fawcett
It is shown that it is possible to build a hybrid classifier that will perform at least as well as the best available classifier for any target conditions, and in some cases, the performance of the hybrid actually can surpass that of the best known classifier.
A Framework for Multiple-Instance Learning
1,183 Citations1997Oded Maron, Tomás Lozano‐Pérez
A new general framework, called Diverse Density, is described, which is applied to learn a simple description of a person from a series of images containing that person, to a stock selection problem, and to the drug activity prediction problem.
Convolution kernels on discrete structures
1,089 Citations1999David Haussler
A new method of constructing kernels on sets whose elements are discrete structures like strings, trees and graphs is introduced, which can be applied iteratively to build a kernel on a innnite set from kernels involving generators of the set.
Lecture notes in computer scienceOn Graph Kernels: Hardness Results and Efficient Alternatives
868 Citations2003Thomas Gärtner, Peter Flach +1 more
As most ‘real-world’ data is structured, research in kernel methods has begun investigating kernels for various kinds of structured data, but only very specific graphs such as trees and strings have been considered.
The MIT Press eBooksConvolution Kernels for Natural Language
812 Citations2002Michael J. Collins, Nigel Duffy
It is shown how a kernel over trees can be applied to parsing using the voted perceptron algorithm, and experimental results on the ATIS corpus of parse trees are given.
EM-DD: An Improved Multiple-Instance Learning Technique
617 Citations2001Qi Zhang, Sally A. Goldman
A new multiple-instance (MI) learning technique that combines EM with the diverse density (DD) algorithm, which provides a new framework for MI learning, in which the MI problem is converted to a single-instance setting by using EM to estimate the instance responsible for the label of the bag.
Machine LearningLearning logical definitions from relations
613 Citations1990J. R. Quinlan
foil is a system that learns Horn clauses from data expressed as relations, based on ideas that have proved effective in attribute-value learning systems, but extends them to a first-order formalism.
Bristol Research (University of Bristol)Text Classification using String Kernels
514 Citations2000Huma Lodhi, John Shawe‐Taylor +2 more
A novel kernel is introduced for comparing two text documents consisting of an inner product in the feature space consisting of all subsequences of length k, which can be efficiently evaluated by a dynamic programming technique.
Relational Data Mining
505 Citations2006Sašo Džeroski
Transactions of the American Mathematical SocietyTheory of Reproducing Kernels
483 Citations1950N. Aronszajn
Multi-Instance Kernels
468 Citations2002Thomas Gärtner, Peter Flach +2 more
A kernel on multi-instance data that can be shown to separate positive and negative sets under natural assumptions is shown and compares favorably with state of the art multi- instance learning algorithms in an empirical study.
ACM SIGKDD Explorations NewsletterA survey of kernels for structured data
450 Citations2003Thomas Gärtner
This survey describes several approaches of defining positive definite kernels on structured instances directly on the basis of areal vector space and thus in a single table.
BioinformaticsEngineering support vector machine kernels that recognize translation initiation sites
425 Citations2000Alexander Zien, Gunnar Rätsch +4 more
With the described techniques the recognition performance can be improved by 26% over leading existing approaches, and there is evidence that existing related methods could profit from advanced TIS recognition.
Data Mining - Practical Machine Learning Tools and Techniques with JAVA Implementations
396 Citations2000I.H. Witten, E. Frank
International Conference on Neural Information ProcessingKernel principal component analysis
392 Citations1999Bernhard Schölkopf, Alexander J. Smola +1 more
Relational instance-based learning
174 Citations1996Werner Emde, Dietrich Wettschereck
International Conference on Machine LearningMulti instance neural networks
157 Citations2000Jan Ramon, Luc De Raedt
Lecture notes in computer scienceKernels for Structured Data
142 Citations2003Thomas Gärtner, John W. Lloyd +1 more
Neural Information Processing SystemsIntegrated Segmentation and Recognition of Hand-Printed Numerals
128 Citations1990James D. Keeler, David E. Rumelhart +1 more
A neural network algorithm that simultaneously segments and recognizes in an integrated system that uses a supervised learning algorithm (backpropagation), but is able to take position-independent information as targets and self-organize the activities of the units in a competitive fashion to infer the positional information.
Lecture notes in computer scienceAttribute-value learning versus inductive logic programming: The missing links
118 Citations1998Luc De Raedt
It is much more tractable to stick to the relational representation than to apply the sketched transformation, which provides a sound theoretical justification for inductive logic programming.
Lecture notes in computer scienceInductive constraint logic
117 Citations1995Luc De Raedt, Wim Van Laer
A novel approach to learning first order logic formulae from positive and negative examples is presented, which corresponds to a conjuctive normal form where each conjunct forms a constraint on positive examples.
Cognitive technologiesLogic for Learning
85 Citations2003John W. Lloyd
The first € price and the £ and $ price are net prices, subject to local VAT, and the €(D) includes 7% for Germany, the€(A) includes 10% for Austria.
arXiv (Cornell University)Robust Classification for Imprecise Environments
83 Citations2000Foster Provost, Tom Fawcett
Acta InformaticaA polynomial time computable metric between point sets
80 Citations2001Jan Ramon, Maurice Bruynooghe
A new measure which is a metric while being computable in polynomial time is introduced and a variant which computes a normalised metric and a variants which can associate different weights with the points in the set are presented.
Machine LearningRelational Instance-Based Learning with Lists and Terms
76 Citations2001Tamás Horváth, Stefan Wrobel +1 more
An improved similarity measure is presented for the first-order instance-based learner ribl that employs the concept of edit distances to efficiently compute distances between lists and terms.
Applied Artificial IntelligenceDiterpene structure elucidation from 13cnmr spectra with inductive logic programming
36 Citations1998Sašo Džeroski, Steffen Schulze-Kremer +4 more
A novel application ofuctive Logic Programming (ILP) to the problem of diterpene structure elucidation from 13 CNMR spectra to discover correlations between peak patterns and chemical structure.
Lecture notes in computer scienceImproved Distances for Structured Data
5 Citations2003Dimitrios Mavroeidis, Peter Flach
The distances introduced are metrics that are defined on the lattice structure of first-order terms for knowledge representation that allow the definition of kernels directly from the distance, thus enabling support vector machines and other kernel methods to be applied to structured objects.