Decision Trees in Mathematical Terms, and What Random Forests and XGBoost Improve

Describe, in mathematical terms, how a decision tree is built and how it makes predictions. Then discuss its advantages and disadvantages, the benefits of a random forest, and what XGBoost gains in comparison. ### Clarifying Questions - Should the description cover classification, regression, or both? - Should it include how continuous features, categorical features and missing values are split? - How deep should the XGBoost discussion go: its training objective and split rule, or the main ideas only? ### Part 1 — How a decision tree is built, in math Define the quantity a split optimizes, how the best split is found, when growth stops, and how a leaf makes its prediction. ```hint Greedy and local Write down the score of a single candidate split, then explain why the tree is grown one split at a time instead of being optimized as a whole. ``` #### What This Part Should Cover - Impurity measures and the split gain, with formulas - The search over features and thresholds, the stopping rules and pruning - Leaf predictions for classification and regression ### Part 2 — Strengths and weaknesses of a single tree Discuss the advantages and disadvantages of a single decision tree. ```hint Change a few rows Ask what happens to a deep tree's structure and predictions when a few training rows change. ``` #### What This Part Should Cover - Practical strengths such as interpretability, mixed data types and no need for feature scaling - Weaknesses in variance, boundary shape and extrapolation - How depth controls the bias-variance trade-off ### Part 3 — Random forests, and what XGBoost adds Explain why a random forest improves on a single tree, then what XGBoost gains compared with it. ```hint Two different repairs One ensemble averages many trees grown independently; the other adds trees one after another. Ask which kind of error each one reduces. ``` #### What This Part Should Cover - Bagging and per-split feature subsampling, and why decorrelating the trees matters - Boosting as stagewise fitting of a loss, and XGBoost's regularized objective - When each ensemble is the better choice, and what it costs ### What a Strong Answer Covers - Correct formulas for impurity, split gain and leaf predictions - An explanation of greedy growth, stopping and pruning - A balanced list of tree strengths and weaknesses grounded in bias and variance - The variance argument for random forests, including the role of tree correlation - XGBoost's second-order, regularized objective and its practical additions, with the trade-offs against random forests ### Follow-up Questions - Why does a random forest choose among a random subset of features at each split instead of all of them? - Derive the optimal leaf weight in XGBoost from its second-order objective. - How does XGBoost handle missing values when it chooses a split? - Your gradient-boosted model overfits. Which settings would you change first?