On The Expressive Power of Decision Tree Ensembles

Sokolov Andrey Pavlovich; Prokhorenkova Liudmila Alexandrovna

On The Expressive Power of Decision Tree Ensembles

Sokolov A. P., Prokhorenkova L. A.

Sokolov Andrey Pavlovich

unior scientific researcher, Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Chair of Mathematical Theory of Intellectual Systems

Prokhorenkova Liudmila Alexandrovna

researcher, Yandex

Published: 2023, vol. 27, issue 1, pp. 18–23

Download full text (In Russian)

Abstract

Decision trees are widely used in machine learning, statistics and data mining. Predictive models based on decision trees show outstanding results in terms of accuracy and training time. Especially on heterogeneous tabular datasets. Performance, simplicity and integrity make this family of algorithms one of the most popular in data science. One important hyper-parameter of decision tree training algorithms is maximum depth of the trees. This paper proves theoretical result that shows how maximum depth of decision trees limits the expressive power of ensemble. This result is applicable to such tree based algorithms as plain Decision Tree, Random Forest, GBDT and others.

Keywords: machine learning, data science, decision tree, random forest, gradient boosting.

BibTeX

@article{IS-Sokolov-Prokhorenkova2023,
  author  = {Sokolov, Andrey Pavlovich and Prokhorenkova, Liudmila Alexandrovna},
  title   = {{On The Expressive Power of Decision Tree Ensembles}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2023},
  volume  = {27},
  number  = {1},
  pages   = {18--23},
}

AMSBIB

\Bibitem{IS-Sokolov-Prokhorenkova2023}
\by A.\,P.~Sokolov, L.\,A.~Prokhorenkova
\paper On The Expressive Power of Decision Tree Ensembles
\jour Intelligent Systems. Theory and Applications
\yr 2023
\vol 27
\issue 1
\pages 18--23
\lang In Russian

Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue