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

《华南理工大学《高级人工智能》复习资料.docx》由会员分享，可在线阅读，更多相关《华南理工大学《高级人工智能》复习资料.docx（14页珍藏版）》请在三一办公上搜索。

1、华南理工大学高级人工智能复习资料1、计算 决策树（去年考的题型）设样本集合如下所示，其中A、B、C是F的属性，试根据信息增益标准（ID3算法）求解F的 决策树。AOOOO111BOO11OO1uolololo(已知 log2(2/3)= -0.5842, log2(1/3)= -1.5850, log2(34)= -0.41504,)431 f 2221HA = 7HA 0 + 7HA 1 =-712log24 + 2log24 + 2log23 + 1log23 = 0.965431 f 3112H = H + H =- 3log + 1log + 1log + 2log = 0.857B

2、7 B=0 7 B=17 2 42 42 32 3 J4 3 1 f1 33 心0H =- H+-H=- = 0.464C 7C=07C=17&2 4&24&2 3&23V.所以第一次分类选属性C，对C=0的四个例子再进行第二次分类。221 (1 .1日Ha = - H 0 + - Ha =-11log2 - + 1log2 -卜 0.5221 f1 1 c.H = , H +, H =-1log / 1log c，= 0.5所以，B 4 B=0 4 B=14 I 2 22 2J可任选属性A或B作为第二次分类的标准，如选属性A，则A=1的两个例子再按属性B分 类，得到Hb = - HB 0 +

3、 - Hb 1 =-血= 0最后，得到F的决策树如下：2、 逻辑推理(去年考的题型)把谓词公式变换成子句形式(Vx)(y)P(a, x, y) f 曰x)(Vy)Q(y, b)R(x)解： 第一步，消去一号，得：(Vx)(y)P(a, x, y) V曰x)(Vy)Q(y, b)VR(x) 第二步，深入到量词内部，得：(Vx)(3y)P(a, x, y) V曰x) (Vy)Q(y, b)VR(x)第三步，变兀易名，得(Vx)(3y)P(a, x, y) V(3u) (V v)(Q(v, b) VR(u) 第四步，存在量词左移，直至所有的量词移到前面， (Vx) (3y) (3u) (V v) (

4、P(a, x, y) V(Q(v, b) VR(u)由此得到前述范式 第五步，消去“孑(存在量词)，略去“V”全称量词 消去(为)，因为它左边只有(Vx)，所以使用x的函数f(x)代替之，这样得到:(Vx)(3u)(Vv) (P(a, x, f(x) V Q(v, b)VR(u) 消去(u)，同理使用g(x)代替之，这样得到：(Vx) (Vv) ( P(a, x, f(x) V Q(v, b) V R(g(x) 贝h略去全称变量，原式的Skolem标准形为：P(a, x, f(x) V Q(v, b) V R(g(x)3、谓词公式表示知识与归结法证明定理过程(去年考的题型)例设已知：(1)能阅

5、读者是识字的；海豚不识字；有些海豚是很聪明的。试证明：有些聪明者并不能阅读。证 首先，定义如下谓词：R(x)： x能阅读。L(x)： x 识字。I(x)： x是聪明的。D(x)： x是海豚。然后把上述各语句翻译为谓词公式：(1)Vx(R(x)fL(x)Vx(D(x)f L(x)已知条件3x(D(x)AI(x)3x(I(x)AR(x)需证结论求题设与结论否定的子句集，得(1) R(x)VL(x)一D(y)V L(y)(3) D (a)(4) I (a)(5) - I(z)VR(z)将子句集进行归结(6) R(a) (4)(5)归结L(a) (6)归结(8) -D(a) (2)(7)归结NIL(8

6、)归结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) = aIBICP (A, B, C, D)=IBICP (A) P (B|A) P (C|A) P (D|B, C)=a P (A)Ib P (B|A)君 P (C|A) P (D|B, C)IB P (B|A)君 P (C|A) P (D|B, C)=P (B|A)2C

7、 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) = aIBICP (A, B, C, D)=aIBICP (A) P (B|A) P (C|A) P (D|B, C)=a P (A)Ib P (B|A)2c P (C|A) P (D|B, C)IB P

8、 (B|A) IC P (C|A) P (D|B, C)=P (B|A)2C 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)=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、【谓词归结：说谎者与老实人】消解反演求解证明谁是说谎

9、者(去年考的题型)一个岛上有两种人，老实人总是说真话，说谎者总是说假话。问岛上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为老实人，分如下情

10、况：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是说真话的人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 -

11、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)vanswer(x)9.T(C) v - T(B)1.和6.归结10.T(C)7.和9.归结11.Answer(C)8.和10.归结所以C是老实人。8.T(x)vanswer(x)9.T(C) v - T(B)1.和6.归结10.-T(

12、B)4.和9.归结11.Answer(B)8.和10.归结所以b不是老实人。8.T(x)vanswer(x)9.T(C) v - T(A)1.和7.归结10.-T(A)2.和9.归结11.Answer(A)8.和10.归结所以A不是老实人。6、朴素贝叶斯学习法（去年考的题型）样例：某种天气是否适合室外打网球训练数据一给定14个样例（下页表）输入新实例 求目标概念的值PlayTennis=Yes/NoDayOutlookTemperatureHumidityWindPlayTennis1sunnyhothighweakno2sunnyhothighstrongno3overcasthothigh

13、weakyes4rainmildhighweakyes5raincoolnormalweakyes6raincoolnormalstrongno7overcastcoolnormalstrongyes8sunnymildhighweakno9sunnycoolnormalweakyes10rainmildnormalweakyes11sunnymildnormalstrongyes12overcastmildhighstrongyes13overcasthotnormalweakyes14rainmildhighstrongno解：将实例代入到朴素贝叶斯分类器输出公式得如下式子v = arg

14、max P(v)n P(a I v )NBj i i jv . e( yes,no=arg max P(v )P(sunny I v )P(cool I v )P(high I v )P(strong I v ) j j j j j v , e( yes,no计算vNB，可以从训练数据中获得P(PlayTennis=Yes)=9/14=0.64P(PlayTennis=No)=5/14=0.36各条件概率为:P(strong|Y)=$9=0.33P(high|Y)=3/9=0.33P(cool|Y)=39=0.33P(sunny|Y)=29=0.22由此得P(strong|N)=35=0.60

15、P(high|N)=4/5=0.80P(cool|N)=15=0.20P(sunny|N)=3/5=0.60P(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概率归一化，则得 0.020/(0.0051+0.0207)=0.8027、语义网络属性关系：AKO,AMO,ISA包含关系

16、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、“哺乳动物”和“猪”、“哺乳动物”和“羊”、“羊” 和“山羊”及“绵羊”、“野猪”和“猪”之间的关系是“是一种”的关系，可用KO来表 示。“山羊”和“头上有角”之间是一种属性关系，可用IS来描述；“绵羊”和“羊毛”之间是一种属性关系，可用HAVE来描述；“野猪”和“森林”之间是位置关系，可用Locate-at来表示。语义网络：8、框架表示法试实现一个“大学教师”的框架，大学教师类属于教师，包括以下属性：学历（学士、硕士、博士）、专业（计算机、电子、自动化、）、职称（助教、讲师、副教授、教授）一般结构：框架名槽名1侧面11值 111.侧面1n1值 1n11.槽名2侧面12值 121.侧面1n2值

18、 1n21.解：框架名： 大学教师类属： 教师学历：（学士，硕士，博士）专业：（计算机，电子，自动化）职称：（助教，讲师，副教授，教授）9、与或型正向演绎推理已知事实：Fido要么会犬叫和咬人，要么Fido就不是狗。已知规则：所有Terrier都是狗；所有会犬叫的东西都是咬人的。求证：存在某个东西，它要么不是Terrier，要么会咬人。证明：将事实用谓词逻辑表示F1： (CRY(X) A BITE (X) ) V DOG(X)F2： Vx (Terrier(x) -DOG(x)F3： Vx(CRY(x)f BITE(x)目标表达式子：3x( Terrier(x) V BITE(x)(CRY(X

19、) A BITE (X) ) V DOG(X)(BITE (X)A BITE (X) ) V DOG(X)BITE (X) ) V DOG(X)由 F2 得 F4： DOG(x) Terrier(x)故 BITE (X) ) V Terrier(x)即 Terrier(x) V BITE(x)结论成立。10、与或型逆向演绎推理已知事实：F1: DOG(FIDO)；狗的名字叫FidoF2:BARKS(FIDO)； Fido 是不叫的F3: WAGS-TAIL(FIDO)； Fido 摇尾巴F4: MEOWS(MYRTLE)；猫咪的名字叫 Myrtle已知规则：R1: WAGS-TAIL(x1)A

20、DOG(x1) t FRIENDLY(xl)；摇尾巴的狗是温顺的狗R2: FRIENDLY(x2)ABARKS(x2) tAFRAID(y2,x2)；温顺而又不叫的东西是不值得害 怕的R3: DOG(x3) t ANIMAL(x3)；狗为动物R4: CAT(x4) t ANIMAL(x4)；猫为动物R5: MEOWS(x5) t CAT(x5)；猫咪是猫求证：是否存在这样的一只猫和一条狗，使得这只猫不怕这条狗？用目标表达式表示此问题 为:3 ( x) 3( y)CAT(x)ADOG(y)AAFRAID(x, y)CAT(x)DOG(y)fe/x5FIDO/yDOG (FIDO)FIDO/ylM

21、YRTLE/xMEOWS (MYRTLE)FIDO/yJ BAEKS (FIDO)CAT(x) A DOG (y)八AFRAID g y) AFRAID9 必 x2)WAGE-TAIL (y)FRIENDLY (xl)FRIENDLY (y) BAEKS (y)D0G(y)CAT (x5)MEOWS (x)FIDO/y J终止在事实节点前的置换为MYRTLE/x和FIDO/y 把它应用到目标表达式 问题的回答语句如下：CAT(MYRTLE)ADOG(FIDO)AAFRAID(MYRTLE,FIDO)9、产生式表示方式以及推理过程设有如下问题：(1) 有五个相互可直达且距离已知的城市a、B、C、

22、D、E,如图所示;(2) 某人从A地出发，去其它四个城市各参观一次后回到A;(3) 找一条最短的旅行路线请用产生式规则表示旅行过程。解：综合数据库(x)(x)中x可以是一个字母，也可以是一个字符串。 初始状态(A) 目标状态(Ax1x2x3x4A)规则集：r1IFL(S)=5THENGOTO(A)r2IFL(S)5THENGOTO(B)r3IFL(S)5THENGOTO(C)r4IFL(S)5THENGOTO(D)r5IFL(S)C-D-E-B-A 总距离为 5+6+8+10+7=36例子Oj= += 1.510、Kmeans集合S见表1,作为一个聚美分析的二维，要求的簇的数童蚌九, a（0.

23、0）为初始的簇中心，Mi =苗=（皿）* m2 = o2=（q的每个对彖，根据其与各个簇中心的距 将它赋给最近的簇，Q dMyO. = V（0-1.5r+（2-0y = 2.5显然d（虬Q）京（虬皿）故将R分配给G*对于I :共1邕0）=如一5+（2一打=729叽皿 4 ） = J（0 5）（00），= 5I因为（M1：O4）所以将Q分配给J对于 ：=5d g 么）=J（O-5）、（O 2）： = B因为心捋皿）家（虹口）所以将Q 分配给5,更新,得到新簇 Ci = QJ和 c2=o2zo3.o4计算平方误差准则，单个方差为25蜻二半（0凶E =（0 0），+（2 2 月+ （0 寸 +（2-

24、2） 瓦=27.25= 01 =（0?0）0Xy10220031.50450552总体平均方差是：E =25 + 2725 = 5225小呻计算新的簇的中心场=0 + 5住2 + 2）=Z52）迅=（0 + L 5 + 5照（0 + 0 + 0）/3）=（2.17 间重复（2）和（3）,得到5分配给J；。卫分配给O3分配给 C2, O4分配给&。事分配给J,更新，得到新铤i=Q0 一和 鸟*q 中心为 捋=（Z5Af2 =（2.17,0）单个方差分别为E = （0-2.5）2 +（2-2）3+（2.5-5）2 +（2-2y|=12.5 E =13.15总体平均误差是：E Ex + E2 12.5 + 13.15 = 25.65由上可以看出，第一次迭代后，总体平均误差值52. 2厂25. 65, 显著减小。由于在两次迭代中，簇中心不变，所以停止迭代过程, 算法停止