贝叶斯网络概率推理中的空间优化方法

Space Optimization Algorithm in Probabilistic Inference of Bayesian Networks

递归调节算法作为一种贝叶斯网络精确推理算法由于存储结果的个数是任意的,存储所占用的内存大小是可变的,所以该算法在空间上是自由的。然而当内存空间有限时,又希望节省计算时间,存储哪些计算结果就成了关键问题。针对此问题本文提出了应用深度优先分支定界法寻找存储占用空间的所有可能性,然后通过任意空间下推理时间的求解公式得到相应的推理时间,进而构造贝叶斯网络推理的时间—空间曲线,通过所构造的曲线找出最优离散存储策略,得到时间和空间之间的最佳的结合点,以最小时间代价换取了最大的存储空间。

Recursive conditioning is an any-space algorithm for exact inference in Bayesian networks because any number of results may be cached.But given a limited amount of memory,which results should be cached in order to minimize the running time of the algorithm becomes a key question.Aiming at this problem,depth-first branch-and-bound method is proposed to search all the potential goal states,average running time under each state is computed,then some optimal time-space tradeoff curves were made.Through the curves,an optimal discrete cache scheme can be found,with this scheme,significant amounts of memory can be removed from the algorithm＇s cache with only a minimal cost in time.