1LogicalFoundationsofArtificialIntelligence尹传环chhyin@bjtu.edu.cnSchoolofcomputer&InformationTechnologyBeijingJiaotongUniversity2Goal了解人工智能领域的基本知识掌握用一阶谓词逻辑表示知识的方法掌握用归结原理求解问题的方法了解非单调逻辑的基本思想和方法能用上述原理和方法解决实际问题3ContentsChapter1:IntroductionLogicalApproachtoAIChapter2:DeclarativeKnowledgeChapter3:InferenceChapter4.ResolutionChapter5.ResolutionStrategiesExpandationofLogicalApproachChapter6.NonmonotonicReasoningChapter7.Induction(MachineLearning)4ContentsChapter8.ReasoningwithUncertainBelief(KnowledgeEngineering)ModalLogicChapter9.KnowledgeandBeliefChapter10.MetaknowledgeandMetareasoningAgent:DistributedArtificialIntelligenceChapter11.StateandChangeChapter12.PlanningChapter13.IntelligentAgentArchitecture5RelatedCoursesKnowledgeEngineering(董兴业)MachineLearning(于剑)ComputationalIntelligence(王志海)DataMing(王志海)DistributedArtificialIntelligenceArtificialNeuralNetwork6TextBook&ReferencesTextbook:LogicalFoundationsofArtificialIntelligence.GeneserethandNilsson,1987.References:人工智能:一种系统方法,MTimJones著,电子工业出版社(英文影印)人工智能原理。石纯一等,清华大学出版社,1993人工智能:一种现代方法(英文影印,第二版)。Russell,s.andNorvig,P.,清华大学出版社,2006.5人工智能。史忠值等,国防工业出版社,20077EvaluationPreviousCourses:DiscreteMathematics;ArtificialIntelligenceHomework:20%FinalReport:20%FinalExam.:60%8Chapter1.IntroductionWhatisArtificialIntelligence(AI)?OriginandDevelopmentofAIResearchFieldsofAIWaysofAIresearch9ArtificialIntelligence人工智能(ArtificialIntelligence,AI)起源于美国1956年的一次夏季讨论会(达特茅斯会议)什么是AI计算-算计图灵测试10图灵其人图灵测试---一种智能的测量方法1950年英国数学家图灵(Turing)在“计算机器与智力”一文中提出图灵1912年生于英国伦敦,1954年死于英国的曼彻斯特,他是计算机逻辑的奠基者,许多人工智能的重要方法也源自于这位伟大的科学家。他对计算机的重要贡献在于他提出的有限状态自动机也就是图灵机的概念,对于人工智能,它提出了重要的衡量标准图灵测试,如果有机器能够通过图灵测试,那他就是一个完全意义上的智能机,和人没有区别了。他杰出的贡献使他成为计算机界的第一人,现在人们为了纪念这位伟大的科学家将计算机界的最高奖定名为图灵奖。11图灵的一生辉煌的成就:24岁提出图灵机理论,31岁参与COLOSSUS的研制,33岁设想仿真系统,35岁提出自动程序设计概念,38岁设计“图灵测验”。特立独行的人生:上班途中戴防毒面具骑自行车、自行车掉链子前及时下车、因同性恋遭到拘捕、吃了泡在氰化物溶液中的苹果致死。发明Enigma破译德军密码,获得大英帝国授予的荣誉勋章唯一一位获得图灵奖的华裔科学家——姚期智。12图灵测试(TuringTest)测试主持人Ai受试者人Bi受试者计算机C界面控制AlanTuring(1950)13TuringTest测试者:主持人C被测试者:一人A、一机器B测试环境:测试主持人C与A或B均不可见;主持人C与A或B之间通过计算机终端会话;测试方式:主持人向A和B提出相同的智能性问题,但不能询问物理特征。A和B在回答问题时,应尽量让主持人相信自己是“人”。测试结论:如果不管如何更换被测试者A和主持人C,主持人能正确分辨出人和机器的概率都小于50%,则认为该机器具有了智能。14图灵机原型图灵机是一条在两个方向上都为无限长的磁带,一个控制器和一个读写磁头组成,磁带被分成一个个独立的存储单元,且控制器的状态是有限的151966年的ELIZA患者:我想谈谈我的母亲。Eliza:当你想到你母亲的时候还会想到什么?患者:她想要控制我,浪费我的生命。Eliza:你的生命?患者:是的,有时我有生命。Eliza:你确定。患者:为什么你认为我没有生命?Eliza:你相信我认为你没有生命?16Parry和Eliza的对话Eliza:请继续。Parry:你知道赛马赌家吗?Eliza:你怎么想到我知道赛马赌家?Parry:有个赛马赌家一次都没有还我钱。Eliza:那对你意味着什么?Parry:我打了那个不还我钱的家伙,我想他可能让他黑社会的朋友报复我。Eliza:还有什么要讨论的吗?Parry:你知道诈骗者吗?Eliza:你为什么要这样问?Parry:你参与过赌博吗?Eliza:为什么你对这种问题感兴趣?Parry:我喜欢赛马。Eliza:你还喜欢什么?Parry:我知道流氓操纵赌博。Eliza:你真正在和谁说话?17如何实现?著名的Eliza程序采用POP-11编码,并使用模式匹配程序matches,例如:[Ihateyou]-inp_sentence;ifinp_sentencematches[I?verbyou==]then[whydoyou^verbme?]=endif;这段程序的结果是[whydoyouhateme?]。18希尔勒的中文屋子罗杰•施安克的“故事理解程序”。机器能理解吗?希尔勒的中文屋子。问题:通过了图灵测试就具有智能吗?19AI的本质问题研究如何制造出人造的智能机器或系统,来模拟人类智能活动的能力,以延伸人们智能的科学。科学发展史:瓦特的蒸汽机;电的发现;计算机的产生20WhatisIntelligence一种认识客观事物和运用知识解决问题的综合能力;观察、学习、理解和认知的能力;运用知识以解决问题的能力;抽象思维,把大量信息组织为有意义系统的能力;21IntellectualAbility感知能力:人们通过感觉器官感知外部世界的能力。记忆能力:是对感知到的外界信息或由思维产生的内部知识的存储过程。思维能力:是对所存储的信息或知识的本质属性、内部规律等的认识过程。抽象思维、形象思维、灵感思维学习能力:是一个具有特定目的的知识获取过程。行为能力:是指人们对感知到的外界信息做出的动作反应的能力。22DefinitionsofAI智能机器(intelligentmachine):能够在各类环境中自主地或交互地执行各种拟人任务的机器。人工智能(能力):用人工的方法在机器上实现的智能,即让智能机器具有人类智能的功能,如推理、证明、识别、感知、理解、规划、学习、问题求解等。人工智能(学科):是一门研究如何构造智能机器或智能系统,使它能模拟、延伸和扩展人类智能的学科。23GoalofAIResearch远期目标:揭示人类智能的根本机理,用智能机器去模拟、延伸和扩展人类智能。近期目标:建造智能计算机代替人类的部分智力劳动。24AI历史回顾(1)第一阶段(40年代-50年代末)神经元网络时代双层网络M-P模型、感知器模型等问题:XOR问题不能解决25AI历史回顾(2)输入1输入2输出000011101110(1,0)(1,1)(0,0)(0,1)26AI历史回顾(3)Minsky的著作:《Perceptions》(感知器)从理论上证明了二层神经元网络不可能解决XOR问题如果要求解XOR问题,神经元网络必须是3层或3层以上的结构对于3层或3层以上的神经元网络,难于找到一个通用的学习算法27一些成果20世纪50年代早期,英国牛津大学的研究者开发出了两个复杂游戏的游戏对弈程序。ChristopherStrachey发明了一个运行在FerrantiMarkI上的西洋跳棋对弈程序。到1952年,他的程序已能够完成合理的对弈。DietrichPrinz则发明了另一个运行在FerrantiMarkI上的程序,这个程序能够下国际象棋。1952年,ArthurSamuel的西洋跳棋对弈程序运行在IBM701上。这个学习型西洋跳棋程序非常特别,因为Samuel可以利用一个程序与它的副本程序进行对弈,从而能够从对手身上学习。结果将产生一个能够击败自身的创造者的程序。到1962年,Samuel的西洋跳棋程序击败了前任康涅狄格州西洋跳棋冠军。(这种方法被认为是演化计算的第一个例子)28AI历史回顾(4)第二阶段(50年代中-60年代中)通用方法时代物理符号系统主要研究的问题:GPS、游戏、翻译等对问题的难度估计不足,陷入困境291958:Newell和Simon的四个预测–十年内,计算机将成为世界象棋冠军–十年内,计算机将发现或证明有意义的数学定理–十年内,计算机将能谱写优美的乐曲–十年内,计算机将能实现大多数的心理学理论乐观的人工智能30一些成果(2)第一个为计算机编写的人工智能程序是“逻辑理论家(LogicTheorist)”。它是AllenNewell、HerbertSimon和J.C.Shaw在1956年为了发现等式的证明而发明的,这个程序最独特之处在于它能够为一个给定的等式找到比当前已知的证明更好的证明。1957年,Simon和Newell在此基础之上发明了通用问题求解器(GeneralProblemSolver,GPS)。通用问题求解器使用手段-目的分析求解问题,但通常受限于游戏问题。McCarthy发明了Lisp语言,提出了Alpha-beta剪枝算法。31Nim游戏是一种二人游戏,每个玩家轮流从一堆或数堆物品中将物品拿走。最后取光物品者将输掉游戏。可以拿走1、2或3件物品。在右边实例中,由玩家1开局,亦以他的失败而结束游戏。玩家1输玩家2输玩家1输玩家2输32Alpha-beta剪枝算法Alpha-beta剪枝算法是一个简单的算法,它通过去掉明显不好的结点达到极小化博弈树搜索的目的。3334AI历史回顾(5)一个笑话(英俄翻译)Thespiritiswilling,butthefleshisweak心有余而力不足Thevodkaisgood,butthemeatisrotten伏特加酒很不错,但肉已腐败35AI历史回顾(6)出错的原因spirit1)精神2)烈酒结论必须理解才能翻译,而理解需要知识36AI历史回顾(7)第三阶段(60年代中-80年代初)知识工程时代专家系统知识工程知识工程席卷全球各国发展计划:美国星球大战计划、英国ALVEY计划、法国UNIKA计划、日本五代