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

三、复杂度分析

在VE算法中，最耗费时间和空间的步骤是对 $Elim(F,Z)$ 的调用。
他的运输段复杂度远远超过其他步骤，所以可以把这一步的复杂度作为整个算法的复杂度。
$Elim(F,Z)$ 从F中挑选出所有涉及Z的函数 $\{f_1,...,f_k\}$ ，将它们相乘得到中间函数g，再讲Z从g中消去。
设 $X_1,...X_t$ 是g中所有除Z之外的变量。
如果把函数表示成多为表，则g所需储存的函数值的个数为 $|Z|\prod^l_{i=1}|X_i|$ 。
因此 $|Z|\prod^l_{i=1}|X_i|$ 是函数g的复杂性的一个恰当的度量，从而也是 $Elim(F,Z)$ 的复杂性的一个恰当的度量。
这称之为Z的消元成本(elimination cost)，记为 $l(Z)$ 。
在推理过程中，VE算法需要消去多个变量，设它们依次为 $Z_1,Z_2,...,Z_n$ ，用总消元成本 $l=\sum^n_{i=1}l(Z_i)$ 来度量VE算法的复杂度。
式 $\sum^n_{i=1}l(Z_i)$ 中最大的一项对整个式子的值的大小起支配作用，因此有时也用它来度量VE算法的复杂性。

在上一章的网络中，设所有变量均取二值，校园顺序 $\rho=<C,E,B,D>$ ，消去C时，需要计算 $g=P(C)P(E|B,C)$ ，共设计3个变量：B,C和E。
所以C的消元成本为 $l(C)=2\times 2\times 2=8$ 。
类似的，其它3个节点E,B和D的消元成本分别为8,8和4。
因此，用 $\rho$ 进行变量消元的总成本为28，其中最大的一项为8.

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。