Impurity Decrease and Conditional Risk

Uncertainty Within a Node

A classification tree assigns a prediction to each terminal cell. At a node, the population distribution of the labels determines how uncertain that prediction is and how much room there may be for improvement by splitting the node. Gini impurity and entropy summarize that uncertainty in different ways. The conditional classification risk answers a related but distinct question: what is the smallest probability of misclassification when one label must be predicted throughout the node?

Work with a finite label set $\{1,\ldots,K\}$, a feature vector $X$, and a class label $Y$. Let $A$ be a node with $P(X\in A)>0$. Its class probabilities are conditional on membership in that node. A candidate split divides $A$ into a finite collection of measurable child nodes $A_1,\ldots,A_J$, with positive conditional probabilities. All quantities below are population quantities; they are not estimated from a sample.

Definition: The class probabilities in node $A$ are $p_k=P(Y=k\mid X\in A)$, for $k=1,\ldots,K$. The node's Gini impurity and entropy are $$ G(A)=1-\sum_{k=1}^K p_k^2,\qquad H(A)=-\sum_{k=1}^K p_k\log p_k, $$ where $0\log 0$ is defined to be $0$. Entropy here uses the natural logarithm and is measured in nats.

Both measures are zero when a node contains only one class. They are larger when the class probabilities are more spread out. For example, if two classes each have probability $1/2$, then $G(A)=1/2$ and $H(A)=\log 2$. These numerical scales differ, so a Gini decrease and an entropy decrease should not be compared by their raw magnitudes.

Population Decrease Under a Split

Write $w_j=P(X\in A_j\mid X\in A)$ for the conditional weight of child $j$, and $p_{jk}=P(Y=k\mid X\in A_j)$ for its class probabilities. The parent probabilities are the weighted averages of the child probabilities:

p_k=\sum_{j=1}^J w_jp_{jk},\qquad \sum_{j=1}^Jw_j=1.

The population decrease in an impurity $I$ is the parent impurity minus the weighted average child impurity. Weighting matters: a small child should not count as much as a large child.

Definition: The population Gini decrease and entropy decrease for the split are $$ \Delta_G=G(A)-\sum_{j=1}^Jw_jG(A_j),\qquad \Delta_H=H(A)-\sum_{j=1}^Jw_jH(A_j). $$

Worked Gini Decrease

Worked Example: A Balanced Binary Split

Suppose a node has two classes, each with probability $0.5$. A candidate split has two equally likely children. In the first child the probabilities are $(0.8,0.2)$; in the second they are $(0.2,0.8)$. The parent probabilities are indeed the child average: $\tfrac12(0.8,0.2)+\tfrac12(0.2,0.8)=(0.5,0.5)$.

The parent Gini impurity is $1-(0.5^2+0.5^2)=0.5$. Each child has Gini impurity $1-(0.8^2+0.2^2)=1-(0.64+0.04)=0.32$. Thus the weighted child impurity is $\tfrac12(0.32)+\tfrac12(0.32)=0.32$, and the decrease is $0.5-0.32=0.18$.

For entropy, the parent value is $-2(0.5\log 0.5)=\log 2\approx0.693147$. Each child has entropy $-0.8\log 0.8-0.2\log 0.2\approx0.500402$. Therefore the entropy decrease is approximately $0.693147-0.500402=0.192745$ nats.

The split makes the children more class-concentrated, though the majority class changes from one child to the other. Both impurity decreases are positive.

Why Both Impurity Decreases Are Nonnegative

The Gini decrease has an exact expression in terms of how far each child's class-probability vector lies from the parent's. Let $p=(p_1,\ldots,p_K)$ and $p_j=(p_{j1},\ldots,p_{jK})$. The squared Euclidean norm is $\lVert v\rVert^2=\sum_k v_k^2$.

Theorem: For any finite split with positive child weights, $$ \Delta_G=\sum_{j=1}^Jw_j\lVert p_j-p\rVert^2\geq 0. $$ Equality holds exactly when every positive-weight child has the same class-probability vector as the parent.

Proof. Since $G(A)=1-\lVert p\rVert^2$, the definition of the decrease gives

\Delta_G =\sum_{j=1}^Jw_j\lVert p_j\rVert^2-\lVert p\rVert^2.

Expand the proposed weighted squared distance, use $\sum_jw_jp_j=p$, and use $\sum_jw_j=1$:

\begin{aligned} \sum_jw_j\lVert p_j-p\rVert^2 &=\sum_jw_j\bigl(\lVert p_j\rVert^2-2p_j^\mathsf{T}p+\lVert p\rVert^2\bigr)\\ &=\sum_jw_j\lVert p_j\rVert^2-2p^\mathsf{T}p+\lVert p\rVert^2\\ &=\sum_jw_j\lVert p_j\rVert^2-\lVert p\rVert^2 =\Delta_G. \end{aligned}

Every term $w_j\lVert p_j-p\rVert^2$ is nonnegative. With positive weights, their sum is zero exactly when every $p_j=p$. $\square$

Entropy has a parallel identity. For probability vectors $q,p$, define their Kullback–Leibler divergence by $D_{\mathrm{KL}}(q\Vert p)=\sum_{k:q_k>0}q_k\log(q_k/p_k)$. In the split identity below, if $p_k=0$, the mixture equation implies $p_{jk}=0$ for every positive-weight child, so no positive term involves division by zero.

Theorem: The population entropy decrease satisfies $$ \Delta_H=\sum_{j=1}^Jw_jD_{\mathrm{KL}}(p_j\Vert p)\geq0. $$

Proof. Expand the right-hand side and collect terms. The mixture identity $\sum_jw_jp_{jk}=p_k$ gives

\begin{aligned} \sum_jw_jD_{\mathrm{KL}}(p_j\Vert p) &=\sum_{j,k:p_{jk}>0}w_jp_{jk}\log p_{jk} -\sum_{k:p_k>0}\left(\sum_jw_jp_{jk}\right)\log p_k\\ &=-\sum_jw_jH(A_j)+\sum_kp_k\log p_k\\ &=H(A)-\sum_jw_jH(A_j)=\Delta_H. \end{aligned}

For nonnegativity, use $\log t\leq t-1$ for $t>0$. For any probability vectors $q,p$ with $q_k>0$ only where $p_k>0$,

D_{\mathrm{KL}}(q\Vert p) =-\sum_{k:q_k>0}q_k\log\frac{p_k}{q_k} \geq\sum_{k:q_k>0}q_k\left(1-\frac{p_k}{q_k}\right) =1-\sum_{k:q_k>0}p_k\geq0.

Equality holds only when $q=p$: equality in $\log t\leq t-1$ requires $p_k/q_k=1$ for each $q_k>0$, and equality in the final inequality requires no probability mass of $p$ outside that support. Applying this to each child proves the theorem. $\square$

Conditional Classification Risk

An impurity is a summary of class uncertainty, not itself the probability of classification error. If a single label must be predicted throughout a node, the best choice is a most probable class. The resulting nodewise Bayes risk is the conditional probability of error under that best constant prediction.

Definition: The conditional classification risk in node $A$, when prediction is constant within that node and loss is zero-one loss, is $$ R^*(A)=1-\max_{1\leq k\leq K}p_k. $$ For a split, the corresponding weighted child risk is $\sum_jw_jR^*(A_j)$, and the decrease in this risk is $R^*(A)-\sum_jw_jR^*(A_j)$.

A split cannot increase the best achievable population classification performance when each child may choose its own label. Indeed, the maximum of the child probabilities, averaged over children, is at least the maximum of their average. More explicitly:

Result: The conditional classification-risk decrease is nonnegative: $$ R^*(A)-\sum_jw_jR^*(A_j) =\sum_jw_j\max_k p_{jk}-\max_k p_k\geq0. $$

Proof. Choose a class $k^*$ attaining $\max_k p_k$; a maximum exists because there are finitely many classes. For every child, $\max_k p_{jk}\geq p_{jk^*}$. Therefore

\sum_jw_j\max_k p_{jk} \geq\sum_jw_jp_{jk^*} =p_{k^*} =\max_kp_k.

Subtracting $\max_kp_k$ proves the stated inequality. $\square$

Worked Example: Impurity Can Decrease Without Risk Decreasing

Worked Example: A Split With No Change in Best Classification Risk

Consider two equally likely classes? No: take three classes and two children with weights $w_1=0.25$ and $w_2=0.75$. Let their probability vectors be $p_1=(0.8,0.1,0.1)$ and $p_2=(0.6,0.2,0.2)$. The parent vector is $\,p=0.25p_1+0.75p_2=(0.65,0.175,0.175)$.

The parent Gini impurity is $1-(0.65^2+2(0.175^2))=1-(0.4225+0.06125)=0.51625$. The first child has Gini impurity $1-(0.64+0.01+0.01)=0.34$; the second has $1-(0.36+0.04+0.04)=0.56$. The weighted child impurity is $0.25(0.34)+0.75(0.56)=0.505$, so the decrease is $0.51625-0.505=0.01125$.

The parent and both children predict class 1. Their respective risks are $1-0.65=0.35$, $1-0.8=0.2$, and $1-0.6=0.4$. The weighted child risk is $0.25(0.2)+0.75(0.4)=0.35$, exactly the parent risk. Thus the split reduces Gini impurity but not the best constant-label misclassification risk.

Worked Example: Unequal Child Weights

Worked Example: A Binary Split With Zero Risk Decrease

A binary-class node has class-1 probability $0.6$, so its parent Gini impurity is $1-(0.6^2+0.4^2)=0.48$, entropy is $-0.6\log0.6-0.4\log0.4\approx0.673012$, and best constant-label risk is $0.4$.

Suppose a split creates a child of weight $0.25$ with class-1 probability $0.9$, and a child of weight $0.75$ with probability $0.5$. Their weighted class-1 probability is $0.25(0.9)+0.75(0.5)=0.225+0.375=0.6$, as required.

The child Gini values are $1-(0.9^2+0.1^2)=0.18$ and $1-(0.5^2+0.5^2)=0.5$. The weighted value is $0.25(0.18)+0.75(0.5)=0.045+0.375=0.42$, giving a Gini decrease of $0.48-0.42=0.06$.

The child entropies are $-0.9\log0.9-0.1\log0.1\approx0.325083$ and $\log2\approx0.693147$. The weighted child entropy is $0.25(0.325083)+0.75(0.693147)\approx0.601131$, so the entropy decrease is approximately $0.673012-0.601131=0.071881$ nats.

The child risks are $0.1$ and $0.5$, giving weighted risk $0.25(0.1)+0.75(0.5)=0.4$, unchanged from the parent. The majority class in each child is class 1, so the split makes the probabilities more concentrated but does not change the chosen label or its overall error.

Interpretation and a Common Pitfall

A positive population Gini or entropy decrease means that the child class distributions, on average, are more concentrated than the parent distribution. The identities above make this precise: Gini measures a weighted squared displacement of class probabilities, while entropy decrease is an average divergence from the parent distribution. The conditional risk decrease instead depends on the largest class probability in each node.

Common mistake: “The split reduces Gini impurity, so its misclassification risk must also decrease.” This does not follow. In the preceding examples, impurity decreases while weighted child Bayes risk stays the same. The correction is to calculate the two criteria separately: impurity evaluates the full class-probability vector, whereas zero-one risk for a constant node prediction depends only on its largest component. A split that does not change the best label can still improve impurity.

These population identities describe what a candidate split does under the true distribution. They do not guarantee that a sample-based estimate of the decrease is accurate, nor do they say that the split yields the best eventual tree. They provide a precise local interpretation of the criteria, separate from the question of how a tree search selects among candidate structures.

Check Your Understanding

Use the definitions and identities above to answer the following.

For a node with class probabilities $(0.7,0.3)$, calculate its Gini impurity, entropy, and conditional classification risk.
Why must parent class probabilities equal the child-weighted average of child probabilities?
State the weighted squared-distance identity for the Gini decrease and its equality condition.
What does the entropy-decrease identity imply about child class distributions when the decrease is zero?
Give the reason a split cannot increase the best achievable population classification risk when child-specific predictions are allowed.