nips nips2002 nips2002-167 nips2002-167-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Corinna Cortes, Patrick Haffner, Mehryar Mohri
Abstract: We introduce 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. We show that rational kernels can be computed efficiently using a general algorithm of composition of weighted transducers and a general single-source shortest-distance algorithm. We also describe several general families of positive definite symmetric rational kernels. These general kernels can be combined with Support Vector Machines to form efficient and powerful techniques for spoken-dialog classification: highly complex kernels become easy to design and implement and lead to substantial improvements in the classification accuracy. We also show that the string kernels considered in applications to computational biology are all specific instances of rational kernels.
[1] Christian Berg, Jens Peter Reus Christensen, and Paul Ressel. Harmonic Analysis on Semigroups. Springer-Verlag: Berlin-New York, 1984.
[2] Jean Berstel. Transductions and Context-Free Languages. Teubner Studienbucher: Stuttgart, 1979.
[3] Samuel Eilenberg. Automata, Languages and Machines, volume A-B. Academic Press, 1974.
[4] David Haussler. Convolution kernels on discrete structures. Technical Report UCSC-CRL-9910, University of California at Santa Cruz, 1999.
[5] Ralf Herbrich. Learning Kernel Classifiers. MIT Press, Cambridge, 2002.
[6] Thorsten Joachims. Text categorization with support vector machines: learning with many relevant features. In Proc. of ECML-98. Springer Verlag, 1998.
[7] Werner Kuich and Arto Salomaa. Semirings, Automata, Languages. Number 5 in EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Berlin, Germany, 1986.
[8] Eugene L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, 1976.
[9] Huma Lodhi, John Shawe-Taylor, Nello Cristianini, and Christopher J. C. H. Watkins. Text classification using string kernels. In NIPS, pages 563–569, 2000.
[10] Mehryar Mohri. Edit-Distance of Weighted Automata. In Jean-Marc Champarnaud and Denis Maurel, editor, Seventh International Conference, CIAA 2002, volume to appear of Lecture Notes in Computer Science, Tours, France, July 2002. Springer-Verlag, Berlin-NY.
[11] Mehryar Mohri. Semiring Frameworks and Algorithms for Shortest-Distance Problems. Journal of Automata, Languages and Combinatorics, 7(3):321–350, 2002.
[12] Mehryar Mohri, Fernando C. N. Pereira, and Michael Riley. Weighted automata in text and speech processing. In ECAI-96 Workshop, Budapest, Hungary. ECAI, 1996.
[13] Mehryar Mohri, Fernando C. N. Pereira, and Michael Riley. The Design Principles of a Weighted Finite-State Transducer Library. Theoretical Computer Science, 231:17–32, January 2000. http://www.research.att.com/sw/tools/fsm.
[14] Fernando C. N. Pereira and Michael D. Riley. Speech recognition by composition of weighted finite automata. In Emmanuel Roche and Yves Schabes, editors, Finite-State Language Processing, pages 431–453. MIT Press, Cambridge, Massachusetts, 1997.
[15] Arto Salomaa and Matti Soittola. Automata-Theoretic Aspects of Formal Power Series. Springer-Verlag: New York, 1978.
[16] Robert E. Schapire and Yoram Singer. Boostexter: A boosting-based system for text categorization. Machine Learning, 39(2/3):135–168, 2000.
[17] Bernhard Scholkopf and Alex Smola. Learning with Kernels. MIT Press: Cambridge, MA, 2002.
[18] Vladimir N. Vapnik. Statistical Learning Theory. John Wiley & Sons, New-York, 1998.
[19] Chris Watkins. Dynamic alignment kernels. Technical Report CSD-TR-98-11, Royal Holloway, University of London, 1999.