Discrete dynamical systems are commonly used to model the spread of contagions on real-world networks. Under the PAC framework, existing research has studied the problem of learning the behavior of a system, assuming that the underlying network is known. In this work, we focus on a more challenging setting: to learn both the behavior and the underlying topology of a black-box system. We show that, in general, this learning problem is computationally intractable. On the positive side, we present efficient learning methods under the PAC model when the underlying graph of the dynamical system belongs to some classes. Further, we examine a relaxed setting where the topology of an unknown system is partially observed. For this case, we develop an efficient PAC learner to infer the system and establish the sample complexity. Lastly, we present a formal analysis of the expressive power of the hypothesis class of dynamical systems where both the topology and behavior are unknown, using the well-known formalism of the Natarajan dimension. Our results provide a theoretical foundation for learning both the behavior and topology of discrete dynamical systems.

在PAC模型下，本文研究了学习系统行为和底层拓扑结构的问题，并表明在一般情况下，这一学习问题是计算上难以处理的；然而，在底层图属于某些特定类别时，我们提出了高效的学习方法；另外，对于拓扑结构部分已知的未知系统，我们开发了一个高效的PAC学习器来推断系统并建立了样本复杂性；最后，我们使用Natarajan维度的著名表述方法对既未知拓扑结构又未知行为的动力系统的假设类的表达能力进行了正式分析，为学习离散动力系统的行为和拓扑结构提供了理论基础。

学习离散动力系统的拓扑结构和行为