《人工智能基础课件》由会员分享，可在线阅读，更多相关《人工智能基础课件（67页珍藏版）》请在金锄头文库上搜索。
1、人工智能基础人工智能基础-数模组张哲What is AI?What is AI?AI可归为以下四种：像人一样思考理性的思考像人一样行动理性的行动类人行为：类人行为：Turing TestTuring Test图灵测试是阿兰图灵提出的，目的是为智能提供一个满足可操作要求的定义。计算机需具以下能力：自然语言处理，知识表示，自动推理，机器学习，计算机视觉，机器人技术。类人思考：认知模型方法类人思考：认知模型方法1960s“认知科学”：信息处理心理学。需要深入了解人类思维。两种途径：内省和心理测试。理性思考：理性思考：“思维法则思维法则”亚里士多德：什么是正确思考的途径？（不能辩驳的推理过程)被后人发
2、展创立逻辑学。19世纪的逻辑学家发展处一种描述世界上的一切事物及其彼此之间关系的精确地命题符号。将非形式化的知识转化成形式化的逻辑符号。理性行动：理性智能体理性行动：理性智能体理性智能体是能够感知并行动的实体，即讲感知历史转化为行动的函数：f:P*A对于每一个给定的环境和任务，我们寻求最高性能的智能体。智能体有基于反射型的，基于目标型的，基于效用的，基于学习的。AI prehistoryAI prehistory哲学逻辑，推理的方法，思维作为学习、语言、理性的物理性基础。数学正式的描述和证明算法、计算、可判定性、易处理性、概率。经济学效用和决策理论。神经科学神经活动的物理基础心理学感知和动力控
3、制的现象计算机科学 制造快速的计算机控制论设计能最大化目标函数的系统语言学知识描述，语法AIAI简史简史1943年，McCuulloch&Pitts:人工神经元模型。1950年，Turing的“计算机器与智能”。1956年，达特茅斯会议，人工智能的诞生。1950s，早期的AI程序。19661973年，AI陷入了计算复杂度，曾一度消失。1980年，AI成为工业。1986年，人工神经网络再度流行。1987年，AI成为科学。State of the artState of the artIBM公司的深蓝击败国际象棋冠军Kasparov。计算机系视觉系统被训练用于驾驶汽车沿车道行进，导航穿越美国285
4、0英里。在1991年的波斯湾危机中，美国用AI技术完成自动后勤规划和运输调度，花了几小时完成旧方法需要几个星期任务。NASA远程智能体程序成为第一个船载自助规划程序，控制航天器的操作调度。用搜索法求解问题用搜索法求解问题基于目标的智能体。先讨论无信息的。渐进复杂性（O()符号），和NP完全性问题。ExampleExample：the 8-puzzlethe 8-puzzleState?Actions?Goal test?Path cost?N-puzzle问题的理想解是NP难问题。Tree search algrithmsTree search algrithmsGeneral tree se
5、archGeneral tree search度量问题求解的性能度量问题求解的性能完备性最优性时间复杂度空间复杂度时间和空间复杂度衡量指标：分支因子(b)最浅的目标节点的深度(d)状态空间中任何路径的最大长度(m)无信息的搜索策略无信息的搜索策略无信息的搜索策略只用到问题定义中已给的信息。广度优先搜索代价一致优先搜索深度优先搜索深度有限搜索迭代深度优先搜索双向搜索广度优先搜索广度优先搜索代价一致优先搜索代价一致优先搜索广度优先总是先扩展深度最浅的未扩展节点。代价一致优先搜索关心的是路径消耗最低的节点。深度优先搜索深度优先搜索深度有限搜索深度有限搜索迭代深度有限搜索迭代深度有限搜索Iterati
6、ve deepening search Iterative deepening search l l=0=0Iterative deepening search Iterative deepening search l l=1=1Iterative deepening search Iterative deepening search l l=2=2Iterative deepening search Iterative deepening search l l=3=3Summary of algrithmsSummary of algrithms重复状态重复状态不能检测出重复状态会将一个线性
7、的问题转化成一个指数的问题。Graph searchGraph search有信息的搜索有信息的搜索还可称为启发式的搜索。是一种在问题本身的定义之外还利用问题的特定知识的策略。最佳优先搜索最佳优先搜索Idea：对每个节点采用评估函数f(n)-对于期望的估计-扩展估计值最高的节点先对节点排序Romania with step costs in kmRomania with step costs in km贪婪最佳优先搜索贪婪最佳优先搜索评价函数f(n)=h(n)=从节点n到目标的耗费的估计E.g.，h(n)=straight-line distance from n to Bucharest贪婪
8、最佳优先搜索扩展看上去最接近目标的节点A*A*搜索搜索Idea：避免拓展那些已经耗费很大的节点。评价函数：f(n)=g(n)+h(n)g(n)从起始节点到节点n的路径耗散h(n)从节点n到目标节点的最低耗散路径的估计耗散值f(n)经过节点n的最低耗散解的估计耗散A*A*搜索例子搜索例子一致性启发式一致性启发式h(n)是一个一致性启发式，也就是h(n)不会过高估计到达目标的耗散，那么A*算法是最优的。最优性证明最优性证明假设节点n是在到达目标节点G的最短路径上但并未被扩展，而节点G2不在最短路径上被扩展。设最短路径长为C*。通过G2的所有路径长C*f(n)=g(n)+h(n)我们可以在状态空间上
9、绘制等值线。以同心带状增长f耗散值的方式添加节点。Properties of A*Properties of A*Complete?Yes(unless there are infinitely many nodes with f f(G)Time?ExponentialSpace?Keeps all nodes in memoryOptimal?Yes启发式函数启发式函数E.g.,for the 8-puzzle:h1(n)=不在位的棋子数h2(n)=曼哈顿距离之和(i.e.,no.of squares from desired location of each tile)h1(S)=?8h
10、2(S)=?3+1+2+2+2+3+3+2=18 如果对于所有节点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局部搜索算法局部搜索算法然而有很多问题中，到达目标的路径是无关的。例如，在八皇后问题中，重要的是最终皇后的布局，而不是加入皇后的次序。这种情况下，我们可以采用局部搜索算法。从一个当前状态（而不是多条路径）出发，通常只移动到与
11、之相邻的状态。Example:Example:n n-queens-queensPut n queens on an n n board with no two queens on the same row,column,or diagonal爬山法搜索爬山法搜索爬山法搜索爬山法搜索问题：取决于初始状态，容易停留在局部最大值。Hill-climbing search:8-queens problemHill-climbing search:8-queens problem启发式耗散h=能相互攻击的皇后对数h=17 for the above stateHill-climbing search:
12、8-queens problemHill-climbing search:8-queens problemA local minimum with h=1可以通过重新随机开始改善模拟退火算法模拟退火算法Idea：通过允许一些坏的移动脱离局部极大值但是会逐渐降低坏方向移动的频率。模拟退火算法模拟退火算法能够证明：当T减少得足够慢时，模拟退火算法达到全局最优的可能性接近1。局部剪枝搜索局部剪枝搜索记录k个状态而不是一个。由k个随机生成的状态开始。每次都生成全部K个状态的所有后继状态。如果其中一个是目标状态，算法就停止。否则，从整个后继列表中选择k个最佳的后继。遗传算法遗传算法把两个父状态结合来生成后继。从k个随机生成的状态开始（种群）。用一个有限长度的字符串表示(通常是0、1串）。每个状态都有它的评价函数（适应度函数）给出评价值。通过杂交，选择，变异来产生后代。Genetic algrithmsGenetic algrithms适应度函数：不可相互攻击皇后队数（min=0,max=8*7/2=28）24/(24+23+20+11)=31%Genetic algrithmsGenetic algrithms
