Improved time complexities for learning Boolean networks
Summary: Existing algorithms for learning Boolean networks (BNs) have time complexities of at least \(O(N\cdot n^{0.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\cdot n^2)\) 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\cdot(N+\log n)\cdot n^2)\), 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.
- An efficient top-down search algorithm for learning Boolean networks of gene expression
- Algorithms for Inference, Analysis and Control of Boolean Networks
- Temporal Boolean network models of genetic networks and their inference from gene expression time series.
- Differentiable learning of matricized DNFs and its application to Boolean networks
- On learning gene regulatory networks under the Boolean network model
- A simple greedy algorithm for finding functional relations: Efficient implementation and average case analysis
- Algorithms for inferring functional dependencies from relations
- An efficient top-down search algorithm for learning Boolean networks of gene expression
- Decision lists and related Boolean functions
- Decision tree approximations of Boolean functions
- Exact learning Boolean functions via the monotone theory
- scientific article; zbMATH DE number 48812 (Why is no real title available?)
- scientific article; zbMATH DE number 3205804 (Why is no real title available?)
- Inferring Boolean functions via higher-order correlations
- Learning functions of \(k\) relevant variables
- Learning juntas in the presence of noise
- On learning gene regulatory networks under the Boolean network model
- On restricted-focus-of-attention learnability of Boolean functions
- On the complexity of inferring functional dependencies
- Tane: An Efficient Algorithm for Discovering Functional and Approximate Dependencies
This page was built for publication: Improved time complexities for learning Boolean networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q280576)
