Exercises — Gini impurity

One class means $p_1=1$ and every other $p_i=0$. $G=1-(1^2+0^2+\dots )=1-1=0$ Answer: $G=0$. A pure box — you can never lose the guessing game, so the mistake probability is zero.

For $K=2$ classes the maximum possible Gini is $1-\frac{1}{K}=1-\frac{1}{2}=0.5$, reached exactly at 50/50. $G=1-(0.5^2+0.5^2)=1-0.5=0.5$ Answer: maximum, $G=0.5$.

Purity is highest when one class dominates. As the mix approaches 50/50, impurity rises. Order (purest → most impure): $(1,0)\prec (0.9,0.1)\prec (0.6,0.4)\prec (0.5,0.5)$. Check with numbers: $0<0.18<0.48<0.5$. The figure below plots the whole 2-class Gini curve $G=2p(1-p)$ and drops these four nodes onto it. Notice how quickly the curve climbs away from the pure ends: moving from $(0.9,0.1)$ to $(0.6,0.4)$ jumps impurity from $0.18$ to $0.48$ — nearly the maximum — even though $p$ only slid from $0.9$ to $0.6$. The lesson to read off the curve: impurity is insensitive near the pure ends (flat) and very sensitive in the middle (steep), which is why a split that pushes a node even slightly past the halfway point barely helps, while one that nudges a near-pure node the rest of the way barely helps either — the payoff lives in the steep middle.

Proportions: $p_{\text{red}}=\frac{3}{5}=0.6$, $p_{\text{blue}}=p_{\text{green}}=\frac{1}{5}=0.2$. $G=1-(0.6^2+0.2^2+0.2^2)=1-(0.36+0.04+0.04)=1-0.44=0.56$ Answer: $G=0.56$.

Parent $p=(\frac{1}{2},\frac{1}{2})$: $G_{\text{parent}}=1-(0.5^2+0.5^2)=0.5$ Left $p=(\frac{5}{6},\frac{1}{6})$: $G_L=1-\left(\frac{25}{36}+\frac{1}{36}\right)=1-\frac{26}{36}=\frac{10}{36}\approx 0.2778$ Right $p=(\frac{1}{6},\frac{5}{6})$ — same numbers by symmetry: $G_R=\frac{10}{36}\approx 0.2778$ Weighted split (each child holds $\frac{6}{12}=\frac{1}{2}$ of the data): $G_{\text{split}}=\frac{1}{2}(0.2778)+\frac{1}{2}(0.2778)=0.2778$ Gini gain: $0.5-0.2778=0.2222$ Answer: $G_{\text{split}}\approx 0.278$, gain $\approx 0.222$.

Both children are pure: $G_L=G_R=0$, so $G_{\text{split}}=\frac{4}{8}(0)+\frac{4}{8}(0)=0$. $\text{gain}=G_{\text{parent}}-G_{\text{split}}=0-0=0$ Answer: gain $=0$. There is no impurity to remove from an already-pure node, so no split can improve it. This is exactly why trees stop splitting pure leaves — a degenerate but crucial case.

Parent $p=(0.7,0.3)$: $G_{\text{parent}}=1-(0.49+0.09)=0.42$.

Split A — both children pure: $G_L=0,G_R=0\Rightarrow G_{\text{split,A}}=\frac{7}{10}(0)+\frac{3}{10}(0)=0$. Gain $=0.42-0=0.42$.

Split B: $G_L$ for $(\frac{5}{6},\frac{1}{6})$: $1-(\frac{25}{36}+\frac{1}{36})=\frac{10}{36}\approx 0.2778$. $G_R$ for $(\frac{1}{2},\frac{1}{2})$: $0.5$. $G_{\text{split,B}}=\frac{6}{10}(0.2778)+\frac{4}{10}(0.5)=0.1667+0.2=0.3667$. Gain $=0.42-0.3667=0.0533$.

Decision: Split A wins. Gain difference $=0.42-0.0533=0.3667$. A perfectly separating split ($G_{\text{split}}=0$) is unbeatable — it achieves the largest gain possible for any given parent.

Gini: $G=1-(0.81+0.01)=0.18$. Entropy: $H=-(0.9{\log }_{2}0.9+0.1{\log }_{2}0.1)=-(0.9(-0.152)+0.1(-3.322))=0.137+0.332=0.469$. So $G=0.18<H=0.469$. Both agree the node is fairly pure (well below their maxima of $0.5$ and $1.0$), but their scales differ. The takeaway: Gini and entropy are monotone friends — as one drops toward 0 the other does too — which is why they pick nearly the same splits. Gini just skips the $\log$, so it's cheaper.

Gains: C $\to 0.30-0.20=0.10$; D $\to 0.30-0.25=0.05$. Since both are compared against the same parent, the smaller $G_{\text{split}}$ does mean the larger gain — so C is better, the ranking is valid. The hidden assumption: both splits act on the same parent node. If C and D were evaluated on different parents (different $G_{\text{parent}}$), comparing raw $G_{\text{split}}$ values would be meaningless — only gain is comparable across parents. Within one node, minimizing $G_{\text{split}}$ = maximizing gain.

Gini is $G=1-\sum p_i^2$, so maximizing $G$ means minimizing $\sum p_i^2$ subject to $\sum p_i=1$. Why equal $p_i$ minimizes the sum of squares (the crucial step, justified): By the Cauchy–Schwarz / power-mean inequality, for any $K$ numbers with a fixed sum $\sum p_i=1$, ${\sum }_{i=1}^K{p}_i^2\ge \frac{{\left({\sum }_i{p}_i\right)}^2}{K}=\frac{1}{K},$ with equality iff all $p_i$ are equal (this is the QM–AM inequality: the quadratic mean is smallest exactly when all values coincide). So $\sum p_i^2$ bottoms out at $\frac{1}{K}$ precisely at the uniform distribution. Equivalently: any imbalance moves mass onto a larger $p_i$ whose square grows faster than the freed-up square shrinks, raising $\sum p_i^2$. Hence the minimizer of $\sum p_i^2$ — and therefore the maximizer of $G$ — is $p=(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4})$. $G_{\max }=1-4{\left(\frac{1}{4}\right)}^2=1-\frac{1}{4}=\frac{3}{4}=0.75$ This matches the general formula $G_{\max }=1-\frac{1}{K}=1-\frac{1}{4}=0.75$. Answer: uniform $p_i=0.25$, $G_{\max }=0.75$.

The data. Four items, class = $f_1\oplus f_2$ (XOR):

Classes A and B each appear twice, so parent $p=(0.5,0.5)$ and $G_{\text{parent}}=0.5$.

(a) Split on $f_1$ alone — zero gain.

• $f_1=0$ → items 1,2 = (A, B) → $p=(0.5,0.5)$, $G=0.5$.
• $f_1=1$ → items 3,4 = (B, A) → $p=(0.5,0.5)$, $G=0.5$. $G_{\text{split}}=\frac{1}{2}(0.5)+\frac{1}{2}(0.5)=0.5,\text{gain}=0.5-0.5=0.$ A greedy tree sees no improvement from $f_1$ and may refuse it. (By symmetry, splitting on $f_2$ alone is identical: also zero gain.)

(b) Two-step lookahead — perfect separation. Take the $f_1$ split anyway, then split each child on $f_2$:

• From $f_1=0$ child {1,2}: split on $f_2$ → $f_2=0$ gives {item 1 = A} (pure, $G=0$); $f_2=1$ gives {item 2 = B} (pure, $G=0$).
• From $f_1=1$ child {3,4}: split on $f_2$ → $f_2=0$ gives {item 3 = B} (pure, $G=0$); $f_2=1$ gives {item 4 = A} (pure, $G=0$).

All four leaves are pure, so the depth-2 tree classifies every item correctly — total impurity $0$. The single feature $f_1$ looked worthless in isolation, but $f_1$ together with $f_2$ is fully predictive.

Answer: single-feature gain $=0$ at both first steps, yet the depth-2 tree reaches $G=0$. Greedy Gini is blind to this feature interaction because it scores each split in isolation. This is the classic XOR problem; deeper trees, feature engineering, or Random Forests mitigate it.

Equal sizes → each weight is $0.5$. $G_{\text{split}}=0.5(0.30)+0.5G_R$ We want gain $=0.48-G_{\text{split}}=0.10\Rightarrow G_{\text{split}}=0.38$. $0.38=0.15+0.5G_R\Rightarrow 0.5G_R=0.23\Rightarrow G_R=0.46$ Answer: $G_R=0.46$.

Start from the definition with $p_1=p$, $p_2=1-p$: $G=1-\left(p^2+(1-p{)}^2\right)$ Expand $(1-p{)}^2=1-2p+p^2$: $G=1-\left(p^2+1-2p+p^2\right)=1-1+2p-2p^2=2p-2p^2=2p(1-p)$ This is a downward parabola in $p$. Its vertex is at $p=0.5$ (halfway between the roots $p=0$ and $p=1$), giving $G=2(0.5)(0.5)=0.5$. Proved: $G=2p(1-p)$, maximal $0.5$ at $p=0.5$. The figure below draws exactly this parabola and marks the two roots and the vertex. Read two things off it: (i) the curve is perfectly symmetric about $p=0.5$ — class 1 at $70\%$ and class 1 at $30\%$ give the same impurity, because "$70\%$ A" and "$70\%$ B" are the same mixed-ness; (ii) the slope is zero at the vertex, confirming $p=0.5$ is the maximum, and steepest near the pure ends, matching the sensitivity story from Ex. 1.3.

With $p_i=\frac{1}{K}$ for all $i$: $G=1-{\sum }_{i=1}^K{\left(\frac{1}{K}\right)}^2=1-K\cdot \frac{1}{K^2}=1-\frac{1}{K}$ As $K$ grows: $\frac{1}{K}\to 0$, so $G_{\max }=1-\frac{1}{K}\to 1$. Interpretation: with more equally likely classes you are almost always wrong when guessing by a random draw — the mistake probability climbs toward certainty (1) but never quite reaches it, because there's always a $\frac{1}{K}$ chance your random label happens to match. This is the ceiling Gini can approach but never touch.

Parent $p=(0.5,0.5)$: $G_{\text{parent}}=0.5$. Left $(\frac{3}{4},\frac{1}{4})$, 4 items: $G_L=1-(\frac{9}{16}+\frac{1}{16})=1-\frac{10}{16}=0.375$. Right $(0,1)$, 2 items: $G_R=1-(0+1)=0$. $G_{\text{split}}=\frac{4}{6}(0.375)+\frac{2}{6}(0)=0.25+0=0.25$ Then $G_{\text{split}}=0.25\le 0.5=G_{\text{parent}}$, so gain $=0.25\ge 0$. ✓ General principle: Gini is a concave function of the class proportions, and $G_{\text{parent}}$ equals Gini of the size-weighted mixture of the children's distributions. By Jensen's inequality, the impurity of the mixture is $\ge$ the weighted mixture of impurities: $G_{\text{parent}}\ge G_{\text{split}}$. A split's expected impurity never rises — which is exactly why greedy purity-chasing on training data terminates only at purity, and why we need Overfitting and Pruning to stop early.