Cousins S B, Chen W, Frisse M E
Department of Internal Medicine, Washington University School of Medicine, St. Louis, MO.
Artif Intell Med. 1993 Aug;5(4):315-40. doi: 10.1016/0933-3657(93)90020-4.
Belief networks combine probabilistic knowledge with explicit information about conditional independence assumptions. A belief network consists of a directed acyclic graph in which the nodes represent variables and the edges express relationships of conditional dependence. When information about one variable's state is given to the network in the form of evidence, an update algorithm computes the posterior marginal probability distributions for the remaining variables in the network. Many algorithms for performing this inference task have been proposed. Exact algorithms report precise results for some classes of networks, but take exponential time (in the number of nodes) both in the worst case and for many interesting networks. Stochastic simulation algorithms estimate the posterior marginal probability distribution for many graph topologies that would require exponential time when using an exact algorithm. Nonetheless, for some belief networks, stochastic simulation algorithms are also known to have exponential worst case performance. This article describes at a tutorial level several stochastic simulation algorithms for belief networks, and illustrates them on some simple examples. In addition, the theoretical and empirical performance of the algorithms is briefly surveyed.
信念网络将概率知识与关于条件独立性假设的明确信息相结合。一个信念网络由一个有向无环图组成，其中节点表示变量，边表示条件依赖关系。当以证据的形式将关于一个变量状态的信息提供给网络时，一种更新算法会计算网络中其余变量的后验边缘概率分布。已经提出了许多执行此推理任务的算法。精确算法为某些类别的网络报告精确结果，但在最坏情况下以及对于许多有趣的网络而言，都需要指数时间（以节点数量计）。随机模拟算法估计许多图拓扑的后验边缘概率分布，而使用精确算法时这些拓扑需要指数时间。尽管如此，对于某些信念网络，随机模拟算法在最坏情况下也具有指数性能。本文以教程的形式描述了几种用于信念网络的随机模拟算法，并在一些简单示例上进行了说明。此外，还简要概述了这些算法的理论和实证性能。
