# On the Trade-off between the Number of Nodes and the Number of Trees in a Random Forest

arXiv: https://arxiv.org/abs/2312.11540 · HTML: https://mlsanity.com/paper/2312.11540/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 18 references that are in the map.
- First posted on arXiv 16 Dec 2023.

## Builds on (most cited first, 4 of 4)

- [Trading Complexity for Sparsity in Random Forest Explanations](https://mlsanity.com/paper/2108.05276/) (2021)
- [On PAC-Bayesian Bounds for Random Forests](https://mlsanity.com/paper/1810.09746/) (2018)
- [When are Deep Networks really better than Decision Forests at small sample sizes, and how?](https://mlsanity.com/paper/2108.13637/) (2021)
- [Improved bounds for the randomized decision tree complexity of recursive majority](https://mlsanity.com/paper/1309.7565/) (2013)

## Abstract (arXiv)

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.