Information gain in decision trees

DefinitionInformation gain of a split#✓fully proved

Let \(p\) be a joint probability law on \(\alpha \times \beta\) with \(\alpha\) and \(\beta\) finite, the law of an attribute \(X\) (first coordinate) and a label \(Y\) (second coordinate). The information gain of splitting on \(X\) for predicting \(Y\) is the real number \(H(Y) - H(Y \mid X)\), where \(H(Y)\) is the Shannon entropy in bits of the marginal law of \(Y\) and \(H(Y \mid X)\) is the conditional entropy in bits of \(Y\) given \(X\) under \(p\).

noncomputable def infoGain (p : PMF (α × β)) : ℝ :=
  shannonEntropy (p.map Prod.snd) - finiteConditionalEntropy p

Uses 2 · Used by 4

Statement usesConditional entropy of a finite joint law · Shannon entropy

Used byInformation gain in terms of entropies · Zero information gain means independence · No split has negative information gain · Information gain is mutual information

TheoremInformation gain in terms of entropies#✓fully proved

Let \(p\) be a joint probability law on \(\alpha \times \beta\) with \(\alpha\) and \(\beta\) finite, and let \(p_X\) and \(p_Y\) be its marginal laws on \(\alpha\) and on \(\beta\). Writing \(H\) for Shannon entropy in bits, the information gain of \(p\) equals \(H(p_X) + H(p_Y) - H(p)\).

theorem infoGain_eq (p : PMF (α × β)) :
    infoGain p = shannonEntropy (p.map Prod.fst) + shannonEntropy (p.map Prod.snd) -
      shannonEntropy p

Uses 4 · Used by 1

Statement usesInformation gain of a split · Shannon entropy

Proof usesConditional entropy of a finite joint law · Chain rule for entropy

Used byInformation gain is mutual information

TheoremNo split has negative information gain#✓fully proved

For every joint probability law \(p\) on \(\alpha \times \beta\) with \(\alpha\) and \(\beta\) finite, the information gain of \(p\) is at least \(0\).

theorem infoGain_nonneg (p : PMF (α × β)) : 0 ≤ infoGain p

Uses 4 · Used by 1

Statement usesInformation gain of a split

Proof usesConditional entropy of a finite joint law · Conditioning does not increase entropy · Shannon entropy

Used byZero information gain means independence

TheoremInformation gain is mutual information#✓fully proved

Let \(\alpha\) and \(\beta\) be finite sets carrying σ-algebras in which singletons are measurable, and let \(p\) be a joint probability law on \(\alpha \times \beta\). The information gain of \(p\), regarded as an element of \([0, \infty]\), equals the mutual information in bits of \(p\) viewed as a probability measure on \(\alpha \times \beta\).

theorem ofReal_infoGain (p : PMF (α × β)) :
    ENNReal.ofReal (infoGain p) =
      measureMutualInformation (⟨p.toMeasure, inferInstance⟩ : ProbabilityMeasure (α × β))

Uses 5 · Used by 1

Statement usesInformation gain of a split · Mutual information of a joint probability measure

Proof usesInformation gain in terms of entropies · Mutual information of a finite joint law · Shannon entropy

Used byZero information gain means independence

TheoremZero information gain means independence#✓fully proved

Let \(\alpha\) and \(\beta\) be finite sets carrying σ-algebras in which singletons are measurable, and let \(p\) be a joint probability law on \(\alpha \times \beta\). The information gain of \(p\) is zero if and only if \(p\), as a measure, equals the product of its marginal law on \(\alpha\) and its marginal law on \(\beta\); that is, exactly when the attribute (first coordinate) and the label (second coordinate) are independent.

theorem infoGain_eq_zero_iff (p : PMF (α × β)) :
    infoGain p = 0 ↔
      p.toMeasure = (p.map Prod.fst).toMeasure.prod (p.map Prod.snd).toMeasure

Uses 5

Statement usesInformation gain of a split

Proof usesNo split has negative information gain · Information gain is mutual information · Mutual information of a joint probability measure · Mutual information vanishes exactly under independence

5 fully proved

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.