Efficient Calculation of Optimal Decisions in Graphical Models

Abstract

We present a method for finding the optimal decision on Random Variables in a graphical model. Upper and lower bounds on the exact value for each decision are used to reduce the complexity of the algorithm, while we still ensure that the decision chosen actually represents the exact optimal choice. Since the highest lower bound value is also a lower bound on the value of the optimal decision, we rule out any candidate with an upper bound of lower value than the highest lower bound. By this strategy, we try to reduce the number of candidates to a number we can afford to do exact calculations on.We generate five Bayesian Networks with corresponding value functions, and apply our strategy to these. The bounds on the values are obtained by use of an available computer program, where the complexity is controlled by an input constant. We study the number of decisions accepted for different values of this input constant. From the first Network, we learn that the bounds does not work well unless we split the calculations into parts for different groups of the nodes. We observe that this splitting works well on the next three Networks, while the last Network illustrates how the method fails when we add more edges to the graph. We realize that our improved strategy is successful on sparse graphs, while the method is unsuccessful when we increase the density of edges among the nodes.