AI考试重点.doc

1.4 人工智能的研究与应用领域 The fields of AI research and application1.博弈 2.自动定理证明 3.专家系统 4.自然语言理解 5 .机器视觉6.自动程序设计 7.机器人学 8.机器学习 9.人工神经网络 10.智能决策支持系统11.智能检索 12.分布式人工智能与Agent13.数据挖掘与知识发现 14.系统与语言工具2.2 一阶谓词逻辑表示法 (First-order prediction representation method)一阶谓词逻辑表示法是一种重要的知识表示方法，它以数理逻辑为基础。谓词逻辑是到目前为止能够表达人类思维活动规律的一种最精确的形式语言，也是目前能够表达人类思维活动的一种最精确的语言，它与人类的自然语言比较接近，又可以方便地存储到计算机中，并被计算机进行精确处理。因此，它是一种最早应用于人工智能中的表示方法。2.2.2用谓词公式表示知识的步骤(1) 定义谓词及个体，确定每个谓词及个体的确切含义；(2) 根据所要表达的事物或概念，为每个谓词中的变元赋以特定的值；(3) 根据所要表达的知识的语义，用适当的连接符号将各个谓词连接起来，形成谓词公式。例 2.2 用谓词公式表示下列规则性知识：自然数都是大于零的整数。任何人都会死的。解 首先定义谓词如下：N(x) 表示x是自然数I(x) 表示x是整数HUMAN(x) 表示x是 人WILLDIE(x) 表示x是会死的GZ(x) 表示x大于零。按照第二步和第三步的要求，可以得到(x)( N(x) I(x)GZ(x)(x)(HUMAN(x) WILLDIE(x)1 产生式系统的组成把一组产生式放在一起，让它们相互配合，协同作用，一个产生式生成的结论可以供另一个产生式作为己知事实使用，以求得问题的解，这样的系统称为产生式系统。产生式系统一般由三个基本部分组成：规则库、综合数据库和推理机。它们之间的关系如图所示。2.3.1 知识的产生式表示产生式可表示的知识种类:确定性的事实、规则和不确定性的事实、规则。1. 确定性规则知识的产生式表示确定性规则知识的产生式形式为P Q 或者 IF P THEN Q其中，P 是产生式的前提，用于指出该产生式是否是可用的条件；Q 是一组结论或操作，用于指出前提P所指示的条件被满足时，应该得出的结论或应该执行的操作。2. 不确定性规则知识的产生式表示产生式可用于不确定知识的表示，不确定性规则知识的产生式形式为P Q ( 可信度 ) 或 IF P THEN Q ( 可信度 )框架表示法几种比较常用的槽名 ISA槽:用于指出对象间抽象概念上的类属关系。其直观含义是“是一个”，“是一种”，“是一只”一般用“ISA”槽指出的联系都具有继承性，即下层框架可继承上层框架所描述的属性和值。 AKO槽:用于具体地指出对象间的类属关系。其直观含义是“是一种”。当用它作为某下层框架的槽时，就明确地指出了该下层框架所描述的事物是其上层框架所描述事物中的一种，下层框架可继承上层框架中的属性和值。 Instance槽：用来表示AKO的逆关系。当用它作为某上层框架的槽时，可在该槽中指出它所联系的下层框架。用“Instance”槽指出的联系都具有继承性，即下层框架可继承上层框架所描述的属性及值。 Part-of槽:用于指出“部分”与“全体”的关系。当用其作为某框架的一个槽时，槽中所填的值称为该框架的上层框架，该框架所描述的对象只是其上层框架所描述对象的一部分。例如，“两只手”是“人体”的一部分。可以将“两只手”和“人体”分别定义成框架，“两只手”称为下层框架，“人体”则为其上层框架。在“两只手”的框架中设置一个槽，其中填上这个框架名。可以表示为：几种比较常用的槽名框架名：Part-of：手指数：单位(个)语义网络表示法(2) 动作和事件的表示有些表示知识的语句涉及的动词既有主语，又有直接宾语和间接宾语。也就是说，既有发出动作的主体，又有接受动作的客体和动作所作用的客体。在用语义网络表示这样的知识时，即可以把动作设立成一个节点，也可以将所发生的动作当成一个事件，设立一个事件节点。动作或事件节点也有一些向外引出的弧，用于指出动作的主体与客体，或指出事件发生的动作以及该事件的主体与客体。例如，张三送给李四一支钢笔。既可以把“送给”作为一个动作节点，也可以把它作为一个事件表示。鲁滨逊归结原理 命题逻辑的归结(2) 命题逻辑的归结反演 归结原理：假设F为已知前提，G为欲证明的结论，归结原理把证明G为F的逻辑结论转化为证明FG为不可满足。 再根据定理3.1，在不可满足的意义上，公式集FG与其子句集是等价的，即把公式集上的不可满足转化为子句集上的不可满足。 应用归结原理证明定理的过程称为归结反演。 在命题逻辑中，已知F，证明G为真的归结反演过程如下： 否定目标公式G，得G; 把G并入到公式集F中，得到F，G； 把F，G化为子句集S。 应用归结原理对子句集S中的子句进行归结，并把每次得到的归结式并入S中。如此反复进行，若出现空子句，则停止归结，此时就证明了G为真。例4.10 设已知的公式集为P, (PQ)R, (ST)Q, T，求证结论R。解：假设结论R假, 将R加入公式集，并化为子句集 S=P,PQR, SQ, TQ, T, R 其归结过程如右图的归结演绎树所示。该树根为空子句。 其含义为：先假设子句集S中的所有子句均为真，即原公式集为真,R也为真；然后利用归结原理，对子句集进行归结，并把所得的归结式并入子句集中；重复这一过程，最后归结出了空子句。 根据归结原理的完备性，可知子句集S是不可满足的，即开始时假设R为真是错误的，这就证明了R为真。鲁滨逊归结原理 谓词逻辑的归结 在谓词逻辑中，由于子句集中的谓词一般都含有变元，因此不能象命题逻辑那样直接消去互补文字。而需要先用一个最一般合一对变元进行代换，然后才能进行归结。可见，谓词逻辑的归结要比命题逻辑的归结麻烦一些。谓词逻辑的归结原理 谓词逻辑中的归结式可用如下定义来描述： 定义3.27 设C1和C2是两个没有公共变元的子句，L1和L2分别是C1和C2中的文字。如果L1和L2存在最一般合一，则称 C12=(C1- L1)( C2- L2)为C1和C2的二元归结式，而L1和L2为归结式上的文字。例4.11 设C1=P(a)R(x)，C2=P(y)Q(b)，求 C12 解：取L1= P(a), L2=P(y)，则L1和L2的最一般合一是=a/y。根据定义3.27,可得 C12=( C1-L1) (C2-L2) =(P(a), R(x)-P(a)(P(a), Q(b)-P(a) =(R(x)(Q(b)= R(x), Q(b) =R(x)Q(b) 例4.12 设C1=P(x)Q(a)，C2=P(b)R(x) ，求 C12 解：由于C1和C2有相同的变元x，不符合定义3.27的要求。为了进行归结，需要修改C2中变元x的名字为，令C2=P(b)R(y)。此时L1= P(x), L2 =P(b)，L1和L2的最一般合一是=b/x。则有 C12=( C1-L1) (C2-L2) =(P(b), Q(a)-P(b) (P(b), R(y)-P(b) =(Q(a) (R(y)= Q(a), R(y) =Q(a)R(y)应用归结原理进行问题求解下面是利用归结原理求取问题答案的步骤：（1）把已知前提条件用谓词公式表示出来，并化成相应的子句集，设该子句集的名字为S1。（2）把待求解的问题也用谓词公式表示出来，然后将其否定，并与一谓词ANSWER构成析取式。谓词ANSWER是一个专为求解问题而设臵的谓词，其变量必须与问题公式的变量完全一致。（3）把问题公式与谓词ANSWER构成的析取式化为子句集，并把该子句集与S1合并构成子句集S。（4）对子句集S应用谓词归结原理进行归结，在归结的过程中，通过合一臵换，改变ANSWER中的变元。（5）如果得到归结式ANSWER ，则问题的答案即在ANSWER谓词中。例 任何兄弟都有同一个父亲，John和Peter是兄弟，且John的父亲是David，问Peter的父亲是谁？解 第一步：将已知条件用谓词公式表示出来，并化成子句集，那么要先定义谓词。（1） 定义谓词：设Father(x,y)表示x是y的父亲。Brother(x,y)表示x和y是兄弟。（2） 将已知事实用谓词公式表示出来。F1 ：任何兄弟都有同一个父亲。(x)(y)(z)(Brother(x,y)Father(z,x)Father(z,y)F2：John和Peter是兄弟。Brother(John,Peter)F3： John的父亲是David。Father(David, John)（3） 将它们化成子句集得：S1=Brother(x,y)Father(z,x)Father(z,y),Brother(John,Peter), Father(David,John)第二步：把问题用谓词公式表示出来，并将其否定与谓词ANSWER作析取。设Peter的父亲是u，则有：Father(u,Peter)。将其否定与ANSWER作析取，得：G：第三步：将上述公式G化为子句集S2，并将S1和S2合并到S。S2 =Father(u,Peter)ANSWER(u)S= S1S2将S中各子句列出如下：（1）Brother(x,y)Father(z,x)Father(z,y)。（2）Brother(John,Peter)。（3）Father(David,John)。（4）Father(u,Peter)ANSWER(u)。第四步：应用归结原理进行归结（5）Brother(John,y)Father(David,y)（1）与（3）归结 =David/z,John/x（6）Brother(John,Peter)ANSWER(David)（4）与（5）归结=David/u,Peter/y（7）ANSWER(David) （2）与（6）归结第五步：得到了归结式ANSWER(David)，答案即在其中，所以u=David。即Peter的父亲是David。例3.23 某人被盗，公安局派出所派出5个侦察员去调查。研究案情时:侦察员A说：“赵与钱中至少有一人作案”；侦察员B说：“钱与孙中至少有一人作案”；侦察员C说：“孙与李中至少有一人作案”；侦察员D说：“赵与孙中至少有一人与此案无关”；侦察员E说：“钱与李中至少有一人与此案无关”。如果这5个侦察员的话都是可信的，试问谁是盗窃犯呢？解: 第一步: 将5位侦察员的话表示成谓词公式，为此先定义谓词。设谓词P(x)表示x是作案者，所以根据题意:A: P(zhao) P(qian) B: P(qian) P(sun)C: P(sun) P(li) D: P(zhao) P(sun)E: P(qian) P(li)以上每个侦查员的话都是一个子句。第二步：将待求解的问题表示成谓词。设y是盗窃犯，则问题的谓词公式为P(y),将其否定并与ANS(y)做析取得:P(y) ANS(y)第三步:求前提条件及P(y) ANS(y)的子句集，并将各子句列表如下:(1) P(zhao) P(qian)(2) P(qian) P(sun)(3) P(sun) P(li)(4) P(zhao) P(sun)(5) P(qian) P(li)(6) P(y) ANS(y)第四步：应用归结原理进行推理。(7) P(qian) P(sun) (1) 与 (4) 归结(8) P(zhao) P(li) (1) 与 (5) 归结(9) P(qian) P(zhao) (2) 与 (4) 归结(10) P(sun) P(li) (2) 与 (5) 归结(11) P(zhao) P(li) (3) 与 (4) 归结(12) P(sun) P(qian) (3) 与 (5) 归结(13) P(qian) (2) 与 (7) 归结(14) P(sun) (2) 与 (12) 归结(15) ANS(qian) (6) 与 (13) 归结，(16) ANS(sun) (6) 与 (14) 归结，所以，本题的盗窃犯是两个人:钱和孙。3.4 自然演绎推理方法 3.4.1 自然演绎推理的概念 自然演绎推理是指从一组已知为真的事实出发，直接运用命题逻辑或谓词逻辑中的推理规则推出结论的过程。自然演绎推理最基本的推理规则是三段论推理，包括假言三段论，假言推理，拒取式。 假言三段论的基本形式为 PQ，QRPR 它表示如果谓词公式PQ和QR均为真，则谓词公式PR也为真。 假言推理可用下列形式表示 P，PQ Q 它表示如果谓词公式P和PQ都为真，则可推得Q为真结论。 拒取式的一般形式为 PQ，Q P 它表示如果谓词公式PQ为真且Q为假，则可推得P为假的结论。 3.4.2 利用演绎推理解决问题在利用自然演绎推理方法求解问题时，一定要注意避免两种类型的错误：肯定后件的错误和否定前件的错误。肯定后件的错误是指当PQ为真时，希望通过肯定后件Q为真来推出前件P为真。这显然是错误的推理逻辑，因为当 PQ及 Q为真时，前件 P既可能为真，也可能为假。否定前件的错误是指当PQ为真时，希望通过否定前件P来推出后件Q为假。这也是不允许的，因为当PQ及P为假时，后件Q既可能为真，也可能为假。例如：“如果S是音乐系的学生，则S至少会演奏一种乐器”，“张毅不是音乐系的学生”推出“张毅不会演奏任何乐器”。例子： 设已知如下事实：A, B, AC, BCD, DQ求证：Q为真。证明：因为 A, AC C 假言推理B, C BC 引入合取词BC，BCD D 假言推理D, DQ Q 假言推理因此，Q为真例子： 设已知如下事实：(1) 只要是需要编程序的课，王程都喜欢。(2) 所有的程序设计语言课都是需要编程序的课。(3) C+是一门程序设计语言课。求证：王程喜欢C+这门课。证明：首先定义谓词Prog(x) x是需要编程序的课。Like(x, y) x喜欢y。Lang(x) x是一门程序设计语言课把已知事实及待求解问题用谓词公式表示如下：Prog(x)Like(Wang , x)(x)( Lang(x)Prog(x)Lang(C+)应用推理规则进行推理：Lang(y)Prog(y) 全称固化Lang(C+)，Lang(y)Prog(y) Prog(C+) 假言推理 C+/yProg(C+), Prog(x)Like(Wang , x) Like(Wang , C+) 假言推理 C+/x因此，王程喜欢C+这门课。可信度方法1975年肖特里菲（E. H. Shortliffe）等人在确定性理论（theory of confirmation）的基础上，结合概率论等提出的一种不确定性推理方法。优点：直观、简单，且效果好。可信度方法所谓可信度就是在实际生活中根据自己的经验对某一事 物或现象进行观察，判断相信其为真的程度。 例如，张三昨天没有上课，他的理由是肚子疼，就此理由而言，听话的人可能完全相信，也可能完全不相信，也可能在某种程度上相信，这与张三平时的表现和人们对他的话相信程度有关。l这里的相信程度就是我们说的可信度。可信度也称为确定 性因子。在以产生式作为知识表示的专家系统MYCIN中，用以度量知识和证据的不确定性。显然，可信度具有较大的主观性和经验性，其准确性是难以把握的。但是，对于某一具体领域而言，由于该领域的专家具有丰富的专业知识和实践经验，要给出该领域知识的可信度还是完全有可能的。另外，人工智能所面临的问题，通常都较难用精确的数学模型进行描述，而且先验概率及条件概率的确定也比较困难，因此用可信度来表示知识及证据的不确定性仍然不失为一种可行的方法。可信度方法C-F模型C-F模型是基于可信度表示的不确定性推理的基本方法，其他可信度方法都是在此基础上发展起来的。CF（H，E）的取值范围: -1,1。 若由于相应证据的出现增加结论 H 为真的可信度，则 CF（H，E） 0，证据的出现越是支持 H 为真，就使CF（H，E) 的值越大。 反之，CF（H，E）0，证据的出现越是支持 H 为真，就使CF(H,E)的值越大；反之，使CF(H,E)0，证据的出现越是支持 H 为假，就使CF(H,E)的值越小；若证据的出现与否与 H 无关，则使 CF(H,E)=0例如果细菌的染色斑呈革兰氏阳性, 且形状为球状,且生长结构为链形,则该细菌是链球菌(0.7)。这就是专家系统MYCIN中的一条规则。这里的0.7就是规则结论的CF值。设有如下一组产生式规则和证据事实，试用确定性理论求出由每一个规则推出的结论及其可信度。规则: if A then B(0.9) if B and C then D(0.8) if A and C then D(0.7) if B or D then E(0.6)事实:A，CF(A)=0.8;C，CF(C)=0.9解由规则得: CF(B)0.9max0, 0.80.72由规则得: CF(D)10.8max0, min0.72，0.9) 0.80.720.576由规则得: CF(D)20.7max0, min0.8，0.9) 0.70.80.56从而 CF(D)CF(D)1CF(D)2CF(D)1CF(D)20.5760.560.5760.560.81344由规则得:CF(E)0.6max0, max0.72，0.81344 0.60.813440.488064 已知 R1：IF A1 THEN B1 CF(B1,A1)=0.8； R2: IF A2 THEN B1 CF(B1,A2)=0.5； R3: IF B1A3 THEN B2 CF(B2,B1A3)=0.8;初始证据为A1,A2,A3的可信度CF均设为1，即,CF(A1)= CF(A2)= CF(A3)=1,对B1,B2一无所知,求CF(B1)和CF(B2)。设有如下一组知识: r1: IF E1 THEN H (0.8) r2: IF E2 THEN H (0.6) r3: IF E3 THEN H (-0.5) r4: IF E4 AND (E5 OR E6) THEN E1 (0.7) r5: IF E7 AND E8 THEN E3 (0.9) 已知: CF(E2)=0.8,CF(E4)=0.5,CF(E5)=0.6,CF(E6)=0.7,CF(E7)=0.6, CF(E8)=0.9 求: CF(H)=? 2.全局择优搜索每次总是从OPEN表的全体节点中选择一个估价值最小的节点。v