A practical analysis of sample complexity for structure learning of discrete dynamic Bayesian networks

Geduk S., Ulusoy I.

OPTIMIZATION, 2021 (Peer-Reviewed Journal) identifier identifier

  • Publication Type: Article / Article
  • Volume:
  • Publication Date: 2021
  • Doi Number: 10.1080/02331934.2021.1892105
  • Journal Name: OPTIMIZATION
  • Journal Indexes: Science Citation Index Expanded, Scopus, Academic Search Premier, ABI/INFORM, Aerospace Database, Applied Science & Technology Source, Computer & Applied Sciences, MathSciNet, zbMATH


Discrete Dynamic Bayesian Network (dDBN) is used in many challenging causal modelling applications, such as human brain connectivity, due to its multivariate, non-deterministic, and nonlinear capability. Since there is not a ground truth for brain connectivity, the resulting model cannot be evaluated quantitatively. However, we should at least make sure that the best structure results for the used modelling approach and the data. Later, this result can be appreciated by further correlated literature of anatomy and physiology. Nearly all of the previously published studies rest on limited data, which brings doubt to the resulting structures. In theory, an immense number of samples is required, which is impossible to collect in practice. In this study, the appropriate number of data which makes a dDBN modelling trustable is searched by practical experiments and found to be O(Kp+1) for binary and ternary-valued networks, where K is the cardinality of the random variables and p is the maximum number of parents possibly present in the network. If a modelling approach satisfies this amount of data, we can at least say that the resulting structure is trustable.