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

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

二、变量消元算法

2. 消元运算
  • 抽象地讲，一个联合分布是一个多变量函数。于是，分解的概念可以自然地推广到一般的多元函数。。
  • 设F(X_1,X_2,...,X_n)是变量\{X_1,X_2,...,X_n\}的一个函数，而F=\{f_1,f_2,...,f_m\}是一组函数，其中每个f_1所涉及的变量是\{X_1,X_2,...,X_n\}的一个子集。
  • 如果F=\prod^m_{i=1}f_i，则称F是F的一个分解(factorization)，f_1,f_2,...,f_m称为这个分解的因子(factor)。
  • 从F(X_1,X_2,...,X_n)出发，可通过如下方式获得变量\X_2,...,X_n的一个函数G(X_2,...,X_n) = \sum_{X_1}F(X_1,X_2,...,X_n)。
  • 从函数F(X_1,X_2,...,X_n)中消去X_1，得到函数G(X_2,...,X_n)这个过程叫消元(elimination)。
  • 设F = \{f_1,...,f_m\}是函数F(X_1,X_2,...,X_n)的一个分解。从F中消去变量X_1指的是如下过程：
  • 从F中删去所有涉及X_1的函数（不失一般性，设这些函数是\{f_1,...,f_k\}）；
  • 将新函数\sum_{X_1}\prod^k_{i=1}f_i放回F中。
  • 定理：设F是函数F(X_1,X_2,...,X_n)的一个分解。设F'是从F中消去X_1后所得的一组函数，G(X_2,...,X_n)是从F(X_1,X_2,...,X_n)中消去X_1后所得的函数。那么，F'是G(X_2,...,X_n)的一个分解。
  • 证明：设F=\{f_1,...,f_m\}，而X_1只在\{f_1,f_2,...,f_k\}中出现。
  • 有G(X_2,...,X_n) = \sum_{X_1}F(X_1,X_2,...,X_n) = \sum_{X_1}\prod^m_{i=1}f_i=\sum_{X_1}(\prod^k_{i=1}f_i\prod^m_{i=k+1}f_i)=(\sum_{X_1}\prod^k_{i=1}f_i)\prod^m_{i=k+1}f_i(因为\prod^m_{i=k+1}f _i不涉及X_1)。 定理得证。
  • 很显然，直接从F(X_1,X_2,...,X_n)中消去变量X_1而得到G(X_2,...,X_n)的计算复杂度相对于变量个数n成指数增长。
  • 但是，从F(X_1,X_2,...,X_n)的一个分解F中消去X_1，而得到G(X_2,...,X_n)的一个分解F'的计算复杂度未必相对于n成指数增长。
  • 实际上，这个过程的主要运算是计算\sum_{X_1}\prod^k_{i=1}f_i，其复杂度只依赖于涉及X_1的因子f_1,...,f_k所涉及到的变量个数可能远远小于n。
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容