Generalization bounds for learning weighted automata

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Generalization bounds for learning weighted automata. / Balle, Borja; Mohri, Mehryar.
In: Theoretical Computer Science, Vol. 716, 15.03.2018, p. 89-106.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Balle, B & Mohri, M 2018, 'Generalization bounds for learning weighted automata', Theoretical Computer Science, vol. 716, pp. 89-106. https://doi.org/10.1016/j.tcs.2017.11.023

APA

Balle, B., & Mohri, M. (2018). Generalization bounds for learning weighted automata. Theoretical Computer Science, 716, 89-106. https://doi.org/10.1016/j.tcs.2017.11.023

Vancouver

Balle B, Mohri M. Generalization bounds for learning weighted automata. Theoretical Computer Science. 2018 Mar 15;716:89-106. Epub 2017 Dec 1. doi: 10.1016/j.tcs.2017.11.023

Author

Balle, Borja ; Mohri, Mehryar. / Generalization bounds for learning weighted automata. In: Theoretical Computer Science. 2018 ; Vol. 716. pp. 89-106.

Bibtex

@article{3053d3aefd0543dbae461f8b44a7079d,

title = "Generalization bounds for learning weighted automata",

abstract = "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.",

keywords = "Learning theory, Generalization bounds, Weighted automata, Rademacher complexity",

author = "Borja Balle and Mehryar Mohri",

year = "2018",

month = mar,

day = "15",

doi = "10.1016/j.tcs.2017.11.023",

language = "English",

volume = "716",

pages = "89--106",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Generalization bounds for learning weighted automata

AU - Balle, Borja

AU - Mohri, Mehryar

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 - Learning theory

KW - Generalization bounds

KW - Weighted automata

KW - Rademacher complexity

U2 - 10.1016/j.tcs.2017.11.023

DO - 10.1016/j.tcs.2017.11.023

M3 - Journal article

VL - 716

SP - 89

EP - 106

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -

Research

Associated organisational unit

Links

Text available via DOI:

Keywords