Entropy and information gain

Entropy measures the average amount of uncertainty or 'surprise' in a random variable's outcomes. The higher the entropy, the less predictable the outcome is, and the more information is needed on average to describe it. It is maximized when all outcomes are equally likely.

The entropy is H = -p·log2(p) - (1-p)·log2(1-p). It uses base-2 logarithms so the result is measured in bits. This reaches its maximum value of 1 bit when p = 0.5.

import math
def entropy(p):
    if p in (0,1): return 0.0
    return -p*math.log2(p) - (1-p)*math.log2(1-p)
print(entropy(0.5))  # 1.0

The maximum entropy of a binary variable is 1 bit, and it occurs when both outcomes are equally likely (p = 0.5). At this point uncertainty is highest because neither outcome can be predicted better than a coin flip.

The entropy is 0, because there is no uncertainty—every example has the same label. A pure node provides complete predictability, which is the ideal outcome of a decision tree split.

Information gain is the reduction in entropy achieved by splitting a dataset on a particular feature. It equals the entropy of the parent node minus the weighted average entropy of the child nodes. Decision trees choose splits that maximize information gain.

Information Gain = H(parent) - Σ (n_child / n_parent) · H(child), where the sum is over all child nodes. The child entropies are weighted by the fraction of samples that fall into each child. A larger gain means a more useful split.

The feature with the highest information gain reduces uncertainty the most, producing the purest child nodes. This leads to a tree that separates the classes more effectively with fewer splits, improving predictive accuracy and interpretability.

Gini impurity measures the probability of misclassifying a randomly chosen element if it were labeled according to the class distribution: Gini = 1 - Σ p_i². Like entropy, it is 0 for pure nodes, but it is computationally cheaper because it avoids logarithms. Both are common splitting criteria in decision trees.

With p = 0.5 for each class, entropy = -0.5·log2(0.5) - 0.5·log2(0.5) = 0.5 + 0.5 = 1 bit. This is the maximum possible entropy for a binary node because the classes are perfectly balanced.

H(X) = -Σ (i=1 to k) p_i · log2(p_i), where p_i is the probability of class i. The sum runs over all possible classes, and any class with probability 0 contributes 0 to the sum.

The maximum entropy is log2(k) bits, achieved when all k outcomes have equal probability 1/k. For example, a fair die with 6 faces has entropy log2(6) ≈ 2.585 bits.

ID3 uses information gain, based on Shannon entropy, to select the attribute that best splits the data at each node. It greedily chooses the attribute with the highest information gain until nodes become pure or no attributes remain.

Information gain is biased toward features with many distinct values (high cardinality), because splitting into many small, nearly pure groups artificially inflates the gain. The gain ratio, used in C4.5, fixes this by dividing information gain by the split's intrinsic information (split information).

Gain Ratio = Information Gain / Split Information, where Split Information is the entropy of the distribution of samples across the split's branches. Dividing by split information penalizes splits that create many branches, correcting the bias of plain information gain.

Base 2 is used so that entropy is measured in bits, which represent the average number of yes/no (binary) questions needed to identify an outcome. Other bases are valid too: natural log gives 'nats' and base 10 gives 'dits/hartleys'.

With p(Yes) = 9/14 ≈ 0.643 and p(No) = 5/14 ≈ 0.357, entropy = -0.643·log2(0.643) - 0.357·log2(0.357) ≈ 0.940 bits. This classic example comes from the 'Play Tennis' dataset.

import math
p=9/14; q=5/14
print(-p*math.log2(p)-q*math.log2(q))  # ~0.940

An information gain of 0 means the split does not reduce entropy at all—the class distribution in the children is the same as in the parent. The feature provides no useful information for separating the classes, so the tree would not benefit from this split.

Conditional entropy H(Y|X) is the average uncertainty remaining about Y after observing X. It equals the weighted sum of the entropies of Y within each value of X. Information gain about Y from X is exactly H(Y) - H(Y|X).

Information gain between a feature X and target Y is mathematically identical to the mutual information I(X;Y) = H(Y) - H(Y|X). It quantifies how many bits of uncertainty about Y are eliminated by knowing X. Mutual information is symmetric: I(X;Y) = I(Y;X).

No, Shannon entropy is always non-negative because each term -p·log2(p) is ≥ 0 for probabilities between 0 and 1. The minimum value is 0, occurring when one outcome is certain. (Differential entropy of continuous variables can be negative, but discrete Shannon entropy cannot.)

Setting the parameter criterion='entropy' makes the tree use information gain (based on Shannon entropy) to choose splits. The default is criterion='gini', which uses Gini impurity instead. There is also 'log_loss' for entropy-equivalent behavior.

from sklearn.tree import DecisionTreeClassifier
clf = DecisionTreeClassifier(criterion='entropy')

Weighted child entropy = (4/8)·0 + (4/8)·1 = 0.5. Information gain = parent entropy - weighted child entropy = 1 - 0.5 = 0.5 bits. The split removed half a bit of uncertainty.

For 6 equally likely outcomes, entropy = log2(6) ≈ 2.585 bits. This represents the average number of yes/no questions needed to determine the outcome of a single roll.

import math
print(math.log2(6))  # 2.585

Entropy is defined over discrete class probabilities, capturing how mixed the class labels are—ideal for classification. Regression targets are continuous, so trees instead use measures like variance or mean squared error reduction, which quantify spread of numeric values rather than label mixing.

As the distribution becomes more skewed toward one class, entropy decreases toward 0. Less mixing means less uncertainty—if one class has probability near 1, outcomes are almost perfectly predictable.

An event that is certain (probability 1) carries 0 bits of information, since -log2(1) = 0. There is no surprise in something guaranteed to happen, so it conveys no new information.

Self-information is I = -log2(p) bits. Rarer events (smaller p) have higher self-information because they are more surprising; an event with p = 1/8 carries 3 bits of information.

Entropy is the expected (average) value of self-information across all outcomes: H = Σ p_i · (-log2 p_i). In other words, it is the average surprise you expect when sampling from the distribution. This is why high-entropy distributions feel unpredictable.

It picks the split with the higher information gain (equivalently, the lowest weighted child entropy). This greedily produces the purest immediate children, even though greedy choices do not always yield a globally optimal tree.

Cross-entropy H(p,q) = -Σ p_i·log(q_i) compares a true distribution p against a predicted distribution q. It is widely used as a loss function for classification, where minimizing it pushes the predicted probabilities closer to the true labels.

Cross-entropy H(p,q) = H(p) + KL(p‖q), where H(p) is the entropy of the true distribution and KL(p‖q) is the Kullback-Leibler divergence. Since H(p) is fixed for given data, minimizing cross-entropy is equivalent to minimizing the KL divergence between predictions and truth.

Feature B is the better split because it has higher information gain (0.40 > 0.25), meaning it reduces the entropy of the target more. A decision tree would choose B at this node to create purer children.

The function computes parent entropy, then the weighted entropy of the two subsets defined by the mask, and returns the difference. Using numpy makes counting class proportions concise. The returned value is the information gain in bits.

import numpy as np
def entropy(y):
    _,c=np.unique(y,return_counts=True); p=c/c.sum()
    return -(p*np.log2(p)).sum()
def info_gain(y, mask):
    n=len(y); l,r=y[mask],y[~mask]
    child=(len(l)/n)*entropy(l)+(len(r)/n)*entropy(r)
    return entropy(y)-child

Greedily maximizing information gain keeps splitting until nodes are pure, which can create very deep trees that memorize noise and quirks of the training data. Such trees fit training data perfectly but generalize poorly, so techniques like pruning, max_depth, or min_samples_leaf are used to limit growth.