View Item 
      •   Home
      • 1. Schools
      • College of Engineering
      • School of Computer Science and Engineering (SCSE)
      • SCSE Journal Articles
      • View Item
      •   Home
      • 1. Schools
      • College of Engineering
      • School of Computer Science and Engineering (SCSE)
      • SCSE Journal Articles
      • View Item
      JavaScript is disabled for your browser. Some features of this site may not work without it.
      Subject Lookup

      Browse

      All of DR-NTUCommunities & CollectionsTitlesAuthorsBy DateSubjectsThis CollectionTitlesAuthorsBy DateSubjects

      My Account

      Login

      Statistics

      Most Popular ItemsStatistics by CountryMost Popular Authors

      About DR-NTU

      Improved time complexities for learning boolean networks

      Thumbnail
      Improved Time Complexities for Learning Boolean Networks.pdf (1.226Mb)
      Author
      Zheng, Yun.
      Kwoh, Chee Keong.
      Date of Issue
      2013
      School
      School of Computer Engineering
      Version
      Published version
      Abstract
      Existing algorithms for learning Boolean networks (BNs) have time complexities of at least O(N · n0:7(k+1)), where n is the number of variables, N is the number of samples and k is the number of inputs in Boolean functions. Some recent studies propose more efficient methods with O(N · n2) time complexities. However, these methods can only be used to learn monotonic BNs, and their performances are not satisfactory when the sample size is small. In this paper, we mathematically prove that OR/AND BNs, where the variables are related with logical OR/AND operations, can be found with the time complexity of O(k·(N+ logn)·n2), if there are enough noiseless training samples randomly generated from a uniform distribution. We also demonstrate that our method can successfully learn most BNs, whose variables are not related with exclusive OR and Boolean equality operations, with the same order of time complexity for learning OR/AND BNs, indicating our method has good efficiency for learning general BNs other than monotonic BNs. When the datasets are noisy, our method can still successfully identify most BNs with the same efficiency. When compared with two existing methods with the same settings, our method achieves a better comprehensive performance than both of them, especially for small training sample sizes. More importantly, our method can be used to learn all BNs. However, of the two methods that are compared, one can only be used to learn monotonic BNs, and the other one has a much worse time complexity than our method. In conclusion, our results demonstrate that Boolean networks can be learned with improved time complexities.
      Subject
      DRNTU::Engineering::Computer science and engineering
      Type
      Journal Article
      Series/Journal Title
      Entropy
      Rights
      © 2013 The Authors, licensee MDPI. This paper was published in Entropy and is made available as an electronic reprint (preprint) with permission of the authors. The paper can be found at the following official DOI: [http://dx.doi.org/10.3390/e15093762]. One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper is prohibited and is subject to penalties under law.
      Collections
      • SCSE Journal Articles
      http://dx.doi.org/10.3390/e15093762
      Get published version (via Digital Object Identifier)

      Show full item record


      NTU Library, Nanyang Avenue, Singapore 639798 © 2011 Nanyang Technological University. All rights reserved.
      DSpace software copyright © 2002-2015  DuraSpace
      Contact Us | Send Feedback
      Share |    
      Theme by 
      Atmire NV
       

       


      NTU Library, Nanyang Avenue, Singapore 639798 © 2011 Nanyang Technological University. All rights reserved.
      DSpace software copyright © 2002-2015  DuraSpace
      Contact Us | Send Feedback
      Share |    
      Theme by 
      Atmire NV
       

       

      DCSIMG