Learning the Topology and Behavior of Discrete Dynamical Systems

Authors

  • Zirou Qiu Computer Science Dept., University of Virginia Biocomplexity Institute, University of Virginia
  • Abhijin Adiga Biocomplexity Institute, University of Virginia
  • Madhav V. Marathe Computer Science Dept., University of Virginia Biocomplexity Institute, University of Virginia
  • S. S. Ravi Biocomplexity Institute, University of Virginia Computer Science Dept., University at Albany – State University of New York.
  • Daniel J. Rosenkrantz Biocomplexity Institute, University of Virginia Computer Science Dept., University at Albany – State University of New York.
  • Richard E. Stearns Biocomplexity Institute, University of Virginia Computer Science Dept., University at Albany – State University of New York.
  • Anil Vullikanti Computer Science Dept., University of Virginia Biocomplexity Institute, University of Virginia

DOI:

https://doi.org/10.1609/aaai.v38i13.29390

Keywords:

ML: Learning Theory, ML: Other Foundations of Machine Learning, MAS: Other Foundations of Multi Agent Systems

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 certain 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 Natarajan dimension formalism. Our results provide a theoretical foundation for learning both the topology and behavior of discrete dynamical systems.
AAAI-24 / IAAI-24 / EAAI-24 Proceedings Cover

Downloads

Published

2024-03-24

How to Cite

Qiu, Z., Adiga, A., Marathe, M. V., Ravi, S. S., Rosenkrantz, D. J., Stearns, R. E., & Vullikanti, A. (2024). Learning the Topology and Behavior of Discrete Dynamical Systems. Proceedings of the AAAI Conference on Artificial Intelligence, 38(13), 14722-14730. https://doi.org/10.1609/aaai.v38i13.29390

Issue

Vol. 38 No. 13: AAAI-24 Technical Tracks 13

Section

AAAI Technical Track on Machine Learning IV