Special Issue Implementation and Application of Automata (CIAA 2010)No Access

A DUAL COORDINATE DESCENT ALGORITHM FOR SVMs COMBINED WITH RATIONAL KERNELS

CYRIL ALLAUZEN

Google Research, 76 Ninth Avenue, New York, NY 10011, USA

Search for more papers by this author

CORINNA CORTES

Google Research, 76 Ninth Avenue, New York, NY 10011, USA

Search for more papers by this author

, and

MEHRYAR MOHRI

Courant Institute of Mathematical Sciences, 251 Mercer Street, New York, NY 10012, USA

Google Research, 76 Ninth Avenue, New York, NY 10011, USA

Search for more papers by this author

https://doi.org/10.1142/S0129054111009021Cited by:1 (Source: Crossref)

Abstract

This paper presents a novel application of automata algorithms to machine learning. It introduces the first optimization solution for support vector machines used with sequence kernels that is purely based on weighted automata and transducer algorithms, without requiring any specific solver. The algorithms presented apply to a family of kernels covering all those commonly used in text and speech processing or computational biology. We show that these algorithms have significantly better computational complexity than previous ones and report the results of large-scale experiments demonstrating a dramatic reduction of the training time, typically by several orders of magnitude.

Keywords:

References

Cyril Allauzen, Mehryar Mohri and Ameet Talwalkar, Sequence kernels for predicting protein essentiality, ICML 2008 (ACM, 2008) pp. 9–16. Google Scholar
Francis R. Bach and Michael I. Jordan, Journal of Machine Learning Research 3, 1 (2002). Web of Science, Google Scholar
Christian Berg et al. , Harmonic Analysis on Semigroups ( Springer-Verlag , Berlin-New York , 1984 ) . Crossref, Google Scholar
Rafael C. Carrosco and Mikel L. Forcada, Computational Linguistics 28(2), 207 (2002). Crossref, Web of Science, Google Scholar
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines, 2001. Software available at , http://www.csie.ntu.edu.tw/cjlin/libsvm . Google Scholar
Michael Collins and Nigel Duffy , Convolution kernels for natural language , NIPS ( MIT Press , 2002 ) . Google Scholar
Corinna Cortes, Patrick Haffner and Mehryar Mohri, Journal of Machine Learning Research 5, 1035 (2004). Web of Science, Google Scholar
Corinna Cortes and Mehryar Mohri, Machine Learning 60(1-3), 117 (2005), DOI: 10.1007/s10994-005-0919-8. Crossref, Web of Science, Google Scholar
Corinna Cortes and Vladimir N. Vapnik, Machine Learning 20(3), 273 (1995). Web of Science, Google Scholar
Jan Daciuket al., Computational Linguistics 26(1), 3 (2000), DOI: 10.1162/089120100561601. Crossref, Web of Science, Google Scholar
Rong-En Fan, P.-H. Chen and C.-J. Lin, Journal of Machine Learning Research 6, 1889 (2005). Web of Science, Google Scholar
Shai Fine and Katya Scheinberg, Journal of Machine Learning Research 2, 243 (2002). Web of Science, Google Scholar
David Haussler. Convolution Kernels on Discrete Structures. Technical Report UCSC-CRL-99-10, University of California at Santa Cruz, 1999 . Google Scholar
Alan J. Hoffman, Journal of Research of the National Bureau of Standards 49, 263 (1952). Crossref, Web of Science, Google Scholar
Cho-Jui Hsiehet al., A dual coordinate descent method for large-scale linear SVM, ICML 2008 (ACM, 2008) pp. 408–415. Google Scholar
Thorsten Joachims , Advances in Kernel Methods: Support Vector Learning ( The MIT Press , 1998 ) . Google Scholar
Werner Kuich and Arto Salomaa , EATCS Monographs on Theoretical Computer Science ( Springer , New York , 1986 ) . Google Scholar
Sanjiv Kumar , Mehryar Mohri and Ameet Talwalkar , On sampling-based approximate spectral decomposition , ICML 2009 ( ACM , 2009 ) . Google Scholar
Christina Leslie and Rui Kuang, Journal of Machine Learning Research 5, 1435 (2004). Web of Science, Google Scholar
Christina S. Leslie, Eleazar Eskin and William Stafford Noble, The Spectrum Kernel: A String Kernel for SVM Protein Classification, Pacific Symposium on Biocomputing (2002) pp. 566–575. Google Scholar
Huma Lodhiet al., Journal of Machine Learning Research 2, 419 (2002). Web of Science, Google Scholar
Zhi-Quan Luo and Paul Tseng, Journal of Optimization Theory and Applications 72(1), 7 (1992), DOI: 10.1007/BF00939948. Crossref, Web of Science, Google Scholar
Mehryar Mohri, Handbook of Weighted Automata, eds. Manfred Droste, Werner Kuich and Heiko Vogler (Springer, 2009) pp. 213–254. Crossref, Google Scholar
Arto Salomaa and Matti Soittola , Automata-Theoretic Aspects of Formal Power Series ( Springer , 1978 ) . Crossref, Google Scholar
John Shawe-Taylor and Nello Cristianini , Kernel Methods for Pattern Analysis ( Cambridge Univ. Press , 2004 ) . Crossref, Google Scholar
Ivor W. Tsang, James T. Kwok and Pak-Ming Cheung, Journal of Machine Learning Research 6, 363 (2005). Web of Science, Google Scholar
Christopher K. I. Williams and Matthias Seeger, Using the Nyström method to speed up kernel machines, NIPS (2000) pp. 682–688. Google Scholar
A. Zienet al., Bioinformatics 16(9), 799 (2000), DOI: 10.1093/bioinformatics/16.9.799. Crossref, Web of Science, Google Scholar