第四章-不确定推理方法精讲

第4章不确定性推理方法 演绎逻辑和一阶谓词逻辑中所运用到的推理是确定性推理 其操作就是进行符号推演 因为它们所依据的证据是确定的 要么为 真 要么为 假 其推理过程也是严密的 所以 所推出的结论也是正确的 要么成立 要么不成立 在现实世界中 确定性的推理问题是少见的 大多还是不确定性的 罗素说 所有传统逻辑习惯上总是假定当前使用的是精确的符号 正因为如此 传统逻辑难以应用于现实生活 而只是存在于虚幻的想象之中 第4章不确定性推理方法 例如 不明确的症状得出正确的医疗诊断给出相应的治疗方案 分析汽车故障问题 发动机不转并且灯不亮 电池或电线有故障通过朋友们的声音或姿势认出他们 理解成份不全的语句 第4章不确定性推理方法 在实际中 存在着很多的不确定性问题 导致了不确定性的知识及不确定性的证据 继而产生了不确定性的推理 不确定性推理是建立在非经典逻辑基础上的一种推理 即从不确定性的初始证据出发 通过运用不确定性的知识 最终推出具有一定程度的不确定性 但却是合理或者近乎合理结论的思维过程 包括概率推理 模糊推理和贝叶斯推理等 我们对于不确定性知识的处理主要是将其确定化 其表示的关键是如何对其不确定性进行量化 量化的目的就是把不确定性转化为确定性 第4章不确定性推理方法 归纳逻辑 inductivelogic 适合用于解决不确定性问题 著名的休谟问题 十八世纪英国哲学家大卫 休谟 从过去太阳每天从东方升起 能否推出明天太阳仍将从东方升起 内在含义是要讨论归纳推理的有效性问题 即我们能否理性证明从有限事例归纳出全称判断是合理的 因此 休谟问题也称为 归纳问题 休谟认为 归纳推理中个别的实际经验的前提 不能必然地推出普遍性的结论 在对休谟问题的辩论过程中 哲学家们提出了各种解决方法 一些学者将概率理论与归纳逻辑相结合 对归纳推理中的或然性进行量化处理 以可能性信度来衡量推理的有效性和合理性 现代归纳逻辑产生了 它是随着数学概率论趋于成熟 而逐渐发展起来 第4章不确定性推理方法 不确定性推理方法的分类 路线1 在推理一级上扩展确定性推理 把不确定的证据和知识与某种度量标准对应起来 并且不断更新结论不确定性的算法 从而构成相应不确定推理的模型 路线2 在控制策略一级上处理不确定性 通过识别领域中引起不确定性的特征和相应的控制策略来限制或减少不确定性对系统的影响 第4章不确定性推理方法 不确定性推理方法的分类 第4章不确定性推理方法 第4章不确定性推理方法 4 1不确定性推理中的基本问题4 2概率方法4 3主观Bayes方法4 4可信度方法4 5证据理论4 6模糊推理方法 4 1不确定性推理中的基本问题 推理 已知事实 证据 知识 某种策略 结论 不确定推理 不确定证据 不确定知识 某种策略 不确定结论 不确定程度 不确定性的表示与量度不确定性匹配算法及阈值的选择组合证据不确定性的算法不确定性的传递算法结论不确定性的合成 4 1不确定性推理中的基本问题 4 1不确定性推理中的基本问题 1 不确定性的表示与量度 1 知识不确定性的表示 知识的静态强度 2 证据不确定性的表示 证据的动态强度 3 不确定性的量度 在专家系统中知识的不确定性一般是由领域专家给出的 通常是一个数值 知识的静态强度 用户在求解问题时提供的初始证据 多来源于观察 在推理中用前面推出的结论作为当前推理的证据 能充分表达相应知识及证据不确定性的程度 度量范围的指定便于领域专家及用户对不确定性的估计 便于对不确定性的传递进行计算 而且对结论算出的不确定性量度不能超出量度规定的范围 度量的确定应当是直观的 同时应有相应的理论依据 例如专家系统MYCIN 用可信度表示知识的证据的不确定性 取值 1 1 4 1不确定性推理中的基本问题 2 不确定性匹配算法及阈值的选择不确定性匹配算法 用来计算匹配双方相似程度的算法 阈值 用来指出相似的 限度 4 1不确定性推理中的基本问题 最大最小方法 C E1andE2 min C E1 C E2 C E1orE2 max C E1 C E2 概率方法 C E1andE2 C E1 C E2 C E1orE2 C E1 C E2 C E1 C E2 有界方法 C E1andE2 max 0 C E1 C E2 1 C E1orE2 min 1 C E1 C E2 还有Hamacher方法 Einstein方法等 3 组合证据不确定性的算法 4 1不确定性推理中的基本问题 4 不确定性的传递算法 1 在每一步推理中 如何把证据及知识的不确定性传递给结论 2 在多步推理中 如何把初始证据的不确定性传递给最终结论 C H g C E f E H C H g C E1 C E2 C H g C E1 C E2 4 1不确定性推理中的基本问题 5 结论不确定性的合成 C H g C1 H C2 H 第4章不确定性推理方法 4 1不确定性推理的基本概念4 2概率方法4 3主观Bayes方法4 4可信度方法4 5证据理论4 6模糊推理方法 4 2概率方法 例 特定的目标身份融合问题 目标身份的可能种类的集合称为假设空间 可以抽象地表示为一个有限集合 该集合中的每个元素的先验概率P H 是已知的 有若干信息源 如传感器 分别能够从某一角度对所关注的目标进行观察 并给出目标身份为假设空间中每一类型的条件下得到这一观察结果的条件概率P E H 利用概率论中著名的贝叶斯法则 就能够得出融合所有信息源观察信息后的目标各种可能身份的后验概率P H E 4 2 1经典概率方法 产生式规则 E 前提条件 Hi 结论 在证据E出现的条件下 结论Hi成立的确定性程度 复合条件 在证据出现时结论的确定程度 IFETHENHi E EiANDE2AND ANDEm 缺点 用于简单的不确定推理 只考虑了证据的 真 假 情况 4 2 2逆概率方法 InverseProbability 1 逆概率方法的基本思想 Bayes公式 2 单个证据的情况产生式规则 有n个可能的结果 在给定的证据下 判定哪一个结果最有可能Bayes公式 结论Hi的先验概率 结论Hi成立时前提条件所对应的证据出现的条件概率 IFETHENHi 4 2 2逆概率方法 举例 想通过调查某地的地质迹象判定此地可能有铜 先知道发现每一种矿物质的概率和每一种矿物被发现时显现的某一迹象的概率 然后使用bayes公式 通过该具体地点的迹象 断定发现铜的可能性 优点 较强的理论背景和良好的数学特征 当证据及结论都彼此独立时计算的复杂度比较低 缺点 要求给出结论Hi的先验概率P Hi 及证据Ej的条件概率P Ej Hi 逆概率方法的优缺点 4 2 2逆概率方法 第4章不确定性推理方法 4 1不确定性推理的基本概念4 2概率方法4 3主观Bayes方法4 4可信度方法4 5证据理论4 6模糊推理方法 4 3主观Bayes方法 empiricalBayesianapproach 1976年 杜达 R O Duda 哈特 P E Hart 等人提出主观Bayes方法 建立了不确定性推理模型 并在地矿勘探专家系统PROSPECTOR中得到了成功的应用 主观Bayes方法 根据证据E的概率 利用知识强度 把结论H的先验概率P H 更新为后验概率P H E 先验概率 在获得与期望结果相关的任何信息之前已经被算出的概率 无条件概率 及证据Ej的条件概率P Ej Hi 此事件被加上一些新信息后的概率 后验概率P Hi Ej 也是条件概率给出新证据后的事件发生的概率 4 3 1知识不确定性的表示 知识 E 前提条件 简单条件或复合条件 H 结论 P H H的先验概率 LS LN 知识强度 似然比 一般由领域专家给出 规则成立的充分性度量 用于指出E对H的支持程度 IFETHEN LS LN H P H P E S 对于初始证据E 由用户根据观察S给出的概率 C E S 对所提供的证据可以相信的程度 称为可信度 对应关系 例如专家系统PROSPECTOR中 4 3 2证据不确定性的表示 多个单一证据的析取 则组合证据的概率 多个单一证据的合取 则组合证据的概率 非运算 4 3 2证据不确定性的表示 4 3 4不确定性的传递算法 P H 专家对结论H给出的先验概率 在没有考虑任何证据的情况下根据经验给出的 随着新证据的出现 对H的信任程度应有所改变 主观Bayes方法推理的任务 先验概率 后验概率 几率 odds 函数 概率 几率函数和概率函数有相同的单调性 4 3 4不确定性的传递算法 1 证据肯定存在的情况 即P E 1 4 3 4不确定性的传递算法 Bayes修正公式 换成几率公式 充分性量度LS的意义 1 LS 1 2 LS 1 3 LS 1 4 LS 0 如果E越是支持H为真时 LS的值应该越大 1 证据肯定存在的情况 4 3 4不确定性的传递算法 2 证据肯定不存在的情况 即P E 0 Bayes修正公式 4 3 4不确定性的传递算法 必要性量度LN的意义 1 LN 1 2 LN 1 3 LN 1 4 LN 0 如果E对H越重要时 LN的值应该越小 2 证据肯定不存在的情况 4 3 4不确定性的传递算法 不可能同时支持H或同时反对H 存在两种情况 1 LS 1且LN 1 2 LS 1且LN 1 不应该存在 1 LS LN 1 2 LS LN 1 4 3 4不确定性的传递算法 例1设有如下知识 4 3 4不确定性的传递算法 求 当证据存在及不存在时 及的值各是多少 4 3 4不确定性的传递算法 解 4 3 4不确定性的传递算法 解 续 4 3 4不确定性的传递算法 3 证据不确定的情况用户告知只有60 的把握说明证据E是真的 表示初始证据E为真的程度为0 6 即 0 6 这里S是对E的观察 在0 P E S 1的情况下 确定的后验概率P H S 要用杜达等人1976年证明了的公式 4 3 4不确定性的传递算法 1 4 3 4不确定性的传递算法 3 4 P E S 为其他值 用线性插值得E H或UED公式 4 3 4不确定性的传递算法 如图所示 Case 1 Case 2 Case 3 Case 4 C P公式 4 3 4不确定性的传递算法 可信度C E S 和P E S 的转换公式 用初始证据C E S 推理的过程 用C P公式求出P H S 当用到中间结论作为证据推理时用E H公式 4 3 5结论不确定性的合成算法 若n条知识都支持相同的结论 且每条知识的前提条件所对应的证据Ei i 1 2 n 都有相应的观察与之对应 则先对每条知识分别求出 然后求出 4 3 5主观Bayes方法的推理网络 所有的知识规则连成一个有向图 图中的节点代表假设结论 弧则代表规则 每条弧对应两个数值 LS LN 用来度量规则成立的充分性和必要性 这样的有向图称为推理网络 推理网络把一些证据和一些重要的假设结论连接起来 叶子节点是向用户提问获取的证据 其它节点就是结论假设 每个结论先附上一个先验概率P H 推理网络的连接就是测定一个结论的概率变化如何影响其它结论 4 3 5结论不确定性的合成算法 主观Bayes方法的主要优点 1 具有较坚实的理论基础 2 知识的静态强度LS及LN是由领域专家根据实践经验给出的 推出的结论有较准确的确定性 3 主观Bayes方法是一种比较实用且较灵活的不确定性推理方法 主观Bayes方法的主要缺点 1 要求领域专家在给出知识时 同时给出H的先验概率 2 Bayes定理中关于事件独立性的要求使主观Bayes方法的应用受到了限制 4 3 5结论不确定性的合成算法 求得先验概率的方法主要包括 1 根据大量试验样本分布得出的试验概率 2 利用等可能性事件概率相等的原则得出的古典概率 3 基于人的主观感觉得出的主观概率 当没有任何先验信息时 可以将各可能事件的先验概率设为相等的 不区分原则 等等 第4章不确定性推理方法 4 1不确定性推理的基本概念4 2概率方法4 3主观Bayes方法4 4可信度方法4 5证据理论4 6模糊推理方法 1975年肖特里菲 E H Shortliffe 等人在确定性理论 theoryofconfirmation 的基础上 结合概率论等提出的一种不确定性推理方法 优点 直观 简单 且效果好 4 4可信度方法 4 4 1可信度的概念 可信度 根据经验对一个事物或现象为真的相信程度 可信度带有较大的主观性和经验性 其准确性难以把握 C F模型 基于可信度表示的不确定性推理的基本方法 产生式规则表示 IFETHENH CF H E CF H E 可信度因子 certaintyfactor 反映前提条件与结论的联系强度 4 4 2C F模型 1 知识不确定性的表示 IF头痛AND流涕THEN感冒 0 7 CF H E 的取值范围 1 1 若由于相应证据的出现增加结论H为真的可信度 则CF H E 0 证据的出现越是支持H为真 就使CF H E 的值越大 反之 CF H E 0 证据的出现越是支持H为假 CF H E 的值就越小 若证据的出现与否与H无关 则CF H E 0 4 4 2C F模型 1 知识不确定性的表示 证据E的可信度取值范围 1 1 对于初始证据 若所有观察S能肯定它为真 则CF E 1 若肯定它为假 则CF E 1 若以某种程度为真 则0 CF E 1 若以某种程度为假 则 1 CF E 0 若未获得任何相关的观察 则CF E 0 CF E 0 6 E的可信度为0 6 2 证据不确定性的表示 4 4 2C F模型 2 证据不确定性的表示 静态强度CF H E 知识的强度 即当E所对应的证据为真时对H的影响程度 动态强度CF E 证据E当前的不确定性程度 4 4 2C F模型 组合证据 多个单一证据的合取则组合证据 多个单一证据的析取则 3 组合证据不确定性的算法 E E1ANDE2AND ANDEn E E1ORE2OR OREn 4 4 2C F模型 C F模型中的不确定性推理 从不确定的初始证据出发 通过运用相关的不确定性知识 最终推出结论并求出结论的可信度值 结论H的可信度由下式计算 4 不确定性的传递算法 4 4 2C F模型 即 该模型没有考虑当证据为假时对结论产生的影响 当证据为真时 结论的可信程度 设知识 5 结论不确定性的合成算法 1 分别对每一条知识求出CF H 4 4 2C F模型 2 求出E1与E2对H的综合影响所形成的可信度CF12 H 5 结论不确定性的合成算法 4 4 2C F模型 设知识 r1 IFE1THENH 0 8 r2 IFE2THENH 0 6 r3 IFE3AND E4ORE5 THENE1 0 7 已知CF E2 0 8 CF E3 0 5 CF E4 0 6 CF E5 0 7求CF H 例 4 4 2C F模型 欲求CF H 因为H由两条不同的知识推出 需要用到结论合成算法 分两步 1 先求CF1 H CF2 H 求CF1 H 时用到传递算法计算CF E1 因为CF E1 是中间结论 对应的是复合条件 所以CF E1 0 7 max 0 CF E3AND E4ORE5 0 7 min CF E3 max CF E4 CF E5 0 7 min 0 5 0 7 0 7 0 5 0 35 解 4 4 2C F模型 CF1 H CF H E1 max 0 CF E1 0 8 0 35 0 28 CF2 H 0 6 max 0 CF E2 0 48 4 4 2C F模型 2 根据合成算法计算CF1 2 H CF1 2 H CF1 H CF2 H CF1 H CF2 H 0 28 0 48 0 28 0 48 0 63 第4章不确定性推理方法 4 1不确定性推理的基本概念4 2概率方法4 3主观Bayes方法4 4可信度方法4 5证据理论4 6模糊推理方法 证据理论 theoryofevidence 又称D S理论 是德普斯特 A P Dempster 首先提出 沙佛 G Shafer 进一步发展起来的一种处理不确定性的理论 D S证据推理针对的是 分不清 或 不知道 这样的不确定性 1981年巴纳特 J A Barnett 把该理论引入专家系统中 同年卡威 J Garvey 等人用它实现了不确定性推理 对不同专家给出不同证据的合成目前 在证据理论的基础上已经发展了多种不确定性推理模型 4 5证据理论 4 5证据理论 4 5 1概率分配函数4 5 2信任函数4 5 3似然函数4 5 4信任函数与似然函数的关系4 5 5概率分配函数的正交和 证据的组合 4 5 1概率分配函数 设D是变量x所有可能取值的集合 且D中的元素是互斥的 在任一时刻x都取且只能取D中的某一个元素为值 则称D为x的样本空间 在证据理论中 D的任何一个子集A都对应于一个关于x的命题 称该命题为 x的值是在A中 设x 所看到的颜色 D 红 黄 蓝 则A 红 x是红色 A 红 蓝 x或者是红色 或者是蓝色 4 5 1概率分配函数 设D为样本空间 领域内的命题都用D的子集表示 则概率分配函数 basicprobabilityassignmentfunction 定义如下 定义4 1设函数M 对任何一个属于D的子集A 命它对应一个数M 0 1 且满足则M 上的基本概率分配函数 M A A的基本概率数 几点说明 1 设样本空间D中有n个元素 则D中子集的个数为个 D的所有子集 2 概率分配函数 把D的任意一个子集A都映射为 0 1 上的一个数M A 时 M A 对相应命题A的精确信任度 3 概率分配函数与概率不同 例如 设A 红 M A 0 3 命题 x是红色 的信任度是0 3 设D 红 黄 蓝 M 红 0 3 M 黄 0 M 蓝 0 1 M 红 黄 0 2 M 红 蓝 0 2 M 黄 蓝 0 1 M 红 黄 蓝 0 1 M 0但 M 红 M 黄 M 蓝 0 4 设D 红 黄 蓝 则其子集个数23 8 具体为 A 红 A 黄 A 蓝 A 红 黄 A 红 蓝 A 黄 蓝 A 红 黄 蓝 A 4 5 1概率分配函数 定义4 2命题的信任函数 belieffunction 且 对命题A为真的总的信任程度 由信任函数及概率分配函数的定义推出 设D 红 黄 蓝 M 红 0 3 M 黄 0 M 红 黄 0 2 4 5 1概率分配函数 似然函数 plansibilityfunction 不可驳斥函数或上限函数 定义4 3似然函数且对所有的 4 5 3似然函数 设D 红 黄 蓝 M 红 0 3 M 黄 0 M 红 黄 0 2 对A为真的信任程度 对A为非假的信任程度 对A信任程度的下限与上限 4 5 4信任函数与似然函数的关系 定义4 4设M1和M2是两个概率分配函数 则其正交和 其中 4 5 5概率分配函数的正交和 证据的组合 如果 则正交和M也是一个概率分配函数 如果 则不存在正交和M 即没有可能存在概率函数 称M1与M2矛盾 定义4 5设是n个概率分配函数 则其正交和为其中 4 5 5概率分配函数的正交和 4 5 5概率分配函数的正交和 设D 黑 白 且设 则 4 5 5概率分配函数的正交和 同理可得 组合后得到的概率分配函数 4 5 6基于证据理论的不确定性推理 基于证据理论的不确定性推理的步骤 1 建立问题的样本空间D 2 由经验给出 或者由随机性规则和事实的信度度量算基本概率分配函数 3 计算所关心的子集的信任函数值 似然函数值 4 由信任函数值 似然函数值得出结论 例5设有规则 1 如果流鼻涕则感冒但非过敏性鼻炎 0 9 或过敏性鼻炎但非感冒 0 1 2 如果眼发炎则感冒但非过敏性鼻炎 0 8 或过敏性鼻炎但非感冒 0 05 有事实 1 小王流鼻涕 0 9 2 小王发眼炎 0 4 问 小王患的什么病 4 5 6基于证据理论的不确定性推理 取样本空间 表示 感冒但非过敏性鼻炎 表示 过敏性鼻炎但非感冒 表示 同时得了两种病 取下面的基本概率分配函数 4 5 6基于证据理论的不确定性推理 将两个概率分配函数组合 似然函数 结论 小王可能是感冒了 信任函数 第4章不确定性推理方法 4 1不确定性推理的基本概念4 2概率方法4 3主观Bayes方法4 4可信度方法4 5证据理论4 6模糊推理方法 4 6模糊推理方法 4 6 1模糊逻辑的提出与发展4 6 2模糊集合4 6 3模糊集合的运算4 6 4模糊关系与模糊关系的合成4 6 5模糊推理4 6 6模糊决策 4 6 1模糊逻辑的提出与发展 1965年 美国L A Zadeh发表了 fuzzyset 的论文 首先提出了模糊理论 从1965年到20世纪80年代 在美国 欧洲 中国和日本 只有少数科学家研究模糊理论 1974年 英国Mamdani首次将模糊理论应用于热电厂的蒸汽机控制 1976年 Mamdani又将模糊理论应用于水泥旋转炉的控制 4 6 1模糊逻辑的提出与发展 4 6 1模糊逻辑的提出与发展 1983年日本FujiElectric公司实现了饮水处理装置的模糊控制 1987年日本Hitachi公司研制出地铁的模糊控制系统 1987年 1990年在日本申报的模糊产品专利就达319种 目前 各种模糊产品充满日本 西欧和美国市场 如模糊洗衣机 模糊吸尘器 模糊电冰箱和模糊摄像机等 模糊性 客观事物在性态与类属方面的不分明性例 某人个子高 某人个子较高 高 与 较高 没有明显的界限 随机性 有明确定义但不一定出现的事物中包含的不确定性 不以人的主观意识而变化 由事物本身的因果规律决定 模糊性 已经出现但难以给定精确定义的事物包含的不确定性 由事物的概念界限模糊和人的主观推理与判断产生 4 6 2模糊集合 论域 所讨论的全体对象 用U等表示 元素 论域中的每个对象 常用a b c x y z表示 集合 论域中具有某种相同属性的确定的 可以彼此区别的元素的全体 常用A B等表示 元素a和集合A的关系 a属于A或a不属于A 即只有两个真值 真 和 假 模糊逻辑给集合中每一个元素赋予一个介于0和1之间的实数 描述其属于一个集合的强度 该实数称为元素属于一个集合的隶属度 集合中所有元素的隶属度全体构成集合的隶属函数 4 6 2模糊集合 1 模糊集合的定义 例如 成年人 集合 1 模糊集合的定义 成年人 隶属度函数图 成年人 特征函数图 0 0 4 6 2模糊集合 当论域中元素数目有限时 模糊集合A的数学描述为 元素x属于模糊集A的隶属度 X是元素x的论域 2 模糊集合的表示方法 4 6 2模糊集合 2 模糊集合的表示方法 1 Zadeh表示法 1 论域是离散且元素数目有限 或 2 论域是连续的 或者元素数目无限 4 6 2模糊集合 2 模糊集合的表示方法 2 序偶表示法 3 向量表示法 4 6 2模糊集合 3 隶属函数常见的隶属函数有正态分布 三角分布 梯形分布等 隶属函数确定方法 1 模糊统计法 2 专家经验法 3 二元对比排序法 4 基本概念扩充法 4 6 2模糊集合 3 隶属函数 例如 以年龄作论域 取 扎德给出了 年老 O与 年青 Y两个模糊集合的隶属函数为 采用Zadeh表示法 4 6 2模糊集合 1 模糊集合的包含关系若 则 2 模糊集合的相等关系若 则 3 模糊集合的交并补运算 交运算 intersection 4 6 3模糊集合的运算 并运算 union 补运算 complement 或者 4 6 3模糊集合的运算 例6设论域 A及B是论域上的两个模糊集合 已知 4 6 3模糊集合的运算 解 4 模糊集合的代数运算 代数积 代数和 有界和 有界积 4 6 3模糊集合的运算 例6设论域 A及B是论域上的两个模糊集合 已知 4 6 3模糊集合的运算 解 4 6 4模糊关系与模糊关系的合成 1 模糊关系 身高与体重的模糊关系表 从X到Y的一个模糊关系R 用模糊矩阵表示 普通关系 两个集合中的元素之间是否有关联 模糊关系 两个模糊集合中的元素之间关联程度的多少 例7某地区人的身高论域X 140 150 160 170 180 单位 cm 体重论域Y 40 50 60 70 80 4 6 4模糊关系与模糊关系的合成 1 模糊关系 模糊关系的定义 A B 模糊集合 模糊关系用叉积 cartesianproduct 表示 叉积常用最小算子运算 A B 离散模糊集 其隶属函数分别为 则其叉积运算 例8已知输入的模糊集合A和输出的模糊集合B 求A到B的模糊关系R 解 1 模糊关系 4 6 4模糊关系与模糊关系的合成 1 模糊关系 4 6 4模糊关系与模糊关系的合成 2 模糊关系的合成 设Q U到V的模糊关系 R V到W的模糊关系 则Q与R的合成为U到W的一个模糊关系 其隶属函数 设则 4 6 4模糊关系与模糊关系的合成 2 模糊关系