An investigation on the conditions of pruning an induced decision tree

Empirical studies have shown that pruning a decision tree can increase the accuracy of a learned concept. A recent result identified conditions under which pruning techniques increase prediction accuracy. However, this result is based on samples of size three. This paper provides a generalization of previous results and investigates conditions where pruning is beneficial for concept accuracy as well as concept simplification. We show that pruning is theoretically useful in many situations.