人工智能理论与应用.pdf

《人工智能理论与应用.pdf》由会员分享，可在线阅读，更多相关《人工智能理论与应用.pdf（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、人工智能理论与应用人工智能理论与应用 张文生张文生研究员研究员/教授教授 中科院自动化研究所 2008年9月 课程安排课程安排 课程的基础部分： 主要讨论人工智能三个基本问题-知识表示、推理与搜索 课程的高级部分： 主要讨论机器学习的若干问题，这取决于课程的时间 基本部分基本部分 符号逻辑、Herbrand定理、Resolution等 启发式搜索理论、推理模型等 知识表示，特别是结构化知识表示，例如：语 义网络与Frame 专家系统原理 高级部分高级部分 主要涉及机器学习： ID3与AQ11* 人工神经网络* 遗传算法* Rough Set 理论 统计机器学习理论 Reinforcement

2、Learning 主曲线 与流形学习 考试方法考试方法 开卷考试 可以阅读任何材料，但是，必须独立完成 考试时间三小时 考试范围，包括本课程的基础部分，以及 高级部分的前三部分 Reference Books Artificial Intelligence: a new synthesis Nils J. Nilsson, 1998 Principle of artificial intelligence, 1982 Morgan Kaufmann Artificial Intelligence: a modern approach Russell, Norvig, 1995 Englewoo

3、d Cliffs, NJ: Prentice Hall Artificial Intelligence(second edition) Rich, Knight, 1991 New York: McGraw-Hill 人工智能 Nilsson著, 郑扣根译, 2000 机械工业出版社 人工智能(上下册) 陆汝钤, 1989, 1995 科学出版社 人工智能原理 石纯一, 黄昌宁, 王家 清华大学出版社 人工智能导论 林尧瑞, 马少平 清华大学出版社 网上资源 书 讲义 BBS 课程安排 1.综述 自动定理证明: 2.命题逻辑与一阶谓词逻辑 3.Herbrand定理 4.归结原理 搜索: 5.产

4、生式系统 6.产生式系统的搜索(一) 7.产生式系统的搜索(二) 8.知识表示 机器学习: 9. 综述, ID3与解释学习 10. 神经网络 11. 遗传算法 12. Rough Sets理论 13. 统计学习理论 14. Reinforcement learning 15. 主曲线 16. 数据挖掘 17: 专家系统 18: 考试 联系方式 Wensheng.zhang 引 言引 言 ?人工智能作为独立的学科(1956年）已经有50多年 的历史，最近发展尤为迅速 ? 当代人工智能的两大支柱：知识表示、搜索技术 ? 知识表示包括： 演绎系统、产生式系统、框架结构、语义网络和过程 性质使得表示等

5、。 ? 搜索技术： 盲目搜索、启发式搜索、博弈树搜索、状态空间搜索、 问题空间搜索等。 目 的目 的 近五十年来，人工智能的研究起起伏伏，新的研究 结果不断出现，同时大量研究被摒弃 历史上，哪些研究至今还是重要的？判断哪类研究 是没有意义的? 了解这些思想与研究，对今后的研究十分重要 提 纲 人工智能之前的研究 人工智能的提出 重要事件 人工智能基础 目前的研究趋势 人工智能之前的研究人工智能之前的研究(1) 十九世纪末James关于神经结构的研究，神 经系统由神经元组成，神经元之间是相互连 接的 二十世纪中叶McCulloch与Pitts对神经元工作 方式的研究，神经元有兴奋与抑制两种状态

6、图 解图 解 McCulloch与与Pitts的研究结果奠定了计 算机科学与技术的基础 的研究结果奠定了计 算机科学与技术的基础 人工智能之前的研究人工智能之前的研究(2) Turing的计算理论与Turing测试 Wiener的控制论 Shannon的信息论 Turing测试测试(1950) 测试者A，被测试者B与C A是人，B与C一个是人，另一个是计算机 A提出问题，B与C分别回答 如果B与C的回答，使得A无法区分是人的回答还 是计算机的回答，则计算机具有了智能 Turing测试第一次给出了检验计算机是否具有智 能的哲学说法 Turing是人工智能之父 Searle的批评的批评(汉语实验室

7、汉语实验室) 一个不懂汉语的人A，一个充分详细的汉语问答手册 不计查手册的时间代价 给A一个使用汉语提出的问题，A通过汉语符号的比 对使用手册，给出回答 Searle问，如果A通过查手册做出的回答与懂汉语的 人一样，A懂汉语吗？ “深蓝深蓝”下棋程序下棋程序 1997年，IBM设计了这个程序 战胜卡斯帕罗夫！ “深蓝”有智能吗？ 媒体与大众认为“有” 科学家认为“没有”，理由恰恰是Searle汉语 实验室 Wiener的控制论的控制论 反馈 对变化环境的适应性 控制的统计特性 计算 计算机科学与控制理论计算机科学与控制理论 计算机科学与控制理论有共同的理念祖先-控制论 Von Neumann与

8、Shannon将Turing的计算理论加入 控制论，形成计算机科学 Ashby将微分方程定性理论加入控制论，形成以稳 定性为基础的控制理论 形成两个不同学科 “人工智能人工智能”提出提出 一般的说，人工智能这个术语来源于1956年 （夏季的）一次关于“复杂信息处理”的 Workshop(达德茅斯大学， MaCarthy 提出Artificial Intelligence这 一名词) 在这次会议上，J.MaCarthy建议将这类研究 称为人工智能 复杂信息处理复杂信息处理 在50年代，计算局限在数值处理，例如，计算弹 道等 1950年，Shannon完成了第一个下棋程序。开创 了非数值计算的先河

9、 Newell, Simon, MaCarthy and Minsky等均提出以 符号为基础的计算 复杂信息处理的任务复杂信息处理的任务 将人的信息加工理解为一种计算 计算机的功能是计算，信息加工是计算，计算机似 乎可以完成人类大脑完成的信息加工任务 符号加工、表示、推理、学习将代替数值计算，成 为计算机的主要用途 复杂信息本质上就是非线性信息，解决非线性问题 是主要任务 人工智能的任务人工智能的任务 根据人类信息加工原理，设计计算系统， 以使计算机完成更复杂的任务 使用计算系统研究人类的思维活动规律 重要事件重要事件 启发式搜索 感知机 基于符号的规则表示 人工智能的主流 适应性 知识发现

10、重要事件重要事件-启发式搜索启发式搜索 1960年，Simon发表了重要的关于启发式搜 索的报告 据此，Newell, Simon and Shaw发表了通用 问题求解器-GPS (General Problem Solver) 启发式搜索启发式搜索 分析中学生解几何习题的口述报告，Simon 认为人类信息加工过程，是在经验知识启示 下，对解空间的搜索过程 经验知识多少，决定了问题求解的有效性， 启发式搜索启发式搜索 科学意义科学意义 启发式搜索的意义：启发式搜索的意义： 揭示了人类信息加工的本质 暗示了一种问题求解的计算模型 决策科学的基础 可接受解代替最优解 这是计算机科学中，对NP完全问

11、题求解需要遵 守的原则之一 重要事件重要事件-感知机感知机 Rosenblatt根据神经系统的工作方式提出了感知机 理论。以此解决机器学习问题 这是一个线性学习理论 Minsky的批评的批评 1969年，Minsky出版Perceptron一书 一方面，他批评感知机无法解决非线性问题，例如 XOR问题 复杂性信息处理应该以解决非线性问题为主 另一方面，几何方法应该代替分析方法作为主要数 学手段 对人工智能研究的影响对人工智能研究的影响 在以后的二十年，感知机的研究方向被忽视 基于符号的知识表示成为主流，例如，规则等 基于逻辑的推理成为主要研究方向 重要事件重要事件-人工神经网络人工神经网络 直

12、到1986年，Rumelhart发现了BP算法，才导致感知 机之类的研究重新兴起 1988年，Minsky重版他的Perceptron，并指出，BP 算法没有解决他在二十年前提出的问题 不幸被他言中了 NP-Hard BP算法是非线性优化算法 非线性优化算法是NP-Hard问题 这意味着，不可能存在一种改进，使得这类算法能 够解决大量数据问题 除非改变算法本身 重要事件重要事件-SVM 1991年，前苏联数学家Vapnik到了西方， 带来了他在1971年的一项研究，统计学习 理论 人们重新认识了感知机与几何在算法设计中 的作用 SVM原理原理 基于泛函分析原理，将样本从欧氏空间映射到 Hilb

13、ert空间 在Hilbert空间定义划分，以使在欧式空间为非线性 划分问题变换为在Hilbert空间为线性划分问题 从而回归到Rosenblatt的感知机 Vapnik的贡献的贡献 奠定了泛化的统计理论 根据泛函分析，提出了核函数的概念，由此，设计 了SVM算法 尽管在理论上，SVM的划分是定义在Hilbert空间， 但是，通过核函数，其计算仅仅依赖于定义在欧式 空间上的样本 问题归结为核函数的选择 基于符号规则的表示基于符号规则的表示 Widrow的Madline模型 Samual的规则表示 Widrow的MADLINE 为了解决XOR问题，Widrow提出使用非光 滑超平面代替连续光滑超平

14、面对样本的划分 其划分对学习来说可能是平凡的 信息长度可能未减少 原 理原 理 重要事件重要事件-规则表示规则表示 尽管Widrow的研究没有获得成功，但是，却 导致基于规则的知识表示的发展 Samual最先提出使用这种知识表示方法，并 使用其设计了下棋程序 影响了二十年人工智能的发展 重要事件重要事件-A*算法 1971年，Nillson提出A*搜索算法 这是对启发式搜索理论的研究结果 这个算法第一次给出了启发式函数对搜索的准 定量描述 没有给出获得启发式知识的途径 启发式搜索启发式搜索 启发式知识是经验的 无需考虑对某个问题的完备性，这意味着，获得 的解可能对给定目标不是最优的 但是，一定

15、是次优的、可接受的 重要事件重要事件-Resolution原理原理 基于符号的表示使得基于逻辑的推理成为可 能 1965年，Robinson根据30年代Herbrand证明 的一个定理，提出了一种相对简单的定理证 明的方法，称为Resolution 不确定推理不确定推理 基于Fuzzy的推理 基于D-S的推理 非单调推理 基于常识的推理 重要事件重要事件-KRL KRL-Knowledge Representation Language 这个研究建立了语义网络、Frame等重要 的知识表示的形式化方法 目前这已成为面向对象程序设计的主要理 论基础之一 知识工程知识工程-专家系统专家系统 197

16、7年，Feigenbuam提出了知识工程概念 在理念上，为专家系统的建立奠定了基础 专家系统已成为人工智能研究的应用 适应性适应性 自从计算机科学与控制理论成为不同学科之后，两 者进行分别研究 计算只是控制研究的工具 计算则完全抛弃了控制的精髓-反馈 近些年，反馈被计算所重视。但是，已不是基于实 数域上的微分方程，而是更为复杂的定义在特定结 构上的反馈 重要事件重要事件-Classifier系统系统 1975年，Holland提出了classfier系统 遗传算法 对变化环境的适应性(桶队算法) 进化计算 复杂性 重要事件重要事件-Society of mind 1986年，Minsky提出了

17、society of mind 其要点是Agent 智能行为来源于agents群体之间的合作与竞争 Agents之间的相互作用是一种是相互的适应 与Nash的对经济行为的论述类似 重要事件重要事件-临场临场AI 1986年，Brooks提出了临场AI的考虑 关键是：智能行为来源于对变化的真实环境的适应 机器昆虫 重要事件重要事件-Reinforcement学习学习 基于适应性的机器学习方法 建立在一类特殊Markov过程上 由此建立适应模型 还很初步 重要事件重要事件-知识发现知识发现 1979年，CMU发展了Bacon系统。试图从数据重新 发现天文学知识 1981年，Stanford发展了AM系统，试图发现新的数 学定理 这些研究成为近年来Data mining的原始思想 KDD and DM 任务：从数据集合中获得简洁、非平凡的解 预测 描述 预 测预 测 与机器学习的原始目标是一致 给定数据集合，根据黑箱原理，选择一个基 函数，建立一个模型，以保证这个模型对这 个领域的其他样本有较高的识别正确率，即 模型有较高的泛化能力 数据描述数据描述 目的：使人理解数据 从给定数据集合，变换为一种简洁表示 这是最具特色的研究 重要事件重要事件-ID3 1986年，Quinlan提出了ID3