PREPROCESSING RULES FOR TRIANGULATION OF PROBABILISTIC NETWORKS *
PREPROCESSING RULES FOR TRIANGULATION OF PROBABILISTIC NETWORKS *
复制标题
概率网络三角剖分的预处理规则*
DOI：
10.1111/j.1467-8640.2005.00274.x
复制
发表时间：
2005
影响因子：
2.8
通讯作者：
F. V. D. Eijkhof
中科院分区：
文献类型：
--
作者：
H. Bodlaender;A. Koster;F. V. D. Eijkhof
目前，最有效的概率网络推理算法建立在网络图的三角测量之上。在本文中，我们表明预处理可以帮助为概率网络找到良好的三角剖分，即最大团尺寸尽可能小的三角剖分。我们提供了一组逐步缩小图的规则，而不失去最优性。这种减少使我们能够在较小的图上解决三角测量问题。根据较小图的三角剖分，通过反转归约步骤获得原始图的三角剖分。我们的实验结果表明，一些众所周知的现实生活中的概率网络的图可以通过预处理得到最佳的三角测量；对于其他网络，其图的大小得到了极大的减小。
Currently, the most efficient algorithm for inference with a probabilistic network builds upon a triangulation of a network's graph. In this paper, we show that pre‐processing can help in finding good triangulations for probabilistic networks, that is, triangulations with a maximum clique size as small as possible. We provide a set of rules for stepwise reducing a graph, without losing optimality. This reduction allows us to solve the triangulation problem on a smaller graph. From the smaller graph's triangulation, a triangulation of the original graph is obtained by reversing the reduction steps. Our experimental results show that the graphs of some well‐known real‐life probabilistic networks can be triangulated optimally just by preprocessing; for other networks, huge reductions in their graph's size are obtained.