论文部分内容阅读
动态系统(Dynamical system)是一个数学概念,指其状态根据一组固定规则(又称演变规则)随时间变化的系统,这组规则确定了系统的一个状态如何演变到另一个状态。离散动态系统指状态随离散时间步演变的动态系统。细胞自动机和布尔网络是典型的离散动态系统。由于布尔网络模型用于定性地分析基因调控网络,因此该模型提出后被广泛用于计算生物学和生物信息学领域。以一阶逻辑为基础的逻辑程序具有较好的知识表示与推理能力,是描述性问题求解的典范。归纳逻辑程序设计(Inductive Logic Programming,简称ILP)以被观察系统的背景知识为基础和观察到数据为样本,学习描述系统的逻辑程序规则,是重要的机器学习框架,在知识发现方面具有重要的应用价值。布尔网络提供了一种定性描述基因网络中最根本的关系和从属关系的工具。根据基因表达的数据反向推断基因网络拓扑结构的技术是目前研究构建基因调控网络模型使用较多的方法。所以根据观察的数据学习或推断网络模型(演变规则)是布尔网络研究中的基础问题之一。由于布尔网络的演变规则(布尔函数)可以用逻辑规则来表示,所以根据观察到的数据推断该网络演变规则的问题可以转变为根据观察到的数据归纳地学习出表示其演变规则的逻辑规则;因此归纳逻辑程序的范式可被用来处理这类学习问题。已有的利用归纳逻辑程序学习布尔网络演变规则的工作主要是从确定的状态转换集合(即每个状态的后继状态是唯一的)学习布尔网络演变规则,因而不能处理非确定状态转换下(后继状态不唯一)布尔网络演变规则的学习。本文主要研究非确定状态转换下布尔网络演变规则的学习,主要工作如下:(1)提出了析取布尔网络的概念、归纳学习析取逻辑程序的算法,并进行了实验。析取布尔网络是传统布尔网络的扩充,能处理部分不确定状态转换。文中证明了该类布尔网络的吸引子可以用析取逻辑程序的支承类语义来刻画,从而建立了联系析取逻辑程序和析取布尔网络之间的桥梁,这使得它们之间的理论结果可以相互借鉴;而且,可以通过观察逻辑程序的状态变换归纳学习析取逻辑程序,从而得到该析取逻辑程序对应的析取布尔网络模型(结构)。提出了从逻辑程序的状态转移变换学习析取逻辑程序的算法(简称LFDT)。该算法基于析取逻辑程序的基消解和组合消解两个规则,是Inoue等人从确定状态转移变换学习正规逻辑程序算法LF1T的推广。以Python实现了该学习算法原型系统,并用了6个描述基因调控的布尔网络为基准,以随机生成的网络状态变换为观察样本,有效学习了表达这些布尔网络在不确定状态转移变换下的析取逻辑程序。讨论了算法学习得到的程序与以逻辑程序表示的演变规则之间的关系,并分析了两个析取逻辑程序等价的相关性质,表明了判定两个析取逻辑程序在Tpd语义下是否等价这类问题的计算复杂性。(2)提出了从不确定状态转移变换学习析取逻辑程序的增量式学习算法LFDTIN。算法LFDT是批量式学习,当有新的状态变换观察样本时,必须由新旧样本组合在一起重新学习。LFDTIN在学习过程中通过修改当前状态可能影响的已有逻辑程序规则来重新学习部分逻辑程序。我们提出了增量学习方式下对已有的逻辑程序进行修改的方法并讨论了该方法的相关性质,证明了算法的可靠性和完备性。用C#实现了该算法原型系统,并以随机生成的哺乳动物基因调控布尔网络的状态转换为观察样本,从不确定状态转化中增量地学习析取逻辑程序。(3)提出了从一般状态转移变换学习异步更新语义下的正规逻辑程序框架NDTLFT。上述LFDT和LFDTIN学习算法都只能学习具有部分不确定状态转移变换的析取逻辑程序,即一个状态的所有后继状态之间在集合包含关系下是极小的。NDTLFT学习框架首先将给定状态的所有后继状态观察样本变换成确定状态变换,然后通过Inoue等人的LF1T学习算法学习得到正规逻辑程序,我们讨论了算法在异步状态变换语义下的可靠性和完备性,用Python实现了该学习算法原型系统。以4个描述基因调控的布尔网络为基准,分别生成了这4个布尔网络在一般、异步、同步语义下的状态转化。根据这些转换学习表示布尔网络演变规则的正规逻辑程序。