大师兄的贝叶斯网络学习笔记（十九）：贝叶斯网络与概率推理（二）

大师兄的贝叶斯网络学习笔记（十八）：贝叶斯网络与概率推理（一）

二、变量消元算法

  • 本节揭示为什么联合分布的分解可以降低概率推理复杂性的原理，并给出一个计算后验概率P(Q|E=e)的基本算法，即变量消元算法(variable elimination)。
1. 概率分布的分解与推理复杂度

  • 概率分布的分解与推理复杂度


  • 以上图为例，考虑计算P(D)，有P(D)=\sum_{A,B,C}P(A,B,C,D)=\sum_{A,B,C}P(A)P(B|A)P(C|B)P(D|C)。
  • 假设所有变量均为二值，而且乘法按顺序进行，上式的运算复杂如下：
  • P(A)与P(B|A)相乘需要4次乘法
  • 其结果与P(C|B)相乘需要8次乘法
  • 结果再与P(D|C)相乘需要16次乘法
  • 共计28次乘法。
  • 另外加法供需14次。
  • 为了利用联合分布的分解来降低推理的计算复杂度，可以注意到在右边的4个因子中，只有P(A)和P(B|A)与变量A相关，而与B相关的因子只有P(C|B)和P(B|A)。
  • 因此有P(D) = \sum_CP(D|C)\sum_B(C|B)\sum_AP(A)P(B|A)。
  • 其中P(A)与P(B|A)相乘需要4次乘法，边缘化消去A需要做2次乘法
  • 这一步与P(C|B)相乘需要做4次乘法，然后消去B需要做2次加法
  • 其结果再与P(D|C)相乘需要做4次乘法，然后消去C需要做2次加法
  • 计算乘法总数为12，而加法为6，复杂度更低。
  • 联合分布的分解之所以能够降低推理的复杂度，主要是因为它使运算可以局部化。
  • 在前面的式子中，消去A涉及所有变量：A、B、C、D，因此复杂度高。
  • 而后面的式子消去A只涉及它自身以及与他直接相连的变量B，因此复杂度低。
  • 在上面的例子中，运算局部化节省了大约一半的预算量。在变量众多的网络中，节省可能是指数级的。
  • 后式本身可以改写为如下算法形式：
  • 设F是贝叶斯网络中所有概率分布的集合，即：F=\{\underline P(A),P(B|A),P(C|B),P(D|C)\}
  • 从F中删去所有含变量A的函数P(A)和P(B|A),并生成一个新函数\fi_1(B) = \sum_AP(A)P(B|A)
  • 然后将其加入F，得到F=\{\fi_1(B),P(C|B),P(D|C) \}
  • 从F中删去所有含变量B的函数\fi_1(B)和P(C|B),并生成新函数\fi_2(C)=\sum_BP(C|B)\fi_1(B)
  • 将其加入F，得到F = \{\phi_2(C),P(D|C)\}
  • 从F中删去所有含变量C的函数\phi_2(C)和P(D|C)，并生成新函数\phi_3(D)=\sum_CP(D|C)\phi_2(C)
  • 返回\phi_3(D)，正是P(D)。
  • 在第2步之后，变量A不再在F的函数中出现，所以可以说，它在第2步中被消去，而A被消去的过程称为消元。
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

友情链接更多精彩内容