A Spectral Learning Algorithm for Finite State Transducers
Abstract
Finite-State Transducers (FSTs) are a popular tool for modeling paired input-output sequences, and have numerous applications in real-world problems. Most training algorithms for learning FSTs rely on gradient-based or EM optimizations which can be computationally expensive and suffer from local optima issues. Recently, Hsu et al. [13] proposed a spectral method for learning Hidden Markov Models (HMMs) which is based on an Observable Operator Model (OOM) view of HMMs. Following this line of work we present a spectral algorithm to learn FSTs with strong PAC-style guarantees. To the best of our knowledge, ours is the first result of this type for FST learning. At its core, the algorithm is simple, and scalable to large data sets. We present experiments that validate the effectiveness of the algorithm on synthetic and real data.
Cite
Text
Balle et al. "A Spectral Learning Algorithm for Finite State Transducers." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2011. doi:10.1007/978-3-642-23780-5_20Markdown
[Balle et al. "A Spectral Learning Algorithm for Finite State Transducers." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2011.](https://mlanthology.org/ecmlpkdd/2011/balle2011ecmlpkdd-spectral/) doi:10.1007/978-3-642-23780-5_20BibTeX
@inproceedings{balle2011ecmlpkdd-spectral,
title = {{A Spectral Learning Algorithm for Finite State Transducers}},
author = {Balle, Borja and Quattoni, Ariadna and Carreras, Xavier},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2011},
pages = {156-171},
doi = {10.1007/978-3-642-23780-5_20},
url = {https://mlanthology.org/ecmlpkdd/2011/balle2011ecmlpkdd-spectral/}
}