08 Chapter08

人工智能原理,(符号计算科学),PrinciplesofArtificialIntelligence,第八章：知识基系统,Chapter08Knowledge-BasedSystems(KBS),01什么是KBS？,Section01WhataKBSIs?,01什么是KBS？,1.1知识基系统就是基于知识的系统,所谓“知识基系统”，其实就是“基于知识的系统”，译自：knowledge-basedsystems(KBS)。,知识基系统，或者基于知识的系统，是符号计算意义下的人工智能系统，或者说，是符号计算意义下的智能机器。,知识基系统，或者基于知识的系统，意味着系统要素(即系统最为重要的元素)是“知识”。,01什么是KBS？,1.2知识基意味着知识库,就其字面意义而言，将knowledge-basedsystem译作“基于知识的系统”似乎更为贴切。,然而，所有的知识基系统，必定都有自己的知识库(KnowledgeBase)，而“知识基”恰好具有“知识库”的含义。,“知识基系统”，自然意味着“具有知识的系统”，同时，也意味着“带有知识库的系统”。,01什么是KBS？,1.3知识基系统的本质特征“知识推理”,“知识”(Knowledge)并不等同于“数据”(Data)。,自然地，“知识库”(KnowledgeBase)也并不等同于“数据库”(DataBase)。,“知识基系统”中的知识，必定需要具备其可利用性，而对知识的利用，自然是一个逻辑推理的过程。,因此，“知识基系统”的本质特征是：“知识+推理”,01什么是KBS？,1.4最典型的知识基系统专家系统(ExpertSystem),最典型的“知识基系统”是“专家系统”(ExpertSystem)。,专家系统的核心部件是：知识库(KnowledgeBased)推理机(InferenceMachine),专家系统体现了“知识基系统”的本质特征：“知识+推理”,02Post机,Section02PostMachine,世界上第一个专家系统(ExpertSystem)，诞生于二十世纪60年代末或70年代初，名为Dendral，是Feigenbaum1965年到斯坦福大学后主持并研制的，是一个可以从化学数据推断分子假说的智能系统。,然而，Dendral的原型可以追溯到更远，那就是产生式系统，或者更准确地说，是Post机。,Post机是专家系统的雏形。,02Post机,2.1Post机是专家系统的雏形,02Post机,2.2符号串置换规则产生式,Post机的历史要追溯到二十世纪40年代。,1943年，Post构造了一种后来被称为“Post机”的符号计算模型。,Post机是一种符号变换系统。Post设计了“符号串置换规则”(StringReplacementRule)，用于对符号串进行重写或变换，并将每一条符号串置换规则称为“产生式”(Production)，后来的“产生式系统”(ProductionSystem)也由此而得名。,02Post机,2.3实现“知识+推理”的要素,Post机对于知识基系统最重要的贡献在于，它将“知识”和“推理”分离，形成了“知识+推理”的体系结构。,Post机的三元结构：(1)符号串置换规则：知识(2)符号置换控制策略：推理(3)总数据库：输入输出接口,02Post机,2.3实现“知识+推理”的要素,Post机还不是知识基系统，因为，符号串置换规则不是本质意义上的专家知识。,然而，Post机的符号置换规则为知识基系统提供了一种知识表达方法，Post机的符号置换操作的控制机制为知识基系统提供了一种推理模式。,Post机具备了实现“知识+推理”的要素。,无论就其体系结构，还是控制行为，Post机都为知识基系统提供了一个原型。,02Post机,2.3实现“知识+推理”的要素,也就是在1965年，Feigenbuam开始了他的Dendral系统的工作，而Dendral的构造就是Post机的构造，Dendral知识的形式采用Post机的产生式，Dendral推理的方式采用Post机的控制策略。,1965年，Newell和Simon基于Post机建立一种认知模型，这大概可以算作最早的知识基系统。,就实现“知识+推理”的目标而言，现代专家系统并未突破Post机的体系结构，就像现代计算机并未突破冯诺依曼机体系结构一样。,03产生式系统,Section03ProductionSystems,03产生式系统,3.1从Post机到产生式系统,Feigenbuam的Dendral系统大约到了1970得以完成，于是，世界上第一个专家系统诞生了。,然而，产生式系统这时已经不再等同于Post机。,换个角度看，我们就会发现，世界上第一个专家系统，实际上是一个产生式系统。,Post机只是一个特殊的符号置换操作系统，而产生式系统泛化了Post机的符号计算功能，使其成为一般的或通用的符号计算系统。,03产生式系统,3.1从Post机到产生式系统,产生式系统中知识的表达形式是Post机的“符号串置换规则”，即所谓的“产生式”(Production)。“产生式系统”(ProductionSystem)因此而得名。,产生式规则是一种高性能的知识表达方法，无论是其知识表达能力，还是其隐喻的逻辑推理机制，都是完美的。,知识基系统大多采用产生式规则的知识表达方法，这类系统因而又被称为“规则基系统”或“基于规则的系统”(Rule-BasedSystem)。,03产生式系统,3.2产生式系统的体系结构,产生式系统的结构即Post机的三元结构：(1)产生式规则库(PRB)(2)控制策略机构(CSA)(3)总数据库(GDB),03产生式系统,3.2产生式系统的体系结构,03产生式系统,3.2产生式系统的体系结构,过程数据是很特殊的，在问题求解过程中，也就是在系统的演化过程，过程数据既可能加入输入数据成为系统进一步演化的基础，又可能加入输出数据，作为系统输出的最终结果。,04专家系统,Section04ExpertSystems,04专家系统,4.1专家系统的内涵定义：,专家系统(ES)是一种计算机程序系统，可以表达为一个二元组：ES=KB,IM，其基本成份就是知识库(KB)和推理机(IM)，知识库KB记忆或存储了特定专业领域内专家级的知识，而推理机IM具有与该专业领域专家相似的知识运用能力，能运用知识库KB中的知识求解专业领域内的问题。,简而言之，所谓专家系统，就是模拟人类专家的计算机程序系统。,我们已经知道，产生式系统(ProductionSystem)是专家系统(ExpertSystem)的雏形，而世界上第一个专家系统Dendral就是一个产生式系统。,然而，专家系统并不等同于产生式系统，或者说，产生式系统并不是专家系统的全部。,04专家系统,4.2专家系统的外延多样性,Dendral之后，各种专家系统层出不穷，它们实现的途径不同，功能不同，在模拟人类专家的共同特征下，表现出了突出的多样性。,04专家系统,4.2专家系统的外延多样性,功能上的多样性,解释型专家系统(forInterpretation)：基本的功能是鉴别事物，例如：指纹识别，语音理解，物质结构分析。,预测型专家系统(forPrediction)：基本的功能是推断未来，例如：气象预报，人口预测，经济预估。,诊断型专家系统(forDiagnosis)：基本的功能是检测系统故障，例如：医疗诊断，汽车故障检测，雷达系统故障诊断。,设计型专家系统(forDesign)：基本的功能是自动设计，例如：自动编程，自动CAD，辅助建筑设计。,04专家系统,4.2专家系统的外延多样性,规划型专家系统(forPlanning)：基本的功能是规划和调度，例如：军事运筹，交通运输调度，工程项目论证。,监测型专家系统(forMonitoring)：基本的功能是监测系统状态，例如：防空预警，疫情监测，楼宇安全系统。,功能上的多样性,控制型专家系统(forControl)：基本的功能是管理和调控系统，例如：自治机器人控制，复杂工业过程控制，企业管理。,04专家系统,4.2专家系统的外延多样性,修理型专家系统(forRepair)：基本的功能是辅助系统修理，例如：汽车修理，飞机修理，宇航系统修理。,教学型专家系统(forInstruction)：基本的功能是辅助教学，又称CAI(Computer-AssistedInstruction)。,功能上的多样性,04专家系统,4.2专家系统的外延多样性,知识表达的多样性,推理形式的多样性,产生式规则语义网络框架剧本黑板谓词逻辑,前向推理逆向推理,确定性推理不确定性推理模糊推理,继承联想网络匹配,04专家系统,4.3专家系统的体系结构基本结构,专家系统ES=KB,IM的核心是“知识推理”，因此，专家系统本质的或基本的构成是：ES=KBIM,04专家系统,4.3专家系统的体系结构一般结构,专家系统的一般结构是一个三元组：ES=KB,IM,IN,IN是解释器(Interpreter)，其功能在于记录推理过程，解释推理结果。,04专家系统,4.3专家系统的体系结构理想结构,专家系统的理想结构是一个五元组：ES=KB,IM,IN,KA,NLP,KA是学习机，其功能在于自主地(或自治地)获取领域知识(KnowledgeAcquiring)。,NLP是自然语言处理模块，是具有自然语言理解功能的人机界面。,05专家系统实践,Section04AnESExercise,05专家系统实践,5.1实践的目的综合运用AI基本原理,专家系统并不神秘。,用Lisp程序设计语言构造一个简单的专家系统并非一件难事。,本节将基于第三章曾经描述过的16条动物知识，综合运用本课程学习的AI基本原理，构造一个简单的动物专家系统。,通过动物专家系统的设计和实现，将检验我们的学成果，并强化我们对AI的学习。,动物专家系统的设计与实现需要我们综合地运用本课程所学习的AI基本原理，其中包括：,知识表达方法：一阶谓词逻辑/产生式规则,推理机制：前向推理/逆向推理/归结原理,控制策略：状态空间法图搜索策略,知识基结构：产生式系统,实现环境：Lisp程序设计语言,05专家系统实践,5.1实践的目的综合运用AI基本原理,05专家系统实践,5.2一个动物专家系统Animal_Expert的设计问题描述,现有：动物专家知识：,知识01：K01“有毛发的动物是哺乳动物”知识02：K02“产乳的动物是哺乳动物”知识03：K03“有羽毛的动物是鸟”知识04：K04“会飞且会下蛋的动物是鸟”知识05：K05“吃肉的哺乳动物是食肉动物”知识06：K06“有利齿有爪且眼睛前视的哺乳动物是食肉动物”,05专家系统实践,5.2一个动物专家系统Animal_Expert的设计问题描述,现有：动物专家知识：,知识07：K07“有蹄的哺乳动物是蹄类动物”知识08：K08“反刍的哺乳动物是蹄类动物”知识09：K09“反刍的蹄类动物是偶蹄类动物”知识10：K10“黄褐色深斑点食肉哺乳动物是猎豹”知识11：K11“黄褐色黑条纹食肉哺乳动物是老虎”,05专家系统实践,5.2一个动物专家系统Animal_Expert的设计问题描述,现有：动物专家知识：,知识12：K12“长腿长颈深斑点黄褐色的蹄类动物是长颈鹿”知识13：K13“有黑色条纹的蹄类动物是斑马”知识14：K14“长腿长颈黑白相间颜色不会飞的鸟是鸵鸟”知识15：K15“会游泳不会飞的黑白色鸟是企鹅”知识16：K16“善于飞行的鸟是海燕”,05专家系统实践,5.2一个动物专家系统Animal_Expert的设计问题描述,要求：设计专家系统Animal_Expert，执行任务：,已知动物x的某些特征，如：“有羽毛”，“会下蛋”，“不会飞”，等等，解答：,(1)“x是什么动物？”一类问题(合适的推理形式：a.正向推理b.谓词演算提取答案),(2)“x是老虎吗？”一类问题(合适的推理形式：a.逆向推理b.谓词演算归结反演),05专家系统实践,5.3Animal_Expert的体系结构产生式系统,我们的动物专家系统Animal_Expert将具有产生式系统的结构：(1)产生式规则库(PRB)(2)控制策略机构(CSA)(3)总数据库(GDB),05专家系统实践,5.4Animal_Expert的知识库知识表达,规则库(PRB),正如第三章所介绍的，Animal_Expert的知识表达是“产生式规则谓词逻辑”的混合体。,定义谓词：,Prd01：be(x,y)(x是y(某种性质的)Prd02：be_a(x,y)(x是y(某种动物)Prd03：has(x,y)(x有y)Prd04：can(x,y)(x会y(动作或技能)Prd05：cannot(x)(x,y)(x不会y(动作或技能)Prd06：be_ungulate(x)(x是蹄类动物),cannot最好用can描述，但这会破坏Horn子句的结构。,定义常量：,Con01：mammal(名称：哺乳动物)Con02：bird(名称：鸟)Con03：carnivore(名称：食肉动物)Con04：ungulate(名称：蹄类动物)Con05：eventoed(名称：偶蹄类动物)Con06：cheetah(名称：猎豹)Con07：tiger(名称：老虎)Con08：giraffe(名称：长颈鹿),05专家系统实践,5.4Animal_Expert的知识库知识表达,规则库(PRB),定义常量：,Con09：zebra(名称：斑马)Con10：ostrich(名称：鸵鸟)Con11：penguin(名称：企鹅)Con12：albatross(名称：海燕)Con13：hairs(名称：毛发)Con14：feathers(名称：羽毛)Con15：hoofs(名称：蹄)Con16：claws(名称：爪),05专家系统实践,5.4Animal_Expert的知识库知识表达,规则库(PRB),定义常量：,Con17：pointed_teeth(名称：利齿)Con18：forward_eyes(名称：前视的眼睛)Con19：long_legs(名称：长腿)Con20：long_neck(名称：长颈)Con21：dark_spots(名称：深斑点)Con22：black_strips(名称：黑条纹)Con23：black_&_white(性质：黑白色的)Con24：tawny(性质：黄褐色的),05专家系统实践,5.4Animal_Expert的知识库知识表达,规则库(PRB),定义常量：,Con24：give_milk(动作：产乳)Con25：fly(动作：飞)Con26：lay_eggs(动作：下蛋)Con27：eat_meat(动作：吃肉)Con28：chewcud(动作：反刍)Con29：swim(动作：游泳)Con30：fly_well(动作：善于飞行),05专家系统实践,5.4Animal_Expert的知识库知识表达,规则库(PRB),05专家系统实践,5.4Animal_Expert的知识库知识表达,规则库(PRB),鉴于Animal_Expert的特殊性，略去全称变量x，动物知识子句的Lisp描述可为：,动物知识K01：“有毛发的动物是哺乳动物”谓词公式：xhas(x,hairs)be_a(x,mammal)Horn子句：has(x,hairs)be_a(x,mammal)Lisp语言描述：(setqK01(+be_amammal)(hashairs),既是谓词公式，又是产生式规则,一般形式：(结论)(前提1)(前提2)(前提n),05专家系统实践,5.4Animal_Expert的知识库知识表达,规则库(PRB),类似地，16条动物知识可分别用Lisp描述：,动物知识K02：“产乳的动物是哺乳动物”(setqK02(+be_amammal)(cangive_milk),动物知识K03：“有羽毛的动物是鸟”(setqK03(+be_abird)(hasfeathers),动物知识K04：“会飞且会下蛋的动物是鸟”(setqK04(+be_abird)(canfly)(canlay_eggs),05专家系统实践,5.4Animal_Expert的知识库知识表达,规则库(PRB),类似地，16条动物知识可分别用Lisp描述：,动物知识K05：“吃肉的哺乳动物是食肉动物”(setqK05(+be_acarnivore)(be_amammal)(caneat_meat),动物知识K06：“有利齿有爪且眼睛前视的哺乳动物是食肉动物”(setqK06(+be_acarnivore)(be_amammal)(haspointed_teeth)(hasclaws)(hasforward_eyes),05专家系统实践,5.4Animal_Expert的知识库知识表达,规则库(PRB),类似地，16条动物知识可分别用Lisp描述：,动物知识K07：“有蹄的哺乳动物是蹄类动物”(setqK07(+be_aungulate)(be_amammal)(hashoofs),动物知识K08：“反刍的哺乳动物是蹄类动物”(setqK08(+be_aungulate)(be_amammal)(canchew_cud),05专家系统实践,5.4Animal_Expert的知识库知识表达,规则库(PRB),类似地，16条动物知识可分别用Lisp描述：,动物知识K09：“反刍的蹄类动物是偶蹄类动物”(setqK09(+be_aeven_toed)(be_aungulate)(canchew_cud),动物知识K10：“黄褐色深斑点的食肉的哺乳动物是猎豹”(setqK10(+(be_acheetah)(be_amammal)(be_acarnivore)(betawny)(hasdark_spots),05专家系统实践,5.4Animal_Expert的知识库知识表达,规则库(PRB),类似地，16条动物知识可分别用Lisp描述：,动物知识K11：“黄褐色黑条纹食肉哺乳动物是老虎”(setqK11(+be_atiger)(be_amammal)(betawny)(be_acarnivore)(hasblack_strips),动物知识K12：“长腿长颈深斑点黄褐色的蹄类动物是长颈鹿”(setqK12(+be_agiraffe)(be_aungulate)(belong_legs)(belong_neck)(betawny)(hasdark_spots),05专家系统实践,5.4Animal_Expert的知识库知识表达,规则库(PRB),类似地，16条动物知识可分别用Lisp描述：,动物知识K13：“有黑色条纹的蹄类动物是斑马”(setqK13(+be_azebra)(be_aungulate)(hasblack_strips),动物知识K14：“长腿长颈黑白相间颜色不会飞的鸟是鸵鸟”(setqK14(+be_aostrich)(be_abird)(belong_legs)(belong_neck)(beblack_&_white)(cannotfly),05专家系统实践,5.4Animal_Expert的知识库知识表达,规则库(PRB),类似地，16条动物知识可分别用Lisp描述：,动物知识K15：“会游泳不会飞的黑白色鸟是企鹅”(setqK15(+be_apenguin)(be_abird)(canswim)(cannotfly)(beblack_&_white),动物知识K16：“善于飞行的鸟是海燕”(setqK16(+be_aalbatross)(be_abird)(canfly)(canfly_well),现在，构造一个由谓词公式子句组成的动物学知识库，将是一个极为简单的任务，我们只需要把那些Lisp描述的子句表Ki_clause组装起来就可以了：,(setqanimal_knowledge_base(K01K02K03K04K05K06K07K08K09K10K11K12K13K14K15K16),05专家系统实践,5.4Animal_Expert的知识库组装PRB,规则库(PRB),动物学知识库animal_knowledge_base简单到了及至，仅仅是一个以Lisp原子为元素的Lisp表。,05专家系统实践,5.5Animal_Expert的全局数据库GDB,Animal_Expert的总数据库GDB将一个Lisp全局变量，其中，可能包括的原子有：,(1)facts：全局变量，记忆或存储输入数据，即问题求解活动开始前已知的事实；,(2)results：全局变量，记忆或存储输出数据，即问题求解活动结束时系统输出的问题求解结论；,(3)hypothesis：全局变量，逆向推理或反演开始时的目标或假设；,总数据库(GDB),05专家系统实践,5.5Animal_Expert的全局数据库GDB,因此，Animal_Expert的总数据库GDB可用Lisp语言描述为：,总数据库(GDB),(setqGDB(factsresultshypothesisOpenClosed),05专家系统实践,5.6Animal_Expert的推理机正向推理机CSA_fw,控制策略(CSA),中间结论,中间结论,中间结论,最终结论,正向推理：由已知前提推断未知结论,已知前提,产生式规,产生式规,产生式规,产生式规,解答：“x是什么动物？”一类特殊疑问句问题。,05专家系统实践,5.6Animal_Expert的推理机正向推理机CSA_fw,控制策略(CSA),设置i=1；,将第i条产生式的前提与GDB中的事实匹配；,若匹配不成功，转向step6；,提取第i条产生式的结论CON；,若CON是新的事实，则将其分别添加进GDB中的facts和results，并转向step1；,若i等于知识库中的产生式总数I，则输出计算结果并停机；,设置i=i+1，转向step2。,05专家系统实践,5.6Animal_Expert的推理机正向推理机CSA_fw,控制策略(CSA),构造正向推理机CSA_fw,KB：临时知识库PR：被操作产生式ANC：PR前提CON：PR结论MAT：ANC各事实匹配情况逻辑值,循环结构初始化，将知识库animal_knowledge_base拷贝给KB。,CONTINUE(cond(nullKB)(returnresults)(setqPR(carKB)(setqKB(cdrKB)(setqANC(cdr(evalPR)(setqMAT(mapcar(lambda(x)(memberp(subst+x)facts)ANC)(cond(not(memberpNilMAT)(setqCON(car(evalPR)(cond(not(memberpCONfacts)(setqresults(consCONresults)(setqfacts(consCONfacts)(setqKBanimal_knowledge_base)(goCONTINUE),05专家系统实践,5.6Animal_Expert的推理机正向推理机CSA_fw,控制策略(CSA),KB空，意味着已无知识可利用，输出计算结果并结束。,将KB中的第一条产生式取出并赋给PR。,将KB中的第一条产生式从KB中删除。,将PR中的前提条件赋给ANC(eval提取PR中Ki的值)。,检查ANC中的各前提条件是否都是已知事实。,如果CON是新的事实，则将CON添加进facts和results，并更KB，重头循环搜索。,用+替换x中的。,05专家系统实践,5.6Animal_Expert的推理机正向推理机CSA_fw,控制策略(CSA),问题P：x是什么动物？,初始化专家系统Animal_Expert全局数据库GDB：,(setqfacts(+canchew_cud)(+hashairs)(setqresultsNil)(setqGDB(factsresults),05专家系统实践,5.6Animal_Expert的推理机正向推理机CSA_fw,控制策略(CSA),运行推理机CSA_fw：,(CSA_fw)results,(+be_aeven_toed)(+be_aungulate)(+be_amammal),K01：有毛发的动物是哺乳动物。,K08：反刍食物的哺乳动物是有蹄动物。,K09：反刍的有蹄类动物是有偶蹄动物。,05专家系统实践,5.6Animal_Expert的推理机正向推理机CSA_fw,控制策略(CSA),问题P：x是什么动物？,05专家系统实践,5.6Animal_Expert的推理机正向推理机CSA_fw,控制策略(CSA),(setqfacts(+betawny)(+canchew_cud)(+hashairs)(+haslong_legs)(+haslong_neck)(+hasdark_spots)(setqresultsNil)(setqGDB(factsresults),05专家系统实践,5.6Animal_Expert的推理机正向推理机CSA_fw,控制策略(CSA),(CSA_fw)results,(+be_agiraffe)(+be_aeven_toed)(+be_aungulate)(+be_amammal),K01：有毛发的动物是哺乳动物。,K08：反刍食物的哺乳动物是蹄类动物。,K09：反刍的有蹄类动物是偶蹄类动物。,K12：长腿长颈深斑点黄褐色的蹄类动物是长颈鹿。,05专家系统实践,5.7Animal_Expert的推理机逆向推理机CSA_bw,控制策略(CSA),过渡前提,过渡前提,过渡前提,已知前提,逆向推理：由既定目标搜索前提条件,既定目标,反向产生式,反向产生式,反向产生式,反向产生式,解答：“x是老虎吗？”一类一般疑问句问题。,05专家系统实践,5.7Animal_Expert的推理机逆向推理机CSA_bw,控制策略(CSA),设置j=1；,取hypothesis第j项hypo(j)；,若hypo(j)在facts中，转向step11；,设置i=1；,取第i条产生式Ki的结论部分CON；,若CONhypo(j)，转向step9；,取Ki的前提部分ANC，并递归调用算法：REC=Backward_Algorithm(ANC)；,05专家系统实践,5.7Animal_Expert的推理机逆向推理机CSA_bw,控制策略(CSA),若REC=“真”，转向step11；,若i等于知识库中的产生式总数I，则返回假；,令：i=i+1，转向step5；,若hypo(j)是新的事实，将其分别地拷贝给facts和results；,若j等于hypothesis的长度H，则返回“真”；,令：j=j+1，转向step2。,05专家系统实践,5.7Animal_Expert的推理机逆向推理机CSA_bw,控制策略(CSA),CSA_bw的Lisp实现：,(defun(CSA_bwhypothesis)(prog(HYPCRB)CONTINUE_ACONTINUE_B内循环体(goCONTINUE_B)(goCONTINUE_A),构造逆向推理机CSA_bw,HYP：假设项CRB：内循环返回值,05专家系统实践,5.7Animal_Expert的推理机逆向推理机CSA_bw,控制策略(CSA),CONTINUE_A(cond(nullhypothesis)(returnT)(setqHYP(carhypothesis)(setqhypothesis(carhypothesis)(cond(not(memberpHYPfacts)(prog(KBPRANCCONREC)(setqKBanimal_knowledge_base)CONTINUE_B内循环：搜索KB中满足HYP的产生式(goCONTINUE_B)cond(equalpCRBNil)(returnNil)(setqfacts(consHYPfacts)(setqresults(consHYPresults)(goCONTINUE_A),hypothesis空意味着各假设项均已得到证实，返回真，并结束。,将hypothesis中第一项取出。,HYP在facts中意味着HYP假设成立，无需对HYP进行操作，循环A处理下一项假设，反之，进入循环B。,KB：临时知识库PR：被操作产生式ANC：PR前提CON：PR结论REC：递归返回值,循环结构初始化，将知识库拷贝给KB。,循环B返回T意味着HYP被证实，而非hypothesis被证实；但循环B返回Nil，不仅意味着HYP被否定，hypothesis也被否定。,HYP是新的事实，将其添加进facts和results。,05专家系统实践,5.7Animal_Expert的推理机逆向推理机CSA_bw,控制策略(CSA),CONTINUE_B(cond(nullKB)(return(setqCRBNil)(setqPR(carKB)(setqKB(cdrKB)(setqCON(car(evalPR)(cond(equalpHYPCON)(setqANC(cdr(evalPR)(setqANC(subst+ANC)(setqREC(CSA_bwANC)(cond(equalpRECT)(return(setqCRBT)(goCONTINUE_B),KB空，意味着已无知识可用于证实HYP，因而也无法证实整个假设。,将PR的结论部分拷贝给CON。,如果HYP=CON，将PR前提部分拷贝给ANC。,用+替换ANC中的。,如果递归返回结果REC为真，表明假设ANC被证实，因而假设项HYP被证实，故成功退出循环B，继续循环A以处理hypothesis中下一个假设项。,将ANC作为新的假设递归地调用推理机CSA_bw。,05专家系统实践,5.7Animal_Expert的推理机逆向推理机CSA_bw,控制策略(CSA),问题P：x是蹄类动物？,初始化专家系统Animal_Expert全局数据库GDB：,(setqfacts(+canchew_cud)(+hashairs)(setqhypothesis(+be_aungulate)(setqresultsNil)(setqGDB(factshypothesisresults),05专家系统实践,5.7Animal_Expert的推理机逆向推理机CSA_bw,控制策略(CSA),运行推理机CSA_bw：,(CSA_bw),T,CSA_bw返回T，意味着假设hypothesis=(+be_aungulate)成立，即x是蹄类动物。,results,(+be_aungulate)(+be_amammal),05专家系统实践,5.7Animal_Expert的推理机逆向推理机CSA_bw,控制策略(CSA),运行示例：,CSA_bw推理过程：,(1)检查假设(+be_aungulate)是否在全局数据库GDB的facts中(不在)；,检索知识库寻找以(+be_aungulate)为结论的产生式，发现：动物知识K07：“有蹄的哺乳动物是蹄类动物”,于是，将(+be_amammal)和(+hashoofs)为新的假设，第一次递归调用推理机CSA_bw(1)；,05专家系统实践,5.7Animal_Expert的推理机逆向推理机CSA_bw,控制策略(CSA),运行示例：,CSA_fw推理过程：,(3)检查假设(+be_amammal)是否在全局数据库GDB的facts中(不在)；,(4)检索知识库寻找以(+be_amammal)为结论的产生式，发现：动物知识K01：“有毛发的动物是哺乳动物”,于是，将(+hashairs)为新的假设，第二次递归调用推理机CSA_bw(2)；,05专家系统实践,5.7Animal_Expert的推理机逆向推理机CSA_bw,控制策略(CSA),运行示例：,CSA_fw推理过程：,(5)检查发现(+hashairs)在facts中，递归CSA_bw(2)返回T，即规则K01成立，假设(be_amammal)被证实，故分别拷贝给facts和results；,(6)又检查假设(+hashoofs)是否在全局数据库GDB的facts中(不在)；,(7)检索知识库，未发现以(+hashoofs)为结论的产生式，递归CSA_bw(1)返回Nil，故规则K07未得到验证，假设(+be_aungulate)还不能证实；,05专家系统实践,5.7Animal_Expert的推理机逆向推理机CSA_bw,控制策略(CSA),运行示例：,CSA_fw推理过程：,(8)继续检索知识库寻找以(+be_aungulate)为结论的产生式，发现：动物知识K08：“反刍的哺乳动物是蹄类动物”,于是，将(+be_amammal)和(+canchew_cud)为新假设，第三次递归调用推理机CSA_bw(3)；,(9)检查假设(+be_amammal)是否在全局数据库GDB的facts中，(在，注：(4)-(5)的结果)；,05专家系统实践,5.7Animal_Expert的推理机逆向推理机CSA_bw,控制策略(CSA),运行示例：,CSA_fw推理过程：,(10)检查发现(+canchew_cud)在facts中，递归CSA_bw(3)返回T，故规则K8成立，即结论(+be_aungulate)成立，假设(+be_aungulate)因而被证实，同时，(+be_aungulate)被分别地拷贝给facts和results。,05专家系统实践,逆向推理机CSA_bw是针对“x是老虎吗？”一类一般疑问句问题的。解答这一类问题的另一种有效的推理形式是归结原理。,Animal_Expert的知识库animal_knowledge_base中的知识是用谓词逻辑公式描述的，并且，具有Horn子句的形式，易于运用归结原理进行反演推理。,归结反演推理机CSA_rp的推理机制自然是归结原理，同时，其归结反演过程的控制策略将采用状态空间法中的图搜索策略。,05专家系统实践,CSA_rp的状态空间S：Horn子句集合,CSA_rp的初始状态s(o)：归结反演中待证明的定理T的否定，即：T，如：(be_atiger)(即求证x是老虎),CSA_rp的目标状态s(g)：归结反演寻求的Nil子句,CSA_rp的算子空间O：归结反演的公里系统A，包括知识库animal_knowledge_base以及关于动物x的已知的事实。,05专家系统实践,将T作为起始节点s(o)放入Open表中；,将sbn中的归结子节点放入Open的前端，并设置其通向nb_r的指针；,若Open第一个节点=Nil，成功退出；,将Open中的第一个节点nb_r送入Closed；,归结节点nb_r，生成其全部归结子节点sbn；,若Open空，则失败退出；,转向step2。,归结反演过程采用深度优先搜索(depth-firstsearch)策略。,05专家系统实践,(defun(CSA_rpnot_Tfacts)(Prog(Axiomnd_rsbn)(setqAxiom(appendfactsanimal_knowledge_base)(cons(gensymst)Open)(setq(carOpen)not_T)(putprop(carOpen)TOPindex)(putprop(carOpen)Nilsubstition)(putprop(carOpen)Nilprd_K)SEARCHDEPTH-FIRSTSEARCH(goSEARCH),CSA_rp的Lisp实现：,T为起始节点s(o),已知事实的集合,Axiom：公理系统nd_r：扩展(归结)节点sbn：归结子节点集合,将知识库与已知事实合并而成公理系统。,生成代表s(o)的原子st001，并放进Open。gensym为Lisp系统函数。,将not_T的值拷贝给st,创建st的指针特性，记录st的父节点，s(o)的指针以TOP标记。,创建st的置换特性，记录st的置换操作，s(o)的置换以Nil标记。,创建st的产生式规则特性，记录生成st所使用的产生式规则Ki，s(o)的置换以Nil标记。,05专家系统实践,SEARCH(cond(nullOpen)(returnnil)(setqnb_r(carOpen)(cond(equalpnb_rnil)(returnT)(setqOpen(cdrOpen)(setqClosed(consnb_rClosed)(expandnb_rsbn)(setqOpen(appendsbnOpen)(mapcar(lambda(x)(putpropxnb_rindex)sbn)(goSEARCH),Open空则失败退出,取Open第一节点,若nb_r=Nil则成功退出。,将nb_r从Open中删除,将nb_r放入Closed,expand为自定义函数，归结扩展nb_r，生成其归结子节点。,将sbn放入Open前端,设置sbn成员指向nb_r的指针。,05专家系统实践,运行示例：已知,待证明定理T：“x是蹄类动物”,公理系统A：(F01F02K01K02K03K04K05K15K16),初始化专家系统Animal_Expert全局数据库GDB：,(setqF01(+canchew_cud)(setqF02(+hashairs)(setqfacts(F01F02)(setqnot_T(be_aungulate)(setqOpenNil)(setqClosedNil)(setqGDB(factsnot_TOpenClosed),05专家系统实践,运行示例：,运行推理机CSA_rp：,(be_aungulate),搜索图,05专家系统实践,(CSA_rp),T,CSA_rp返回T，意味着定理T=(+be_aungulate)成立，即x是蹄类动物。,Open,(st0011st0010st0008st0007),st0011=Nil(s(g),st0001=s(o)=(be_aungulate),05专家系统实践,由Open和Closed，以及各节点的指针特性index和应用规则特性prd_K，可获得CSA_rp推理的路径：,indexstate_vprd_K(1)st0001(be_aungulate)Nil(2)st0005(canchew_cud)(be_amammal)K08(3)st0006(be_amammal)F01(4)st0009(hashairs)K01(5)st0011(Nil)F02,05专家系统实践,正向推理机CSA_fw是针对“x是什么动物？”一类特殊疑问句问题的。解答这一类问题的另一种有效办法是基于归结原理的答案提取技术。,谓词演算中，答案提取的过程分为两个大的步骤，第一：基于归结原理生成归结树；第二：基于归结树生成解答树。,实际上，解答树的生成过程，是问题xP(x)中存在变量x的置换过程，因此，只要我们记录下归结树上的置换s=x/C，便可得到答案P(C)。,05专家系统实践,在基于归结原理的谓词演算中，针对“x是什么动物？”一类特殊疑问句问题，首先需要运用谓词逻辑描述问题，即：T=xbe_a(x),于是：第一：归结的任务就是证明存在“某个x”，它使谓词逻辑公式be_a(x)成立；第二：答案提取的任务就是找到使be_a(x)成立的“某个x”。,05专家系统实践,CSA_ra的状态空间S：Horn子句集合,CSA_ra的初始状态s(o)：问题T=xbe_a(x)的否定，即：T=(be_ax),CSA_ra的目标状态s(g)：归结反演寻求的Nil子句,CSA_ra的算子空间O：归结反演的公里系统A，包括知识库animal_knowledge_base以及关于动物x的已知的事实。,注：CSA_ra仍然采用深度优先的搜索策略。,将T作为起始节点s(o)放入Open表中；,设置sbn归结子节点通向nb_r的指针，记录其应用的事实Fi或知识Ki，以及置换s=x/C；,将Open中的第一个节点nb_r送入Closed；,归结节点nb_r，生成其全部归结子节点sbn；,将sbn中的归结子节点放入Open的前端；,若Open空，