华南理工大学?高级人工智能?复习资料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分类，得到 最后，得到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) 第四步，存在量词左移，直至所有的量词移到前面， (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) 那么，略去全称变量，原式的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) 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 (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) = a P (A)a同理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 (C|A) P (D|B, C)=0.5*0.5*1+0.5*0.5+0.50.5*0.5+0.5*0P (A|D) = a P (A) * 0.5 = 0.25a归一化得P (A|D)5、【谓词归结：说谎者及老实人】消解反演求解证明谁是说谎者 (去年考的题型)一个岛上有两种人，老实人总是说真话，说谎者总是说假话。问岛上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) ， 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为老实人，分如下情况： 1A说谎，B说真话 H(B) , H(A), H(C) H(C) 通过消解反演得到空子树，故该假设不成立2B说谎，A说真话 H(A), H(B), H(C) H(C) 通过消解反演得到空子树，故该假设不成立3A,B都说谎 H(A), V(B,C) H(B), V(A,C) H(C)通过消解反演没有空子树，故该假设成立总结：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) 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. TC) 7.和9.归结11. Answer(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、朴素贝叶斯学习