教程-人工智能第12章讲稿

1、第一章 引言 1.1 人工智能研究什么？ 关于人工智能的 强定义和弱定义强： 可以让机器THINKING 、ACTING LIKE HUMAN ； 哲学、科学问题，人的心智是如何工作的，能够建造人工心智吗？ *AI是探讨HUMAN THINKING AND HUMAN ACTIVITIES 中那些尚未算法化的功能行为.。永远地 探索下去。*人脑的思维推理过程的机械化？*大脑的意识是什么？ *计算机能够有自觉性和意识吗？直觉和快速反应的原因？ 未自觉意识到推理步，和脑中进行了复杂推理步骤，两者并不矛盾。弱 ：让计算机成为有效的TOOLS FOR SIMULATING AND MODELING H

2、UMAN THINKING AND HUMAN ACTIVITIES； 工程问题 复杂系统的结构、功能和智能行为: o 结构，（由部分到全体，由元件及互连到系统的 构成规律; 结构互连与 系统功能、系统行为的关系）； o 功能，（I/O,作用，任务，目标）； o 智能行为，（物理的或信息的运动过程）； 输入、输出的反应序列；1.2 哲学和科学中 研究 思维和智能的本质 使用 逻辑学方法、心理学的方法、非线性动力学系统的方法、等 多学科：哲学，心理学，脑科学，逻辑，认知科学，神经生理学，语言学，计算语言学，人 工智能，非线性科学混沌Chaos ）研究 thinking ，thought ，rea

3、soning 思想、思维能力、推理能力,mind心智，意识， intelligence 智力，聪明,intentionality，consciousness 自我意识意识、自我理解是大问题：Chinese Room Problem懂得怎样做 懂得自己作了什么例子 英翻中房间翻译和理解 Chinese Room Problem人工建造的复杂系统是否能够具有意识，懂得自己在干什么？一个房间内，有只懂得英文的一个人，一叠用英文写的翻译规则和符号对照表等书籍，一叠白纸；一个小窗能够递进递出薄的纸片；房间进行翻译工作；在外部看，这个房间是正在进行中文翻译工作，但是假定该人不懂中文，书籍和表格等也谈不上懂

4、得中文，那么直觉上，我们认为这个房间的工作没有任何谈得上具有理解understanding 中文的工作。因此，这例子说明，虽然系统功能上正常运行并解决问题，但谈不上系统对其问题任务有任何理解。*Turing Test，图灵测试的意义Alan Turing 1950提出，假设 1机器和人双方没有物理接触2可以间接交流信息（打字机）3机器是否能够让人以为人是在和另一个人交流问题？*图灵认为在2000年以前，可能构造计算机和人们交谈5分钟，并有30%的把握可以FOOL人。全面图灵测试( 再加摄象机和行动机器人) 他的支持派的研究成果: *自动逻辑推理 :推理机械化 ；三段论，演绎逻辑推理,研究逻辑思

5、维规律；1965年光景，Robinson给出horn子句的refutation 半完全性定理.但表达不完整知识，推理的时空爆炸性等仍困难 他的反对派。存在计算机不可能解决的问题：(无法算法化的)图灵:停机问题;(存在着计算机不能通用求解的问题类)LUCAS提出:GODEL不完全定理说明人比计算机高明，任意的形式化的公理系统(一组公理加一组推理规则)F都可能构造一个GODEL命题 G(F): G(F) 是F中的合法句子, 且如果F是无矛盾的,则 G(F)在F中是真的，且 不能被F所导出; 例系统 ：对象A,B,C; 关系=,; 且遵循传递律; 已知X=B; B=C; 问句子F： X =C ？验证

6、F为真(验证时相同对象可替换)? 可以导出否?*图灵测试的意义：研究智能行为使实验研究成为可能数学家的发明新形式系统的直觉灵感可能算法化吗?大脑和机器的本质区别是什么?是大脑的复杂物理结构和物理运动的系统复杂性产生思维吗?大脑的意识是什么？计算机能够有自觉性和意识吗？意识：知道自己的当前思维状态和行动状态；怎样评判有无意识？会写作意味着，不仅是写作本身，而且是知道自己写了什么； 你无法知道别人的内部思维状态。 科学实验无法肯定或否定它,空调器和温血动物中的温度调节，有没有思维状态？空调器喜欢气候凉爽、期望温度会往下降，一个科学实验的各个阶段需要得到有关直觉和意识的测量数据,但它“测量”-本身会

7、严重影响 直觉和意识。 知觉、自觉性、意识conscious等，不可分解性： 目前无法把意识分解为其他组成部分：红、痛、面包香味等分解为更小的部分 思维状态mental state它和大脑的物理状态之间不是一一对应的：在生 理上的新陈代谢、个别细胞的死亡，不影响知识、技能和感知经验的状态大问题：意识和行为的关系，意识影响行为吗？ 思辩性问题：碳脑到硅脑的神经细胞置换实验。假定科学发展到某一天，大脑内的生物神经元、生物神经构件已经可以被硅等价物所替换，而且可以使大脑整体行为上完全不发生改变。 试问： 受试者的意识最终会有改变吗？ 两种回答：不变，硅脑和碳脑意识完全相同 （计算机完全可能有意识）

8、变， 硅脑和碳脑的意识不同，那么意识在碳硅替换过程中何时发生改变？ 何时？突然变化或渐变（！），很大可能是渐变； 那么意识的渐变会影响行为吗？意识影响行为吗？可能的回答：是！行为会相应变化 基于神经生理学的研究：神经元的基本结构和基本功能，对于低级动物到高级动物，结构和功能在进化，但没有大的区别。低级动物没有意识，只有自适应分辨式adaptive的能力，在进化的哪一级出现了意识？1.3 人工的智能 建造人工的智能，使计算机具有和人相类似的，对事件和环境的反应和行动的 理性反映能力（行为表现）研究方法的特点是 逻辑，数学和工程， 研究方法具有工程的特点：难解问题的近似解决算法研究如何用计算机解决

9、需要人的复杂智慧才能解决的问题具有合理的思维能力，思维不发神经。已知的知识和给定的目标， 具有合理的行动能力。合理性，RATIONAL 虽然可能有时犯错误，但可被接受。 人工智能困难：知识的复杂性; 表达不完整知识; 推理的时空爆炸性; 学习; 规划; 多主体通信等， 没有可靠的理论。当前人工智能的现状 重要挑战问题GRAND CHALLENGE: Knowbots / Infobots Intelligent Help Desks理解你需要什么信息，Natural Language Understanding (NLU)好的翻译 必须理解内容，NL-Generating 说话人是带感情的 Q

10、ualitative Reasoning量和质， Machine Vision空间关系和时间关系, Machine Learning,归纳，类比 等等*计算机打败国际象棋大师 1996*旅行社的旅游咨询顾问（online的语言问答，由boston到旧金山，结果票价节省 1994）*Voyager探险者号，Marvel实时专家系统发现了一个重要问题，提前发出警告 1992*小汽车以每小时55英里的速度向前，驾驶员坐在旁边没有驾驶。 机器人配有摄象镜头、声纳探测仪、激光测距仪1993*城市交通堵塞及事故警报系统，十字路口 及 路段1994*内科淋巴系统疾病计算机专家系统，对著名专家提供了有益帮助。

11、1991 GOFAI:Good Old-Fashion AI （First-order logic ;rule- based system）；Dreyfus教授对GOFAI提出批评：常识、不确定性、学习、缺乏机器人式的situated agent和环境的交互关系,等等1.4 Agent agent的 P A G E 四部特征 PAGE: Percept,Action,Goal,Environment*具有sensors感知外界环境的能力，（能够获得一个percept sequence），感知序列*具有对环境采取行动的能力，（一组可选的行动，包括为了得到进一步的信息而采取的行动）*加上 具有成功

12、地达到目的（goal）之能力 给出了最终的状态条件，和达到目的的行为过程的评价 Performance Measure*已知关于环境的一部分知识,Knowledge为什么提出Agent Paradigm？ Agent的定义*例如 打扫房间的吸尘机器人 行动：step-forward, direction-turn, tube-suck, 谓词：agent_in(x,y); dirt_in(x,y);agent_facing(d:direction); 函数：DO(行动)： 状态 行动 状态*各种不同应用环境，AGENT的特性大不一样 交通网络的交通疏导; 因特网信息查询; 多个机器人的合作装配

13、; 空间探测; 空调自动调温；打扫房间的吸尘机器人； 软件deamon精灵；*环境的类型：可能是 随时间而改变（动态性），环境可能是无法精确预测的（随机的），环境可 能是要求开放的（应用环境本身可以集成于多种、新的环境中；软件精灵）；离散的（下棋机器 人）或者连续的（ SOCCER ROBOTS 空间争抢、躲避） *AGENT方法是：Conceptualization Paradigm as well as Implementation Technique for Software applications，方法特点：Agents和所在的环境的关系，及时反应能力环境有 随机不确定, 或动态环境

14、，当agent对环境的感知能力不完备，agent对他自己的行动在环境上引起的可能差错、失误 必须有所准备，exception handling reactive对环境能够自动、主动作出反应，对自己的行为和内部状态有控制力goaldirected带有实现规定目标的责任，和为完成任务主动采取行动；Communication, 和其他agent的互相配合，通信协商能力； goaldirected， 和 reactive 两者配合好 , 难objects vs agents两者的区别agent的主动反应能力，多个agents的并行多线程能力；是object基础系统不具备的（除active object

15、）区别：如何 “请求执行” A请求执行 一个行动B：action:“Objects do it for free (A调用它)Agents do it for money（A请B帮忙执行）”理论上说，对于AGENT只看评价性能最优，（谁打赢了SOCCER GAME？） 而不问blief,desire,intention 并不恰当.智能不应该仅仅是事先嵌入的死板知识，从实际经验（历史的感知-行动序列）和环境的状态变化，应该能够适应多类不同的环境, 从环境中学习总结，改进行为.由它过去获得的全部经验（从经验学习）而不是完全基于先验的经验和知识。B-D-I BELIEF-DESIRE-INTENTI

16、ONDESIRE 渴望，愿望d ； 愿望本身应该 持续时间、持续性较久 它和GOAL（目标）性质上有相同处和相异之处 agent希望能够有朝一日实现 在AGENT预期的一些相关可能环境状态中，都有实现此目标d的可能，持 续性, 实现d的办法并不一定已经明确， DESIRE集合中各个di 可以有矛盾不一致；必须经过考虑审量 DELIBERATION后， 才可以得出一组互相一致的GOALSIntention 意图 是 给出的一种性质条件， *具有持续性，在不同的时刻具有 持续的意图， * 可满足性，有可能实现， 规定了：该AGENT所向往的各种可 能发展前途中，int应该成立 agent的行动是和

17、满足int密切相关的； * 但是，如果agent的知识不够或者由于环境的其他干扰， 行动的结果将无法保证一 定满足int，可能是不成功的；Belief 信念b, Agent对一组可能世界状态的描述，在这可能世界集合中，对 Agent 而言，他相信都具有性质b; Agent所具有的信息，是有关他的环境 的信息，belief可以用于选择行动的决策 *对于当前世界而言，信念并不保证总是真的，可能被否定或更新 *信念和知识的关系， 知识是当前的事实证据所支持的信念；是真的； * Belief(agent, b)Belief(agent, Belief(agent, b) )Agent 的实现类别* R

18、eactive, Reactive with memory,自动驾驶，空调（目标固定）*Goal-based, 潜艇寻的，目标是用户根据情况才确定*Utility-based, 多目标，评价函数*Problem-Solving，事先规划 第2章目录 问题求解、启发式搜索; 2.1 问题求解; 2.2 通用搜索算法 ; 2.3 启发式搜索第二章 问题求解， 启发式搜索2.1问题求解AGENT问题求解 = 问题的表达 + 求解的控制状态空间 是一种问题的 表达和分析方法:问题的状态空间：从任意一个状态出发，各种任意的操作序列所可以达到的状态集合的全体；问题 = 初态，目标, 为达到目标而可以采取的

19、行动集合 以及 COST函数；问题 = 初始状态集合 + 操作集合 + 测试目标状态的函数 + +对操作序列的评价函数搜索求解：求出由初态到目标态的一个操作序列，满足目标状态条件*搜索树随行动序列而不断展开;*搜索树和搜索网络（有无 相同结点）,？有环的路线 *刚刚出现过的结点不要再展开 *已经出现过的结点不要展开,查验困难搜索树结点的数据结构struct node problem-state-type state; /状态，其内容和具体应用有关node * parent-node; / 指向父结点的指针int the selected operator;/该分支的行动 操作算子int pat

20、h-depth; /自根到此的深度float path-cost; / 自根到此的费用，函数g 搜索策略的时间空间复杂性：问题常常出在空间复杂性 搜索策略的完备和最优性：对解的好坏，有评价函数, 找到解, 和 解是否最优?是否所有各种问题都可以用状态空间问题求解来表达？有些类型的问题并不自然地具有 “状态 行动 新的状态”的 描述形式，例如 *？数学公式演算，公式化简 *？口语翻译Function General_Search ( 问题的初态 ，行动集，目标状态判定函数，选择状态的优先策略） returns solution /可能无解，解集合为空 /初始时，把 (问题的初态集合) 作为搜索树

21、的当前叶结点集合，并 /建立 搜索树的根结点；loop DOIF搜索树已经没有叶结点，或按照(选择状态的优先策略) 全部叶结点都不符合挑选要求 then return failure在搜索树上 按照(状态选择优先策略)选择 一个叶结点 IF 所选叶结点满足(目标状态判定函数) then return solution / 相应的解 else使用(行动集)使所选结点扩展形成它的全部可能叶结 点，放入当前叶结点集合；/当前可扩展候选结点集，一般是一个队列，必须有排序策略 end loop基本搜索方法$广度优先(深度为评价函数)，深度8,分支10:结点一亿个,时间31小时(每个结点费时1 ms),

22、空间11个GBYTE(每个结点100个字节)$双向广度优先（由启始和目标终点同时搜索）$深度优先$增量式深度优先( 深度d, 每一个给定深度d，做深度搜索，但限于= d为止),如果没有解,则把深度常数d加一（d+）后再做. 深度d，ITERATIVE DEEPENING SEARCH2.3 Heuristic启发式搜索Best-first search的含义：所有的前沿结点按照一定结点评价函数排序，最好的被选出加以扩展；一般的搜索算法则只要求能够从新旧前沿叶结点中挑出一个,没有BEST-FIRST要求。 /initial-node函数（prblm-initial-state）:nodes /c

23、urrent-node当前结点 /expand-node函数（parnt-node,prblm-operators）:nodes /Frontier-node-set 结点集，所有已经被父结点扩展出来， / 但是本身尚未扩展的结点,亦即叶结点 /queuing-func(frntier-set,new_nodes): frntier-set nodes; /排序排好new_nodes以及frntier-set; / queuing-func是用于评价结点是否适宜用于当前扩展 /要维护一个前沿结点集合，对此函数queuing-func /的性质未加限制, Function best-first-search (problem, queuing-func) return solutionfrntier-set = initial-node(prblm-initial-state）;loopif frntier-set is empty then return failure;currnt-node = top(frntier-set);if currnt-node satisfies the prblm goal-test then return currnt-node;frntier-set = queuing-func(frntier-set, exp