Fast Kernels for String and Tree Matching
The MIT Press eBooksPublished 16 July 2004
S. V. N. Vishwanathan, Alexander J. Smola
Citations293
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 new algorithm suitable for matching discrete objects such as strings and trees in linear time is presented, thus obviating dynamic programming with quadratic time complexity and improvement on the currently available algorithms makes string kernels a viable alternative for the practitioner.
Abstract
In this paper we present a new algorithm suitable for matching discrete objects such as strings and trees in linear time, thus obviating dynamic programming with quadratic time complexity. Furthermore, prediction cost in many cases can be reduced to linear cost in the length of the sequence to be classified, regardless of the number of support vectors. This improvement on the currently available algorithms makes string kernels a viable alternative for the practitioner.
Keywords
Computer Science
Mathematics and Computers in SimulationIntroduction to automata theory, languages and computation
10,827 Citations1981
Technical reportsMaking Large-Scale SVM Learning Practical
4,317 Citations2006Thorsten Joachims
This chapter presents algorithmic and computational results developed for SVM light V 2.0, which make large-scale SVM training more practical and give guidelines for the application of SVMs to large domains.
Biological sequence analysis probabilistic models of proteins and nucleic acids
3,654 Citations2010Richard Durbin
Communications of the ACMEfficient string matching
2,946 Citations1975Alfred V. Aho, Margaret J. Corasick
A simple, efficient algorithm to locate all occurrences of any of a finite number of keywords in a string of text that has been used to improve the speed of a library bibliographic search program by a factor of 5 to 10.
Linear pattern matching algorithms
1,810 Citations1973Peter Weiner
A linear time algorithm for obtaining a compacted version of a bi-tree associated with a given string is presented and indicated how to solve several pattern matching problems, including some from [4] in linear time.
Journal of the ACMA Space-Economical Suffix Tree Construction Algorithm
1,518 Citations1976Edward M. McCreight
A new algorithm is presented for constructing auxiliary digital search trees to aid in exact-match substring searching that has the same asymptotic running time bound as previously published algorithms, but is more economical in space.
AlgorithmicaOn-line construction of suffix trees
1,465 Citations1995Esko Ukkonen
An on-line algorithm is presented for constructing the suffix tree for a given string in time linear in the length of the string, developed as a linear-time version of a very simple algorithm for (quadratic size) suffixtries.
THE SPECTRUM KERNEL: A STRING KERNEL FOR SVM PROTEIN CLASSIFICATION
944 Citations2001Christina S. Leslie, Eleazar Eskin +1 more
A new sequence-similarity kernel, the spectrum kernel, is introduced for use with support vector machines (SVMs) in a discriminative approach to the protein classification problem and performs well in comparison with state-of-the-art methods for homology detection.
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.
Journal of Computational BiologyA Discriminative Framework for Detecting Remote Protein Homologies
494 Citations2000Tommi Jaakkola, Mark Diekhans +1 more
A new method for detecting remote protein homologies is introduced and shown to perform well in classifying protein domains by SCOP superfamily using a new kernel function derived from a generative statistical model for a protein family, in this case a hidden Markov model.
Computers & ChemistryUse of receiver operating characteristic (ROC) analysis to evaluate sequence matching
474 Citations1996Michael Gribskov, Nina L. Robinson
The ROC is used in this work to investigate the effects of scoring table and gap penalties on database searches, and it is concluded that the optimal conditions for alignments and database searches are not, and should not be expected to be, the same.
Hidden Markov support vector machines
469 Citations2003Yasemin Altün, Ioannis Tsochantaridis +1 more
This paper presents a novel discriminative learning technique for label sequences based on a combination of the two most successful learning algorithms, Support Vector Machines and Hidden Markov Models which it is called HM-SVMs and handles dependencies between neighboring labels using Viterbi decoding.
The MIT Press eBooksLearning Kernel Classifiers
456 Citations2001Ralf Herbrich
This book provides the first comprehensive overview of both the theory and algorithms of kernel classifiers, including the most recent developments, and a detailed introduction to learning theory, including VC and PAC-Bayesian theory, data-dependent structural risk minimization, and compression bounds.
Machine LearningText Categorization with Support Vector Machines. How to Represent Texts in Input Space?
403 Citations2002Edda Leopold, Jörg Kindermann
It is shown that in the case of text classification, term-frequency transformations have a larger impact on the performance of SVM than the kernel itself.
Mismatch String Kernels for SVM Protein Classification
266 Citations2002Eleazar Eskin, Jason Weston +2 more
A class of string kernels, called mismatch kernels, are introduced for use with support vector machines (SVMs) in a discriminative approach to the protein classification problem, and show that the mismatch kernel used with an SVM classifier performs as well as the Fisher kernel, the most successful method for remote homology detection.
The MIT Press eBooksDynamic Alignment Kernels
242 Citations2000Chris Watkins
This paper shows that the scores produced by certain dynamic align ment algorithms for sequences are in fact valid kernel functions, proved by expressing the alignment scores explicitly as dot products.
BioinformaticsRemote homology detection: a motif based approach
193 Citations2003Asa Ben‐Hur, Douglas L. Brutlag
A method for detecting remote homology that is based on the presence of discrete sequence motifs that performs significantly better than an SVM method that uses BLAST or Smith-Waterman similarity scores as features.
AlgorithmicaSublinear approximate string matching and biological applications
186 Citations1994Wonil Chang, Eugene L. Lawler
This work gives an algorithm that is sublinear time0((n/m)k logbm) when the text is random andk is bounded by the threshold m/(logbm + O(1)).
AlgorithmicaFrom Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction
159 Citations1997Robert Giegerich, Stefan Kurtz
The terminology of the most recent algorithm, Ukkonen's on-line construction, is used to explain its historic predecessors, revealing relationships much closer than one would expect, since the three algorithms are based on rather different intuitive ideas.
Journal of Computer and System SciencesDynamic dictionary matching
90 Citations1994Amihood Amir, Martı́n Farach-Colton +3 more
An algorithm is presented that performs any sequence of the following operations in the given time bounds that can insert a new pattern into the dictionary or delete a pattern from it.
Neural Information Processing SystemsRational Kernels
52 Citations2002Corinna Cortes, Patrick Haffner +1 more
A general family of kernels based on weighted transducers or rational relations, rational kernels, that can be used for analysis of variable-length sequences or more generally weighted automata, in applications such as computational biology or speech recognition are introduced.
Theoretical Computer SciencePredicting nearly as well as the best pruning of a planar decision graph
27 Citations2002Eiji Takimoto, Manfred K. Warmuth
This work designs efficient on-line algorithms that predict nearly as well as the best pruning of a planar decision graph and implicitly maintains one weight for each of the prunings.
Lecture notes in computer scienceFast Regular Expression Search
21 Citations1999Gonzalo Navarro, Mathieu Raffinot
A new algorithm to search regular expressions is presented, which is able to skip text characters, and is fast, the fastest one in many cases of interest.
IFAC Proceedings VolumesHilbert space embeddings in dynamical systems
10 Citations2003Alexander J. Smola, S. V. N. Vishwanathan
This paper recovers the diffusion kernels of Kondor and Lafferty, generalised versions of directed graph kernels of Gatner, novel kernels on matrices and new similarity measures on Markov Models.