AIS-BN: An adaptive importance sampling algorithm for evidential reasoning in large Bayesian networks
AIS-BN: An adaptive importance sampling algorithm for evidential reasoning in large Bayesian networks
复制标题
DOI：
10.1613/jair.764
复制
发表时间：
2000-01-01
影响因子：
5
通讯作者：
Druzdzel, MJ
中科院分区：
文献类型：
--
作者：
Cheng, J;Druzdzel, MJ
随机抽样算法虽然是非常大的贝叶斯网络模型中精确算法的一个有吸引力的替代方案，但已观察到在证据极不可能的证据推理中表现不佳。为了解决这个问题，我们提出了一个自适应的重要性采样算法，AIS-BN，即使在极端条件下，显示有前途的收敛速度，似乎优于现有的采样算法一致。这种性能改进的三个来源是（1）基于有限维积分中重要性抽样的理论性质和贝叶斯网络的结构优势的重要性函数初始化的两种算法，（2）重要性函数的平滑学习方法，（3）动态加权函数，用于合并算法不同阶段的样本。BN算法沿着两种最先进的通用采样算法，似然加权（Fung & Chang，1989; Shachter & Peot，1989）和自重要性采样（Shachter & Peot，1989）。我们在测试中使用了科学界可用的三个大型真实的贝叶斯网络模型：CPCS网络（Pradhan等人，1994）、Pathopathy网络（Heckerman，Horvitz，& Nathwani，1990）和安第斯山脉网络（Conati，Gertner，VanLehn，& Druzdzel，1997），证据不太可能为10（-41）。虽然AIS-BN算法总是比其他两种算法表现得更好，但在大多数测试用例中，它在结果精度方面实现了数量级的改进。在给定所需精度的情况下，速度的提高甚至更加引人注目，尽管我们无法在这里报告数值结果，因为其他算法几乎从未达到过甚至由AIS-BN算法的前几次迭代所达到的精度。
Stochastic sampling algorithms, while an attractive alternative to exact algorithms in very large Bayesian network models, have been observed to perform poorly in evidential reasoning with extremely unlikely evidence. To address this problem, we propose an adaptive importance sampling algorithm, AIS-BN, that shows promising convergence rates even under extreme conditions and seems to outperform the existing sampling algorithms consistently. Three sources of this performance improvement are (1) two heuristics for initialization of the importance function that are based on the theoretical properties of importance sampling in finite-dimensional integrals and the structural advantages of Bayesian networks, (2) a smooth learning method for the importance function, and (3) a dynamic weighting function for combining samples from different stages of the algorithm.We tested the performance of the AIS-BN algorithm along with two state of the art general purpose sampling algorithms, likelihood weighting (Fung & Chang, 1989; Shachter & Peot, 1989) and self-importance sampling (Shachter & Peot, 1989). We used in our tests three large real Bayesian network models available to the scientific community: the CPCS network (Pradhan et al., 1994), the PathFinder network (Heckerman, Horvitz, & Nathwani, 1990), and the ANDES network (Conati, Gertner, VanLehn, & Druzdzel, 1997), with evidence as unlikely as 10(-41). While the AIS-BN algorithm always performed better than the other two algorithms, in the majority of the test cases it achieved orders of magnitude improvement in precision of the results. Improvement in speed given a desired precision is even more dramatic, although we are unable to report numerical results here, as the other algorithms almost never achieved the precision reached even by the first few iterations of the AIS-BN algorithm.