Reducing the number of trees in a bag of binary decision trees governed by the majority vote

In this paper, we focus on the prediction phase of a random forest and study the problem of representing a bag of decision trees using a smaller bag of decision trees, where we only consider binary decision problems on the binary domain and simple decision trees in which an internal node is limited to querying the Boolean value of a single variable. As a main result, we show that given a constant integer c the majority function of an odd number n of variables can be represented by a bag of $$n-2c$$ decision trees each of which has size polynomial in n. We also show that a general bag of n decision trees can be represented by another bag containing only $$n-2c$$ polynomial-size decision trees, provided a small classification error is allowed. A related result on the k-out-of-n functions is presented as well.