A dual coordinate descent algorithm for SVMs combined with rational kernels

Cyril Allauzen, Corinna Cortes, Mehryar Mohri

Research output: Contribution to journalArticlepeer-review


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)
Pages (from-to)1761-1779
Number of pages19
JournalInternational Journal of Foundations of Computer Science
Issue number8
StatePublished - Dec 2011


  • Machine learning
  • coordinate descent
  • optimization
  • rational kernels
  • support vector machines
  • weighted automata

ASJC Scopus subject areas

  • Computer Science (miscellaneous)


Dive into the research topics of 'A dual coordinate descent algorithm for SVMs combined with rational kernels'. Together they form a unique fingerprint.

Cite this