智能决策支持系统和智能技术的决策支持

,*,*,决策支持系统,系统工程专业本科学员必修课,第四章 智能决策支持系统和智能技术的决策支持,人工智能基本原理,本章内容,智能决策支持系统概述,专家系统与智能决策支持系统,神经网络的决策支持,遗传算法的决策支持,机器学习的决策支持,4.1 智能决策支持系统概述,4.1.1 智能决策支持系统概念,4.1.2 智能决策支持系统结构,1981年，,Bonczek,提出了,DSS,三系统结构，该结构中有,“,知识系统,”,，使得不少学者将,DSS,划为人工智能的范畴，研究知识表示与知识推理，这样，,DSS,与人工智能的专家系统的界限变得模糊了。,1980年，,Spraque,提出,DSS,的三部件结构，是传统,DSS,结构的典型代表。,IDSS,实际上就是在,DSS,基础上增加了,知识部件,。,4.1.1 智能决策支持系统概念,知识部件,知识库,知识管理系统,推理机,4.1.2 智能决策支持系统结构,1.人工智能的决策支持技术,（1）专家系统,（2）神经网络,（3）遗传算法,（4）机器学习,（5）自然语言理解,2.智能决策支持系统结构形式,（1）,IDSS,的基本结构形式,问题综合与交互系统,模型库管理系统,数据库管理系统,人工智能技术,专家系统 神经网络,遗传算法 机器学习,自然语言理解,模型库,数据库,（2）,IDSS,的简化结构图,问题综合与交互系统,模型库管理系统,数据库管理系统,知识库管理系统,推理机,模型库,数据库,知识库,用户,4.2 人工智能基本原理,4.2.1 逻辑推理,4.2.2 知识表示与知识推理,4.2.3 搜索技术,4.2.1 逻辑推理,1.形式逻辑,（1）概念：概念反映事物的特有属性和属性的取值。,（3）推理：从一个或多个判断推出一个新判断的过程。,（2）判断：对概念的肯定或否定；,是研究人的思维形式及其规律的科学，主要用于形成,概念,，作出,判断,，进行,推理,。,2 推理的种类,演绎推理,归纳推理,类比推理,假言推理,三段论推理,数学归纳法,假言易位推理,枚举归纳推理,（1）假言推理：,“,如果,p，,那么,q,”,为真，同时,“,p,”,为真，则推出,“,q,”,为真。,pq，p,q,（2）三段论推理：,“,如果,p，,那么,q,”,为真，同时,“,如果,q，,那么,r,”,为真，则推出,“,如果,p，,那么,r,”,为真。,pq，q r,p r,（3）,假言易位推理：,“,如果,p，,那么,q,”,为真，同时,“,非,q,”,为真，则推出,“,非,p,”,为真。,pq，q,p,演绎推理,（1）数学归纳法：,A,包含,B,1,、B,2,，,A,真,B,1,真，,B,n,B,n1,归纳推理,（2）枚举归纳推理：由所见的某一类事物的部分分子具有某种属性，而且没有遇到相反的情况，于是得出这一类事物都具有这种属性的一般性结论。,S,1,是,P，S,2,是,P,S,n,是,P，,S,1,S,n,是,S,类中的部分分子，而且没有遇到相反的事例,所以，,S,类事物都是,P,类比推理：,A,事物有,a、b、c、d,属性，,B,事物有,a、b、c,属性（ 或,a,，,、b,，,、c,，,相似属性）,所以，,B,事物也可能有,d,属性（或,d,，,相似属性）,由两个（或两类）事物在某些属性上相同，进而推断它们在另一个属性也可能相同的推理。,3.总结,（1）演绎推理的结论没有超出已知的知识范围，而归纳推理和类比推理的结论超出了已知的知识范围；,（2）演绎推理中由于前提和结论有必然联系，只要前提为真，结论一定为真。归纳推理和类比推理中前提和结论，不能保证有必然联系，具有或然性。这样的结论未必是可靠的，需要经过严格的验证和证明。,4.2.2 知识、知识表示,知识是加工了的、深思熟虑过的、经过推理了的、已经达成共识的关于实体的状态以及实体之间的联系的一系列事实，可以用来指导行动，是理解自然规律并根据自然规律预测实际系统行为的能力。,知识的概念,：,是以各种不同方式把多个信息关联在一起的信息结构。是人们对客观事物及其规律的认识，知识还包括人们利用客观规律解决实际问题的方法和策略等。,描述性知识,：表示对象及概念的特征及其相互关系的知识，及问题求解状况的知识，也称为事实性知识。,判断性知识,：表示与领域有关的问题求解知识，如推理规则等，也称启发性知识。,过程性知识,：表示问题求解的控制策略，即如何应用判断性知识进行推理的知识。,计算机所处理的知识，按其作用可大致分为三类：,知识按其作用的层次可分为两类：,对象级知识,：直接描述有关领域对象的知识,元级知识,：描述对象级知识的知识,4.2.2 知识、知识表示,4.2.2 知识、知识表示,知识表示：,知识表示是对知识的一种描述，或者说是一组约定，是一种计算机可以接受的、用于描述知识的数据结构，对知识进行表示就是把知识表示成便于计算机存储和利用的某种数据结构。,知识表示的要求,1,）表示能力：能够将问题求解所需的知识正确有 效地表达出来；,2,）可理解性：所表达的知识简单、易于理解；,3,）可访问性：能够有效地利用所表达的知识；,4,）可扩充性：能够方便地对知识进行扩充。,4.2.2 知识、知识表示,知识表示的方法,谓词逻辑,产生式规则,语义网络,框架,剧本,谓词逻辑的合法表达式也称合式公式。它由原子公式、连接词和量词组成。,原子公式：由谓词、括号和括号中的项组成,办公地点关系,刘凌,401,陈东华,402,张明亮,418,办公地点（刘凌、,401,）,办公地点（陈东华、,402,）,办公地点（张明亮、,418,）,1,一阶谓词逻辑,兰色（盒子）,颜色（盒子、兰色）,值（颜色、盒子、兰色）,盒子是兰色的,原子公式：由谓词、括号和括号中的项组成,谓词逻辑的合法表达式也称合式公式。它由原子公式、连接词和量词组成。,1,一阶谓词逻辑,连接词：用来组合原子公式以形成较复杂的合式公式。,合取：,PQ,，当,P,、,Q,皆为真时，才为真，否则为假；类似“,AND”,析取：,PQ,，当,P,、,Q,皆为假时，则为假，否则为真；类似“,OR”,蕴涵：,P=Q,只有,P,为真，,Q,为假时，蕴涵式为假，否则为真；,否定：,P,，当,P,为假时，才为真，否则为假。,1,一阶谓词逻辑,P,Q,P=Q,T,T,T,T,F,F,F,T,T,F,F,T,1,一阶谓词逻辑,量词：,、 ，分别为全称量词和存在量词。,例子：“张某送给屋里的每个人一件礼物”,（,y,）, IN(y , ROOM) HUMAN( y ) =,(,x,) GIVE(ZHANG , x , y) PRESENT(x),1,一阶谓词逻辑,2 产生式规则,产生式(,Production),一词，首先是由美国数学家波斯特（,E.Post）,提出来的。波斯特根据替换规则提出了一种称为波斯特机的计算模型，模型中的每一条规则当时被称为一个产生式。后来，这一术语几经修改扩充，被用到许多领域。例如，形式语言中的文法规则就称为产生式。,产生式也称为产生式规则，或简称规则。,2 产生式规则,产生式规则的一般形式为：,前件后件,其中，前件就是前提，后件是结论或动作，前件和后件可以是由逻辑运算符,AND,、,OR,、,NOT,组成的表达式。,2 产生式规则,产生式规则知识一般表示为：,if A then B,产生式规则的语义,：,如果前提满足，则可得结论或者执行相应的动作，即后件由前件来触发。所以，前件是规则的执行条件，后件是规则体。,例如，下面就是几个产生式规则：,(1)如果银行存款利率下调，那么股票价格上涨；,(2)如果炉温超过上限，则立即关闭风门；,(3)如果键盘突然失灵且屏幕上出现怪字符，则是病毒发作；,一条产生式规则就是一条知识。用产生式可以实现推理和操作，,产生式规则是知识表示形式,。,产生式规则知识有,正向,和,逆向,两种推理方式,。,（1）正向推理,逐条搜索规则库，对每一条规则的前提条件都检查事实库中是否存在；,对前提条件中各子项，若事实库中不是全部都存在，放弃该条规则；,若在事实库中全部存在，则执行该条规则，并结论放入到事实库中；,反复执行上述过程，直至推出目标，并存放入事实库中。,算法,：,例如：在产生式规则库中有3条规则，在事实库中存在,B、C、E,3,个事实，且它们均为真。希望通过正向推理，证明目标,G,为真。,B、C、E,1、,A B-G,2、C D-A,3、E-D,V,V,产生式规则库,事实库,推理过程：,（1）正向推理,（2）逆向推理,从目标开始，寻找以此目标为结论的规则，并对该规则的前提进行判断；,若该规则的前提中某个子项是另一规则的结论，再找此结论的规则；,重复上述过程，直到对某个规则的前提能够进行判断；,按此规则前提的判断得出结论的判断，由此回溯到上一个规则的推理，一直回溯到目标的判断。,算法,：,B、C、E,1、,A B-G,2、C D-A,3、E-D,V,V,产生式规则库,事实库,推理过程：,G,B,A,C,D,E,（2）逆向推理,从概念结点间问它们之间的关系,通过概念和关系问其他结点,由,J.R.Quilian,于1968年在研究人类联想记忆时提出的一种心理学模型。,3 语义网络,基本思想：,用结点表示概念，用弧线表示概念之间的关系，将领域知识表示成一种结构图形式；,在语义网络中，寻找概念之间的内在联系，主要通过语义网络的形式推理来回答两类问题：,3 语义网络,结点,代表实体，表示各种事物、概念、情况、属性、状态、事件、动作等；,语义单元,是由有向图表示的三元组(结点1,弧,结点2),结点1,结点2,语义关系,弧,是有方向和标注的，方向体现了结点所代表的实体的主次关系，即结点1为主，结点2为辅；,标注,表示所连接的两个实体之间的语义联系。,试用语义网络表示命题,“,某学校小学生坐车去春,游,”,。,动作方式,某学校,小学生,动作目的,春游,坐车,属于,3 语义网络,基本的语义关系,(1)Is-a,和,Part-of,型关系,Is-a,：表示一个事物是另一个事物的实例，表示具体与抽象关系，此关系的一个最主要的特点是属性的继承关系。,灵长类,动物,Is-a,Is-a,型语义网络,3 语义网络,轮胎,汽车,Part-of,Part-of,型语义网络,(1)Is-a,和,Part-of,型关系,Part-of,：表示一个事物是另一个事物的一部分，是部分与整体的关系。,基本的语义关系,3 语义网络,Is,：表示一个结点是另一个结点的属性,中国的陆地面积,960万平方公里,Is,Is,型语义网络,(1)Is-a,和,Part-of,型关系,基本的语义关系,3 语义网络,(2)属性(类属)关系,Have,：表示一个结点具有另一个结点所描述的属性,Have,属性关系语义网络,鸟,翅膀,Have,基本的语义关系,3 语义网络,(2)属性(类属)关系,A-Kind-of,：表示一个事物是另一个事物的一种类型，表示隶属关系。,AKO,属性关系语义网络,鸭嘴兽,哺乳动物,A-Kind-of,基本的语义关系,3 语义网络,(2)属性(类属)关系,Can,：表示一个结点能做另一个结点的事情。,Can,属性关系语义网络,草鱼,水草,eat,基本的语义关系,3 语义网络,(3)其他关系,时间关系,：指不同事物在其发生时间方面的先后关系。,Before：,表示一个事物在一个事物之前发生；,After：,表示一个事物在一个事物之后发生；,位置关系,：指不同事物在位置方面的关系。,Located-on,Located-at,Located-under,Located-inside,Located-outside,3 语义网络,语义网络的推理,语义的推理过程主要有两种：,继承,和,匹配,继承的思想：,对事物的描述从抽象结点传递到具体结点，从而得到所需结点的属性值，通常是沿着,Is-a，A-Kind-of,等继承弧进行。,3 语义网络,语义网络的推理,3 语义网络,语义网络继承推理示意图,小米,谷物,麻雀1,麻雀,鸟,动物,翅膀,飞行工具,AKO,AKO,AKO,Is-a,Is-a,eat,Have,匹配的思想：,在知识库的语义网络中寻找与待求问题相符的语义网络模式。,小米,谷物,麻雀1,麻雀,鸟,动物,翅膀,飞行工具,AKO,AKO,AKO,Is-a,Is-a,eat,Have,举例：已知麻雀是一种鸟，求麻雀的特点。,某港海浪,动作对象,海浪,战舰,轻轻,isa,动作方式,晃动,isa,某港战舰,动作主体,语义网的推理,试用语义网络表示命题,“,海浪把战舰轻轻地摇,”,问1 海浪和战舰有什么关系？(寻找概念间的关系),问2 怎样晃动？(通过概念和关系寻找其他结点),问3 晃动哪些战舰？(寻找概念间的关系),框架,框架是描述对象（一个事物、事件或概念）属性的一种数据结构，由一组描述物体的各个方面的槽（属性）所组成。每个槽（属性）又可包含若干侧面（属性的一个方面），每个侧面都有自己的名字和填入的值。,明斯基1975年提出，用来表示经验性知识,一般框架的结构:,frame,slot,slot,值21,值22,值11,值12,下面是一个描述“教师”的框架：,框架名：,类属：,工作： (教学，科研),缺省：教学,性别：(男，女),学历：(中师，高师),类型：(，),框架,框架,槽值可以有如下几种类型：,具体值,value,默认值,default,过程值,procedure：,该值是一个计算过程，它利用该框架的其它槽值，按给定计算过程（公式）进行计算得出具体值。,另一框架名：当槽值是另一框架名时，就构成了框架调用，这样就连成了一个框架链。有关框架聚集起来就组成框架系统。,空（待填入）,框架,框架是知识表示的基本单位。,不同的框架之间可以通过属性之间关系建立联系，从而构成一个框架网络，充分表达相关对象间的各种关系。,特点：主要描述事物的内部结构及事物之间的类属关系。,框架名：,动作：攻打,动作发出者：美国,动作接受者：伊拉克,后果：，,框架名：,动作：抵抗,动作发出者：伊拉克,动作接受者：美国,后果：，,框架名：,动作：投降,动作发出者：伊拉克,动作接受者：美国,后果,: 萨达姆政府垮台,框架名：,动作：撤军,动作发出者：美国,后果：遭国际社会谴责,框架推理的主要形式为：填充槽值。,填充槽值的主要方法为：匹配、继承。,匹配：在求解某个问题时，先把问题用一个框架表示出来，然后与知识库中的已有框架进行匹配。如果匹配成功，就可获得有关信息。,继承：子框架可以拥有其父框架的槽及其槽值。,框架,(1) 匹配,框架是一类事物的完整描述。事物之间匹配只能是部分相同槽的匹配。,框架1：王强,是 人,性别 男,行动,音量,进取心 中等,框架2：消防车,是 车辆,颜色 红,行动 快,音量 极高,载物 水,匹配此两框架的槽：行动和音量。,得到王强的行动是快的，音量是极高的。,框架,例：王强的行动和音量象消防车。我们要知道王强的行动和音量究竟是什么，应该对两个框架进行匹配。,框架,(2) 继承,有两种继承，即直接继承和时序继承。,直接继承,：在框架网络中下层框架直接从上层 框架中继承所有的属性值和条件。如“墙”继承“房子”的所有属性,时序继承,：有条件的继承。,框架,例：框架名：旧中国,政体：资产阶级专政,面积：960万平方公里,人口：4亿5千万,领导党派：国民党,框架名：新中国,政体：人民民主专政,面积：,人口：4亿5千万（当时1949年）,领导党派：共产党,其中，面积和人口是相同的，其它槽值就改变了。这就是有条件的继承。,关于框架的例子,例 描述学校的框架,框架名：,类属：,类型：范围,(大学，中学，小学),位置：(省(直辖市)，市),面积：单位(平方米),教工人数：,学生人数：,例 描述大学的框架,框架名：,类属：,类型：范围,(综合性大学，专科性大学),专业：默认值：综合,学院数：,教学楼：,教工人数：,学生人数：,位置：(省(直辖市)，市),面积：单位(平方米),例 描述某所大学的框架,框架名：,类属：,姓名：中国医科,大学,专业：医学,学院数：13,教学楼：20,办公楼：40,学生宿舍：20,教工宿舍：60,教工人数：4000,职工人数：5000,学生人数：20000,位置：北京市,面积：10000万平方米,创建时间：2002年4月,1、有的槽有槽值，有的槽值不明显，有的槽没有槽值，有的槽值是一个框架名；,2、这3个框架是层层嵌套的，上位框所具有的属性，下位框也一定具有，下位框可以从上位框继承某些槽值和侧面值。,3、框架的推理基于匹配和继承的原则。,剧本,剧本是描述一定范围内一串原型事物的结构。,剧本由六部分组成：,(1) 开场条件,：事件发生之前必须满足的条件。,例如，肚子饿了需要进餐，且有钱等。,(2) 结局,：事件发生之后，通常会成为现实的情况。,例如，肚子不再饿了，花了钱等。,(3) 道具,：用来表示与剧本所描述的事件有关的物体。,例如，餐桌、菜单、食物等。,(4) 角色,：剧本中描述事件中的人物。,例如，经理、顾客、服务员等。,(5) 线索,：剧本表达事件的时序模式。,例如，小食店、餐厅、酒家等。,(6) 场次,：事件发生的顺序。每个场次可用框架描述。,剧本,剧本特点,：结构呆板，知识表示范围窄，不适合用于表达各种知识，但对于表达事先构思好的特定知识非常有效。,回顾,人工智能基本原理,知识表示与知识推理,谓词逻辑,产生式规则,语义网络,框架,剧本,智能决策支持系统结构,4.2.3 搜索技术,1.问题求解过程的形式表示,2.盲目搜索方法,3.启发式搜索,状态空间表示法,与或树表示法,广度优先搜索法,生成测试法,深度优先搜索法,爬山法,状态空间表示法的基本思想：,定义状态的描述形式，通过使用这种描述形式可把问题的一切状态都表示出来；定义一组算符，通过使用算符可把问题由一种状态转变为另,种状态。问题的求解过程是,个不断把算符作用于状态的过程。,如果在使用某个算符后得到的新状态是目标状态，就得到了问题的一个解。这个解是从,初始状态到目标状态所用算符构成的序列,。,例子1：,重排九宫问题，在3,x3,的方格棋盘上放置分别标有数字1、2、3、4、5、6、7、8共8个棋子，初始状态为,S,0,，,目标状态为,S,g,，,如图所示。,可使用的算符有：,空格左移，空格上移，空格右移，空格下移。即只允许把位于空格左、上、右、下的邻近棋子移入空格。要求寻找从初始状态到目标状态的路径。,由图2可以看出，解的路径是：,S,0,3,8,16,26,该路径使用的算符序列：空格上移，空格左移，空格下移，空格右移。,“,与或树,”,表示法的基本思想,“,与或树,”,表示法也称为问题归约方法（包括分解与等价变换）。,分解,：把一个复杂问题分解为若干个较为简单的子问题，每个子问题又可继续分解为若干个更为简单的子问题。重复此过程，直到不需要再分解或者不能再分解为止。然后对每个子问题分别进行求解，最后把各子问题的解复合起来就得到了原问题的解。,例如，把问题,P,分解为三个子问题,P,1,，P,2,，P,3,，,可用图表示。,P,1,，P,2,，P,3,是问题,P,的三个子问题，只有当这三个子问题都可解时，问题,P,才可解，称,P,1,，P,2,，P,3,之间存在,“,与,”,关系；称节点,P,为,“,与,”,节点；由,P、 P,1,，P,2,，P,3,所构成的图称为,“,与,”,树。在图中，为了标明某个节点是,“,与,”,节点，通常用一条弧把各条边连接起来。,等价变换,：对于一个复杂问题，除了可用,“,分解,”,方法进行求解外，还可利用同构或同态的等价变换，把它变换成若干个较容易求解的新问题。若新问题中有一个可求解，则就得到了原问题的解。问题的等价变换过程也可用一个图表示出来，称为,“,或,”,树。,分解和等价变换也可结合起来使用，此时的图称为,“,与/或,”,树。其中既有,“,或,”,节点，也有,“,与,”,节点，如右图所示。,4.2.3 搜索技术,1.问题求解过程的形式表示,2.盲目搜索方法,3.启发式搜索,状态空间表示法,与或树表示法,广度优先搜索法,生成测试法,深度优先搜索法,爬山法,广度优先搜索法,（1）基本思想,从初始状态,S,0,开始，利用算符，生成所有可能的后继状态，构成下一层节点，检查目标节点,G,是否出现，若未出现，就对该层所有的状态节点，分别顺序利用算符，成生该层所有节点的后继节点，再检查是否出现,G，,若未出现，继续生成再下层的所有状态节点，这样一层一层展开，直到目标出现。,S,0,S,1,S,2,S,3,S,11,S,12,S,21,S,22,S,31,S,111,S,121,S,122,S,221,S,311,G,（2）算法,1)把初始节点,S,0,故入,OPEN,表。,2)如果,OPEN,表为空，则问题无解，退出 。,3)把,OPEN,表的第一个节点(记为节点,n),取出放入,CLOSED,表。,4)考察节点,n,是否为目标节点。若是，则求得了问题的解，退出。,5)若节点,n,不可扩展，则转第2)步。,6)扩展节点,n，,将其子节点放入,OPEN,表的尾部，并为每一 个子节点都配置指向父节点的指针，然后转第2)步。,广度优先搜索的,盲目性较大,，当目标节点距离初始节点较远时将会产生许多无用节点，因此搜索效率低，但是，只要问题有解，用宽度优先搜索,总,可以得到解，而且得到的是路径,最短的路径,。,深度优先搜索法,（1）基本思想,从初始状态,S,0,开始，利用算符，生成搜索树下一层的任意一个节点，检查目标节点是否出现，若未出现，以此节点利用一个算符生成再下一层的任一节点，然后再检查目标节点是否出现，若未出现，继续以上操作过程，一直进行到叶节点（即不能再生成新的状态节点），当它仍不是目标节点时，回溯到上一层，取另一可能扩展搜索的分支。生成新的状态节点。仍不是目标，采用相同的回溯办法回退到上层节点，扩展可能的分支生成新状态节点。如此一直下去，直到目标节点出现。,S,0,S,1,S,2,S,3,S,11,S,12,S,21,S,22,S,31,S,111,S,121,S,122,S,221,S,311,G,（2）算法,1)把初始节点,S,0,故入,OPEN,表。,2)如果,OPEN,表为空，则问题无解，退出。,3)把,OPEN,表的第一个节点(记为节点,n),取出放入,CLOSED,表。,4)考察节点,n,是否为目标节点。若是，则求得了问题的解，退出。,5)若节点,n,不可扩展，则转第2)步。,6)扩展展节点,n，,将其全部子节点放入到,OPEN,表的首部，并为其配置指向父节点的指针，然后转第2)步。,例子2：,对图所示的重排九宫问题进行深度优先搜索，可得到的搜索树这只是搜索树的一部分，尚未到达目标节点，仍需继续往下搜索。,在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上，则可较快地得到解。但是，如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不能得到解。所以深度优先搜索是不完备的，即使问题有解，它也不一定能求得解。显然，用深度优先求得的解，也不一定是路径最短的解。,4.2.3 搜索技术,1.问题求解过程的形式表示,2.盲目搜索方法,3.启发式搜索,状态空间表示法,与或树表示法,广度优先搜索法,生成测试法,深度优先搜索法,爬山法,启发式搜索,基本思想,：对每个在搜索过程中遇到的新状态，用一个估计函数（启发式函数）并计算其值的大小，确定下一步将从哪个状态开始继续前进。,启发式函数的一般形式为：,f(x)g(x)h(x),g(x),为从初始节点,S,0,到节点,x,已经实际付出的代价；,h(x),是从节点,x,到目标节点,S,g,的最优路径的估计代价。,f(x),为从初始节点,S,0,到目标节点,S,g,的总代价；,例3：,重排九宫问题，在3,x3,的方格棋盘上放置分别标有数字1、2、3、4、5、6、7、8共8个棋子，初始状态为,S,0,，,目标状态为,S,g,，,如图所示。,要求用,启发式搜索,从初始状态到目标状态的路径。,6,4个不在位,g(n),代表结点搜索的深度，表示单位消耗的情况；,h(n),代表结点,“,不在位,”,的棋子数；,f(n),可估计出通向目标结点的希望程度；,设计估计函数：,f(n)=g(n)+h(n),不在位棋子数的计算方法：,6,2,1,3,4,8,7,6,5,初始,S,0,C,2,1,3,4,8,7,5,6,2,1,3,4,8,6,5,7,2,1,3,4,8,7,6,5,A,B,2,1,6,h=4,f(n)=4,2,1,3,8,7,4,5,6,2,1,3,8,7,4,5,6,2,1,3,4,7,8,5,6,D,E,F,4,3,h=3,h=3,h=4,f(n)=5,f(n)=5,f(n)=6,h=3,h=4,h=2,h=4,f(n)=6,f(n)=7,f(n)=5,f(n)=7,1,7,3,4,2,8,5,6,1,8,3,4,2,7,5,6,M,N,7,h=0,h=2,f(n)=5,f(n)=7,8,2,4,3,7,1,5,6,2,7,3,4,8,6,1,5,2,1,4,3,7,8,5,6,2,1,4,3,7,8,5,6,G,H,I,J,5,1,8,3,2,7,4,5,6,6,K,1,8,3,2,7,4,5,6,L,h=1,f(n)=5,h=3,f(n)=7,h=5,h=3,h=5,f(n)=6,f(n)=6,f(n)=4,4.3 专家系统与智能决策支持系统,4.3.1 专家系统的原理,4.3.2 产生式规则专家系统,4.3.3 专家系统与决策支持系统的集成,4.3.4 建模专家系统,定义：,专家系统（,Expert System,，,ES,）是指具有大量专门知识，并能运用这些知识解决特定领域中实际问题的计算机程序系统。,近年来这个术语已经被一个更中性的术语“基于知识的系统”（,Knowledge-Based Systems,，,KBS,）或“知识系统”（,Knowledge Systems,，,KS,）替代了 。,ES,模仿专家的推理过程进行专门问题的求解，它的能力来源于它所拥有的专门知识和推理机制。,定义：,专家，是指掌握了某一特定领域的专业知识、解决问题的能力达到了一定水平、拥有丰富的实践经验的学者。,4.3.1 专家系统的原理,1,、,1968,年，,DENDRAL,系统是一种帮助化学家判断某待定物质的分子结构专家系统。,1965,年在美国斯坦福大学研制，用,lisp,语言编写；,2,、,1971,年，,MACSYMA,符号数学专家系统；,3,、,1973,年，,MYCIN,医疗系统；,4,、,1976,年，,PROSPETOR,地质勘探专家系统。,1.,专家系统的概念与特点,专家系统的产生与发展,专家系统已成为世界各国最热门的竞争性研究课题，日本、美国、英国等国家纷纷将其列为国家重点研究项目，投入了大量的人力和资金，,日本把专家系统作为第五代计算机研究的核心内容，英国已将专家系统智能数据库列入国家四大重点项目,。,我国对于专家系统的研究工作起步较晚，但经过,20,年的艰苦努力，已经在理论研究和应用开发方面取得了很大进展，在,中医治疗、油井记录分析、地震预测、气象预报、军事指挥、作战模拟、战场管理,等方面研制了一批专家系统。,1.,专家系统的概念与特点,专家系统的产生与发展,专家系统应该具备以下四个要素,:,(1),应用于某专门领域；,(2),拥有专家级知识；,(3),能模拟专家的思维；,(4),能达到专家级水平。,1.,专家系统的概念与特点,专家系统的基本概念,专家,能够认识并描述问题；,能够快速并恰当地处理问题；,解释问题解决方案；,能从实践中学习；,调整知识；,能够打破规则。,专家 、专家知识、专家知识的转化,专家系统的基本概念,专家知识：通过训练、阅读和实践而获得的广泛的、与问题有关的专门知识。,问题的领域知识,规则（启发性）,全局策略,元知识,事实,专家系统的基本概念,专家知识的转化,ES,的目标,把专家的知识转化到计算机中，并为非专家使用。,活动,知识获取,知识表示,知识推理,知识转换,知识存于知识库中,专家系统的特点,具有丰富的经验和知识，能运用知识高效地推出结论；,能进行符号处理；,能根据不确定的知识进行推理；,具有元知识；,知识的独立性；,推理不是固定形式。,专家系统的基本概念,专家系统与知识系统的关系,专家系统拥有的知识是专家知识，而且主要是经验性知识。,知识系统,(KnowledgeBased System),的知识已不限于专家的经验知识，可以是领域知识或通过机器学习所获得的知识等。,专家系统不会疲劳、遗忘，不受环境、情绪的影响，具有计算速度快、计算结果准确等优点；,专家系统可以快速升级与复制。,专家系统与专家的比较,专家系统与数据库检索的关系,数据库中存放的记录可以看成是事实性知识。如果把检索数据库记录看成是推理的话，它也是一种知识推理。,它与专家系统的不同在于：,知识只含事实性知识，不包含规律性知识。,推理是对已有记录的检索，记录不存在，则检索不到。不能适应变化的事实，推理不出新事实。,1.,专家系统的概念与特点,算法（推理过程）是固定形式的。算法一经确定，推理过程就固定了。而专家系统的推理是不固定形式的，随着问题不同，推理过程也不一样。,数值计算只能处理数值，不能处理符号。,数值计算是用算法解决实际问题，对不同的数据可以算出不同的结果。如果把数据看成是知识，算法看成推理的话，它也是一种知识推理。它与专家系统的不同在于：,专家系统与,数值计算,的关系,1.,专家系统的概念与特点,专家系统与,数值计算和数值处理区别,专家系统特点,：知识包括事实和规则；适合于符号处理；推理不固定于形式；能得出未知的事实；,数值计算和数值处理,专家系统,数据库检索,事实性知识,规律性知识,推理是对已有记录的检索，记录没有则检索不到,能推理出新事实,数值计算,推理过程固定,推理过程不固定,只能处理数值,既能处理数值，又能处理符号,1.,专家系统的概念与特点,2.,专家系统的功能和结构,存储问题求解所需的知识；,存储具体问题求解的初始数据和推理过程中的各种信息；,利用已有知识，进行问题求解，并控制和协调系统运行；,能够对推理过程、结论或系统自身行为做出必要的解释；,提供知识获取，机器学习以及知识库的维护手段；,提供用户接口，便于用户使用以及分析和理解用户的各种要求和请求。,专家系统应具备功能：,专家系统的基本结构,专家,知识获取,用户,人机接口,知识库,推理机,咨询,建议,全,局,数,据,库,2.,专家系统的功能和结构,专家系统一般结构：,基本任务是把知识输入到知识库中，并负责维持知识的一致性及完整性，建立起良好的知识库,推理机是专家系统的思维机构，其任务是模拟领域专家的思维过程，控制并执行对问题的求解。,能够对自己的行为做出解释，回答用户提出的,“,WHY HOW,”,等问题，是专家系统区别于一般程序的重要特征之一，也是取信于用户的一个重要措施。,人机接口是专家系统与领域专家、知识工程师及一般用户之间的界面，由一组程序及相应的硬件组成，用于完成输入输出工作。,综合数据库是初始事实、问题描述以及系统运行过程中的中间结果、最终结果、运行信息等的工作存储器。综合数据库是推理机不可缺少的一个工作场地，同时由于它可记录推理过程中的各有关信息，又为解释机构提供了回答用户咨询的依据。,知识库是合理组织的关于某一特定领域的陈述型知识和过程型知识的集合。知识库和传统数据库的区别在于它不但包含了大量的简单事实，而且包含了规则和过程型知识。,122,专家系统由两大部分组成：,开发环境、应用环境,知识获取,人机接口,解释机制,推理机,专家,用户,知识库,知识工程师,文档,数据库,123,知识获取的主要手段,（,1,）面谈法,（,2,）模拟法,知识获取,（,3,）机器学习,环境,学习,知识库,执行,监督,选例,机器学习系统的结构,知识获取的困难,知识获取,获取专家启发性知识是十分困难的，其原因：,（,1,）知识表示失配。,（,2,）专家的启发性知识是不精确的。,（,3,）有些启发性知识表示的不可能性。,（,4,）缺乏开发专家系统的现代技术。,（,5,）知识测试与调试的困难性。,知识库(,Knowledge Base),知识库是合理组织的关于某一特定领域的陈述型知识和过程型知识的集合；,知识库有两个主要问题：,知识表示,和,知识的精确程度。,知识库中知识表示,知识表示,产生式规则（,IF_THEN）,谓词逻辑,模糊逻辑,（真假二值） （,0,1,连续值）,框架,语义网络,过程性知识,剧本,知识库中知识表示的精度,精确知识,公式,公理,原理性,不精确知识,经验性,可信度,概率,证据理论,模糊数学,知识精确度,知识库管理,知识管理包括：知识的分类、知识的组织和存储、知识的检索、知识的增加、知识的删除、知识的修改、知识的拷贝和转储、知识的一致性、完整性和无冗余性检查等。,知识库的组织,知识库的组织应确保知识库与推理机的独立；,便于知识的扩充、维护与修改；,便于知识的运用和输入输出操作；,便于系统中采用多种知识表示模式；,便于知识的一致性、完整性、无冗余性的检查与维护；,便于知识的检索与匹配，充分考虑知识运用和处理的效率；,尽量节省知识库的占用空间。,知识库管理,知识库的管理与维护,知识库的建立与撤销；,知识的增加、插入、删除、修改和检索；,知识的一致性、完整性、无冗余性检查与维护；,友好的输出方式；,提供知识字典，用于知识的管理与控制；,知识库分块交换功能；,知识库的重组；,知识库的安全与保密；,知识库恢复。,知识库管理,（,1,）在对知识库进行调试时，要求解释系统具有这样的功能，即检索知识库中已有的内容，跟踪专家系统的运行，并能记录知识的运用情况、上下文中的各种参数、中间结果的演变等，还能提供出错信息，,能对知识库中的错误方便地进行定位和修改,。解释系统这种辅助发现和更正知识库中错误的作用，对于专家系统设计者来说，起到了“助手”的作用。,解释机制,解释系统的作用,（,2,）用户操作使用专家系统时，要求系统在问题求解过程中，给出推理过程和推理结论合理的、正确的解释，提高用户对系统求解的信赖度，便于推广应用并起到辅助决策的作用。,（,3,）由于专家系统知识库中的知识一般是领域专家的专门知识，应对非领域专家的用户得到一些直觉的知识训练，以便掌握专门知识，起到“教师”的作用。,解释机制,解释系统的作用,准确性。解释机制对系统所做的工作应能给出准确的描述，避免解释内容的冗余和繁杂；,可理解性。解释机制的解释应易于理解，应尽可能接近自然语言或领域的形式语言；,智能性。包括两个方面：解释机制尽可能易于使用；尽可能对用户提出的问题生成合理且较快的解释。,解释系统的设计要求,解释机制,元知识：,关于知识的知识。,知识分为两级：,领域级知识：特定领域的知识。,元级知识：说明如何运用领域知识的知识。,元知识一般采用与领域级知识相同的表示形式，并作为一个知识实体与领域级知识共存于知识库中。,元知识,从领域专家获取,知识工程师在开发实际系统过程中获取,从系统的运行结果中获取,元知识,的获取：,指导规则的选择,记录与领域知识有关的事实,规则的论证,检查规则中的错误,描述领域知识表示的结构,论证系统的体系结构,辅助优化系统,说明系统的能力,元知识分类,1,）指导知识的选择,有一条以上规则的前提部分和当前事实匹配时，选择规则策略：,策略,1,：如果某一规则的前提比另一规则的前提更专 门，则先选用更专门的规则。,策略,2,：按规则排列顺序，先选用前一条规则。,策略,3,：优先选用被满足的条件较多的规则。,策略,4,：首先选择执行代价小的规则。,如有两条规则,A,H,，,A,B,K,，若,A,，,B,成立，应先选第,2,条。,元知识的作用,2,）记录与领域知识有关的事实,记录某种处理方法的平均运行时间；,统计一个程序在运行过程中询问用户的次数；,统计规则的成功与失败的比率等，提供有关与领域知识的信息。,3,）规则的论证,指出某些规则存在的理由，用于推理的解释。,如：,R1,： 如果溢出液是硫酸，则用石灰。,理由：石灰能中和硫酸，且所形成的化合物是不溶,的，能沉淀出来。,4,）检查规则中的错误,4.3.2 产生式规则专家系统,目前，用于产生式规则知识形式建立专家系统是最广泛和最流行。,原因：,产生式规则知识表示容易被人理解；,它是基于演绎推理的，保证了推理结果的正确性；,大量产生式规则所连成的推理树可以是多棵树，宽度反映实际问题的范围，深度反映实际问题的难度。,4.3.2 产生式规则专家系统,一.产生式规则,产生式规则知识一般表示为：,if A then B,或表示为,“,如果,A,成立则,B,成立，简化为,A B。,产生式规则知识的特点：,(1) 相同的条件可以得出不同的结论。,如：,ABAC,规则集能描述和解决各种不同的灵活的实际问题；把规则知识集中的所有规则连成一棵,“,与或,”,树（知识树）,，建立这些规则之间的关联。,(4),一条规则中的结论，可以是另一条规则中的条件。,如,CDF，FBZ,(2),相同的结论可以由不同的条件来得到。,如,AGBG,(3),条件之间可以是,“,与,”,连接和,“,或,”,连接,如,ABG，ABG（,相当于,AG，BG）,知识精确程度,由于专家的大部分决策都是在知识不确定的情况下作出的，因此，在决策模型的实际应用过程中，经常使用可信度（,CF）,来表示事实和规则的确信程度。,CF,的取值范围为：,0,CF1,或0,CF100,二.推理树（与或树 ）,基本思想,：按逆向推理思想把规则库所含的总目标（它是某些规则的结论）作为根结点，按规则的前提和结论展开成,一棵树,的形式。,这棵树一般称为推理树或知识树，它把规则库中的所有规则都连结起来。由于连结时有,“,与,”,关系和,“,或,”,关系，从而构成了,“,与/或,”,推理树。,二.推理树（与或树 ）,例：若有规则集为：,A（BC）G,（IJ）KA,XFJ,LB,MEC,WZM,PQE,画出“与、或”推理树。,用规则的前提和结论形式画出一般的推理树形式,总目标,G(,结论),前提,A,(,结论),前提,B,(,结论),前提,C,(,结论),前提,J,(,结论),前提,I,前提,L,前提,M,(,结论),前提,E,(,结论),?,前提,X,前提,F,前提,Z,前提,P,前提,Q,?,前提,W,?,?,?,?,?,?,（1）每条规则对应的节点分支有,“,与,”,关系、,“,或,”,关系；,（2）树的根节点是推理树的总目标；,（3）相邻两层是一条或多条规则连接；,（4）每个节点可以是单值，也可以是多值；,（5）所有的叶节点，都安排向用户提问，或者把它的值直接存放在全局数据库中。,推理树的特点：,总目标,G(,结论),前提,A,(,结论),前提,B,(,结论),前提,C,(,结论),前提,J,(,结论),前提,I,前提,L,前提,M,(,结论),前提,E,(,结论),?,前提,X,前提,F,前提,Z,前提,P,前提,Q,?,前提,W,?,?,?,?,?,?,逆向推理过程在推理树中反映为推理树的深度优先搜索过程。,三 逆向推理过程,N,1,7,9,8,2,G,A,B,C,J,I,K,L,M,E,4,5,Y,X,F,Z,P,Q,10,11,12,3,Y,W,Y,Y,Y,N,6,在计算机中实现时，并不把规则连成推理树，而是利用规则栈来完成。当调用此规则时，把它压入栈内（相当于对树的搜索），当此规则的结论已求出（,yes,或,no）,时，需要将此规则退栈（相当于对树的回溯）。,规则栈,注意,对中间结点的否定需要注意的是，若当该结点还有其它,“,或条件,”,分枝时，不能立即确定该结点为,no，,必须再搜索另一分枝，当另一分枝回溯为,yes,时，该结点仍为,yes。,每个结点有两种可能，即,yes,和,no，,叶结点为,no,是由用户回答形成的。中间结点为,no,是由叶结点为,no，,回溯时引起该结点为,no。,中间结点只有所有,“,或,”,分枝的回溯值均为,no,时，才能最后确定该中间结点为,no。,实例：动物分类问题的产生式系统描述及其求解。,r,1,：,若某动物有奶，则它是哺乳动物。,r,2,：,若某动物有毛发，则它是哺乳动物。,r,3,：,若某动物是哺乳动物且有爪且有犬齿且目盯前,方，则它是食肉动物。,r,4,：,若某动物是哺乳动物且吃肉，则它是食肉动物。,r,5,：,若某动物是食肉动物且黄褐色且有黑色条纹，则它是老虎。,设由下列动物识别规则组成一个规则库，推理机采用上述逆向推理算法，建立一个产生式系统。该产生式系统就是一个小型动物分类知识库系统。规则：,初始事实：,f,1,：,某动物有毛发。,f,2,：,吃肉。,f,3,：,黄褐色。,f,4,：,有黑色条纹。,目标条件为：该动物是什么？,动物分类逆向推理树,该动物是老虎,1. 事实数据库,事实数据库中每一个事实除该命题本身，还应该包含更多的内容。每个事实有如下属性，构成了关系型结构：,事实数据库,四、解释机制和事实数据库,2. 解释机制,解释机制是专家系统中重要内容。它把推理过程显示给用户，让用户知道目标是如何推导出来的。消除用户对目标结论的疑虑。,解释机制有两种实现方法：一种是推理过程的全部解释；一种是推理过程中正确路径的解释。,四、解释机制和事实数据库,五、不确定性推理,事实的不确定性,事实的不确定性一般用可信度,CF(Certainty Factor),值表示，它的取值范围为：,0,CF1,或0,CF100,例：,“,头有点痛,”,表示成：头痛,CF,（,0.8),“,这批货可能今天运不到,”,表示成：运到,CF,（,0.2),“,这个问题不好解决,”,表示成：解决,CF,（,0.4),五、不确定性推理,规则的不确定性,规则反映了客观事物的规律性。大量的实际问题中，专家掌握的规则大多是经验性的，不是精确的。,推理的不确定性,由于事实和规则的不确定性，从而产生了结论的不确定性。它反映不确定性的传播过程。,例：如果乌云密布并且电闪雷鸣，则天要下暴雨,(0.95),。,A,B,CF(0.95,),如果头痛发烧，则患了感冒,(0.8),。,C,D,CF(0.8),五、不确定性推理, 前提中,AND（,与）连接时，结论可信度的计算公式,规则形式：,IF E,1,E,2,.E,N,THEN H,CF(R),结论,H,的可信度为：,CF(H)CF(R),MINCF(E,1,)，CF(E,2,)CF(E,N,),五、不确定性推理, 前提中,OR（,或）连接时结论的可信度计算公式,规则形式：,IF E,1,OR E,2,THEN H,CF(R),把它转化成等价的两条规则，即,IFE,1,THENHCF(R),IFE,2,THENHCF(R),五、不确定性推理,如果已知两条规则形式如下:,IFE,1,THENHCF(R,1,),IFE,2,THENHCF(R,2,),则结论,H,的可信度计算分别有：,CF1(H)CF(R,1,),CF(E,1,),CF2(H)CF(R,2,),CF(E,2,),合并为：,CF(H)CF1(H)+CF2(H)CF1(H),CF2(H),五、不确定性推理,对于三条规则，如：,IF E,1,THEN H CF(R,1,),IF E,2,THEN H CF(R,2,),IF E,3,THEN H CF(R,3,),先按二条规则合并方法计算出：,CF12(H)CF1(H)+CF2(H)CF1(H),CF2(H),再将它和第三条规则合并：,CF(H)CF12(H)+CF3(H)CF12(H),CF3(H),其中,CF3(H)CF(R,3,),CF(E,3,),对于多,OR,连接：依次分解、滚动式合并,不确定性推理和确定性推理的区别,可信度的差别,推理过程的差别,对于确定性推理，当结论的可信度为,1,时，就不再进行推理；对于不确定性推理，当某个结论的可信度不为,1,时（即,CF1,），对于相同结论的其它规则仍然要进行推理，求该结论的可信度，并和已计算出该结论的可信度进行合并。,确定性推理,：,先引用规则,R,1,，提问,A,？当回答为,yes,时，推得结论,G,成立，即,yes,，这样就不再搜索,R,2,对结论,G,进行推理。,例如，有两条相同结论的规则,R,1,：,AG,；,R,2,：,BCG,由于,G,的可信度不为,1,，还必须对结论,G,的其它规则进行推理。再引用规则,R,2,，提问,B,和,C,？,设回答,B,为,yes,，,CF(0.7),，回答,C,为,yes,，,CF(0.8),，计算,G,的可信度为：,CF2(G),0.9,MIN0.7,，,0.8,0.63,合并,G,的可信度为：,CF(G),CF1(G)+CF2(G),CF1(G)CF2(G),0.56+0.63,0.560.63,0.84,不确定性推理,：,R,1,：,AG,CF(0.8),；,R,2,：,BCG,CF(0.9),推理时，先引用规则,R,1,，提问,A,？当回答为,yes,时，还须给定可信度，设为,CF(0.7,），求得,G,的可信度：,CF1(G),0.8,0.7,0.56,例：有如下规则集和可信度：,R,1,：ABCGCF(0.8）,R,2,：DEACF(0.7）,R,3,：JKBCF(0.8）,R,4,：PQCCF(0.9）,R,5,：F（RS）D CF(0.6）,已知事实及可信度,F(0.4)，R(0.5)，S(0.6)，E