Fast Kernels for String and Tree Matching
Abstract
In this paper we present a new algorithm suitable for matching discrete objects such as strings and trees in linear time, thus obviating dynarrtic programming with quadratic time complexity. Furthermore, prediction cost in many cases can be reduced to linear cost in the length of the se(cid:173) quence 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.
Cite
Text
Smola and Vishwanathan. "Fast Kernels for String and Tree Matching." Neural Information Processing Systems, 2002.Markdown
[Smola and Vishwanathan. "Fast Kernels for String and Tree Matching." Neural Information Processing Systems, 2002.](https://mlanthology.org/neurips/2002/smola2002neurips-fast/)BibTeX
@inproceedings{smola2002neurips-fast,
title = {{Fast Kernels for String and Tree Matching}},
author = {Smola, Alex J. and Vishwanathan, S.v.n.},
booktitle = {Neural Information Processing Systems},
year = {2002},
pages = {585-592},
url = {https://mlanthology.org/neurips/2002/smola2002neurips-fast/}
}