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.
Original language | English (US) |
---|---|
Pages (from-to) | 1761-1779 |
Number of pages | 19 |
Journal | International Journal of Foundations of Computer Science |
Volume | 22 |
Issue number | 8 |
DOIs | |
State | Published - Dec 2011 |
Keywords
- Machine learning
- coordinate descent
- optimization
- rational kernels
- support vector machines
- weighted automata
ASJC Scopus subject areas
- Computer Science (miscellaneous)