nips nips2002 nips2002-85 nips2002-85-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Alex J. Smola, S.v.n. Vishwanathan
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 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.
[1] A. Amir, M. Farach, Z. Galil, R. Giancarlo, and K. Park. Dynamic dictionary matching. Journal of Computer and System Science, 49(2):208-222, October 1994.
[2] w. I. Chang and E. L. Lawler. Sublinear approximate sting matching and biological applications. Algorithmica, 12(4/5):327-344, 1994.
[3] M. Collins and N. Duffy. Convolution kernels for natural language. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems 14, Cambridge, MA, 2001. MIT Press.
[4] R. Durbin, S. Eddy, A. Krogh, and G. Mitchison. Biological Sequence Analysis: Probabilistic models ofproteins and nucleic acids. Cambridge University Press, 1998.
[5] R. Giegerich and S. Kurtz. From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction. Algorithmica, 19(3):331-353, 1997.
[6] M. Gribskov and N. L. Robinson. Use of receiver operating characteristic (ROC) analysis to evaluate sequence matching. Computers and Chemistry, 20(1):25-33, 1996.
[7] D. Haussler. Convolutional kernels on discrete structures. Technical Report UCSCCRL-99-1O, Computer Science Department, UC Santa Cruz, 1999.
[8] R. Herbrich. Learning Kernel Classifiers: Theory and Algorithms. MIT Press, 2002.
[9] T. S. Jaakkola, M. Diekhans, and D. Haussler. A discriminative framework for detecting remote protein homologies. Journal of Computational Biology, 7:95-114, 2000.
[10] T. Joachims. Making large-scale SVM learning practical. In B. SchOlkopf, C. J. C. Burges, and A. J. Smola, editors, Advances in Kernel Methods-Support Vector Learning, pages 169-184, Cambridge, MA, 1999. MIT Press.
[11] E. Leopold and J. Kindermann. Text categorization with support vector machines: How to represent text in input space? Machine Learning, 46(3):423-444, March 2002.
[12] C. Leslie, E. Eskin, and W. S. Noble. The spectrum kernel: A string kernel for SVM protein classification. In Proceedings of the Pacific Symposium on Biocomputing, pages 564-575, 2002.
[13] E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249-260, 1995.
[14] S. V. N. Vishwanathan. Kernel Methods: Fast Algorithms and Real Life Applications. PhD thesis, Indian Institute of Science, Bangalore, India, November 2002.
[15] C. Watkins. Dynamic alignment kernels. In A. J. Smola, P. L. Bartlett, B. Scholkopf, and D. Schuurmans, editors, Advances in Large Margin Classifiers, pages 39-50, Cambridge, MA, 2000. MIT Press.