第八章 不确定知识的表示与推理
教学目的：对不确定知识的表示方法及推理技术。
教学重点和难点：1. 随机性知识的表示、模糊性知识的表示、模糊集合与模糊逻辑和多值逻辑；2. 不确定性推理的一般模式；3. 基于证据理论的不确定性推理；难点：模糊集合与模糊逻辑和模糊性知识的表示。
主要教学内容及要求：
了解：不确定性推理的一般模式
理解：不确定性推理方式
掌握：随机性知识的表示、模糊性知识的表示、模糊集合与模糊逻辑和多值逻辑；基于证据理论的不确定性推理。
熟练掌握：主观Bayes 方法及其推理方法
对于许多比较复杂的人工智能系统，往往含有复杂性、不完全性、模糊性或不确定性。当采用产生式系统或专家系统的结构时，要求设计者建立某种不确定性问题的代数模型及其计算和推理过程。为此，下面我们将和大家一起讨论一些常用的不确定性推理方法。
8.1 概率推理
基于概率论的不确定性推理有很多种，在这里我们仅讨论比较成熟的一种推理方法──主观Bayes 方法。
1.Bayes 公式及主观Bayes 方法
主观Bayes 方法是R.O.Duda 、P.E.Hart 等人1976年在Bayes 公式的基础上经适当改进提出了主观Bayes 方法，它是最早用于处理不确定性推理的方法之一，已在地矿勘探专家系统PROSPECTOR 中得到了成功的应用。下面我们先来介绍Bayes 公式。
若有诸事件A 1,A 2,…，A n ，彼此独立，且B 为事件A 1＋A 2＋…＋A n 的子事件，P (A i )>0(i=1,2,…,n) ，P (B )>0，那么Bayes 公式可表示为：
式中，为先验概率；为后验概率。Bayes 公式就是从先验概率推导出后验概率的公式。为阐明主观Bayes 方法，先引入几个概念：
(1) 几率函数
几率函数定义为
它表示x 的出现概率与不出现概率之比，显然随P (x ) 的加大(x ) 也加大，而且
当P(x)=0时，有(x ) ＝ 0
当P(x)=1时，有(x ) ＝∞
于是，取值于[0,1]的P (x ) 被放大为取值于[0, ∞]的(x ) 。
(2) 充分性度量
充分性度量定义为
它表示E 对H 的支持程度，取值于[0, ∞],由专家给出。
(3) 必要性度量
必要性度量定义为
它表示 对Ｈ的支持程度，即E 对H 为真的必要性程度，取值范围为[0,+∞]，也是由专家凭经验给出。
2. 证据的不确定性描述
在主观Bayes 方法中，证据的不确定性也是用概率表示的。在PROSPECTOR 中，由于根据观察S 直接求出P(E/S)非常困难，所以它采用了一种变通的方法，即引进了可信度C(E/S)的概念，用户可根据实际情况在[-5,5]中选取一个整数作为初始证据的可信度。可信度C(E/S)与概率P(E/S)的对应关系可用下式表示：
特别地， C(E/S)=-5，表示在观察S 下证据E 肯定不存在，即P(E/S)=0； C(E/S)=0 ，表示在观察S 与证据E 无关，即P(E/S)=P(E)； C(E/S)=5 ，表示在观察S 下证据E 肯定存在，即P(E/S)=1。 这样，用户只要对证据E 给出在观察S 下的可信度C(E/S)，系统即可求出相应的P(E/S)。 对于组合证据
E ＝E 1 AND E2AND …AND En
则
P(E/S)＝min{P(E1/S), P(E2/S), …,P(En /S)}
对于组合证据
E ＝E 1 OR E2 OR … OR En
则
P(E/S)＝max{P(E1/S),P(E2/S),…,P(En /S)}
3. 基于主观Bayes 方法的不确定性推理
在主观Bayes 方法中，知识是用产生式规则表示的，具体形式为：
IF E THEN (LS,LN) H (P(H))
LS,LN 在上文已有定义，P(H)是专家给出的先验概率。推理就由P(H)，P(E)，LS 和LN 求出
的过程。而一条规则的前项有可能肯定存在，也可能肯定不存在，或者不确定，而且在不同情况下求解后验概率的方法亦不相同，以下分别予以讨论。
(1)证据E 确定必出现时，即P(E)=P(E/S)=1，由Bayes 公式，
由以上两式可得，
即有，
若需要以概率的形式表示，再由公式
计算出
这就是把先验概率P (H ) 更新为后验概率P(H/E)的计算公式。
(2)证据E 确定必不出现时，即P(E)=P(E/S) = 0，采用和上述类似的方法可得
从而
这就是把先验概率P(H)更新为后验概率
(3) 当证据E 不确定时，即
的计算公式。
就不能用上面的公式计算后验概率，可用Duda 于1976年给出的公式
来计算出后验概率。这分为四种情况：
① 当
故
这就是证据肯定存在的情况。
② 当
故有
这就是证据肯定不存在的情况。
③ 当时，Ｅ与Ｓ无关，利用全概率公式有，
④ 当即
为其它值时，通过分段线性插值的方法，就可以得到计算的公式，
该公式称为EH 公式。
对于初始证据，由于其不确定性是用可信度给出，此时只要把计算与的公式：
的对应关系转换公式代入EH 公式，就可以得到用可信度
该公式称为CP 公式。
这样，当用初始证据进行推理时，根据用户告知的通过运用CP
公式就可以求出
当用推理过程中得到的中间结论作为证据进行推理时，通过运用EH
公式就可求出
4. 结论不确定性的合成算法
若有n 条规则都支持相同的结论，而且每条规则的前提条件所对应的证据Ｅi （i = 1,2,…,n）都有相应的观察S i 与之对应，此时只要先对每条规则分别求出
主观Bayes 方法是在概率论的基础上发展起来的，具有较完善的理论基础，且知识的输入转化为对LS 和LN 的赋值，这就避免大量的数据统计工作，是一种比较实用且较灵活的不确定性推理方法。但是，它在要求专家给出LS 和LN 的同时，还要求给出先验概率
P (H ) ，而且要求事件间相互独立，这仍然比较困难，从页也就限制了它的应用。
8.2 贝叶斯网络
贝叶斯网络亦称信念网络(Belief Network)，于是1985年由Judea Pearl首先提出。它是一种模拟人类推过程中因果关系的不确定性处理模型，其网络拓朴结构是一个有向无环图(DAG)。它的节点用随机变量或命题来标识，认为有直接关系的命题或变量则用弧来连接。例如，假设结点E 直接影响到结点H ，即E→H，则建立结点E 到结点H 的有向弧(E,H)，权值(即连接强度) 用条件概率P(H/E)来表示，如图4.19所示：
图8.1 有两个结点的贝叶斯网络示意图
图 8.2 有6个节点的贝叶斯网络
一般来说，有n 个命题x 1,x 2,,x n 之间相互关系的一般知识可用联合概率分布来描述。但是，这样处理使得问题过于复杂。Pearl 认为人类在推理过程中，知识并不是以联合概率分布形表现的，而是以变量之间的相关性和条件相关性表现的，即可以用条件概率表示。如
例如，对如图4.20所示的贝叶斯网络，
有
一旦命题之间的相关性由有向弧表示，条件概率由弧的权值来表示，则命题之间静态结构关系的有关知识就表示出来了。
当获取某个新的证据事实时，要对每个命题的可能取值加以综合考查，进而对每个结点定义一个信任度，记作Bel(x)。可规定
Bel(x) = P(x=xi / D)
来表示当前所具有的所有事实和证据D 条件下，命题x 取值为x i 的可信任程度，然后再基于Bel 计算的证据和事实下各命题的可信任程度。
8.3 模糊逻辑推理与可能性理论
模糊推理与前面几节讨论的不确定性推理有着实质性的区别。前面那几种不确定性推理的理论基础是概率论，它所研究的事件本身有明确而确定的含义，只是由于发生的条件不充分，使得在条件与事件之间不能出现确定的因果关系，从而在事件的出现与否上表现出不确
定性，那些推理模型是对这种不确定性，即随机性的表示与处理。模糊推理的理论基础是模糊集理论以及在此基础上发展起来的模糊逻辑，它所处理的事物自身是模糊的，概念本身没有明确的外延，一个对象是否符合这个概念难以明确地确定模糊推理是对这种不确定性，即模糊性的表示与处理。
1. 模糊逻辑推理
模糊逻辑推理是基于模糊性知识(模糊规则) 的一种近似推理，一般采用Zadeh 提出的语言变量、语言值、模糊集和模糊关系合成的方法进行推理。
(1) 语言变量
语言变量一般用来描述那些不精确的事件或现象，就是我们通常所说的属性名，例如“年纪”就是一个语言变量，其取值可为“老”、“中”、“青”等。这些值可看成是论域U=[0, 150]上模糊子集的标名，而数字变量u ∈[0, 150]称为基变量。
(2) 证据模糊性及模糊规则的表示
命题的模糊性可用模糊子集来描述，例如设有命题“张三比较小”，则可以表示为
其中＝“比较小”=1/1+1/2+0.5/3+0.2/4+0.1/5+0/6=(1,1,0.5,0.2,0.1,0) 是一个模糊子集，代表“比较小”这个模糊概念。
一条模糊规则实际上是刻划了其前件中的模糊集与结论中的模糊集之间的一种对应关系。Zadeh 认为，这种对应关系是两个集合间的一种模糊关系，因而它也可以表示为模糊集合。特别地，对于有限集，则这个模糊集合就可以表示为一个模糊矩阵。例如有规则
其中，都是模糊子集，表示模糊概念。这个规则就表示了也可以表示为一个模糊子集。于是， 之间的一种模糊关系，表示这模糊关系，则
其中，U 、V 分别为模糊集合
对于的隶属度。
，Zadeh 给出了一种方法：
＝
其中、分别代表取最小值和取量大值，即min 、max 。如果所属的论域，是元素 为求得隶属度 都是有限集，则就是一个矩阵。
这样，一条模糊规则就可以用隶属度刻划的模糊集合来描述。
(3) 模糊推理
模糊推理有很多种，在这里我们仅介绍一种简单而常用的方法，如需要更深一步的研究，可参考其它有关书籍。
模糊推理可以通过模糊关系的合成来进行。假设有规则
：
其推理模式为
=
=
其中，
一般情况下，n=1。
这样， 就是规则R 按上述方法导出模糊集合，而就是所推的结论。当然，它仍是一个模糊集合。如果需要，可再将它翻译为自然语言的形式。
2. 可能性理论
Zadeh 1965年提出了模糊集合论，在此基础上1978年又建立了可能性理论，并将不确定性理解为可能性。在本节，我们简单介绍一下可能性理论，欲想进行一步的了解可参考有关文献。
假设U 为一论域，x 是取值于U 上模糊变量，是U 上的一个模糊子集。那么对于模糊命题“x is
赋值
= ”就可以导出一个等于的可性分布。这样，
“x is ”可变成一个可能性
它用来定义在U 中取任何可能值的可能性。例如，令U 表示人，对于“x比较小”这一模糊命题可表示为
“”。其中x U ， = "比较小" = 1/1 + 1/2 + 0.5/3 + 0.2/4 + 0.1/5 + 0/6 = (1,1,0.5,0.2,0.1,0),那么这一命题就以导出如下的可性分布：
POSS {x =1}=1
POSS {x =2}=1
POSS {x =3}=0.5
POSS {x =4}=0.2
POSS {x =5}=0.1
POSS {x =6}=0
另外，还规定
POSS (x =a ∧x =b )= min {poss (x =a ), poss (x =b )}
POSS (x =a ∨x =b )= max {POSS (x =a ), POSS (x =b )}
POSS (x a )=1－POSS (x =a )
综上所述, x 的可能性分布本质上就是一个模糊子集。因此，可能性分布与模糊集合的表现形式是一致的，所以我们可以用模糊集合的一些运算规则对可能性分布进行操作。总之，果如以可能性来度量不确定性，则我们就可运用可能性理论来讨论不确定性推了。
8.4 缺省推理
1．引言
建立在谓词逻辑基础上的传统系统是单调的，其意思是：已知为真的命题数目随时间而严格增加。那是由于新的命题可加入系统，新的定理可被证明，但这种加入和被证明决不会导致前面已知为真或已被证明的命题变成无效。这种系统具有以下优点：
(1) 当加入一新命题时，不必检查新命题与原有知识间的不相容性。
(2) 对每一个已被证明了的命题，不必保留一个命题表。它的证明以该命题表中的命题为根据，因为不存在那些命题会被取消的危险。
可是，这种单调系统不能很好地处理常常出现在现实问题领域中的3类情况，即不完全的信息、不断变化的情况、以及求解复杂问题过程中生成的假设。
很少有能在处理过程中拥有它所需要的一切信息的系统。但当缺乏信息时，只要不出现相反的证据，就可以作一些有益的猜想。构造这种猜想称为缺省推理(default reasoning)。例如，假设当你去朋友家吃晚饭，并经过路旁的卖花亭时，对于“你的主人喜欢花吗?”这样一个问题，你可能没有任何具体信息可作为回答问题的依据。但若利用一般的规则——因为大多数人们喜欢花，假定这个具体的人也喜欢，除非有相反的证据(如对花过敏) ，那么，你可作出决定。这类缺省推理是非单调的(即加进一条信息就可能迫使取消另一条信息) ，因为用这种方式推导出来的命题是依赖于在某个命题中缺少某种信念，即如果前面那些缺省的命题一旦加入系统，就必须消除用缺省推理产生的命题。这样一来，如果你拿着花走到门口时，你的主人立刻打喷嚏，你就应取消以前的信念——你的主人喜欢花。当然，你也必须取消建立在已被取消的信念基础上的任何信念。
上述举例说明了一个普通类型的缺省推理，称为最可能选择。如果知道一些事情中的某件事必为真，在缺乏完全知识条件下，应选最可能的那个。如：大多数人喜欢花；大多数狗有尾巴；对瑞典人而言，最一般的头发颜色为淡黄色。另一重要类型的缺省推理是约束推理(circumscription)在这种推理中只有当能证明某些对象满足性质P 时，才认为它们满足性质P 。例如，设需求解的问题是划船过河，可能列举许多妨碍成功过河的因素，如没有船桨，船漏水，船搁浅在泥沙中等等。而重要的是，问题求解程序不必去证明这些条件不是真的(因为可能问题本身的说明根本没提到船桨) 。程序能作的是，假定只有那些能够清楚地被证明为真的事情才是真的(希望没一个为真) ，否则不为真。那时，程序才能往前进行并假定能使用船。
2．定义
一个既精确又可算的缺省推理的描述，必涉及结论Y 且缺少某一信息X 。所以缺省推理的定义为：
缺省推理的定义1：如果X 不知道，那么得结论Y 。
但在所有的系统中，除最简单的系统外，只有存贮在数据库中的事件的极小部分可看成是已知的。不过，通过各种努力，事件的其余部分可从已知部分推导出来。所以缺省推理的定义更像是：
缺省推理的定义2：如果X 不能被证明，那么得结论Y 。
但是，如果仍然以谓词逻辑工作，那怎么能知道X 不能被证明? 由于这系统是不可判定的，所以对任一X 来说，仍不能担保它能否被证明。于是我们不得不重新考虑定义： 缺省推理的定义3：如果X 不能在某个给定的时间内被证明，那么得结论Y 。
值得注意，定义推出结论Y 的推理过程依赖于逻辑领域外的某些事件，在规定时间内可作多少计算，以及在寻找待求的证明中计算是否有效。因此作出关于系统行为的形式说明就显得特别重要。加之，我们丧失了谓词逻辑所具有的对所提出的证明的正确性进行验证的能力，即使一个证明存在，也不一定能保证找到它。假如现在得到一证明，对证明过程中的某一步来说，由于没有能力证明X ，所以得结论Y 。但由于X 是否可被证明是不可判定的，因而包含这个证明在内的更大的证明也就不可判定。于是，由于缺乏完全的知识，对缺省推理的需要迫使我们使用这样的系统，它的行为不易形式地描述出来。
即使有幸获得了关于某一情况的完全知识，也不能由此而长时间使用它，因为客观世界在迅速地变化着。这意味着在一个时刻完全精确的说明不会是持久的。这就是框架问题，一种引入状态变量对它进行处理的方法，已在第2.5节介绍过。但这种方法不很完善，因为只要状态中各谓词为真，它就要对每个状态作单独的描述。于是得花很多精力来重复地说明一个缓慢变化的事实。而且，凡每一操作执行后，就得引进一新状态，因此很难发现若干个操作序列已导致同一情况。另一种求解不断变化的世界问题的方法，是取消那些不能再精确描述世界的命题，而代之以另一些更精确的命题。这又使其变成了非单调系统。在这类系统中，命题既可从知识库中删去，也可加入。而且当一个命题被取消后，其证明依赖于这个被取消命题的其它命题也应取消。
即使供某一系统采用的知识不存在上述两个问题，一个好的问题求解系统在问题求解过程中，也可能产生某些非单调行为的知识。假若要编一程序来求解一个极简单的问题，例如找一适当时间使3个忙人能同时参加会议。一个办法是首先假设会议在某个具体日期举行，比如星期三，并将关于此假设的命题放入数据库中，再从3个人的时间安排表中检查不相容性。如果出现冲突，就表示假设的命题必须取消，而代之以另一个希望不矛盾的命题。当然，任何依赖于这个被取消命题而建立起来的命题也必须取消。于是又得到一个非单调系统。 当然，这种情况可用带回溯的直
接树搜索来处理。一切假设和由假设
得出的推论，均记录在产生它们的搜
索树的结点上。当产生一个不相容时，
只需回溯到尚未探索过的路径的一个
结点上。这时原假设和它们的推论将
自动消失。这种回溯方法如图4.22所
示。
它显示出一个安排会议程序的搜
索树的一部分。为此，程序必须求解
一个约束满足问题，即找出每个参加
者都有空闲的开会日期与时刻，并有
可供开会的房间。 图 8.3 非面向从属关系的回溯
求解该问题时，系统必须试图在一个时刻满足一个约束。最初，几乎没有根据可以肯定哪个时间最好，所以随意确定为星期三。于是产生一个新的约束，解的其余部分必须满足会议在星期三举行的假设，且存放在所产生的结点上。接着，程序试图选择一个时刻，使之适合于所有参加者。在他们的工作时间表中，通常白天的会议时刻可能在除14∶00外的任意时刻，所以选择14∶00作为开会时间，至于在哪一天倒没关系。然而，程序发现在星期三无房间可供开会使用。所以它回溯穿过结点(假设星期三的结点) ，并改在另一天，比如星期
二。现在就必须复制导出时刻为14∶00的推理链，因为它回溯到选日期时，原推理链已经消失，尽管该时刻推理未依靠任何关于日期为星期三的假设。
如果按照搜索过程产生命题的次序去取消命题，而不是按照该命题内涵的不相容性去取消命题，那么将会产生很大的浪费。最好是在需要时既能直接将假设插入到数据库，又能取消它们。这种方式称为面向从属关系的回溯。
基于下述一些原因中的任何一个，都可察觉非单调推理系统的必要性：
(1) 不完全知识的出现要求缺省推理。
(2) 一个不断变化的世界必须用适应不断变化的数据库来描述。
(3) 产生一个问题的完全解可能要求关于部分解的暂时的假设。
3. 非单调推理系统
正确性维持系统(Truth Maintenane System,TMS)是一个已经实现了的非单调推理系统。它用以协助其它推理程序维持系统的正确性，所以它的作用不是生成新的推理，而是在其它程序所产生的命题之间保持相容性。一旦发现某个不相容，它就调出自己的推理机制，面向从属关系的回溯，并通过修改最小的信念集来消除不相容。
在TMS 中，每一命题或规则均称为节点，且对任一节点，以下两种状态必居其一： IN 相信为真
OUT 不相信为真，或无理由相信为真，或当前没有可相信的理由。
每个节点附有一证实表，表中每一项表示一种确定节点有效性的方法。IN 节点是指那些至少有一个在当前说来是有效证实的节点。OUT 结点则指那些当前无任何有效证实的节点。也许有人想知道为什么要不厌其烦地保留OUT 结点? 当然，花许多功夫去产生一些表示不正确命题的节点是没有意义的。但必须记住，在非单调推理系统中，产生一节点是以表示一个假定为真的命题，例如，使用缺省推理的结果。这时其余节点则在假设原始节点为IN 的基础上产生。
但新信息的出现可能引起原始节点变成OUT(缺少信息时用缺省推理) ，那时，一切基于它的节点都相应要变为OUT 。不过，保留这些节点和它们的相互依赖性仍有用处。因为一旦有效信息发生了变化，而且引起原始节点再变为IN 时，那些在它的基础上用来产生其它节点的推理就不必重作了。于是，当原始节点再变为IN 时，其它各个节点的某个基于原始节点的证实将随之变为有效，这些节点也就变为IN 了。
在系统中，有两种方式可用来证实一个节点的有效性可依赖于其它节点的有效性：
(1) 支持表(SL(IN 节点)(OUT 节点))
(2) 条件证明(CP(结论)
(IN 假设)
(OUT 假设))
1. 支持表(Support List)
支持表最通用。如果在IN 节点表中提到的节点当前都是IN ，且在OUT 节点表中提到的节点当前都是OUT ，那么，它们是有效的。例如，下述节点：
(1)现在是冬天(SL( ) ( ))
(2)天气是寒冷的(SL(1) ( ))
节点(1)的SL 证实中的IN 和OUT 表为空，表明它不依赖于任何别的节点中当前的信念或缺少信念。这类节点称为前提。而节点(2)的SL 证实的IN 表中含节点(1)。这说明导致节点(2)可信任结论的推理链依赖于当前在节点(1)的信念。如果在将来某个时刻，TMS 除掉了节点(2)的前提节点(1)，那么，由于节点(2)失去了依据，因而也要从IN 表中除去。
综上所述，TMS 的推理与直接的谓词逻辑系统相类似，除了它能撤消前提并对数据库的其余部分作适当的修改外，其余很相似。如果一个SL 证实的OUT 表不是空的，TMS 也能处理缺省推理，如：
(1) 现在是冬天(SL( ) ( ))
(2) 天气是寒冷的(SL(1) (3))
(3) 天气是温暖的
若节点(1)是IN ，节点(3)是OUT ，节点2才为IN 。这个证实实际上是说：“如果现在是冬天，又没有天气是温暖的证据，则结论为：天气是寒冷的”。如果在将来某一时刻，出现了天气是温暖的证据(即为节点(3)提供了一个证实) ，那么TMS 将使节点(2)变为OUT ，因为它不再有一个有效的证实。像节点(2)这样的节点(它们为IN 是根据一个含有非空OUT 表的SL 证实) 被称为假设。本例再次说明有必要存贮节点，甚至存贮那些为OUT 的节点。节点
(3)为OUT 构成节点(2)之证实的一部分。但如果节点(3)不存在，就不能这样表示。值得注意的是，TMS 本身并不产生证实。节点(2)的证实来自冬季一般天气是寒冷的这样一个领域的知识。由此，这个证实必须由使用TMS 的问题求解程序提供。TMS 能作的仅是利用证实来维持一个相容的信念数据库。
2. 条件证明(Condition Prove)
条件证明(CP)的证实表示有前提的论点。无论何时，只要在IN 假设中的节点为IN ，OUT 假设中的节点为OUT ，则结论节点往往为IN 。于是，条件证明的证实有效。处理CP 比SL 更难。事实上，TMS 是通过把它们转换成SL 证实来进行处理的。
TMS 将显式证实与当前相信为真(即在IN 表上) 的命题一起存贮。当查出不相容时，它只消除必须删去者。如前所述，此过程称为面向从属关系的回溯。我们仍用安排会议的问题来说明它如何工作。
说明如下：设从节点(1)、(2)开始，
(1) 日期(会议)=星期三(SL( ) (2))
(2) 日期(会议)≠星期三
目前没有相信“开会日期不应是星期三”的证实，所以节点1是IN 以表示日期为星期三这一假设。
经某些推理后，安排会议系统得出会议必须在下午2∶00举行的结论，这是根据若干节点得出来的。这样一来，有如下节点：
(1) 日期(会议)=星期三(SL( )(2))
(2) 日期(会议)≠星期三
(3) 时刻(会议)=14∶00(SL(57，103，45) ( ))
节点(1)、(3)在IN ，节点(2)在OUT 。现在，安排会议的程序要找一间房子，结果发现星期三下午两点钟无空房可供会议使用。于是通过产生下一节点来告诉TMS ：
(4) 矛盾(SL(1，3) ( ))
这时，调用面向从属关系的回溯过程。它查看矛盾节点的SL 证实中的节点，比如说A1…Ak，然后向后跟踪，通过Ai 的SL 证实中的节点，比如说B1…Bs，再回到B 的SL 证
实中的节点，继续寻找假设，试图找到这样一个假设集，只要除去该集中一个假设，矛盾就可消除。
在此例中，这个集只包含一个元素，即节点(1)，回溯机制通过产生一个不相容节点来记录它，不相容节点表示不相容的假设集。于是得到下面的节点集：
(1) 日期(会议)=星期三(SL( ) (2))
(2) 日期(会议)≠星期三
(3) 时间(会议)=14∶00(SL(57，103，45) ( ))
(4) 矛盾(SL(1，3) ( ))
(5) 不相容N-1(CP4(1，3) ( ))
在TMS 选择不相容假设中的一个(这里只有节点(1)，所以选择是简单的事) ，并且通过使节点(1)的OUT 表中的一个节点变为IN 来使节点(1)变为OUT 。(因为一切假设都有非空的OUT 表，所以可以这样作) 。本例中又只有一个节点能使其为IN 。使节点(2)为IN 的方法就为节点(2)提供了一个以不相容节点为根据的证实。于是，我们现在有：
(1) 日期(会议)=星期三(SL( ) (2))
(2) 日期(会议)≠星期三(SL(5) ( ))
(3) 时间(会议)=14∶00(SL(57，103，45) ( ))
(4) 矛盾(SL(1，3) ( ))
(5) 不相容N-1(CP4(1，3) ( ))
节点(2)与节点(5)为IN ，就引起节点(1)为OUT ，因为节点(1)的证实依赖于节点(2)是OUT 。节点(4)现在也变成OUT 。这样一来，矛盾就消除了，可选择一个新的日期。由于矛盾中不包含时间，所以仍保持下午2∶00不变。
第八章 不确定知识的表示与推理
教学目的：对不确定知识的表示方法及推理技术。
教学重点和难点：1. 随机性知识的表示、模糊性知识的表示、模糊集合与模糊逻辑和多值逻辑；2. 不确定性推理的一般模式；3. 基于证据理论的不确定性推理；难点：模糊集合与模糊逻辑和模糊性知识的表示。
主要教学内容及要求：
了解：不确定性推理的一般模式
理解：不确定性推理方式
掌握：随机性知识的表示、模糊性知识的表示、模糊集合与模糊逻辑和多值逻辑；基于证据理论的不确定性推理。
熟练掌握：主观Bayes 方法及其推理方法
对于许多比较复杂的人工智能系统，往往含有复杂性、不完全性、模糊性或不确定性。当采用产生式系统或专家系统的结构时，要求设计者建立某种不确定性问题的代数模型及其计算和推理过程。为此，下面我们将和大家一起讨论一些常用的不确定性推理方法。
8.1 概率推理
基于概率论的不确定性推理有很多种，在这里我们仅讨论比较成熟的一种推理方法──主观Bayes 方法。
1.Bayes 公式及主观Bayes 方法
主观Bayes 方法是R.O.Duda 、P.E.Hart 等人1976年在Bayes 公式的基础上经适当改进提出了主观Bayes 方法，它是最早用于处理不确定性推理的方法之一，已在地矿勘探专家系统PROSPECTOR 中得到了成功的应用。下面我们先来介绍Bayes 公式。
若有诸事件A 1,A 2,…，A n ，彼此独立，且B 为事件A 1＋A 2＋…＋A n 的子事件，P (A i )>0(i=1,2,…,n) ，P (B )>0，那么Bayes 公式可表示为：
式中，为先验概率；为后验概率。Bayes 公式就是从先验概率推导出后验概率的公式。为阐明主观Bayes 方法，先引入几个概念：
(1) 几率函数
几率函数定义为
它表示x 的出现概率与不出现概率之比，显然随P (x ) 的加大(x ) 也加大，而且
当P(x)=0时，有(x ) ＝ 0
当P(x)=1时，有(x ) ＝∞
于是，取值于[0,1]的P (x ) 被放大为取值于[0, ∞]的(x ) 。
(2) 充分性度量
充分性度量定义为
它表示E 对H 的支持程度，取值于[0, ∞],由专家给出。
(3) 必要性度量
必要性度量定义为
它表示 对Ｈ的支持程度，即E 对H 为真的必要性程度，取值范围为[0,+∞]，也是由专家凭经验给出。
2. 证据的不确定性描述
在主观Bayes 方法中，证据的不确定性也是用概率表示的。在PROSPECTOR 中，由于根据观察S 直接求出P(E/S)非常困难，所以它采用了一种变通的方法，即引进了可信度C(E/S)的概念，用户可根据实际情况在[-5,5]中选取一个整数作为初始证据的可信度。可信度C(E/S)与概率P(E/S)的对应关系可用下式表示：
特别地， C(E/S)=-5，表示在观察S 下证据E 肯定不存在，即P(E/S)=0； C(E/S)=0 ，表示在观察S 与证据E 无关，即P(E/S)=P(E)； C(E/S)=5 ，表示在观察S 下证据E 肯定存在，即P(E/S)=1。 这样，用户只要对证据E 给出在观察S 下的可信度C(E/S)，系统即可求出相应的P(E/S)。 对于组合证据
E ＝E 1 AND E2AND …AND En
则
P(E/S)＝min{P(E1/S), P(E2/S), …,P(En /S)}
对于组合证据
E ＝E 1 OR E2 OR … OR En
则
P(E/S)＝max{P(E1/S),P(E2/S),…,P(En /S)}
3. 基于主观Bayes 方法的不确定性推理
在主观Bayes 方法中，知识是用产生式规则表示的，具体形式为：
IF E THEN (LS,LN) H (P(H))
LS,LN 在上文已有定义，P(H)是专家给出的先验概率。推理就由P(H)，P(E)，LS 和LN 求出
的过程。而一条规则的前项有可能肯定存在，也可能肯定不存在，或者不确定，而且在不同情况下求解后验概率的方法亦不相同，以下分别予以讨论。
(1)证据E 确定必出现时，即P(E)=P(E/S)=1，由Bayes 公式，
由以上两式可得，
即有，
若需要以概率的形式表示，再由公式
计算出
这就是把先验概率P (H ) 更新为后验概率P(H/E)的计算公式。
(2)证据E 确定必不出现时，即P(E)=P(E/S) = 0，采用和上述类似的方法可得
从而
这就是把先验概率P(H)更新为后验概率
(3) 当证据E 不确定时，即
的计算公式。
就不能用上面的公式计算后验概率，可用Duda 于1976年给出的公式
来计算出后验概率。这分为四种情况：
① 当
故
这就是证据肯定存在的情况。
② 当
故有
这就是证据肯定不存在的情况。
③ 当时，Ｅ与Ｓ无关，利用全概率公式有，
④ 当即
为其它值时，通过分段线性插值的方法，就可以得到计算的公式，
该公式称为EH 公式。
对于初始证据，由于其不确定性是用可信度给出，此时只要把计算与的公式：
的对应关系转换公式代入EH 公式，就可以得到用可信度
该公式称为CP 公式。
这样，当用初始证据进行推理时，根据用户告知的通过运用CP
公式就可以求出
当用推理过程中得到的中间结论作为证据进行推理时，通过运用EH
公式就可求出
4. 结论不确定性的合成算法
若有n 条规则都支持相同的结论，而且每条规则的前提条件所对应的证据Ｅi （i = 1,2,…,n）都有相应的观察S i 与之对应，此时只要先对每条规则分别求出
主观Bayes 方法是在概率论的基础上发展起来的，具有较完善的理论基础，且知识的输入转化为对LS 和LN 的赋值，这就避免大量的数据统计工作，是一种比较实用且较灵活的不确定性推理方法。但是，它在要求专家给出LS 和LN 的同时，还要求给出先验概率
P (H ) ，而且要求事件间相互独立，这仍然比较困难，从页也就限制了它的应用。
8.2 贝叶斯网络
贝叶斯网络亦称信念网络(Belief Network)，于是1985年由Judea Pearl首先提出。它是一种模拟人类推过程中因果关系的不确定性处理模型，其网络拓朴结构是一个有向无环图(DAG)。它的节点用随机变量或命题来标识，认为有直接关系的命题或变量则用弧来连接。例如，假设结点E 直接影响到结点H ，即E→H，则建立结点E 到结点H 的有向弧(E,H)，权值(即连接强度) 用条件概率P(H/E)来表示，如图4.19所示：
图8.1 有两个结点的贝叶斯网络示意图
图 8.2 有6个节点的贝叶斯网络
一般来说，有n 个命题x 1,x 2,,x n 之间相互关系的一般知识可用联合概率分布来描述。但是，这样处理使得问题过于复杂。Pearl 认为人类在推理过程中，知识并不是以联合概率分布形表现的，而是以变量之间的相关性和条件相关性表现的，即可以用条件概率表示。如
例如，对如图4.20所示的贝叶斯网络，
有
一旦命题之间的相关性由有向弧表示，条件概率由弧的权值来表示，则命题之间静态结构关系的有关知识就表示出来了。
当获取某个新的证据事实时，要对每个命题的可能取值加以综合考查，进而对每个结点定义一个信任度，记作Bel(x)。可规定
Bel(x) = P(x=xi / D)
来表示当前所具有的所有事实和证据D 条件下，命题x 取值为x i 的可信任程度，然后再基于Bel 计算的证据和事实下各命题的可信任程度。
8.3 模糊逻辑推理与可能性理论
模糊推理与前面几节讨论的不确定性推理有着实质性的区别。前面那几种不确定性推理的理论基础是概率论，它所研究的事件本身有明确而确定的含义，只是由于发生的条件不充分，使得在条件与事件之间不能出现确定的因果关系，从而在事件的出现与否上表现出不确
定性，那些推理模型是对这种不确定性，即随机性的表示与处理。模糊推理的理论基础是模糊集理论以及在此基础上发展起来的模糊逻辑，它所处理的事物自身是模糊的，概念本身没有明确的外延，一个对象是否符合这个概念难以明确地确定模糊推理是对这种不确定性，即模糊性的表示与处理。
1. 模糊逻辑推理
模糊逻辑推理是基于模糊性知识(模糊规则) 的一种近似推理，一般采用Zadeh 提出的语言变量、语言值、模糊集和模糊关系合成的方法进行推理。
(1) 语言变量
语言变量一般用来描述那些不精确的事件或现象，就是我们通常所说的属性名，例如“年纪”就是一个语言变量，其取值可为“老”、“中”、“青”等。这些值可看成是论域U=[0, 150]上模糊子集的标名，而数字变量u ∈[0, 150]称为基变量。
(2) 证据模糊性及模糊规则的表示
命题的模糊性可用模糊子集来描述，例如设有命题“张三比较小”，则可以表示为
其中＝“比较小”=1/1+1/2+0.5/3+0.2/4+0.1/5+0/6=(1,1,0.5,0.2,0.1,0) 是一个模糊子集，代表“比较小”这个模糊概念。
一条模糊规则实际上是刻划了其前件中的模糊集与结论中的模糊集之间的一种对应关系。Zadeh 认为，这种对应关系是两个集合间的一种模糊关系，因而它也可以表示为模糊集合。特别地，对于有限集，则这个模糊集合就可以表示为一个模糊矩阵。例如有规则
其中，都是模糊子集，表示模糊概念。这个规则就表示了也可以表示为一个模糊子集。于是， 之间的一种模糊关系，表示这模糊关系，则
其中，U 、V 分别为模糊集合
对于的隶属度。
，Zadeh 给出了一种方法：
＝
其中、分别代表取最小值和取量大值，即min 、max 。如果所属的论域，是元素 为求得隶属度 都是有限集，则就是一个矩阵。
这样，一条模糊规则就可以用隶属度刻划的模糊集合来描述。
(3) 模糊推理
模糊推理有很多种，在这里我们仅介绍一种简单而常用的方法，如需要更深一步的研究，可参考其它有关书籍。
模糊推理可以通过模糊关系的合成来进行。假设有规则
：
其推理模式为
=
=
其中，
一般情况下，n=1。
这样， 就是规则R 按上述方法导出模糊集合，而就是所推的结论。当然，它仍是一个模糊集合。如果需要，可再将它翻译为自然语言的形式。
2. 可能性理论
Zadeh 1965年提出了模糊集合论，在此基础上1978年又建立了可能性理论，并将不确定性理解为可能性。在本节，我们简单介绍一下可能性理论，欲想进行一步的了解可参考有关文献。
假设U 为一论域，x 是取值于U 上模糊变量，是U 上的一个模糊子集。那么对于模糊命题“x is
赋值
= ”就可以导出一个等于的可性分布。这样，
“x is ”可变成一个可能性
它用来定义在U 中取任何可能值的可能性。例如，令U 表示人，对于“x比较小”这一模糊命题可表示为
“”。其中x U ， = "比较小" = 1/1 + 1/2 + 0.5/3 + 0.2/4 + 0.1/5 + 0/6 = (1,1,0.5,0.2,0.1,0),那么这一命题就以导出如下的可性分布：
POSS {x =1}=1
POSS {x =2}=1
POSS {x =3}=0.5
POSS {x =4}=0.2
POSS {x =5}=0.1
POSS {x =6}=0
另外，还规定
POSS (x =a ∧x =b )= min {poss (x =a ), poss (x =b )}
POSS (x =a ∨x =b )= max {POSS (x =a ), POSS (x =b )}
POSS (x a )=1－POSS (x =a )
综上所述, x 的可能性分布本质上就是一个模糊子集。因此，可能性分布与模糊集合的表现形式是一致的，所以我们可以用模糊集合的一些运算规则对可能性分布进行操作。总之，果如以可能性来度量不确定性，则我们就可运用可能性理论来讨论不确定性推了。
8.4 缺省推理
1．引言
建立在谓词逻辑基础上的传统系统是单调的，其意思是：已知为真的命题数目随时间而严格增加。那是由于新的命题可加入系统，新的定理可被证明，但这种加入和被证明决不会导致前面已知为真或已被证明的命题变成无效。这种系统具有以下优点：
(1) 当加入一新命题时，不必检查新命题与原有知识间的不相容性。
(2) 对每一个已被证明了的命题，不必保留一个命题表。它的证明以该命题表中的命题为根据，因为不存在那些命题会被取消的危险。
可是，这种单调系统不能很好地处理常常出现在现实问题领域中的3类情况，即不完全的信息、不断变化的情况、以及求解复杂问题过程中生成的假设。
很少有能在处理过程中拥有它所需要的一切信息的系统。但当缺乏信息时，只要不出现相反的证据，就可以作一些有益的猜想。构造这种猜想称为缺省推理(default reasoning)。例如，假设当你去朋友家吃晚饭，并经过路旁的卖花亭时，对于“你的主人喜欢花吗?”这样一个问题，你可能没有任何具体信息可作为回答问题的依据。但若利用一般的规则——因为大多数人们喜欢花，假定这个具体的人也喜欢，除非有相反的证据(如对花过敏) ，那么，你可作出决定。这类缺省推理是非单调的(即加进一条信息就可能迫使取消另一条信息) ，因为用这种方式推导出来的命题是依赖于在某个命题中缺少某种信念，即如果前面那些缺省的命题一旦加入系统，就必须消除用缺省推理产生的命题。这样一来，如果你拿着花走到门口时，你的主人立刻打喷嚏，你就应取消以前的信念——你的主人喜欢花。当然，你也必须取消建立在已被取消的信念基础上的任何信念。
上述举例说明了一个普通类型的缺省推理，称为最可能选择。如果知道一些事情中的某件事必为真，在缺乏完全知识条件下，应选最可能的那个。如：大多数人喜欢花；大多数狗有尾巴；对瑞典人而言，最一般的头发颜色为淡黄色。另一重要类型的缺省推理是约束推理(circumscription)在这种推理中只有当能证明某些对象满足性质P 时，才认为它们满足性质P 。例如，设需求解的问题是划船过河，可能列举许多妨碍成功过河的因素，如没有船桨，船漏水，船搁浅在泥沙中等等。而重要的是，问题求解程序不必去证明这些条件不是真的(因为可能问题本身的说明根本没提到船桨) 。程序能作的是，假定只有那些能够清楚地被证明为真的事情才是真的(希望没一个为真) ，否则不为真。那时，程序才能往前进行并假定能使用船。
2．定义
一个既精确又可算的缺省推理的描述，必涉及结论Y 且缺少某一信息X 。所以缺省推理的定义为：
缺省推理的定义1：如果X 不知道，那么得结论Y 。
但在所有的系统中，除最简单的系统外，只有存贮在数据库中的事件的极小部分可看成是已知的。不过，通过各种努力，事件的其余部分可从已知部分推导出来。所以缺省推理的定义更像是：
缺省推理的定义2：如果X 不能被证明，那么得结论Y 。
但是，如果仍然以谓词逻辑工作，那怎么能知道X 不能被证明? 由于这系统是不可判定的，所以对任一X 来说，仍不能担保它能否被证明。于是我们不得不重新考虑定义： 缺省推理的定义3：如果X 不能在某个给定的时间内被证明，那么得结论Y 。
值得注意，定义推出结论Y 的推理过程依赖于逻辑领域外的某些事件，在规定时间内可作多少计算，以及在寻找待求的证明中计算是否有效。因此作出关于系统行为的形式说明就显得特别重要。加之，我们丧失了谓词逻辑所具有的对所提出的证明的正确性进行验证的能力，即使一个证明存在，也不一定能保证找到它。假如现在得到一证明，对证明过程中的某一步来说，由于没有能力证明X ，所以得结论Y 。但由于X 是否可被证明是不可判定的，因而包含这个证明在内的更大的证明也就不可判定。于是，由于缺乏完全的知识，对缺省推理的需要迫使我们使用这样的系统，它的行为不易形式地描述出来。
即使有幸获得了关于某一情况的完全知识，也不能由此而长时间使用它，因为客观世界在迅速地变化着。这意味着在一个时刻完全精确的说明不会是持久的。这就是框架问题，一种引入状态变量对它进行处理的方法，已在第2.5节介绍过。但这种方法不很完善，因为只要状态中各谓词为真，它就要对每个状态作单独的描述。于是得花很多精力来重复地说明一个缓慢变化的事实。而且，凡每一操作执行后，就得引进一新状态，因此很难发现若干个操作序列已导致同一情况。另一种求解不断变化的世界问题的方法，是取消那些不能再精确描述世界的命题，而代之以另一些更精确的命题。这又使其变成了非单调系统。在这类系统中，命题既可从知识库中删去，也可加入。而且当一个命题被取消后，其证明依赖于这个被取消命题的其它命题也应取消。
即使供某一系统采用的知识不存在上述两个问题，一个好的问题求解系统在问题求解过程中，也可能产生某些非单调行为的知识。假若要编一程序来求解一个极简单的问题，例如找一适当时间使3个忙人能同时参加会议。一个办法是首先假设会议在某个具体日期举行，比如星期三，并将关于此假设的命题放入数据库中，再从3个人的时间安排表中检查不相容性。如果出现冲突，就表示假设的命题必须取消，而代之以另一个希望不矛盾的命题。当然，任何依赖于这个被取消命题而建立起来的命题也必须取消。于是又得到一个非单调系统。 当然，这种情况可用带回溯的直
接树搜索来处理。一切假设和由假设
得出的推论，均记录在产生它们的搜
索树的结点上。当产生一个不相容时，
只需回溯到尚未探索过的路径的一个
结点上。这时原假设和它们的推论将
自动消失。这种回溯方法如图4.22所
示。
它显示出一个安排会议程序的搜
索树的一部分。为此，程序必须求解
一个约束满足问题，即找出每个参加
者都有空闲的开会日期与时刻，并有
可供开会的房间。 图 8.3 非面向从属关系的回溯
求解该问题时，系统必须试图在一个时刻满足一个约束。最初，几乎没有根据可以肯定哪个时间最好，所以随意确定为星期三。于是产生一个新的约束，解的其余部分必须满足会议在星期三举行的假设，且存放在所产生的结点上。接着，程序试图选择一个时刻，使之适合于所有参加者。在他们的工作时间表中，通常白天的会议时刻可能在除14∶00外的任意时刻，所以选择14∶00作为开会时间，至于在哪一天倒没关系。然而，程序发现在星期三无房间可供开会使用。所以它回溯穿过结点(假设星期三的结点) ，并改在另一天，比如星期
二。现在就必须复制导出时刻为14∶00的推理链，因为它回溯到选日期时，原推理链已经消失，尽管该时刻推理未依靠任何关于日期为星期三的假设。
如果按照搜索过程产生命题的次序去取消命题，而不是按照该命题内涵的不相容性去取消命题，那么将会产生很大的浪费。最好是在需要时既能直接将假设插入到数据库，又能取消它们。这种方式称为面向从属关系的回溯。
基于下述一些原因中的任何一个，都可察觉非单调推理系统的必要性：
(1) 不完全知识的出现要求缺省推理。
(2) 一个不断变化的世界必须用适应不断变化的数据库来描述。
(3) 产生一个问题的完全解可能要求关于部分解的暂时的假设。
3. 非单调推理系统
正确性维持系统(Truth Maintenane System,TMS)是一个已经实现了的非单调推理系统。它用以协助其它推理程序维持系统的正确性，所以它的作用不是生成新的推理，而是在其它程序所产生的命题之间保持相容性。一旦发现某个不相容，它就调出自己的推理机制，面向从属关系的回溯，并通过修改最小的信念集来消除不相容。
在TMS 中，每一命题或规则均称为节点，且对任一节点，以下两种状态必居其一： IN 相信为真
OUT 不相信为真，或无理由相信为真，或当前没有可相信的理由。
每个节点附有一证实表，表中每一项表示一种确定节点有效性的方法。IN 节点是指那些至少有一个在当前说来是有效证实的节点。OUT 结点则指那些当前无任何有效证实的节点。也许有人想知道为什么要不厌其烦地保留OUT 结点? 当然，花许多功夫去产生一些表示不正确命题的节点是没有意义的。但必须记住，在非单调推理系统中，产生一节点是以表示一个假定为真的命题，例如，使用缺省推理的结果。这时其余节点则在假设原始节点为IN 的基础上产生。
但新信息的出现可能引起原始节点变成OUT(缺少信息时用缺省推理) ，那时，一切基于它的节点都相应要变为OUT 。不过，保留这些节点和它们的相互依赖性仍有用处。因为一旦有效信息发生了变化，而且引起原始节点再变为IN 时，那些在它的基础上用来产生其它节点的推理就不必重作了。于是，当原始节点再变为IN 时，其它各个节点的某个基于原始节点的证实将随之变为有效，这些节点也就变为IN 了。
在系统中，有两种方式可用来证实一个节点的有效性可依赖于其它节点的有效性：
(1) 支持表(SL(IN 节点)(OUT 节点))
(2) 条件证明(CP(结论)
(IN 假设)
(OUT 假设))
1. 支持表(Support List)
支持表最通用。如果在IN 节点表中提到的节点当前都是IN ，且在OUT 节点表中提到的节点当前都是OUT ，那么，它们是有效的。例如，下述节点：
(1)现在是冬天(SL( ) ( ))
(2)天气是寒冷的(SL(1) ( ))
节点(1)的SL 证实中的IN 和OUT 表为空，表明它不依赖于任何别的节点中当前的信念或缺少信念。这类节点称为前提。而节点(2)的SL 证实的IN 表中含节点(1)。这说明导致节点(2)可信任结论的推理链依赖于当前在节点(1)的信念。如果在将来某个时刻，TMS 除掉了节点(2)的前提节点(1)，那么，由于节点(2)失去了依据，因而也要从IN 表中除去。
综上所述，TMS 的推理与直接的谓词逻辑系统相类似，除了它能撤消前提并对数据库的其余部分作适当的修改外，其余很相似。如果一个SL 证实的OUT 表不是空的，TMS 也能处理缺省推理，如：
(1) 现在是冬天(SL( ) ( ))
(2) 天气是寒冷的(SL(1) (3))
(3) 天气是温暖的
若节点(1)是IN ，节点(3)是OUT ，节点2才为IN 。这个证实实际上是说：“如果现在是冬天，又没有天气是温暖的证据，则结论为：天气是寒冷的”。如果在将来某一时刻，出现了天气是温暖的证据(即为节点(3)提供了一个证实) ，那么TMS 将使节点(2)变为OUT ，因为它不再有一个有效的证实。像节点(2)这样的节点(它们为IN 是根据一个含有非空OUT 表的SL 证实) 被称为假设。本例再次说明有必要存贮节点，甚至存贮那些为OUT 的节点。节点
(3)为OUT 构成节点(2)之证实的一部分。但如果节点(3)不存在，就不能这样表示。值得注意的是，TMS 本身并不产生证实。节点(2)的证实来自冬季一般天气是寒冷的这样一个领域的知识。由此，这个证实必须由使用TMS 的问题求解程序提供。TMS 能作的仅是利用证实来维持一个相容的信念数据库。
2. 条件证明(Condition Prove)
条件证明(CP)的证实表示有前提的论点。无论何时，只要在IN 假设中的节点为IN ，OUT 假设中的节点为OUT ，则结论节点往往为IN 。于是，条件证明的证实有效。处理CP 比SL 更难。事实上，TMS 是通过把它们转换成SL 证实来进行处理的。
TMS 将显式证实与当前相信为真(即在IN 表上) 的命题一起存贮。当查出不相容时，它只消除必须删去者。如前所述，此过程称为面向从属关系的回溯。我们仍用安排会议的问题来说明它如何工作。
说明如下：设从节点(1)、(2)开始，
(1) 日期(会议)=星期三(SL( ) (2))
(2) 日期(会议)≠星期三
目前没有相信“开会日期不应是星期三”的证实，所以节点1是IN 以表示日期为星期三这一假设。
经某些推理后，安排会议系统得出会议必须在下午2∶00举行的结论，这是根据若干节点得出来的。这样一来，有如下节点：
(1) 日期(会议)=星期三(SL( )(2))
(2) 日期(会议)≠星期三
(3) 时刻(会议)=14∶00(SL(57，103，45) ( ))
节点(1)、(3)在IN ，节点(2)在OUT 。现在，安排会议的程序要找一间房子，结果发现星期三下午两点钟无空房可供会议使用。于是通过产生下一节点来告诉TMS ：
(4) 矛盾(SL(1，3) ( ))
这时，调用面向从属关系的回溯过程。它查看矛盾节点的SL 证实中的节点，比如说A1…Ak，然后向后跟踪，通过Ai 的SL 证实中的节点，比如说B1…Bs，再回到B 的SL 证
实中的节点，继续寻找假设，试图找到这样一个假设集，只要除去该集中一个假设，矛盾就可消除。
在此例中，这个集只包含一个元素，即节点(1)，回溯机制通过产生一个不相容节点来记录它，不相容节点表示不相容的假设集。于是得到下面的节点集：
(1) 日期(会议)=星期三(SL( ) (2))
(2) 日期(会议)≠星期三
(3) 时间(会议)=14∶00(SL(57，103，45) ( ))
(4) 矛盾(SL(1，3) ( ))
(5) 不相容N-1(CP4(1，3) ( ))
在TMS 选择不相容假设中的一个(这里只有节点(1)，所以选择是简单的事) ，并且通过使节点(1)的OUT 表中的一个节点变为IN 来使节点(1)变为OUT 。(因为一切假设都有非空的OUT 表，所以可以这样作) 。本例中又只有一个节点能使其为IN 。使节点(2)为IN 的方法就为节点(2)提供了一个以不相容节点为根据的证实。于是，我们现在有：
(1) 日期(会议)=星期三(SL( ) (2))
(2) 日期(会议)≠星期三(SL(5) ( ))
(3) 时间(会议)=14∶00(SL(57，103，45) ( ))
(4) 矛盾(SL(1，3) ( ))
(5) 不相容N-1(CP4(1，3) ( ))
节点(2)与节点(5)为IN ，就引起节点(1)为OUT ，因为节点(1)的证实依赖于节点(2)是OUT 。节点(4)现在也变成OUT 。这样一来，矛盾就消除了，可选择一个新的日期。由于矛盾中不包含时间，所以仍保持下午2∶00不变。