TY - GEN
T1 - On the rademacher complexity of weighted automata
AU - Balle, Borja
AU - Mohri, Mehryar
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - Weighted automata (WFAs) provide a general framework for the representation of functions mapping strings to real numbers. They include as special instances deterministic finite automata (DFAs), hidden Markov models (HMMs), and predictive states representations (PSRs). In recent years, there has been a renewed interest in weighted automata in machine learning due to the development of efficient and provably correct spectral algorithms for learning weighted automata. Despite the effectiveness reported for spectral techniques in real-world problems, almost all existing statistical guarantees for spectral learning of weighted automata rely on a strong realizability assumption. In this paper, we initiate a systematic study of the learning guarantees for broad classes of weighted automata in an agnostic setting. Our results include bounds on the Rademacher complexity of three general classes of weighted automata, each described in terms of different natural quantities. Interestingly, these bounds underline the key role of different data-dependent parameters in the convergence rates.
AB - Weighted automata (WFAs) provide a general framework for the representation of functions mapping strings to real numbers. They include as special instances deterministic finite automata (DFAs), hidden Markov models (HMMs), and predictive states representations (PSRs). In recent years, there has been a renewed interest in weighted automata in machine learning due to the development of efficient and provably correct spectral algorithms for learning weighted automata. Despite the effectiveness reported for spectral techniques in real-world problems, almost all existing statistical guarantees for spectral learning of weighted automata rely on a strong realizability assumption. In this paper, we initiate a systematic study of the learning guarantees for broad classes of weighted automata in an agnostic setting. Our results include bounds on the Rademacher complexity of three general classes of weighted automata, each described in terms of different natural quantities. Interestingly, these bounds underline the key role of different data-dependent parameters in the convergence rates.
UR - http://www.scopus.com/inward/record.url?scp=84945932358&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84945932358&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-24486-0_12
DO - 10.1007/978-3-319-24486-0_12
M3 - Conference contribution
AN - SCOPUS:84945932358
SN - 9783319244853
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 179
EP - 193
BT - Algorithmic Learning Theory - 26th International Conference, ALT 2015
A2 - Gentile, Claudio
A2 - Zilles, Sandra
A2 - Chaudhuri, Kamalika
PB - Springer Verlag
T2 - 26th International Conference on Algorithmic Learning Theory, ALT 2015
Y2 - 4 October 2015 through 6 October 2015
ER -