《人工智能导论》课件 第3章 推理方法

第3章推理方法《人工智能》学习要点逻辑推理概述自然演绎推理归结演绎推理基于可信度的推理基于证据理论推理模糊推理

逻辑推理概述《人工智能》学习要点推理的定义推理的方式及分类推理的控制策略推理的定义从已知事实出发，通过运用已掌握的知识，找出其中蕴涵的事实，或归纳出新的事实。从初始证据出发，按某种策略不断运用知识库中的已知知识，逐步推出结论。例：医疗诊断专家系统初始证据：病人的症状、化验结果知识：专家经验、医学常识初始证据已知事实结论推理推理方式及其分类推理方式及其分类推出结论的途径演绎推理归纳推理默认推理知识确定性确定性推理不确定性推理中间结论与目标距离单调推理非单调推理是否运用启发知识启发式推理非启发式推理推理方式及其分类从推出结论的途径划分：演绎推理：从全称到单称，从一般到个别，常用三段论。大前提，如：足球运动员的身体都是强壮的小前提，如：高波是足球运动员结论，如：高波的身体是强壮的归纳推理：从足够多的个体归纳出一般性的结论，从个别到一般。完全归纳，如：检测全部产品合格该厂产品合格不完全归纳，如：检测全部样品合格该厂产品合格默认推理：知识不完全的情况下，默认某个条件成立进行的推理。A成立，B未知（默认B成立）结论推理方式及其分类从推出结论的途径划分：按所用知识的确定性划分：确定性推理：推理时所用的知识与证据都是确定的，推出的结论也是确定的，

其值或者为真，或者为假。自然演绎推理归结演绎推理与/或形演绎推理不确定性推理：推理时所用的知识与证据不都是确定的，推出的结论也是不确定的。似然推理（概率论）模糊推理（模糊逻辑）推理方式及其分类从推出结论的途径划分：按所用知识的确定性划分：按中间结论是否越来越接近最终目标划分：单调推理：随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。基于经典逻辑的演绎推理非单调推理：由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前面的某一步，重新开始。默认推理X：鸟→X：会飞→X:企鹅X：鸟→X：不会飞→推理方式及其分类从推出结论的途径划分：按所用知识的确定性划分：按中间结论是否越来越接近最终目标划分：按推理中是否运用启发性知识划分：启发式推理启发性知识：与问题有关且能加快推理过程、提高搜索效率的知识。非启发式推理推理控制策略推理控制策略方向控制正向推理逆向推理混合推理双向推理求解策略求一个解求所有解求最优解限制策略深度限制宽度限制时间限制空间限制冲突消解策略按针对性排序按新鲜性排序按匹配度排序按条件数排序搜索策略广度优先深度优先启发式

搜索推理的控制策略:如何使用领域知识使推理过程尽快达到目标的策略。推理的方向正向推理：已知事实结论算法：初始已知事实送入数据库DB。检查DB中是否包含问题的解；有，求解结束，成功退出；无，执行下一步。根据DB中的事实扫描知识库KB，检查KB中是否有可适用的知识；

有，转4；无，转6。把KB中所有适用知识选出来，构成可适用知识集KS，转下一步。若KS非空，按某个策略选出一条知识进行推理，推出的新事实加入DB中，转2；若KS为空，转6。询问用户是否补充新事实；有，补充事实加入DB，转3；无，解不出，失败退出。需解决的问题：匹配的方法，知识库搜索策略，冲突消解策略特点：简单，易实现；目的性不强，效率低。推理的方向正向推理：已知事实结论逆向推理：从某个假设目标出发算法：提出要求证目标（假设）。检查该目标是否在数据库DB中；若在，退出推理或进行下一个假设进行验证；否则，执行下一步。判断目标是否是证据；若是，将其加入DB；否则，执行下一步。找出知识库KB中所有能导出该目标的知识，构成可适用知识集KS，转下一步。从KS中按某个策略选出一条知识，将该知识的条件作为新假设，转2。需解决的问题：目标是否是证据？知识的选择策略？一条知识的运用条件一般都有多个，当其中的一个经验证成立后，如何自动地换为对另一个的验证？特点：目的性强，可解释；起始目标不宜选择，复杂。推理的方向正向推理：已知事实结论逆向推理：从某个假设目标出发混合推理：先正向后逆向：先进行正向推理，帮助选择某个目标，即从已知事实演绎出部分结果，然后再用逆向推理证实该目标或提高其可信度。先逆向后正向：先假设一个目标进行逆向推理，然后再利用逆向推理中得到的信息进行正向推理，以推出更多的结论。双向推理：正向推理与逆向推理同时进行，且在推理过程中的某一步骤上“碰头”的一种推理。冲突消解策略推理过程中事实与知识的匹配情况：恰好有一条匹配成功；无可匹配的知识；多条匹配成功(一对多、多对一、多对多)—需要冲突消解。冲突消解策略按针对性排序按已知事实的新鲜性排序按匹配度排序按条件个数排序

自然演绎推理《人工智能》学习要点推理与推理模式演绎推理基本形式假言推理直言三段论推理方法推理：属于形式逻辑，是从已知的前提经推导获得结论的过程例如“天下雨了，地上湿漉漉的。”推理模式：

演绎推理：从一般性推导出特殊性（数学家的方法）

归纳推理：从特殊性归纳出一般性（科学家的方法）溯因推理：借由结论和规则来支援前提以解释结论（侦探家的方法）

类比推理：从一个特殊性推断出另一特殊性（近似归纳推理）数学归纳法属于演绎推理还是

归纳推理？三大推理模式演绎推理归纳推理溯因推理规则(rule)-情况(case)-结果(result)豆子实例自然演绎推理

演绎推理的基本形式简单论证形式：肯定前件：(p→q)∧p⇒q（）如果有火灾，就会有浓烟。有火灾。因此，有浓烟。（）否定后件：(p→q)∧¬q⇒¬p（）如果有火灾，就会有浓烟。没有浓烟。因此，没有火灾。（）肯定后件：(p→q)∧q⇒p（

）如果有火灾，就会有浓烟。有浓烟。因此，有火灾。（

）否定前件：(p→q)∧¬p⇒¬q（

）如果有火灾，就会有浓烟。没有火灾。因此，没有浓烟。（

）演绎推理的基本形式三段论证形式：假言三段论：(p→q)∧(q→r)⇒(p→r)如果我不能起床，则我不能上班。如果我不能上班，则我不能得到报酬。所以，如果我不能起床，则我不能得到报酬。选言三段论：(p∨q)∧¬p⇒q要么小王赢要么小张赢。小王没有赢。所以，小张赢了。直言三段论：大前提：所有M是P。小前提：所有S是M。结论：所有S是P。所有生物都会死。所有人都是生物。所以，所有人都会死。推理方法

推理方法例1：因为中国的大学都施行校长负责制，而陕西理工大学也是中国的大学，所以陕西理工大学也是由校长负责的。例2：因为中国的大学分布在全各国各地，而陕西理工大学也是中国的大学，所以陕西理工大学也分布在全各国各地。大前提：正确小前提：正确结论：错误大前提：正确小前提：正确结论：正确自然演绎推理例，已知事实：（1）凡是容易的课程小王（Wang）都喜欢；（2）C班的课程都是容易的；（3）ds是C班的一门课程。求证：小王喜欢ds这门课程。应用推理规则进行推理：(

x)(EASY(x)→LIKE(Wang,x))

EASY(z)→LIKE(Wang,z)全称固化(

x)(C(x)→EASY(x))

C(y)→EASY(y)全称固化所以

C(ds),C(y)→EASY(y)

EASY(ds)P规则及假言推理

所以EASY(ds),EASY(z)→LIKE(Wang,z)

LIKE(Wang,ds)T规则及假言推理证明：定义谓词：EASY(x)：x是容易的；LIKE(x,y)：x喜欢y；C(x)：x是C班的一门课程。已知事实和结论用谓词公式表示：

(

x)(EASY(x)→LIKE(Wang,x))(

x)(C(x))→EASY(x))C(ds)

?LIKE(Wang,ds)自然演绎推理优点：表达定理证明过程自然，易理解。拥有丰富的推理规则，推理过程灵活。便于嵌入领域启发式知识。缺点：易产生组合爆炸，得到的中间结论一般呈指数形式递增。

归结演绎推理《人工智能》学习要点归结演绎原理谓词公式化为子句集应用归结反演求解问题归结反演推理反证法P

Q，当且仅当P

Q

F，即Q为P的逻辑结论，

当且仅当P

Q是不可满足的。定理Q为P1,P2,

…,

Pn的逻辑结论，当且仅当(P1

P2

…

Pn

)

Q是不可满足的。思路要证明P

Q

P

Q

为矛盾式（永假式）

子句集不可满足

海伯伦定理

鲁宾逊归结原理P

Q≡Q

P逆否命题等价P

Q≡PQ蕴含消除等价归结基本原理将假设的谓词公式转换为合取范式：P

(P

Q)

(﹁P

Q)构造子句集S合取范式形式下的子命题（元素）的集合子句集S：S={P,P

Q,﹁P

Q}消除互补对，得到归结式互补对：C1=P

C1’,

C2=﹁P

C2’,存在互补对P和﹁P归结式：R(C1,C2)=C12=C1’

C2’子句集中添加R(C1,C2)。不断归结，直到子句集有空子句，说明谓词公式为矛盾式，原命题成立。归结反演举例证明公式：(P→Q)→(﹁Q→﹁P)证明：（1）根据归结原理，将待证明公式转化成待归结命题公式：

(P→Q)∧﹁(﹁Q→﹁P)（2）分别将公式前项化为合取范式：

P→Q＝﹁P∨Q

结论求﹁后的后项化为合取范式：

﹁(﹁Q→﹁P)＝﹁(Q∨﹁P)＝﹁Q∧P

两项合并后化为合取范式：

(﹁P∨Q)∧﹁Q∧P（3）则子句集为：

{﹁P∨Q,﹁Q,P}（4）对子句集中的子句进行归结可得： 1.

﹁P∨Q 2.

﹁Q 3.

P 4.

Q， （1，3归结） 5.

NIL （2，4归结）

由上可得原公式成立。谓词公式化为子句集的方法例：(

x)((

y)P(x,y)

(

y)(Q(x,y)

R(x,y)))解：(1)消去谓词公式中的“

”和“

”符号 P→Q

P

Q P

Q

(P

Q)(

P

Q) (

x)(

(

y)P(x,y)

(

y)(

Q(x,y)

R(x,y))) (2)把否定符号

移到紧靠谓词的位置上 (

x)((y)

P(x,y)

(y)(Q(x,y)

R(x,y))) (3)变量标准化，每个量词采用不同的变元 (

x)((y)

P(x,y)

(z)(Q(x,z)

R(x,z)))谓词公式化为子句集的方法例：(

x)((

y)P(x,y)

(

y)(Q(x,y)

R(x,y)))解：(4)消去存在量词a.存在量词不出现在全称量词的辖域内，用常量替换。

b.存在量词出现在一个或者多个全称量词的辖域内，

用一个Skolem函数替换变元，函数的自变量为全称量词的变元。 (

x)(

P(x,f(x))

(Q(x,g(x))

R(x,g(x))) (5)化为前束形，所有全称量词移到公式最左边 (6)化为Skolem标准形 (

x)((

P(x,f(x))

(Q(x,g(x)))

(

P(x,f(x))

R(x,g(x))))谓词公式化为子句集的方法例：(

x)((

y)P(x,y)

(

y)(Q(x,y)

R(x,y)))解：(7)略去全称量词

(

P(x,f(x))

(Q(x,g(x)))

(

P(x,f(x))

R(x,g(x))) (8)消去合取连词，用子句集表示 {

P(x,f(x))

(Q(x,g(x)),

P(x,f(x))

R(x,g(x))} (9)子句集标准化，每个字句的变量符号不一样

P(x,f(x))

(Q(x,g(x)),

P(y,f(y))

R(y,g(y))}归结反演基于反证法，应用归结原理证明定理的过程称为“归结反演”。用归结反演证明的步骤：将已知前提表示为谓词公式F。将待证明的结论表示为谓词公式Q，并否定得到﹁Q

。把谓词公式集{F,﹁Q}化为子句集S。应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入到S中。如此反复进行，若出现了空子句，则停止归结，此时就证明了Q为真。归结反演例

某公司招聘工作人员，A，B，C三人应试，经面试后公司表示如下想法：（1）

三人中至少录取一人。（2）

如果录取A而不录取B，则一定录取C。（3）如果录取B，则一定录取C。求证：公司一定录取C。证明：公司的想法用谓词公式表示为：P(x),录取x。

P(A)

P(B)

P(C)

P(A)

P(B)

P(C)

P(B)

P(C)

把要求证的结论用谓词公式表示出来并否定，

得：

P(C)把上述公式化成字句集：(1)P(A)

P(B)

P(C)

P(A)

P(B)

P(C)

P(B)

P(C)

P(C)归结反演

应用归结反演求解问题归结原理除了定理证明外还可求取问题答案，应用归结原理求解问题的步骤：已知前提F

用谓词公式表示，并化为子句集S

；把待求解的问题Q

用谓词公式表示，并否定Q，再与ANSWER

构成析取式

（﹁Q∨ANSWER

）；把（﹁Q∨ANSWER）化为子句集，并入到子句集S中，得到子句集S’;

对S’应用归结原理进行归结；若得到归结式ANSWER

，则答案就在ANSWER中。归结反演

应用归结反演求解问题

例：已知F1：王（Wang）先生是小李（Li）的老师。 F2：小李与小张（Zhang）是同班同学。 F3：如果x与y是同班同学，则x的老师也是y的老师。

求：小张的老师是谁？

解：定义谓词：

T(x,y):x是y的老师 C(x,y):x与y是同班同学

把已知前提表示成谓词公式： F1：T(Wang,Li) F2：C(Li,Zhang) F3：(

x)(

y)(

z)(C(x,y)

T(z,x)T(z,y))

把目标表示成谓词公式，并把它否定后与

ANSWER析取： G：

(x)T(x,Zhang)ANSWER(x)归结反演

应用归结反演求解问题

例3.11已知F1：王（Wang）先生是小李（Li）的老师。 F2：小李与小张（Zhang）是同班同学。 F3：如果x与y是同班同学，则x的老师也是y的老师。

求：小张的老师是谁？

解：把上述公式化为子句集： (1)T(Wang,Li) (2)C(Li,Zhang) (3)

C(x,y)

T(z,x)T(z,y) (4)

T(u,Zhang)ANSWER(u)

应用归结原理进行归结： (5)

C(Li,y)

T(Wang,y) (1)(3)归结 (6)

C(Li,Zhang)

ANSWER(Wang) (4)(5)归结 (7)ANSWER(Wang) (2)(6)归结小结人工智能的发展历程人工智能的三大学派人工智能发展历史上的大师

基于可信度的不确定性推理《人工智能》学习要点不确定性推理的基本问题C-F模型中的

不确定性表示与量度C-F模型中的证据组合C-F模型中的传递算法C-F模型中结论合成C-F模型应用案例不确定性推理定义推理从已知事实（证据）出发，通过运用相关知识逐步推出结论或者证明某个假设成立或不成立的思维过程。不确定性推理从不确定性的初始证据出发，通过运用不确定性的知识，最终推出具有一定程度的不确定性但却是合理或者近乎合理的结论的思维过程。初始证据已知事实新的事实结论不确定性推理中的基本问题不确定性的表示与量度知识不确定性的表示证据不确定性的表示不确定性的量度不确定性匹配及阈值的选择组合证据不确定性的算法不确定性的传递算法结论不确定性的合成不确定性随机性模糊性经验引起不完全引起不确定性数学理论概率论模糊集粗糙集可信度方法方法的提出1975年肖特里菲(E.H.Shortliffe)等人在确定性理论(TheoryofConfirmation)的基础上，结合概率论等提出的一种不确定性推理方法。优点直观、简单，且效果好。可信度(Certainty)根据经验对一个事物或现象为真的相信程度。可信度带有较大的主观性和经验性，其准确性难以把握。C-F模型（Certainty-Factor，可信度因子）基于可信度表示的不确定性推理的基本方法。C-F模型知识不确定性的表示IFETHENH(CF(H,E))例：

IF头痛AND流涕THEN感冒(0.7)CF(H,E)的取值范围:[-1,1]。CF(H,E)>0，证据E的出现支持

H为真CF(H,E)<0，证据E的出现支持

H为假CF(H,E)=0，证据E的出现与否与H

无关静态强度CF(H,E)证据不确定性的表示可信度因子:

CF(E)＝0.6，E的可信度为0.6证据E的可信度取值范围：[-1，1]肯定它为真，则CF(E)=1肯定它为假，则CF(E)=–1。某种程度为真，则0<CF(E)<1。某种程度为假，则－1<CF(E)<0。未获得任何相关的观察，

则CF(E)=0。动态强度CF(E)C-F模型不确定性的表示与量度知识不确定性的表示：IFETHENH(CF(H,E)=X)证据不确定性的表示：CF(E)＝0.6组合证据不确定性的算法AND条件下的证据合成：证据​E=E1ANDE2AND…ANDEn则

CF(证据​E)=min{CF(E1),CF(E2),…,CF(En)}OR条件下的证据合成：证据​E=E1ORE2OR…OREn则

CF(证据​E)=max{CF(E1),CF(E2),…,CF(En)}CF(A)=

0.6

CF(B)=

0.5，CF(AANDB)=min(0.6,0.5)=0.5

CF(AorB)=max(0.6,0.5)=0.6C-F模型不确定性的表示与量度知识不确定性的表示：IFETHENH(CF(H,E)=X)证据不确定性的表示：CF(E)＝0.6组合证据不确定性的算法不确定性的传递算法—结论H的可信度计算：CF(H)=CF(H,E)max(0,CF(E))}当CF(E)<0时，则CF(H)=0当CF(E)=1时，则CF(H)=CF(H,E)IFAANDBTHENC

(CF=0.8)CF(A)=

0.6

CF(B)=

0.5，CF(AANDB)

=min(0.6,0.5)=0.5CF(H)=0.5*0.8=0.4C-F模型结论不确定性的合成算法设有如下知识：IFE1THENH(CF(H,E1)) IFE2THENH(CF(H,E2))(1)分别对每一条知识求出CF(H)：CF1(H)=CF(H,E1)max(0,CF(E1)}CF2(H)=CF(H,E2)max(0,CF(E2)}(2)求出E1与E2对H的综合影响所形成的可信度CF1,2(H)

C-F模型例：设有如下所示的一组知识：r1:IF头痛AND流涕THEN感冒(CF=0.7)r2:IF咳嗽AND发热THEN流感(CF=0.8)

已知：CF(头痛)=0.6,CF(流涕)=0.3,CF(咳嗽)=0.8,CF(发热)=0.4.

求：计算CF(感冒)和CF(流感)的置信度。解：感冒的置信度：证据合成：min⁡(0.6,0.3)=0.3置信度计算：0.3×0.7=0.21流感的置信度:证据合成：min⁡(0.8,0.4)=0.4置信度计算：0.4×0.8=0.32结论:流感的置信度较高，为0.32。

基于证据理论推理《人工智能》学习要点概率分配函数信任函数似然函数证据组合基于D-S的推理步骤不确定性推理中的基本问题不确定性的表示与量度知识不确定性的表示证据不确定性的表示不确定性的量度不确定性匹配及阈值的选择组合证据不确定性的算法不确定性的传递算法结论不确定性的合成不确定性随机性模糊性经验引起不完全引起不确定性数学理论概率论模糊集粗糙集初始证据已知事实结论推理证据理论基本概念即：D-S理论，是德普斯特（A.P.Dempster）首先提出，沙佛（G.Shafer）进一步发展起来的一种处理不确定性的理论。1981年，巴纳特（J.A.Barnett）把该理论引入专家系统中，

同年，卡威（J.Garvey）等人用它实现了不确定性推理。目前，在证据理论的基础上已经发展了多种不确定性推理模型。概率分配函数基本概念设D为变量x所有可能取值的集合，D中的每一个子集都表示一个命题。概率分配函数用于为每个子集分配一个在[0,1]之间的数值，称为基本概率数M(A)。M(A)代表的是子集A为真的可信度，而M(∅)始终为0，表示不可能事件。例：如果D是{红，黄，蓝}，命题“x是红色”分配M({红})=0.3，

这表示我们对“x是红色”这一命题的信任度为0.3。概率分配函数概率分配函数与传统的概率不同概率分配函数允许我们将信任分配到多个命题的子集，而不是将其完全分配给个别命题。如：设D={红，黄，蓝}

M({红})=0.3，M({黄})=0，M({蓝})=0.1，

M({红，黄})=0.2，M({红，蓝})=0.2，M({黄，蓝})=0.1，

M({红，黄，蓝})=0.1，M(Ø)=0

按照概率的要求M({红})+M({黄})+M({蓝})=1

但：M({红})+M({黄})+M({蓝})=0.4信任函数定义命题的信任函数（BeliefFunction)Bel:2D[0,1]

，且

Bel(A)：对命题A为真的总的信任程度。由信任函数及概率分配函数的定义推出： ,

设D={红，黄，蓝}

M({红})=0.3，M({黄})=0，M({红，黄})=0.2，

=0.3+0+0.2=0.5

𝐁𝐞𝐥({红,黄})=𝐌({红})+𝐌({黄})+𝐌({红,黄})似然函数似然函数（PlausibilityFunction)：不可驳斥函数或上限函数。定义4.3：似然函数Pl:2D[0,1]，且𝑃𝑙(A)=1−𝐵𝑒𝑙(¬A)，

A

D例：设D={红，黄，蓝}

M({红})=0.3，M({黄})=0，M({红，黄})=0.2，

𝐁𝐞𝐥({红,黄})=𝐌({红})+𝐌({黄})+𝐌({红,黄})=0.3+0+0.2=0.5

𝑃𝑙({蓝})=1−𝐵𝑒𝑙(¬{蓝})=1−𝐵𝑒𝑙({红，黄})＝1−0.5＝0.5

概率分配函数的正交和（证据的组合）同样的证据有可能得到不同的概率分配函数对样本空间D={a,b}，从不同的来源得到如下两个概率分配函数M1({a})=0.3,M1({b})=0.6,M1({a,b})=0.1,M1(Ø)=0M2({a})=0.4,M2({b})=0.4,M2({a,b})=0.2,M2(Ø)=0需要对两个概率分配函数进行组合，德普斯特提出了正交和的计算方法定义：设M1和M2是两个概率分配函数；则其正交和M=M1

M2：

其中：

如果K0，则正交和M也是一个概率分配函数；

如果K=0，则不存在正交和M，即没有可能存在概率函数，称M1与M2矛盾。

概率分配函数的正交和（证据的组合）例

设D={黑，白}，且设𝑀1({黑},{白},{黑,白},Φ

)

=

(

0.3,

0.5,

0.2,

0

)

𝑀2({黑},{白},{黑,白},Φ

)

=

(

0.6,

0.3,

0.1,

0)

则：

或

概率分配函数的正交和（证据的组合）例

设D={黑，白}，且设𝑀1({黑},{白},{黑,白},Φ

)

=

(

0.3,

0.5,

0.2,

0

)

𝑀2({黑},{白},{黑,白},Φ

)

=

(

0.6,

0.3,

0.1,

0)

则：

组合后得到的概率分配函数:

基于证据理论的不确定性推理基于证据理论的不确定性推理的步骤：建立问题的样本空间D。由经验给出，或者由随机性规则和事实的信度度量算基本概率分配函数。计算所关心的子集的信任函数值、似然函