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

ABSTRACT

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\left(K^{p+1}\right)$ 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.

Keywords:

• Discrete Dynamic Bayesian Nnetworks
• Sample Complexity
• Structure Learning

Acknowledgments

This study was completed as a part of the master's thesis completed and advised by the authors [55].

Disclosure statement

No potential conflict of interest was reported by the author(s).