人工智能入门 课件 7.总结

总结AI:Summary2理解并创造智能实体两种观点:弱AI(图灵测试);强AI(中文屋实验)六种途径:符号智能；人工神经网络;机器学习;行为智能;进化计算;群智能。AI:Summary3S.J.RusselllandP.Norvig,“artificialintelligence:amodernapproach”.具有学习能力的智能系统的架构AI:Summary4大纲路线图1:学习-神经网络-行为智能路线图2:搜索-图搜索-进化计算学习学习意味着变化AI:Summary6AI:MachineLearning6定义学习任务基于经验，根据性能准则，提升完成相应任务的性能任务:下跳棋性能:对于任意对手，取胜的概率

经验:以自己为对手，进行的练习任务:识别手写字性能:被正确分类的字所占的比例经验:经过人工标注的手写字的数据库任务:视觉传感器自动驾驶性能:出错前行驶的平均距离经验:人类驾驶的时候记录下来的一系列图像和对应控制命令AI:Summary7AI:NouvelleAI7学习中的信息反馈类型监督学习学习需要的输入输出对已经给定或者可以推导得到。非监督学习没有输出的信息强化学习智能体在环境中作出行动，对于智能体的每一步行动，都会得到一个评价值，但是不被告知如何行动才可以正确的达到目标。AI:Summary8学习的实质函数估计三个问题1.怎样假设函数形式?2.怎样设计学习目标?3.怎样发现最优函数?AI:Summary9AI:ANN91.1怎样假设函数形式?-1

M-P神经元θx1x2xnyω1ω2ωn输入输出阈值McClloch与Pitts，《神经活动中固有的思想逻辑运算》,1943f:激活函数g:整合函数AI:Summary10AI:ANN10整合函数加权求和

径向距离AI:Summary11AI:ANN11激活函数

阈值型线性饱和线性S型函数双曲正切函数高斯函数AI:Summary12AI:ANN12前馈网络的一般结构反馈网络的一般结构AI:Summary13AI:ANN13单层感知器阈值激活函数输出单元相互独立,即没有共享的权重Rosenblatt,1957AI:Summary14（0,0）（1,-0.5）（1,1.5）（2,0.5）

class1

class24.11设计一个感知器，用于区分两类数据，其中第一类数据是（1,1.5）和（2,0.5），第二类数据是（0,0）和（1,-0.5）输入1输入2输出11.5020.500011-0.51w1w2yx1x2AI:Summary15满足以上约束（只是一种可能）-1-1yx1x2-1AI:Summary16AI:ANN16多层感知器(MLP)层与层之间通常是全连接的隐含层单元的个数通常手动选择AI:Summary17监督学习:-使实际输出与期望输出之间的误差最小

(BP)-最大化信息增益(IG)(决策树)

强化学习:

使长期的累积收益最大非监督学习:

使数据与聚类之间的距离最小

(聚类)1.2怎样设计学习目标?AI:Summary18r(state,action)即时奖励值Q(state,action)valuesV*(state)values100

0

0

100

G

0

0

0

0

0

0

0

0

0

90

81100

G

0

81

72

90

81

81

72

90

81

100

G

90100081901001.3怎样发现最优函数?

使用累计折扣收益，折扣率=0.981=0+0.9*90Q-学习算法AI:Summary19Q值例:Hanoi塔AI:Summary20补充题：以下GridWorld中，除了到达目标状态（G）的动作获得的即时奖励为10以外，其余动作对应的即时奖励皆为0。如采用折扣系数为0.8的累积折扣收益，请计算图中的Q函数值，直接标注在图中。G1086.41086.486.41086.4搜索(最优化)01AI:Summary22什么是搜索?以可以接受的计算代价，在问题所有解答中找出最优解或可行解。理想的搜索算法：尽可能快地找到最优解。求解的效果与效率之间存在矛盾-完备性,最优性,复杂性-盲目vs.启发,局部

vs.全局,可行

vs.最优.AI:Summary23数学和计算机科学中的核心主题确定性搜索-图搜索随机和基于群体的搜索-进化计算-群智能启发式搜索方法AI:Summary24用于问题求解图搜索算法的一般结构是不断扩展顶点，直到发现目标顶点（状态空间）或者确定初始顶点的可解性（与或图）。).不同图搜索算法的主要区别在于顶点的扩展顺序不同。盲目搜索不考虑问题特性,包括广度优先搜索、深度优先搜索、有界深度优先搜索和迭代加深深度优先搜索。启发式搜索算法根据问题所提供的启发式信息，用估价函数估计顶点的搜索效率，选择估计效率最高的顶点进行扩展。2.1图搜索AI:Summary25状态空间vs.与/或图状态空间与/或图AI:Summary262.5为什么采用与或图表示法时，解决问题的答案对应于一个子图，而不是一条路径？答：因为与节点AI:Summary27A*算法是影响最大的，应用于状态空间的启发式搜索算法。它通过对估价函数施加一定约束，可以保证搜索到最优解。可容许的启发式函数:如果对于每一个顶点n都有h(n)≤h*(n)，则该启发式函数h(n)是可容许的。其中h*(n)表示从顶点n到目标顶点的最小代价。支配性:如果对于所有顶点都有

h2(n)≥h1(n)

，并且两者都是可容许的，则h2

优于h1,使用h2

搜索速度更快A*算法AI:Summary282.3请用状态空间法求解农夫过河问题，该问题是：一农夫带着一只狼、一只羊和一筐菜来到河边，欲乘船到河对岸。但船太小，农夫每次只能带一样东西过河。而在没有农夫看管的情况下，狼会吃羊，羊会吃菜。农夫应该怎样做，才能在没有任何损失的情况下把所有东西带到河对岸？2.13试用A*算法解决习题2.3中给出的农夫过河问题。解：问题状态表示为（a,b,c,d），其中a,b,c,d分别表示农夫、狼，羊和菜的位置，1表示在左岸，0表示在右岸。则起始状态为(1,1,1,1)，终止状态为(0,0,0,0)。改变状态的操作共八种，分别为：农夫带着{狼、羊、菜}从{左岸到右岸、右岸到左岸}。搜索路径为：(1,1,1,1)

(0,1,0,1)

(1,1,0,1)

(0,0,0,1)

(1,0,1,1)

(0,0,1,0)

(1,0,1,0)

(0,0,0,0)

AI:Summary29h(x)=河左岸物体个数

或无穷大（≠人：狼、羊对应位不能相等；羊、菜对应位不能相等）(1,1,1,1)h=3f=3(0,0,1,1)h=∞f=∞(0,1,0,1)h=2f=3(0,1,1,0)h=∞f=∞(1,1,0,1)h=2f=4(0,0,0,1)h=1f=4(0,1,0,0)h=1f=4(1,0,0,1)h=∞f=∞(1,0,1,1)h=2f=6(1,1,0,0)h=∞f=∞(1,1,1,0)h=2f=6102345AI:Summary30(1,0,1,1)h=2f=6(0,0,1,0)h=1f=6(0,0,0,1)h=1f=6(1,0,1,0)h=1f=7(1,1,1,0)h=2f=8(0,0,0,0)h=0f=7h(x)=河左岸物体个数

或无穷大（≠人：狼、羊对应位不能相等；羊、菜对应位不能相等）续上图6(1,0,0,1)h=∞f=∞7910(1,1,1,0)h=2f=68AI:Summary31博弈树

表示博弈过程的数据结构

在想象对手是最强对手的情况下采取最好的行动，这在结构上表现为与或图极大极小算法

-限制博弈树的深度-评价博弈状态-选择移动到具有最高极大极小值的位置!α-β剪枝

在有界深度优先搜索过程中，通过剪掉一些不必要的分枝达到提高搜索效率的目的。博弈搜索AI:Summary322.17极大极小搜索的思想基础是什么？为什么博弈子树的深度越深，计算机博弈水平越高？答：思想基础是：假设对方为最强对手，在考虑对方每一步都作出最佳应对的情况下，也就是对自己最不利的情况下（极小），选择能给自己带来最大收益的一步（极大）。原因：子树深度越深，表示思考的步数越多，从而能够得到更好的结果。AI:Summary332.21设有如图所示的一棵博弈树，其中末一行的数字是叶顶点的静态估值，请对该博弈树作如下工作：用极小极大值法计算各节点的倒推值。利用-剪枝技术剪去不必要搜索的分枝。叙述剪枝发生在何处，即剪去了哪些分枝（在剪枝处用×在图上做标记）。

AI:Summary34进化计算基于生物进化理论优化行为—最优解个体

–

解;适应度

–

目标;环境

–

问题EC的组成表示:个体和种群适应度估计:目标选择:父代和子代基因操作:突变和/或重组初始化/终止条件2.2进化计算AI:Summary35AI:EC35进化算法构成tt+1突变重组繁殖选择图片来源IdaSprinkhuizen-Kuyper:Introductionto

EvolutionaryComputation,2000.AI:Summary36AI:EC36进化机制遗传增加了多样性突变重组选择减少了多样性用于繁殖的父代选择生存下来的子代选择AI:Summary37AI:EC37进化中的循环过程重组突变种群子代父代父代选择子代选择图片来源BenPaechter:EvolutionaryComputing–APracticalIntroductionAI:Summary38AI:EC38EC的理想性能图片来源:IntroductiontoStochasticSearchandOptimization(ISSO)byJ.C.SpallAI:Summary39AI:EC39如何构建EA算法?Step1.设计一种表示方法Step2.设计从遗传物质到表现性状的映射关系(不是必需的)Step3.给出适应度函数Step4.设计合理的遗传操作:突变

和/或重组Step5.决定如何选择父代样本和子代样本

Step6.决定如何初始化一个种群以及算法迭代的终止条件AI:Summary40用于八皇后问题的EA算法例123456781234567887642531135246788764512313562874543212647812345678AI:Summary41进化计算的主要特点:并行+随机易于应用进化计算的主要分支：遗传算法进化规划进化策略遗传规划进化计算的主要特点与分支AI:Summary42表示:位串(基因型