华南理工大学《高级人工智能》复习资料.docx
《华南理工大学《高级人工智能》复习资料.docx》由会员分享，可在线阅读，更多相关《华南理工大学《高级人工智能》复习资料.docx（17页珍藏版）》请在冰点文库上搜索。
华南理工大学《高级人工智能》复习资料
华南理工大学《高级人工智能》复习资料
1、计算决策树（去年考的题型）
设样本集合如下所示，其中A、B、C是F的属性，试根据信息增益标准（ID3算法）求解F的决策树。
ABCF
0000
0011
0100
0111
1001
1011
1100
（已知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的决策树如下：
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）
（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
/\
BC
\/
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）∑BP（B|A）∑CP（C|A）P（D|B,C）
∑BP（B|A）∑CP（C|A）P（D|B,C）
=P（B|A）∑CP（C|A）P（D|B,C）+P（~B|A）∑CP（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）∑BP（B|~A）∑CP（C|~A）P（D|B,C）
∑BP（B|~A）∑CP（C|~A）P（D|B,C）
=P（B|~A）∑CP（C|~A）P（D|B,C）+P（~B|~A）∑CP（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
归一化得
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为说谎者
解法二：
设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不是老实人。
6、朴素贝叶斯学习法（去年考的题型）
样例：
某种天气是否适合室外打网球
训练数据—给定14个样例（下页表）
输入新实例
求目标概念的值PlayTennis=Yes/No
Day
Outlook
Temperature
Humidity
Wind
PlayTennis
1
sunny
hot
high
weak
no
2
sunny
hot
high
strong
no
3
overcast
hot
high
weak
yes
4
rain
mild
high
weak
yes
5
rain
cool
normal
weak
yes
6
rain
cool
normal
strong
no
7
overcast
cool
normal
strong
yes
8
sunny
mild
high
weak
no
9
sunny
cool
normal
weak
yes
10
rain
mild
normal
weak
yes
11
sunny
mild
normal
strong
yes
12
overcast
mild
high
strong
yes
13
overcast
hot
normal
weak
yes
14
rain
mild
high
strong
no
解：
将实例代入到朴素贝叶斯分类器输出公式得如下式子
计算vNB，可以从训练数据中获得
P（PlayTennis=Yes）=9/14=0.64
P（PlayTennis=No）=5/14=0.36
各条件概率为：
P（strong|Y）=3/9=0.33P（strong|N）=3/5=0.60
P（high|Y）=3/9=0.33P（high|N）=4/5=0.80
P（cool|Y）=3/9=0.33P（cool|N）=1/5=0.20
P（sunny|Y）=2/9=0.22P（sunny|N）=3/5=0.60
由此得
P（yes）P（strong|Y）P（high|Y）P（cool|Y）P（sunny|Y）=0.64*0.33*0.33*0.33*0.22=0.0051
P（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.0207/（0.0051+0.0207）=0.802
7、语义网络
属性关系：
AKO,AMO,ISA包含关系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）绵羊是一种羊，它能生产羊毛。
分析：
对象有猪、羊都、动物、哺乳动物、野猪、山羊、绵羊、森林、羊毛、角等。
语义关系，“动物”和“哺乳动物”、“哺乳动物”和“猪”、“哺乳动物”和“羊”、“羊”和“山羊”及“绵羊”、“野猪”和“猪”之间的关系是“是一种”的关系，可用AKO来表示。
“山羊”和“头上有角”之间是一种属性关系，可用IS来描述；
“绵羊”和“羊毛”之间是一种属性关系，可用HAVE来描述；
“野猪”和“森林”之间是位置关系，可用Locate-at来表示。
语义网络：
8、框架表示法
试实现一个“大学教师”的框架，大学教师类属于教师，包括以下属性：
学历（学士、硕士、博士）、专业（计算机、电子、自动化、……）、职称（助教、讲师、副教授、教授）
一般结构：
＜框架名＞
＜槽名1＞
＜侧面11＞
＜值111＞…＜值11k1＞
＜侧面1n1＞
＜值1n11＞…＜值1n1kn1＞
＜槽名2＞
＜侧面12＞
＜值121＞…＜值1211＞
＜侧面1n2＞
＜值1n21＞…＜值1n21n2＞
…
解：
框架名：
<大学教师>
类属：
<教师>
学历：
（学士，硕士，博士）
专业：
（计算机，电子，自动化）
职称：
（助教，讲师，副教授，教授）
9、与或型正向演绎推理
已知事实：
Fido要么会犬叫和咬人，要么Fido就不是狗。
已知规则：
①所有Terrier都是狗；②所有会犬叫的东西都是咬人的。
求证：
存在某个东西，它要么不是Terrier，要么会咬人。
证明：
将事实用谓词逻辑表示
F1：
（CRY（X）∧BITE（X））∨~DOG（X）
F2：
x（Terrier（x）→DOG（x））
F3：
x（CRY（x）→BITE（x））
目标表达式子：
x（~Terrier（x）∨BITE（x））
（CRY（X）∧BITE（X））∨~DOG（X）
（（BITE（X）∧BITE（X））∨~DOG（X）
BITE（X））∨~DOG（X）
由F2得F4：
~DOG（x）→~Terrier（x）
故BITE（X））∨~Terrier（x）
即~Terrier（x）∨BITE（x）结论成立。
10、与或型逆向演绎推理
已知事实：
F1:
DOG（FIDO）；狗的名字叫Fido
F2:
～BARKS（FIDO）；Fido是不叫的
F3:
WAGS-TAIL（FIDO）；Fido摇尾巴
F4:
MEOWS（MYRTLE）；猫咪的名字叫Myrtle
已知规则：
R1:
[WAGS-TAIL（x1）∧DOG（x1）]FRIENDLY（x1）；摇尾巴的狗是温顺的狗
R2:
[FRIENDLY（x2）∧～BARKS（x2）]～AFRAID（y2,x2）；温顺而又不叫的东西是不值得害怕的
R3:
DOG（x3）ANIMAL（x3）；狗为动物
R4:
CAT（x4）ANIMAL（x4）；猫为动物
R5:
MEOWS（x5）CAT（x5）；猫咪是猫
求证：
是否存在这样的一只猫和一条狗，使得这只猫不怕这条狗?
用目标表达式表示此问题为:
（x）（y）[CAT（x）∧DOG（y）∧～AFRAID（x，y）]
终止在事实节点前的置换为{MYRTLE/x}和{FIDO/y}。
把它应用到目标表达式，我们就得到该问题的回答语句如下：
[CAT（MYRTLE）∧DOG（FIDO）∧～AFRAID（MYRTLE,FIDO）]
9、产生式表示方式以及推理过程
设有如下问题：
（1）有五个相互可直达且距离已知的城市A、B、C、D、E，如图所示；
（2）某人从A地出发，去其它四个城市各参观一次后回到A;
（3）找一条最短的旅行路线
请用产生式规则表示旅行过程。
解：
综合数据库（x）
（x）中x可以是一个字母，也可以是一个字符串。
初始状态（A）
目标状态（Ax1x2x3x4A）
规则集：
r1:
IFL（S）=5THENGOTO（A）
r2:
IFL（S）<5THENGOTO（B）
r3:
IFL（S）<5THENGOTO（C）
r4:
IFL（S）<5THENGOTO（D）
r5:
IFL（S）<5THENGOTO（E）
其中L（S）为走过的城市数，GOTO（x）为走向城市x
路线如下图所示:
最短旅行路线为：
A->C->D->E->B->A
总距离为5+6+8+10+7=36
10、Kmeans
升级会员 