《知识表示和推理之产生式系统.ppt》由会员分享,可在线阅读,更多相关《知识表示和推理之产生式系统.ppt(33页珍藏版)》请在金锄头文库上搜索。
1、第三章第三章 知识表示知识表示和推理和推理用计算机实现知识的表示用计算机实现知识的表示和推理和推理3.1 知识与推理中的关系知识与推理中的关系v专家系统的知识管理特点专家系统的知识管理特点待处理的知识是庞大的,凌乱无序的;待处理的知识是庞大的,凌乱无序的;可以对知识进行增删、修改等简单操作;可以对知识进行增删、修改等简单操作;其知识数据的表示是符合人类思维习惯的,如其知识数据的表示是符合人类思维习惯的,如具有模糊性等。具有模糊性等。2中南大学 智能系统与智能软件研究所3.2 产生式系统产生式系统v定义定义:用来描述若干个不同的以一用来描述若干个不同的以一个基本概念为基础的系统。这个基本个基本概
2、念为基础的系统。这个基本概念就是产生式规则或产生式条件和概念就是产生式规则或产生式条件和操作对的概念操作对的概念。3中南大学 智能系统与智能软件研究所产生式系统可表示的知识种类产生式系统可表示的知识种类v产生式系统适合于表示事实性知产生式系统适合于表示事实性知识和规则性知识。识和规则性知识。4中南大学 智能系统与智能软件研究所产生式的基本形式产生式的基本形式:产生式通常用于表示具有因果关系的知识,产生式通常用于表示具有因果关系的知识,其基本形式是:其基本形式是: P PQQ或者或者 IF P THEN QIF P THEN Q其中,其中,P P是产生式的前提,用于指出该产生式是产生式的前提,用
3、于指出该产生式是否可用的条件;是否可用的条件;QQ是一组结论或操作,用是一组结论或操作,用于指出前提于指出前提P P所指示的条件被满足时,应该所指示的条件被满足时,应该得出的结论或应该执行的操作。得出的结论或应该执行的操作。5中南大学 智能系统与智能软件研究所3.2.1 3.2.1 产生式系统的构造产生式系统的构造推理机构推理机构图图3.1 产生式系统的构成产生式系统的构成作业领域作业领域知识库知识库存放产生式的前提存放产生式的前提及结论及结论存放产生式的规则存放产生式的规则解决规则与前提的匹配、解决规则与前提的匹配、冲突及操作等问题冲突及操作等问题6中南大学 智能系统与智能软件研究所1. 作
4、业领域作业领域v存放事实数据(前提)以及假设(结论)存放事实数据(前提)以及假设(结论)等的场所。等的场所。 例如,对动物园某个野兽的观察得到:例如,对动物园某个野兽的观察得到: D1 身上有毛身上有毛 D2 有尖锐的牙齿有尖锐的牙齿 D3 有锋利的爪子有锋利的爪子 D4 身体是黄褐色身体是黄褐色 D5 身上有黑色斑点身上有黑色斑点 这些事实数据是存放在作业领域里的。这些事实数据是存放在作业领域里的。7中南大学 智能系统与智能软件研究所 2. 知识库知识库v存放存放IF THEN形式的规则的库,又称之为形式的规则的库,又称之为规则库。规则库。 IF 前提前提 成立成立 THEN 结论结论/行动
5、行动 成立成立 规则的举例可见书上规则的举例可见书上36页的页的9条规则。条规则。8中南大学 智能系统与智能软件研究所3. 推理机构推理机构v实现作业领域里的事实与知识库中的规实现作业领域里的事实与知识库中的规则进行匹配,并根据匹配的规则选取一则进行匹配,并根据匹配的规则选取一种予以执行。种予以执行。v推理方法分为三种推理方法分为三种前向推理前向推理后向推理后向推理双向推理双向推理9中南大学 智能系统与智能软件研究所3.6.2 推理机构的运行推理机构的运行 v前向推理前向推理:从一组表示事实的命题出发,使用一从一组表示事实的命题出发,使用一组产生式规则,用以证明该命题是否成立。组产生式规则,用
6、以证明该命题是否成立。 一一般般策策略略:先先提提供供一一批批事事实实(数数据据)到到作作业业领领域域中中。系系统统利利用用这这些些事事实实与与规规则则的的前前提提相相匹匹配配,触触发发匹匹配配成成功功的的规规则则,把把其其结结论论作作为为新新的的事事实实添添加加到到作作业业领领域域中中。继继续续上上述述过过程程,用用更更新新过过的的作作业业领领域域的的所所有有事事实实再再与与规规则则库库中中另另一一条条规规则则匹匹配配,用用其其结结论论再再次次修修改改作作业业领领域域的的内内容容,直直到到没没有有可可匹匹配配的的新新规规则,不再有新的事实加到作业领域中。则,不再有新的事实加到作业领域中。10
7、中南大学 智能系统与智能软件研究所v选择规则到选择规则到执行操作的步骤执行操作的步骤 1. 匹配匹配 把作业领域数据与规则的条件部分相匹配。把作业领域数据与规则的条件部分相匹配。 2. 冲突冲突 当有一条以上规则的条件部分和作业领域的数当有一条以上规则的条件部分和作业领域的数据相匹配时,就需要决定首先使用哪一条规则,据相匹配时,就需要决定首先使用哪一条规则,这这称为冲突消解。称为冲突消解。 3. 操作操作 操作就是执行规则的操作部分。操作就是执行规则的操作部分。11中南大学 智能系统与智能软件研究所v冲突消解冲突消解冲突消解的策略有很多种,经常使用的要素有:冲突消解的策略有很多种,经常使用的要
8、素有:v规则的重要程度;规则的重要程度;v规则条件部的详细程度;规则条件部的详细程度;v规则的使用时刻;规则的使用时刻;v规则的差别大小;规则的差别大小;v数据的生成时刻,一般以新生成的规则优先。数据的生成时刻,一般以新生成的规则优先。12中南大学 智能系统与智能软件研究所v例如,例如,在美式足球中,设有以下两条规则:在美式足球中,设有以下两条规则:R1 IF fourth dawn (R1 IF fourth dawn (第四次进攻第四次进攻) ) short yardage ( short yardage (前三次少于前三次少于1010码码) ) THEN punt ( THEN punt
9、 (踢悬空球踢悬空球) )R2 IF fourth dawnR2 IF fourth dawn short yardage short yardage within 30 yards(from the goal line) within 30 yards(from the goal line) THEN field goal ( THEN field goal (射门射门) )按条件的详细程度,选用规则按条件的详细程度,选用规则R2R2。13中南大学 智能系统与智能软件研究所冲突消解的冲突消解的LEX策略策略a)把已经执行过的一组规则从冲突集合把已经执行过的一组规则从冲突集合中清除;中清除;b
10、)选择具有更新数据的一组规则;选择具有更新数据的一组规则;c)选择规则条件更详细的一组规则;选择规则条件更详细的一组规则;d)选择任意一组规则。选择任意一组规则。按照编号顺序进行冲突消解,在规则变为按照编号顺序进行冲突消解,在规则变为一个的时刻,结束处理。一个的时刻,结束处理。14中南大学 智能系统与智能软件研究所前向推理过程前向推理过程 v设存在下列规则集合:设存在下列规则集合:R1: PR1: P1 1 P P2 2R2: PR2: P2 2 P P3 3R3: PR3: P3 3 P P4 4且作业领域中已存在事实且作业领域中已存在事实P1P1,则前向推理过程如则前向推理过程如下图所示。
11、下图所示。已知已知 规则规则1 P1 规则规则2 P2P3 规则规则3 推出推出 P415中南大学 智能系统与智能软件研究所举例:辨别动物园里的动物举例:辨别动物园里的动物 利用书上给出的事实数据及推理规利用书上给出的事实数据及推理规则进行前向推理。则进行前向推理。16中南大学 智能系统与智能软件研究所推理过程推理过程 1. 1.规则的匹配规则的匹配在在9 9条规则中,只有条规则中,只有R1R1的前件与事实的前件与事实D1D1完全完全匹配,所以选择匹配,所以选择R1R1进行推理,得到进行推理,得到身上有毛身上有毛规则规则R1它是哺乳动物它是哺乳动物事实事实D617中南大学 智能系统与智能软件研
12、究所推理过程推理过程 2.2.对对新新产生的事实数据产生的事实数据D6D6再进行规则匹配,再进行规则匹配, 并结合事实并结合事实D2D2,D3D3找到规则找到规则R6R6,推理后,推理后得得哺乳动物哺乳动物有尖锐的牙齿有尖锐的牙齿规则规则R6它是食肉动物它是食肉动物事实事实D7有锋利的爪子有锋利的爪子18中南大学 智能系统与智能软件研究所推理过程推理过程 3.3.根据新事实数据根据新事实数据D7D7,及作业领域原有的,及作业领域原有的D4D4、D5D5数据,找到匹配规则数据,找到匹配规则R9R9,推理得,推理得食肉动物食肉动物规则规则9它是猎豹它是猎豹结论结论身体是黄褐色身体是黄褐色有黑色斑点
13、有黑色斑点19中南大学 智能系统与智能软件研究所v后向推理后向推理:从表示目标的命题出发,使用一组产从表示目标的命题出发,使用一组产生式规则证明事实命题成立,即首先提出一批假设目生式规则证明事实命题成立,即首先提出一批假设目标,然后逐一验证这些假设标,然后逐一验证这些假设。 一般策略:首先假设一个可能的目标,然后由产生一般策略:首先假设一个可能的目标,然后由产生式系统试图证明此假设目标是否在作业领域中。若在式系统试图证明此假设目标是否在作业领域中。若在作业领域中,则该假设目标成立;否则,若该假设为作业领域中,则该假设目标成立;否则,若该假设为终叶(证据)节点,则询问用户。若不是,则再假定终叶(
14、证据)节点,则询问用户。若不是,则再假定另一个目标,即寻找结论部分包含该假设的那些规则,另一个目标,即寻找结论部分包含该假设的那些规则,把它们的前提作为新的假设,并力图证明其成立。这把它们的前提作为新的假设,并力图证明其成立。这样反复进行推理,直到所有目标均获证明或者所有路样反复进行推理,直到所有目标均获证明或者所有路径都得到测试为止。径都得到测试为止。 20中南大学 智能系统与智能软件研究所后向推理过程后向推理过程 v规则集合与前向推理的相同,首先假设结论规则集合与前向推理的相同,首先假设结论P P4 4成立,则由规则成立,则由规则3 3逆推,需要事实逆推,需要事实P P3 3存在;如存在;
15、如果果P P3 3在在作业领域中并不存在作业领域中并不存在,则,则需将其假设为需将其假设为结论,结论,依此类推,直到作业领域中再也,依此类推,直到作业领域中再也找不到匹配的规则为止。如果这时事实找不到匹配的规则为止。如果这时事实P P1 1存在存在于作业领域中,则于作业领域中,则P P4 4得得证,否则证,否则P P4 4不不成立。成立。事实事实 规则规则1 P1 规则规则2 假设假设 P2假设假设 P3 规则规则3 假设假设 P421中南大学 智能系统与智能软件研究所基于与基于与/或树的后向推理或树的后向推理v将目标作为与将目标作为与/或树的根,进行扩展:或树的根,进行扩展:对于同一个规则,
16、需同时满足的条件被设对于同一个规则,需同时满足的条件被设为为AND关系;关系;对于同一个结论或目标(包括推理过程中对于同一个结论或目标(包括推理过程中产生的),可用来满足其的规则设为产生的),可用来满足其的规则设为OR关关系。系。22中南大学 智能系统与智能软件研究所基于与基于与/或树的后向推理或树的后向推理v从与从与/或树的根(目标)出发,进行搜或树的根(目标)出发,进行搜索:索:1.匹配:寻找与各结论或目标相匹配的规匹配:寻找与各结论或目标相匹配的规则,并将其各条件设为与则,并将其各条件设为与AND关系;如关系;如果有多条规则,则将它们之间设为果有多条规则,则将它们之间设为OR关关系。系。
17、2.选择:选择其中一条规则进行扩展,如选择:选择其中一条规则进行扩展,如果一条都没有,那说明推理失败。果一条都没有,那说明推理失败。3.验证:被选中的规则的所有条件如果与验证:被选中的规则的所有条件如果与作业领域里的事实相匹配,则该规则的作业领域里的事实相匹配,则该规则的结论得到验证。以此逆推,直至根节点。结论得到验证。以此逆推,直至根节点。23中南大学 智能系统与智能软件研究所举例:假设在动物园里看到的举例:假设在动物园里看到的动物是猎豹,则根据规则库里动物是猎豹,则根据规则库里的现有的现有9条规则,可作出它的后条规则,可作出它的后向推理向推理AND/OR树。树。24中南大学 智能系统与智能
18、软件研究所它是猎豹它是猎豹食肉动物食肉动物身上有黑色斑点身上有黑色斑点身体是黄褐色身体是黄褐色R9SS25中南大学 智能系统与智能软件研究所它是猎豹它是猎豹食肉动物食肉动物身上有黑色斑点身上有黑色斑点身体是黄褐色身体是黄褐色R9哺乳动物哺乳动物吃肉吃肉R5NSSN26中南大学 智能系统与智能软件研究所它是猎豹它是猎豹食肉动物食肉动物身上有黑色斑点身上有黑色斑点身体是黄褐色身体是黄褐色R9哺乳动物哺乳动物吃肉吃肉R5SSN哺乳动物哺乳动物有尖锐的牙齿有尖锐的牙齿有锋利的爪子有锋利的爪子R6SS27中南大学 智能系统与智能软件研究所它是猎豹它是猎豹食肉动物食肉动物身上有黑色斑点身上有黑色斑点身体是
19、黄褐色身体是黄褐色R9哺乳动物哺乳动物吃肉吃肉R5SSN哺乳动物哺乳动物有尖锐的牙齿有尖锐的牙齿有锋利的爪子有锋利的爪子R6SS身上有毛身上有毛R1SSSS28中南大学 智能系统与智能软件研究所它是猎豹它是猎豹食肉动物食肉动物身上有黑色斑点身上有黑色斑点身体是黄褐色身体是黄褐色R9哺乳动物哺乳动物吃肉吃肉R5SSN哺乳动物哺乳动物有尖锐的牙齿有尖锐的牙齿有锋利的爪子有锋利的爪子R6SS身上有毛身上有毛R1SSSS29中南大学 智能系统与智能软件研究所v双向推理:双向推理:双向推理的推理策略是同时从双向推理的推理策略是同时从目标向事实推理和从事实向目标推理,并在目标向事实推理和从事实向目标推理,
20、并在推理过程中的某个步骤,实现事实与目标的推理过程中的某个步骤,实现事实与目标的匹配。匹配。事实事实 规则规则1 P1 规则规则2 P2 规则规则n-1 假设假设 PnPn-1 规则规则n-2 30中南大学 智能系统与智能软件研究所产生式表示法的特点1. 清晰性:清晰性: 产生式表示格式固定、形式简单,规产生式表示格式固定、形式简单,规则间相互较为独立,没有直接关系,则间相互较为独立,没有直接关系,使知识库的建立较为容易,处理较为使知识库的建立较为容易,处理较为简单。简单。31中南大学 智能系统与智能软件研究所产生式表示法的特点2.模块性:模块性: 规则库与推理机构是分离的,这种结规则库与推理机构是分离的,这种结构给知识库的修改带来方便,无须修构给知识库的修改带来方便,无须修改程序,对系统的推理路径也容易做改程序,对系统的推理路径也容易做出解释。出解释。32中南大学 智能系统与智能软件研究所产生式表示法的特点3.自然性:自然性: 产生式表示法用产生式表示法用“如果如果 ,则,则 ”的形式表示知识,符合人类的思的形式表示知识,符合人类的思维习惯,是人们常用的一种表达因果维习惯,是人们常用的一种表达因果关系的知识表示形式,既直观自然,关系的知识表示形式,既直观自然,又便于推理。又便于推理。33中南大学 智能系统与智能软件研究所