Research On Inductive Learning Of Discrete Dynamic Systems Based On Logic Programs

A dynamical system is a mathematical concept system whose state changes over time according to a set of fixed rules which determine how one state of the system evolves.A discrete dynamic system is a system in which the state variables change in discrete time points.A Boolean Network is an example of the discrete dynamical system.Since it can be used to analyze gene regulatory network,the model has been widely used in computational biology and bioinformatics.Logic programming is a typical programming paradigm,which is based on first-order logic.It has been widely applied in knowledge representation and reasoning.Inductive logic programming(ILP in short)learns logic program from observed background knowledge and data,where the background knowledge and data are logic programs.It is an important learning framework in machine learning.Boolean networks provide a qualitative description of the fundamental relationships between genes and gene regulatory networks.Constructing the gene regulatory network from gene expression data is an important problem in computational biology.Since Boolean functions can be converted to logic programs,inferring dynamics of Boolean Networks can be translated into learning logic programs from the observed data.Thus,the paradigm of ILP can be used to handle such a learning task.Most of the existing research in ILP learns the dynamics of synchronous Boolean Networks from deterministic state transitions.They cannot learn logic programs from non-deterministic state transitions.This paper aims to learn dynamics of Boolean Networks from non-deterministic state transitions.The main contribution are three folds:(1)A Disjunctive Boolean Network is proposed.It is an extension of classical Boolean network and can deal with partial uncertain state transition.It has been proved that the attractor of this kind of Boolean network can be characterized by the supporting class semantics of disjunctive logic program.The bridge between disjunctive logic program and disjunctive Boolean network is established,which makes the theoretical results between them can be used for reference.Furthermore,the model or structure of disjunctive Boolean networks can be learned by inductive learning disjunctive logic programs from the observed state transitions of the logic programs.An algorithm LFDT for learning disjunctive logic program from state transitions of logic program was proposed.The algorithm is based on the ground and combined resolution rules of disjunctive logic program,and it is an extension of the learning algorithm LF1T for normal logic programs from state transitions based on Inoue et al.A prototype of the learning algorithm was implemented with Python and was benchmarked with six Boolean networks.The randomly generated transitions of network state were used as observation samples to learn the disjunctive logic program that expresses these Boolean networks under the uncertain state transitions.This thesis discussed the relationship between the logic programs obtained from the algorithm and the evolution rules represented by logical programs,and its related properties of equivalence of disjunctive logic programs.Computational complexity of decision the equivalency of these programs under_PT~d semantics is discussed.(2)An incremental learning algorithm LFDTIN based on LFDT for learning disjunctive logic program from uncertain state transitions is proposed.The algorithm LFDT is a batch learner,whenever there is a new state transitions,the old sample must be combined with the new one to learn.During the learning process,LFDTIN relearns some logic programs by revising existing logic rules that may be affected by the current state.We propose a method to modify the existing logic program in incremental learning mode and discuss its related properties.The soundness and completeness of the algorithm are discussed.The prototype of the algorithm was implemented with C#.For the state transitions generated randomly by mammalian Boolean network,a logic program was incrementally learned from the uncertain state transitions.(3)The learning framework NDTLFT to learn normal logic program under the asynchronous update semantics from the general state transition transformation was developed.The above LFDT and LFDTIN algorithms can only learn disjunction logic programs with partial uncertain state transitions i.e.,all subsequent states of a state are subset minimal.The NDTLFT framework first transforms all subsequent state transitions of a given state into a deterministic state transition,and then learns the normal logic program through the existing learning algorithm LF1T of Inoue et al.We discuss the soundness and completeness of the algorithm under the asynchronous and general semantics.A prototype system of the algorithm was implemented in Python.Based on four Boolean networks describing four gene regulations,respectively,the state transitions of these four Boolean networks under general,asynchronous,and synchronous semantics were generated.Normal logic programs representing the evolution rules of Boolean networks were learned using this algorithm.