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

2006-11-03
Abul, Osman
Alhajj, Reda
Polat, Faruk
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.