浙江大学远程教育学院人工智能讲座

浙江大学远程教育学院《人工智能》讲座徐从富(CongfuXu)PhD,AssociateProfessorEmail:[e-mail]ntelligence,CollegeofComputerScience,ZhejiangUniversity,Hangzhou310027,P.R.ChinaDecember4,2006第二讲人工智能原理及应用(Lecture2Principles&ApplicationsofAI)2提纲知识表示专家系统人工神经网络不确定性推理机器学习数据挖掘AI的若干研究前沿32.1知识表示知识是智能的基础获得知识运用知识符合计算机要求的知识模式计算机能存储、处理的知识表示模式数据结构（List,Table,Tree,Graph,etc.）2.1.1知识表示的重要性4数据(Data)信息的载体和表示用一组符号及其组合表示信息信息(Information)数据的语义数据在特定场合下的具体含义知识(Knowledge)信息关联后所形成的信息结构：事实&规则经加工、整理、解释、挑选、改造后的信息2.1.2数据、信息与知识52.1.3知识的特性相对正确性一定条件下某种环境中......不确定性存在“中间状态”“真”（“假”）程度随机性模糊性经验性不完全性......可表示性&可利用性语言文字图形图像视频音频神经网络概率图模型......62.1.4知识的分类常识性知识、领域性知识（作用范围）事实性知识、过程性知识、控制知识（作用及表示）确定性知识、不确定性知识（确定性）逻辑性知识、形象性知识（结构及表现形式）零级知识、一级知识、二级知识（抽象程度）72.1.5常用的知识表示方法一阶谓词（FirstOrderPredicate）产生式（Production）框架（Framework）语义网络（SemanticNetwork）剧本（Script）过程（Procedure）面向对象（Object-Oriented）Petri网（PetriNetwork）信念网（BeliefNetwork）本体论（Ontology）……82.1.6如何选择合适的知识表示方法？充分表示领域知识有利于对知识的利用便于理解和实现便于对知识的组织、管理与维护92.1.7一阶谓词表示法1.何谓一阶谓词？定义谓词：就是带参数的命题。谓词公式：用连词（,,等）把原子谓词公式组成的合适公式。举例CITY(X),~HUMAN(X),INROOM(ROBOT,R1),etc.HUMAN(X)LAWED(X)，表示：人人都受法律管制{[HUMAN(X)LAWED(X)][COMMIT(X)PUNISHED(X)]}，表示：如果由于某个X是人而受到法律管制，则这个人犯了罪就一定要受到惩罚。10SyntaxitemUsuallyusedOthers取反：Negation(not)~P,PP（加上划线）合取：Conjunction(and)PQP&QP·QPQP,Q析取：Disjunction(or)PQP|QP;QP+Q蕴涵：Implication(if)PQPQPQ等价：Equivalence(iff)PQPQPQ全称量词：Universal(all)(x)P(x)xP(x)xP(x)存在量词：Existential(exists)(x)P(x)xP(x)xP(x)关系：RelationR(x,y)(Rxy)RxyxRy2.常用的谓词公式表示方法对照表113.谓词公式的表达方法举例实例1试用谓词演算表示如下英文句子：“Foreverysetx,thereisasety,suchthatthecardinalityofyisgreaterthanthecardinalityofx.”对应的谓词公式：(x){SET(x)(y)(u)(v)[SET(y)CARD(y,u)CARD(x,v)G(u,v)]}实例2“世上决没有无缘无故的爱，也没有无缘无故的恨。”对应的谓词公式：x[爱(x)y缘故(x,y)]t[恨(t)s缘故(t,s)]124.一阶谓词表示法的优、缺点(1)优点自然性接近自然语言，容易接受精确性用于表示精确知识严密性有严格的形式定义和推理规则易实现性易于转换为计算机内部形式13一阶谓词表示法的优、缺点（续）(2)缺点无法表示不确定性知识所能表示的知识范围太狭窄难以表示启发性知识及元知识未能充分利用与问题本身特性有关的知识组合爆炸经常出现事实、规则等的组合爆炸效率低推理与知识的语义完全割裂142.1.8产生式表示法1943年E.Post第一次提出称为“Post机”的计算模型一种描述形式语言的语法AI中应用最多的知识表示方法之一Feigenbaum研制的化学分子结构专家系统DENDRALShortliffe研制的的诊断感染性疾病的专家系统MYCIN……15PQCF=[0,1]或IFPTHENQCF=[0,1]其中，P是产生式的前提，Q是一组结论或操作，CF(CertaintyFactor)为确定性因子，也称置信度。【说明】：谓词逻辑中的蕴涵式与产生式的基本形式相似，事实上，蕴涵式只是产生式的一种特殊情况。1.产生式的基本形式162.产生式系统的优、缺点(1)产生式系统的优点a）自然性：由于产生式系统采用了人类常用的表达因果关系的知识表示形式，既直观、自然，又便于进行推理。b）模块性：产生式是规则库中的最基本的知识单元，形式相同，易于模块化管理。c）有效性：能表示确定性知识、不确定性知识、启发性知识、过程性知识等。d）清晰性：产生式有固定的格式，既便于规则设计，又易于对规则库中的知识进行一致性、完整性检测。17（2）产生式系统的缺点a）效率不高产生式系统求解问题的过程是一个反复进行“匹配—冲突消解—执行”的过程。由于规则库一般都比较庞大，而匹配又是一件十分费时的工作，因此，其工作效率不高。此外，在求解复杂问题时容易引起组合爆炸。b）不能表达具有结构性的知识产生式系统对具有结构关系的知识无能为力，它不能把具有结构关系的事物间的区别与联系表示出来，因此，人们经常将它与其它知识表示方法（如框架表示法、语义网络表示法）相结合。183.产生式系统的适用领域（1）由许多相对独立的知识元组成的领域知识，彼此之间关系不密切，不存在结构关系。如：化学反应方面的知识。（2）具有经验性及不确定性的知识，而且相关领域中对这些知识没有严格、统一的理论。如：医疗诊断、故障诊断等方面的知识。（3）领域问题的求解过程可被表示为一系列相对独立的操作，而且每个操作可被表示为一条或多条产生式规则。192.1.9框架表示法1.框架理论1975年美国著名AI学者Minsky在其论文“Aframeworkforrepresentingknowledge”中提出了框架理论，并把它作为理解视觉、自然语言对话及其它复杂行为的基础。框架理论的基本思想：认为人们对现实世界中各种事物的认识都是以一种类似于框架的结构存储在记忆中的，当面临一个新事物时，就从记忆中找出一个合适的框架，并根据实际情况对其细节加以修改、补充，从而形成对当前事物的认识。202.框架的一般表示形式框架名槽名1：侧面名1值1，值2，...，值p1侧面名2值1，值2，...，值p2侧面名m1值1，值2，...，值pm1槽名n：侧面名1值1，值2，...，值r1约束：约束条件1约束条件n213.框架及其实例框架名：tx未遂杀人案犯罪意图：x犯罪结果：杀人被杀者：y杀人动机：x未遂被y发现知情人：{zi|iI}罪犯：t条件一：若x为强奸，则t必须是男性条件二：有某个zi指控t条件三：t招认在《聊斋志异》中有个《胭脂》的故事，开始时邑宰判错了案，就是因为他头脑里有个破案的框架：22框架实例：鄂秋準强奸未遂杀人案犯罪意图：强奸犯罪结果：杀人被杀者：卞牛医杀人动机：强奸未遂被卞牛医发现知情人：卞妻，胭脂罪犯：鄂秋準条件一：鄂秋準为男性，成立条件二：胭脂指控鄂秋準，成立条件三：鄂秋準招认，成立邑宰用上述框架去套胭脂一案，结果得到了该框架的一个实例：234.框架表示法的优、缺点（1）优点a）结构性b）继承性c）自然性（2）缺点不善于表达过程性的知识，经常与产生式表示法结合起来使用，以取得互补的效果。242.1.10语义网络表示法1.语义网络的提出及基本思想1968年J.R.Quillian在其博士论文中最先提出语义网络，把它作为人类联想记忆的一个显式心理学模型，并在他设计的可教式语言理解器TLC(TeachableLanguageComprehenden)中用作知识表示方法。语义网络的基本思想：在这种网络中，用“节点”代替概念，用节点间的“连接弧”(称为联想弧)代替概念之间的关系，因此，语义网络又称联想网络。它在形式上是一个带标识的有向图。由于所有的概念节点均通过联想弧彼此相连，Quillian希望他的语义网络能用于知识推导。252.语义网络举例与歌曲《军港之夜》中的歌词“海浪把战舰轻轻地摇”对应的语义网络：全域行为事物方式海浪战舰摇动轻轻某港海浪某港战舰子集子集子集子集子集个体个体子集个体动作对象动作方式动作主体263.语义网络表示法的优、缺点（1）语义网络表示法的优点a）结构性：因为语义网络是一种结构化的知识表示方法，它能把事物的属性以及事物间的各种语义联想显式地表示出来。b）联想性：它最初是作为人类联想记忆模型提出来的。c）自然性：直观地把事物的属性及其语义联系表示出来，便于理解，自然语言与语义网络的转换比较容易实现，故语义网络表示法在自然语言理解系统中的应用最为广泛。27（2）语义网络表示法的缺点a）非严格性：与一阶谓词逻辑相比，语义网络没有公认的形式表示体系。一个给定的语义网络所表达的含义完全依赖于处理程序如何对它进行解释。通过推理网络而实现的推理不能保证其正确性。此外，目前采用的表示量词（包括全称量词和存在量词）的语义网络表示法在逻辑上是不充分的，不能保证不存在二义性。b）处理上的复杂性：语义网络表示知识的手段多种多样，虽然灵活性很高，但同时也由于表示形式的不一致使得对其处理的复杂性提高，对知识的检索也就相对复杂，要求对网络的搜索要有强有力的组织原则。282.1.11剧本（脚本）表示法剧本表示法是1975年R.C.Schank依据他的概念依赖理论而提出的一种知识表示方法。脚本与框架类似，由一组槽组成，用来表示特定领域内一些事件的发生序列。1.概念依赖理论【难点】在人类的各种知识中，常识性知识是数量最多、涉及面最宽、关系最复杂的知识，很难把它们形式化地表示出来交给计算机处理。概念依赖理论的基本思想：把人类生活中各类故事情节的基本概念抽取出来，构成一组原子概念，确定这些原子概念间的相互依赖关系，然后把所有故事情节都用这组原子概念及其依赖关系表示出来。292.剧本（脚本）的构成1、剧本：描述特定范围内原型事件的结构。2、剧本的组成（1）进入条件：指出剧本所描述的事件可能发生的先决条件，即事件发生的前提条件。（2）角色：描述事件中可能出现的人物。（3）道具：描述事件中可能出现的有关物体。（4）场景：描述事件序列，可以有多个场景。（5）结局：给出剧本所描述的事件发生以后必须满足的条件。30广义的知识表示语言任何程序设计语言例如：C,C++,Java,XML,etc.狭义的人工智能语言把知识和智能传授给计算机的表示语言专门用于编程求解AI问题典型代表：LISP语言、PROLOG语言……2.1.12知识表示语言311.LISP语言概况提出：1960年，美国AI之父McCarthy首次给出含义：LISP是LIStProcesser（表处理器）之意目的：为处理AI中的符号编程问题而