Noesis
2.3.2Tree-Based & Instance Methods

Entropy and information gain

1,752 words8 min readdifficulty · medium6 backlinks
🇮🇳 Yeh note Hinglish mein padho →

WHAT are we measuring?

WHY this exact formula? We want a number that is:

  1. 00 when we are certain (one class has p=1p=1),
  2. large when we are maximally confused,
  3. additive for independent information.

These three requirements force a log⁡\log shape. Let's derive it.

HOW to derive entropy from scratch

We demand two properties:

  • Certainty carries no info: I(1)=0I(1)=0.
  • Independent events add: if two independent things happen with probs pp and qq, the joint prob is pqpq, and total surprise should add: I(pq)=I(p)+I(q)I(pq) = I(p)+I(q).

The only continuous function turning multiplication into addition is the logarithm: I(p)=−log⁡bp.I(p) = -\log_b p. The minus sign makes it positive (since p≤1⇒log⁡p≤0p\le 1 \Rightarrow \log p \le 0). Choosing base b=2b=2 gives bits.

Entropy is just the average surprise over the distribution: H(S)=E[I]=∑ipi (−log⁡2pi)=−∑ipilog⁡2pi.H(S) = \mathbb{E}[I] = \sum_i p_i \,(-\log_2 p_i) = -\sum_i p_i \log_2 p_i.

Figure — Entropy and information gain

Information Gain

WHY the weights ∣Sv∣/∣S∣|S_v|/|S|? After splitting, a random example lands in child vv with probability ∣Sv∣/∣S∣|S_v|/|S|. The expected leftover entropy is the weighted average of child entropies. Gain = parent entropy − expected child entropy. It can never be negative (splitting cannot increase uncertainty, by concavity of HH).

Worked Example 1 — a single split

Dataset: 14 examples, 9 "Yes", 5 "No". Attribute Wind ∈ {Weak, Strong}.

  • Weak (8 examples): 6 Yes, 2 No
  • Strong (6 examples): 3 Yes, 3 No

Step 1 — parent entropy. H(S)=−914log⁡2914−514log⁡2514≈0.940H(S) = -\tfrac{9}{14}\log_2\tfrac{9}{14} - \tfrac{5}{14}\log_2\tfrac{5}{14} \approx 0.940 Why this step? We need the "mess before the question" as a baseline.

Step 2 — child entropies. H(Weak)=−68log⁡268−28log⁡228≈0.811H(\text{Weak}) = -\tfrac{6}{8}\log_2\tfrac{6}{8} - \tfrac{2}{8}\log_2\tfrac{2}{8} \approx 0.811 H(Strong)=−36log⁡236−36log⁡236=1.000H(\text{Strong}) = -\tfrac{3}{6}\log_2\tfrac{3}{6} - \tfrac{3}{6}\log_2\tfrac{3}{6} = 1.000 Why? Strong is a 50/50 mess → maximal 1 bit; Weak leans Yes → less messy.

Step 3 — weighted child entropy. 814(0.811)+614(1.000)≈0.464+0.429=0.892\tfrac{8}{14}(0.811) + \tfrac{6}{14}(1.000) \approx 0.464 + 0.429 = 0.892 Why weight? Bigger children matter more to the average outcome.

Step 4 — gain. IG=0.940−0.892≈0.048 bitsIG = 0.940 - 0.892 \approx 0.048 \text{ bits} Why small? Wind barely cleaned things up — probably not the best split.

Worked Example 2 — a perfect split

3 Yes, 3 No. Attribute splits into: {3 Yes} and {3 No}.

  • H(S)=1H(S) = 1 bit (perfect 50/50).
  • Each child is pure → H=0H=0.
  • Weighted child entropy =12(0)+12(0)=0= \tfrac12(0)+\tfrac12(0)=0.
  • IG=1−0=1IG = 1 - 0 = 1 bit.

Why maximal? One question removed all uncertainty — the dream split.

Forecast-then-Verify

Common Mistakes (Steel-manned)

Gini — the fast cousin (WHY it exists)

Active Recall

Recall Why does entropy use a logarithm?

Because we want independent information to add: I(pq)=I(p)+I(q)I(pq)=I(p)+I(q). Only −log⁡-\log turns the multiplication of independent probabilities into a sum. Base 2 ⇒ bits.

Recall Can information gain be negative?

No. HH is concave, so the weighted average of child entropies never exceeds the parent's. Worst case IG =0=0 (a useless split).

Recall What value maximizes binary entropy and what is it?

p=0.5p=0.5, giving H=1H=1 bit.

Recall Explain like I'm 12

Imagine a bag of red and blue marbles. If they're all red, you're never surprised pulling one — that's zero mess (entropy 0). If it's half-and-half, every pull is a coin flip — maximum mess (1 bit). A good "question" splits the bag so each smaller bag is mostly one color. Information gain is how much messiness you removed by asking. The tree keeps asking the question that removes the most mess first.

Mnemonic

Flashcards

What does entropy measure in a decision tree node?
The impurity/uncertainty of the class distribution; 0 = pure, max when classes are equally likely.
Write the entropy formula.
H(S)=−∑ipilog⁡2piH(S) = -\sum_i p_i \log_2 p_i (bits).
Why a logarithm in entropy?
So independent information adds: I(pq)=I(p)+I(q)I(pq)=I(p)+I(q), uniquely satisfied by −log⁡-\log.
Binary entropy at p=0.5?
1 bit (maximum).
Information gain formula?
IG(S,A)=H(S)−∑v∣Sv∣∣S∣H(Sv)IG(S,A)=H(S)-\sum_v \frac{|S_v|}{|S|}H(S_v).
Why weight child entropies by ∣Sv∣/∣S∣|S_v|/|S|?
It's the expected leftover entropy — probability an example falls in that child.
Can information gain be negative?
No; by concavity of entropy, min gain is 0.
What bias does information gain have and its fix?
Bias toward high-cardinality attributes; fix with Gain Ratio (IG / SplitInfo).
Gini impurity formula?
Gini=1−∑ipi2Gini = 1 - \sum_i p_i^2; log-free, used by CART.
SplitInfo formula?
−∑v∣Sv∣∣S∣log⁡2∣Sv∣∣S∣-\sum_v \frac{|S_v|}{|S|}\log_2\frac{|S_v|}{|S|}.

Connections

  • Decision Trees — entropy/IG drive node splitting.
  • Gini Impurity — alternative impurity measure (CART).
  • ID3 and C4.5 Algorithms — use IG and Gain Ratio.
  • Cross-Entropy Loss — same −∑plog⁡q-\sum p\log q shape in neural nets.
  • KL Divergence — entropy generalized to compare distributions.
  • Overfitting and Pruning — pure leaves via IG can overfit.

Concept Map

I(pq)=I(p)+I(q)

self-info

average over p_i

base 2 log

max when equal

one class only

2-class version

baseline mess

subtract weighted

weight Sv over S

pick highest

never negative

Surprise I(p)

Logarithm shape

I(p) = -log2 p

Entropy H(S)

Units in bits

Maximal uncertainty

H = 0 pure

Binary entropy H(p)

Information Gain

Weighted child entropy

Child landing prob

Chosen tree split

Concavity of H

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho ek node ke andar Yes/No labels ka mixture pada hai. Entropy batati hai ki ye mixture kitna "messy" hai. Agar saare same class ke hain (all Yes ya all No), entropy = 0, matlab bilkul pure, koi confusion nahi. Agar 50-50 hai, entropy = 1 bit — maximum confusion, jaise fair coin flip. Formula hai H=−∑pilog⁡2piH = -\sum p_i \log_2 p_i, aur log isliye aata hai kyunki hum chahte hain ki independent information add ho — sirf log hi multiplication ko addition mein badalta hai.

Information gain ka matlab: koi feature (question) puchhne se entropy kitni kam hui. Gain = parent ki entropy minus children ki weighted average entropy. Weight isliye kyunki bada child zyada matter karta hai. Decision tree har step pe wahi split chunta hai jiska gain sabse zyada ho — matlab jo sabse zyada confusion saaf kare.

Ek dhyan dene wali baat: information gain high-cardinality features (jaise ID number) ki taraf biased hai, kyunki wo har row ko alag pure group mein daal deta hai — fake high gain. Iska fix hai Gain Ratio, jo split ke size ko penalize karta hai. Aur agar speed chahiye to Gini use karo — log nahi lagta, fast hota hai, aur usually same split choose karta hai.

Go deeper — visual, from zero

D1FoundationsEvery symbol from zero · 1,827 wordsD2Visual walkthroughThe derivation in pictures · 1,807 wordsD3Worked examplesEvery scenario covered · 3,578 wordsD4ExercisesGraded, full solutions · 3,041 wordsD5Question bankConcept traps, quick reveals · 1,493 words

Test yourself — Tree-Based & Instance Methods

L1 RecognitionL2 RecallL3 ProductionL4 ApplicationL5 Mastery

Connections

Overfitting in decision treesAI-ML · 2.3.5Gini impurityAI-ML · 2.3.3Log-loss - binary cross-entropyAI-ML · 2.2.10Entropy and KL divergenceAI-ML · 1.3.18Sample spaces, events, and axioms of probabilityAI-ML · 1.3.1Entropy and KL divergenceAI-ML · 1.3.18Gini impurityAI-ML · 2.3.3Perplexity as a metricAI-ML · 4.2.9Soft Actor-Critic (SAC)AI-ML · 5.2.11Lower bound for comparison sorts — Ω(n log n) proof via decision treesCoding · 3.6.9