Variable elimination for influence diagrams with super value nodes

摘要

In the original formulation of influence diagrams (IDs), each model contained exactly one utility node. In 1990, Tatman and Shachter introduced the possibility of having super value nodes that represent a combination of their parents' utility functions. They also proposed an arc-reversal algorithm for IDs with super value nodes. In this paper we propose a variable-elimination algorithm for influence diagrams with super value nodes which is faster in most cases, requires less memory in general, introduces much fewer redundant (i.e., unnecessary) variables in the resulting policies, may simplify sensitivity analysis, and can speed up inference in IDs containing canonical models, such as the noisy OR.