TY - JOUR
T1 - Generalization bounds for learning weighted automata
AU - Balle, Borja
AU - Mohri, Mehryar
N1 - Funding Information:
MM's work was partly funded by NSF CCF-1535987 and IIS-1618662 .
Publisher Copyright:
© 2017 Elsevier B.V.
PY - 2018/3/15
Y1 - 2018/3/15
N2 - This paper studies the problem of learning weighted automata from a finite sample of strings with real-valued labels. We consider several hypothesis classes of weighted automata defined in terms of three different measures: the norm of an automaton's weights, the norm of the function computed by an automaton, and the norm of the corresponding Hankel matrix. We present new data-dependent generalization guarantees for learning weighted automata expressed in terms of the Rademacher complexity of these classes. We further present upper bounds on these Rademacher complexities, which reveal key new data-dependent terms related to the complexity of learning weighted automata.
AB - This paper studies the problem of learning weighted automata from a finite sample of strings with real-valued labels. We consider several hypothesis classes of weighted automata defined in terms of three different measures: the norm of an automaton's weights, the norm of the function computed by an automaton, and the norm of the corresponding Hankel matrix. We present new data-dependent generalization guarantees for learning weighted automata expressed in terms of the Rademacher complexity of these classes. We further present upper bounds on these Rademacher complexities, which reveal key new data-dependent terms related to the complexity of learning weighted automata.
KW - Generalization bounds
KW - Learning theory
KW - Rademacher complexity
KW - Weighted automata
UR - http://www.scopus.com/inward/record.url?scp=85036514806&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85036514806&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2017.11.023
DO - 10.1016/j.tcs.2017.11.023
M3 - Article
AN - SCOPUS:85036514806
VL - 716
SP - 89
EP - 106
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -