华南理工大学《高级人工智能》复习资料

1、 13 / 13华南理工大学高级人工智能复习资料1、计算 决策树 (去年考的题型)设样本集合如下所示，其中A、B、C是F的属性，试根据信息增益标准(ID3 算法)求解F的决策树。 A B C F 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 0(已知log2(2/3)= -0.5842, log2(1/3)= -1.5850, log2(3/4)= -0.41504, ) 所以 第一次分类选属性C，对C=0的四个例子再进行第二次分类。 所以，可任选属性A或B作为第二次分类的标准，如选属性A，则A=1的两个例子再按属性B分类，得到 最

2、后，得到F的决策树如下：CA+C=1C=0BA=0A=1+B=0B=12、逻辑推理 (去年考的题型)把谓词公式变换成子句形式("x)($y)P(a, x, y) ($x)("y)Q(y, b)R(x)解： 第一步，消去号，得： ("x)($y)P(a, x, y) ($x) ("y)Q(y, b)R(x) 第二步，深入到量词内部，得： ("x)($y)P(a, x, y) ($x) ("y)Q(y, b)R(x) 第三步，变元易名，得("x)($y)P(a, x, y) ($u) (" v)(Q(v, b) R(u

3、) 第四步，存在量词左移，直至所有的量词移到前面， ("x) ($y) ($u) (" v) (P(a, x, y) (Q(v, b) R(u)由此得到前述范式 第五步，消去“$”（存在量词），略去“"”全称量词 消去($y)，因为它左边只有("x)，所以使用x的函数f(x)代替之，这样得到：("x)($u)("v) (P(a, x, f(x) Q(v, b)R(u) 消去($u)，同理使用g(x)代替之，这样得到：("x) ("v) ( P(a, x, f(x) Q(v, b) R(g(x) 则，略去全称变量，原

4、式的Skolem标准形为： P(a, x, f(x) Q(v, b) R(g(x)3、谓词公式表示知识 与归结法证明定理过程 (去年考的题型)例 设已知： (1)能阅读者是识字的； (2)海豚不识字； (3)有些海豚是很聪明的。试证明：有些聪明者并不能阅读。 证 首先，定义如下谓词： R(x)：x能阅读。 L(x)：x识字。 I(x)：x是聪明的。 D(x)：x是海豚。然后把上述各语句翻译为谓词公式：(1) "x(R(x)L(x)(2) "x(D(x) L(x) 已知条件(3) $x(D(x)I(x)(4) $x(I(x)R(x) 需证结论求题设与结论否定的子句集，得(1)

5、 R(x)L(x)(2) D(y) L(y)(3)D (a)(4)I (a)(5) I(z)R(z)将子句集进行归结(6) R(a) (4)(5)归结(7) L(a) (1)(6)归结(8) D(a) (2)(7)归结(9) NIL (3)(8)归结4、贝叶斯网络推理 (去年考的题型)根据图所给出的贝叶斯网络，其中：P(A)=0.5, P(B|A)=1, P(B|A)=0.5,P(C|A)=1, P(C|A)=0.5, P(D|BC)=1, P(D|B,C)=0.5, P(D|B,C)=0.5, P(D|B,C)=0。计算下列概率P(A|D) A / B C / DP (A|D) = aBCP

6、 (A, B, C, D)= aBCP (A) P (B|A) P (C|A) P (D|B, C)= a P (A)B P (B|A) C P (C|A) P (D|B, C)B P (B|A) C P (C|A) P (D|B, C)= P (B|A) C P (C|A) P (D|B, C) + P (B|A) C P (C|A) P (D|B, C)= P (B|A) P (C|A) P (D|B, C) + P (C|A) P (D|B, C) + P (B|A) P (C|A) P (D|B, C) + P (C|A) P (D|B, C)=1*1*1+0 + 0=1P (A|D)

7、 = a P (A) * 1 = 0.5a同理P (A|D) = aBCP (A, B, C, D)= aBCP (A) P (B|A) P (C|A) P (D|B, C)= a P (A)B P (B|A) C P (C|A) P (D|B, C)B P (B|A) C P (C|A) P (D|B, C)= P (B|A) C P (C|A) P (D|B, C) + P (B|A) C P (C|A) P (D|B, C)= P (B|A) P (C|A) P (D|B, C) + P (C|A) P (D|B, C) + P (B|A) P (C|A) P (D|B, C) + P

8、(C|A) P (D|B, C)=0.5*0.5*1+0.5*0.5+0.50.5*0.5+0.5*0=0.5P (A|D) = a P (A) * 0.5 = 0.25a归一化得P (A|D) = 0.675、【谓词归结：说谎者与老实人】消解反演求解证明谁是说谎者 (去年考的题型)一个岛上有两种人，老实人总是说真话，说谎者总是说假话。问岛上A、B、C三人：谁说谎？A答：B和C都说谎B答：A和C都说谎C答：A和B至少有一人说谎问题：请问谁是说谎者？解法一：令H(x) 表示X说真话, W(x,y)表示x，y中至少一人说谎，V(x,y)表示x,y中至少一人说真话如果 A为老实人，得子句如下：H(A

9、) ， H(B) , H(C)V (A, B)H(A) , H(B) 通过消解反演得到空子树，故该假设不成立如果 B为老实人，得子句如下：V (B, C)H(B) , H(A) , H(C)H(A) , H(B) 通过消解反演得到空子树，故该假设不成立如果 C为老实人，分如下情况： 1）A说谎，B说真话 H(B) , H(A), H(C) H(C) 通过消解反演得到空子树，故该假设不成立2）B说谎，A说真话 H(A), H(B), H(C) H(C) 通过消解反演得到空子树，故该假设不成立3）A,B都说谎 H(A), V(B,C) H(B), V(A,C) H(C)通过消解反演没有空子树，故该

10、假设成立总结：A,B为说谎者解法二：设T(x): x是说真话的人A说真话：T(A)®¬T(B)Ù ¬ T(C)A说假话： ¬ T(A)®T(B) Ú T(C)B说真话：T(B)®¬T(A)Ù ¬ T(C)B说假话： ¬ T(B)®T(A) Ú T(C)C说真话：T(C)®¬T(A) Ú ¬ T(B)C说假话： ¬ T(C)®T(A) Ù T(B) 化为字句集1. ¬T(A) &

11、#218; ¬ T(B)2. ¬T(A) Ú ¬ T(C)3. T(A) Ú T(B) Ú T(C)4. ¬T(B) Ú ¬ T(C)5. T(C) Ú ¬T(A) Ú ¬ T(B)6. T(A) Ú T(C)7、T(C) Ú T(B) 求解问题的否定式和answer的析取8. ¬T(x)Úanswer(x)9. T(C) Ú ¬ T(B) 1. 和6.归结10. T（C) 7.和9.归结11. Answe

12、r(C) 8.和10. 归结所以C是老实人。8. T(x)Úanswer(x)9. T(C) Ú ¬ T(B) 1. 和6.归结10. ¬ T(B) 4.和9.归结11. Answer(B) 8.和10. 归结所以B不是老实人。8. T(x)Úanswer(x)9. T(C) Ú ¬ T(A) 1. 和7.归结10. ¬ T(A) 2.和9.归结11. Answer(A) 8.和10. 归结所以A不是老实人。6、朴素贝叶斯学习法 (去年考的题型)样例：某种天气是否适合室外打网球 训练数据给定14个样例(下页表) 输

13、入新实例<Outlook=sunny, Temperature=cool, Humidity=high, Wind=strong> 求目标概念的值PlayTennis=Yes/NoDayOutlookTemperatureHumidityWindPlayTennis1sunnyhothighweakno2sunnyhothighstrongno3overcasthothighweakyes4rainmildhighweakyes5raincoolnormalweakyes6raincoolnormalstrongno7overcastcoolnormalstrongyes8sunn

14、ymildhighweakno9sunnycoolnormalweakyes10rainmildnormalweakyes11sunnymildnormalstrongyes12overcastmildhighstrongyes13overcasthotnormalweakyes14rainmildhighstrongno解：将实例代入到朴素贝叶斯分类器输出公式得如下式子计算vNB，可以从训练数据中获得P(PlayTennis=Yes)=9/14=0.64P(PlayTennis=No)=5/14=0.36各条件概率为：P(strong|Y)=3/9=0.33P(strong|N)=3/5=0

15、.60P(high|Y)=3/9=0.33P(high|N)=4/5=0.80P(cool|Y)=3/9=0.33P(cool|N)=1/5=0.20P(sunny|Y)=2/9=0.22P(sunny|N)=3/5=0.60由此得P(yes)P(strong|Y)P(high|Y)P(cool|Y)P(sunny|Y) =0.64*0.33*0.33*0.33*0.22=0.0051P(no)P(strong|N)P(high|N)P(cool|N)P(sunny|N) =0.36*0.60*0.80*0.20*0.6=0.0207由此知朴素贝叶斯分类器的输出结果是PlayTennis=No

16、概率归一化，则得0.0207/(0.0051+0.0207)=0.8027、语义网络属性关系： AKO,AMO,ISA 包含关系 Part_of 属性关系 Have,Can 时间关系 Before,After位置关系： Locted-on，Located-at，Located-under，Located-inside，Located-outside相近关系： Simliar-to，Near-to因果关系： If-then 组成关系：Composed-of用语义网络表示下列命题（1）猪和羊都是动物；（2）猪和羊都是哺乳动物；（3）野猪是猪，但生长在森林中；（4）山羊是羊，头上长着角；（5）绵羊是

17、一种羊，它能生产羊毛。分析：对象有猪、羊都、动物、哺乳动物、野猪、山羊、绵羊、森林、羊毛、角等。 语义关系，“动物”和“哺乳动物”、“哺乳动物”和“猪”、“哺乳动物”和“羊”、“羊”和“山羊”及“绵羊”、“野猪”和“猪”之间的关系是“是一种”的关系，可用AKO来表示。“山羊”和“头上有角” 之间是一种属性关系，可用IS来描述；“绵羊”和“羊毛”之间是一种属性关系，可用HAVE来描述；“野猪”和“森林”之间是位置关系，可用Locate-at来表示。语义网络：8、框架表示法试实现一个“大学教师”的框架，大学教师类属于教师，包括以下属性：学历（学士、硕士、博士）、专业（计算机、电子、自动化、）、职称

18、（助教、讲师、副教授、教授）一般结构：框架名 槽名1 侧面11 值111值11k1 侧面1n1 值1n11值1n1kn1 槽名2 侧面12 值121值1211 侧面1n2 值1n21值1n21n2 解： 框架名：<大学教师> 类属：<教师> 学历：（学士，硕士，博士） 专业：（计算机，电子，自动化）职称：（助教，讲师，副教授，教授）9、与或型正向演绎推理 已知事实：Fido要么会犬叫和咬人，要么Fido就不是狗。 已知规则：所有Terrier都是狗；所有会犬叫的东西都是咬人的。 求证：存在某个东西，它要么不是Terrier，要么会咬人。 证明： 将事实用谓词逻辑表示F1

19、：(CRY(X) BITE（X）) DOG(X)F2："x (Terrier(x) DOG(x)F3："x(CRY(x)BITE(x)目标表达式子： $x( Terrier(x) BITE(x) (CRY(X) BITE（X）) DOG(X) (BITE（X） BITE（X）) DOG(X)BITE（X）) DOG(X)由F2得F4： DOG(x) Terrier(x)故 BITE（X）) Terrier(x)即 Terrier(x) BITE(x) 结论成立。10、与或型 逆向演绎推理 已知事实：F1: DOG(FIDO)；狗的名字叫 Fido F2: BARKS(FID

20、O)；Fido是不叫的 F3: WAGS-TAIL(FIDO)；Fido摇尾巴F4: MEOWS(MYRTLE)；猫咪的名字叫Myrtle 已知规则： R1: WAGS-TAIL(x1)DOG(x1) ® FRIENDLY(x1)；摇尾巴的狗是温顺的狗 R2: FRIENDLY(x2)BARKS(x2) ® AFRAID(y2,x2)；温顺而又不叫的东西是不值得害怕的 R3: DOG(x3) ® ANIMAL(x3)；狗为动物 R4: CAT(x4) ® ANIMAL(x4)；猫为动物 R5: MEOWS(x5) ® CAT(x5)；猫咪是猫 求证：是否存在这样的一只猫和一条狗，使得这只猫不怕