Decision Trees, Random Forests & Gradient Boosting
Gradient boosting still wins most tabular problems in production. Know how it works internally, why it beats random forests, and how to explain its predictions.
Covers: Tree splitting criteria, bagging vs boosting, XGBoost/LightGBM internals, feature importance, SHAP, hyperparameter tuning
If a company has tabular data — and almost every company does — gradient boosting is probably running in production somewhere. Interviewers know this, so tree questions get asked far more often than the deep-learning questions candidates over-prepare for.
30-second answer
It greedily evaluates every feature and threshold and picks the split that maximises the reduction in an impurity measure, weighted by child sizes. Classification uses Gini (1 − Σp²) or entropy (−Σp log p); regression uses variance/MSE reduction. Gini and entropy agree on the chosen split about 98% of the time, so Gini is preferred purely because it avoids a logarithm.
The weighted impurity decrease. The tree picks the (feature, threshold) pair that maximises this.
| Criterion | Formula | Range (binary) | Notes |
|---|---|---|---|
| Gini impurity | 0 → 0.5 | Probability that two random draws differ in class. Default in CART/sklearn. | |
| Entropy | 0 → 1 | Information-theoretic; slightly more sensitive to small probability changes. | |
| MSE / variance | ≥ 0 | Regression default; equivalent to maximising between-group variance. | |
| MAE | ≥ 0 | Robust to outliers but much slower — no closed-form incremental update. |
import numpy as np
def gini(y):
if len(y) == 0: return 0.0
p = np.bincount(y) / len(y)
return 1.0 - (p ** 2).sum()
def best_split(X, y):
n, n_feat = X.shape
parent, best = gini(y), (None, None, 0.0)
for j in range(n_feat):
order = np.argsort(X[:, j])
xs, ys = X[order, j], y[order]
for i in range(1, n): # every candidate threshold
if xs[i] == xs[i - 1]:
continue # no split between equal values
left, right = ys[:i], ys[i:]
weighted = (len(left)*gini(left) + len(right)*gini(right)) / n
gain = parent - weighted
if gain > best[2]:
best = (j, (xs[i] + xs[i - 1]) / 2, gain)
return best # (feature_index, threshold, gain)
rng = np.random.default_rng(0)
X = rng.normal(size=(200, 3))
y = ((X[:, 1] > 0.4) ^ (X[:, 2] > -0.2)).astype(int) # XOR-ish on features 1,2
print(best_split(X, y)) # (1, 0.4108..., 0.0621) -> finds feature 1 near 0.41That nested loop is per node after sorting, and overall including the sorts. Understanding this cost is what motivates every optimisation in modern boosting libraries: histogram binning (bucket continuous features into 255 bins so you scan bins not rows), pre-sorted column blocks, and cached gradient statistics.
Properties that fall out of the greedy algorithm
- Scale-invariant — splits are threshold comparisons, so standardising features changes nothing. This is why trees need no feature scaling and linear models do.
- Handles non-linearity and interactions natively — depth-2 already encodes a two-way interaction with no feature engineering.
- Greedy, therefore not globally optimal — finding the optimal tree is NP-hard. This is exactly why ensembles help: many greedy trees explore different parts of the space.
- Struggles with additive linear relationships — approximating needs a staircase of many splits, while a linear model needs one coefficient. Good instinct for when not to use trees.
- Biased toward high-cardinality features — a feature with many unique values has more candidate thresholds and so more chances to look good by luck.
Say these points
- Greedy search over (feature, threshold), maximising weighted impurity decrease.
- Gini vs entropy: near-identical results; Gini is cheaper (no log).
- Cost is O(n·d) per node — the reason histogram binning exists.
- Trees are scale-invariant and model interactions natively but fit linear trends poorly.
- Depth and leaf-size constraints matter far more than the impurity criterion.
Avoid these mistakes
- Standardising features 'because it's good practice' before a tree model.
- Claiming entropy is meaningfully better than Gini.
- Forgetting that greedy splitting means the tree is not globally optimal.
Expect these follow-ups
- How do trees handle missing values without imputation?
- Why are trees biased toward high-cardinality features, and how do you counter it?
- What is cost-complexity pruning and how do you choose ccp_alpha?
30-second answer
Bagging trains many deep, low-bias, high-variance trees on bootstrap samples in parallel and averages them — averaging independent errors reduces variance without adding bias, so more trees only ever converges. Boosting trains shallow, high-bias trees sequentially, each fitting the previous ensemble's residuals — this reduces bias but each tree also fits some noise, so past a point more trees increases variance and test error rises.
| Bagging (Random Forest) | Boosting (XGBoost/LightGBM) | |
|---|---|---|
| Trees are trained | In parallel, independently | Sequentially, each on the last one's errors |
| Base learner | Deep trees (low bias, high variance) | Shallow trees (high bias, low variance) |
| Primarily reduces | Variance | Bias |
| More trees | Monotonically converges — cannot overfit | Eventually overfits — needs early stopping |
| Parallelisable | Fully (across trees) | Only within a tree |
| Sensitive to noisy labels | Robust (averaging) | Sensitive (chases outliers) |
| Typical accuracy on tabular | Very good, minimal tuning | Best-in-class, needs tuning |
Why averaging cannot hurt
As grows, ensemble variance decreases monotonically toward a floor of , where is the average pairwise correlation between trees. It converges — it never turns around. And this formula explains the single design decision that makes a random forest more than 'bagged trees': random feature subsampling at each split (max_features) exists purely to reduce , lowering that asymptote. Without it, every tree would pick the same dominant feature first and be highly correlated.
Why boosting can turn around
Boosting is a stagewise additive model: , where is fitted to the negative gradient of the loss at . Each tree deliberately targets what the ensemble got wrong — including the parts that were wrong because of noise. After the signal is exhausted, further trees fit noise, training loss keeps falling and validation loss rises. That is why every boosting library ships early stopping, and why n_estimators in boosting is a hyperparameter to tune while in a random forest it is 'as many as you can afford'.
import numpy as np
from sklearn.ensemble import RandomForestClassifier, GradientBoostingClassifier
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.metrics import log_loss
X, y = make_classification(n_samples=3000, n_features=20, n_informative=6,
flip_y=0.15, random_state=0) # 15% label noise
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=0)
print(f"{'trees':>6} {'RF test':>9} {'GBM train':>11} {'GBM test':>10}")
for n in (10, 50, 100, 300, 800, 2000):
rf = RandomForestClassifier(n_estimators=n, random_state=0, n_jobs=-1).fit(X_tr, y_tr)
gbm = GradientBoostingClassifier(n_estimators=n, learning_rate=0.1,
max_depth=3, random_state=0).fit(X_tr, y_tr)
print(f"{n:>6} {log_loss(y_te, rf.predict_proba(X_te)):>9.4f}"
f" {log_loss(y_tr, gbm.predict_proba(X_tr)):>11.4f}"
f" {log_loss(y_te, gbm.predict_proba(X_te)):>10.4f}")
# trees RF test GBM train GBM test
# 10 0.5661 0.5108 0.5326
# 50 0.4415 0.3652 0.4188
# 100 0.4297 0.2914 0.4159 <- GBM test minimum around here
# 300 0.4238 0.1436 0.4512 <- train still falling, TEST RISING
# 800 0.4221 0.0402 0.5187
# 2000 0.4218 0.0061 0.6033 <- badly overfit
#
# RF converges and flattens. GBM turns around. Early stopping is not optional.Say these points
- Bagging: parallel, deep trees, reduces variance, monotone in tree count.
- Boosting: sequential, shallow trees, reduces bias, overfits past an optimum.
- Ensemble variance floor is ρσ² — feature subsampling exists to lower ρ.
- Recipe: low learning rate + many estimators + early stopping.
- 'RFs can't overfit' applies to tree count, not tree depth or noisy small data.
Avoid these mistakes
- Tuning n_estimators for boosting by grid search instead of early stopping.
- Using deep trees in a boosted model (max_depth 3–8 is the normal range).
- Claiming random forests are immune to overfitting in all senses.
Expect these follow-ups
- Why does XGBoost include the second-order (Hessian) term?
- How does Extremely Randomised Trees differ from a random forest?
- Explain stacking and when it beats a single well-tuned GBM.
30-second answer
XGBoost uses second-order gradients with explicit regularisation and grows trees level-wise. LightGBM grows leaf-wise (best-first), uses histogram binning plus GOSS sampling and exclusive feature bundling, making it much faster on wide/large data but more prone to overfitting on small data. CatBoost uses ordered boosting and ordered target statistics to eliminate the prediction-shift bias from categorical encoding, and is the strongest default when you have many categorical features.
XGBoost: second-order optimisation
The core innovation is taking a second-order Taylor expansion of the loss rather than just the gradient. With the first derivative and the second:
Two things to notice. First, the optimal leaf weight has a closed form — no line search. Second, is subtracted from the gain, so a split whose improvement does not exceed is rejected: pruning is built into the objective rather than bolted on afterwards.
LightGBM: speed through three tricks
| Technique | What it does | Effect |
|---|---|---|
| Leaf-wise growth | Split the leaf with the highest gain anywhere in the tree, not level by level | Lower loss per tree; needs num_leaves control or it overfits |
| Histogram binning | Bucket continuous features into ~255 bins before splitting | Split search becomes O(bins) not O(n); ~10× faster |
| GOSS | Keep all large-gradient rows, randomly subsample the small-gradient ones with reweighting | Fewer rows scanned with little accuracy loss |
| EFB | Bundle mutually-exclusive sparse features into a single feature | Collapses one-hot dimensionality |
CatBoost: fixing target-encoding bias
CatBoost attacks a subtle statistical problem called prediction shift. In standard gradient boosting, the gradients used to fit tree are computed with a model that was itself trained on those same rows — so residuals are optimistically small and the model is biased. Target encoding of categoricals compounds this. CatBoost's ordered boosting imposes a random permutation and, for each row, computes both its target statistic and its gradient using only rows earlier in the permutation. It is the same out-of-fold logic as leak-free target encoding, generalised to the whole boosting procedure.
# ---------- XGBoost: the reliable default ----------
import xgboost as xgb
model = xgb.XGBClassifier(
n_estimators=5000, learning_rate=0.03,
max_depth=6, min_child_weight=1,
subsample=0.8, colsample_bytree=0.8, # stochastic boosting: decorrelates trees
reg_lambda=1.0, reg_alpha=0.0, gamma=0.0,
tree_method="hist", early_stopping_rounds=100,
eval_metric="auc",
)
model.fit(X_tr, y_tr, eval_set=[(X_va, y_va)], verbose=False)
print("best iteration:", model.best_iteration) # early stopping picks n_estimators
# ---------- LightGBM: fastest on wide/large data ----------
import lightgbm as lgb
params = dict(objective="binary", metric="auc", learning_rate=0.03,
num_leaves=63, max_depth=8, # KEEP max_depth set!
min_data_in_leaf=100, # the anti-overfit knob
feature_fraction=0.8, bagging_fraction=0.8, bagging_freq=1,
lambda_l2=1.0, verbosity=-1)
booster = lgb.train(params, lgb.Dataset(X_tr, y_tr), num_boost_round=5000,
valid_sets=[lgb.Dataset(X_va, y_va)],
callbacks=[lgb.early_stopping(100), lgb.log_evaluation(0)])
# ---------- CatBoost: best when categoricals dominate ----------
from catboost import CatBoostClassifier, Pool
cat_features = ["city", "device", "merchant_id"] # pass RAW strings, no encoding
model = CatBoostClassifier(iterations=5000, learning_rate=0.03, depth=6,
l2_leaf_reg=3.0, eval_metric="AUC",
early_stopping_rounds=100, verbose=0)
model.fit(Pool(X_tr, y_tr, cat_features=cat_features),
eval_set=Pool(X_va, y_va, cat_features=cat_features))Say these points
- XGBoost: second-order Taylor expansion, closed-form leaf weights, γ prunes inside the gain.
- LightGBM: leaf-wise growth + histograms + GOSS + EFB — fast, but overfits small data.
- num_leaves < 2^max_depth, and raise min_data_in_leaf on small datasets.
- CatBoost: ordered boosting and ordered target statistics eliminate prediction shift.
- Accuracy is comparable when tuned; choose on speed, categoricals and tooling.
Avoid these mistakes
- Leaving LightGBM's max_depth at −1 on a small dataset.
- One-hot encoding categoricals before handing them to CatBoost (defeats its main advantage).
- Tuning n_estimators by grid search rather than early stopping.
Expect these follow-ups
- How does XGBoost handle missing values during split finding?
- Why does subsample < 1 help boosting, given each tree already sees the residuals?
- When would a neural network beat GBDT on tabular data?
30-second answer
Default impurity-based importance is biased toward high-cardinality and continuous features, is computed on training data so it rewards overfitting, and splits credit arbitrarily among correlated features. Use permutation importance on a held-out set for a global, model-agnostic view, and SHAP values when you need per-prediction attributions with consistency guarantees.
| Method | What it measures | Main weakness |
|---|---|---|
Impurity (feature_importances_) | Total impurity decrease attributed to each feature | Cardinality bias; computed on train data; free and instant |
| Permutation importance | Metric drop when a feature is shuffled | Misleading with correlated features (shuffling creates impossible rows) |
| Drop-column importance | Metric drop when a feature is removed and the model refit | The ground truth, but costs a full retrain per feature |
| SHAP | Game-theoretic per-prediction attribution | Expensive in general; TreeSHAP makes it fast for trees |
Proving the cardinality bias
import numpy as np, pandas as pd
from sklearn.ensemble import RandomForestClassifier
from sklearn.inspection import permutation_importance
from sklearn.model_selection import train_test_split
rng = np.random.default_rng(0)
n = 2000
df = pd.DataFrame({
"real_binary": rng.integers(0, 2, n), # 2 unique values, REAL signal
"noise_continuous":rng.normal(size=n), # continuous, NO signal
"noise_id": rng.permutation(n), # 2000 unique values, NO signal
})
y = (df["real_binary"] + rng.normal(scale=0.5, size=n) > 0.5).astype(int)
X_tr, X_te, y_tr, y_te = train_test_split(df, y, test_size=0.3, random_state=0)
rf = RandomForestClassifier(n_estimators=300, random_state=0).fit(X_tr, y_tr)
print("IMPURITY importance (train, biased):")
for f, v in sorted(zip(df.columns, rf.feature_importances_), key=lambda t: -t[1]):
print(f" {f:18s} {v:.3f}")
perm = permutation_importance(rf, X_te, y_te, n_repeats=20, random_state=0)
print("\nPERMUTATION importance (holdout, honest):")
for f, v in sorted(zip(df.columns, perm.importances_mean), key=lambda t: -t[1]):
print(f" {f:18s} {v:+.3f}")
# IMPURITY importance (train, biased):
# noise_id 0.417 <- pure noise, ranked FIRST
# noise_continuous 0.336 <- pure noise, ranked SECOND
# real_binary 0.247 <- the only real signal, ranked LAST
#
# PERMUTATION importance (holdout, honest):
# real_binary +0.281
# noise_continuous -0.002
# noise_id -0.004SHAP: what makes it different
SHAP assigns each feature its Shapley value — its average marginal contribution across all possible orderings of feature inclusion. It is the unique attribution satisfying local accuracy (attributions sum to the prediction minus the base value), missingness, and consistency (if a model changes so a feature matters more, its attribution cannot decrease). No other common method has all three.
Local accuracy: the base value plus all SHAP values reconstructs the exact prediction.
import shap
explainer = shap.TreeExplainer(model) # exact & fast for tree ensembles
sv = explainer(X_test) # (n_samples, n_features)
# Global: mean |SHAP| per feature — the honest ranking
import numpy as np
order = np.argsort(-np.abs(sv.values).mean(0))
for i in order[:5]:
print(f"{X_test.columns[i]:22s} {np.abs(sv.values[:, i]).mean():.4f}")
# Local: explain ONE decision to a customer or a regulator
i = 42
print(f"\nbase value : {sv.base_values[i]:+.3f}")
for j in np.argsort(-np.abs(sv.values[i]))[:4]:
print(f" {X_test.columns[j]:22s} {sv.values[i, j]:+.3f}")
print(f"prediction : {sv.base_values[i] + sv.values[i].sum():+.3f}")
# base value : -1.204
# n_late_payments_12m +0.812
# credit_utilization +0.451
# account_age_months -0.223
# income_band -0.118
# prediction : -0.282One practical caveat: with strongly correlated features, permutation importance shuffles one and the model recovers via its correlated twin, so both look unimportant. In that situation use grouped permutation (shuffle the correlated block together), hierarchical clustering on the correlation matrix, or conditional/interventional SHAP.
Say these points
- Impurity importance is biased toward high-cardinality features and computed on training data.
- Permutation importance on a holdout set is the honest, cheap global default.
- SHAP uniquely satisfies local accuracy, missingness and consistency.
- Correlated features break naive permutation — use grouped permutation.
- Importance is not causation; interventions require a causal design.
Avoid these mistakes
- Presenting impurity importance to stakeholders unchecked.
- Computing permutation importance on the training set.
- Treating SHAP magnitude as a causal effect size.
Expect these follow-ups
- How does TreeSHAP achieve polynomial time when exact Shapley is exponential?
- Explain the difference between interventional and conditional SHAP.
- How would you validate that a feature is causally driving the outcome?
30-second answer
Fix the learning rate low and let early stopping choose the tree count, then tune in order of impact: tree complexity (max_depth/num_leaves, min_child_weight), then sampling (subsample, colsample), then regularisation (lambda, alpha). Use Bayesian optimisation or Optuna's TPE rather than grid search, add a pruner to kill bad trials early, and always tune against the same CV scheme you will report.
Order of impact
| Priority | Parameters | Typical range | Why |
|---|---|---|---|
| 0 — fix, don't tune | learning_rate + n_estimators | η ∈ 0.01–0.05, n very high | Early stopping picks the count; low η dominates high η in final accuracy |
| 1 — highest impact | max_depth / num_leaves, min_child_weight / min_data_in_leaf | depth 3–10, leaves 15–255, min_child 1–100 | Directly controls the bias/variance of each learner |
| 2 — strong | subsample, colsample_bytree | 0.6–1.0 | Decorrelates trees; the boosting analogue of RF feature sampling |
| 3 — refinement | reg_lambda, reg_alpha, gamma | λ 0–10 (log), α 0–1, γ 0–5 | Fine-grained shrinkage; matters most on small/noisy data |
| 4 — problem-specific | scale_pos_weight, custom objective | ≈ neg/pos ratio | Class imbalance and asymmetric costs |
import optuna, numpy as np, lightgbm as lgb
from sklearn.model_selection import StratifiedKFold
from sklearn.metrics import roc_auc_score
optuna.logging.set_verbosity(optuna.logging.WARNING)
def objective(trial):
params = {
"objective": "binary", "metric": "auc", "verbosity": -1,
"learning_rate": 0.03, # FIXED, not tuned
"num_leaves": trial.suggest_int("num_leaves", 15, 255, log=True),
"max_depth": trial.suggest_int("max_depth", 3, 12),
"min_data_in_leaf": trial.suggest_int("min_data_in_leaf", 5, 300, log=True),
"feature_fraction": trial.suggest_float("feature_fraction", 0.5, 1.0),
"bagging_fraction": trial.suggest_float("bagging_fraction", 0.5, 1.0),
"bagging_freq": 1,
"lambda_l2": trial.suggest_float("lambda_l2", 1e-3, 20.0, log=True),
"lambda_l1": trial.suggest_float("lambda_l1", 1e-3, 5.0, log=True),
}
scores = []
cv = StratifiedKFold(5, shuffle=True, random_state=0)
for fold, (tr, va) in enumerate(cv.split(X, y)):
booster = lgb.train(
params, lgb.Dataset(X.iloc[tr], y[tr]), num_boost_round=5000,
valid_sets=[lgb.Dataset(X.iloc[va], y[va])],
callbacks=[lgb.early_stopping(100, verbose=False)])
scores.append(roc_auc_score(y[va], booster.predict(X.iloc[va])))
trial.report(float(np.mean(scores)), fold) # enables mid-CV pruning
if trial.should_prune():
raise optuna.TrialPruned()
return float(np.mean(scores))
study = optuna.create_study(
direction="maximize",
sampler=optuna.samplers.TPESampler(seed=42, n_startup_trials=20),
pruner=optuna.pruners.MedianPruner(n_warmup_steps=2))
study.optimize(objective, n_trials=200, timeout=6 * 3600)
print("best AUC :", round(study.best_value, 5))
print("best params:", study.best_params)
print("pruned :", sum(t.state == optuna.trial.TrialState.PRUNED for t in study.trials))Why not grid search
Bergstra & Bengio's classic result: with hyperparameters where only a few matter, grid search wastes almost all its evaluations exploring irrelevant dimensions. Random search covers the important dimensions with far more distinct values for the same budget. Bayesian methods (TPE, GP-based) go further by modelling the response surface and concentrating trials where improvement is likely. Grid search over 6 hyperparameters is the clearest sign of an inexperienced practitioner.
- Log-scale the right parameters. Learning rate, λ, α and min_data_in_leaf are multiplicative — always
log=True. - Prune aggressively. MedianPruner or Hyperband kills hopeless trials after a fold or two, often tripling the number of configurations you can explore.
- Seed-average the winner. Retrain the best configuration with 5 seeds and average predictions; typically worth more than the last 100 trials of search.
- Record everything. Log every trial to MLflow or W&B — the search itself is an experiment you will want to audit later.
Say these points
- Fix a low learning rate and let early stopping choose n_estimators.
- Tune in order: tree complexity → sampling → regularisation → imbalance.
- Use TPE/Bayesian search with a pruner; grid search wastes the budget.
- Log-scale multiplicative hyperparameters.
- The best-of-200 CV score is biased — confirm on an untouched holdout.
Avoid these mistakes
- Tuning learning rate and n_estimators jointly in the search space.
- Grid searching six parameters and exhausting the budget on two of them.
- Reporting the tuned CV score as the expected production performance.
Expect these follow-ups
- How does Hyperband/ASHA allocate budget differently from Bayesian optimisation?
- How would you parallelise this search across 20 machines?
- When is a 0.002 AUC improvement worth shipping?
Showing 5 of 5 questions for trees-ensembles-and-boosting-interview.
Check your understanding
5 questions · no sign-up, nothing stored
Hands-on challenge
Build it — this is what you talk about in a deep-dive round.
Beat a tuned GBM baseline the honest way
Take any tabular dataset and build a reproducible pipeline that improves on a default LightGBM without fooling yourself.
Requirements
- A leak-free CV scheme appropriate to the data (grouped and/or time-based), used identically for every experiment.
- Baseline: LightGBM with defaults + early stopping. Record the CV mean and standard deviation.
- Optuna search with a pruner over the priority-ordered space; log every trial.
- Compare impurity, permutation and SHAP importances and write up where they disagree and why.
Stretch goals
- Add a 5-seed average of the best configuration and quantify the gain versus more search trials.
- Stack LightGBM + CatBoost + a regularised linear model and measure whether stacking beats the best single model by more than one standard error.