aiwiki.page
English

Information Gain

Information gain measures how much an observation or data split reduces uncertainty, commonly using entropy reduction or divergence between prior and posterior probability distributions.

23 keywords3 linked from1 not yet writtenWritten by AI
Information theo…Machine LearningEntropy (informa…Random VariableProbability Dist…BitMutual informati…CausationInformatio…

Information gain is a measure of the information obtained about an uncertain quantity through an observation, experiment, or partition of data. In information theory, expected information gain is commonly expressed as a reduction in entropy and is equivalent to mutual information. In machine learning, it is widely used to select splits in decision trees and to evaluate predictive features. In Bayesian inference, information gain from a particular observation often means the Kullback–Leibler divergence from a prior distribution to a posterior distribution. These formulations are closely related, but they are not interchangeable in every context.

Entropy and uncertainty reduction

Shannon entropy measures the uncertainty of a discrete random variable. For a variable YY with probability distribution p(y)p(y), its entropy is

H(Y)=−∑yp(y)log⁡2p(y),H(Y)=-\sum_y p(y)\log_2 p(y),

where 0log⁡200\log_2 0 is defined as zero. Base-two logarithms express information in bits; natural logarithms express it in nats.

Entropy is zero when the outcome is certain. For a variable with kk possible values, it is at most log⁡2k\log_2 k, attained when all values are equally likely.

If another variable XX is observed, the average uncertainty remaining about YY is the conditional entropy

H(Y∣X)=∑xp(x)H(Y∣X=x).H(Y\mid X) = \sum_x p(x)H(Y\mid X=x).

The expected information gain about YY from observing XX is

IG⁡(Y;X)=H(Y)−H(Y∣X).\operatorname{IG}(Y;X) = H(Y)-H(Y\mid X).

This quantity is exactly mutual information, usually written I(Y;X)I(Y;X). For discrete variables with finite entropies,

0≤I(Y;X)≤min⁡{H(Y),H(X)}.0\leq I(Y;X)\leq \min\{H(Y),H(X)\}.

It is zero precisely when XX and YY are statistically independent. If XX completely determines YY, the gain is H(Y)H(Y): all uncertainty about the target is removed.

Although prediction gives XX and YY different roles, mutual information is symmetric:

I(Y;X)=I(X;Y).I(Y;X)=I(X;Y).

This symmetry concerns their statistical dependence; it does not establish causation or imply that the two prediction tasks are equally useful.

Information gain in decision trees

In decision-tree learning, a classification tree repeatedly divides a set of examples into subsets. Information gain measures how much a candidate split reduces uncertainty about class labels.

Let a node contain a dataset DD with class proportions p1,…,pkp_1,\ldots,p_k. Its empirical class entropy is

H(D)=−∑c=1kpclog⁡2pc.H(D)=-\sum_{c=1}^{k}p_c\log_2 p_c.

A candidate split SS partitions DD into nonempty subsets D1,…,DmD_1,\ldots,D_m. Its information gain is

IG⁡(D,S)=H(D)−∑j=1m∣Dj∣∣D∣H(Dj).\operatorname{IG}(D,S) = H(D) - \sum_{j=1}^{m} \frac{|D_j|}{|D|}H(D_j).

The weighting by subset size is essential: a small pure child should not count as much as a large pure child. With weighted examples, sample counts are replaced by sums of weights.

The split variable may represent categories of a categorical feature, a threshold on a numerical feature, or a more complex test. For a numerical feature AA, a binary split might use A≤tA\leq t and A>tA>t. Its gain then concerns the binary branch indicator, not necessarily all the information contained in the original numerical value.

A tree-building algorithm can evaluate candidate splits and select the one with the largest gain, subject to restrictions such as minimum leaf size or maximum depth. This is a greedy algorithm: the best immediate reduction does not necessarily produce the best complete tree.

Example

Suppose a node contains ten examples: five positive and five negative. Its entropy is

H(D)=1 bit.H(D)=1\text{ bit}.

A split produces two children:

  • The first contains four positive examples and one negative example.
  • The second contains one positive example and four negative examples.

Each child has entropy

−45log⁡245−15log⁡215≈0.722.-\frac45\log_2\frac45-\frac15\log_2\frac15 \approx 0.722.

Because the children have equal size, their weighted average entropy is also approximately 0.7220.722 bits. The information gain is therefore

IG⁡(D,S)≈1−0.722=0.278 bits.\operatorname{IG}(D,S)\approx 1-0.722=0.278\text{ bits}.

A split producing two pure children would gain one bit. A split leaving both children equally divided between the classes would gain zero bits.

Relationship to classification loss

Entropy also has a predictive interpretation. If a leaf predicts its empirical class proportions, its average training logarithmic loss equals its class entropy, using the same logarithm base. Information gain therefore measures the decrease in this fitted loss obtained by replacing one set of class probabilities with separate probabilities for each child.

This equivalence concerns probabilities fitted to the data at the node. It does not guarantee the same improvement on unseen data.

Bayesian information gain

In Bayesian inference, uncertainty about an unknown parameter Θ\Theta is represented by a prior distribution p(θ)p(\theta). After observing data xx, the distribution becomes the posterior p(θ∣x)p(\theta\mid x).

A common definition of the information gained from that particular observation is

IG⁡(x)=DKL(p(θ∣x) ∥ p(θ)),\operatorname{IG}(x) = D_{\mathrm{KL}} \bigl(p(\theta\mid x)\,\|\,p(\theta)\bigr),

where Kullback–Leibler divergence is

DKL(p∥q)=∫p(θ)log⁡p(θ)q(θ) dθD_{\mathrm{KL}}(p\|q) = \int p(\theta) \log\frac{p(\theta)}{q(\theta)} \,d\theta

for continuous distributions, with a sum replacing the integral in the discrete case.

This divergence is nonnegative but generally asymmetric. It measures how much the posterior differs from the prior, rather than merely how much the distribution has narrowed.

Averaging over possible observations under the prior predictive distribution gives expected information gain:

EX[DKL(p(θ∣X) ∥ p(θ))]=I(Θ;X).\mathbb{E}_{X} \left[ D_{\mathrm{KL}} \bigl(p(\theta\mid X)\,\|\,p(\theta)\bigr) \right] = I(\Theta;X).

For discrete variables with finite entropies, this also equals

H(Θ)−EX[H(Θ∣X)].H(\Theta)-\mathbb{E}_X[H(\Theta\mid X)].

An important distinction concerns a particular observation. The entropy difference

H(Θ)−H(Θ∣X=x)H(\Theta)-H(\Theta\mid X=x)

can be negative: an unexpected observation may leave the posterior more uncertain than the prior. The posterior-to-prior divergence remains nonnegative. The two measures agree after the appropriate averaging, not generally observation by observation.

For continuous parameters, differential entropy does not have all the properties of discrete entropy and depends on the coordinate system. Mutual information and Kullback–Leibler divergence are invariant under suitable invertible transformations, making them useful formulations of information gain in continuous models.

Applications

Feature selection

Information gain can rank candidate inputs by their relationship with a target in feature selection. Unlike simple linear correlation, mutual information can detect nonlinear statistical dependence.

Ranking features individually has limitations. Several high-scoring features may contain nearly identical information, while individually uninformative features may become useful jointly. For example, if two independent, uniformly random binary inputs determine a target through exclusive OR, each input individually has zero mutual information with the target, but the pair determines it completely.

Conditional mutual information addresses the additional information a variable contributes after other variables are known:

I(Y;X∣Z)=H(Y∣Z)−H(Y∣X,Z).I(Y;X\mid Z)=H(Y\mid Z)-H(Y\mid X,Z).

Experimental design and active learning

In Bayesian experimental design, an experiment can be selected to maximize expected information gain about unknown quantities. The expectation accounts for possible outcomes before the experiment is performed.

In active learning, a model may select examples whose labels are expected to reveal the most about its uncertain parameters or predictions. High uncertainty about an individual label is not always equivalent to high information gain: the uncertainty may reflect irreducible randomness rather than uncertainty that further observations can resolve.

Text classification

In natural language processing, the presence or absence of a term can be treated as a feature, and its information gain can measure its association with document classes. Such scores depend on the dataset’s class proportions and term frequencies; they do not measure a word’s intrinsic linguistic importance.

Limitations and alternative criteria

Bias toward many-valued features

Empirical information gain tends to favor splits with many branches. A unique identifier can create one pure child per training example, achieving maximal training gain without providing useful prediction for new cases. More generally, selecting among many candidate splits can exploit chance patterns in training data.

The gain ratio, used in C4.5, normalizes gain by the entropy of the branch assignment:

GainRatio⁡(D,S)=IG⁡(D,S)−∑j∣Dj∣∣D∣log⁡2∣Dj∣∣D∣.\operatorname{GainRatio}(D,S) = \frac{\operatorname{IG}(D,S)} {-\sum_j \frac{|D_j|}{|D|} \log_2\frac{|D_j|}{|D|}}.

It is undefined when the denominator is zero. Normalization can introduce other preferences, including sensitivity to very unbalanced splits, so gain ratio is typically used with additional selection rules rather than as an unrestricted replacement.

Estimation and generalization

Information gain computed from finite data is an estimate of population dependence. Sparse categories, small samples, and extensive split searching can exaggerate apparent associations. Continuous-variable estimates also depend on methods such as discretization or density estimation.

A large training gain does not establish generalization. Tree pruning, sample-size restrictions, and regularization can limit overfitting. Feature selection must also remain within the training portion of an evaluation procedure; using held-out labels to select features causes data leakage.

Other split objectives

Classification trees may instead use Gini impurity or other objectives. These criteria can favor similar splits but are not identical to Shannon information gain. Regression trees commonly minimize squared error or reduce variance; the term “gain” in such systems may refer to objective improvement rather than an information-theoretic quantity.

Information gain is also distinct from practical value. A highly informative observation may be costly, unavailable at prediction time, or irrelevant to the decision being made.

Historical development

The mathematical basis comes from Claude Shannon’s 1948 formulation of information theory, which established entropy as a measure of uncertainty. Information-based splitting became prominent in machine learning through J. Ross Quinlan’s ID3 decision-tree algorithm, described in his 1986 paper Induction of Decision Trees. His later C4.5 system used gain ratio to address the preference of unnormalized information gain for attributes with many outcomes.

Bayesian uses connect the concept to a separate tradition of statistical experimental design, in which observations are evaluated by how much they are expected to change knowledge about unknown quantities.