Asymptotical lower limits on required number of examples for learning boolean networks

Abul O., Alhajj R., Polat F.

21st International Symposium on Computer and Information Sciences (ISCIS 2006), İstanbul, Turkey, 1 - 03 November 2006, vol.4263, pp.154-164 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 4263
  • Doi Number: 10.1007/11902140_18
  • City: İstanbul
  • Country: Turkey
  • Page Numbers: pp.154-164
  • Middle East Technical University Affiliated: Yes


This paper studies the asymptotical lower limits on the required number of samples for identifying Boolean Networks, which is given as Omega(logn) in the literature for fully random samples. It has also been found that; O(logn) samples are sufficient with high probability. Our main motivation is to provide tight lower asymptotical limits for samples obtained from time series experiments. Using the results from the literature on random boolean networks, lower limits on the required number of samples from time series experiments for various cases are analytically derived using information theoretic approach.