基于因果图推理算法研究及应用

基于因果图推理算法研究及应用

张文鹏1吴家伟2邵磊2

（1.华电集团山东公司；2.华电国际十里泉发电厂）

摘要：针对因果图推理中存在计算复杂等困难，提出了一种新的因果图近似推理算法。该方法直接在因果图中进行推理，避免了因果图割集展开，从而有效地降低了因果图推理复杂度，提高了因果图推理的计算速度，并且把它应用到电厂四管泄漏故障中。

关键词：因果图；知识表示；不确定性推理；四管泄漏

引言

近些年来，人工智能研究的课题主要集中在知识表示、机器学习等领域。知识表示和知识获取方法一直是人工智能的研究关键，它是专家系统的重要烟具内容。而如何有效的获取和实现计算机处理知识表示方式是各国学者研究的焦点，并提出了一些有价值的方法。但是，目前的知识表示方法仍有一定缺陷，不能适用于专家系统。因为在专家系统中处理的信息通常是不精确的，人们通常根据本领域的知识，进行归纳总结出知识的确定性因果关系，却难于获得不确定知识的描述，这是由于不确定知识的可信度不易获取。

张勤教授于1994年提出了一种不确定推理方法——动态因果图[1](以下简称因果图)是一种基于概率论与图论的不确定性表达和推理模型，是一种将因果知识和概率知识相结合的信息表示框架。这种知识表达方式非常直观，便于专家给定知识。

本文针对因果图解析推理算法[1]的逻辑运算量大等缺陷，提出一种因果近似推理算法，并把它应用到火电厂四管泄漏故障中。

2因果图

2.1因果图模型

因果图是基于概率分析、图论的一种不确定性知识表达和推理模型，是一种将因果知识和概率知识相结合的信息表示框架。它是在贝叶斯网的基础上发展而来，是一个允许具有环路的有向图。因此它可以形式化表示为：

（1）

其中，各符号分别代表：

D代表因果图模型。

X代表中间事件（或中间事件变量）。它表示任何有原因的事件；在图中用圆圈表示，至少一个输入，输出无限制。

B代表基本事件（或基本事件变量）。它表示没有原因或不去考虑其原因的事件，并且它至少为一个中间事件的原因.显然，基本事件之间相互独立。在图中用方框表示，无输入，至少一个输出。

G代表逻辑门。用于将输入变量通过逻辑运算组合成输出变量，输入变量到输出变量的映射有一张真值表表示，既可以是简单的与、或、非关系，也可以表示更复杂的逻辑关系。在图中用门表示，以基本事件、中间事件或逻辑门作为输入，以中间事件作为输出。

P代表连接事件（或连接事件变量）。它表示父节点事件导致子节点发生的事件，当父节点事件发生并且该连接事件发生，子节点事件必定发生。从数值上其概率表示父节点与子节点间的因果强度，但作为一个事件，它与父节点事件相互独立。在图中用一条有向弧表示，以基本事件、中间事件或逻辑门为输入，始终指向中间事件。

S代表因果图结构。有基本事件、中间事件、逻辑门、连接事件构成的有向图，它定性的表示了各节点间的因果关系。

A代表因果图的参数。由基本事件的先验概率，连接事件的连接概率。逻辑门的真值表组成，它定量的表示了各节点间的因果关系。

图1为一个因果图示例，在图中未有任何标记的连接事件，表示当父节点事件发生时，子节点事件必然发生，即该事件发生的概率为1。

2.2因果图解析算法推理过程

因果图解析算法推理分为四个步骤：

求中间事件的一阶割集。

这里割集就是一组事件以逻辑与的关系组合在一起，每个割集之间的关系为逻辑或。仅有和某节点事件相邻的事件构成的割集成为一阶割集。

求中间事件的最终割集。

仅有基本事件和连接事件表示的割集表达式称为节点事件的最终割集。

求中间事件的不交化割集。

图1典型因果图示例

设，其中，是一个,,,是变量的状态下标，则节点事件的不交化割集表达式[3]可表示为：

，其中“+”为互斥或操作符。

计算某中间事件的概率，或在给定的证据下，计算感兴趣事件的后验。

3一种新的因果图的近似推理算法

3.1因果图解析推理算法的缺陷

因果图解析推理算法存在计算时间长，计算复杂，逻辑运算量大的缺陷[4]。主要是由于以下原因造成：

最终割集在不交化过程中，应用相补、吸收和幂等律等逻辑运算使计算量大幅增加；

不交化最终割集表达式的逻辑与运算必进行吸收运算，这使得要对不交化的最终割集进行比较，计算量大。

3.2一种新的因果图近似推理算法

基于因果图解析算法的复杂运算，现给出一种新的因果图近似推理算法。

（I）基于因果图的推理在因果图中，假设所有的基本事件和连接事件相互独立。

具体规则如下：

只有一个事件（基本事件或中间事件或门事件）导致中间事件发生，则中间事件发生的概率为：

假设一个基本事件导致中间事件发生，为基本事件的概率，为连接事件的概率，为中间事件的概率，则：

（2）多个事件导致同一中间事件发生，则中间事件的发生概率为：

假设两个基本事件导致中间事件发生，并且，，然后求：

（5）

当有多个事件导致同一中间事件发生时，则

（6）

（3）与/或逻辑门运算的处理

若事件通过逻辑与/或运算后，导致中间事件发生。

①与门运算

假设，则

（7）

于是，

②或门运算

假设，则

（8）

于是，

（II）将因果图转为因果树。

为简化推理运算，在推理前需把因果图转化为因果树。因果树是以中间事件为树根，以因果图中基本事件为树叶，通过逻辑与/或门组织起的因果图。[5]若因果图存在有向环路，这个过程需要进行逻辑解环，逻辑解环的主要目的是消除因果图中存在的有向环路，该过程针对每一个中间事件节点单独进行。

解环规则[1]：一个节点不能在同一时刻成为导致自己发生的原因。其主要思想为针对每一个节点求解以该节点为根的一棵树，要求该树的每一条支路上不存在相同的节点，且如果对该树的任一节点继续展开将会破坏上述要求。以图4所示的因果图[1]为例，经过逻辑解环展开后如图5所示的一个森林。该森林的每一棵树成为一棵因果树。

图4带有向环路的因果图图5（1）节点对应的因果树

图5（2）节点对应的因果树

（III）因果树的新的近似推理算法。

具体推理算法如下所示：

把因果图转换为因果树；

根据要求的中间事件节点选定某一棵因果树，依据（I）中的三个规则从叶节点开始进行推理，最终求出中间事件的概率。

4某火电厂四管泄漏故障应用案例

假设有一批知识如下：

R1IFTHEN

R2IFTHEN

R3IFTHEN

R4IFTHEN

有这些知识构成的推理网络[2]如图6所示。在泄漏故障发生过程中，电厂业务专家告知：，

。

图6CF模型推理网络

由上述模型转化为对应的因果图如图7所示。对应的基本事件及连接事件的概率需要经过式（3）和（4）进行转换。

图7CF模型对应的因果图

下面应用新的因果图近似推理算法求解。

由图7可知：

,,,,

,,,

,。

由于图7所示的因果图本来就是一棵因果树，因此不用考虑从因果图向因果树的转换，也不用考虑有因果循环的情况，因此，直接5.2（III）步骤2进行计算，具体过程如下：

①；

②；

③

；

④

。

结束语

针对因果图解析推理算法的逻辑运算量大等缺陷，提出了一种新的因果图的近似推理算法，无需进行标准因果图推理算法的前三步，有效降低了推理复杂度，提高了实际运行速度，并且把这种算法应用于电厂四管泄漏中，因果图解决实际问题有重要意义。

参考文献

[1]张勤.DUCG:一种新的动态不确定因果知识的表达和推理方法(I):离散、静态、证据确定和有向无环图情况[J].计算机学报,2010,33(4):634.

[2]王洪春,石庆喜,张勤.基于因果图的一种推理算法[J].微计算机与计算机,2005,22(5):1-3,7.

[3]王洪春.基于因果图的一种知识获取方法[J].计算机仿真,2006,23(3):126-128.

作者简介

张文鹏，男，1973年9月，山东郓城，本科，汉，华电集团山东公司，250014，高级工程师，热能动力。