Entropy and Information Gain

Entropy is a measure of the average uncertainty, or "surprise," in a random variable's distribution. For a discrete label $Y$ taking values in $\{1, \dots, K\}$ with probabilities $p_1, \dots, p_K$ (estimated from class frequencies in a dataset $S$), the Shannon entropy is

with the convention $0 \log_2 0 = 0$. Entropy is measured in bits when using $\log_2$. It is exactly $0$ when one class has probability $1$ (perfectly pure, no uncertainty) and it is maximized at $\log_2 K$ when all classes are equally likely (maximum uncertainty). For binary classification ($K=2$), $H(S) \in [0, 1]$, peaking at $p=0.5$.

Information gain (IG) measures how much splitting a dataset $S$ on a feature (or feature/threshold pair) $A$ reduces this uncertainty. If the split partitions $S$ into subsets $S_1, \dots, S_m$ (e.g., $m=2$ for a binary threshold split, or $m = |\text{values}(A)|$ for a categorical split), then

The second term is the weighted average entropy of the children, sometimes called the conditional entropy $H(Y \mid A)$. Information gain is therefore literally the mutual information between the label $Y$ and the split variable $A$: $IG(S,A) = H(Y) - H(Y\mid A) = I(Y; A) \ge 0$, with equality only when $A$ is independent of $Y$ within $S$. Non-negativity of information gain is not an accident — it follows from the concavity of the entropy function (Jensen's inequality), so a split can never increase expected uncertainty about $Y$ on average.

Gini impurity is an alternative impurity measure used by CART:

It can be interpreted as the expected error rate if you labeled a randomly drawn example from $S$ according to the label distribution itself (i.e., predicting class $k$ with probability $p_k$ and being wrong with probability $1-p_k$). Like entropy, Gini impurity is $0$ for a pure node and maximized when classes are balanced. The corresponding split-quality score, the Gini gain, is defined analogously to information gain:

Both entropy and Gini are special cases of a broader family of impurity functions — concave functions of $p$ that vanish at the vertices of the probability simplex ($p_k=1$ for some $k$) and peak at the uniform distribution. This shared shape is exactly why they tend to prefer similar splits in practice, even though their numeric values and derivatives differ.

Building a tree with an impurity-based criterion is a greedy, recursive procedure. At each node, the algorithm searches over all candidate features and (for continuous features) all candidate thresholds, computes the information gain (or Gini gain) for each candidate split, and commits to the single best one — without ever reconsidering that choice later. This is what makes tree induction fast: it never explores the combinatorially many possible trees, only a sequence of locally optimal decisions. ```text function ENTROPY(S):

# S: multiset of class labels n = |S| if n == 0: return 0 H = 0 for each class k present in S: p_k = count(S, k) / n H -= p_k log2(p_k) return H function GINI(S): n = |S| if n == 0: return 0 G = 1 for each class k present in S: p_k = count(S, k) / n G -= p_k p_k return G function BEST_SPLIT(S, features, criterion=ENTROPY): H_parent = criterion(S) best_gain = -infinity best_split = None for A in features: candidate_thresholds = CANDIDATE_THRESHOLDS(S, A) for t in candidate_thresholds: S_left = { x in S : x[A] <= t } S_right = { x in S : x[A] > t } if |S_left| == 0 or |S_right| == 0: continue # degenerate split, skip weighted = (|S_left| / |S|) criterion(S_left) + (|S_right| / |S|) criterion(S_right) gain = H_parent - weighted if gain > best_gain: best_gain = gain best_split = (A, t, S_left, S_right) return best_split, best_gain function BUILD_TREE(S, features, max_depth, depth=0): if ENTROPY(S) == 0 or depth == max_depth or |features| == 0: return LEAF(majority_class(S)) # base case: pure or exhausted split, gain = BEST_SPLIT(S, features) if split == None or gain <= 0: return LEAF(majority_class(S)) # no useful split found (A, t, S_left, S_right) = split left_child = BUILD_TREE(S_left, features, max_depth, depth+1) right_child = BUILD_TREE(S_right, features, max_depth, depth+1) return NODE(test = (A <= t), left_child, right_child) ``` `CANDIDATE_THRESHOLDS` sorts the distinct values of feature $A$ observed in $S$ and considers midpoints between consecutive distinct values where the class label changes — a standard optimization, since the impurity can only improve at a boundary between differently-labeled adjacent points, so it never helps to place a threshold strictly inside a run of same-label points. For a categorical feature, either every subset of categories is tried (small cardinality) or, more commonly, a per-value one-vs-rest split is used. The recursion terminates because each recursive call operates on a strictly smaller subset (`S_left` and `S_right` are proper, non-empty subsets of `S` whenever a split is accepted), and depth is capped, so the tree has finite depth and every branch reaches a base case.

Time complexity. Let $n = |S|$ be the number of examples at a node and $d$ the number of features. Computing entropy or Gini for one candidate split requires a pass over class counts, which can be maintained incrementally: sort the $n$ values of a continuous feature once ($O(n \log n)$), then sweep left-to-right, updating running class counts in $O(1)$ per boundary and recomputing the two impurities in $O(K)$ per threshold, where $K$ is the number of classes. This gives $O(n \log n + nK)$ per feature per node, so $O(d \cdot n \log n)$ per node when sorting dominates (typical for $K \ll n$). Across a full tree of depth $D$, since the total number of examples summed across all nodes at one depth level is $O(n)$ (each example lives in exactly one node per level), the total cost is

in the (common) balanced case, and $O(n \cdot d \cdot n \log n) = O(d\, n^2 \log n)$ in the worst case of a maximally unbalanced tree with $D = O(n)$. Sorting can be done once per feature at the root and maintained via indices during partitioning, avoiding repeated full sorts — a standard implementation optimization in libraries like scikit-learn and CART, bringing the typical practical cost close to $O(d\, n \log n)$ total amortized in balanced trees. Space complexity is $O(n)$ per feature to hold sorted indices, plus $O(K)$ for running counts, so $O(nd)$ overall for a naive implementation, or $O(n)$ if features are processed one at a time and released.

Correctness of the greedy criterion. There is no claim that maximizing information gain at each node yields the globally optimal decision tree (finding the optimal tree of bounded size is NP-hard in general). What can be proven is narrower and more useful: information gain is a sound local measure of split quality, in the sense that 1. $IG(S,A) \ge 0$ always. Proof sketch: entropy is a strictly concave function of the probability vector $p$. By Jensen's inequality, for any partition of $S$ into $S_1,\dots,S_m$ with weights $w_j = |S_j|/|S|$ and label distributions $p^{(j)}$ satisfying $p = \sum_j w_j p^{(j)}$ (law of total probability),

which rearranges to $IG(S,A) = H(S) - \sum_j w_j H(S_j) \ge 0$. So splitting can never increase expected uncertainty about $Y$ — a split is informative or, at worst, neutral, never harmful in expectation. 2. $IG(S,A) = 0$ if and only if $A$ is (empirically) independent of $Y$ within $S$ — that is, the class distribution is identical in every child. This matches intuition: a split that doesn't change the label distribution anywhere provides no information. 3. Gini gain satisfies the same two properties, by the identical Jensen's-inequality argument applied to the concave function $G(p) = 1 - \sum_k p_k^2$. So the greedy algorithm is correct in the sense that it always makes locally non-harmful, information-theoretically justified choices, and it is a standard, well-studied heuristic for the (NP-hard) combinatorial problem of finding a small, accurate tree — analogous to how greedy heuristics are used for other NP-hard problems where exhaustive search is infeasible. The tradeoff is that greediness with no lookahead can miss splits that only pay off two levels down (the classic XOR problem: neither single feature reduces impurity alone, but their combination perfectly separates the classes). This limitation, and the tendency of unconstrained greedy growth to overfit training noise, motivates the pruning and depth-control techniques covered in Tree Pruning and Complexity Control.

Entropy vs. Gini — a practical note. Both are concave, both vanish at pure nodes, both peak at the uniform distribution — but they are not identical curves. For binary classification with $p$ the probability of the positive class:

Entropy is somewhat more sensitive near the extremes (it penalizes small impurities more sharply due to the logarithm), while Gini is computationally cheaper (no logarithms) and is what CART uses by default. Empirically, trees built with either criterion tend to agree on splits over 90% of the time in practice; disagreements are rare and rarely matter for final accuracy, though entropy-based gain has the additional bias problem addressed by gain ratio, discussed below.

Consider a tiny "Play Tennis" dataset with 14 examples and a binary label (Play = Yes/No), split on the categorical feature Outlook with values Sunny, Overcast, Rain.

Step 1 — Parent entropy.

Step 2 — Entropy of each child. Sunny (2 Yes, 3 No; $p=0.4, 0.6$):

Overcast (4 Yes, 0 No; pure):

Rain (3 Yes, 2 No; $p=0.6, 0.4$):

Step 3 — Weighted child entropy.

Step 4 — Information gain.

Step 5 — Compare against another candidate feature, say Wind (Weak/Strong):

Since $0.246 > 0.048$, the algorithm chooses Outlook as the root split, because it produces far more purity reduction — the Overcast branch becomes an immediate pure leaf (all "Yes"), while Wind leaves both children substantially mixed. This matches the classic ID3 worked trace and illustrates exactly why greedy IG-maximization is a reasonable, checkable procedure: at every candidate, you can hand-verify the arithmetic and confirm the algorithm's choice is the one that locally destroys the most uncertainty.

Gini cross-check. Using Gini impurity instead: $G(S) = 1 - (0.643^2 + 0.357^2) = 0.459$. For Outlook, $G(\text{Sunny}) = 1-(0.4^2+0.6^2) = 0.48$, $G(\text{Overcast}) = 0$, $G(\text{Rain}) = 0.48$, giving weighted Gini $= \frac{5}{14}(0.48)+0+\frac{5}{14}(0.48) = 0.343$, so $\Delta G = 0.459-0.343=0.116$. For Wind: $G(\text{Weak})=1-(0.75^2+0.25^2)=0.375$, $G(\text{Strong})=1-(0.5^2+0.5^2)=0.5$, weighted $=\frac{8}{14}(0.375)+\frac{6}{14}(0.5)=0.4286$, so $\Delta G = 0.459-0.4286=0.0304$. Gini agrees: Outlook again wins decisively over Wind, confirming the two criteria give the same qualitative split decision here.

Quinlan's ID3 was built directly on Shannon's entropy formula, treating each feature test as a "question" whose expected information value could be computed exactly the way Shannon computed channel capacity. Breiman and colleagues, working independently in statistics, arrived at Gini impurity via a different route — minimizing expected misclassification cost under a two-class Bayes-error argument — yet the resulting splits so closely resemble entropy-based ones that both criteria remain standard, interchangeable defaults in modern libraries.

Every major tree-based library implements exactly this machinery: scikit-learn's `DecisionTreeClassifier` exposes `criterion='gini'` or `'entropy'` directly as a parameter, and both XGBoost and LightGBM use closely related (though second-order, loss-derivative-based) impurity surrogates when growing each boosting-round tree. Random forests, used in genomics for gene-expression classification and in finance for credit-risk scoring, build hundreds of such trees, each one repeatedly invoking information-gain or Gini-gain computations at every node. Medical decision-support tools favor entropy/Gini-based trees specifically because the splits are human-readable ("if age > 50 and troponin > threshold..."), unlike black-box neural models — auditability is a first-class requirement in clinical and regulatory settings. Feature-selection pipelines also borrow information gain directly (independent of any tree) as a fast univariate filter to rank candidate predictors before more expensive modeling. Finally, this same entropy-reduction logic generalizes to mutual-information feature selection in NLP and to impurity-based feature importance scores reported by every scikit-learn or ranger (R) random forest, making entropy and Gini impurity two of the most-invoked formulas in applied machine learning, even when practitioners never see the word "entropy" in the API they call.

Ask the tutor: How does the entropy-based information gain criterion change when the target variable is continuous, as in regression trees?