Every automaton can be decomposed into a cascade of basic automata. This is the Prime Decomposition Theorem by Krohn and Rhodes. We show that cascades allow for describing the sample complexity of automata in terms of their components. In particular, we show that the sample complexity is linear in the number of components and the maximum complexity of a single component. This opens to the possibility for learning automata representing large dynamic 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 in turn implies that it is only possible to learn automata where the number of states and letters is linear in the amount of data available. Instead our results show that one can in principle learn automata with infinite input alphabets and a number of states that is exponential in the amount of data available.
翻译:每个自动图都可分解成一个基本自动数据级联。 这是由克罗恩和罗得斯制作的原始分解理论。 我们显示, 级联允许用其组件来描述自动数据样本的复杂性。 特别是, 我们显示, 样本的复杂性在组件数量和单个组件的最大复杂性方面是线性复杂的。 这打开了学习由多个部分相互作用组成的大型动态系统的自动数据的可能性。 这与对自动数据样本复杂性的既定理解形成鲜明的对比, 后者以状态和输入字母的总数来描述, 而这反过来意味着, 只有在状态和字母数量在可用数据数量上线性的情况下, 才能学习自动数据 。 相反, 我们的结果显示, 原则上可以用无限的输入字母来学习自动数据, 以及可用数据数量指数指数化的状态 。