第四章不确定推理教程以及答案.ppt

第四章不确定性推理 本章内容 不确定性推理中的基本问题 证据理论 概率方法 主观Bayes方法 4 1 6 3 可信度方法 5 不确定性推理方法分类 2 4 1不确定性推理中的基本问题 要实现对不确定性知识的处理 必须要解决不确定知识的表示问题 不确定信息的计算问题 以及不确定性表示和计算的语义解释问题 1 表示问题 1 知识不确定性的表示2 证据的不确定性表示 2 计算问题 1 不确定性的传递算法2 结论不确定性的合成3 组合证据的不确定性算法 3 语义问题 1 知识的不确定性度量2 证据的不确定性度量 4 2不确定性推理方法分类 1 模型方法特点 把不确定的证据和不确定的知识分别与某种度量标准对应起来 并且给出更新结论不确定性的算法 从而构成了相应的不确定性推理的模型 非数值方法是指出数值方法外的其他各种处理不确定性的方法 它采用集合来描述和处理不确定性 而且满足概率推理的性质 非数值方法 数值方法是对不确定性的一种定量表示和处理方法 数值方法 数值方法 分类 2 模糊推理 1 基于概率的方法 对于数值方法 按其依据的理论不同又可分为以下两类 4 2不确定性推理方法分类 4 2不确定性推理方法分类 纯概率方法虽然有严密的理论依据 但它通常要求给出事件的先验概率和条件概率 而这些数据又不易获得 因此其应用受到了限制 为了解决这这个问题 人们在概率理论的基础上发展起来了一些新的方法及理论 1 主观Bayes方法 2 可信度方法 3 证据理论 它是PROSPECTOR专家系统中使用的不确定推理模型 是对Bayes公式修正后形成的一种不确定推理方法 它是MYCIN专家系统中使用的不确定推理模型 它以确定性理论为基础 方法简单 易用 它通过定义信任函数 似然函数 把知道和不知道区别开来 4 2不确定性推理方法分类 2 控制方法特点 通过识别领域中引起不确定性的某些特征及相应的控制策略来限制或减少不确定性对系统产生的影响 这类方法没有处理不确定性的统一模型 其效果极大地依赖于控制策略 相关性制导回溯 机缘控制 启发式搜索 设有如下产生式规则 IFETHENH其中 E为前提条件 H为结论 具有随机性 根据概率论中条件概率的含义 我们可以用条件概率表示上述产生式规则的不确定性程度 即表示为在证据出现的条件下 结论H成立的确定性程度 对于复合条件E E1ANDE2AND ANDEn可以用条件概率作为在证据出现时结论的确定程度 4 3概率方法 4 3 1经典概率方法 4 3概率方法 4 3 2Bayes定理 设为一些事件 互不相交 P Bi 0 i 1 2 n 且则对于有 4 3 1 Bayes公式容易由条件概率的定义 乘法公式和全概率公式得到 在Bayes公式中 称为先验概率 而称为后验概率 也就是条件概率 4 3概率方法 4 3 3逆概率方法的基本思想 1 单个证据的情况 如果用产生式规则IFETHENHii 1 2 n其中前提条件E代替Bayes公式中B 用Hi代替公式中的Ai就可得到i 1 2 n 4 3 2 这就是说 当已知结论Hi的先验概率 并且已知结论Hi i 1 2 成立时前提条件E所对应的证据出现的条件概率P E Hi 就可以用上式求出相应证据出现时结论Hi的条件概率P Hi E 4 3概率方法 2 多个证据的情况 对于有多个证据和多个结论并且每个证据都以一定程度支持结论的情况 上面的式子可进一步扩充为 4 3 3 逆概率公式的优点是它有较强的理论背景和良好的数学特征 当证据及结论彼此独立时计算的复杂度比较低 其缺点是要求给出结论的先验概率及证据的条件概率 尽管有些时候比相对容易得到 但总的来说 要想得到这些数据仍然是一件相当困难的工作 另外 Bayes公式的应用条件是很严格的 它要求各事件互相独立等 如若证据间存在依赖关系 就不能直接使用这个方法 4 3概率方法 4 3 4逆概率方法的优缺点 4 4主观Bayes方法 4 4 1知识不确定性的表示 在主观Bayes方法中 知识是用产生式规则表示的 具体形式为IFETHEN LS LN H P H 其中 1 E是该知识的前提条件 它既可以是一个简单条件 也可以是复合条件 2 H是结论 P H 是H的先验概率 它指出在没有任何证据情况下的结论H为真的概率 即H的一般可能性 其值由领域专家根据以往的实践及经验给出 3 LS LN 为规则强度 其值由领域专家给出 LS LN相当于知识的静态强度 4 4主观Bayes方法 4 4 2证据不确定性的表示 若以O A 或P A 表示证据A的不确定性 则转换公式是 4 4主观Bayes方法 4 4 3不确定性的遗传算法 1 证据肯定存在的情况在证据E肯定存在时 把先验几率O H 更新为后验几率O H E 的计算公式为 4 4 1 如果将上式换成概率 就可得到 4 4 2 这是把先验概率P H 更新为后验概率P H E 的计算公式 4 4主观Bayes方法 2 证据肯定不存在的情况在证据E肯定不存在时 把先验几率O H 更新为后验几率O H E 的计算公式为 4 4 3 如果将上式换成概率 就可得到 4 4 4 这是把先验概率P H 更新为后验概率P H E 的计算公式 4 4主观Bayes方法 3 证据不确定的情况在证据不确定的情况下 不能再用上面的公式计算后验概率 而要用杜达等人1976年证明了的公式 4 4 5 来计算 下面分四种情况讨论这个公式 4 4 5 1 当P E S 1时 此时式 4 4 5 变成这就是证据肯定存在的情况 2 当P E S 0时 此时式 4 4 5 变成这就是证据肯定不存在的情况 4 4主观Bayes方法 3 当P E S P E 时 表示E与S无关 利用全概率公式将公式 4 4 5 变为 4 当P E S 为其它值时 通过分段线性插值就可得计算P H S 的公式该公式称为EH公式或UED公式 4 4主观Bayes方法 4 组合证据的情况 1 当组合证据是多个单一证据的合取时 即E E1andE2and andEn时 如果已知则P E S min 2 当组合证据E是多个单一证据的析取时 即E E1orE2or orEn时 如果已知则 P E S max 非 运算用下式计算 4 4主观Bayes方法 若有n条知识都支持相同的结论 而且每条知识的前提条件所对应的证据都有相应的观察与之对应 此时只要先对每条知识分别求出然后就可运用下述公式求出 4 4主观Bayes方法 4 4 4结论不确定性的合成算法 4 4主观Bayes方法 例2设有如下知识R1 IFATHEN 20 1 B1 0 03 R2 IFB1THEN 300 0 0001 B2 0 01 求 当证据A不存在时 P B2 A 的值是多少 解 1 由于A必发生 由R1得 2 由于B1不是必发生的 所以需作插值处理 设 4 4 5例子 4 4主观Bayes方法 当 时 有 所以在此区间插值 由于 主观Bayes方法的主要优点如下 1 主观Bayes方法中的计算公式大多是在概率论的基础上推导出来的 具有较坚实的理论基础 2 知识的静态强度LS及LN是由领域专家根据实验经验给出的 这就避免了大量的数据统计工作 另外 它既用LS指出了证据E对结论H的支持程度 又用LN指出了E对H的必要性程度 这就比较全面地反映了证据与结论间因果关系 符合现实世界中某些领域的实际情况 使推出的结论有较准确的确定性 4 4主观Bayes方法 4 4 6主观Bayes方法的主要优缺点 3 主观Bayes方法不仅给出了在证据肯定存在或肯定不存在情况下由H的先验概率更新为后验概率的方法 而且还给出了在证据不确定情况下更新先验概率为后验概率的方法 另外 由其推理过程可以看出 它确实实现了不确定性的逐级传递 因此 可以说主观Bayes方法是一种比较实用且较灵活的不确定性推理方法 它的主要缺点如下 1 要求领域专家在给出知识的同时给出H的先验概率P H 这是比较困难的 2 Bayes方法中关于事件间独立性的要求使主观Bayes方法的应用受到了限制 4 4主观Bayes方法 所谓可信度就是在实际生活中根据自己的经验对某一事物或现象进行观察 判断相信其为真得程度 例如 张三昨天没有上课 他的理由是肚子疼 就此理由而言 听话的人可能完全相信 也可能完全不相信 也可能在某种程度上相信 这与张三平时的表现和人们对他的话相信程度有关 这里的相信程度就是我们说的可信度 可信度也称为确定性因子 4 5可信度方法 4 5 1可信度的概念 在以产生式作为知识表示的专家系统MYCIN中 用以度量知识和证据的不确定性 显然 可信度具有较大的主观性和经验性 其准确性是难以把握的 但是 对于某一具体领域而言 由于该领域的专家具有丰富的专业知识和实践经验 要给出该领域知识的可信度还是完全有可能的 另外 人工智能所面临的问题 通常都较难用精确的数学模型进行描述 而且先验概率及条件概率的确定也比较困难 因此用可信度来表示知识及证据的不确定性仍然不失为一种可行的方法 4 5可信度方法 4 5可信度方法 4 5 2C F模型 C F模型是基于可信度表示的不确定性推理的基本方法 其他可信度方法都是在此基础上发展起来的 1 知识不确定性的表示 2 证据不确定性的表示 3 组合证据不确定性的算法 4 不确定性的传递算法 5 结论不确定性的合成算法 4 5可信度方法 4 5 3可信度方法应用举例 已知R1 IFA1THENB1CF B1 A1 0 8 R2 IFA2THENB1CF B1 A2 0 5 R3 IFB1 A3THENB2CF B2 B1 A3 0 8 初始证据为A1 A2 A3的可信度CF均设为1 即 CF A1 CF A2 CF A3 1 对B1 B2一无所知 求CF B1 和CF B2 例4 5 1 4 5可信度方法 解 由于对B1 B2一无所知 所以使用合成算法进行计算 由题意得到推理网络如下图所示 4 5可信度方法 1 对于知识 分别计算 2 利用合成算法计算的综合可信度 3 计算的可信度 这时 作为的证据 其可信度已由前面计算出来 CF 0 9 而的可信度为初始制定的1 由规则和公式 4 5 1 得到 所以 所求得的 的可信度更新值分别为 4 6证据理论 4 6 1基本概念 证据理论假设有一个不变的两两相斥的完备元素集合U 如下图所示 这里U为 例如 U 三轮车 汽车 火车 U 赤 橙 黄 绿 青 蓝 紫 U 马 牛 羊 鸡 狗 兔 图4 4证据理论说明图 4 6证据理论 4 6 2D S理论 证据理论是用集合表示命题的 设D是变量x所有可能取值的集合 且D中的元素是互斥的 在任一时刻x都取D中的某一个元素为值 则称D为x的样本空间 在证据理论中 D的任何一个子集A都对应于一个关于x的命题 称该命题为 x的值在A中 证据理论中 为了描述和处理不确定性 引入了概率分配函数 信任函数及似然函数等概念 设D为样本空间 领域内的命题都用D的子集表示 则概率分配函数 FunctionofProbabilityAssignment 定义如下 定义4 6 1设函数M 且满足则称M是上的概率分配函数 M A 称为A的基本概率函数 FunctionofBasicProbabilityAssignment 即对于样本空间D的任一子集都分配一个概率值 4 6证据理论 1 概率分配函数 定义4 6 2设函数Bel 且 则称为命题A的信任函数 FunctionofBelief 即命题A的信任函数值 就是A的所有子集的基本概率分配函数之和 用来表示对A的总信任 Bel函数又称为下限函数 以Bel A 表示对命题A为真的信任程度 4 6证据理论 2 信任函数 似然函数 PlausibleFunction 又称为不可驳斥函数或上限函数 下面给出它的定义 定义4 6 3似然函数 且 命题A的似然函数值就是所有与A相交的子集的基本概率分配函数之和 用来表示不否定A的信任度 4 6证据理论 3 似然函数 因为 所以即由于表示对A为真的信任程度 表示对A为非假的信任程度 因此可分别称和为对A信任程度的下限和上限 记作 4 6证据理论 4 信任函数与似然函数的关系 有时对同样的证据会得出两个不同的概率分配函数 例如 对于样本空间 从不同的来源可分别得到如下两个概率分配函数 此时需要对它们进行组合 德普斯特提出的组合方法可对这两个概率分配函数进行正交和运算 4 6证据理论 5 概率分配函数的正交和 4 6证据理论 设是两个概率分配函数 则其正交和为其中 如果 则正交和M也是一个概率分配函数 如果K 0 则不存在正交和M 称矛盾 定义4 6 4 4 6证据理论 定义4 6 5 对于多个概率分配函数 如果它们可以组合 则也可通过正交和运算将它们组合为一个概率分配函数 其定义如下 设是n个概率分配函数 则其正交和为其中 4 6证据理论 定义4 6 5 6 类概率函数 除了可以利用区间 Bel A 和 表示A的不确定性以外 还可以用A的类概率函数表示A的不确定性 定义4 6 6命题A的类概率函数为其中 分别是A及D中元素的个数 具有如下性质 4 6证据理论 4 6 3知识的不确定性的表示 在该模型中 不确定性知识用如下的产生式规则表示 IFETHENCF 其中 1 E为前提条件 它是样本空间D的子集 E既可以是简单条件 也可以是用AND或OR连接起来的复合条件 2 H是结论 它用样本空间中的子集表示 是该子集中的元素 3 CF是可信度因子 用集合形式表示 其中 用来指出的可信度 与一一对应 应满足如下条件 4 6证据理论 4 6 4证据的不确定性的表示 不确定性证据E的确定性用CER E 表示 对于初始证据 其确定性由用户给出 当用前面推理所得结论作为当前推理的证据时 其确定性由推理得到 CER E 的取值范围为 1 组合证据不确定性的算法当组合证据是多个证据的合取 即时 则E的确定性CER E 为当组合证据是多个证据的析取 即时 则E的确定性CER E 为 4 6证据理论 2 不确定性的传递算法1 如果只有一条知识支持结论H 即IFETHEN结论H的确定性通过下述步骤求出 对于上述知识 H的概率分配函数规定为这样便求得M H 4 6证据理论 2 如果有两条知识支持同一结论 即IFTHENIFTHEN结论H的确定性通过下述步骤求出 首先分别对每一条知识求出概率分配函数 然后再用公式对求正交和 从而得到H的概率分配函数M 4 6证据理论 3 如果有n条知识都支持同一结论H 则用公式对求其正交和 从而得到H的概率分配函数M 最后求出 4 6证据理论 4 按如下公式求出H的确定性CER H CER H MD H E f H 其中 MD H E 是知识的前提条件与相应证据E的匹配度