Learning the Topology and Behavior of Discrete Dynamical Systems

• URL: http://arxiv.org/abs/2402.11686v2
• Date: Fri, 29 Mar 2024 19:16:16 GMT
• Title: Learning the Topology and Behavior of Discrete Dynamical Systems
• Authors: Zirou Qiu, Abhijin Adiga, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz, Richard E. Stearns, Anil Vullikanti,
• Abstract summary: We focus on the problem of learning the behavior and the underlying topology of a black-box system. We show that, in general, this learning problem is computationally intractable. Our results provide a theoretical foundation for learning both the behavior and topology of discrete dynamical systems.
• Score: 30.424671907681688
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Learning System Dynamics without Forgetting [60.08612207170659]
  Predicting trajectories of systems with unknown dynamics is crucial in various research fields, including physics and biology. We present a novel framework of Mode-switching Graph ODE (MS-GODE), which can continually learn varying dynamics. We construct a novel benchmark of biological dynamic systems, featuring diverse systems with disparate dynamics.
  arXiv  Detail & Related papers  (2024-06-30T14:55:18Z)
• Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks [30.424671907681688]
  We study the learnability of dynamical systems over multilayer networks, which are more realistic and challenging. We present an efficient PAC learning algorithm with provable guarantees to show that the learner only requires a small number of training examples to infer an unknown system.
  arXiv  Detail & Related papers  (2024-05-11T02:35:08Z)
• Learning Governing Equations of Unobserved States in Dynamical Systems [0.0]
  We employ a hybrid neural ODE structure to learn governing equations of partially-observed dynamical systems. We demonstrate that the method is capable of successfully learning the true underlying governing equations of unobserved states within these systems.
  arXiv  Detail & Related papers  (2024-04-29T10:28:14Z)
• Capturing Actionable Dynamics with Structured Latent Ordinary Differential Equations [68.62843292346813]
  We propose a structured latent ODE model that captures system input variations within its latent representation. Building on a static variable specification, our model learns factors of variation for each input to the system, thus separating the effects of the system inputs in the latent space.
  arXiv  Detail & Related papers  (2022-02-25T20:00:56Z)
• Leveraging the structure of dynamical systems for data-driven modeling [111.45324708884813]
  We consider the impact of the training set and its structure on the quality of the long-term prediction. We show how an informed design of the training set, based on invariants of the system and the structure of the underlying attractor, significantly improves the resulting models.
  arXiv  Detail & Related papers  (2021-12-15T20:09:20Z)
• Constructing Neural Network-Based Models for Simulating Dynamical Systems [59.0861954179401]
  Data-driven modeling is an alternative paradigm that seeks to learn an approximation of the dynamics of a system using observations of the true system. This paper provides a survey of the different ways to construct models of dynamical systems using neural networks. In addition to the basic overview, we review the related literature and outline the most significant challenges from numerical simulations that this modeling paradigm must overcome.
  arXiv  Detail & Related papers  (2021-11-02T10:51:42Z)
• Supervised DKRC with Images for Offline System Identification [77.34726150561087]
  Modern dynamical systems are becoming increasingly non-linear and complex. There is a need for a framework to model these systems in a compact and comprehensive representation for prediction and control. Our approach learns these basis functions using a supervised learning approach.
  arXiv  Detail & Related papers  (2021-09-06T04:39:06Z)
• Estimating Linear Dynamical Networks of Cyclostationary Processes [0.0]
  We present a novel algorithm for guaranteed topology learning in networks excited by cyclostationary processes. Unlike prior work, the framework applies to linear dynamic system with complex valued dependencies. In the second part of the article, we analyze conditions for consistent topology learning for bidirected radial networks when a subset of the network is unobserved.
  arXiv  Detail & Related papers  (2020-09-26T18:54:50Z)
• Learning Stable Deep Dynamics Models [91.90131512825504]
  We propose an approach for learning dynamical systems that are guaranteed to be stable over the entire state space. We show that such learning systems are able to model simple dynamical systems and can be combined with additional deep generative models to learn complex dynamics.
  arXiv  Detail & Related papers  (2020-01-17T00:04:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.