首页 理论教育 真值维护系统

真值维护系统

时间:2022-02-11 理论教育 版权反馈
【摘要】:真值维护系统或称TMS正是被设计用于处理这类复杂情况的。一种更加有效的方法是基于准则的真值维护系统,或 JTMS。一个基于假设的真值维护系统,或称ATMS,被设计成用来使假设世界之间的这类上下文切换特别高效。ATMS在同一时刻表示已经被考虑的所有状态。真值维护系统同时也提供一种生成解释的机制。用来实现真值维护系统的准确算法有一点复杂,这里我们不再谈论。因此,你不应该期待真值维护是万能药。

10.8 真值维护系统

前面的小节讨论了从知识表示系统得到的推论只有缺省情况,而不是绝对的确定。不可避免地,这里面某些推论的事实最后发现是错误的,将不得不在新的信息面前撤消。这个过程称为信度修正[48]。假设一个知识库KB包含一条语句P——可能是被前向链接算法记录的一个缺省结论,或可能只是一个不正确的断言——我们想要执行TELL(KB,¬P)。为了避免产生矛盾,我们必须首先执行RETRACT(KB, P)。这听起来足够容易。然而问题出现了,如果有任何附加语句从P中推断出来并在KB中得到断言。例如,蕴含式PQ可能被用来添加Q。明显的“解决方案”——撤消从P推断出的所有语句——会失败,因为这样的语句可能有除了P以外的其它准则。例如,如果R和RQ也在KB中,那么Q毕竟不是不得不消除的。真值维护系统(truth maintenance system)或称TMS正是被设计用于处理这类复杂情况的。

真值维护的一个非常简单的方法是通过对语句进行从 P1到 Pn的编号,记录语句被告诉给知识库的顺序。当调用了 RETRACT(KB,Pi)时,系统恢复到 Pi被添加前的状态,由此删除 Pi以及任何从 Pi得到的推论。然后语句Pi+1到Pn可以被再次添加。这是简单的,而且它保证知识库是一致的,但是撤消Pi需要撤消和重新断言n−i个语句,以及撤消和重新完成从这些语句得到的推论。对已经添加了许多事实的系统而言——比如大型商业数据库——这是不切实际的。

一种更加有效的方法是基于准则的真值维护系统,或 JTMS。在一个 JTMS 中,知识库的每条语句用一个由推理出它的语句集组成的准则来标记。例如,如果知识库已经包含了 PQ,那么TELL(P)将引起用准则{P,PQ}把Q添加到知识库。通常,一个语句可以有任何数目的准则。准则被用来使得撤消保持高效率。给定RETRACT(P)调用,JTMS会准确地删除那些满足条件的语句,条件就是P是该语句的每条准则的成员。所以,如果一个语句Q有唯一准则{P,PQ},那么它会被删除,如果它有附加准则{P,P∨RQ},它仍然会被删除,但是如果它还有准则{R,P∨RQ},那么它会被留下。这样,撤消P需要的时间只依赖于从P推导出的语句数,而不是从P进入知识库以后添加的其它语句数。

JTMS假定那些被考虑过一次的语句将可能被再次考虑,所以我们把语句标记为ou(t 在知识库外),而不是当一个语句失去所有准则时就从知识库中完全删除。如果随后的断言恢复准则之一,那么我们把语句标记为in(返回知识库中)。这样,JTMS保留它使用的全部推理链,并当一条准则再次变得有效时,不需要重新推导语句。

除了处理对不正确信息的撤消,TMS能被用来加速对多重假设环境的分析。例如,假想罗马尼亚奥林匹克委员会正在选择将在罗马尼亚举行的2048年奥运会的游泳(swimming),田径(athletics)、骑马(equestrian)项目的场地。例如,设第一个假设为Site(Swimming,Pitestci),Site(Athletics,Bucharest),和Site(Equestrian, Arad)。然后必须进行大量的推理来计算出后勤的结果和因此对这个选择产生的满意程度。如果我们想考虑用Site(Athletics,Sibiu)替代,那么TMS避免了再次从头开始的需要。作为替代,我们只是简单地撤消Site(Athletics,Bucharest),并断言Site(Athletics,Sibiu),而且TMS将照顾必要的修正。从选择Bucharest产生的推理链可以对Sibiu再次使用,倘若结论是同样的话。

一个基于假设的真值维护系统,或称ATMS,被设计成用来使假设世界之间的这类上下文切换特别高效。在JTMS中,准则的维护允许你通过少量的撤消和断言从一个状态迅速地移动到另一个状态,但是在任何时刻只表示一个状态。ATMS在同一时刻表示已经被考虑的所有状态。然而 JTMS 只需要简单地用in或out标记每个语句,AT M S则需要对每个语句记录哪个假设会使该语句为真。换句话说,每个语句有一个用一套假设集组成的标记。语句只有在一个假设集中的全部假设都成立时才成立。

真值维护系统同时也提供一种生成解释的机制。技术上,语句P的一个解释是一个语句集合E,这样的E蕴涵P。如果E中的语句已知为真,那么E提供了足够的基础来证明P也一定是成立的。但是解释也可以包括假设——并不已知为真的语句,但是如果它们正确的话,仍然足够来证明P。例如,一个人可能没有足够的信息证明他的汽车不能启动,但是一个合理的解释可能包括电池失效的假设。这与汽车如何运转的知识相结合,解释了观察到的无行为的状况。在大部分情况下,我们倾向于一个最小的解释E,意味着E中没有合适的子集也是一个解释。ATMS能够通过我们希望的任何顺序的假设(诸如“车内的汽油”或者“电池失效”),甚至一些互相矛盾的假设来生成对“汽车不能启动”问题的解释。然后我们通过看语句“汽车不能启动”的标记来很快地读出将证明该语句的假设集。

用来实现真值维护系统的准确算法有一点复杂,这里我们不再谈论。真值维护问题的计算复杂度至少跟命题推理一样大——也就是,NP 难题。因此,你不应该期待真值维护是万能药。不过,当小心使用时,TMS能够在逻辑系统的能力上提供一个实质的增强以处理复杂环境和假设。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈