A New Pruning Method for Solving Decision Trees and Game Trees
The main goal of this paper is to describe a new pruning method for solving decision trees and game trees. The pruning method for decision trees suggests a slight variant of decision trees that we call scenario trees. In scenario trees, we do not need a conditional probability for each edge emanating from a chance node. Instead, we require a joint probability for each path from the root node to a leaf node. We compare the pruning method to the traditional rollback method for decision trees and game trees. For problems that require Bayesian revision of probabilities, a scenario tree representation with the pruning method is more efficient than a decision tree representation with the rollback method. For game trees, the pruning method is more efficient than the rollback method.
Keywords: Decision theory, decision trees, game trees
PDF Link: /papers/95/p482-shenoy.pdf
AUTHOR = "Prakash Shenoy
TITLE = "A New Pruning Method for Solving Decision Trees and Game Trees",
BOOKTITLE = "Proceedings of the Eleventh Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-95)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1995",
PAGES = "482--490"