Information gain

On this page 8

Information gain is the reduction in entropy of a target variable that results from partitioning a dataset on the value of a feature. In machine learning, it is the classic splitting criterion for decision trees: at each node, the algorithm evaluates candidate features or thresholds and selects the one whose split leaves the child nodes most pure with respect to the class labels.

The measure comes from information theory, where entropy quantifies uncertainty in bits. Information gain is mathematically identical to the mutual information between a feature and the label, estimated on the training sample at a node, which is why it also appears in feature selection and in active learning outside of tree induction.

How information gain is calculated

Information gain is calculated as the entropy of the parent node minus the weighted average entropy of the child nodes. Entropy for a node with class proportions p1 to pk is H = -sum of pi log2 pi, so a pure node has entropy of 0 bits and a perfectly balanced binary node has entropy of 1 bit.

For a split that sends n1 of n samples left and n2 right, the formula is IG = H(parent) – (n1/n) H(left) – (n2/n) H(right). The weighting by sample share matters: a tiny child node that happens to be pure contributes little, because it covers only a small fraction of the data. The gain is always non-negative on the training sample, since splitting never increases weighted entropy.

The following worked calculation shows each step for a binary churn dataset of 100 customers, 40 of whom churned, split on whether the contract is monthly.

NodeSamples (churn / stay)Entropy in bitsWeight
Parent100 (40 / 60)0.9711.00
Monthly contract50 (35 / 15)0.8810.50
Annual contract50 (5 / 45)0.4690.50
Weighted children1000.675Sum
Information gainNot applicable0.296Result
Worked calculation of information gain for one split

The split removes roughly 0.30 bits of uncertainty per sample. The algorithm repeats this computation for every candidate split and keeps the highest-scoring feature and threshold.

Information gain in decision tree algorithms

Information gain drives greedy, top-down tree induction, in which each node chooses the locally best split without looking ahead. The criterion is applied recursively until a stopping rule fires, such as a maximum depth, a minimum number of samples per leaf or a gain below a threshold.

Different algorithm families apply the idea in different forms, and the table summarizes the most common ones.

AlgorithmSplitting criterionHandling of numeric featuresNotable trait
ID3Raw information gainNot supported nativelyMultiway splits on categorical features
C4.5Gain ratioBinary threshold searchCorrects bias toward many-valued features
CARTGini impurity by defaultBinary threshold searchEntropy available as an option
scikit-learn treesGini, entropy or log lossSorted threshold scanBinary splits only
Gradient boosting treesLoss reduction, not entropyHistogram binningSame greedy logic, different objective
How major tree algorithms use information gain

For numeric features, the algorithm sorts the values and tests thresholds between adjacent distinct values, which costs O(n log n) per feature per node. Histogram-based implementations approximate this with a few hundred bins to scale to millions of rows.

Information gain is one of several impurity-based splitting criteria, and in practice it produces trees very similar to those grown with Gini impurity. Differences appear mainly in edge cases, in computational cost and in how each criterion treats features with many distinct values.

CriterionWhat it measuresRange for two classesMain strengthMain weakness
Information gainEntropy reduction0 to 1 bitClear information-theoretic meaningFavors many-valued features
Gain ratioGain divided by split information0 to about 1Penalizes fragmenting splitsUnstable when split information is near 0
Gini impurity decreaseReduction in misclassification probability0 to 0.5No logarithm, slightly fasterLess sensitive to small probability changes
Chi-squared statisticDependence between feature and label0 upwardGives a significance testNeeds adequate expected counts
Variance reductionDrop in target variance0 upwardWorks for regression targetsNot defined for classes
Comparison of splitting and relevance criteria

Empirical studies consistently find that entropy and Gini disagree on only a small fraction of splits, so the choice rarely changes accuracy. The more consequential decision is whether to correct for cardinality bias with gain ratio or with a pruning strategy.

Bias toward high-cardinality features

Raw information gain is systematically biased toward features with many distinct values. A feature such as a customer ID splits the data into one sample per branch, every child becomes pure, and the gain equals the full parent entropy even though the feature has no predictive value on new data.

C4.5 addresses this with the gain ratio, which divides information gain by the split information, the entropy of the partition sizes themselves. Many-way splits have high split information, so their ratio drops. Binary-only implementations reduce the problem but do not eliminate it, because a numeric or high-cardinality feature offers more candidate thresholds and therefore more chances to find a spuriously good split.

  • Use gain ratio or conditional inference trees when categorical features differ widely in cardinality.
  • Remove identifier-like columns such as row numbers, timestamps used as keys and free-text codes before training.
  • Prefer permutation importance over impurity-based feature importance when reporting which features matter.

Using information gain in practice

Information gain is used both inside tree learners and as a standalone filter for feature selection, where each feature is scored against the label and the top-ranked ones are kept. The table maps common situations to recommended choices.

SituationRecommended choiceReason
Single interpretable treeEntropy or Gini with pruningResults are similar; pruning controls overfitting
Many categorical levelsGain ratio or target encodingReduces cardinality bias
Text classification with sparse termsInformation gain as a filterFast univariate ranking of thousands of terms
Strongly interacting featuresWrapper or embedded selectionUnivariate gain misses joint effects
Continuous targetVariance reductionEntropy is defined for discrete labels
Decision guide for applying information gain

When used as a filter, information gain is univariate: it scores each feature in isolation. Two features that are individually uninformative but jointly predictive, as in an XOR pattern, both receive near-zero gain, which is the main reason filter methods are paired with model-based checks.

Limitations and common mistakes

The most frequent error is treating high training-set gain as evidence of generalization. Deep trees keep finding positive gain on smaller and smaller nodes, which is a direct route to overfitting unless depth, leaf size or cost-complexity pruning constrains growth.

  • Estimating entropy on very small nodes gives noisy values, so a minimum leaf size of 5 to 50 samples is common.
  • Information gain on imbalanced classes can favor splits that isolate the majority class; class weights adjust the proportions used in entropy.
  • Discretizing numeric features before computing gain can hide the best threshold.
  • Reading impurity-based feature importance as causal influence confuses association with cause.

Put simply

Information gain answers a simple question: how much does asking this one question clear things up? Imagine sorting a mixed pile of apples and oranges. Asking whether a fruit is orange in color separates the pile almost perfectly, so that question has high information gain. Asking whether the fruit weighs more than 50 grams barely helps, so its gain is low.

A decision tree plays this guessing game automatically. At each step it tries every available question and picks the one that makes the groups tidiest. The catch is that a question with very many possible answers can look helpful only because it chops the data into tiny pieces.

In practice

A data analyst at a regional telecom operator builds a churn model on 120,000 customer records with 30 features. Before fitting a gradient boosting model, the analyst ranks features by information gain against the churn label. Contract type scores 0.21 bits, monthly charges 0.09 bits and support calls 0.07 bits, while a store branch code with 400 values scores suspiciously high at 0.18 bits.

Switching to gain ratio drops the branch code to the bottom of the list, confirming that its score came from cardinality bias rather than real signal. The analyst removes it, fits a depth-5 decision tree with an entropy criterion for an interpretable summary, and presents the top three splits to the retention team. The final model shows validation AUC unchanged after dropping the branch code, with a simpler and more stable feature set.