题目:贝叶斯网络推理算法简单罗列
上一篇《贝叶斯网络与最大可能解释(MPE)问题》理清了最大可能解释(Most Probable Explanation, MPE)的概念,接下来准备在MATLAB中基于工具箱FullBNT-1.0.4实现贝叶斯网络推理,但在此之前还是走马观花式地看一下贝叶斯网络推理算法,本篇取名为“罗列”意味着非常简略的提及一下,因此不要期待能够学得什么具体内容,仅为后面MATLAB实现作一个过渡和铺垫~
贝叶斯网络推理算法大致可分为精确推理算法和挖推理算法两类。精确推理算法希望能计算出目标变量的边际分布或条件分布的精确值,然而此类算法的计算复杂度随着极大团规模的增长呈指数增长,因此仅适用于贝叶斯网络的规模较小时。当贝叶斯网络的规模较大时,多采用近似推理,近似推理算法可以在较低时间复杂度下获得原问题的近似解。
在【周志华. 机器学习[M]. 清华大学出版社,2016.】的14.4节(学习与推断)中介绍了两种精确推理算法(变量消去和信念传播),14.5节介绍了两种近似推理算法(MCMC采样和变分推断)。
在【刘俊娜. 贝叶斯网络推理算法研究[D]. 合肥工业大学, 2007.】2.5节提到:精确推理算法主要有:多树传播(Polytree Propagation)推理算法;团树传播的(Clique TreePropagation)方法,如联结树(Junction Tree Propagation)推理算法;基于组合优化的求解方法,如符号推理(Symbolic ProbabilisticInference)和桶消元推理(Bucket Elemination Inference)算法。近似推理算法主要有:基于搜索的(Search—Based)方法;Monte Carlo算法。针对不同的贝叶斯网络,用户可以选择合适的推理算法进行推理。各种推理算法相互独立,方便用户选择。图2.5给出了现有贝叶斯网络推理的各种算法。