【人工智能_人工智能原理与应用】第四章不确定性推理

L/O/G/O 第四章 不确定性推理 本章内容 不确定性推理中的基本问题 证据理论 概率方法 主观 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、 控制方法 特点 :通过识别领域中引起不确定性的某些特征及 相应的控制策略来限制或减少不确定性对系统产生的 影响，这类方法没有处理不确定性的统一模型，其效 果极大地依赖于控制策略。 相关性制 导回溯 机缘控制 启发式 搜索 设有如下产生式规则： IF E THEN H 其中， E为前提条件， H为结论，具有随机性。 根据概率论中条件概率的含义，我们可以用条件概率 表示上述产生式规则的不确定性程度，即表示为在证据 出现的条件下，结论 H成立的确定性程度。 对于复合条件 E = E1 AND E2 AND AND En 可以用条件概率作为在证据出现时结论的确定程度。 4.3 概率方法 4.3.1 经典概率方法 4.3 概率方法 4.3.2 Bayes定理 设 为一些事件， 互不相 交， P(Bi)0， i=1,2, n，且 则对于 有， (4.3.1) Bayes公式容易由条件概率的定义、乘法公式和全概 率公式得到。在 Bayes公式中，称为先验概率，而称为后 验概率，也就是条件概率。 4.3 概率方法 4.3.3 逆概率方法的基本思想 1单个证据的情况 如果用产生式规则 IF E THEN Hi i 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方法中，知识是用产生式规则表示的，具体 形式为 IF E THEN (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 = E1 and E2 and and En 时，如果已知 则 P(E/S)=min （ 2）当组合证据 E是多个单一证据的析取时，即 E = E1 or E2 or or En 时，如果已知 则， P(E/S)=max “ 非 ” 运算用下式计算 4.4 主观 Bayes方法 若有 n条知识都支持相同的结论 ，而且每条知识的 前提条件所对应的证据 都有相应的观察 与之对应，此时只要先对每条知识分别求出 然后就可运用下述公式求出 4.4 主观 Bayes方法 4.4.4 结论不确定性的合成算法 4.4 主观 Bayes方法 例 2 设有如下知识 R1： IF A THEN (20， 1) B1(0.03) R2： IF B1 THEN (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.2 C-F模型 C-F模型是基于可信度表示的不确定性推理的基本方法， 其他可信度方法都是在此基础上发展起来的。 1知识不确定性的表示 2证据不确定性的表示 3组合证据不确定性的算法 4不确定性的传递算法 5结论不确定性的合成算法 4.5 可信度方法 4.5.3 可信度方法应用举例 已知 R1： IF A1 THEN B1 CF(B1,A1)=0.8； R2: IF A2 THEN B1 CF(B1,A2)=0.5； R3: IF B1 A3 THEN B2 CF(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一无所知，所以使用合成算法进行计算。 由题意得到推理网络如下图所示。 B2 B1 A3 A1 A2 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.2 D-S理论 证据理论是用集合表示命题的。设 D是变量 x所有可能 取值的集合，且 D中的元素是互斥的，在任一时刻 x都取 D中 的某一个元素为值，则称 D为 x的样本空间。在证据理论中， D的任何一个子集 A都对应于一个关于 x的命题，称该命题为 “ x的值在 A中 ” 。 证据理论中，为了描述和处理不确定性，引入了概率分 配函数、信任函数及似然函数等概念。 设 D为样本空间，领域内的命题都用 D的子集表示，则概 率分配函数（ Function of Probability Assignment）定义 如下。 定义 4.6.1 设函数 M： ,且满足 则称 M是 上的概率分配函数， M(A)称为 A的基本概率函 数（ Function of Basic Probability Assignment），即 对于样本空间 D的任一子集都分配一个概率值。 4.6 证据理论 1、概率分配函数 定义 4.6.2 设函数 Bel： ,且 （ ） 则称为命题 A的信任函数（ Function of Belief） ,即命题 A的信任函数值，就是 A的所有子集的基本概率分配函数之和 ，用来表示对 A的总信任。 Bel函数又称为下限函数，以 Bel （ A）表示对命题 A为真的信任程度。 4.6 证据理论 2. 信任函数 似然函数（ Plausible Function）又称为不可驳斥 函数或上限函数，下面给出它的定义。 定义 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 知识的不确定性的表示 在该模型中，不确定性知识用如下的产生式规则表示： IF E THEN CF = 其中， （ 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，即 IF E THEN 结论 H的确定性通过下述步骤求出。 对于上述知识， H的概率分配函数规定为 这样便求得 M(H)。 4.6 证据理论 2）如果有两条知识支持同一结论，即 IF THEN IF THEN 结论 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)是知识的