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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
UCT-ADP Progressive Bias Algorithm for Solving Gomoku
We combine Adaptive Dynamic Programming (ADP), a reinforcement learning method and UCB applied to trees (UCT) algorithm with a more powerful heuristic function based on Progressive Bias method and two pruning strategies …
Reinforcement LearningOptimally Pruning Decision Tree Ensembles With Feature Cost
We consider the problem of learning decision rules for prediction with feature budget constraint. In particular, we are interested in pruning an ensemble of decision trees to reduce expected feature cost while maintainin…
Ensemble PruningPredictionAdaptively Pruning Features for Boosted Decision Trees
Boosted decision trees enjoy popularity in a variety of applications; however, for large-scale datasets, the cost of training a decision tree in each round can be prohibitively expensive. Inspired by ideas from the multi…
Fast Linear Model Trees by PILOT
Linear model trees are regression trees that incorporate linear models in the leaf nodes. This preserves the intuitive interpretation of decision trees and at the same time enables them to better capture linear relations…
modelModel SelectionregressionMulti-Armed Bandits-Based Optimization of Decision Trees
Decision trees, without appropriate constraints, can easily become overly complex and prone to overfit, capturing noise rather than generalizable patterns. To resolve this problem,pruning operation is a crucial part in o…
Reinforcement LearningMulti-Armed Bandits