Automata Cascades: Expressivity and Sample Complexity
Authors: Alessandro Ronca, Nadezda Alexandrovna Knorozova, Giuseppe De Giacomo
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that the sample complexity is linear in the number of components and the maximum complexity of a single component, modulo logarithmic factors. This opens to the possibility of learning automata representing large dynamical systems consisting of many parts interacting with each other. It is in sharp contrast with the established understanding of the sample complexity of automata, described in terms of the overall number of states and input letters, which implies that it is only possible to learn automata where the number of states is linear in the amount of data available. Instead our results show that one can learn automata with a number of states that is exponential in the amount of data available. Overall, our results show that the sample complexity of automata can be decoupled from the the number of states and input letters. Rather, it can be described in terms of the components of a cascade capturing the automaton. |
| Researcher Affiliation | Collaboration | Alessandro Ronca1, Nadezda Alexandrovna Knorozova2,3, Giuseppe De Giacomo1,4 1DIAG, Sapienza University of Rome 2Relational AI 3IFI, University of Zurich 4Computer Science Department, University of Oxford |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper does not provide concrete access information for a publicly available or open dataset used for training. It uses an illustrative 'Minecraft-like domain' example, but not as an experimental dataset. |
| Dataset Splits | No | The paper is theoretical and does not describe experimental dataset splits for validation. |
| Hardware Specification | No | The paper does not provide specific hardware details as it focuses on theoretical contributions. |
| Software Dependencies | No | The paper does not provide specific ancillary software details with version numbers. |
| Experiment Setup | No | The paper does not contain specific experimental setup details, as it is a theoretical work. |