人工智能技术导论.pptx

1、人工智能技术导论（第二版)廉师友 编著,参考书,人工智能马少平、朱小燕编著，清华大学出版社人工智能及其应用蔡自兴、徐光祐编著，清华大学出版社 Artificial Intelligence A New Synthesis(人工智能)Nils J.Nilsson,第一章 人工智能概述,人工智能的概念人工智能的研究途经与方法人工智能的分工领域人工智能的基本技术人工智能的发展概括,什么是人工智能,人工智能(Artificial Intelligence)是指由计算机实现的人造智能。作为一门学科，人工智能可定义为：人工智能是一门研究如何构造智能机器（智能计算机）或智能系统，使它能模拟、延伸、扩展人类智

2、能的学科人工智能是一门交叉边缘学科，与人工智能有关的学科有：计算机科学、数学、语言学、神经生理学、神经心理学、脑科学、认知科学、逻辑学、控制论等,什么是人的智能,智能是人脑的属性和产物。智能具有的主要特征：A、具有感知能力。通过视觉、听觉、触觉、味觉和嗅觉感知外部世界。B、具有记忆与思维能力。记忆能存储由感知器官感知到的外部信息以及由思维所产生的知识。思维用于对记忆的信息进行处理。思维可分为逻辑思维和形象思维。C、具有学习能力及自适应能力。D、具有行为能力。发现规律 应用规律 分析问题 解决问题图灵测试中文屋子问题（约翰希尔勒）,为什么要研究人工智能,现有计算机系统的局限性。智能低下、缺乏自学

3、习、自适应、自优化能力。人类智能的局限性。学习能力因人而异、学习速度慢、效率低。信息化社会的迫切要求。,人工智能的目标,近期目标：使现有的电子数字计算机能模拟人类的部分智能行为。远期目标：制造智能计算机，使计算机具有看、听、说等感知和交互能力、具有联想、推理、理解、学习等高级思维能力，还要有分析问题、解决问题和发明创造的能力。深蓝（32CPU，200万次/秒，200万个棋局）,人工智能的表现形式,智能软件智能设备智能网络智能计算机智能机器人智能体(Agent)(艾真体),人工智能的研究途径与方法,结构模拟（神经计算、生理学派、连接主义）模拟人脑的神经网络结构实现智能。主要特征：1、通过神经元之

4、间的并行协同作用实现信息处理，具有并行性、动态性、全局性。2、通过神经元间分布式的物理联接存储信息。联想记忆、容错性。3、通过神经元间连接强度的动态调整实现自学习和自适应功能。4、善于模拟人类的形象思维过程。,人工智能的研究途径与方法,功能模拟（符号主义、心理学派、逻辑学派）以人脑的心理模型为基础，将问题或知识表示成某种逻辑网络，采用符号推演的方法，实现搜索、推理和学习等功能。主要特征：1、立足于逻辑运算和符号操作，适合于模拟人的逻辑思维过程。2、知识用显式的符号表示，容易表达人的心理模型。3、现有的数字计算机可以方便地实现高速的符号处理。4、能与传统的符号数据库进行链接，易于模块化。5、以知

5、识为基础。,人工智能的研究途径与方法,行为模拟（行为主义、进化主义、控制论学派）基于感知-行为模型的研究途径和方法。模拟人在控制过程中的智能活动和行为特征：自寻优、自适应、自组织、自学习。强调智能系统与环境的交互，认为智能取决于感知和行动,智能行为可以不要知识。智能只有放在环境中才是真正的智能，智能的高低体现在对环境的适应性上Brooks，机器虫,人工智能的分支领域,基于脑功能模拟的领域划分1、机器感知（信息输入）。使计算机具有类似于人的感知能力，能通过“感知”直接从外界获取信息，是对人的感知的模拟及延伸。机器视觉、机器听觉。相关学科：模式识别（语音识别、图像识别）。信息-电信号序列-预处理-

6、提取特征-模式匹配2、机器联想。基于内容的联想，与具体存储位置无关。联想存储技术。3、机器推理。又称为计算机推理、自动推理，是人工智能的核心课题之一。推理：从一些已知判断（前提）推出一个新判断（结论）的思维过程。演绎推理、归纳推理、类比推理确定性推理、不确定性推理基于概率逻辑的或然推理(随机性)、基于模糊逻辑的似然推理(模糊性)串行推理、并行推理,人工智能的分支领域,4、机器学习。使机器自己获取知识。对人类已有知识的获取、对客观规律的发现、对自身行为的修正。机器学习分为：机械学习、指导学习、解释学习、类比学习、示例学习、发现学习等。这些属于符号学习。另外还有神经网络学习。5、机器理解。图形理解

7、（物景分析）、自然语言理解。理解是感知的延伸和深化。6、机器行为（机器人行动规划）。智能机器人的核心技术，反映了机器人的智能水平解决问题依靠规划功能确定行动步骤和动作序列任务：在一个特定的工作区域中自动生成从初始状态到目标状态的动作序列、运动路径和轨迹的控制程序,人工智能的分支领域,基于研究途径和实现技术的领域划分1、符号智能以符号知识为基础，通过符号推理进行问题求解知识工程(知识获取、知识表示、知识管理、知识运用、知识库系统)、符号处理2、计算智能以数据为基础，通过数值计算进行问题求解人工神经网络、进化计算(遗传算法、遗传程序设计、进化规划、进化策略)、模糊技术、人工生命,人工智能的分支领域

8、,基于应用领域的领域划分1、难题求解难题的概念路径规划、组合优化、天气预报、股市分析、市场预测、机器博弈NP(Nondeterministic Polynomial)和NPC(Nondeterministic Polynomial Complete)问题难题求解技术能促进人工智能其他领域的发展2、自动定理证明自然演绎法、判定法、定例证明器、计算机辅助证明四色问题(1976.6,K.Appeel)。3、自动程序设计超级编译系统自动程序综合和自动程序验证。,人工智能的分支领域,4、自动翻译。机器翻译。自然语言理解。一边站着一个人他想起来了5、智能控制1965，KS.FU(傅京孙)提出将启发式推理规

9、则用于学习控制系统6、智能管理。人工智能与管理科学、系统工程和计算机技术的结合。7、智能决策。人工智能应用于决策支持系统。8、智能通讯。在通讯的各个环节和层次上实现智能化。如网控、转接、信息转换等。使通讯网随时运行于最佳状态。9、智能仿真。仿真是在三种类型知识-描述性知识、目的性知识和处理知识的基础上产生另一种形式的知识-结论性知识。10、智能CAD。人工智能应用于CAD的设计自动化、智能交互、智能图形学、自动数据采集方面。11、智能CAI。人工智能应用于CAI：自动生成各种问题与练习、自动选择与调整教学内容和进度、自动生成答案、自然语言理解能力、不断改善教学策略。,人工智能的分支领域,基于应

10、用系统的领域划分1、专家系统。基于人类专家知识的程序系统。能模拟专家的思维方式。2、知识库系统。3、智能数据库系统。传统数据库系统+人工智能。4、智能机器人系统。具备感知、思维、人-机通讯和运动能力。,人工智能的分支领域,基于计算机系统结构的领域划分1、智能操作系统。并行性、分布性和智能性。2、智能多媒体系统。人工智能与多媒体技术的有机结合。3、智能计算机系统。4、智能网络系统。模糊和神经网络技术应用于网络的业务量预测和控制、资源动态分配、动态路由选择等方面。,人工智能的分支领域,基于实现工具与环境的领域划分1、智能软件工具。人工智能程序设计语言，如表处理语言LISP、逻辑程序设计语言PROL

11、OG、面向对象程序设计语言Smalltalk等。知识表示语言FRL、OPS5。专家系统工具、知识工程工具等。2、智能硬件平台。直接支持智能系统开发和运行的机器硬件。,人工智能的分支领域,基于体系结构的领域划分集中式人工智能（个体智能）分布式人工智能（群体智能）个体智能的组合或叠加DPS（分布式问题求解），自顶向下MAS（多智能体系统），自底向上,人工智能的基本技术,推理技术。推理是智能的核心。推理以逻辑为基础。基于谓词逻辑的自然演绎推理和归结反演推理。基于非标准逻辑如多值逻辑、模态逻辑、时态逻辑、模糊逻辑、非单调逻辑的推理。搜索技术。人工智能的基本技术。许多智能活动的过程，都可以看作或抽象为一

12、个“问题求解”过程。“问题求解”就是在问题空间中进行搜索的过程。盲目搜索、启发式搜索。神经网络搜索。知识表示与知识库技术。知识表示是指知识在计算机中的表示方式。知识表示要符合知识的逻辑结构和物理结构，并适合于计算机存储和处理。知识库由知识构成。知识的组织、管理、维护和优化。,人工智能的基本技术,归纳技术。机器自动提取概念、获取知识、发现规律的技术。归纳技术与知识获取和机器学习密切相关。基于符号处理的归纳和基于神经网络的归纳。数据库知识发现（KDD,Knowledge Discovery in Database)和数据挖掘(Data Mining)技术。联想技术。联想记忆，联想存储。,人工智能的

13、发展概况,孕育期（1956年之前）1、公元前，Aristotle提出形式逻辑的一些主要定律，三段论至今仍是演绎推理的基本依据。2、培根（1561-1626）曾系统地提出了归纳法。提出“知识就是力量”3、德国数学家Leibniz（1646-1716）提出了万能符号和推理计算的思想，为数理逻辑的产生和发展奠定了基础。4、英国逻辑学家Boole（1815-1864）创立了布尔代数，在思维法则一书中首次用符号语言描述了思维活动的基本推理法则。5、英国数学家Turing于1936年提出理想计算机的数学模型，即图灵机。Turing测试。6、1943年，McCulloch 和 Pitts提出M-P神经元模型

14、。7、1946年，世界上第一台电子计算机诞生。,人工智能的发展概况,人工智能学科的产生（1956年）1956年夏季，McCarthy,Minsky,Lochester,Shannon,More,Samuel,Selfridge,Solomonff,Newell,Simon等十人在Dartmouth大学召开历时两个多月的研讨会，讨论机器智能的有关问题。由McCarthy提出“人工智能”一词，人工智能从此成为一门学科。,人工智能的发展概况,符号主义AI发展概况1、形成（1956-1965）（人工智能的推理期。结构良好问题。搜索策略和算法）（1）、1956年，Samuel的跳棋程序。1959,196

15、2（2）、定理证明方面，1956年Newell等的逻辑理论机（LT）程序；1958年，王浩的工作；1965年，Robinson提出的消解原理。（3）、模式识别方面，1959年Selfridge的模式识别程序；1965年Roberts编制了可以分辨积木构造的程序。（4）、问题求解方面。1960年，Newell的通用问题求解(GPS)程序。（5）、1960年，McCarthy研制成功LISP语言。,人工智能的发展概况,人工智能的知识期（1965-70年代末）（1）、专家系统方面。1965年，Feigenbaum的专家系统DENDRAL，1968年投入使用。DENDRAL对知识表示、存储、获取和推理

16、的技术为以后的专家系统的建造树立了榜样，对AI的发展产生了深刻的影响。之后著名的专家系统有：医学专家系统MYCIN，地质勘探专家系统PROSPECTOR，计算机配置专家系统R1等。（2）、1969年，国际人工智能联合会议(IJCAI)召开。1970年，“Artificial Intelligence”杂志创刊。（3）、1977年，Feigenbaum在第五届国际人工智能会议上，提出了“知识工程”的概念。发展期（20世纪80年代后）专家系统与知识工程在理论、技术和应用方面都有长足的进步和发展。出现了多专家系统、大型专家系统、微专家系统、分布式专家系统等。智能管理信息系统、智能决策支持系统、智能控

17、制系统等。,人工智能的发展概况,连接主义途径发展概况1、1943年，神经生理学家McCulloch 和Pitts提出M-P神经元模型。1944年，Hebb提出Hebb学习规则。2、1957年，Rosenblatt提出Perceptron单层神经网络模型。1962年，Widrow提出自适应线性元件Adaline。应用于天气预报、电子线路板分析、人工视觉等。3、1969年，Minsky和Papert发表Perceptrons，证明了单层人工神经网络无法实现一个简单的异或逻辑函数XOR，把神经网络的研究带入低谷。4、在低谷期，Kohonen Grossberg和Anderson等人仍坚持研究，取得了

18、一些有价值的结果。5、20世纪80年代中期以后，神经网络研究复苏，掀起了新一轮研究热潮。1986年，Hopfield网络成功应用于TSP问题。1986年Rumelhart提出BP算法，解决了多层人工神经元网络的学习问题。1987年6月，第一届国际神经网络大会（IJCNN）召开，盛况空前。目前，NN与专家系统、知识工程成为AI的两个主流方向。NN在智能控制、信号处理、最优化、知识工程等领域都有成功应用。,当前发展趋势,1、传统以符号处理为中心的人工智能与神经网络的结合。神经网络：识别 联想 学习 适应，负责对外界的感知和交互专家系统：判断 推理 搜索，负责高层的决策与控制2、新理论、新技术的出现

19、。Fuzzy,Genetic Algorithm,Chaos,Artificial life,Soft Computing,Computational Intelligence,Rough set,Data Mining,Knowledge discovery in database,Data warehouse,Situated AI,Agent-based distributed AI 等。,第二章 基于谓词逻辑的机器推理,谓词、函词、量词个体：研究对象中可以独立存在的具体的或抽象的客体。个体用个体常元或个体变元表示，如x,y,z,a,b,c,等。谓词：描述个体性质及个体之间相互关系的词。

20、如P、Q、R，等。例、命题“2是素数”中，2是个体，“是素数”是谓词。可表示为P(2).函词（函数）：某些个体是其它个体的函数，描述这种关系的词称为函词。例、命题“小李的父亲是医生”可表示为Doctor(father(Li).量词：存在量词“”；全称量词“”。例、“任何实数的平方都非负”可表示为 x(R(x)N(s(x)。“存在偶素数”可表示为 x(E(x)P(x)。,一些命题的表示,凡是人都有名字 x(M(x)N(x)不存在最大的整数x(G(x)y(G(y)D(x,y)x(G(x)y(G(y)D(y,x)对所有的自然数，均有X+YXx y(N(x)N(y)S(x,y,x)某些人对某些食物过敏

21、 x y(M(x)F(y)G(x,y),谓词公式,项的定义：1、个体常元和个体变元是项；2、设f是n元函词符号，t1,t2,tn是项，则f(t1,t2,tn)是项。3、只有有限次使用1，2得到的符号串才是项。原子公式：P是n元谓词，t1,t2,(tn是项，则P(t1,t2,tn)称为原子谓词公式(原子公式)(原子)。谓词公式：1、原子公式是谓词公式；2、若A、B是谓词公式，则 A，A B，A B，A B，A B，xA，xA也是谓词公式；3、只有有限次地应用步骤1，2形成的符号串才是谓词公式。辖域：xA 和 xA中，x称为量词的指导(作用)变元，A称为x的辖域。辖域中与该量词的指导变元相同的变元

22、称为约束变元，其它变元(如果存在的话)称为自由变元。例、xP(x)；x(H(x)G(x,y)；xA(x)B(x)约束变元的改名：两个规则,部分逻辑蕴含式（p59-p60),析取三段论：A(A B)B假言推理（分离规则）：A(A B)B拒取式：B(A B)A假言三段论：(A B)(BC)A C二难推论:(A B)(A C)(BC)C全称指定规则US(Universal Specification)：xA(x)A(y)，y是个体域中任一确定元素。存在指定规则ES(Existential Specification)：xA(x)A(c)，c是个体域中某一确定元素。全称推广规则UG(Universal

23、 Generalization)：A(y)xA(x)，y是个体域中任一确定元素。存在推广规则 EG(Universal Generalization)：A(c)xA(x)，c是个体域中某一确定元素。,自然演绎推理,以谓词公式的等价式及推理定律为基础进行的推理称为自然演绎推理。例见教材p61。推理过程是一个符号变换过程，类似于人们使用自然语言进行推理的思维过程。推理与谓词公式的含义无关，是一种形式推理。自然演绎推理在机器上实施比较困难推理规则太多应用规则需要很强的模式识别能力中间结论的指数递增,子句集,定义1 原子谓词公式及其否定称为文字；若干个文字的一个析取式称为一个子句；由r个文字组成的子句

24、称为r-文字子句，1-文字子句称为单元子句，不含任何文字的子句称为空子句，记为或NIL。定义2 对一个谓词公式G，通过一定的步骤得到的子句集合S称为G的子句集。,子句集,（1）、利用等价式A B A B和 A B(A B)(B A)消去联结词“”和“”。（2）、缩小否定联结词的作用范围，使其仅作用于原子公式。可利用下列等价式：A A；(AB)A B，(A B)A B；xA(x)x A(x)，xA(x)x A(x)（3）、重新命名变元名，使不同量词约束的变元有不同的名字。（4）、消去存在量词。若存在量词不在全称量词的辖域内，则用一个常量符号替换该存在量词辖域中的相应约束变元。这样的常量称为Sko

25、lem常量；若该存在量词在一个或多个全称量词的辖域内，则用这些全称量词指导变元的一个函数替换该存在量词约束的变元。这样的函数称为Skolem函数。例如x1 x2 xnyP(x1,x2,xn,y)中y可用Skolem函数f(x1,x2,xn)替换为x1 x2 xnP(x1,x2,xn,f(x1,x2,xn)。,子句集,（5）、把全称量词全部移到公式的左边。（6）、把全称量词后面的公式利用等价关系A(B C)(AB)(A C)化为子句的合取式，得到的公式称为Skolem标准形。Skolem标准形的一般形式为x1 x2 xnM，其中M是子句的合取式。（7）、消去全称量词。（8）、对变元更名，使子句间

26、无同名变元。（9）、消去合取词，以子句为元素组成的集合称为谓词公式的子句集。例：把如下谓词公式化为子句集。xyP(x,y)yQ(x,y)R(x,y),子句集,求解过程 xyP(x,y)yQ(x,y)R(x,y)1)xyP(x,y)yQ(x,y)R(x,y)2)xyP(x,y)yQ(x,y)R(x,y)3)xyP(x,y)zQ(x,z)R(x,z)4)xP(x,f(x)Q(x,g(x)R(x,g(x)5)P(x,f(x)Q(x,g(x)R(x,g(x)6)P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x)7)P(x,f(x)Q(x,g(x)(P(y,f(y)R(y,g(y)8)P

27、(x,f(x)Q(x,g(x)，(P(y,f(y)R(y,g(y)定理1 谓词公式G 不可满足当且仅当其子句集S不可满足。子句集S是不可满足的是指其全部子句的合取式是不可满足的。,命题逻辑中的归结原理,要证明在前提P下结论Q成立，即是证明P Q永真，这只须证明P Q不可满足。根据定理1，只须证明P Q的子句集不可满足。由于子句之间是合取关系，只要有一个子句不满足，则整个子句集不可满足。由于空子句是不可满足的，所以如果子句集中包含空子句，则该子句集是不可满足的。若子句集中不包含空子句，则可通过Robinson提出的归结原理对子句集进行归结，归结过程保证子句集的不可满足性不变。一旦归结出空子句，则

28、证明结束。因此，归结原理把定理的证明化为子句集中归结出空子句的过程。,命题逻辑中的归结原理,定义、设L是一个文字，则称L与L为互补文字。定义、设C1、C2是命题逻辑中的两个子句，C1 中有文字L1，C 中有文字L，且L1与L互补，从C1，C中分别删除L1，L，再将剩余部分析取起来，构成的新子句C1称为C1与C2的归结式（消解式），C1，C2称为C1的亲本子句。C1=PQ R,C2=Q S,C1=P R S定理、归结式C1是其亲本子句C1与C2的逻辑结论。推论、设C1，C2是子句集S的两个子句，C1是它们的归结式，则（）若用C1代替C1和C2后得到新子句集S1，则由S1的不可满足性可推出原子句集

29、S的不可满足性。即S1不可满足S不可满足）若把C1加入到S中，得到新子句集S，则S与S在不可满足意义上是等价的。即S2不可满足 S不可满足,命题逻辑中的归结原理,例、用归结原理证明R是P,(P Q)R，(SU)Q，U的逻辑结果。求子句集P,(PQ)R,(SU)Q,U,RP,(P Q)R,(S U)Q,U,RP,P Q R,S Q,U Q,U,R(子句集)归结演绎P Q R R P Q P Q P QQ U Q U U U,替换与合一,问题的提出谓词逻辑和命题逻辑中使用归结原理的差别C1=P(x)Q(x),C2=P(a)R(y)C1=P(a)Q(a),C2=P(a)R(y)定义 一个替换(Sub

30、stitution)是形如t1/x1,t2/x2,tn/xn 的有限集合，其中t1,t2,tn 是项(替换的分子)，x1,x2,xn是互不相同的个体变元(替换的分母)。ti/xi表示用ti代换xi。ti与xi不同，xi也不能循环出现在tj中(j=1,2,n)。基替换(t1,t2,tn 均不含变元)、空替换例：a/x,g(c)/y,f(g(b)/z，g(y)/x,f(x)/y,替换与合一,定义7 设t1/x1,t2/x2,tn/xn 是一个替换，E是一个表达式，把E中出现的所有个体变元xi都用ti 替换，记为E，得到的结果称为E在下的替换实例(Instance)。Eg：E=P(x,y,g(z),

31、a/x,f(b)/y,c/z，E=P(a,f(b),g(c)定义 设t1/x1,t2/x2,tn/xn，u1/y1,u2/y2,um/ym 是两个替换，则将集合t1/x1,t2/x2,tn/xn，u1/y1,u2/y2,um/ym 中符合下列条件的两种情形删除：ti/xi，当ti xi ui/yi，当yi x1,x2,xn 得到的集合仍是一个替换，称为与的复合或乘积，记为 例:设=f(y)/x,z/y=a/x,b/y,y/z=f(b)/x,y/y,a/x,b/y,y/z=f(b)/x,y/z,替换与合一,定义 设S=F1,F2,Fn 是一个原子谓词公式集，若存在一个替换，使得F1 F2 Fn，

32、则称为S的一个合一(Unifier)，并称S为可合一的。一个公式集的合一一般不唯一定义10 设是公式集S的一个合一，如果对S的任何一个合一，都存在一个替换，使得，则称为S的一个最一般合一(Most General Unifier)，简称MGU 设S=P(u,y,g(y),P(x,f(u),z),有=u/x,f(u)/y,g(f(u)/z 对其它某个合一,如=a/x,f(a)/y,g(f(a)/z,a/u，可找到替换=a/u，使得,替换与合一,定义11 设S是一个非空的具有相同谓词名的原子公式集，从S中各公式的左边第一个项开始，同时向右比较，每一组不都相同的项的差异部分组成的集合称为S的差异集。

33、公式集S=P(a,x,f(g(y),P(z,h(z,u),f(u)的差异集为a,z,x,h(z,u),g(y),u,替换与合一,设S为一非空有限具有相同谓词名的原子谓词公式集，求S的MGU的算法：(1)令k=0,Sk=S,k=（表示空替换）(2)若Sk只含有一个谓词公式，则算法停止，k就是要求的最一般合一(3)求Sk的差异集Dk(4)若Dk中存在元素 xk 和 tk，其中xk是变元，tk是项且xk不在tk中出现，则置Sk+1=Sktk/xk，k+1=ktk/xk，k=k+1，然后转步(2)(5)算法停止，S的最一般合一不存在,替换与合一,求S=P(a,x,f(g(y),P(z,h(z,u),f(u)的MGUk=0S0=S,0=,D0=a,z1=0a/z=a/zS1=S0a/z=P(a,x,f(g(y),P(a,h(a,u),f(u)k=1D1=x,h(a,u)2=1h(a,u)/x=a/z