Feature importance from trees

WHAT are we computing?

The three ingredients:

• Impurity $i(t)$: how mixed a node is (Gini or entropy for classification, variance/MSE for regression).
• Impurity decrease $\Delta i(t)$: how much the split cleans up the node.
• Weighting $N_t/N$: a split high in the tree affects many samples → counts more.

HOW: derive $\Delta i(t)$ from first principles

WHY do we weight children? A parent node with $N_t$ samples splits into a left child ($N_{t_L}$) and right child ($N_{t_R}$). We compare the parent's impurity to the average impurity of the children — but a child holding more samples should count more. So we weight children by their sample fractions:

$\Delta i(t)=i(t)\;-\;\frac{N_{t_L}}{N_t}\,i(t_L)\;-\;\frac{N_{t_R}}{N_t}\,i(t_R)$

Why this is always $\ge 0$: greedy tree algorithms choose the split that maximizes this drop, and impurity is a concave function, so splitting can never increase (weighted) impurity. That's why importances are non-negative.

Now multiply by the arrival weight $N_t/N$ (fraction of all data that reaches node $t$) and sum over every node splitting on $f$ → gives $\text{Imp}(f)$ above.

Forests: average over trees

For a Random Forest / GBM with $T$ trees, importance is the mean over trees, usually normalized to sum to 1: $\text{Imp}_{\text{forest}}(f)=\frac{1}{T}\sum_{\tau=1}^{T}\text{Imp}_\tau(f),\qquad \widehat{\text{Imp}}(f)=\frac{\text{Imp}(f)}{\sum_{g}\text{Imp}(g)}$

Worked Example 1 — one split, Gini

Root has 10 samples: 5 positive, 5 negative. A split on feature $X_1$ gives:

• Left: 4 samples (4 pos, 0 neg)
• Right: 6 samples (1 pos, 5 neg)

Step 1 — parent impurity. Why? Baseline mixed-ness. $i(\text{root})=1-(0.5^2+0.5^2)=0.5$

Step 2 — child impurities. Why? Measure how clean each side got. $i(L)=1-(1^2+0^2)=0$ $i(R)=1-((1/6)^2+(5/6)^2)=1-(0.0278+0.6944)=0.2778$

Step 3 — weighted child impurity. Why? Big child counts more. $\frac{4}{10}(0)+\frac{6}{10}(0.2778)=0.1667$

Step 4 — impurity decrease. Why? Cleanup achieved. $\Delta i = 0.5-0.1667=0.3333$

Step 5 — arrival weight. Root sees all data, $N_t/N=10/10=1$. $\text{Imp}(X_1)=1\times 0.3333=\boxed{0.3333}$

Worked Example 2 — deeper node weighting

Suppose $X_2$ splits at a node reached by only 3 of 10 samples, with $\Delta i=0.4$.

Step — apply arrival weight. Why? A split affecting few samples shouldn't dominate. $\text{Imp}(X_2)=\frac{3}{10}\times 0.4=0.12$

Even with a bigger local $\Delta i$ (0.4 > 0.3333), $X_2$ (0.12) ranks below $X_1$ (0.3333) because $X_1$'s split touched everyone. This is the whole reason for $N_t/N$.

Normalized: $\widehat{\text{Imp}}(X_1)=\frac{0.3333}{0.4533}=0.735$, $\widehat{\text{Imp}}(X_2)=0.265$.

Worked Example 3 — regression (variance drop)

Node with $y=\{2,4,6,8\}$, $\bar y=5$. Split into $\{2,4\}$ and $\{6,8\}$.

Step 1 — parent variance. $\frac{(9+1+1+9)}{4}=5$ Step 2 — child variances. Each child: $\bar y=3$ or $7$, var $=\frac{1+1}{2}=1$. Step 3 — weighted. $\frac12(1)+\frac12(1)=1$ Step 4 — decrease. $\Delta i=5-1=4$. Big drop → this feature separates $y$ well.

Flashcards

Connections

• Decision Trees — MDI is a byproduct of the same impurity used to grow the tree.
• Gini vs Entropy — choice of $i(t)$ changes importance values.
• Random Forests — importance averaged over many trees for stability.
• Gradient Boosting — also exposes split-based importances (gain/cover/frequency).
• Permutation Importance — unbiased, model-agnostic alternative.
• SHAP Values — game-theoretic attribution fixing MDI biases.
• Bias-Variance Tradeoff — training MDI overestimates due to overfitting.

Concept Map

Hinglish (regional understanding)