Entropy and information gain — Hinglish notes

2.3.2 · AI-ML › Tree-Based & Instance Methods

HUM KYA MEASURE KAR RAHE HAIN?

YE EXACT FORMULA KYUN? Hum ek aisa number chahte hain jo:

$0$ ho jab hum certain hon (ek class ki $p = 1$ ho),
bada ho jab hum maximally confused hon,
independent information ke liye additive ho.

Ye teeno requirements milke ek $lo g$ shape ko force karti hain. Chaliye isse derive karte hain.

ENTROPY KO SCRATCH SE KAISE DERIVE KAREIN

Hum do properties demand karte hain:

Certainty mein koi info nahi: $I (1) = 0$ .
Independent events add hote hain: agar do independent cheezein probs $p$ aur $q$ se hoti hain, to joint prob $pq$ hogi, aur total surprise add honi chahiye: $I (pq) = I (p) + I (q)$ .

Sirf ek hi continuous function hai jo multiplication ko addition mein convert karta hai — logarithm: $I (p) = - lo g_{b} p .$ Minus sign ise positive banata hai (kyunki $p \leq 1 \Rightarrow lo g p \leq 0$ ). Base $b = 2$ chunne se bits milte hain.

Entropy sirf distribution par average surprise hai: $H (S) = E [I] = \sum_{i} p_{i} (- lo g_{2} p_{i}) = - \sum_{i} p_{i} lo g_{2} p_{i} .$

Information Gain

WEIGHTS $∣ S_{v} ∣/∣ S ∣$ KYUN? Splitting ke baad, ek random example child $v$ mein probability $∣ S_{v} ∣/∣ S ∣$ se land karta hai. Expected leftover entropy, child entropies ka weighted average hai. Gain = parent entropy − expected child entropy. Ye kabhi negative nahi ho sakta (splitting uncertainty badha nahi sakti, $H$ ki concavity ki wajah se).

Worked Example 1 — ek 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) = - \frac{9}{14} lo g_{2} \frac{9}{14} - \frac{5}{14} lo g_{2} \frac{5}{14} \approx 0.940$ Ye step kyun? Humein question se pehle ka "mess" ek baseline ki tarah chahiye.

Step 2 — child entropies. $H (Weak) = - \frac{6}{8} lo g_{2} \frac{6}{8} - \frac{2}{8} lo g_{2} \frac{2}{8} \approx 0.811$ $H (Strong) = - \frac{3}{6} lo g_{2} \frac{3}{6} - \frac{3}{6} lo g_{2} \frac{3}{6} = 1.000$ Kyun? Strong 50/50 mess hai → maximal 1 bit; Weak Yes ki taraf jhukta hai → kam messy.

Step 3 — weighted child entropy. $\frac{8}{14} (0.811) + \frac{6}{14} (1.000) \approx 0.464 + 0.429 = 0.892$ Weight kyun? Bade children average outcome par zyada matter karte hain.

Step 4 — gain. $I G = 0.940 - 0.892 \approx 0.048 bits$ Itna chhota kyun? Wind ne cheezein barely saaf ki — shayad best split nahi hai ye.

Worked Example 2 — ek perfect split

3 Yes, 3 No. Attribute split karta hai: {3 Yes} aur {3 No} mein.

$H (S) = 1$ bit (perfect 50/50).
Har child pure hai → $H = 0$ .
Weighted child entropy $= \frac{1}{2} (0) + \frac{1}{2} (0) = 0$ .
$I G = 1 - 0 = 1$ bit.

Maximal kyun? Ek question ne saari uncertainty remove kar di — dream split.

Forecast-then-Verify

Common Mistakes (Steel-manned)

Gini — fast cousin (YE KYUN EXIST KARTA HAI)

Active Recall

Recall Entropy logarithm kyun use karta hai?

Kyunki hum chahte hain independent information add ho: $I (pq) = I (p) + I (q)$ . Sirf $- lo g$ hi independent probabilities ke multiplication ko sum mein convert karta hai. Base 2 ⇒ bits.

Recall Kya information gain negative ho sakta hai?

Nahi. $H$ concave hai, isliye child entropies ka weighted average kabhi parent se zyada nahi hota. Worst case IG $= 0$ (ek useless split).

Recall Kaunsi value binary entropy maximize karti hai aur wo kya hai?

$p = 0.5$ , jo $H = 1$ bit deta hai.

Recall 12 saal ke bachche ko explain karo

Socho ek bag mein laal aur neele marbles hain. Agar sab laal hain, to ek nikaalte waqt kabhi surprise nahi hoga — ye hai zero mess (entropy 0). Agar aadhe-aadhe hain, to har baar nikalna ek coin flip hai — maximum mess (1 bit). Ek accha "question" bag ko aisa split karta hai ki har chhota bag mostly ek color ka ho. Information gain ye hai ki poochh ke kitna messiness remove hua. Tree pehle wahi question poochna rakhta hai jo sabse zyada mess remove karta hai.

Mnemonic

Flashcards

Decision tree node mein entropy kya measure karta hai?

Class distribution ki impurity/uncertainty; 0 = pure, max jab classes equally likely hon.

Entropy formula likho.

H (S) = - \sum_{i} p_{i} lo g_{2} p_{i}

(bits).

Entropy mein logarithm kyun?

Taaki independent information add ho:

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

, jo uniquely

- lo g

se satisfy hota hai.

p=0.5 par binary entropy?

1 bit (maximum).

Information gain formula?

I G (S, A) = H (S) - \sum_{v} \frac{∣ S _{v} ∣}{∣ S ∣} H (S_{v})

Child entropies ko

∣ S_{v} ∣/∣ S ∣

se weight kyun karte hain?

Ye expected leftover entropy hai — probability ki ek example us child mein girega.

Kya information gain negative ho sakta hai?

Nahi; entropy ki concavity se, minimum gain 0 hai.

Information gain mein kaunsa bias hai aur iska fix kya hai?

High-cardinality attributes ki taraf bias; Gain Ratio (IG / SplitInfo) se fix karo.

Gini impurity formula?

G ini = 1 - \sum_{i} p_{i}^{2}

; log-free, CART use karta hai.

SplitInfo formula?

- \sum_{v} \frac{∣ S _{v} ∣}{∣ S ∣} lo g_{2} \frac{∣ S _{v} ∣}{∣ S ∣}

Connections

Decision Trees — entropy/IG node splitting drive karte hain.
Gini Impurity — alternative impurity measure (CART).
ID3 and C4.5 Algorithms — IG aur Gain Ratio use karte hain.
Cross-Entropy Loss — neural nets mein same $- \sum p lo g q$ shape.
KL Divergence — entropy generalized to compare distributions.
Overfitting and Pruning — IG se pure leaves overfit kar sakti hain.