Large-scale training of SVMs with automata kernels

Cyril Allauzen, Corinna Cortes, Mehryar Mohri

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationImplementation and Application of Automata - 15th International Conference, CIAA 2010, Revised Selected Papers
Number of pages11
StatePublished - 2011
Event15th International Conference on Implementation and Application of Automata, CIAA 2010 - Winnipeg, MB, Canada
Duration: Aug 12 2010Aug 15 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6482 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other15th International Conference on Implementation and Application of Automata, CIAA 2010
CityWinnipeg, MB

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Large-scale training of SVMs with automata kernels'. Together they form a unique fingerprint.

Cite this