Generalization bounds for learning weighted automata
From MaRDI portal
Publication:1704563
Abstract: This paper studies the problem of learning weighted automata from a finite labeled training sample. We consider several general families 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, or 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 families. We further present upper bounds on these Rademacher complexities, which reveal key new data-dependent terms related to the complexity of learning weighted automata.
Recommendations
- Learning weighted automata
- Weighted automata are compact and actively learnable
- A lower bound for learning distributions generated by probabilistic automata
- Learning weighted automata over principal ideal domains
- Approximate learning of limit-average automata
- Spectral learning of weighted automata. A forward-backward perspective
- On the Rademacher complexity of weighted automata
- On Optimal Learning Algorithms for Multiplicity Automata
- Algorithmic Learning Theory
Cites work
- scientific article; zbMATH DE number 1804106 (Why is no real title available?)
- scientific article; zbMATH DE number 3932372 (Why is no real title available?)
- scientific article; zbMATH DE number 41838 (Why is no real title available?)
- scientific article; zbMATH DE number 49190 (Why is no real title available?)
- scientific article; zbMATH DE number 3497806 (Why is no real title available?)
- scientific article; zbMATH DE number 3588051 (Why is no real title available?)
- scientific article; zbMATH DE number 1552503 (Why is no real title available?)
- scientific article; zbMATH DE number 3371972 (Why is no real title available?)
- A Canonical Form for Weighted Automata and Applications to Approximate Minimization
- A trace inequality of John von Neumann
- Absolute convergence of rational series is semi-decidable
- An introduction to matrix concentration inequalities
- Biological Sequence Analysis
- Combinatorial methods in density estimation
- Dimension-free concentration bounds on Hankel matrices for spectral learning
- Formal Analysis of Online Algorithms
- Foundations of machine learning
- Handbook of weighted automata
- Lp DISTANCE AND EQUIVALENCE OF PROBABILISTIC AUTOMATA
- Learning weighted automata
- Matrices de Hankel
- Model checking linear-time properties of probabilistic systems
- Noncommutative rational series with applications
- On the Rademacher complexity of weighted automata
- On the computational complexity of approximating distributions by probabilistic automata
- Rational kernels: theory and algorithms
- Realizations by stochastic finite automata
- Spectral learning of weighted automata. A forward-backward perspective
- Understanding machine learning. From theory to algorithms
- Uniform Central Limit Theorems
- VC-dimensions of finite automata and commutative finite automata with \(k\) letters and \(n\) states
- Weighted automata algorithms
Cited in
(5)
This page was built for publication: Generalization bounds for learning weighted automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1704563)
