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
the majority function of $n$ variables can be represented by a bag of $T$ ($<
n$) decision trees each with polynomial size if $n-T$ is a constant, where $n$
and $T$ must be odd (in order to avoid the tie break). We also show that a bag
of $n$ decision trees can be represented by a bag of $T$ decision trees each
with polynomial size if $n-T$ is a constant and a small classification error is
allowed. A related result on the $k$-out-of-$n$ functions is presented too.

本论文主要研究将一组决策树表示为较小的一组决策树的问题，其中只考虑二进制域上的二元决策问题和简单决策树。通过实验，我们展示了如果 $n-T$ 是一个常数，即 $n$ 和 $T$ 必须是奇数（以避免并列情况），则 $n$ 个变量的多数函数可以由 $T$ 个决策树的集合以多项式大小表示，同时也证明了如果 $n-T$ 是一个常数且允许小的分类错误，则 $n$ 个决策树可以由 $T$ 个决策树的集合以多项式大小表示。我们还介绍了关于 $k$ 个为真的 $n$ 个函数的相关结果。