人工智能原理4new

1、Review1. 不确定性推理 基于概率的不确定性推理 基于可信度的不确定性推理 模糊推理2. 遗传算法 11 知识的不确定性 在各种实际应用领域中，严格精确的和确定的知识并不多见，大量的知识是不精确的和不确定的，需要采用不确定推理或称为不精确推理对不确定知识进行处理。可以说，不确定性(Uncertainty)是智能问题的本质特征，因此，智能系统的能力更主要反映在求解不确定性问题的能力上。2知识的不确定性 现实生活中的事物有时很难用精确的概念来描述，比如高、矮、胖、瘦等。对于不确定性知识要用不确定推理来处理，否则有可能得出一些荒谬的结论。 专家系统中的不确定性表现在三个方面，第一是证据或事实的

2、不确定性，第二是规则的不确定性，第三是推理的不确定性。3知识的不确定性1、证据的不确定性(1) 证据的歧义性：如“同意总理开会” “I saw a man with a telescope.”(2) 证据的不完全性 证据尚未收集完全 证据的特征值不完全(3) 证据的不精确性：如“大约是1.7米”(4) 证据的模糊性：如“年轻”(5) 证据的可信性(6) 证据的随机性4知识的不确定性2、规则的不确定性 产生式规则的不确定性主要有以下几个方面。(1) 构成规则前件的模式的不确定性 如：有一条产生式规则“如果患者发高烧且常流清鼻涕，则患者感冒”5知识的不确定性(2) 观察证据的不确定性 例如，患者发

3、高烧的体温观察值并不是恒定的。晚上可能是39，早上可能是38.5 。(3) 规则前件的证据组合的不确定性 例如，有一位患者的体温一直都是40 ，流清鼻涕，但并不是常流清鼻涕。6知识的不确定性(4) 规则本身的不确定性 每一条规则并不都具有100%的信任度，这就是规则的不确定性，或称为规则强度(5) 规则结论的不确定性 由于规则的前件包含有各种不确定性因素，运用不确定的规则，导出的结论也就不可避免地是不确定的。7知识的不确定性 此外，在规则使用过程中，还有两种典型的使用规则的不确定性。(1) 冲突消解策略包含有使用规则的不确定性(2) 选择假设进行反向推理验证的不确定性8知识的不确定性3、推理的

4、不确定性 由于证据的不确定性和规则的不确定性在推理过程中的动态积累和传播从而导致推理结论的不确定性。因此，需要采用某种不确定性的测度，并能在推理过程中来传递和计算这种不确定性的测度，最总得到结论的不确定性测度。 在不确定推理中，不确定性测度的计算有以下三种基本的计算模式。9知识的不确定性10知识的不确定性11知识的不确定性12知识的不确定性13一、不确定性推理及实现1.基本概念 (1)什么是不确定性推理 不确定性推理就是从不确定性的初始证据出发，通过运用不确定性的知识，最终推出具有一定程度的不确定性但却合理或者近乎合理的结论的思维过程。 2 不确定性推理14 (2) 不确定性推理中的基本问题

5、在不确定性推理中，知识和证据都具有某种程度的不确定性，这就为推理机的设计与实现增加了复杂性和难度。 它除了必须解决推理方向、推理方法、控制策略等基本问题外，一般还需要解决不确定性的表示和量度、不确定性匹配、不确定性的传递算法以及不确定性的合成等重要问题。 不确定性推理15(3)不确定性的传递算法 推理过程中不确定性的传递过程，包括如下两个密切相关的子问题： 在每一步推理中，如何把证据及知识的不确定性传递给结论； 在多步推理中，如何把初始证据的不确定性传递给最终结论。 不确定性推理16不确定性推理 对前一个问题，在不同的不确定推理方法中所采用的处理方法各不相同。 对第二个问题，各种推理方法所采用

6、的处理方法基本相同，即：把当前推出的结论及其不确定性程度作为证据放入数据库中，供以后推理使用。17 (4). 结论不确定性的合成 推理时有时会出现这样的情况：用不同的知识进行推理得到了相同的结论，但不确定性的程度却不同。此时，需要用合适的算法对它们进行合成。在不同的不确定推理方法中所采用的处理方法各不相同。不确定性推理18不确定性推理二、 常用的不确定性推理方法介绍(1) 基于概率的不确定推理 利用新的信息将先验概率P(H)更新为后验概率P(H|E)的一种计算方法.基于概率的不确定推理于1976 年提出，其首先在Prospector专家系统中使用，它以概率论中的全概率公式和Bayes公式为基础

7、。19基于概率的不确定推理20基于概率的不确定推理21基于概率的不确定推理22 (2) 可信度方法(Certainty Factor) 可信度方法是由E.H.Shortliffe等人在确定性理论的基础上，结合概率提出的一种不确定性推理方法，首先在Mycin系统中得到了成功的应用。 其核心思想是： 利用确定性因子CF（值） . 联系于具体的断言 . 联系于每条规则 . 通过CF的计算传播不确定性 不确定性推理23 (1) 可信度 根据经验对一个事物或现象为真的相信程度。 (2) C-F模型 C-F 模型是基于可信度表示的不确定性推理的基本方法。 可信度方法24 . 知识不确定性的表示 在C-F模

8、型中，知识是用产生式规则表示的，其一般形式是： if E then H (CF(H, E) 其中， E：是知识的前提条件，它既可以是一个单个条件，也可以是用 and 及 or 连接起来的复合条件； H：是结论，它可以是一个单一结论，也可以是多个结论。 可信度方法25 CF(H,E)：是该条知识的可信度，称为可信度因子或规则强度，静态强度。 CH(H,E) 在-1，1上取值，它指出当前提条件 E 所对应的证据为真时，它对结论为真的支持程度。 例如： if 头痛 and 流涕 then 感冒（0.7） 表示当病人确有“头痛”及“流涕”症状时，则有7成的把握认为 他患了感冒。 可信度方法26基于概率

9、的不确定推理 在基于概率的不确定性推理模型中，证据e的不确定性用e发生的概率P(e)表示，产生式规则“if e then h”的不确定性表示为在事件e(证据)已经发生的条件下、事件h (结论)发生的概率P(h|e),如果已知P(e), P(h), P(e|h)那么根据贝叶斯公式可得证据e支持结论h的不确定性测度为：27基于概率的不确定推理28基于概率的不确定推理29基于概率的不确定推理30基于概率的不确定推理31基于概率的不确定推理32基于概率的不确定推理33基于概率的不确定推理34基于概率的不确定推理35基于概率的不确定推理36基于概率的不确定推理37基于概率的不确定推理38基于概率的不确定

10、推理39基于概率的不确定推理40基于概率的不确定推理41基于概率的不确定推理42基于概率的不确定推理43基于概率的不确定推理44基于概率的不确定推理45基于概率的不确定推理46基于可信度的不确定推理 可信度方法是由E.H.Shortliffe等人在确定性理论的基础上，结合概率提出的一种不确定性推理方法，首先在Mycin系统中得到了成功的应用。 其核心思想是： 利用确定性因子CF 47 1. 知识不确定性的表示 在C-F模型中，知识是用产生式规则表示的，其一般形式是： if E then H (CF(H, E) 其中， E：是知识的前提条件，它既可以是一个单个条件，也可以是用 and 及 or

11、连接起来的复合条件； H：是结论，它可以是一个单一结论，也可以是多个结论。 48 CF(H,E)：是该条知识的可信度，称为可信度因子或规则强度，静态强度。 CH(H,E) 在-1，1上取值，它指出当前提条件 E 所对应的证据为真时，它对结论为真的支持程度。 例如： if 头痛 and 流涕 then 感冒（0.7） 表示当病人确有“头痛”及“流涕”症状时，则有7成的把握认为 他患了感冒。 49基于可信度的不确定推理2、信任度与不信任度50基于可信度的不确定推理51基于可信度的不确定推理52基于可信度的不确定推理3、可信度 在可信度不确定推理模型中，把信任度MB与不信任度MD组合成一个单一的不确

12、定性测度，这就是可信度53基于可信度的不确定推理54基于可信度的不确定推理55基于可信度的不确定推理4、三种基本不确定性测度的计算 (1)证据组合的不确定性测度 (2)并行规则的不确定性测度 (3)顺序规则的不确定性测度56基于可信度的不确定推理57基于可信度的不确定推理58基于可信度的不确定推理59基于可信度的不确定推理60基于可信度的不确定推理5、例子61基于可信度的不确定推理62基于可信度的不确定推理63 例：有下列一组知识： r1： if E1 then H ( 0.8 ) r2： if E2 then H ( 0.6 ) r3： if E3 then H ( - 0.5 ) r4：

13、if E4 and ( E5 or E6 ) then E1 ( 0.7 ) r5： if E7 and E8 then E3 ( 0.8 ) 已知： CF ( E2 ) = 0.8， CF ( E4 ) = 0.5，CF ( E5 ) = 0.6， CF ( E6 ) = 0.7， CF ( E7 ) = 0.6， CF ( E8 ) = 0.9， 求： CF ( H ) = ? 解：由已知知识得到推理网络： HE2E3E7E8E1E4E5E664由 r4 得到： CF( E1 ) = 0.7 max 0, CF E4 and (E5 or E6 ) = 0.7 max 0, min CF(

14、E4) ,CF (E5 or E6 ) = 0.7 max 0, min CF(E4) , max CF ( E5 ) , CF( E6 ) = 0.7 max 0, min 0.5 , max 0.6 , 0.7 = 0.7 0.5 = 0.35 由 r5 得到： CF( E3 ) = 0.9 max 0, CF ( E7 and E8 ) = 0.9 0.6 = 0.54 由 r1 得到： CF1( H ) = 0.8 max 0, CF ( E1 ) = 0.8 0.35 = 0.28 65 由 r2 得到： CF2( H ) = 0.6 max 0, CF ( E2 ) = 0.6 0

15、.8 = 0.48 由 r3 得到： CF3( H ) = - 0.5 max 0, CF ( E3 ) = - 0.5 0.54 = - 0.27 结论不确定性的合成 CF1，2( H ) = CF1 ( H ) + CF2 ( H ) CF1 ( H ) CF2 ( H ) = 0.28 + 0.48 0.28 0.48 = 0.63 CF1,2,3 ( H ) = = 0.49 即：CF( H ) = 0.49 CF1,2 ( H ) + CF3( H )1 min | CF1,2 ( H ) | , | CF3( H ) |66例：某企业选择人员规则(要求1）： r1: IF (有工作

16、经验 or 本科以上学历 ) and 有相关知识背景 then 录用（0.9) r2:IF 工作两年以上 and 作过相关工作 then 有工作经验 （0.8) r3:IF k1 and k2 and k3 and k4 then 有相关知识背景(0.9) k1,k2,k3: 相关课程的成绩/100应用举例67规则关系图录用经验本科背景两年相关k2k3k4k1r1r3r268设有一本科毕业生，其相关课程的成绩为k1=60,k2=80,k3=40,k4=90推理过程：R3,R1CF(知识背景)=0.9*min0.6,0.8,0.4,0.9=0.36CF(录用）0.9*min0.36,1=0.32

17、录用的可能性为3269基于可信度的不确定推理二、带有阈限的不确定推理70基于可信度的不确定推理71基于可信度的不确定推理72基于可信度的不确定推理结论h的可信度CF(h)： 1）求极大值法 2) 加权求和法 3) 有限和法73基于可信度的不确定推理74练习：设有如下一组知识:R1: IF E1 THEN H(0.8,0.5)R2: IF E2 THEN H(0.6,0.7)R3: IF E3 THEN H(-0.5, 0.6)R4: IF E4 AND (E5 OR E6) THEN E1(0.7,0.5)R5: IF E7 AND E8 THEN E3(0.9,0.6)已知: CF(E2)=

18、0.8,CF(E4)=0.5,CF(E5)=0.6 CF(E6)=0.7, CF(E7)=0.6, CF(E8)=0.9求: CF(H)75例：某企业选择人员规则： r1: IF (有工作经验 or 本科以上学历 ) and 有相关知识背景 then 录用（0.9, 0.6) r2:IF 工作两年以上 and 作过相关工作 then 有工作经验 （0.8，0.5) r3:IF k1 and k2 and k3 and k4 then 有相关知识背景(0.9,0.7) 注：k1,k2,k3,k4: 相关课程的成绩/100, 0.7 成绩最低要到达70分应用举例76设有一本科毕业生，其相关课程的成

19、绩为k1=60,k2=80,k3=40, k4=90推理过程：R3,R1CF(k3)时，规则才启用。0 CF(H)=CF(H,E)CF(E) 启动多条规则的处理（冲突消解）IF E11(w11) and E12(w12) and.and E1m(w1m) THEN H1(CF(H,E1), 2)IF E21(w21) and E22(w22) and.and E2m(w2m) THEN H2(CF(H,E2), 2) IF En1(wn1) and En2(wn2) and.and Enm(w2m) THEN Hn(CF(H,En), n)如果n条规则都满足CF(Ei)= i i=1,2,n

20、(1)选择组合证据CF(Ei)可信度最大的一条规则执行。 (2)前面的合成方法 85例：某企业选择人员规则： r1: IF (有工作经验 or 本科以上学历 )(0.6) and 有相关知识背景(0.4) then 录用（0.9, 0.6) r2:IF 工作两年以上(0.4) and 作过相关工作(0.6) then 有工作经验 （0.8，0.5) r3:IF k1(0.2) and k2(0.2) and k3(0.2) and k4(0.4) then 有相关知识背景(0.9,0.7) 注：k1,k2,k3: 相关课程的成绩/100应用举例86设有一本科毕业生A，其相关课程的成绩为k1=6

21、0,k2=80,k3=40,k4=90推理过程：CF(E3)= (0.6*0.2+0.8*0.2+0.4*0.2+0.9*0.4)=0.720.7R3: CF(知识背景)=0.9*0.72=0.648R1: CF(E1)=0.6*1+0.4*0.648=0.860.6CF(录用）0.9*0.86=0.77录用的可能性为7787设有一本科毕业生B，其相关课程的成绩为k1=60,k2=60,k3=40, k4=90推理过程：R3CF(E3)= (0.6*0.2+0.6*0.2+0.4*0.2+0.9*0.4)=0.680.7,R3不启动推理失败，未录用。88模糊推理 Zadeh在1965年提出了模

22、糊集合论，1978年又提出了可能性理论。 模糊命题：含有模糊概念、模糊数据或带有确信程度的语句称为模糊命题。 形式化为：x is A或者x is A (CF) 其中，X是论域上的变量，用来代表所论对象的属性；A是模糊概念或模糊数；CF是该模糊命题的确信度，它可以是一个确定的数，也可以是模糊数，还可以是模糊语言值。89模糊推理 模糊知识的表示：模糊产生式规则的一般形式为 其中E是用模糊命题表示的模糊条件，它既可以是由单个模糊命题表示的简单条件，也可以是由多哥模糊命题构成的组合条件；H是用模糊命题表示的模糊结论；CF是该产生式规则所表示的知识可信度因子，它既可以是一个确定的数，也可以是一个模糊数或

23、模糊语言值； 是规则的阈值，用于指出规则可被使用的限制。 90模糊推理(3) 模糊匹配 由于模糊规则的模糊条件是模糊命题，与之匹配的证据也是模糊命题，因此需要采用模糊匹配的方法来计算两个模糊命题的相似程度，即匹配度。 a.贴近度 b.语义距离913 遗传算法一、简介遗传算法的概念和思想是由美国的Holland教授提出的。它的主要特点是模拟自然界生物体从低级到高级的进化过程,由初始种群出发,采用优胜劣汰,适者生存的自然法则选择个体,通过交配，变异来产生下一代种群,如此逐代进化,直到满足期望的条件。923 遗传算法二、优点遗传算法利用简单的编码技术和交叉繁殖机制来表达复杂现象,不必描述问题的全部特

24、征,从而解决那些结构尚无人理解的复杂问题.由于它不受搜索空间的限制性假设的约束,不必要求连续性,导数存在和单峰等假设,能从离散的,多极值的,含有噪音的高维问题中以很大概率找到全局最优解.933 遗传算法三、遗传学术语遗传算法是遗传学和计算机科学相互结合渗透而成的一门交叉学科，它使用了遗传学的一些概念和基本术语来描述它的计算方法，因此，了解这些术语对于学习和应用遗传算法是十分必要的。943 遗传算法生物遗传物质的主要载体是染色体，最主要的遗传物质是DNA。染色体由基因组成，染色体中基因的位置称为基因座，基因所取的值称为等位基因。基因和基因座决定了染色体的特征，也决定了生物个体的性状。953 遗传

25、算法染色体有两种表示模式，即基因型表示模式和表现型表示模式。基因型是指与生物个体表现出来的性状密切相 关的基因组成。表现型是指生物个体所表现出来的性状。同一种基因型的生物个体在不同的环境条件下表现出来的性状会有差异，因此，表现型是基因型与环境条件相互作用的结果。963 遗传算法四、遗传算法的概念与计算方法 遗传算法中，与染色体相对应的是数据或数组。在标准的遗传算法中，染色体可用一维的 串结构数据来表示，串的各个位置对应染色体的基因座，各位置上所取的值对应等位基因。遗传算法对染色体进行处理，或者称为对基因型个体(Individual)进行处理。一定数量的个体组成 群体(Population)，群

26、体中的个体数称为群体 大小(Population Size)或群体规模。各个个体对环境的适应程度称为适应度(Fitness)。973 遗传算法 执行遗传算法时有两个必需的数据转换操作。编码操作：把染色体数据从表现型表示转换成基因型表示。译码操作：它是同编码操作相反的数据转换操作，译码操作把染色体数据从基因型表示转换成表现型表示。983 遗传算法遗传算法的基本流程如下图所示。他以群体中的所有个体为对象。选择(Selection)、杂交(Crossbreed)、变异(mutation)是三个主要的遗传算子。对当前群体的所有个体的适应度计算编码和初始群体生成选 择杂 交变 异993 遗传算法应用遗传

27、算法求解问题，需要根据求解的具体问题进行下述5个方面的工作：1) 参数编码的格式及参数编码。2) 初始群体的设定3) 适应度函数的设计4) 遗传操作的设计5) 控制参数设计，主要是指群体规模和遗传操作中所需要使用的有关控制参数的设定和设计1003 遗传算法五、例子 应用遗传算法求f(x) = x2的最大值的解， x0, 31。1013 遗传算法(1) 编码 此问题给出的数据031是表现型表示模式，需要通过编码把它们转换成遗传空间的基因型表示。基因型表示模式通常是串结构形式，十进制数可以很方便地转换成二进制数串，因此，我们把031编码为5位长的二进制无符号整数表示形式。例如，x=8的基因型表示为

28、01000，x=13的基因型表示为01101。1023 遗传算法(2) 初始群体的生成 遗传算法是对一个群体中的所有个体为对象进行遗传操作的，为了简化该例子的说明，假定群体规模n=4，即群体由4个个体组成。初始群体的每个个体都是从遗传空间中随机选择的，假设随机选择的4个个体分别是x1=13=01101, x2=24=11100, x3=8=01000, x4=19=10011。初始群体也称为进化的初始代或第一代(first generation)群体。1033 遗传算法(3) 适应度函数设计和适应度计算 遗传算法在搜索求解过程中一般不需要其他外部信息，仅用设计的适应度函数来评估个体的优劣，作为

29、对个体进行遗传操作的依据。某个个体xi的适应度函数值fi称为这个个体xi的适应度，按适应度的大小来评估个体的优劣，适应度越大的个体越优良，优胜劣汰，遗传进化的结果将得到f(x)值最大的解x。 f(x) = x21043 遗传算法(4) 选择操作 选择操作是从当前群体中选出优良的个体，使它们有机会作为父代来繁殖下一代。判断个体优良的依据就是个体的适应度，个体的适应度越高，该个体被选择的机会就越多。 选择操作的实现方法很多，最简单的方法就是直接按适应度fi选择个体，也可以把选择操作算子设计成适应度fi的某种函数s(fi)，由该函数值来选择个体。1053 遗传算法1061073 遗传算法杂交操作可分

30、为下述两个步骤来实现：1、随机配对：对配对池中的任意两个个体随机进行配对。2、杂交繁殖：对任何一对配对个体随机指定一个交叉位置k，1=k=m，两个个体从基因座1至基因座k上的基因值对应彼此交换，从而产生两个新的后代个体。基因座的编号是从串的最低位1到最高位m。1083 遗传算法(5) 杂交操作 杂交操作是对配对池的当前群体中的基因型个体随机配对，然后使配成一对的个体彼此交换部分信息，从而得到这一对个体的两个后代个体。1093 遗传算法1101113 遗传算法(6) 变异操作 变异操作是指把一个个体的基因座的基因值进行改变，从而得到一个新的个体。1123 遗传算法 该例通过5次迭代处理，由初始群

31、体繁殖生成第六代群体，迭代处理过程如表7.1所示。1133 遗传算法1143 遗传算法六、遗传算法的应用 预测预报是人们对客观事物发展变化的一种认识与估计。对某个对象系统选择哪一种方法来建立预测预报模型，关键在于用此方法建立的预测模型的计算值与实际值的拟合程度。我们用一个实际例子来说明遗传算法在建立预测预报模型中的应用。1153 遗传算法1163 遗传算法 应用遗传算法建立预测模型可以分为两个步骤：(1) 建模分析(2) 采用遗传算法求解模型的待定参数1173 遗传算法 由表7.2给出的1978年1999年的货物年吞吐量，可作出实际年吞吐量曲线。由此曲线可见，港口年吞吐量的总趋势在增长，但有准周期性的振荡。1183 遗传算法(1) Logistic生长曲线如下图所示，可用于反映一般处于成长发展时期中的对象系统随时间的生长情况。所以采用Logistic曲线描述港口年