Control 版 (精华区)

发信人: dagam (断情), 信区: Control
标  题: [转载]非确定性因素！[2]
发信站: 哈工大紫丁香 (2001年07月01日11:52:02 星期天), 站内信件


规则的格式
既然是使用我们自己编写的推理引擎，那么我们就可以自己定义规则的格式，而不需要
使用prolog提供的标准格式，
怎样就更加易于用户理解阅读规则。它的基本形式如下：
rule(Name,LHS,RHS).
LHS是前提，而RHS是结论。Name是规则名称。
在prolog提供的标准的规则结构中是这样的形式：
RHS:-LHS.
对于RHS，它包括结论以及这个结论的可信度。
rhs(Goal,CF).
LHS则包括一系列的子目标用来证明或者推翻RHS。
lhs(GoalList).
其中GoalList是子目标的列表。
下面来定义目标的格式，在这里我们使用最简单的目标格式：属性以及其值。例如gas_
gauge(汽油表）是一个属性，
而low则是它的值。有些属性具有布尔值，就是说只有是或者不是两种值。我们定义的一
种结构贮存这种值：
av(Attribute,Value).其中Attribute，Value都是简单的原子。
完整的规则结构如下：
rule(Name,
lhs( [av(A1, V1), av(A2, V2), ....] ),
rhs( av(Attr, Val), CF) ).
前面的规则5按照这种形式表达的话就是：
rule(5,
lhs( [av(turns_over, yes), av(gas_gauge, empty)] ),
rhs( av(problem, flooded), 80) ).
很明显这种规则的定义并不是很容易阅读。不过它对于我们的推理引擎是再合适不过的
了。在今后的我们会介绍
两种增进规则的阅读性的方法，一种是使用定义操作符的方法，另外一种是使用prolog
内建的DCG功能。（关于DCG
在prolog的语言教学的最后一章：自然语言中有介绍）
推理引擎
到目前为止我们已经定义了自己的知识表达的规则，下面我们就来开发自己的推理引擎
。首先我们来总结一下推理
引擎需要完成的工作。
如前面说叙述的那样处理可信度。
维护工作空间的数据。
找到关于某个属性的所有的信息，并且保存到工作空间中。
推理引擎所使用的主要的谓词如下：
findgoal
---already known
fact
---ask user
askable
query_user
---derive from rules
fg
rule
prove
findgoal
adjust
update
fact
combine
这里使用树状结构表达谓词之间的层次，下面我们都会分别详细介绍。
存储空间的格式
让我们首先来定义存储空间中储存的格式。我们使用下面的格式储存：
fact(av(A,V),CF).
使用fact储存已经知道的事实。
寻找属性的值
我们从寻找某个目标的值开始编写推理引擎。在这个汽车专家系统中我们是希望找到pr
oblem这个属性的值。主谓词为
findgoal/2，在这个汽车专家系统中我们可以在解释器中输入下面的询问以开始和专家
系统的对话：
?-findgoal(av(problem,X),CF).
findgoal需要处理三种不同的情况：
属性值已经存在与工作空间；
有能够推理出属性值的规则；
必须对用户进行询问。
我们使用askable谓词定义那些属性是需要从用户那里获得的，同时也定义询问的提示，
例如：
askable(live,'Where does it live?').
使用前面的fact谓词和askable谓词，我们可以来编写findgoal了。
findgoal的第一个子句用来处理工作空间中已经存在的信息。如果在工作空间中找到了
所需要的信息，就不需要执行其
他的子句了，因此最后面有个截断符号。
findgoal(av(Attr,Val),CF):-
fact(av(Attr,Val),CF),
!
如果在工作空间没有找到相关的信息，而所要询问的属性被定义为从用户那里获得的时
候，就向用户提问。
findgoal(av(Attr, Val), CF) :-
not fact(av(Attr, _), _),
askable(Attr, Prompt),
query_user(Attr, Prompt),
!,
findgoal(av(Attr, Val), CF).
query_user谓词向用户询问属性值以及它的确信度，然后把用户的回答加入到工作空间
中，而最后的递归调用findgoal
则会找到query_user加入工作空间的信息。
query_user(Attr, Prompt) :-
write(Prompt),
read(Val),
read(CF),
asserta( fact(av(Attr, Val), CF)).
最后我们要来编写从规则推算出属性值的子句。注意，我们的推理引擎需要找出和目标
有关的信息，然后合并确信度。
这个工作有fg谓词完成。fg使用尾递归的方法找出所有从RHS可以推导出目标属性值的规
则。当属性值的确信度为100，
或者所有的规则搜索完毕的时候，就是fg递归的边界条件。
findgoal(Goal, CurCF) :-
fg(Goal, CurCF).
fg(Goal, CurCF) :-
rule(N, lhs(IfList), rhs(Goal, CF)), %寻找某个包含目标Goal的规则
prove(IfList, Tally), %计算前提可信度
adjust(CF, Tally, NewCF), %根据规则确信度和前提确信度计算新的确信度。
update(Goal, NewCF, CurCF), %更新数据。
CurCF == 100, !. %如果确信度为100就停止搜索。
fg(Goal, CF) :- fact(Goal, CF).
在fg中调用了3个新的谓词：
prove-检查LHS前提，并且计算它的确信度。
adjust-联合LHS确信度和RHS确信度。
update-更新工作空间中的值。
这个新的推理引擎的工作原理如下：首先找到RHS和目标匹配的规则，然后把这个规则的
LHS（前提）传递给prove，
prove计算前提的确信度，为了计算前提的确信度，就需要递归调用findgoal。如果pro
ve失败，那么就回溯到上一个目标，
也就是寻找下一个符合目标的规则。
prove(IfList, Tally) :-
prov(IfList, 100, Tally).
prov([], Tally, Tally).
prov([H|T], CurTal, Tally) :-
findgoal(H, CF), %找到前提H的确信度CF，
min(CurTal, CF, Tal),%比较CF和当前的最小的确信度CurTal，返回其中较小的一个。

Tal >= 20, %判断前提确信度大于极限确信度。
prov(T, Tal, Tally). %递归处理剩下的列表。
min(X, Y, X) :- X =< Y, !.
min(X, Y, Y) :- Y =< X.
prove的输入参数是规则的前提列表，而输出则是这个前提列表的确信度。prove调用pr
ov，prov多一个保存临时数据的参数。
prov递归调用它自己来逐个考虑前提列表中的每个前提，而它递归调用findgoal找到每
个前提的确信度。由于前提确信度就是
所有前提中最小的确信度，所以使用min谓词寻找最小的值。每一次保存的临时数据都是
到目前为止最小的前提确信度。
当prove成功的找到了前提确定度以后，就使用adjust谓词联合前提确信度和规则确信度
，从而得到最终的目标确信度。
adjust(CF1, CF2, CF) :-
X is CF1 * CF2 / 100,
int_round(X, CF).
int_round(X, I) :-
X >= 0,
I is integer(X + 0.5).
int_round(X, I) :-
X < 0, I is integer(X - 0.5).
由于系统的工作空间中可能已经存在关于某个目标的确信度，所以要使用update来联合
通过不同的途径计算的某
个目标的几个确信度。即完成前面所说的联合目标确信度的工作。
update(Goal, NewCF, CF) :-
fact(Goal, OldCF),
combine(NewCF, OldCF, CF),
retract( fact(Goal, OldCF) ),
asserta( fact(Goal, CF) ),
!.
update(Goal, CF, CF) :-
asserta( fact(Goal, CF) ).
combine(CF1, CF2, CF) :-
CF1 >= 0,
CF2 >= 0,
X is CF1 + CF2*(100 - CF1)/100,
int_round(X, CF).
combine(CF1, CF2, CF) :-
CF1 < 0,
CF2 < 0,
X is - ( -CF1 -CF2 * (100 + CF1)/100),
int_round(X, CF).
combine(CF1, CF2, CF) :-
(CF1 < 0; CF2 < 0),
(CF1 > 0; CF2 > 0),
abs_minimum(CF1, CF2, MCF),
X is 100 * (CF1 + CF2) / (100 - MCF),
int_round(X, CF).
这几个谓词比较简单，这里就不详细的解释了，其实就是按照前面的公式直接编写出来
的。
最后还要加上能够处理否定的子句，因为某个规则也可能是“如果不....就....”的形
式。在这里我们加入一个新的findgoal子句来处理这种情况：
findgoal(not Goal, NCF) :-
findgoal(Goal, CF),
NCF is - CF, !.
它可以解释为如果Goal的确信度是CF，那么not Goal确信度就是-CF。
这个子句应该放在所有的findgoal子句的前面。
到此为止，我们的推理引擎就全部制作完毕了，怎么样，理解了么？
外壳程序
这里所使用的外壳程序和上一章所介绍的类似，就不再多解释了。这里的top_goal和上
一章的有所不同，请自己体会。
super :-
repeat,
write('consult, load, exit'), nl,
write(':'),
read_line(X),
doit(X),
X == exit.
doit(consult) :- top_goals, !.
doit(load) :- load_rules, !.
doit(exit).
top_goals :-
top_goal(Attr),
top(Attr),
print_goal(Attr),
fail.
top_goals.
top(Attr) :-
findgoal(av(Attr, Val), CF), !.
top(_) :- true.
print_goal(Attr) :-
nl,
fact(av(Attr, X), CF),
CF >= 20,
outp(av(Attr, X), CF), nl,
fail.
print_goal(Attr) :-
write('done with '), write(Attr), nl, nl.
outp(av(A, V), CF) :-
output(A, V, PrintList),
write(A-'cf'-CF),
printlist(PrintList),
!.
outp(av(A, V), CF) :-
write(A-V-'cf'-CF).
printlist([]).
printlist([H|T]) :- write(H), printlist(T).
改进规则的表达
到目前为止我们已经介绍完了包含非确定因素的专家系统的编写方法，最后我们讨论一
下如何使用prolog的DCG功能美
化规则的定义方法。（关于DCG在prolog的语言教学的最后一章：自然语言中有介绍）
load_rules(F) :-
clear_db,
see(F),
lod_ruls,
write('rules loaded'), nl,
seen, !.
lod_ruls :-
repeat,
read_sentence(L),
process(L),
L == eof.
process(eof) :- !.
process(L) :-
trans(R, L, []),
assertz(R), !.
process(L) :-
write('translate error on:'), nl,
write(L), nl.
clear_db :-
abolish(top_goal, 1),
abolish(askable, 4),
abolish(rule, 3).
这段代码调用read_sentence把句子转化为列表，然后再使用trans谓词把列表转化为pr
olog的子句。也就是说这段程序把
前面我们容易看懂得规则翻译成推理引擎能够是别的规则格式。
顶层的翻译谓词trans用以识别三种允许的规则表达模式。
trans(top_goal(X))-->[goal, is, X].
trans(top_goal(X))-->[goal, X].
trans(askable(A, M, P))-->
[ask, A], menux(M), prompt(A, P).
trans(rule(N, lhs(IF), rhs(THEN, CF)))--> id(N), if(IF), then(THEN, CF).
下面的谓词用以识句子中的菜单和提示语。
menux(M)--> [menu, '('], menuxlist(M).
menuxlist([Item])--> [Item, ')'].
menuxlist([Item|T])--> [Item], menuxlist(T).
prompt(_, P)--> [prompt, P].
prompt(P, P)--> [].
最后是分析规则结构的谓词。根据我们的需要可以写出非常接近自然语言的规则翻译功
能。
id(N)-->[rule, N].
if(IF)-->[if], iflist(IF).
iflist([IF])-->phrase(IF), [then].
iflist([Hif|Tif])-->phrase(Hif), [and], iflist(Tif).
iflist([Hif|Tif])-->phrase(Hif), [', '], iflist(Tif).
then(THEN, CF)-->phrase(THEN), [cf], [CF].
then(THEN, 100)-->phrase(THEN).
phrase(not av(Attr, yes))-->[not, Attr].
phrase(not av(Attr, yes))-->[not, a, Attr].
phrase(not av(Attr, yes))-->[not, an, Attr].
phrase(not av(Attr, Val))-->[not, Attr, is, Val].
phrase(not av(Attr, Val))-->[not, Attr, are, Val].
phrase(av(Attr, Val))-->[Attr, is, Val].
phrase(av(Attr, Val))-->[Attr, are, Val].
phrase(av(Attr, yes))-->[Attr].
使用DCG可以方便的定义简便的知识库的语法。（原文转自“垂钓听竹轩”）


iflist([Hif|Tif])-->phrase(Hif), [', ']从不喜欢光光一个,可惜偏偏光光一个
then(THEN, CF)-->phrase(THEN), [cf], [CF].
then(THEN, 100)-->phrase(THEN).
phrase(not av(Attr, yes))-->[not, Attr].
phrase(not av(Attr, yes))-->[not, a, Attr].
phrase(not av(Attr, yes))-->[not, an, Attr].
phrase(not av(Attr, Val))-->[not, Attr, is, Val].
phrase(not av(Attr, Val))-->[not, Attr, are, Val].
phrase(av(Attr, Val))-->[Attr, is, Val].
phrase(av(Attr, Val))-->[Attr, are, Val].
phrase(av(Attr, yes))-->[Attr].
使用DCG可以方便的定义简便的知识库的语法。（原文转自“垂钓听竹轩”）

--

--
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: heart.hit.edu.cn]