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.
| Node | Samples (churn / stay) | Entropy in bits | Weight |
|---|---|---|---|
| Parent | 100 (40 / 60) | 0.971 | 1.00 |
| Monthly contract | 50 (35 / 15) | 0.881 | 0.50 |
| Annual contract | 50 (5 / 45) | 0.469 | 0.50 |
| Weighted children | 100 | 0.675 | Sum |
| Information gain | Not applicable | 0.296 | Result |
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.
| Algorithm | Splitting criterion | Handling of numeric features | Notable trait |
|---|---|---|---|
| ID3 | Raw information gain | Not supported natively | Multiway splits on categorical features |
| C4.5 | Gain ratio | Binary threshold search | Corrects bias toward many-valued features |
| CART | Gini impurity by default | Binary threshold search | Entropy available as an option |
| scikit-learn trees | Gini, entropy or log loss | Sorted threshold scan | Binary splits only |
| Gradient boosting trees | Loss reduction, not entropy | Histogram binning | Same greedy logic, different objective |
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 compared with related criteria
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.
| Criterion | What it measures | Range for two classes | Main strength | Main weakness |
|---|---|---|---|---|
| Information gain | Entropy reduction | 0 to 1 bit | Clear information-theoretic meaning | Favors many-valued features |
| Gain ratio | Gain divided by split information | 0 to about 1 | Penalizes fragmenting splits | Unstable when split information is near 0 |
| Gini impurity decrease | Reduction in misclassification probability | 0 to 0.5 | No logarithm, slightly faster | Less sensitive to small probability changes |
| Chi-squared statistic | Dependence between feature and label | 0 upward | Gives a significance test | Needs adequate expected counts |
| Variance reduction | Drop in target variance | 0 upward | Works for regression targets | Not defined for classes |
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.
| Situation | Recommended choice | Reason |
|---|---|---|
| Single interpretable tree | Entropy or Gini with pruning | Results are similar; pruning controls overfitting |
| Many categorical levels | Gain ratio or target encoding | Reduces cardinality bias |
| Text classification with sparse terms | Information gain as a filter | Fast univariate ranking of thousands of terms |
| Strongly interacting features | Wrapper or embedded selection | Univariate gain misses joint effects |
| Continuous target | Variance reduction | Entropy is defined for discrete labels |
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.