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? 归一化得