人工智能基础.ppt

1、人工智能基础,-数模组张哲,What is AI?,AI可归为以下四种：,类人行为：Turing Test,图灵测试是阿兰图灵提出的，目的是为智能提供一个满足可操作要求的定义。 计算机需具以下能力：自然语言处理，知识表示，自动推理，机器学习，计算机视觉，机器人技术。,类人思考：认知模型方法,1960s“认知科学”：信息处理心理学。 需要深入了解人类思维。 两种途径：内省和心理测试。,理性思考：“思维法则”,亚里士多德：什么是正确思考的途径？（不能辩驳的推理过程) 被后人发展创立逻辑学。 19世纪的逻辑学家发展处一种描述世界上的一切事物及其彼此之间关系的精确地命题符号。 将非形式化的知识转化成形

2、式化的逻辑符号。,理性行动：理性智能体,理性智能体是能够感知并行动的实体，即讲感知历史转化为行动的函数： f: P* A 对于每一个给定的环境和任务，我们寻求最高性能的智能体。 智能体有基于反射型的，基于目标型的，基于效用的，基于学习的。,AI prehistory,哲学逻辑，推理的方法，思维作为学习、语言、理性的物理性基础。 数学正式的描述和证明算法、计算、可判定性、易处理性、概率。 经济学效用和决策理论。 神经科学神经活动的物理基础 心理学感知和动力控制的现象 计算机科学 制造快速的计算机 控制论设计能最大化目标函数的系统 语言学知识描述，语法,AI简史,1943年，McCuulloch

3、& Pitts:人工神经元模型。 1950年，Turing的“计算机器与智能”。 1956年，达特茅斯会议，人工智能的诞生。 1950s，早期的AI程序。 19661973年，AI陷入了计算复杂度，曾一度消失。 1980年，AI成为工业。 1986年，人工神经网络再度流行。 1987年，AI成为科学。,State of the art,IBM公司的深蓝击败国际象棋冠军Kasparov。 计算机系视觉系统被训练用于驾驶汽车沿车道行进，导航穿越美国2850英里。 在1991年的波斯湾危机中，美国用AI技术完成自动后勤规划和运输调度，花了几小时完成旧方法需要几个星期任务。 NASA远程智能体程序成为

4、第一个船载自助规划程序，控制航天器的操作调度。,用搜索法求解问题,基于目标的智能体。 先讨论无信息的。 渐进复杂性（O()符号），和NP完全性问题。,Example：the 8-puzzle,State? Actions? Goal test? Path cost? N-puzzle问题的理想解是NP难问题。,Tree search algrithms,General tree search,度量问题求解的性能,完备性 最优性 时间复杂度 空间复杂度 时间和空间复杂度衡量指标： 分支因子(b) 最浅的目标节点的深度(d) 状态空间中任何路径的最大长度(m),无信息的搜索策略,无信息的搜索策略只

5、用到问题定义中已给的信息。 广度优先搜索 代价一致优先搜索 深度优先搜索 深度有限搜索 迭代深度优先搜索 双向搜索,广度优先搜索,代价一致优先搜索,广度优先总是先扩展深度最浅的未扩展节点。 代价一致优先搜索关心的是路径消耗最低的节点。,深度优先搜索,深度有限搜索,迭代深度有限搜索,Iterative deepening search l =0,Iterative deepening search l =1,Iterative deepening search l =2,Iterative deepening search l =3,Summary of algrithms,重复状态,不能检测出

6、重复状态会将一个线性的问题转化成一个指数的问题。,Graph search,有信息的搜索,还可称为启发式的搜索。 是一种在问题本身的定义之外还利用问题的特定知识的策略。,最佳优先搜索,Idea：对每个节点采用评估函数f(n) -对于期望的估计 -扩展估计值最高的节点 先对节点排序,Romania with step costs in km,贪婪最佳优先搜索,评价函数f(n)=h(n)=从节点n到目标的耗费的估计 E.g.，h(n)=straight-line distance from n to Bucharest 贪婪最佳优先搜索扩展看上去最接近目标的节点,A*搜索,Idea：避免拓展那些已

7、经耗费很大的节点。 评价函数： f(n) = g(n) + h(n) g(n)从起始节点到节点n的路径耗散 h(n)从节点n到目标节点的最低耗散路径的估计耗散值 f(n)经过节点n的最低耗散解的估计耗散,A*搜索例子,一致性启发式,h(n)是一个一致性启发式，也就是h(n)不会过高估计到达目标的耗散，那么A*算法是最优的。,最优性证明,假设节点n是在到达目标节点G的最短路径上但并未被扩展，而节点G2不在最短路径上被扩展。设最短路径长为C*。 通过G2的所有路径长C*f(n)=g(n)+h(n),我们可以在状态空间上绘制等值线。以同心带状增长f耗散值的方式添加节点。,Properties of

8、A*,Complete? Yes (unless there are infinitely many nodes with f f(G) ) Time? Exponential Space? Keeps all nodes in memory Optimal? Yes,启发式函数,E.g., for the 8-puzzle: h1(n) =不在位的棋子数 h2(n) =曼哈顿距离之和 (i.e., no. of squares from desired location of each tile) h1(S) = ? 8 h2(S) = ? 3+1+2+2+2+3+3+2 = 18,如果对于

9、所有节点h2(n) h1(n) ，那么h2(n) 性能更加优势。 搜索耗损（平均扩展节点数） d=12IDS = 3,644,035 nodesA*(h1) = 227 nodes A*(h2) = 73 nodes d=24 IDS = too many nodesA*(h1) = 39,135 nodes A*(h2) = 1,641 nodes,局部搜索算法,然而有很多问题中，到达目标的路径是无关的。例如，在八皇后问题中，重要的是最终皇后的布局，而不是加入皇后的次序。 这种情况下，我们可以采用局部搜索算法。从一个当前状态（而不是多条路径）出发，通常只移动到与之相邻的状态。,Example

10、: n-queens,Put n queens on an n n board with no two queens on the same row, column, or diagonal,爬山法搜索,爬山法搜索,问题：取决于初始状态，容易停留在局部最大值。,Hill-climbing search: 8-queens problem,启发式耗散h =能相互攻击的皇后对数 h = 17 for the above state,Hill-climbing search: 8-queens problem,A local minimum with h = 1 可以通过重新随机开始改善,模拟退火算法,Idea：通过允许一些坏的移动脱离局部极大值但是会逐渐降低坏方向移动的频率。,模拟退火算法,能够证明：当T减少得足够慢时，模拟退火算法达到全局最优的可能性接近1。,局部剪枝搜索,记录k个状态而不是一个。 由k个随机生成的状态开始。 每次都生成全部K个状态的所有后继状态。 如果其中一个是目标状态，算法就停止。否则，从整个后继列表中选择k个最佳的后继。,遗传算法,把两个父状态结合来生成后继。 从k个随机生成的状态开始（种群）。