222知识表示与问题求解(产生式法)

1智能控制技术上海大学机电工程与自动化学院杜鑫自动化系仪自教研室22.2知识表示与问题求解知识表示法2.2.1一阶谓词知识表示法2.2.2产生式知识表示法自动化系仪自教研室3产生式表示法又称为产生式规则表示法。有心理学家认为，人脑对知识的存储就是产生式形式。产生式最早由P.Post于1943年提出，用于构造Post机计算模型；1972A.Newell和H.A.Simon在研究人类的认识模型中提出了Rule-Based产生式系统方法以及规则表示模式。目前，产生式表示法已经成为人工智能中应用最多的一种知识表示法，许多成功的专家系统都用它来表示知识。2.2.2产生式知识表示法自动化系仪自教研室42.2.2产生式知识表示法2.2.2.1产生式表示知识的基本方法2.2.2.2产生式系统的组成2.2.2.3产生式系统的推理方式2.2.2.4产生式系统应用举例2.2.2.5产生式表示法的特点自动化系仪自教研室52.2.2产生式知识表示法2.2.2.1产生式表示知识的基本方法事实的表示规则的表示产生式与蕴含式的区别产生式与条件语句的区别自动化系仪自教研室62.2.2产生式知识表示法2.2.2.1产生式表示知识的基本方法事实的表示-事实的定义事实是断言一个语言变量的值或断言多个语言变量之间关系的陈述句“雪是白的”其中“雪”是语言变量，“白的”是语言变量的值“王峰热爱祖国”“王峰”和“祖国”是语言变量,“热爱”是语言变量之间的关系例如：语言变量的值或语言变量之间的关系可以是数字、词等自动化系仪自教研室7确定性事实知识的表示。一般使用三元组表示：（对象，属性，值），或者（关系，对象1，对象2）例如：事实“老李年龄是45岁。”可以表示为：(Li，Age，45)事实“老李、老张是朋友。”可以表示为：(Friend，Li，Zhang)2.2.2产生式知识表示法2.2.2.1产生式表示知识的基本方法事实的表示-事实的表示自动化系仪自教研室8不确定性事实知识的表示。一般使用四元组表示：（对象，属性，值，可信度）或者（关系，对象1，对象2，可信度）例如：事实“老李年龄很可能是45岁。”可以表示为：(Li，Age，45，0.8)事实“老李、老张不大可能是朋友。”可以表示为：(Friend，Li，Zhang，0.1)2.2.2产生式知识表示法2.2.2.1产生式表示知识的基本方法事实的表示-事实的表示自动化系仪自教研室92.2.2产生式知识表示法2.2.2.1产生式表示知识的基本方法规则的表示P是产生式的前提，也称为前件，它给出了该产生式可否使用的先决条件，由事实的逻辑组合来构成；-描述事物之间的因果关系-规则的产生式表示形式常称为产生式规则规则的作用产生式规则的基本形式P→Q或者IFPTHENQQ是一组结论或操作，也称为产生式的后件，它指出当前题P满足时，应该推出的结论或应该执行的动作自动化系仪自教研室102.2.2产生式知识表示法2.2.2.1产生式表示知识的基本方法规则的表示产生式的含义如果前提P满足，则可推出结论Q或执行Q所规定的操作产生式规则的例子r6:IF动物有犬齿AND有爪AND眼盯前方THEN该动物是食肉动物其中，r6是该产生式的编号；“动物有犬齿AND有爪AND眼盯前方”是产生式的前提P；“该动物是食肉动物”是产生式的结论Q。自动化系仪自教研室112.2.2产生式知识表示法2.2.2.1产生式表示知识的基本方法与蕴涵式的主要区别蕴涵式表示的知识只能是精确的，产生式表示的知识可以是不确定的原因是蕴涵式是一个逻辑表达式，其逻辑值只有真和假蕴含式的匹配一定要求是精确的，而产生式的匹配可以是不确定的原因是产生式的前提条件和结论都可以是不确定的，因此其匹配也可以是不确定的自动化系仪自教研室122.2.2产生式知识表示法2.2.2.1产生式表示知识的基本方法与蕴涵式的主要区别例如，在专家系统MYCIN中有如下产生式：IF本生物的染色斑是革兰氏阴性，本微生物的形状呈杆状，病人是中间宿主THEN该微生物是绿脓杆菌，置信度为0.6这在谓词中的逻辑蕴含式是不能表示的！它表示，当前题中列出的各个条件都满足时，结论“该微生物是绿脓杆菌”可以相信的程度是0.6。自动化系仪自教研室132.2.2产生式知识表示法2.2.2.1产生式表示知识的基本方法与(计算机程序语言)条件语句的主要区别前件结构不同--产生式的前件可以是一个复杂的的结构--传统程序设计语言中的左部仅仅是一个布尔表达式控制流程不同--产生式系统中满足前提条件的规则被激活后，不一定被立即执行，能否执行将取决于冲突消解策略--传统程序设计语言中是严格地从一个条件语句向其下一个条件语句传递自动化系仪自教研室14推理机综合数据库规则库产生式系统的基本结构2.2.2产生式知识表示法2.2.2.2产生式系统的组成把一组产生式放在一起，让它们互相配合，协同作用，一个产生式的结论可以供给另个产生式作为前提使用，以这种方式求得问题的解决，这样的系统称为产生式系统自动化系仪自教研室152.2.2产生式知识表示法2.2.2.2产生式系统的组成综合数据库DB(DataBase)推理过程中，当规则库中某条规则的前提可以和综合数据库的已知事实匹配时，该规则被激活输入的事实中间结论最终结论问题的初始状态用于推理过程的规则匹配存放求解问题的各种当前信息推理机综合数据库规则库产生式系统的基本结构自动化系仪自教研室162.2.2产生式知识表示法2.2.2.2产生式系统的组成规则库RB(RuleBase)•也称知识库KB(KnowledgeBase),用于存放与求解问题有关的所有规则的集合推理机综合数据库规则库产生式系统的基本结构作用：是产生式系统问题求解的基础要求：知识的完整性、一致性、准确性、灵活性和知识组织的合理性自动化系仪自教研室172.2.2产生式知识表示法2.2.2.2产生式系统的组成推理机(InferenceEngine)推理机综合数据库规则库产生式系统的基本结构选择匹配冲突消解执行操作终止推理路径解释自动化系仪自教研室18正向推理2.2.2产生式知识表示法2.2.2.3产生式系统的推理策略也称为数据驱动方式，它是从初始状态出发，朝着目标状态前进，正向使用规则的一种推理方法。所谓正向使用规则，是指以问题的初始状态作为初始综合数据库，仅当综合数据库中的事实满足某条规则的前提时，该规则才被使用优点是简单明了且能求出所有解缺点是执行效率较低，原因是它驱动了一些与问题无关的规则，具有一定的盲目性。自动化系仪自教研室19推理机的一次正向推理过程从规则库中取一个条规则，将其前提同当前动态数据库中的事实/数据进行模式匹配匹配成功否把该规则的结论放入当前动态数据库：或执行规则所规定的动作NY2.2.2产生式知识表示法2.2.2.3产生式系统的推理策略正向推理自动化系仪自教研室20优点是不寻找无用数据，不使用与问题无关的规则。因此，对那些目标明确的问题，使用反向推理方式是一种最佳选择。2.2.2产生式知识表示法2.2.2.3产生式系统的推理策略也称为目标驱动方式，它是从目标（作为假设）状态出发，朝着初始状态前进，反向使用规则的一种推理方法。所谓逆向使用规则，是指以问题的目标状态作为初始综合数据库，仅当综合数据库中的事实满足某条规则的后件时，该规则才被使用。反向推理自动化系仪自教研室21例-动物识别系统这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：R1:IF该动物有毛THEN该动物是哺乳动物R2:IF该动物有奶THEN该动物是哺乳动物R3:IF该动物有羽毛THEN该动物是鸟R4:IF该动物会飞AND会下蛋THEN该动物是鸟R5:IF该动物吃肉THEN该动物是食肉动物R6:IF该动物有犬齿AND有爪AND眼盯前方THEN该动物食肉动物2.2.2产生式知识表示法2.2.2.4产生式系统的应用举例自动化系仪自教研室22R7:IF该动物是哺乳动物AND有蹄THEN该动物是有蹄类动物R8:IF该动物是哺乳动物AND是嚼反刍动物THEN该动物是动物有蹄类动物R9:IF该动物是哺乳动物AND是食肉动物AND是黄褐色AND身上有暗斑点THEN该动物是金钱豹2.2.2产生式知识表示法例-动物识别系统2.2.2.4产生式系统的应用举例例-动物识别系统这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：自动化系仪自教研室23R10:IF该动物是哺乳动物AND是食肉动物AND是黄褐色AND身上有黑色条纹THEN该动物是虎R11:IF该动物是有蹄类动物AND有长脖子AND有长腿AND身上有暗斑点THEN该动物是长颈鹿2.2.2产生式知识表示法例-动物识别系统2.2.2.4产生式系统的应用举例这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：自动化系仪自教研室24R12:IF该动物是有蹄类动物AND身上有黑色条纹THEN该动物是斑马R13:IF该动物是鸟AND有长脖子AND有长腿AND不会飞AND有黑白二色THEN该动物是驼鸟2.2.2产生式知识表示法2.2.2.4产生式系统的应用举例例-动物识别系统这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：自动化系仪自教研室252.2.2产生式知识表示法2.2.2.4产生式系统的应用举例例-动物识别系统这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：R14:IF该动物是鸟AND会游泳AND不会飞AND有黑白二色THEN该动物是企鹅R15:IF该动物是鸟AND善飞THEN该动物是信天翁自动化系仪自教研室262.2.2产生式知识表示法2.2.2.4产生式系统的应用举例例-动物识别系统这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：说明：上述规则仅是一种直接表示方式，用三元组表示R15如下：R15：IF（动物，类别，鸟）AND（动物，本领，善飞）THEN（动物，名称，信天翁）自动化系仪自教研室272.2.2产生式知识表示法2.2.2.4产生式系统的应用举例例-动物识别系统这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：该系统是用来识别7种动物的,但它并没有简单地设计7条规则,而是设计了15条.自动化系仪自教研室282.2.2产生式知识表示法2.2.2.4产生式系统的应用举例例-动物识别系统这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：当已知的事实不完全时,虽不能推出最终结论,但可以得到分类结果当需要增加对其它动物(如牛马等)的识别时,规则中只需增加关于这些动物个性方面的知识,如R9-R15那样,而对R1-R10可直接利用,这样增加的规则就不会太多自动化系仪自教研室292.2.2产生式知识表示法2.2.2.4产生式系统的应用举例例-动物识别系统这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：现给定初始条件，即初始综合数据库包含有如下事实：该动物有暗斑点，有长脖子，有长腿，有奶，有蹄求该动物是那种动物？自动化系仪自教研室302.2.2.4产生式系统的应用举例例-动物识别系统长颈鹿斑马长脖子长腿暗斑点有蹄类黑条纹有蹄哺乳动物嚼反刍动物有毛r2r7r8r11r12