《华南理工大学《高级人工智能》复习资料讲解》由会员分享，可在线阅读，更多相关《华南理工大学《高级人工智能》复习资料讲解（13页珍藏版）》请在金锄头文库上搜索。
1、华南理工大学高级人工智能复习资料1、计算决策树（去年考的题型）设样本集合如下所示，其中A、B、C是F的属性，试根据信息增益标准（ID3算法）求解F的 决策树。A000011B001100C010101(已知 log2(2/3)= -0.5842, log2(1/3)= -1.5850, log2(3/4)= -0.41504, )431 (2221 H = -H+ 3H=$2log - + 2log - + 2log - + 1log - = 0.965A 7 A=07 A=17 I 2 -2 -2 32 3JH = -H + 3H =-1 $3log 3 + 1log 1 + 1log 1
2、+ 2log , = 0.857B 7 B=0 7 B=17 I 2 -2 -2 32 3 J- 3 1L. 1 ”3 ”3 M 01 n H =-H +-H =- = 0.464C 7 C=0 7 C=17 見 4&2 -&2 3&2 3V.所以第一次分类选属性C,对C=0的四个例子再进行第二次分类。2 2 1 ( 111H = - H+ - H=Q1log - + 1log - = 0.5A - A=0 4 A=1-&2 2&2 22 2 1111H = H+ H=-/blog一 + 1log_ = 0.5所以，B - B=0 4 B=1- I 2 22 2J可任选属性A或B作为第二次分类
3、的标准，如选属性A,则A=1的两个例子再按属性B分 类，得到H =1H +1H =-16= 0B 2 B =0 2 B=122、逻辑推理(去年考的题型)把谓词公式变换成子句形式(Vx)(my)P(a, x, y) (3x)(Vy)Q(y, b)R(x)解：- 第一步，消去一号，得：(Vx)(3y)P(a, x, y) V(3x)(Vy)Q(y, b)VR(x)- 第二步，深入到量词内部，得：(Vx)(3y)P(a, x, y) V(3x) (Vy)Q(y, b)VR(x)-第三步，变兀易名，得(Vx)(3y)P(a, x, y) V(3u) (V v)(Q(v, b) VR(u)- 第四步，存
4、在量词左移，直至所有的量词移到前面，一(Vx) (3y) (3u) (V v) (P(a, x, y) V(Q(v, b) VR(u)由此得到前述范式- 第五步，消去“3(存在量词)，略去“V”全称量词- 消去(3y),因为它左边只有(Vx),所以使用x的函数f(x)代替之，这样得到: (Vx)(3u)(Vv) (P(a, x, f(x) V Q(v, b)VR(u)- 消去(3u)，同理使用g(x)代替之，这样得到：(Vx) (Vv) ( P(a, x, f(x) V Q(v, b) V R(g(x)- 贝y,略去全称变量，原式的Skolem标准形为：P(a, x, f(x) V Q(v,
5、b) V R(g(x)3、谓词公式表示知识 与归结法证明定理过程 (去年考的题型) 例 设已知：(1) 能阅读者是识字的；(2) 海豚不识字； (3)有些海豚是很聪明的。试证明：有些聪明者并不能阅读。证 首先，定义如下谓词：R(x)： x 能阅读。L(x)： x 识字。I(x)： x 是聪明的。D(x)： x 是海豚。 然后把上述各语句翻译为谓词公式：(1)Vx(R(x)L(x)Vx(D(x)f L(x)已知条件3x(D(x)Al(x)3x(I(x)AR(x)需证结论求题设与结论否定的子句集，得(1) R(x)VL(x)(2) D(y)V L(y)(3) D (a)(4) I (a)l(z)V
6、R(z)将子句集进行归结(6) R(a) (4)(5)归结(7) L(a) (1)(6)归结(8) D(a) (2)(7)归结(9) NlL (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/BC/DP (A|D)=边 BCP (A, B, C, D)=吨CP (A) P (B|A) P (C|A) P (D|B, C)= P (A)
7、!B P (B|A) Ic 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 (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) * 1 = 0.5a同理P (A|D) = alBICP (A, B, C, D)=alBICP (
8、A) P (B|A) P (C|A) P (D|B, C)=a P (A)!B P (B|A) Ic P (C|A) P (D|B, C)IB P (B|A) Ic P (C|A) P (D|B, C)= P (B|A)IC P (C|A) P (D|B, C) + P (B|A)IC 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*0=0.5
9、P (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) ，- H(B) , - H(C)V (A, B)H(A) , H(B)通过消解
10、反演得到空子树，故该假设不成立如果 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 为说谎者解法二：设T(x): x是说真话的人
11、A 说真话：T(A)t-T(B)a - T(C)A 说假话：-T(A)tT(B) v T(C)B 说真话：T(B)t-T(A)a - T(C)B 说假话：-T(B)tT(A) v T(C)C 说真话：T(C)t-T(A) v - T(B)C 说假话：-T(C)tT(A) a T(B) 化为字句集1. -T(A) v - T(B)2. -T(A) v - T(C)3. T(A) v T(B) v T(C)4. -T(B) v - T(C)5. T(C) v -T(A) v - T(B)6. T(A) v T(C)7. T(C) v T(B)求解问题的否定式和 answer 的析取8. -T(x)
12、vanswer(x)9. T(C) v T(B)10. T(C)11. Answer(C) 所以C是老实人。8. T(x)vanswer(x)9. T(C) v T(B)10. T(B)11. Answer(B) 所以 B 不是老实人。8. T(x)vanswer(x)9. T(C) v T(A)10. T(A)11. Answer(A)所以A不是老实人。1. 和 6.归结7.和 9.归结8.和 10. 归结1. 和 6.归结4.和 9.归结8.和 10. 归结1. 和 7.归结2.和 9.归结8.和 10. 归结6、朴素贝叶斯学习法（去年考的题型）样例：某种天气是否适合室外打网球 训练数据给
13、定14 个样例（下页表） 输入新实例求目标概念的值PlayTennis=Yes/NoDayOutlookTemperatureHumidityWindPlayTennis1sunnyhothighweakno2sunnyhothighstrongno3overcasthothighweakyes4rai nmildhighweakyes5rai ncoolnormalweakyes6rai ncoolnormalstrongno7overcastcoolnormalstrongyes8sunnymildhighweakno9sunnycoolnormalweakyes10rai nmildnormalweakyes11sunnymildnormalstrongyes12overcastmildhighstrongyes13overcasthotnormalweakyes14rai nmildhighstrongno解：将实例代入到朴素贝叶斯分类器输出公式得如下式子v = arg max P(v)n P(a I v )NB j i i jv .日 yes ,no=arg max P(v )P(sunny I v )P(cool I v )P(high I v )P
