人工智能原理不精确推理

人工智能原理 第 7章 不精确推理 本章内容 7.1 不精确推理的必要性 7.2 贝叶斯概率推理 7.3 贝叶斯网络 7.4 可信度方法 * 7.5 模糊推理 参考书目 第 7章 不精确推理 7.1 不精确推理的必要性 不精确推理的原因 / 方法 第 7章 不精确推理 4 为什么要不精确推理 做不精确推理的原因有多种： 推理所需的信息不完备： 竞争双方不知道对 方信息 背景知识不足： 疑难病症的机理 多种原因导致同一结果： 疾病的诊断 信息描述模糊： 目击者对嫌疑犯的描述 信息中含有噪声： 做假帐，虚假统计报表， 采集数据当中的噪声（雷达、声纳 /化验）等 第 7章 不精确推理 5 不精确推理的原因 规则是模糊的： 定性描述，如“如果刑事犯 罪猖獗，就应加大打击力度”等 推理能力不足： 天气预报的计算 解决方案不唯一： 多个方案如何选优的问题 两种不确定性 环境的不确定性 智能体几乎从来无法 了解关于其环境的全部事实 反映环境的知识的不确定性 过于复杂 而无组织 知识粥 (knowledge soup) 第 7章 不精确推理 6 不确定环境下的智能体行动 从智能体角度看，他不得不在不确定 的环境下行动 克服这种不确定性的解决方案 1)条件规划 2)使用简单而不完全正确的模型 大部分时间模型或者规划可行，但有时 会出现矛盾 理性决策 依赖于各种目标的相对重要 性，也依赖于这些目标被实现的可能性 第 7章 不精确推理 7 不确定性下的决策 不确定性的存在改变了智能体进行决 策的方式 智能体要在各种规划的不同可能结果之 间进行选择 (有所偏好 ) 一种结果是一个被完全确定的状态 任 何状态对于智能体来说都具有一定程度 的有用性即效用，智能体将偏好具有更 高效用的状态 决策理论 =概率理论 +效用理论 理性智能体选择能产生最高效用的行动 第 7章 不精确推理 8 不精确推理 现实不确定性需要不精确推理，将数 值计算引入推理过程 继续使用逻辑联结词 真假值概率化，以表示某种可靠程度 在推理的前提和结论之间建立概率公式 （解释） 前提称为证据，结论称为假设 应用：专家系统中的推理网络 (PROSPECTOR系统 / MYCIN系统 ) 第 7章 不精确推理 9 贝叶斯网络 (Bayesian network) 智能体使用概率对行动结果 (用事件之间 的联系表示 )进行预测，进而选择期望效 用最高的行动 贝叶斯网络 (也叫贝叶斯信念网 )是一个节 点标注了定量概率信息的有向图，反映 了一个事件对于另一个事件的影响程度 / 表示了变量之间的依赖关系和概率信息 贝叶斯网络是事件之间联系的全面而形 象的表示 第 7章 不精确推理 10 知识粥 (Knowledge Soup) 现实世界的复杂性和不确定性反映在 智能体内部 异质的、不固定的、经 常不一致的知识 称为知识粥 “粥体 ”包含小块 (small chunk)对应于规 则、框架等，大块 (large chunk)对应于 整个理论 这些“块”的内部是一致的，“块”之 间可以是不一致的 从整体来说，知识往往具有这样的特 性 模糊、不确定、随机、无知 第 7章 不精确推理 7.2 Bayes概率推理 7.2.1 有关概念和公式 7.2.2 几率和似然比 7.2.3 似然比应用 第 7章 不精确推理 12 主观 Bayes主义 主观 Bayes主义： 将概率推理与归纳逻辑的解释联系起来 ， 现 实世界的一些因果关系可以形成一种信念 ， 它并非在所有场合下都正确 ， 可称为部分信 念 / 表示这种信念的最好方法是概率方法 ， 对概率的解释有若干种 ， 其中 Bayes创立了 主观解释 ， 也称为主观 Bayes主义 其要点是：概率是个人的一种合理置信度 ， 每个人的估计 (概率 )虽然各不相同 ， 但应该 满足概率的基本规律和其他某些客观规律 ， 因而是合理的 第 7章 不精确推理 13 7.2.1 有关概念和公式 在 Bayes概率推理中 ， 推理规则表示为 if E(前提 /证据 ) then H(结论 /假设 )(LS, LN) 规则强度用 LS/LN表示 (也称为似然比 ) / 其不精确推理过程是：根据证据 E的概率 P(E)， 利用规则的 LS和 LN， 把结论的先 验概率 P(H)更新为后验概率 P(H|E)， 因而 也称为概率传播 第 7章 不精确推理 14 Bayes条件概率 Bayes条件概率：令假设 H的先验概率为 P(H)， P(H)是指定的 / 证据 E为真时 H的 条件概率为 P(H|E)， P(H|E)的一部分是指 定的，一部分是根据 P(H)和指定的 P(H|E) 计算出来的，这部分计算出的概率称为 后验概率 条件概率 P(H|E)可看作以一定概率成立的 EH 的推理规则 第 7章 不精确推理 15 概率公理 Bayes概率服从如下公理 (Kolmogorov公理 )： (1)0P(H)1 (2)P(H=T)=1 / P(H=F)=0 (3)P(H G)=P(H)+P(G)P(H G) / 当 H和 G互斥 有 P(H G)=P(H)+P(G) 特别有 P(H)+P( H)=1 / 一般地有 P(Hi|E)=1即证 据 E下 Hi的全体构成了一切可能的假设，其中任 意 Hi和 Hj (ij)互斥 这样的概率公理是不能违反的 (p364论证 ) 第 7章 不精确推理 16 条件概率公式 条件概率公式 P(H&G)=P(H|G)P(G)=P(G|H)P(H) 该公式指明了 H和 G两个假设之间存在着 相关性 如果 H和 G相互独立 ， 则 P(H|G)=P(H) P(G|H)=P(G) P(H&G)=P(H)P(G) 第 7章 不精确推理 17 全概率公式 全概率公式：一个假设的先验概率可以 表示为两个假设的概率 ， 其中后面一个 假设遍历各种可能性且各个可能性之间 是独立的 ， 则有 P(H)=iP(H&Gi)=iP(H|Gi)P(Gi) 其解释为：假设 H的概率等于从各种证据 提供的信息所推出的条件概率之和 / 证 据满足独立性和完全性 这个公式也称为全联合分布 第 7章 不精确推理 18 边缘化 上述全概率公式从另一个角度可以视为 通用化边缘规则： P(Y)=zP(Y,z)=zP(Y|z)P(z) 将随机变量的某个变量的分布抽取出来 ， 求和从而得到该变量的无条件概率 (或称 为边缘概率 ) / 其过程称为边缘化或求和 消元 (summing out) 用于从多个变量的全概率分布中求取某 个变量的概率 ， 进行推理 第 7章 不精确推理 19 归一化 在一定条件下某个随机变量的绝对概率 值可以根据概率公理来归一化 一种结 果作为分子 ， 同条件各种结果之和作为 分母 通常 ， 同条件下结果只有 2个 a/ a， 故有 p(a|*)+p( a|*)=1 (*为某种条件 ) 引入归一化常数 =1/p(a)+p( a) 第 7章 不精确推理 20 逆概率公式 逆概率公式 从条件概率公式可得 如果有多个假设 H1Hn， 则上式化为 )( )()|()|( GP HPHGPGHP 第 7章 不精确推理 n j jj ii i HPHGP HPHGP GHP 1 )()|( )()|( )|( 21 逆概率公式的例子 逆概率公式不仅是条件概率公式的一个简 单变形 ， 实际上很有用处 如果某个条件 概率不便计算 ， 则可以先计算其逆概率 ， 而后算出所要的条件概率 例子： 求 P(肺炎 |咳嗽 )可能比较困难，但统 计 P(咳嗽 |肺炎 )可能比较容易 (因为要上医院 ) / 假设 P(肺炎 )=1/10000，而 P(咳嗽 )=1/10， 90%的肺炎患者都咳嗽，则 P(肺炎 |咳嗽 )= 第 7章 不精确推理 0 0 0 9.01.0 0 0 0 1.09.0)( )()|( 咳嗽 肺炎肺炎咳嗽 P PP 22 修正因子 (1) 可以将前面的逆概率公式写成 这说明先验概率 P(H)可以通过方括号部分 (作为修正因子 )修正为后验概率 P(H|E) (证 据 E为真时 H的后验概率 ) 在上面的例子中 ， 医生认为一个人得肺炎 的可能性为万分之一 ， 一旦发现患者咳嗽 ， 就将调整为万分之九 第 7章 不精确推理 )()( )|()|( HPEP HEPEHP 23 修正因子 (2) 将 E看作证据 ， 先验概率 P(E)越小 ， 且 H为 真时 E的条件概率 P(E|H)越大 ， 则修正因 子所起作用越大 在上例中 ， 如果 P(咳嗽 )=0.0001 / P(咳嗽 |肺炎 )=0.9999 / P(肺炎 )不变 则 P(肺炎 |咳嗽 )=0.9999， 远远超过原来的万 分之九 第 7章 不精确推理 24 后验概率递推公式 当有 n个互相独立的证据 ， 则有公式 上式 可以写成递推公式形式： 上式说明：随着新证据的不断获得 ， 从证据少 时的后验概率推出证据多时的后验概率 ， 且每 一步都是把上一步的后验概率视为新证据到来 时的先验概率 )( )( )|( )&|( 1 1 1 HP EP HEP EEHP n i i n i i n 第 7章 不精确推理 )&|()( )|()&|( 1 1 111 m m mm EEHP EP HEPEEHP 25 6.2.2 几率和似然比 引入相对量度 定义 几率： 称为 H的几率或先验几率，取值范围 0,) 由此反过来有 定义 条件几率： )(1 )( )( )()( HP HP HP HPHO 第 7章 不精确推理 )(1 )()( HO HOHP )|( )|()|( EHP EHPEHO 26 后验几率和先验几率的关系 例子 ： O(晴天 |冬天早晨有雾 )=4.2， 如果冬天 早晨有雾 ， 则该天为晴天的可能性是非晴天可 能性的 4.2倍 由几率定义 、 条件几率定义和条件概率公式可 以推得后验几率和先验几率的关系： 第 7章 不精确推理 )()|( )|()|( HOHEP HEPEHO 27 似然比 定义 似然比： LS=P(E|H)/P(E| H) LN=P( E|H)/P( E| H) 则可得下述关系： O(H|E)=LS*O(H) O(H| E)=LN*O(H) 有多个证据独立时 ， 其公式是 第 7章 不精确推理 n i in HOHELSEEHO 1 1 )()|()&|( 28 似然比约束 对 LS和 LN的约束 对于 LS和 LN有如下约束要求：二者都是非负 的 ， 并且满足 第 7章 不精确推理 1&1 1&1 1&1 LNLS LNLS LNLS 29 6.2.3 似然比应用 似然比 (规则强度 )LS和 LN的应用 当 P(E)=1时，利用 LS将先验几率 O(H)更 新为后验几率 O(H|E) / 当 P( E)=1时，利 用 LN来更新几率 在专家系统 PROSPECTOR(一个用于探矿 的 ES)中同时应用了 LS和 LN，分别表示 正面证据和反面证据的支持，称为充分 因子和必要因子，并将 LS、 LN附着在每 条规则之上 第 7章 不精确推理 30 LS和 LN的作用 当 LS很大 ， 说明证据成立时假设成立的 可能性很大 ， 否则 LS1说明 E排斥 H； LN很小 ， 说明证据不成立时假设不成立 的可能性很大 LS和 LN之值接近 1时说明证据成立或不 成立对于结论是否成立影响不大 一般情况下 ， LS和 LN不是根据定义计算 出来的 ， 而是给定的 第 7章 不精确推理 31 应用举例 (1) 例子：评职称的概率 设某副教授 X要评正教授 ， 现有 4个指标 ， 却 有 8人参与竞争 / 投票前夕 ， X作了如下预测： 如果不考虑评委因素 ， 则成功概率 =1/2， 此 相当于先验几率 O(H)=1；如果考虑评委因素 ， 则情况如下： 校评委共 15人 ， 其中 5人来自其他竞争者所 在系 ， 4人与 X素有微隙 ， 尤其是其中 2人兼 具来自其他竞争者所在系 ， 对 X的成功构成 了极大威胁 ， 但聊以自慰的是评委中有 5位 老朋友 ， 估计会投 X的票 第 7章 不精确推理 32 应用举例 (2) 为此 ， X定义了如下的似然比： LS(评委 Y1出席 |X评上 )=1/2 Y1来自其他 竞争者所在系 ， 同时令 LN=2 (LS*LN=1) LS(评委 Y2出席 |X评上 )=1/4 Y2 与 X 素有 微隙 ， 同时令 LN=4 LS(评委 Y3出席 |X评上 )=1/8 Y3来自其他 竞争者所在系兼与 X素有微隙 ， 同时令 LN=8 LS(评委 Y4出席 |X评上 )=4 Y4 是 X 的老 朋友 ， 同时令 LN=1/4 LS(评委 Y5出席 |X评上 )=1 Y5不属于以 上情况 ， LN=1 第 7章 不精确推理 33 应用举例 (3) 若 15人全体出席，且假定各条件互相独立， 则按公式 (6.11)， X评上的后验概率是： O(X评上 |15人出席 )= 根据几率和概率之间的关系 ， 换为概率 P=O/ (1+O)=1/9， X评上的希望不大 第 7章 不精确推理 8 11)1()4() 8 1() 4 1() 2 1( 35223 34 应用举例 (4) 但是 ， 当又有消息说 ， 一位来自其他竞 争者所在系兼与 X素有微隙的评委 A不能 出席 ， 而代之以一位态度中立的评委 / 此 时 ， X又作了一番推测： LS( A出席 |X评上 )=LN(A出席 |X评上 )=8 LS(中立评委 |X评上 )=1 则在原结果的基础上乘上上述因子 ， 使得 后验几率 =1， 即后验概率 =1/2， X评上的 前景大大改观 第 7章 不精确推理 7.3 贝叶斯网络 7.3.1 贝叶斯网络的表示 7.3.2 贝叶斯网络中的精确推理 7.3.3 贝叶斯网络的近似推理 第 7章 不精确推理 36 贝叶斯网络定义 贝叶斯网络 (Bayesian network)是一个有向图 ， 其中每个节点都标注了定量概率信息 (1)一个随机变量集合组成网络节点 ， 变量可以是 离散的或者连续的 (2)一个连接节点对的有向边或者箭头的集合 ， 如 果存在从节点 X指向节点 Y的有向边 ， 则称 X是 Y的一个父节点 (3)每个节点都存在一个条件概率分布 P(Xi|Parent(Xi)，量化父节点对该节点的影响 (4)图中不存在有向环 (是有向无环图 DAG) 第 7章 不精确推理 37 6.3.1 贝叶斯网络的表示 从一个例子 (防盗网 )开始 第 7章 不精确推理 Burglary Earthquake Alarm JohnCall MaryCall P(B) .001 P(E) .002 B E P(A) T T .95 T F .94 F T .29 F F .001 A P(J) T .90 F .05 A P(M) T .70 F .01 38 条件概率表 每个节点旁的条件概率表 (简称 CPT)中 的值对应一个条件事件的概率 如 P(A)=0.94=P(A|Burglary Earthquake) 条件事件是父节点取值的一个可能组合 每行的概率之和应改为 1(表中只给出了为真 的情况 ， 为假的概率应为 1-p) 一个具有 k个布尔父节点的布尔变量的条件 概率表中有 2k个独立的可指定的概率 (注意概 率值是独立的 ) 没有父节点的节点的概率只有 1行 / 为先验 概率 第 7章 不精确推理 39 全联合概率分布 贝叶斯网络给出了关于相关事件的完整 描述 ， 通过计算全联合概率分布求取 联合分布中的某项是对每个变量赋予一个特 定值情况下的合取概率 就是条件概率表中适当元素的乘积 例子 P(j m a b e) =P(j|a)P(m|a)P(a|b e)P(b)P(e) =0.90*0.70*0.001*0.999*0.998=0.00062 第 7章 不精确推理 n i iinn Xpar e ntxPxnxPxXxXP 1 11 )(|(),.1(),.,( 40 链式法则 初始的合取概率化为更小的条件概率和 更小的合取式 / 这些条件概率的合取式 实际上就是父节点到子节点的概率乘积 P(Xi|Xi-1,X 1)=P(Xi|Parent(Xi) 如果 父节点包含于条件 Xi-1,X 1之中 此为链式法则 父子节点的关系使得贝叶斯网络具有局 部结构化的特性，即每个节点只和数量 有限的其它部分产生直接的相互作用 第 7章 不精确推理 41 局部结构化与节点顺序 由于贝叶斯网络的局部结构化 ， 每个随 机变量可以至多受到至多 k个其它随即变 量的影响 (k=常数 ) 设网络中有 n个节点 (随机变量 )， 指定每个 条件概率表所需信息量至多为 2k个数据 ， 则 整个网络可以用 n2k个数据完全描述 /而全联 合概率分布需要 2n个数据 构造贝叶斯网络的次序：添加节点首先 从 “ 根本原因 ”开始 ， 然后加入受其直接 影响的变量 ， 直到叶节点 (不影响任何其 它节点 ) 第 7章 不精确推理 42 条件独立关系 贝叶斯网络中节点相互独立 (下面两个定 义等价 )： (1)给定父节点 ， 一个节点与它的非后代节点 是条件独立的 (2)给定一个节点的父节点 、 子节点以及子节 点的父节点 (Markov blanket)， 这个节点对 于其它节点都是条件独立的 图示 第 7章 不精确推理 43 条件独立关系图示 第 7章 不精确推理 U1 U m X Z1 j Zn j Y1 Yn U1 U m X Z1j Znj Y1 Yn 44 噪声或关系 (1) 贝叶斯网络中尽管父节点个数 k很小 ， 但 是要完成条件概率表仍需要 O(2k)数据 如果找到了变量依赖的 “ 噪声 ” 逻辑关 系 ， 则可以用 O(k)个参数完成条件概率 表 噪声或 (noisy-OR)关系用于刻画不确定关 系 ， 使逻辑或的推广 噪声或关系考虑到每个父节点引起子节 点为真的能力的不确定性 第 7章 不精确推理 45 噪声或关系 (2) 这种不确定性用一个例子表示： 发烧 (fever)为真，当且仅当以下三者之一为 真 感冒 (cold)/流感 (flu)/疟疾 (malaria) 但是可能病人得了以上疾病却没有发烧症状， 这就是父节点为真其子节点未必真的不确定 性 即父子关系被抑制 此时可以认为： fever为假当且仅当所有为真 的 父节点被抑制，其概率为每个父节点被抑 制的概率的乘积 第 7章 不精确推理 46 噪声或关系 (3) 假设每个单独抑制的概率如下 P(fever|cold,flu,malaria)=0.6 P(fever|cold,flu,malaria)=0.2 P(fever|cold,flu,malaria)=0.1 则可以建立一个完整的条件概率表 /大大减 少了所需参数，成为一种有效表示 如 P(fever|cold,flu,malaria)=0.2*0.1=0.02 P(fever|cold,flu,malaria)=0.6*0.2*0.1=0.012 P(fever|cold,flu,malaria)=1-0.012=0.988 第 7章 不精确推理 47 6.3.2 贝叶斯网络中的精确推理 概率推理系统中的基本任务是计算被查 询变量的后验概率 设 X为待查询变量 / e为观察到的证据 / E=E1Em 证据变量集合 / Y=Y1Yn 非 证据变量集合 (也称隐变量 ) 全部变量集合 =X E Y 推理的任务是：求 后验概率 P(X|e) 实际上，根据边缘化规则可得 P(X|e)=P(X,e)=yP(X,e,y) 第 7章 不精确推理 48 查询实例 (1) 上式表明：在贝叶斯网络中计算条件概 率的乘积并求和 ， 以便回答查询 以防盗警报为例 ， 求 P(B|JohnCalls=T,M=F) 证据 JohnCalls=True/MaryCalls=False 查询变量 Burglary=True 隐含变量 Earthquake/Alarm 用首字母简化式有： P(b|j,m)=P(b,j,m) =EAP(b,E,A,j,m) 第 7章 不精确推理 49 查询实例 (2) 进一步代入条件概率： P(b|j,m)=EAP(b)P(E)P(A|b,e)P(j|A)P(m|A) 上式最坏复杂度仍然是 O(n2n)对所有变量求和 改进 将相对常数移到求和符号以外 P(b|j,m)=P(b)EP(E)AP(A|b,E)P(j|A)P(m|A) 计算过程 (遍历 A=a/a和 E=e/e) P(j|a)=0.90 P(m|a)=0.30 P(j|a)=0.05 P(m|a)=0.99 P(a|b,e)=0.95 P(a|b,e)=0.05 P(a|b,e)=0.94 P(a|b,e)=0.06 第 7章 不精确推理 50 查询实例 (3) 乘积求和过程 EP(E)AP(A|b,E)P(j|A)P(m|A) =P(e)*AP(A|b,e)P(j|A)P(m|A)+ P(e)*AP(A|b,e)P(j|A)P(m|A) =P(e)*P(a|b,e)*P(j|a)*P(m|a)+P(a|b,e)* P(j|a)*P(m|a)+P(e)*P(a|b,e)*P(j|a)* P(m|a)+P(a|b,e)* P(j|a)*P(m|a) =0.002*0.95*0.90*0.30+0.05*0.05*0.99 +0.998*0.94*0.90*0.30+0.06*0.05*0.99 =0.002*0.2565+0.0025+0.998*0.2538+0.0030 =0.002*0.2590+0.998*0.2568=0.2568 第 7章 不精确推理 51 查询实例 (4) 相应地有 P(b|j,m)=P(b)*0.2568=0.001*0.2568 =*0.0002568 类似地有 P(b|j,m)=*P(b)EP(E)AP(A|b,E)P(j|A)P (m|A)=*P(b)*0.002*(0.0783+0.0351) +0.998*(0.0003+0.0495)=*0.999*0.0499 =*0.0499 归一化以后有 P(B|j,m)= 只有 John打电话而出现盗贼的概率小于 1/100 第 7章 不精确推理 52 变量消元法 (1) 在计算中我们发现 P(j|a)*P(m|a)和 P(j|a)*P(m|a)重复计算了两次，如何消 除重复？只要保留一次计算结果既可 (动态 规划 ) 通过点积 (pointwise product)求和的方法消去隐 含变量 二元向量 fM(A)=P(m|a) P(m|a)T 消去 A： fAJM(B,E)=fA(a,B,E)*fJ(a)*fM(a) =fA(a,B,E)*fJ(a)*fM(a)+fA(a,B,E)*fJ(a)*fM(a) 第 7章 不精确推理 53 变量消元法 (2) 在这样的计算中只要做： 计算两个因子的点积 在因子乘积中对一个变量求和消元 由此消除了重复计算 在计算中，消除以下无关节点： 删除不是查询变量也非证据变量的叶节点 删除所有不是查询变量祖先也不是证据变量祖 先的节点 第 7章 不精确推理 54 精确推理的复杂度 单连通结构 贝叶斯网络中任何两个节点都 至多只有一条无向路径相连 此时，单连通上的精确推理的时间和空间复 杂度都和网络规模呈线性关系 而对于多连通结构 (见下图 )，最坏情况下变 量消元法可能具有指数级的时空复杂度 此 时贝叶斯网络的推理是一个 NP问题 所以要寻找多连通网络中的近似算法 第 7章 不精确推理 55 多连通网络 第 7章 不精确推理 S R P(W) T T .99 T F .90 F T .90 F F .00 C P(R) T .80 F .20 sprinkler Rain Wet grass C P(S) T .10 F .50 P(C)=.5 cloudy 56 6.3.3 贝叶斯网络的近似推理 大规模多连通网络的精确推理是不可操作的， 所以要考虑近似的推理方法 采用随机采样方法，也称蒙特卡罗算法 (Monte Carlo algorithm)：给出问题的近似解 答，近似的精度依赖于所生成采样点的多少 此处近似的含义 不是通过计算求出网络中 某个点的条件概率 (因为复杂度高 )，而是对 该事件进行采样而获得概率 第 7章 不精确推理 57 后验概率计算的采样方法 有两类采样方法： 直接采样方法 计算样本的频率 马尔科夫链采样方法 根据马尔科夫覆盖中的 变量当前值来采样 直接采样方法 依据已知概率来生成样本 拒绝采样算法 / 似然加权算法 马尔科夫链采样方法 证据变量概率固定条 件下随机生成样本 第 7章 不精确推理 58 直接采样方法 直接采样方法是按照拓扑结构次序依次对每 个变量进行采样，被采样变量值的概率分布 依赖于父节点已取得的赋值 具体实现： 拒绝采样算法 首先按照先验概率分布采样， 然后排除所有与证据不匹配的样本，最后计算 样本频率 似然加权 证据变量的值用权值 (条件概率 )来表 示，只对非证据变量进行采样 第 7章 不精确推理 59 采样样本与概率分布 样本的向量表示 cloudy, sprinkler, rain, wetGrass F/T或者 0/1表 示为假或为真 / 如 T, F, T, T 采样按照已知概率分布进行，但不是等于这 个概率分布值，而是说分布与之相符 cloudy=0.5,0.5 / 第 1次采样 49/51，第 2次采样 52/48 如此等等 每次采样应该在一定的条件下 (这就是条件 概率 )进行，不满足条件的样本不再考虑 第 7章 不精确推理 60 采样过程举例 (1) 通过例子说明采样过程 / 算法均省略 (1)因为 P(cloudy)=, 故 cloudy的采样样本 T/F各占 50%，假设 (不妨 )返回 T (2)P(sprinkler|cloudy=T)=，故 sprinkler的 采样样本 T/F各占 10%和 90%，应该返回 F 注意：此时采样样本均为 形式，其中 占 10%， 占 90% (3)P(rain|cloudy=T)=，故 rain的采样样本 T/F各占 80%和 20%, 应该返回 T / 样本形式类似 于 (2) 第 7章 不精确推理 61 采样过程举例 (2) (4)P(wetGrass|sprinkler=F, rain=T)=， 则返回 T / 采样样本形式 占 90%， 占 10% 实际上如此生成的样本完全符合先验概 率，即 对于上例， cloudy sprinkler rain wetGrass =T F T T=0.5*0.9*0.8*0.9=0.324 第 7章 不精确推理 n i iinnps xP ar e ntxPxxPxxS 1 11 )(|().().( 62 拒绝采样方法 从已知分布的采样出发 (其计算如上 )，通过 去掉不满足证据条件的样本来计算 (估计 )那 些未知分布的事件的概率 例子： P(Rain|Sprinkler=T)未知其概率 / 采样 100 个样本 其中 73个为 ，不满足前提条件 余下 的 27个中 8个为 rain=T / 19个为 rain=F P(Rain|Sprinkler=T)= 拒绝采样方法的最大问题就是效率比较低 第 7章 不精确推理 63 一致的估计 拒绝采样方法能产生真实概率的一致估计 估计的概率在无限多 (大量样本的极限 )条件 下成为精确值，这样的估计称为一致的 (consistent)，即 P(x1,x m)=NPS(x1,x m)/N 第 7章 不精确推理 64 似然加权方法 (1) 对证据节点的概率进行似然加权，即按照先 验概率的乘积进行计算 / 对非证据节点进行 采样，采样样本服从先验概率分布 例子：求 P(rain|sprinkler=T,wetGrass=T)的概率 采样过程如下： (1)权值 w=1.0 (2)P(cloudy)=，据此采样，返回 T (3)Sprinkler是证据变量，取值 T，则 ww*P(sprinkler=T|cloudy=T)=1.0*0.1=0.1 第 7章 不精确推理 65 似然加权方法 (2) (4)P(rain|cloudy=T)=，据此进行采样，假 设 =T (5)wetGrass是证据变量，取值 T，则有 ww*P(wetGrass=T|sprinkler=T,rain=T) =0.1*0.99=0.099 此即 cloudy sprinkler rain wetGrass=T T T T =0.099 / 解释： sprinkler=T & wetGrass=T条件下 rain=T的概率很低 似然加权方法也得到对于真实概率的一致估 计 / 从采样与加权的乘积去理解联合分布概 率的计算，依然是全部条件概率的乘积 第 7章 不精确推理 66 马尔科夫链采样 (1) 直接采样法按照先验概率去采样 马尔科夫链采样对证据变量以外的变量每次 随机地采样 举例：考虑求 P(rain|sprinkler=T,wetGrass=T) 证据变量固定 sprinkler=T/wetGrass=T 隐变量 cloudy/rain则随机采样 初始值不妨假设 cloudy=T/rain=F 初始状态 = 第 7章 不精确推理 67 马尔科夫链采样 (2) 然后反复按照以下 2个步骤采样 (1)当前条件下 对 cloudy随机采样，结果 = (2)当前条件下 对 rain随机采样，结果 = 最后得到若干样本，例如 rain=T=20 / rain=F=60，则 P(rain|sprinkler=T,wetGrass=T)= = (?) 第 7章 不精确推理 68 马尔科夫链采样的合理性 (1) 马尔科夫链 采样过程最终会进入“动态平衡 ” 状态 被采样变量服从马尔科夫覆盖下的条 件概率分布，且“稳态分布” =真实后验概 率 P(x|e) 我们所需要求解的正是给定证据变量 e下某 个变量的概率值 P(x|e) 证明过程： 转移概率 状态 x到状态 x q(x x) 时刻 t处于状态 x的概率 t(x) 第 7章 不精确推理 69 马尔科夫链采样的合理性 (2) 下一时刻处于状态 x的概率 t+1(x)=xt(x)q(x x) 稳态分布 (stationary distribution)当 t+1(x)=t(x)时，马尔科夫链达到稳态分布， 即 (省略 t) (x)=x(x)q(x x) 对于所有 x 细致平衡 任意两个状态间沿两个方向转换概 率相等 (x)q(x x)=(x)q(x x) 对于所有 x, x 简单公式推导 (求和 )可证明细 致平衡中蕴含着稳 态分布 第 7章 不精确推理 70 马尔科夫链采样的合理性 (3) 前述马尔科夫链采样过程称为 Gibbs采样器， 其转移概率写为： q(x x)=q(xi,xi) (xi,xi)=P(xi|xi,e) 由此证明满足细致平衡 (p398)，也就是稳态 分布 而 P(xi|xi,e)正是所求的贝叶斯网络中条件 概率 最终每个时刻的状态概率值都相同 第 7章 不精确推理 7.4 可信度方法 * 7.4.1 可信度定义与性质 7.4.2 证据不确定下 CF的计算 7.4.3 可信度推理例子 第 7章 不精确推理 72 6.4 可信度方法 可信度方法的原则 Mycin系统设计时 考虑了如下一些原则： (1)用接近统计理论的近似方法； (2)用专家经验估计代替统计数据； (3)尽量减少经验估计； (4)适用于证据增量式增加的情况； (5)数据的轻微扰动不影响最终的推理结论 证据理论是其基础 (Dempster-Shafer) 第 7章 不精确推理 73 确认理论为基础 以确认理论为基础，和概率理论的区 别： 设 E为证据， H为假设，则概率论公式为 P(H|E)+P(H|E)=1 CF(certainty factor)表示确认理论下的定 量可信度，则有公式 CF(H|E)+CF(H|E)=0 含义： E肯定了 H(=1)就同时否定了 H (=-1) 第 7章 不精确推理 74 肯定和否定的程度 用两个量来表示在给定证据下，对某个 假设的肯定和否定的程度 表示： MB(measure belief) / MD(disbelief) 含义： MB(H|E)=a 证据 E的出现使假设 H的可信度 增加了数量 a / MD(H|E)=b 证据 E的出现使假 设 H的不可信度增加了数量 b 显然 a/b不能同时大于 0 CF(H|E)=MB(H|E)-MD(H|E) 第 7章 不精确推理 75 6.4.1 可信度定义与性质 MB和 MD的解释：其值应该由专家给出 / 但为了提供某种理论依据，给出其概率 解释， 一般不直接用于构造知识库 其他 若 )( )()(),|(m a x 1)(1 )|( Hp HpHpEHp Hp EHMB 第 7章 不精确推理 其他 若 )( )(),|(m i n )( 1)(1 )|( Hp HpEHpHp Hp EHMD 76 有关性质 (1) MB和 MD的性质 (1)由定义，当 p(H)=1时 MB(H|E)=p(H|E)=1 MD(H|E)=p(H|E)=0 (2)由定义，当 p(H)=1时 MB(H|E)=p(H|E)=0 MD(H|E)=p(H|E)=1 (3)恒有 0MB(H|E)， MD(H|E)1 (4)互斥性：当 MB(H|E)0时 MD(H|E)=0 当 MD(H|E)0时 MB(H|E)=0 即恒有 MB(H|E)*MD(H|E)=0 (5)若 MB(H|E)=1时则对任何 E有 MD(H|E)=0； 反之，若 MD(H|E)=1时则对任何 E有 MB(H|E)=0 第 7章 不精确推理 77 有关性质 (2) 复合证据的处理 (1)MB(H|E1&E2)=MB(H|E1)+MB(H|E2)- MB(H|E1)*MB(H|E2) MD(H|E1&E2)=MD(H|E1)+MD(H|E2)- MD(H|E1)*MD(H|E2) 多于 2个证据的，可以进一步组合 (E1&E2)&E3. (2)MB(H|E1&E2)=MB(H|E1) MD(H|E1&E2)=MD(H|E1) 其中 E2为未知真假的证据 第 7章 不精确推理 78 CF定义与性质 可信度因子 CF(H|E)=MB(H|E)-MD(H|E) 根据 MB/MD的互斥性知， CF只取 MB或 MD之 一值 性质： (1)-1CF(H|E)1 (2)CF(H|E)+CF(H|E)=0 (3)令 E+=E1&En 为所有支持 H的证据总和 (即 MB(H|Ei)0) / E-=E1&E m 为所有不支 持 H的证据总和 (即 MD(H|Ej)0) CF(H|E+&E-)=MB(H|E+)-MD(H|E-) 第 7章 不精确推理 79 CF性质 当多个证据导出同一假设时，先求出各自 MB/MD然后利用复合证据处理公式得出总的 MB/MD，再得到 CF (4)若 H1Hk是 k个互相独立的假设， E为对其 有利的证据，则 第 7章 不精确推理 1)|( 1 k i i EHCF 80 6.4.2 证据不确定下的 CF计算 不确定证据下 CF的计算 证据 E本身不确定，其可信度用 CF(E)或 CF(E|S)表示， S是证据 E的观察 / 有性质如 下： (1)当证据 E以某种程度为真时， 0CF(E)1以 某种程度为假时， -1CF(E)0 (2)证据 E肯定真时 CF(E)=1 证据肯定假时 CF(E)=-1 对证据一无所知时 CF(E)=0 第 7章 不精确推理 81 证据的 CF计算 (1) CF对复合证据的处理：同 MB/MD的定义 (1)CF(H|E1&E2)=CF(H|E1)+CF(H|E2) CF(H|E1)*CF(H|E2) (2)CF(H|E1&E2)=CF(H|E1) 其中 E2为未知真假的证 据 证据的合取与析取 (1)E=E1 and and En CF(E1and and En)=minCF(E1),CF(En) (2)E=E1 or or En CF(E1 or or En)=maxCF(E1),CF(En) 第 7章 不精确推理 82 证据的 CF计算 (2) 由证据与规则的可信度求假设的可信 度 CF(H|S)=CF(H|E)max0,CF(E) (CF(E)0 时 则不能应用 ) MB(H|S)=MB(H|E)max0,CF(E) MD(H|S)=MD(H|E)max0,CF(E) 第 7章 不精确推理 83 可信度阈值 可信度阈值的设定 为了使专家数据的轻微扰动不影响推理结论， Mycin系统 设置了最低阈值 0.2，即只有 CF0.2 的证据才对信念函数 MB/MD起作用 由此补充对假设可信度的计算 (1)MB(H|E)=0 如果 MD(H|E)=1或 CF(E)0.2 (2)MD(H|E)=0 如果 MB(H|E)=1或 CF(E)0.2 (3)MB/MD/CF(H|S)=MB/MD/CF(H|E)*CF(E) 如果 CF(E)0.2 否则为 0 第 7章 不精确推理 84 6.4.3 可信度推理例子 推理规则形式 :=, 设有推理网络如下图所示，其推理规 则为 (1)A BH, 0.7 (2)CH, 0.5 (3)(D E) F (G I)H, 0.9 (4)JH, 0.3 每个证据的可信度标在叶子节点的下面，节 点分叉带弧者为与节点 第 7章 不精确推理 85 推理网络 第 7章 不精确推理 H C J A B F D E G I 0.2 0.5 0.4 0.2 0.8 0. 1 0.6 0.4 - 0.8 0.3 0.9 0.5 0.7 86 求解过程 (1) 求解步骤： (1)CF(H|A B)=0.7*min0.2,0.5=0.14 按照阈值规定可不考虑其对假设 H推理的贡 献，即下一步不参与计算 (2)CF(H|C)=0.5*0.4=0.2 (3)CF(H|(D E) F (G I)=0.9*min max0.4,0.2,0.6,max0.8,0.1=0.9*0.4=0.36 (4)CF(H|J)=0.3*(-0.8)=-0.24 第 7章 不精确推理 87 求解过程 (2) (5)由定义可知 MB1=0.2 MB2=0.36 MB3=0 MD1=0 MD2=0 MD3=0.24 MB=0.2+0.360.2*0.36=0.488 MD=0.24 故 CF=MB MD=0.488 0.24=0.248 第 7章 不精确推理 88 求解过程 (3) 如果将 CF=0.14计算在内，则 MB=0.14+0.2+0.36 0.14*0.2 0.14*0.36 0.2*0.36+0.14*0.2*0.36 =0.55968 MD=0.24 CF=0.55968 0.24=0.31968 注意：计算的步骤是分别求每个证据的 CF或 MB/MD，然后用复合证据公式计算 MB/MD， 最后得 CF=MBMD 第 7章 不精确推理 7.5 模糊推理 7.5.1 模糊数据的确定 7.5.2 模糊关系及其投影 7.5.3 模糊推理的例子 第 7章 不精确推理 90 7.5.1 模糊数据的确定 确定模糊数据 即 隶属函数的确定 如何确定隶属函数 ？ 有多种方法 调查投票 根据投票统计所得的数据确定出 隶属函数 用概率分布函数模拟 分为 3种 (1)正态分布 (2)戒上型函数 (3)戒下型函数 第 7章 不精确推理 91 调查投票例子 调查投票 根据投票统计所得的数据确 定出隶属函数 例子 古代选美： 明末南京有 “ 秦淮八艳 ” ， 要判断谁更漂亮 ？ 不同人有不同看法 ， 现设有 100人投票 ， 可 通过与其中一位比较的方法确定一种相对量 度 / 设其他 7位与李香君比较 (得票数少于 50者被认为不如她 ， 多者则超过她 )， 根据 每个人所得票数可得隶属函数 / 显然 ， 在 隶属度函数中 ， 李香君本人应该放在 0.5的 位置 第 7章 不精确推理 92 调查投票结果表示 第 7章 不精确推理 序号 1 2 3 4 5 6 7 8 姓名 顾横波 柳如是 陈圆圆 李香君 寇白门 董小宛 马湘兰 卞玉京 得票 42 43 45 - 54 55 58 67 93 概率分布函数 (1) 用概率分布函数来逼近隶属函数 (1)中心强 、 两边弱 、 中间对称的隶属度分布 可用正态分布来逼近 ， 如 “ 中年 ” ； (2)对于隶属度随某种属性值而增长的情况 ， 可采用单调递增或非减函数 ， 特别是当属性值 足够大时隶属度恒为 1的情况 ， 可采用戒下型 函数 ， 如 “ 老年 ” ； (3)对于隶属度随某种属性值而减小的情况 ， 可采用单调递减或非增函数 ， 当属性值足够小 时隶属度恒为 1的情况 ， 可采用戒上型函数 ， 如 “ 童年 ” 第 7章 不精确推理 94 函数分布函数 (2) 上述 3种函数的公式为： (1)正态分布 (x)= (2)戒下型函数 2)( b ax e 第 7章 不精确推理 bx bxae ax x ax bx c 1 10 0 )( 22 )( 95 函数分布函数 (3) (3)戒上型函数 三个函数的图形如下： 0 a 1 0 a b 1 0 a b 1 bx bxae ax x bx ax c 0 10 1 )( 22 )( 第 7章 不精确推理 1 96 7.5.2 模糊关系及其投影 模糊关系：模糊关系是集合的笛卡尔 积的子集 +对集合的隶属函数 (如第 3章 定义 ) 设 R为 A1A2.An上的一个 n元模糊关系 ， 则 R中的元素表示为 (a1,a2, ,an),(a1,a2, ,an) 其中 an Ai， (a1,a2, ,an)是对 R的隶属度 构成了 n维空间超矩阵 第 7章 不精确推理 97 模糊关系的合成 模糊关系的合成：设 R是 U V上的模糊关 系 ， S是 V W上的模糊关系 ， 则 R与 S的合 成关系 Z=R S的元素为： Zij = (ui,w), 这里是 (ui,vk),R(ui,vk)与 (vk,wj), S(vk,wj)的 合成 ， 而 V的元素个数为 n(k=1n组合一遍 ) 第 7章 不精确推理 ),(),( 1 jkSkiR n k wvvuM inM a x 98 模糊关系例子 例 1： 设 R模糊关系表示“天下乌鸦一般黑” 定义在集合 U2上， U中的每个元素是乌鸦，如 俄罗斯乌鸦、美国乌鸦、科索沃乌鸦、南联盟 乌鸦等等， R是 U2中任意 2只乌鸦之间是否一样 黑的程度，其隶属度如 (美国乌鸦 , 科索沃乌鸦 ) =0.7 / 又设 S模糊关系表示“天下乌鸦打仗一样 激烈” (即任意 2只乌鸦参与争斗时的激烈程度 是否一致 )，则对于第 i只和第 j只乌鸦来说，存 在 1只乌鸦 c， c和第 i只乌鸦一样黑、和第 j只乌 鸦打仗一样激烈的为真程度用 R S的元素 RS(ij) 表示 第 7章 不精确推理 99 模糊关系的投影 模糊关系的投影：设 R是 A1 . An上的 一个模糊关系，则在 Ak=Ai1 . Aik上的 一个 k元模糊关系 Rk定义为其上的投影， 其中 1kn， 1i1i2.ikn R k= 其中 Ak为在 A1 An中去掉 k个 Ai1 Aik后 所得 n-k个 Aj的笛卡尔积 第 7章 不精确推理 ),(),( 21 , 21 nR AkbAka ii aaaM a xaaia i k 100 定义的解释 解释： 上述定义的意思是投影集合 (模糊子集 ) 的个体元素 (即前半部分 )来自 Ak(是一个 k元向 量 )，第 2个隶属度元素则是 与其他 n-k 个 Aj中的全部个体元素组合后得到的 |Aj1| |Aj(n-k)|个 R中取极大值的结果 如 果基底集合为 Un，则投影共有 |U|k个不同元素， 每个元素从 |U|n-k个不同 R中取极大值 / 同理， 还可以定义隶属度为取极小值结果 / 这样的投 影分别称为胖投影和瘦投影，统称为柱状扩展 第 7章 不精确推理 101 模糊关系投影例子 (1) 例 2： 设某公司有 3个部门构成集合 A1=a, b, c， 新聘 3位员工构成集合 A2=d, e, f， 令 A=A1 A2， A上的模糊关系 R定义为 “ 将新员 工安排到各部门的合适人选 ” ， 这个二元模糊 关系的隶属函数矩阵如下表示 第 7章 不精确推理 d e f a 0.8 0.4 0.6 b 0.2 0.5 0.7 c 0.9 0.6 0.3 102 模糊关系投影例子 (2) R在 A1上的胖投影 RF(A1)=(a, 0.8), (b, 0.7), (c, 0.9)，表示各部门 找到合适人选的乐观估计 R在 A1上的瘦投影 RT(A1)=(a, 0.4), (b, 0.2), (c, 0.3)，表示相应的 悲观估计 另一方面， RF(A2)=(d, 0.9), (e, 0.6), (c, 0.7)，表示各人能 在各部门找到合适工作的乐观估计 RF=(d, 0.2), (e, 0.4), (f, 0.3)为相应的悲观估计 第 7章 不精确推理 103 模糊关系投影例子 (3) 注意：这里乐观估计并不能全部实现，因为会 产生冲突，如果 a部门安排了合适人选 d，则 c部 门就找不到最合适人选；同样， d在 c部门找到 最合适工作，则 e就找不到最合适工作了 第 7章 不精确推理 104 7.5.3 模糊推理的例子 模糊推理 A B可看作 A与 B之间存在函数 关系。实际应用中使用了第 3章给出的计 算方法，即 模糊推理的例子 规则 A=“如果气候温和并且雨量充沛则适于 种柑橘” 第 7章 不精确推理 ) ) )(),(m i n (),(m a x ()( BvAvAvBAv 105 模糊推理的例子 (1) 其中各模糊集表示为： 气候温和 C=(10, 0.5), (20, 1), (30, 0.5), (40, 0.2)， 其个体元素构成的分明集记为 #C=10, 20, 30,40是平均摄氏温度 雨量充沛 R=(100, 0.1), (200, 0.4), (300, 0.7), (400, 1)， 对应的分明集 #R=100, 200, 300, 400是年降雨量 (毫米 ) 适于种柑橘 S=(100, 0.5), (200, 0.7), (300, 1)， 对应的分明集 #S=100, 200, 300是单株产量 (斤 ) 第 7章 不精确推理 106 模糊推理的例子 (2) 那么，模糊推理规则为 C R S，显然隶属函 数值 v可通过如下公式求得： )(),(m in ()( RvCvRCv 第 7章 不精确推理 )(),(m i n (1)(1)( RvCvRCvRCv )(),(),(m i n ( m i n (),(),(m i n (1m a x )(),(m i n (),(m a x ()( SvRvCvRvCv SvRCvRCvSRCv 故可得出下页的模糊矩阵 107 模糊推理的例子 (3) 矩阵中每个元素值表示在一定的气候和雨量组 合下 (每行 )不同单株产量 (列 )的可能性 (隶属函 数值 ) 第 7章 不精确推理 气候和雨量 组合 单株产量 100 单株产量 200 单株产量 300 ( 1 0 ,1 0 0 ) 0 .9 0 .9 0 .9 ( 1 0 ,2 0 0 ) 0 .6 0 .6 0 .6 ( 1 0 ,3 0 0 ) 0 .5 0 .5 0 .5 ( 1 0 ,4 0 0 ) 0 .5 0 .5 0 .5 ( 2 0 ,1 0 0 ) 0 .9 0 .9 0 .9 ( 2 0 ,2 0 0 ) 0 .6 0 .6 0 .6 ( 2 0 ,3 0 0 ) 0 .5 0 .7 0 .7 ( 2 0 ,4 0 0 ) 0 .5 0