On evidence absorption for belief networks

AbstractMore and more real-life applications of the belief-network framework are emerging. As applications grow larger, the belief networks involved increase in size accordingly. For large belief networks, probabilistic inference tends to become rather time-consuming. In the worst case this tendency may not be denied, as probabilistic inference is known to be NP-hard. However, it is possible to improve on the average-case performance of the algorithms involved. For this purpose, the method of evidence absorption can be exploited. In this paper, we detail the method of evidence and outline its integration into a well-known algorithm for probabilistic inference. The ability of the method to improve on the average-case computational expense of probabilistic inference is illustrated by means of experiments performed on both randomly generated and real-life belief networks