Some Alternatives to Parikh Matrices Using String Kernels

• Autorzy: Clark A. , Watkins C.
• Języki publikacji: EN

Abstrakty

EN

We describe methods of representing strings as real valued vectors or matrices; we show how to integrate two separate lines of enquiry: string kernels, developed in machine learning, and Parikh matrices [8], which have been studied intensively over the last few years as a powerful tool in the study of combinatorics over words. In the field of machine learning, there is widespread use of string kernels, which use analogous mappings into high dimensional feature spaces based on the occurrences of subwords or factors. In this paper we show how one can use string kernels to construct two alternatives to Parikh matrices, that overcome some of the limitations of the Parikh matrix construction. These are morphisms from the free monoid to rings of real-valued matrices under multiplication: one is based on the subsequence kernel and the other on the gap-weighted string kernel. For the latter kernel we demonstrate that for many values of the gap-weight hyper-parameter the resulting morphism is injective.

Słowa kluczowe

EN

string; parikh matrix

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 84, nr 3-4
• Strony: 291--303
• Opis fizyczny: bibliogr. 14 poz.

Twórcy

autor

Clark A.

autor

Watkins C.

• Department of Computer Science, Royal Holloway, University of London, Egham TW20 0EX, UK,

Bibliografia

• [1] Atanasiu, A.: On the Injectivity of the Parikh Matrix Mapping, Fundamenta Informaticae, 49(4), 2002, 289-299.
• [2] Atanasiu, A., Martin-Vide, C, Mateescu, A.: Codifiable Languages and the Parikh Matrix Mapping, Journal of Universal Computer Science, 7(8), 2001, 783-793.
• [3] Clark, A., Costa Florencio, C, Watkins, C: Languages as Hyperplanes: grammatical inference with string kernels, ECML, 17th European Conference on Machine Learning, Springer-Verlag, 2006.
• [4] Clark, A., Costa Florencio, C, Watkins, C, Serayet, M.: Planar Languages and Learnability, Proceedings of the International Conference on Grammatical Inference, Springer-Verlag, Tokyo, Japan, 2006.
• [5] Egecioglu, O., Ibarra, O.: A Matrix q-Analogue of the Parikh Map, Technical report, UCSB Technical Report, TR 2004-06, 2004.
• [6] Haussler, D.: Convolution Kernels on Discrete Structures, Technical Report UCSC-CRL-99-10, Department of Computer Science, University of California at Santa Cruz, 1999.
• [7] Kontorovich, L., Cortes, C, Mohri, M.: Learning Linearly Separable Languages., Algorithmic Learning Theory, 17th International Conference,, 2006.
• [8] Mateescu, A., Salomaa, A., Salomaa, K., Yu, S.: A sharpening of the Parikh mapping, Theoretical Informatics and Applications, 35(6), 2001, 551-564.
• [9] Mateescu, A., Salomaa, A., Yu, S.: Subword histories and Parikh matrices, /. Comput. Syst. Sci, 68, 2004, 1-21.
• [10] Parikh, R. J.: On context-free languages, Journal of the ACM, 13(4), 1966,570-581.
• [11] Salomaa, A.: On Languages Defined by Numerical Parameters, Technical Report 663, Turku Centre for Computer Science, 2005.
• [12] Serbanuta, T.: Extending Parikh matrices, Theoretical Computer Science, 310(1), 2004, 233-246.
• [13] Shawe-Taylor, J., Christianini, N.: Kernel Methods for Pattern Analysis, Cambridge University Press, 2004.
• [14] Watkins, C: Kernels from Matching Operations, Technical Report CSD-TR-98-07, CS Dept., Royal Hol-loway, University of London, 1999