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, Türkiye, 1 - 03 Kasım 2006, cilt.4263, ss.154-164 identifier identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 4263
  • Doi Numarası: 10.1007/11902140_18
  • Basıldığı Şehir: İstanbul
  • Basıldığı Ülke: Türkiye
  • Sayfa Sayıları: ss.154-164
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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.