Abstract
In classification problems, machine learning algorithms often make use of the assumption that (dis)similar inputs lead to (dis)similar outputs. In this case, two questions naturally arise: what does it mean for two inputs to be similar and how can this be used in a learning algorithm? In support vector machines, similarity between input examples is implicitly expressed by a kernel function that calculates inner products in the feature space. For numerical input examples the concept of an inner product is easy to define, for discrete structures like sequences of symbolic data however these concepts are less obvious. This article describes an approach to SVM learning for symbolic data that can serve as an alternative to the bag-of-words approach under certain circumstances. This latter approach first transforms symbolic data to vectors of numerical data which are then used as arguments for one of the standard kernel functions. In contrast, we will propose kernels that operate on the symbolic data directly.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Schölkopf, B.: The kernel trick for distances. Technical report, Microsoft Research (2000)
Joachims, T.: Learning to Classify Text Using Support Vector Machines. Kluwer Academic Publishers, Dordrecht (2002)
Vanschoenwinkel, B., Manderick, B.: A weighted polynomial information gain kernel for resolving pp attachment ambiguities with support vector machines. In: The Proceedings of the Eighteenth International Joint Conferences on Artificial Intelligence (IJCAI 2003), pp.133–138 (2003)
Vapnik, V.: The Nature of Statistical Learning Theory. Springer, Heidelberg (1998)
Cristianini, N., Shawe-Taylor, J.: An Introduction to Support Vector Machines and other Kernel-based Learning Methods. Cambridge University Press, Cambridge (2000)
Haussler, D.: Convolution kernels on discrete structures (1999)
Hein, M., Bousquet, O.: Maximal margin classification for metric spaces. In: Proceedings of Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, Colt/Kernel 2003, Washington, DC, USA, pp. 72–86. Springer, Heidelberg (2003)
Rost, B., Sander, C.: Improved prediction of protein secondary structure by use of sequence profiles and neural networks. In: Proceedings of the National Academy of Science USA, vol. 90, pp. 7558–7562 (1993)
Chih-Chung, C., Chi-Jen, L.: LIBSVM: A Library for Support Vector Machines (2004)
McNamee, P., Mayfield, J.: Entity extraction without language-specific resources. In: Proceedings of CoNLL 2002, pp. 183–186. Taipei, Taiwan (2002)
Kudoh, T., Matsumoto, Y.: Use of support vector learning for chunk identification. In: Proceedings of CoNLL 2000 and LLL 2000, Lisbon, Portugal (2000)
Takeuchi, K., Collier, N.: Use of support vector machines in extended named entity. In: Proceedings of CoNLL 2002, pp. 119–125. Taipei, Taiwan (2002)
Hua, S., Sun, Z.: A novel method of protein secondary structure prediction with high segment overlap measure: Support vector machine approach. Journal of Molecular Biology 308 (2), 397–407 (2001)
Degroeve, S.: Design and Evaluation of a Linear Classification Strategy for Gene Structural Element Recognition. PhD thesis, Universiteit Gent, Faculty of Sciences, Gent, Belgium (2004)
Levenshtein, V.: Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics - Doklady 10, 10, 707–710 (1966)
Nerbonne, J., Heeringa, W., Kleiweg, P.: Comparison and classification of dialects. In: Preceedings of EACL 1999 (1999)
Daelemans, W., Zavrel, J., van der Sloot, K., van den Bosch, A.: Timbl: Tilburg memory-based learner, version 4.3. Technical report, Tilburg University and University of Antwerp (2002)
Vanschoenwinkel, B.: A discrete kernel approach to support vector machine learning in language independent named entity recognition. In: Proceedings of BENELEARN 2004 (Annual Machine Learning Conference of Belgium and The Netherlands), pp. 154–161 (2004)
Zavrel, J., Daelemans, W., Veenstra, J.: Resolving pp attachment ambiguities with memory-based learning. In: Proceedings CoNNL, Madrid, Computational Linguistics, Tilburg University, pp. 136–144 (1997)
Leslie, C., Eskin, E., Noble, W.S.: The spectrum kernel: A string kernel for svm protein classification. In: Proceedings of the Pacific Symposium on Biocomputing, pp. 564–575 (2002)
Kuang, R., Ie, E., Wang, K., Siddiqi, M., Freund, Y., Leslie, C.: Profile-based string kernels for remote homology detection and motif extraction. In: Computational Systems Biology Conference (2004)
Saunders, C., Tschach, H., Shawe-Taylor, J.: Syllables and other string kernel extensions. In: Proceedings of the 19th International Conference on Machine Learning, pp. 530–537. Morgan Kaufmann, San Francisco (2002)
Rost, B.: Rising accuracy of protein secondary structure prediction. Marcel Dekker, New York (2003)
Dayhoff, M., Schwartz, R.: Matrices for detecting distant relationships. Atlas of Protein Sequences, 353–358 (1979)
Henikoff, S., Henikoff, J.: Amino acid substitution matrices from protein blocks. Proceedings of the National Academy of Science USA 89(2), 10915–10919 (1992)
Cuff, J., Barton, G.: Evaluation and improvement of multiple sequence methods for protein secondary structure prediction. Proteins: Struct., Funct., Genet. 35, 508–519 (1999)
Riis, S.K., Krogh, A.: Improving prediction of protein secondary structure using structured neural networks and multiple sequence alignments. Journal Of Computational Biology 3, 163–183 (1996)
Noreen, E.W.: Computer-Intensive Methods for Testing Hypotheses. John Wiley & Sons, Chichester (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Vanschoenwinkel, B., Manderick, B. (2005). Appropriate Kernel Functions for Support Vector Machine Learning with Sequences of Symbolic Data. In: Winkler, J., Niranjan, M., Lawrence, N. (eds) Deterministic and Statistical Methods in Machine Learning. DSMML 2004. Lecture Notes in Computer Science(), vol 3635. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11559887_16
Download citation
DOI: https://doi.org/10.1007/11559887_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29073-5
Online ISBN: 978-3-540-31728-9
eBook Packages: Computer ScienceComputer Science (R0)