Automata Cascades: Expressivity and Sample Complexity.
Alessandro RoncaNadezda Alexandrovna KnorozovaGiuseppe De GiacomoPublished in: AAAI (2023)
Keyphrases
- sample complexity
- theoretical analysis
- learning problems
- learning algorithm
- pac learning
- vc dimension
- supervised learning
- upper bound
- active learning
- generalization error
- lower bound
- special case
- pac learnability
- training examples
- finite state
- regular expressions
- sample complexity bounds
- irrelevant features
- sample size
- uniform convergence
- data sets
- learning tasks
- markov decision processes
- average case
- reinforcement learning
- training data
- e learning