1 / 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, )
HA?431?222HA?0?HA?1???2log2?2log2?2log2?1log2777?4431???0.965 3?HB?431?3112?HB?0?HB?1???3log2?1log2?1log2?2log2??0.857 777?4433?431?1330?HC?0?HC?1???1log2?3log2?3log2?0log2??0.464 777?4433?HC? 所以 第一次分类选属性C，对C=0的四个例子再进行第二次分类。
HA?221?11?HA?0?HA?1???1log2?1log2??0.5 444?22?221?11?HB?0?HB?1???1log2?1log2??0.5 所以，444?22?HB?可任选属性A或B作为第二次分类的标准，如选属性A，则A=1的两个例子再按属性B分
类，得到
HB?111HB?0?HB?1???0??0 222 最后，得到F的决策树如下：
C=0
A
A=1 B B=0 B=1 C C=1 + A=0 — + — 2 / 13
2、逻辑推理 (去年考的题型) 把谓词公式变换成子句形式
～(?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)
3 / 13
(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 \\ / D
P (A|D) = ?∑B∑CP (A, B, C, D)
= ?∑B∑CP (A) P (B|A) P (C|A) P (D|B, C) = ? 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 =1
P (A|D) = ? P (A) * 1 = 0.5? 同理
P (~A|D) = ?∑B∑CP (~A, B, C, D)
= ?∑B∑CP (~A) P (B|~A) P (C|~A) P (D|B, C) = ? 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.5[0.5*0.5+0.5*0] =0.5
P (~A|D) = ? P (~A) * 0.5 = 0.25? 归一化得
4 / 13
P (A|D) = 0.67 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为老实人，分如下情况： 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)
通过消解反演没有空子树，故该假设成立
总结：A,B为说谎者
5 / 13
解法二：设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. T（C) 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不是老实人。