(只有部分概念,计算题不包括)
第一章
【人工智能的定义】
⑴人工智能主要研究人类智能活动的规律,构造具有一定智能的人工系统,研究如何让计算机去完成以往需要人类智力才能胜任的工作。
人工智能的发展划分为:
孕育期(1956年前)
形成期(1956年-1969年)-达特茅斯会议
发展期-基于知识的系统
实用期-神经网络的复兴
智能主体的兴起
符号主义:(AI研究的传统观点)强调物理符号系统,思维过程是富符号模式的处理过程。
联接主义:又称仿生学派,强调神经元的运作。
行为主义:智能行为的基础是“感知-行动”,是在与环境的交互作用中表现出来的。
人工智能的主要研究领域:
专家系统 数据挖掘 语义web 自然语言理解 机器人 模式识别 智能控制 博弈 自动证明定理
第二章:
知识表示知识表示是数据结构及其处理机制的综合
知识表示=符号(结构)+处理机制
基本的知识表示方式
谓词逻辑表示法 产生式表示法 语义网络表示法 框架表示法
脚本 状态空间表示法 面向对象的知识表示
产生式规则
通常用于表示事物间的因果关系;
【基本形式】
IF P then Q 或 P —> Q,其中
P表示规则的条件(或称前提);
Q表示规则激活时应该执行的动作(或得到的结论);
【规则分类】
①前提-结论型
②条件-动作型
产生式系统的组成
把一组产生式放在一起,让他们互相配合,协同作用,一个产生式生成的结论可以供另一个产生式作为已知事实使用,以求得问题的解决,这样的系统称为产生式系统。一般说来,一个产生式系统由以下三个基本部分组成
产生式系统推理机的推理方式有正向推理、反向推理和双向推理三种。
语义网络
1. 类属关系
AKO(A-Kind-of):表示一个事物是另一个事物的一种类型。
AMO(A-Member-of):表示一个事物是另一个事物的成员。
ISA(Is-a):表示一个事物是另一个事物的实例。
2. 包含关系
Part-of,Member-of
3.属性关系
Have:表示一个结点具有另一个结点所描述的属性。
Can:表示一个结点能做另一个结点的事情。
4.时间关系
Before:表示一个事件在一个事件之前发生。
After:表示一个事件在一个事件之后发生。5. 位置关系
Located-on:表示一物体在另一物体之上。
Located-at: 表示一物体在某一位置。
Located-under: 表示一物体在另一物体之下。
Located-inside: 表示一物体在另一物体之中。
Located-outside: 表示一物体在另一物体之外。
6. 相近关系
Similar-to:表示一事物与另一事物相似。
Near-to: 表示一事物与另一事物接近。
7. 因果关系
If-then
8. 组成关系
Compsoed-of
每个学生都学习了一门外语★
1、框架的一般表示结构
框架由描述事物各个方面属性的槽(slot)组成
框架更强调表示事物的内部结构;
语义网络节点更强调表示事物间的关系;
(1)ISA槽
ISA槽用于指出对象间抽象概念上的类属关系。其直观意义是“是一个”,“是一种”,“是一只”……。在一般情况下,用ISA槽指出的联系都具有继承性。
(2)AKO槽
AKO槽用于具体地指出对象间的类属关系。其直观意义是“是一种”。当用它作为某下层框架的槽时,就明确地指出了该下层框架所描述的事物是其上层框架所描述事物中的一种,下层框架可继承上层框架中值或属性。
(3)Instance槽
Instance槽用来表示AKO槽的逆关系。当用它作为某上层框架的槽时,可在该槽中指出它所联系的下层框架。用Instance槽指出的联系都具有继承性,即下层框架可继承上层框架中所描述的属性或值。
(4)Part-of槽
Part-of槽用于指出部分和全体的关系。当用其作为某框架的一个槽时,槽中所填的值称为该框架的上层框架名,该框架所描述的对象只是其上层框架所描述对象的一部分。
第三章
符号说明:
s-初始状态节点
G-搜索图
OPEN-存放待展扩节点的表
CLOSE-存放已被扩展的节点的表
MOVE-FIRST(OPEN)-取OPEN表首的节点作为当前要被扩展的节点n,同时将节点n移至CLOSE表
盲目搜索常用的简单方式:
?宽度优先(基本思想)——扩展当前节点后生成的子节点总是置于OPEN表的后端,即OPEN表作为队列使用,先进先出,使搜索优先向横广方向发展。
?深度优先(基本思想)——扩展当前节点后生成的子节点总是置于OPEN表的前端,即OPEN表作为栈使用,后进先出,使搜索优先向纵深方向发展。
深度优先、宽度优先 比较:
适用场合
深度优先——当一个问题有多个解答或多条解答路径,且只须找到其中一个时;往往应对搜索深度加以限制。
宽度优先——确保搜索到最短的解答路径。
共同优缺点:
?可直接应用一般图搜索算法实现,不需要设计特别的节点排序方法,从而简单易行,适合于许多复杂度不高的问题求解任务。
?节点排序的盲目性,由于不采用领域专门知识去指导排序,往往会在白白搜索了大量无关的状态节点后才碰到解答,所以也称为盲目搜索。
启发式搜索
——1.A算法(掌握)
【基本思想】
设计体现启发式知识的评价函数f(n);
指导一般图搜索中OPEN表待扩展节点的排序:
【评价函数f(n)=g(n)+h(n) (掌握) 】
n-搜索图G中的节点;
f(n)- G中从s经n到ng,估计的最小路径代价;
g(n)- G中从s到n,目前实际的路径代价;
h(n)-从n到ng,估计的最小路径代价;
h(n)值-依赖于启发式知识加以计算;
h(n)称为启发式函数(掌握意义!)。
如何用评价函数来实现A算法? ( 掌握!)
A算法的设计与一般图搜索相同,划分为二个阶段:
1、初始化
建立只包含初始状态节点s的搜索图G:={s}
OPEN:={s}
CLOSE:={}
2、搜索循环
MOVE-FIRST(OPEN)-取出OPEN表首的节点n
⑥扩展出n的子节点,插入搜索图G和OPEN表 对每个子节点ni,计算f(n,ni)=g(n,ni)+h(ni)
⑦适当的标记和修改指针(子节点?父节点)
⑧排序OPEN表(评价函数f(n)的值排序)
通过循环地执行该算法,搜索图会因不断有新节点加入而逐步长大,直到搜索到目标节点
A算法的可采纳性——定义f*(n)=g*(n)+h*(n)
n-搜索图G中最短解答路径的节点;
f*(n)- s经节点n到ng的最短解答路径的路径代价;
g*(n)-该路径前段(从s到n)的路径代价;
h*(n)-该路径后段(从n到ng)的路径代价;
A*算法定义:
1、在A算法中,规定h(n)≤h*(n);
2、经如此限制以后的A算法就是A*算法。
A*算法是可采纳的,即总能搜索到最短解答路径
启发式函数的强弱及其影响
定理:解决同一问题的两个A*算法A1和A2,
若h1(n) ≤ h2(n) ≤ h*(n)且g1(n)=g2(n)
则t(A1) ≥ t(A2)
其中,h1、h2分别是算法A1、A2的启发式函数,t指示相应算法到达目标状态时搜索图含的节点总数。
h(n)接近h*(n)的程度——衡量启发式函数的强弱
A*算法搜索问题解答的关键
h(n)在满足h(n) ≤ h*(n)的条件下,越大越好!
问题规约:是由初始问题出发,运用操作算子产生一些子问题,对子问题再运用操作算子产生子问题的子问题,这样一直进行到产生的问题均为本原问题,则问题得解。
启发式函数的强弱及其影响
定理:解决同一问题的两个A*算法A1和A2,
若h1(n) ≤ h2(n) ≤ h*(n)且g1(n)=g2(n)
则t(A1) ≥ t(A2)
其中,h1、h2分别是算法A1、A2的启发式函数,t指示相应算法到达目标状态时搜索图含的节点总数。
算法AO*与A*的比较★
解图——解答路径
估计代价最小的局部解图加以优先扩展——OPEN表中f(n)最小的节点;
只考虑评价函数f(n)=h(n)——同时计算分量g(n)和h(n),
应用LGS存放待扩展局部解图,并依据fi(n0)值排序——应用OPEN表和CLOSE表分别存放待扩展节点和已扩展节点,并依据f(n)值排序OPEN表。
MINMAX基本思想:
(1)当轮到MIN走步的节点时(取与时),MAX应考虑最坏的情况(即f(p)取极小值)。
(2)当轮到MAX走步的节点时(取或时),MAX应考虑最好的情况(即f(p)取极大值)。
(3)评价往回倒推时,相应于两位棋手的对抗策略,交替使用(1)和(2)两种方法传递倒推值。
所以这种方法称为极大极小过程。
α-β过程就是把生成后继和倒推值估计结合起来,及时剪掉一些无用分支,以此来提高算法的效率。
第四章
谓词公式永真性和可满足性概念:
永真永假:如果谓词公式P,对个体域D上的任何一个解释都取得了真值(假值),则称P在D上是永真的(永假的);如果公式P在每个非空个体域上均为永真(永假),则称P永真(永假的)。
可满足:对于谓词公式P,如果至少存在一个解释使得公式P在此解释下的真值为真,则称公式P是可满足的。
连词优先级别是?非,∧、∨,蕴含,等价,但可通过括号改变优先级。
设C1=L、 C2=?L,则归结式C为空;
以□表示为空的归结式C,并称C=□为空子句;
因为C1和C2是一对矛盾子句,不可同时满足,所以□是不可满足的子句;
通过往S中加入□而产生的扩展子句集S’不可满足;
空子句□是用归结原理判定子句集S不可满足的成功标志。
空子句是不可满足(即永假)的子句
归结反演的基本思路:
要从作为事实的公式集F证明目标公式W为真;
①先将W取反~W ,加入公式集F;
②标准化F∧~W为子句集S;
③通过归结演绎证明S不可满足,得出W为真的结论。
第五章
要实现对不确定性知识的处理,要解决
不确定知识的表示问题
不确定信息的计算问题
不确定性表示
计算的语义解释问题
3种不确定推理方法(不同的确定性程度定义):
主观Bayes方法
可信度方法
证据理论
LS——充分性因子
=1:O(Q/P)=O(Q),P对Q无影响;
>1:O(Q/P)>O(Q),P支持Q;
<1:O(Q/P)<O(Q),P不支持Q;
LN——必要性因子
=1:O(Q/﹁P)=O(Q),﹁P对Q无影响;
>1:O(Q/﹁P)>O(Q),﹁P支持Q;
<1:O(Q/﹁P)<O(Q),﹁ P不支持Q;
主观Bayes:
分段线性插值:
可信度定义:
⑴规则的不确定性
MYCIN提出的可信度方法中,推理规则表示为:
IF E THEN H,CF(H,E),其中:
证据E——命题的合取∧和析取∨组合;
结论H——单一命题;
CF(H,E)——确定性因子,简称为可信度,证据E为真的情况下,结论F为真的可能程度;
CF(H,E)=MB(H,E)-MD(H,E)
⑴MB(H,E)=a——信任度量
证据E成立使结论H的可信度增加了数量a;
⑵MD(H,E)=b ——不信任度量
证据E成立使结论H的不可信度增加了数量b;
信任函数Bel
Bel(A)=A的所有子集B的基本概率m(B)之和;
Bel(A)表示当前证据下,假设集A的综合信任度;
②似然(真)函数Pl
Pl(A)表示A非假的信任程度
表示对A不知道是真是假的程度:
[Bel(A),Pl(A)]来综合描述A的不确定性;
3个特殊区间:
[1,1]:信任A为真;
[0,0]:信任A为假;
[0,1]:对A是真是假一无所知;
[1,0]:错误
假设集A的类概率函数f(A)
其中:|A|:假设集A包含元素的个数;
|U|:论域U包含元素的个数;
第六章
学习系统的基本结构如图所示
机器学习所采用的策略可分为: 机械学习 示教学习 类比学习 示例学习
归纳学习(induction learning)是应用归纳推理进行学习的一种方法。根据归纳学习有无教师指导,可把它分为示例学习和观察与发现学习。前者属于有师学习,后者属于无师学习。
归纳学习的双空间模型
①特化搜索
从最泛化的假设(概念描述)出发;
每次取用一个新的例子,产生一些特化的描述;
直到产生出足够特化的解描述;
②泛化搜索
从最特化的假设(例子空间中的一个正例)开始;
每次取用一个新的例子,产生一些泛化的描述;
直到产生出足够泛化的解描述。
“泛化策略”:
采用宽度优先、自底向上的搜索方式;
“特化策略”:
采用宽度优先、自顶向下的搜索方式;
【相同点】
新例子的加入会导致新假设的增加和已存在假设的删除 ;
正例——剪裁过于特化的假设。
反例——生成一些特化假设
优点:分类和测试速度快,特别适合于大数据库的分类问题。
缺点:决策树的知识表示不如规则那样易于理解;两颗决策树进行比较,以判断它们是否等价的问题是子图匹配问题,是NP完全的;不能处理未知属性值的情况;对噪声问题没有好的处理方法。
1把以下合适公式化简为合取范式的子句集:
(1)Ø (" x)($ y)($ z){P(x) Þ (" x)[Q(x, y) Þ R(z)]}
(2) ( " x)( $ y){{P(x) Ù [Q(x) Ú R(y)]} Þ (" y)[P(f(y)) Þ Q(g(x))]}
(3) ("x)( $y){P(x) Ù [Q(x)Ú R(y)]}Þ (" y){[P(f(y))Þ Q(g(y))]Þ (" x)R(x)}
(1) · Ø("x)( $y)( $z){P(x) Þ ("x)[Q(x,y) Þ R(z)]}
· Ø("x)( $y)( $z){ ØP(x) Ú ( "x)[ØQ(x,y) Ú R(z)]}
· ($x)( "y)( "z){ P(x) Ù ($ x)[Q(x,y) Ù ØR(z)]}
· P(A) Ù [Q(f(y,z), y) Ù ØR(z)]
· {P(A), Q(f(y,z),y), Ù ØR(w)}
(2) · ("x)($y){{P(x) Ù [Q(x) Ú R(y)]} Þ ("y)[P(f(y)) Þ Q(g(x))]}
· ("x)($y){Ø{P(x) Ù [Q(x) Ú R(y)]} Ú("y)[ØP(f(y)) Ú Q(g(x))]}
· ("x)($y){ØP(x) Ú [ØQ(x) Ù ØR(y)] Ú
("w)[ØP(f(w)) Ú Q(g(x))]}
· ("x){ØP(x) Ú [ØQ(x) Ù ØR(h(x))] Ú
("w)[ØP(f(w)) Ú Q(g(x))]}
· [ØP(x) Ú ØQ(x) Ú ØP(f(w)) Ú Q(g(x))] Ù
[ØP(x) Ú ØR(h(x)) Ú ØP(f(w)) Ú Q(g(x))]
· {ØP(x1) Ú ØQ(x1) Ú ØP(f(w1) Ú Q(g(x1)),
ØP(x2) Ú ØR(h(w2)) Ú ØP(f(w2)) Ú Q(g(x2))}
(3) · ("x)($y){P(x) Ù [Q(x) Ú R(y)]} Þ
("y){[P(f(y)) Þ Q(g(y))]Þ("x)R(x)}
· Ø("x)($y){P(x) Ù [Q(x) Ú R(y)]} Ú
( "y){Ø[ØP(f(y)) Ú Q(g(y))] Ú ("x)R(x)}
· ($x)("y){ ØP(x) Ú [ØQ(x) Ù ØR(y)]} Ú
("w){Ø[ØP(f(w)) Ú Q(g(w))] Ú ("v)R(v)}
· {ØP(A) Ú[ØQ(A) Ù ØR(y)]} Ú
{[P(f(w)) Ù ØQ(g(w))] Ú R(v)}
· ØP(A) Ú {[ØQ(A) Ú P(f(w))] Ù [ØQ(A) Ú ØQ(g(w))] Ù
[ØR(y) Ú P(f(w))] Ù [ØR(y) Ú ØQ(g(w))]} Ú R(v)
· {ØP(A) Ú ØQ(A) Ú P(f(w1)) Ú R(v1),
ØP(A) Ú ØQ(A) Ú Q(g(w2)) Ú R(v2),
ØP(A) Ú ØR(y3) Ú P(f(w3)) Ú R(v3),
ØP(A) Ú ØR(y4) Ú Q(g(w4)) Ú R v4)}
2假设已知下列事实:
1) 小李(Li)喜欢容易的(Easy)课程(Course)。
2) 小李不喜欢难的(Difficult)课程。
3) 工程类(Eng)课程都是难的。
4) 物理类(Phy)课程都是容易的。
5) 小吴(Wu)喜欢所有小李不喜欢的课程。
6) Phy200是物理类课程。
7) Eng300是工程类课程。
请用归结反演法回答下列问题:
1) 小李喜欢什么课程?
2) 证明小吴喜欢Eng300课程
将已知事实形式化表示为合适公式:
(1) ("x)[Course(x) Ù Easy(x) Þ Like(Li,x)];
(2) ("x)[Course(x) Ù ØEasy(x) Þ ØLike(Li,x)];
(3) ("x)[Course(x) Ù Eng(x) Þ ØEasy(x)];
(4) ("x)[Course(x) Ù Phg(x) Þ Easy(x)];
(5) ("x)[Course(x) Ù ØLike(x) Þ Like(Wu,x)];
(6) Course(Phy200) Ù Phy(Phy200);
(7) Course(Eng300) Ù Eng(Eng300);
· 问题表示为以下合适公式(目标公式):
(1)( $x)[Coure(x) Ù Like(Li,x)];
(2)Like(Wu),Eng300);
· 将所有事实和对应于问题的目标公式取反加以化简,并标准化为合取范式子句集:
(1) ØCourse(x1) Ú ØEasy(x1) Ú Like(Li,x1);
(2) ØCourse(x2) Ú Easy(x2) Ú ØLike(Li,x2);
(3) ØCourse(x3) Ú ØEny(x) Ú ØEasy(x3);
(4) ØCourse(x4) Ú ØPhy(x4) Ú Easy(x4);
(5) ØCourse(x5) Ú Like(Li,x5) Ú Like(Wu,x5);
(6) Course(Phy200);
(7) Phy(Phy200);
(8) Course(Eng300);
(9) Eng(Eng300);
(10) 目标公式(1)的取反: (1) ØCourse(x6) Ú ØLike(Li,x6);
(11) 目标公式(2)的取反: (1) ØLike(Wu,Eng300);
· 解决问题(1)
令(10)的取反为:Ask(x6)=Course(x6) Ù Like(Li,x6)
提取的问题回答为: Course(Phy200) ÙLike(Li,Phy200)
即小李喜欢Phy200课程.
· 解决问题(2)
3.对于规则P Þ Q,已知p(Q)=0.04,LS=100,LN=0.4,利用主观Bayes方法求出P(Q/P)和p(Q/ØP):
O(θ/P)=LS*O(θ)=100*0.04/(1-0.04)=4.2
P(θ/P)=O(θ/P))/(1+O(θ/P))=4.2/5.2=0.81
O(θ/¬P)=LN*O(θ)=0.4*0.04/(1-0.04)=0.017
P(θ/¬P)=O(θ/¬P)/(1+O(θ/¬P))=0.017/1.017=0.017
4.在上题中,若P自身的确定性依赖P’,且有p(P)=0.05,规则P’Þ P的LS=120,LN=0.3,用观Bayes方法求出P(θ/P')。
(1).求P(P/P')
O(P/P')=LS*O(P)=120*0.05/(1-0.05)=6.4
P(P/P')=O(P/P')/(1+O(P/P'))=6.4/7.4=0.87
(2).求P(θ/P')
因为P(P/P')=0.87> p(P),根据
P(θ/P')=0.04+(0.81-0.04)*(0.87-0.05)/(1-0.05)=0.04+0.66=0.70
5. 在MYCIN中,设有如下规则:
R1: IF E1 THEN H (0.8)
R2: IF E2 THEN H (0.6)
R3: IF E3 THEN H (-0.5)
R4: IF E4 AND (E5 OR E6) THEN E1 (0.7)
R5: IF E7 AND E8 THEN E3 (0.9)
在系统运行中已从用户处得CF(E2)=0.8, CF(E4)=0.5, CF(E5)=0.6, CF(E6)=0.7, CF(E7)=0.6, CF(E8)=0.9, 求H的综合可信度CF(H)。
解 (1)求证据E4,E5,E6逻辑组合的可信度
(2)根据规则R4,求CF(E1)
(3)求证据E7,E8逻辑组合的可信度
(4)根据规则R5, 求CF(E3)
(5)根据规则R1, 求CF1(H)
(6)根据规则R2, 求CF2(H)
(7)根据规则R3, 求CF3(H)
(8)组合由独立证据导出的假设H的可信度CF1(H),CF2(H)和CF3(H),得到H的综合可信度:
6.设学生考试成绩的论域为{A,B,C,D,E},小王成绩得A、得B、得A或B的基本概率分别分配到0.2、0.1、0.3,Bel({C, D, E})为0.2;请给出Bel({A, B})、Pl({A, B})和f({A, B})。
答:Bel({A, B}) = m({A}) + m({B}) + m({A, B}) = 0.2 + 0.1 + 0.3 = 0.6
Pl({A, B})= 1 - Bel({C, D, E}) = 1 - 0.2 = 0.8
f({A, B}) = Bel({A, B}) + |{A, B}| / |U| · [Pl({A, B}) -Bel({A, B})] = 0.6 + 2/5 ·(0.8 - 0.6) =0.6 + 0.08 = 0.68
人工智能学习心得今天是我学习人工智能的第一堂课也是我上大学以来第一次接触人工智能这门课通过老师的讲解我对人工智能有了一些简单的感性…
1PROLOG程序一般由一组事实规则和问题组成事实一般表示对象的性质或关系规则一般表示对象间的因果关系蕴含关系或对应关系问题表示用…
1谈谈你对于人工智能的认识人工智能就是人造智能目前指用计算机模拟或实现的智能因此人工智能又称机器智能人工智能在我看来应该是像人一样…
第一章什么是人工智能智能就是在巨大的搜索空间中迅速找到一个满意解的能力即是知识和智力的总和智能的特征1感知能力2记忆与思维能力3学…
11什么是人工智能人工智能ArtificialIntelligence是利用设备或机器用人工的方法对人脑的思维活动过程进行模拟当使…
51简述机器学习十大算法的每个算法的核心思想工作原理适用情况及优缺点等1C45算法ID3算法是以信息论为基础以信息熵和信息增益度为…
形象思维抽象思维灵感思维人工智能的核心内容搜索技术推理技术知识表示人工智能语言应用领域专家系统知识库系统决策支持系统自然语言理解智…
1人工智能是何时何地怎样诞生的19xx年夏季美国的一些从事数学心理学计算机科学信息论和神经学研究的年轻学者汇聚在Dartmouth…
深圳大学硕士研究生课程作业人工智能人工智能学习报告深圳大学机电与控制工程学院彭建柳学号09430102101引言人工智能Artif…
人工智能及其应用课程总结20世纪40年代计算机的发明揭开了人类发展的新篇章使得人类追寻已久的脑力劳动机械化问题获得了解决的方法和途…