更新命题(或证据)的不确定性值的算法
规则前件中诸证据的组合方法
表2中给出了规则前件中诸证据的组合方法,注意这里与PROSPECTOR一样,都使用了基于模糊逻辑的方法。
规则前件
规则前件的不确定性值
E2ANDE1
min{CF(E1,e),CF(E2,e)}
E2ORE1
max{CF(E1,e),CF(E2,e)}
NOTE
-CF(E,e)
表2e表示与前件中的证据相关的所有证据CF(E1,e)和CF(E2,e)
分别表示E1和E2的当前不确定性值
例给出某规则之前件E,E=(E1ANDE2ANDE3)OR(E4ANDNOTE5),e是与E相关的所有证据,前件E中诸Ei(i=1,2,…,5)的当前不确定性值为:
CF(E1,e)=0.9,CF(E2,e)=0.8,CF(E3,e)=0.3,CF(E4,e)=0.5,CF(E5,e)=0.4.
E之不确定性值的计算如下
E=max{min(CF(E1,e),CF(E2,e),CF(E3,e)),min(CF(E4,e),-CF(E5,e))}
=max{min(0.9,0.8,0.3),min(-0.5,-(-0.4))}
=max{0.3,-0.5}=0.3
一条规则中的不确定性值的传播
MYCIN中的规则,IFETHENHCF(H,E),其中E,H,CF(H,E)分别是规则的前件,规则之后件(或曰结论),规则强度。
规则强度表示:
当E为真(或者说,规则前件为真)时,H为真的程度。
规则也可表成:
.
(2.10)
作为公式(2.1.11)的例子,有规则R1:
IFE1ANDE2ANDE3THENHCF(H,E1ANDE2ANDE3),e表示与E1,E2,E3有关的所有证据,E=E1ANDE2ANDE3=E1E2E3,已知CF(H,E)=0.7,CF(E1,e)=0.5,CF(E2,e)=0.6,CF(E3,e)=0.3.
注意:
推理树(即与或树)之叶节点的不确定性值是由用户给出的。
规则R1前件的不确定性:
CF(E,e)=CF(E1E2E3,e)=min{CF(E1,e),CF(E2,e),CF(E3,e)}=min{0.5,0.6,0.3}=0.3>0.2,可见规则R1满足触发条件,这里的0.2表示规则触发阈值。
为何设置规则触发阈值?
?
规则R1后件(或结论)的不确定性:
CF(H,e)=CF(E,e)×CF(H,E)=0.3×0.7=0.21
两条后件相同之规则的结论的不确定性值的综合
(2.11)
如果另有一条满足触发条件的规则R2,其后件也是H,并且e*表示与规则R2之前件中的证据相关的所有证据,CF(H,e*)=0.5,那么可用公式(2.11)计算CF(H,e)=0.21和CF(H,e*)=0.5的综合结果:
CF(H,e&e*)=CF(H,e)+CF(H,e*)-CF(H,e)×CF(H,e*)=0.71-0.105=0.605
显然,公式(2.11)具有可交换性,即CF(H,e1&e2)=CF(H,e2&e1),在被综合(或组合)的结论相同的一组规则中,两两综合次序与综合结果无关。
.
§4MYCIN的不确定性值(或不确定性因子)计算的封闭性
CF[-1,+1],显然只须对公式(2.11)证明封闭性。
证明:
假设有两条规则IFE1THENHCF(H,E1)和IFE2THENHCF(H,E2),e1和e2分别表示与E1和E2相关的所有证据。
a.CF(H,e1)0且CF(H,e2)0
CF(H,e1&e2)=CF(H,e1)+CF(H,e2)-CF(H,e1)×CF(H,e2)
=CF(H,e1)×(1-CF(H,e2))+CF(H,e2)
1-CF(H,e2)+CF(H,e2)=1
因为CF(H,e1)×CF(H,e2)CF(H,e2),
所以CF(H,e1)+CF(H,e2)-CF(H,e1)×CF(H,e2)CF(H,e1)+CF(H,e2)-CF(H,e2)0
有0CF(H,e1&e2)1
b.CF(H,e1)0且CF(H,e2)0
CF(H,e1&e2)=CF(H,e1)+CF(H,e2)+CF(H,e1)×CF(H,e2)
=-(|CF(H,e1)|+|CF(H,e2)|-|CF(H,e1)|×|CF(H,e2)|)
故由a.可知-1CF(H,e1&e2)0
c.CF(H,e1)×CF(H,e2)=-1
由公式(2.1.12),可知CF(H,e1&e2)=0
d.CF(H,e1)×CF(H,e2)<0并且|CF(H,e1)×CF(H,e2)|1
不妨令CF(H,e1)<0,CF(H,e2)>0
d1.假定|CF(H,e1)||CF(H,e2)|
d2.假定|CF(H,e1)||CF(H,e2)|
当|CF(H,e1)|=|CF(H,e2)|时,X=0;当|CF(H,e1)|=1时,X=-1;
故有-1X0.证毕
§5确定性因子的困难
虽然MYCIN在疾病诊断方面取得了很大的成功,但是在确定性因子的理论方面却存在着一些困难。
它的主要优点是不确定性的计算简单,信任和不信任清晰地被分开,能表达无知,CF也很直观、容易被理解。
确定性因子存在的主要困难:
有时确定性因子方法得到的CF值和条件概率值相反。
例,如果
P(H1)=0.8P(H2)=0.2P(H1|E)=0.9P(H2|E)=0.8
那么,我们有CF(H1,E)=0.5和CF(H2,E)=0.75.
确定性因子方法的一个意图是用CF值来排列,比方说疾病假说的次序,但是具有较高条件概率的假说却有较低的CF值,这是明显是一个矛盾。
在MYCIN中,未要求(从而不能保证)任一个推理链中的任意两条规则的确定性因子(规则强度)间是概率独立的。
某一个(任意一个)推理链中的任意两条规则是:
,
那么,通常有P(H|e)P(H|I)×P(I|e),其中I是基于证据e的该推理链中的一个中间假说(或假设)。
但是,在MYCIN中就认为有下式成立:
P(H|e)=P(H|I)×P(I|e)()
在上述问题存在的情况下,MYCIN还能取得如此的成功,主要是因为比较短的推理链和比较简单的假设(或假说)缘故。
值得庆幸的是,在实际应用中相当数量的问题是能满足“比较短的推理链和比较简单的假设”的要求的。
事实上,亚当斯(Adams,1985年)具体说明了确定性因子理论实际上是标准概率论的近似。
实际应用问题常常具有较短的推理链,决不是说实际问题的解决只需一步推理,一般说来,不是很复杂的问题推理链大约不超过5步(推理树大约在5层)。
第三章基于确定性因子模型的专家系统的验证
§1引言
专家系统(ExpertSystem,ES)是一个智能程序,它能对那些需要专家知识才能解决的应用问题,包括应用难题,提供权威专家水平的解答。
ES是一种智能化的计算机程序系统,因此,在ES的建造过程中对一些技术细节必须加以认真考虑。
作为一种基于知识的系统,ES必须具有一定数量的、高水平的应用领域知识,而这些知识必须能够反映出权威专家解决问题的特点和经验。
一般说来,在建造ES之初,需要知识工程师和领域专家的密切合作,一方面权威领域专家根据所要解决的领域问题的特点,总结和整理领域知识,和知识工程师一起完成领域问题求解建模,另一方面知识工程师要构建(或选用合适的)知识表示和问题求解的形式化模型。
知识的质量和丰富程度对于ES的性能影响很大,所以对知识进行有效的评价和检测,是ES建造的关键步骤之一。
在人类的认知和推理过程中,无论是对一个事实(或曰命题、证据)的描述,还是对一条规则的刻画,都具有不确定性和/或模糊性,所以ES需要具有处理不确定性和/或模糊性问题的能力。
本文的讨论主要面对具有不确定性的领域问题。
迄今为止有代表性的不确定性处理模型主要有MYCIN模型、PROSPECTER模型、证据理论模型和贝叶斯网等等。
确定性因子理论(CertaintyFactorTheory),也被称为确定性因子,确定性因子方法,斯坦福确定性因子代数(TheStanfordCertaintyFactorAlgebra)等。
70年代中期斯坦福大学的肖特里夫(Shortliffe)等人为建造专家系统MYCIN,开展了处理不确定性的方法确定性因子理论的研究[2].
一方面,尽管在确定性因子的理论方面存在着一些困难,但由于其不确定性值的计算简单,信任
和不信任清晰地被分开,能表达无知,CF(CertaintyFactor)很直观、容易被领域专家理解,并且MYCIN在诊断等方面的应用中又取得了很大成功,所以基于确定性因子采用产生式规则表达知识的专家系统
一直有着广泛的应用。
另一方面,在确定性因子理论研究和基于确定性因子理论的专家系统的建造方面仍然有一些重要的技术细节被忽略,并且在已开发的一些专家系统中还存在着错误,如果这些问题不予以认真解决,那么对专家系统研究、建造和应用都有较大的副面影响。
由此,本文打算以不确定性处理方法和知识表示形式分别采用确定性因子理论和产生式规则的专家系统(简称为基于确定性因子的专家系统或MYCIN类专家系统)为例,侧重研究:
如何测试、评价已开发的基于确定性因子的专家系统。
§2测试、评价内容
本文打算重点测试、评价基于确定性因子的专家系统的推理机和知识库。
对推理机的测试、评价内容主要包括不确定性计算(或曰不确定性处理模型),推理控制策略,不确定性计算、推理控制策略和知识表达的关系,推理效率和准确性,不确定性计算模型的敏感性分析等。
对知识库的测试、评价主要包括知识库的一致性、完备性,规则的质量,循环推理链,规则之间的约束关系等。
这里应指出的是本文所选择的测试、评价内容是不完备的,只是较好地覆盖了应重点测试和评价的条款。
§2.1推理机的测试与评价[1-7]
1.不确定性值计算的封闭性
对于一个不确定性处理模型,其不确定性值计算的封闭性必须被证明。
特别对于新提出的模型,这一问题是绝对不能缺少的。
MYCIN的确定性因子模型的封闭性已有证明,故本文不再讨论。
2.测试证据(或事实)阈值
测试要点:
证据的存在阈值,证据的不存在阈值,证据的无知阈值;
测试方法:
●检查技术报告中是否明确设定了证据的三种阈值,若设定了则评价阈值的设定是否合理;
●检查程序实现是否与技术报告相一致:
通过分析相应的算法判断;通过合适的例子进行检测。
合理设定证据阈值的例子
在不确定性的意义下,说某证据E趋向于存在,是指该证据(或该事实)的不确定性值达到或超过某一指定的阈值。
在专家系统和知识库的建造中应认真设定证据的存在阈值。
对于MYCIN系统,一般说来:
一个证据的信度值大于等于0.2则说该证据趋向于存在(在阈值意义下,简称存在),一个证据的信度值小于等于0.2则说该证据趋向于不存在(在阈值意义下,简称不存在),一个证据的信度值在0.2与0.2之间则说对该证据趋向于无知(在阈值意义下,简称无知)。
迄今为止,有关文献仅仅提到规则触发阈值[2]。
证据阈值是证据存在阈值、证据不存在阈值和对证据无知阈值的总称。
证据阈值可由下式表达:
3.规则触发阈值[2]
测试要点:
规则触发阈值
测试方法:
●检查技术报告是否明确设定了规则触发阈值,若设定了则评价阈值的设定是否合理;
●检查程序实现的是否和技术报告相一致:
通过分析相应的算法进行判断;使用合适的例子进行检测。
规则触发阈值合理设定的例子
为了避免误差较大的观点被传播,应设定规则触发阈值,一般可设为0.2~0.3.规则被触发的条件是:
规则前件的不确定性值大于等于规则触发阈值(当触发阈值大于零时)或小于等于规则触发阈值(当触发阈值小于零时)。
证据阈值和规则触发阈值的设定,一方面提高了系统的推理效率,另一方面也避免了误差(因传播所导致)的扩大化。
4.检查是否选用了正确的综合(或曰组合)公式[1][2]
任意前件中诸证据相互独立的两条规则,若其前件不同但其后件相同,且它们的后件都是假设或中间假设,则称这两条规则具有综合关系。
在实际生活中如果人们对同一问题的看法不一致时,一般应遵循少数服从多数的原则。
这一原则应体现在规则的综合公式中。
例如,若某综合节点H汇集了三路证据,其中有两路证据支持H,另有一路证据反对H,并且这三路证据对H的支持强度或反对强度基本相同,并假定以H为后件的三条规则都满足规则触发条件,那么综合的结果就好象三路证据中仅仅有一路支持H的证据存在一样。
两条前件不同,后件(一个假设或中间假设,也称为结论或中间结论)相同之规则的结论的不确定性值的正确综合公式为:
公式中的
作为分母,保证了少数服从多数成立。
5.综合节点的匹配冲突消解
在与或树中,具有综合关系的多条(2条)规则之后件,一个假设或中间假设,被称做(与或树中的)一个综合节点。
假定以某一个综合节点为后件的规则有N条,且有M条规则满足了规则触发条件,MN,那么推理机必须确保这M条规则依序被执行,就是说这M条规则中只要有一条规则R*被执行,那么其余的M1条规则就要紧接着R*,一条紧接着一条地被执行。
检查方法:
1.分析推理机算法;2.使用合适的例子进行测试。
6.敏感性分析[4][6]
分析、测试一棵与或树的诸叶节点的不确定性值的变化对根节点的不确定性值的影响,以确定输出对输入变化的敏感程度,较好的不确定性计算模型既不应该太敏感,也不应该过于迟钝。
检测方法:
给出分析不确定性模型的方法;选择合适的数据组进行测试。
§2.2知识库的测试与评价[2][7]
1.规则强度阈值
检查知识库中的规则是否符合规定